一种改进离群区间计算的PRM带宽测量算法*

王志钊 陆余良 杨国正 关永耀

(1.电子工程学院, 合肥,230037;2. 中国人民解放军94647部队,福州,350001)

一种改进离群区间计算的PRM带宽测量算法*

王志钊1陆余良1杨国正1关永耀2

(1.电子工程学院, 合肥,230037;2. 中国人民解放军94647部队,福州,350001)

主动式网络路径可用带宽测量是目前网络路径带宽测量使用的主要方法，与被动式网络路径可用带宽测量相比，具有更高的灵活性且部署方便。为解决主动式网络路径可用带宽测量定义不明确、通用性不强、协议不规范和结果不准确等问题，规范定义了探测通信协议和报文结构，建立了较为完整、统一和规范的主动式网络路径可用带宽测量框架，提出了序列时延增加度和基于序列时延增加度的离群区间计算方法，改进了网络背景流量分析方法，降低了背景流量对网络路径可用带宽测量的干扰，最后使用NS2仿真对比验证了该算法的有效性。

序列时延增加度；离群区间；可用带宽测量；网络测量

引 言

网络带宽测量是指通过主动或被动网络测量技术，设置或观测数据发送源的发送速率、包大小、发送间隔及其他参数，获取测量点与目标设备的数据流量、丢包率、包间隔和传输时延等测量数据的变化特征，利用数据发送速率与路径带宽相近时，测量数据的变化规律，根据探测包间隔模型(Probe gap model,PGM)和探测包速率模型(Prober rate model,PRM)等测量模型，对路径带宽进行分析与获取。被动网络测量对通过网络监测设备的网络数据、流量和传输时延等信息进行被动监测和收集，需要在大范围内部署专门的网络测量设备，实现成本较高而且不利于更新和升级，但对网络正常通信数据流产生的影响较小，测量结果较为准确。而主动测量则通过主动向网络中发送探测数据来测量数据接收速率、丢包率和传输时延等信息，不需要大范围部署网络监测设备，易于实现和更新，缺点是会对正常网络通信数据流产生影响，测量结果准确度相对较低。在实际对网络路径带宽进行测量时，出于规模成本和实现难度的考虑，通常采用主动网络测量的方法来实现。

根据带宽测量实现原理的不同，主动带宽测量模型可分为PGM和PRM两种。PGM假设路径中仅存在一条瓶颈链路，根据探测报文发送间隔和接收间隔的变化来估算路径可用带宽，优点是速度快、测量数据量小、对正常网络通信流量影响较小，缺点是实际网络路径难以满足只有一条瓶颈链路，测量准确度不高，具体实现有Delphi[1]，IGI/PTR[2]，Spruce[3]和CProbe[4]等；PRM则基于自拥塞的原理，调整测量数据发送速率，当测量数据发送速率接近或者高于路径可用带宽时，测量数据的传输时延会发生较大变化，选择离群区间进行计算测量网络路径可用带宽。优点是准确度较高，适应实际网络路径的复杂性，缺点则是测量数据量较大，会对正常网络通信流量产生较大影响，具体实现则有：Pathload[5]，Pathchirp[6]，基于报文对序列的测量方法(Trains of packet pairs，TOPP)[7],基于非相邻探测包间隔的测量方法(Gaps of non-adjacent probing packets，GNAPP)[8]等。以上带宽测量实现方法从不同角度出发，针对测量准确度、时间效率、注入数据量及网络路径复杂性等不同需求偏向时，各有其优势和不足。PRM在测量数据影响不大、准确性要求高时比较适用，但是目前PRM的实现方法，缺乏在数据发送速率接近路径可用带宽时，离群区间选择受背景流量影响的详细分析，因此测量结果精确度不高。本文针对该问题，结合背景流量对带宽测量过程中传输延迟的影响，提出了一种基于测量序列时延增加度的离群区间计算方法，有效提高了PRM带宽测量的精确度。

1 基本概念和相关工作

1988年,Jacobson 在文献[9]中提出了“Window Flow Control ′Self-clocking′”模型，并对带宽测量相关概念进行了初步说明。现对带宽测量的相关概念进行重新明确，对于由链路L1,L2,…，Ln组成的一条网络路径，将每一跳链路Li在单位时间内能达到的最大数据传输速率定义为链路带宽Ci，其中数据传输速率为网络层数据的传输速率，单位是bit/s，由此可以定义网络路径带宽B为链路L1,L2,…，Ln的最小带宽。

定义1 路径带宽B=min(C1,C2,…，Cn)

由于在网络链路中存在其他业务流量，将链路Li中不影响其他业务流量时能达到的最大数据传输速率定义为链路可用带宽ABi，同样，将网络路径的可用带宽AB定义为L1,L2,…，Ln的最小可用带宽。

定义2 路径可用带宽AB=min(AB1,AB2,…，ABn)

刘敏在文献[10]中从链路空闲率的角度，对链路在(t1，t2)时段内的可用带宽ABi(t1，t2)进行数学定义如下。

(1)

PGM是根据包发送和接收时间间隔的变化来计算瓶颈链路带宽，如图1所示，设瓶颈链路带宽为C，包长为L，则可以根据数据接收时间差Δt来计算C=L/Δt。该测量方法发送测量数据量小，速度快，但仅针对网络路径中只有一条瓶颈链路时有效，且在实际测量中，由于背景流量的存在，其测量结果并不是路径带宽B，而是在多路流量下的渐近散布率(Asymototicdispersionrate,ADR)[11]。

图1 PGM测量模型Fig．1 PGM Model

PRM以自拥塞原理为基础，调整测量数据的发送速率并计算数据的单向传输延迟(One-way delay, OWD)，Pathload根据定义4和5来判断数据流发送速率是否达到路径可用带宽[12]。

定义4 流成对比测试值(Stream pairwise comparison test,SPCT)

(2)

定义5 流成对差测试值(Stream pairwise difference test,SPDT)

(3)

Pathchirp以指数级降低包序列中的发送时间间隔，根据单向传输延迟的变化情况，将第k+1个测量报文的单向延迟q(k+1)比第k个测量报文单向延迟q(k)增大时的k作为区间左边界，利用定义6确定子区间的右边界，将长度超过L的子区间定义为离群区间，然后利用离群区间对路径可用带宽进行估计。

定义6 离群区间确定方法

(4)

式中：F为延迟降低参数，对发送速率低于离群区间左边界的测量数据，路径可用带宽以离群区间左边界测量数据发送速率Ei为估计值，对发送速率高于离群区间右边界的测量数据，以离群区间右边界测量数据发送速率Ej来估计，离群区间内部测量数据的发送速率Ek为路径可用带宽估计值，然后利用定义7对路径可用带宽进行计算[6]。

定义7 可用带宽计算方法

(5)

Guerrero等采用K-means聚类方法降低背景流量干扰[13]，Aceto等提出了UANM测量架构改进测量方法[14]。目前国内外研究分别针对路径可用带宽测量方法和背景流量分析提出了相应的概念和计算方法，但仍存在处理突发性背景流量时错误率高，测量数据发送速率估计精确度低和聚类方法数据集依赖性强等问题。针对当前路径可用带宽测量算法的不足，本文利用多序列提高测量数据发送速率精度，将序列分窗口计算序列时延增加度对离群区间进行定位降低突发背景流量影响，提出了基于测量序列时延增加度的PRM可用带宽测量算法。

2 基于测量序列时延增加度的PRM可用带宽测量算法

2.1 测量收发通信协议与报文结构

图2 数据发送时间分布 Fig．2 Data transmission time distribution

对于1 000Mbps的网络适配器，1K字节的报文，其理论发送时间约为8μs。为了获取实际情况下，测量数据读取系统时间、填充和发送字节数组、循环判断与比较等处理时间带来的数据发送时间误差，利用配置为1 000Mbps网络适配器的计算机进行实验，连续发送100个长度为1K字节的UDP报文，对数据实际发送时间进行记录，并使用wireshark抓包工具监视和对比，100个测量报文的实际发送时间如图2所示。

通过对测量数据实际发送时间的分析，连续两个测量数据的发送时间间隔为9～12μs，符合网络适配器的发送速率。每连续发送约10个包，发送时间间隔会剧烈增大一次，增大幅度在529μs到903μs之间。如Ribeiro在文献[6]中所述，进程上下文的切换会对测量报文的收发带来影响，探测分组大小以及探测序列长度均会对探测结果产生影响[15]，不同软硬件配置及网络覆盖范围等实际因素也会对测量结果产生影响[16]。在测量报文发送与接收方式上，pathload采用以发送速率Rs发送若干报文列，接收端计算各报文列Spct和Spdt后，与发送端交互调整Rs。收发端的相互交互和报文发送速率的不断调整增加了发送报文时程序处理时间带来的误差，而pathchirp则采用以发送间隔指数级降低的方式，发送一组报文，该种方式降低了发送端和接收端的相互交互和发送速率的调整判断条件，但是单个报文的单向传输延迟变化不能够准确代表某发送速率下单向传输延迟的变化情况，通过序列分析能够提高准确性和抗噪声性[17]。

为了降低测量程序在发送和接收测量数据时对报文处理时间带来的干扰，减小收发端互操作带来的影响，提高测量数据发送时间、接收时间和单向传输延迟等获取和计算的准确度，本文提出了新的测量数据的发送、接收协议和测量报文的结构。根据网络OSI或TCP/IP协议分层标准，收发通信协议属于应用层协议，在UDP协议上层实现。测量过程分为两个阶段，如图3所示。

图3 收发端状态迁移图Fig．3 Sender and Receiver state transition diagram

第一个阶段是握手阶段，发送端和接收端的交互在第一个阶段完成，主要目的是发送端将测量需要的参数告知接收端，并通过3次握手数据报文的发送时间与接收时间对发送端和接收端的时钟偏差进行估计；第二个阶段是测量阶段，发送端按照发送速率递增的方法发送s个测量报文序列，每个测量序列由n个测量报文组成，第i个测量报文序列的发送速率与第i-1个测量报文序列发送速率关系为

(6)

根据收发通信协议的通信内容，测量报文分为三种类型：发送端握手报文、接收端握手确认报文和测量报文。因此将测量报文结构定义为：报文第1个字节代表发送报文端的状态，报文接收端根据发送端状态解析报文内容并调整接收端状态；第2～3个字节则声明测量报文的长度，接收端根据长度字段对缓冲区大小进行设置，并根据报文长度计算路径可用带宽；第4个字节作为保留字段；第5～8个字节用一个32位整数表示报文序列号，与发送时间间隔相关联；第9～12个字节用一个32位整数表示报文在序列内的序号，与序列时延增加度相关；第13～20个字节则用64位整数表示报文发送时间，以μs为单位，接收端接收到测量报文后，根据接收时间和本字段保存的报文发送时间，对报文的相对单向传输延迟进行计算。

2.2 序列时延增加度

考虑发送端以速率Rs向接收端发送测量报文序列，路径可用带宽为B，利用NS仿真环境对理想情况下测量报文序列的单向传输延迟的分布情况进行模拟，结果如图4和5所示。

图4 RsB时单向传输时延分布情况 Fig．4 One-way delay distribution when RsB

理想情况下，当发送速率小于路径可用带宽时，测量报文的owd不随报文序列发生变化，可以使用定义8进行计算，L代表报文长度。owd分布情况如图4所示。当发送速率大于路径可用带宽时，测量报文的owd随报文序列线性增加，第i+1个报文的单向传输时延owd(i+1)与第i个报文的单向传输时延关系利用定义(9)表示，其owd分布情况如图5所示。

定义8Rs

(7)

定义9Rs>B时单向传输时延关系

(8)

测量数据报文在实际网络中传输时，由于网络设备、背景流量等因素的影响，单向传输时延与理想情况有较大差别。为了从受背景流量等因素影响下的单向延迟数据中对测量报文发送速率和路径可用带宽的相对关系进行分析，pathload利用SPCT和SPDT来表征报文序列的单向时延逐渐增大的趋势，Pathchirp则利用定义6分析测量报文发送速率与路径可用带宽的相对关系。SPCT和SPDT以及定义6能够在一定程度上反映网络路径可用带宽和测量报文发送速率的关系，但是对不同方式背景流量的干扰，准确性会有所不同，不能够精确有效地适应各种背景流量状况。

算法1 序列时延增加度算法

输入: 序列单向传输时延d1,d2,…,dn；窗口个数k

输出: 序列时延增加度A

算法:

(1)分别计算每个窗口中单向传输时延的最小值

(2)消除背景流量影响，对于任意1≤x≤k，若存在x≤y≤k，满足window_min[y]≤window_min[x]，则认为x受背景流量干扰，其所处窗口的最小单向时延以window_min[y]为准，即window_min[x]=window_min[y]。

图6 单向传输时延分布 Fig．6 One-way delay distribution

图6为某发送速率下单向传输时延的分布情况。以图6为例对序列时延增加度进行分析计算，可在第61个测量报文处获取最低OWD为2 878 150μs，第81个测量报文处的最低OWD增大到2 878 200μs，第91个测量报文处的最低OWD增大到2 878 350μs。第61个测量报文代表对于发送速率为Rs的测量报文序列来说，受突发背景流量最小的测量报文，其单向传输时延为2 878 150 μs。而其后的第81个和第91个测量报文分别代表了随着测量报文的发送，若发送速率超过路径可用带宽，在突发背景流量影响最小的情况下，其OWD将逐步增大到2 878 200和2 878 350 μs。取窗口个数k=10，窗口最小单向传输时延结果如表1所示。

根据统计后获取到的递增窗口最小单向时延window_min[1]，window_min[2]，…，window_min[k]，其序列时延增加度用定义10表示，该公式对序列递增的程度及影响窗口数进行分析，得出序列的递增程度。

表1 窗口单向传输时延计算结果

定义10 序列时延增加度计算方法

(9)

以表1的数据进行计算，其序列时延增加度为0+0+0+0+0+0+0.5+0+0+1.5=2

2.3 基于序列时延增加度的离群区间和路径可用带宽计算

相对于SPCT和SPDT，序列时延增加度用来描述某发送速率下，连续发送的测量报文随报文增加其相对单向传输时延增加的程度。与Pathchirp所定义的离群区间不同，本文将离群区间定义为发送速率范围[Rsi,Rsj],范围长度大于L，且在此范围内序列单向时延增加度大于阀值A并连续增大。不同于文献[18]，探测序列发送速率采用按步长递增的方式，序列时延增加度能够精确测量出发送速率是否达到最大可用带宽，当发送速率达到离群区间的左边界Rsi时，表示发送速率已经达到可用最大可用带宽。基于序列时延增加度的离群区间和路径可用带宽测量算法如算法2所述。

算法2 网络路径最大可用带宽测量算法

输入: 测量序列发送速率R1,R2,…,Rs

测量序列时延增加度A1,A2,…,As

输出: 路径最大可用带宽B

算法:

(1)If(A1,A2,…,AL递增)

降低探测报文最低发送速率并重新测量,return；

Else

(2)定位离群区间[Ai,Ai+L-1]，满足A

(3)返回网络路径可用带宽B=Ai。

3 实验验证

图7 仿真网络拓扑环境 Fig．7 Network simulate topology environment

图8 网络路径可用带宽测量结果对比 Fig．8 Comparison of the measurement result

Pathchirp测量工具由RichardBaraniuk等于2003年开发，后经过不断改进，目前的版本是2.4.1，是基于PRM且具有较高效率和精确度的测量工具。为了对基于测量序列时延增加度的PRM可用带宽测量算法进行验证，选取Pathchirp作为对比，实验环境使用NS2作为仿真环境，网络拓扑结构定义与Pathchirp一致，如图7所示。节点0作为测量点发送端，节点2作为测量点接收端，节点3到节点2发送CBR背景数据流量。分别对2Mbps到8Mbps间不同速率的CBR背景数据流量，测量节点0到节点2的最大可用带宽。测量时序列个数设置为100，序列内探测报文个数设置为50，窗口个数为10，实际网络路径可用带宽、Pathchirp测量结果和基于序列时延增加度的测量结果如图8所示。测量详细数据对比与准确度如表2所示。

NS2的仿真结果显示，基于序列时延增加度的网络路径最大可用带宽测量算法能够获得更加精确的测量结果。与Pathchirp相比，较大地提高了网络路径可用带宽测量的准确度。

4 结束语

背景流量对网络路径可用带宽测量结果的干扰是带宽测量无可回避的关键问题，目前众多网络路径可用带宽测量算法对背景流量干扰的解决方法均不够理想。本文使用探测序列代替了Pathchirp中仅使用两个相邻探测包的时间间隔来表征发送速率，规范定义了测量通信协议和报文结构，提出了特定发送速率下表征发送速率与路径可用带宽的序列时延增加度的计算方法，并利用时延增加度来定位和计算离群区间与网络最大可用带宽。利用NS2进行仿真实验验证了算法的有效性和准确性，通过与Pathchirp测量结果的对比，基于序列时延增加度的离群区间计算和网络路径可用带宽测量方法对实际网络可用带宽测量具有较高精确性，且在背景流不同的情况下，能够适应流量变化，准确计算路径可用带宽。

表2 测量结果与准确度对比

[1] Ribeiro V, Coates M, Riedi R, et al. Multifractal cross-traffic estimation[C] // Proc of ITC Specialist Seminar on IP Traffic Measurement Modeling & Management. Monterey,USA:Rice University, 2000:1-5.

[2] Hu N, Steenkiste P.Evaluation and characterization of available bandwidth probing techniques[J].IEEE Journal on Selected Areas in Communications, 2003, 21(6):879-894.

[3] Strauss J, Katabi D, Kaashoek F. A measurement study of available bandwidth estimation tools[C] // Proceedings of the 3rd ACM Sigcomm Conference on Internet Measurement. New York，USA:ACM,2003: 39-44.

[4] Carter R L, Crovella M E.Measuring bottleneck link speed in packet-switched networks[J].Performance Evaluation, 1996, 27(28):297-318.

[5] Jain M, Dovrolis C. Pathload: A measurement tool for end-to-end available bandwidth[C] // Passive and Active Measurement Workshop.Ft Collins:Springer, 2002:14-25.

[6] Ribeiro V, Riedi R, Baraniuk R, et al. Pathchirp: Efficient available bandwidth estimation for network paths[C] // Passive and Active Measurement Workshop. San Diego:Springer,2003(4):6-8.

[7] Melander B, Bjorkman M, Gunningberg P. A new end-to-end probing and analysis method for estimating bandwidth bottlenecks[C] //Global Telecommunications Conference. San Francisco,USA: IEEE, 2000(1): 415-420.

[8] Li M, Wu Y L, Chang C R.Available bandwidth estimation for the network paths with multiple tight links and bursty traffic[J].Journal of Network and Computer Applications, 2013, 36(1):353-367.

[9] Jacobson V. Congestion avoidance and control[C]// ACM Sigcomm Computer Communication Review. New York,USA: ACM,1988(18): 314-329.

[10]刘敏, 李忠诚, 过晓冰, 等.端到端的可用带宽测量方法[J].软件学报, 2006, 17(1):108-116.

Liu Min,Li Zhongcheng, Guo Xiaobing, et al. An end-to-end available bandwidth estimation methodology[J]. Journal of software,2006,17(1):108-116.

[11]Dovrolis C, Ramanathan P, Moore D. What do packet dispersion techniques measure?[C] // Twentieth Annual Joint Conference of the Computer and Communications Societies. Anchorage, USA: IEEE, 2001(2): 905-914.

[12]Jain M, Dovrolis C. End-to-end available bandwidth: Measurement methodology, dynamics, and relation with TCP throughput[C]// ACM SIGCOMM Computer Communication Review. New York,USA:ACM,2002(32): 295-308.

[13]Guerrero C D, Morillo D S. On the reduction of the available bandwidth estimation error through clustering withk-means [C] // Latin-America Conference on Communications. Cuenca,USA:IEEE，2012: 1-5.

[14]Aceto G, Botta A, Pescapé A, et al.Unified architecture for network measurement: The case of available bandwidth[J].Journal of Network and Computer Applications, 2012, 35(5):1402-1414.

[15]何莉, 余顺争.一种测量任意链路可用带宽的方法[J].软件学报, 2009, 20(4):997-1013.

He Li,Yu Shunzheng. Methodology for measuring available bandwidth on arbitrary links[J].Journal of Software,2009,20(4):997-1013.

[16]周辉, 李丹, 王永吉.可用带宽度量系统中的若干基本问题[J].软件学报, 2008, 19(5):1234-1255.

Zhou Hui,Li Dan,Wang Yongji.Fundamental problems with available bandwidth measurement systems[J].Journal of Software, 2008, 19(5):1234-1255.

[17]黄翔东, 李文元, 王兆华.基于快速序列变换的线性网络冲激响应测量算法[J].数据采集与处理, 2006, 21(2):142-148.

Huang Xiangdong,Li Wenyuan,Wang Zhaohua.Determination algorithm for impulse responses of LTI-Meshwork based on fast m-sequence transform[J].Journal of Data Acquisition and Processing, 2006,21(2):142-148.

[18]张大陆, 胡治国, 朱安奇, 等.一种自负载降速率包列可用带宽测量算法[J].软件学报, 2012, 23(2):335-351.

Zhang Dalu, Hu Zhiguo, Zhu Anqi,et al. Self-loading decreasing rate packet train method for available bandwidth estimation[J].Journal of Software,2012,23(2):335-351.

Improved Outlier Range Calculation Algorithm for PRM Bandwidth Measurement

Wang Zhizhao1, Lu Yuliang1, Yang Guozheng1, Guan Yongyao2

(1.Electronic Engineering Institute, Hefei, 230037, China; 2. PLA 94647,Fuzhou,350001,China)

Active measurement has been a primary method used in network path bandwidth measurements to date,with greater flexibility and deployment convenience compared to the passive one.The available bandwidth measurement probe model is not precise enough for background traffic and problems with high error rate, so we define the communication protocol, detect packet structure, and propose the calculation method of the increase rate of sequence delays and the outlier range. The algorithm can reduce the interference of background traffic on the network path. The effectiveness of the algorithm has been verified by using NS2 simulation.

increase rate of sequence delay; outlier range; available bandwidth measurement; network measurement

2014-05-31；

2015-01-31

TP39

A

王志钊(1988-)，男，硕士研究生，研究方向: 网络测量、信息安全，E-mail：78761186@qq.com。

关永耀(1983-)，男，本科，研究方向：计算机网络安全。

陆余良(1964-)，男，教授，博士生导师，研究方向：信息安全。

杨国正(1982-)，男，博士，研究方向：计算机网络安全。