多跳无线网络可用带宽检测研究

韩盼盼 张巍

摘要：带宽是网络路径的重要参数之一，带宽测量的发展有助于改善网络应用程序和提高服务的质量，其在容量分配、服务质量管理、服务器路由选择等领域均有广泛应用。文章提出一种基于二分法的多跳无线网络可用带宽自适应检测方法，该方法利用二分法思想，不仅可以测量提高无线网络可用带宽测量值的精度，还能提高多跳无线网络的可靠性，减少网络的负载，改善网络的性能。

关键词：带宽；二分法；自适应检测

随着Internet的快速发展，网络规模不断扩大，网络应用在为人们的生活带来便利的同时，也对网络的服务质量提出了更高要求。由于网络规模巨大，拓扑结构复杂，使得研究者难以对网络分析建立起精确的数学模型，因此网络测量成为网络行为学研究的主要途径。多跳无线网络中节点通过无线链路以多跳的方式进行通信，随着人们对信息服务需求的快速增长，近年来多跳无线网络的研究和应用得到不断的扩展，以往人们对多跳无线网络的研究主要集中在如何高效地为网络中的节点提供充分连接上，而随着网络中有服务质量（QoS，Quality of Service）要求的多媒体业务逐渐增多，如何支持和保证业务的QoS要求成为多跳无线网络研究中亟待解决的问题，在多跳无线网络中，获取传输路径上的可用带宽信息是支持和保证业务QoS的重要前提。通过可用带宽信息才有可能实行对带宽敏感业务的带宽预留和QoS路由接纳控制等操作，才有可能最大化地利用网络资源，同时由于可用带宽与传输延时等其他QoS参数有着紧密的联系，获取可用带宽的信息还有助于优化其他QoS参数的设计。

目前，可用带宽测量技术主要分为两大类：基于探测分组间隔模型的方法（Probe Gap Model，PGM）和基于探测分组速率模型的方法（Probe Rate Model，PRM），但这两者之间各有优缺点。本文针对现有技术的不足，提出一种可以减少对网络负载压力，同时也缩短了测量时间的基于二分法的多跳无线网络可用带宽自适应检测方法。

1 多跳无线网络传统下载方法与分析

PGM方法是通过计算探测分组的输出间隔和输入间隔的时间差，估计出背景业务流量的大小，再用己知路径带宽减去估计得到的背景业务流量的大小得到可用带宽测量值，PGM方法前提是己知路径的容量大小，其主要代表有IGI，Spruce等测量技术。

PRM方法是通过在网络中引入拥塞通过分析探测分组的时延情况来估算可用带宽，得到其测量值，PRM方法的优点是概念简单，其关键点是如何准确地捕捉到时延变化的转折点，其主要代表有TOPP，Path Chirp等测量技术。

2 基于二分法的多跳无线网络可用带宽自适应检测方法

2.1 基于二分法的多跳无线网络可用带宽自适应检测方法

基于二分法的多跳无线网络可用带宽自适应检测方法包括如下步骤：

（SI）源主机利用二分法的思想将一串具有大范围速率的包串（如典型网络中为l-IOOMbps）发送到目的主机进行无线网络的可用带宽测量，包串中各数据包对应的速率呈线性形式递增的，其递增的斜率参数为h，参数h的大小由用户的需求和网络来决定，当用户对网络需求量较大，适当地提高h的数值，当用户对网络的需求量较小，适当地降低h的数值，然后根据从目的主机返回的排队时延的信息得到可用带宽估测值。其中第i次测量所发包串的包速率范围被划分成2m+l个区域，即B1^（i），B2^（i），…，Bn^（i），…，BN^（i），N=2^m+l，m，i为正整数，其中B_n=[b_n，l，b_n，2]，当i=l时，中间区域B_（n+1）/2^（i）典型取值的范围为45-60源主机。首先发送中间区域B_（n+1）/2^（i）范围的数据包串进行第i次的测量，被测目的主机将包串的排队时延信息反馈给源主机。

（l）当返回的排队时延含有转折点，则可根据转折点计算得到源主机到目的主机之间的可用带宽的数值，而可用带宽的数值的获得是通过源主机发送包与包之间的间隔呈线性形式递增的包串，然后根据目的主机反馈的包串的排队时延的信息对每个包的可用带宽做一个估测值Ek^（m），然后对多个Ek^（m）取加权平均值，作为这次测量得到的可用带宽的估测值D^（m），即： 源主机需要将从目的主机反馈回来的排队时延信息分割成属于离群区间和不属于离群区间，假设q^k是第k个包的排队时延，每一个q^kk+1

（3）如果返回的排队时延不属于步骤（l）和（2）的情况，则源主机重新选取包速率范围被划分的区域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B_N+1/2ⁱ，B_N^（i+1）=B_N^（i），重新步骤（S1）进行第（i+1）次测量。

（4）重复上述步骤，当N值为1或者返回排队时延含有转折点时，停止上述步骤。当返还的排队时延含有转折点时可以分析计算得到源主机到目的主机之间的可用带宽的估计值；当返回的排队时延没有转折点并且变化幅度很大，则源主机重新选取包速率范围被划分的区域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B₁^（i），B_N^（i+1）=B_n+1/2^（i）。回到步骤（SI）进行第（i+1）次测量；当返回的排队时延不属于所述上述2种情况，则源主机重新选取包速率范围被划分的区域，即B₁^（i+1），B₂^（i+1），…，B_n^（i+1），…，B_N^（i+1），其中B₁^（i+1）=B_（N+1）/2^（i），B_N^（i+1）=B_N^（i），回到步骤（SI）进行第（i+1）次测量，当N值为l或返回排队时延含有转折点，计算得到源主机到目的主机之间可用带宽的估计值。

（S2）源主机每隔t时间向目的主机发送数据包串进行另外一次测量，该次测量的数据包串速率的范围是上次测得可用带宽数值的±M范围，M取用带宽数值的7%。t取决于网络的实际情况，数据包串之间的包与包的之间的时间间隔t₁等于无线网络中瓶颈链路的带宽容量C除以前一个包发送的速率v，即t₁=C/v，该次测量的数据包串速率范围是上次测得可用带宽数值的±n的范围，n可取可用带宽数值的7%。

（S3）每次测量后，被测量的目的主机将把本次测量是否成功以及数据包串的排队时延信息反馈回源主机，然后源主机根据反馈回的排队时延信息计算得到这次测量可用带宽的数值或者调整探测包串速率范围的大小；当源主机接收到的是数据包串的测量成功的信息，即反馈回来的排队时延信息经分析处理存在转折点时，则重复步骤（S2）（S3），进行下一次的测量，经过多次测量以后，根据从目的主机返回的排队时延信息对网络的可用带宽计算估测值E_m，将这些数据取平均值得出可用带宽的估测值E_m⁰，然后选取处于估测值（1±b%） XE_m⁰的范围的数据，其中b的典型取值为30，计算这些数据的平均值，得出新的可用带宽的估计值E_m¹，并且求出这些数据的方差D₁。如果Dl>c，其中c的大小由系统对测量数据的精度来决定，c可取0.3～0.5，则选取出处于估测值（1±（b%～ 5%））E_m¹的范围的数据，计算其平均值，并得到新的带宽估计值E_m²以及对应的方差D2，按调整范围依次缩小5%的规律重复上述步骤，直到第n次选取的数据方差D_n^c。当源主机接收到的是数据包串的测量不成功的信息，则将上一次的探测包串速率范围变化±A，然后发送调整后的数据包，进行另外一次的测量，同时计数器将测量不成功的次数加1，当测量连续k次不成功，取4-6倍K，则源主机由步骤（SI）开始进行重新测量。步骤（S3）中的当源主机接收到的是数据包串的测量不成功的信息，探测包串速率变化范围变化±A采用的变化原则是：当没有变化或者变化幅度很小，则源主机调整包串速率范围使得数据包串的范围上下限分别增大A，A取5%，并且重新发送数据包串进行测量；当没有转折点并且变化幅度很大，则源主机调整包串速率范围使得数据包串的范围上下限分别减小A，A取5%，并且重新发送数据包串进行测量。

2.2 基于二分法的多跳无线网络可用带宽自适应检测方法的优点

（1）每次的测量都是发送以上次的测量分析得到的可用带宽数值为中心的一定速率范围的包串，这样可以减少对网络的负载压力，同时也缩短了测量的时间。（2）根据反馈回来的当前网络信息，自适应的调整包串中包与包之间的间隔发送时间，不仅可以实现对无线网络可用带宽的实时监测，还能减少数据包丢失和差错率，改善了网络的性能。

3 结语

带宽是衡量IP网络性能重要的度量参数之一，对其准确测量与估计是流量工程中网络资源控制与QoS中接入控制必须解决的问题。本文基于二分法的多跳无线网络可用带宽自适应检测方法，不仅可以实现对无线网络可用带宽实时监测，还能减少差错率和数据包的丢失，改善了网络的性能。