一种基于自适应采样的网络丢包率测量方法*

黎文伟，蔡建国，王志明

(1.湖南大学 信息科学与工程学院，湖南 长沙 410082；2. 湖南大学 工商管理学院，湖南 长沙 410082；3. 东莞职业技术学院 计算机工程系， 广东 东莞 523808)

IP网络中，流量突发会使网络拥塞，网络服务质量降低，甚至出现丢包.对于实时性要求不高的网络应用，如HTTP，FTP等，网络丢包会降低其传输吞吐量[1]；但通过数据重传，它们仍能正常工作.然而，对于VoIP、流媒体等高实时性要求的网络应用，丢包不仅会显著降低其性能，还会影响其正常工作[2].因此，需要准确地测量端到端路径丢包率，了解网络丢包特征，以此来改进网络应用的设计或调整其运行时的参数配置，从而优化应用的性能[3].

常用的丢包率测量方法有被动测量和主动测量两类.文献[4]提出了基于TCP协议过程分析的丢包率被动测量方法.文献[5]研究了高速网络环境的丢包率被动测量.文献[6]提出以卡尔曼滤波来提高丢包率被动测量精度的方法.被动测量方法无需产生探测负载，可减轻网络负担.但它需要依赖已有的网络流量，无法对任意端到端路径进行测量.故主动测量在丢包率测量中应用更为普遍.

主动测量具有实施简单、测量灵活等优点.主动测量丢包率的基本过程是在指定的时间区间内，周期性地从源端向目的端发送探测包.若某探测包在指定时间阈值内收到响应包，则获得一个端到端时延的测量样本；若超过指定时间阈值仍未收到响应包则记录为丢包事件.测量过程结束后，记录的丢包事件次数除以测量过程发送的探测包总数即为该时间区间内端到端路径丢包率；获得的时延测量样本集合则构成了时间区间内端到端路径时延的时间序列.这种周期探测方式过程简单、容易实现，因而被广泛应用.最常用的主动测量工具Ping即采用这种方式测量丢包率及时延.

但周期探测的本质是一种离散采样方式，其测量结果受探测周期选择的影响.由于网络流量的随机突发性，丢包也具有随机突发特征[7].测量的探测周期太大，则不能充分探测丢包事件，丢包率测量结果有误差.所以，往往需要较密集地发送探测包，即需有较小的采样周期，才能充分地探测到突发的丢包事件，准确测量丢包率.而持续的小采样周期会给端到端路径带来不可忽视的测量负载，使得测量结果与无测量负载的路径实际丢包率不相符.故实现周期探测方式的工具，如Ping，所测量的丢包率结果往往存在较大误差[8].

周期探测方式存在较大测量误差的根本原因在于周期探测难以适应丢包的随机突发特征，从而充分采样丢包事件.对此，现有研究试图从测量过程的设计或基于理论推导选择探测方式来解决问题.文献[9]提出的ZING工具可测量端到端路径的单向丢包率，但需要端主机协作.Sting工具则通过控制TCP协议通信过程来测量丢包率[10].文献[11]提出了BADABING工具来提高丢包率测量精度．文献[12]分析了其采样方式的缺陷.文献[13]则建议应以泊松采样为丢包率等网络性能指标的基本测量方式.泊松采样是一种渐近采样方式，可无偏地估计被测量过程的时间平均统计量.但现代的高速互联网在正常条件下路径丢包并不频繁，丢包率较低[7].由于泊松采样的渐近特性，在平均采样频率不高时，测量过程可能需较长的时间才能准确测量端到端路径丢包率[14].因此周期探测仍是目前最常用的测量方式.

与现有研究不同，本文从考虑探测方式应与网络状态相适应的角度出发来改进方法.为解决周期探测方式测量误差较高的问题，本文提出一种探测周期自适应调整的丢包率测量方法，通过利用时延-丢包相关性及丢包-丢包相关性，根据测量过程中大时延测量样本和丢包事件对网络突发丢包的指示作用，设定适当的触发阈值，在出现大时延测量样本和丢包事件时，降低探测周期；而在时延较平缓时则增大探测周期，既保证了在无突发丢包时，不会产生太大的测量负载，也保证了出现突发性丢包时，能充分对丢包事件采样，从而在不大幅提高探测量的前提下，提高了丢包率测量的准确性.仿真实验结果表明：与ping相比，该方法测量误差降低较多，而探测量开销却增加不多；与较为准确的BADABING工具相比，测量误差相差不大，但探测量开销却明显减少.因此，该方法在测量精度和探测量开销上有较好的折中.可见该方法保持较小测量负载情况下仍可取得较高测量精度，适于在实际网络测量中应用.

1 测量方法设计

1.1 基本思想

周期探测方式测量丢包率存在的困难在于，由于丢包的随机突发特征，难以选择合适的采样周期.采样周期太大，测量不准确；采样周期太小，则测量负载的影响不可忽视.事实上，对于具有随机突发性的被测对象，自适应采样往往比简单的周期采样更具优势.如文献[15]即通过自适应采样，在保持较小采样数量前提下获得了较理想的网络流量采样结果.因此，本文的基本思想是在周期探测基础上，自适应地调整采样周期.在可能存在突发丢包时，降低采样周期，以充分采样丢包事件；而在网络状态较平稳时，则增大采样周期，以降低测量负载；由此使得丢包率测量能保持较小测量负载并降低丢包率测量误差.

实现上述思想的自适应采样测量方法基本流程如图1所示.与周期采样的测量方法相比，图1中增加了探测周期调整模块，该模块主要运行自适应调整算法，动态调整探测周期.显然，设计适当的自适应调整算法来合理调整探测周期是测量方法的关键.

图1 自适应采样测量方法流程

1.2 算法关键问题

为使测量能保持较小负载和误差，自适应调整算法首先应对当前是否可能存在突发丢包进行分析和判断，以确定探测周期调整的方向；其次，需要设计合适的探测周期调整策略，使得周期调整幅度能快速适应网络状况的变化.因此，该算法主要应解决两个问题：1)分析判断当前是否存在突发丢包.2)根据判断结果合理调整探测周期.下面分别进行讨论.

1.2.1 突发丢包的判断

IP网络中，丢包主要由于网络流量的突发增加而导致.就网络性能而言，突发流量导致网络出现短时间拥塞，使得网络时延增加，并出现丢包.因此，突发丢包并不是孤立出现的，而是往往伴随着较大的时延或者短时间连续的丢包而发生.事实上，时延与丢包、丢包与丢包之间存在一定的相关性[16].因此，在测量中可以利用此相关性来判断突发丢包的出现.

设测量过程共进行n次探测，即发送了n个探测包，探测结果表示为序列{d1,d2,…,dn}.对于第i次探测，若未丢包，di为探测到的时延值；若丢包，置di为0.随着测量的进行，若第k次探测的结果dk为0或较大的时延值，根据上述相关性特征，可以认为此时处于突发丢包时段.由于单使用dk的取值不方便判断突发丢包，可定义排队时延比率指标qr如式(1)：

(1)

式中：dmin为当前探测到的时延最小值，通常认为dmin未包含任何排队时延[17]；dth为当前所有探测到的丢包事件前一个时延值的最小值.式(1)可视为当前排队时延相对出现丢包事件的最小排队时延的比率.dk不为0时，若qr小于1，表明当前排队时延小于之前出现丢包事件的最小排队时延，网络未拥塞；若qr大于1，则表明当前排队时延大于之前出现丢包事件的最小排队时延，网络可能出现突发丢包.若dk为0，则当前已出现突发丢包，下一刻亦可能出现突发丢包，故补充qr定义等于1.

排队时延比率指标qr可作为突发丢包的判断指标，但对偶然出现的大时延值或丢包过于敏感，容易误判.故补充考察短时间内的时延变化趋势.若短期内时延出现明显增长趋势，则可能出现流量突发，从而可能出现突发丢包.为此，设第k次探测及之前共w次探测的结果序列为{dk-w+1,…,dk-1,dk}，根据文献[18]的分析，定义时延变化趋势指标Sk为：

(2)

式(2)中，I(X)为示性函数，定义为：

时延变化趋势指标Sk反映了结果序列中相邻时延值递增的比例.根据文献[18]的分析，Sk大于0.55时，结果序列有明显的增长趋势.本文沿用这一结果.此外，w的取值亦对使用Sk来判断短期内时延变化趋势有影响.参数w可视为考察时延变化趋势时考虑的时间窗口大小.有研究表明网络的突发式拥塞持续时间通常不超过1 s[19]，故本文设置计算Sk的时间窗口为5 s，则w的初值可计算为：

w=「5/T0⎤．

(3)

式(3)中，「⎤表示上取整运算，T0为初始探测周期.测量过程中，随着探测周期的动态调整，w的取值也将变动.

在测量过程中，结合排队时延比率指标qr和时延变化趋势指标Sk,可对出现的突发丢包进行较好的判断.具体过程在1.3小节讨论.

1.2.2 探测周期调整策略

在对是否出现突发丢包进行判断后需要进行适应性的探测周期调整.总体策略是当出现突发丢包时应减小探测周期，而网络状态平稳时应增大探测周期.

由于探测周期的调整对保持较小的测量误差和测量负载有决定性作用，调整策略应能快速适应网络状态的变化.为此，探测周期调整时采用减半或倍增的方式.设当前探测周期为Tk，若判断当前处于突发丢包状态，为充分采样丢包事件，则探测周期调整为Tk+1=Tk/2；若判断当前未处于突发丢包状态，则探测周期调整为Tk+1=2Tk，以降低测量负载.

需要注意的是，这种减半或倍增的调整策略对探测周期的调整幅度是几何量级的.若没有其它条件约束，将可能出现极小或极大的探测周期而影响测量过程.考虑到自适应调整探测周期时，若探测周期过大会使得采样过于稀疏；而探测周期太小，则相邻探测包的结果相互干扰.因此可以设置允许的最大、最小探测周期来限定探测周期的调整范围.

设最大探测周期为Tmax，最小探测周期为Tmin，则任意一次采样的探测周期Ti均需满足Tmin≤Ti≤Tmax.通常认为时间相隔5 s的探测包是相互独立的，故设置最大探测周期Tmax为5 s.文献[20]的研究表明，若时间间隔小于50 ms，则前后探测包可能存在相互干扰.故设置最小探测周期Tmin为0.05 s.

1.3 自适应调整算法

依据上一节的分析，将突发丢包判断过程和探测周期调整过程进行整合，得到的探测周期自适应调整算法流程如图2所示.

图2 自适应调整算法流程

图2中，若Sk<0.55，表明时延未表现明显增长趋势，网络状态平稳，故增大探测周期.此时无需考察qr的取值，以避免调整算法对偶然出现的大时延或丢包事件过于敏感.若Sk≥0.55，则考察qr的取值.若qr<1，则当前虽然时延有增长趋势，但不能确定是否处于突发丢包状态，故保守地保持探测周期不变.若Sk≥0.55且qr≥1，表明当前时延有明显增长趋势，且当前排队时延大于之前出现丢包事件的最小排队时延，指示当前处于突发丢包状态，故减小探测周期.

在计算qr和Sk时需要使用到一些参数，这些参数的初始化在图1所示的测量初始化时进行，之后则在输出新的探测周期Tk+1时进行更新.需要指出的是，本文对一些参数的具体取值进行了讨论，如Tmax,Tmin等，它们可视为算法运行时的默认值.实际使用时，这些参数的取值均可另行设置，以适应不同的端到端路径特性.

2 仿真实验

在ping的基础上对本文方法进行了实现，称之为asping.与探测周期固定的ping工具不同，asping在测量过程中将自适应地调整探测周期.为评估asping在测量丢包率时的准确性和探测包开销，在仿真环境进行了实验，并与ping，BADABING等工具进行比较.

2.1 仿真实验设置

本文仿真实验使用ns-2构建的网络拓扑如图3所示.图3中，S1至Sn为发送端，R1至Rn为接收端，模拟网络的实际用户.发送端向对应接收端发送符合指数开关(ON-OFF)过程的流量，多个叠加后即具有自相似特征.开、关的均值分别设置为1 s和14 s.在开状态下，发送端发送长度为1 000字节的数据包，发送时间间隔服从均值为10 ms的指数分布.设置发送端总数为140，故中间链路的利用率约为70%.路由器的缓存容量设置为50个数据包.由于每次仿真得到的网络实际丢包率均有不同，为保证结果有可比较性，仿真时设置Sp,SB,Sa为测量源主机，分别模拟ping,BADABING,Asping工具同时向对应测量目的主机发送包长为64字节的探测包，亦即同时进行丢包率的测量.

图3 仿真网络拓扑

2.2 实验结果

在图3所示网络拓扑共运行了10次时间为1 000 s的仿真试验，记录各工具测量的丢包率及探测量进行比较分析，探测周期设置为5 s.网络实际丢包率则根据发送端发送的数据包总数及接收端接收数据包总数来计算.

2.2.1 测量误差

图4给出了10次仿真试验的实际丢包率RL及各工具的测量结果.由图4可知，10次仿真试验的实际丢包率并不固定，但均小于3%.相对于实际丢包率，3种方法中ping的测量误差最大.特别是第3次、4次和7次仿真试验，由于ping未能探测到丢包事件，其测量的丢包率结果为0.之所以ping有较大测量误差，是因为仿真设置的探测周期较大，而ping的周期探测是固定的，故难以充分探测丢包事件.10次仿真试验中BADABING有6次具有最小的测量误差，可以认为BADABING的测量精度最优.本文提出的asping方法测量误差明显小于ping，虽然多数仿真中asping方法的测量误差略高于BADABING，但亦有少数仿真试验asping方法的测量误差小于BADABING，可认为asping的测量精度仅略低于BADABING.

实验序号

2.2.2 探测量开销

探测量开销是测量方法评估的另一个重要指标，且探测量开销在一定程度上影响了测量精度.图5给出了10次仿真试验中3种工具的探测量开销，因仿真时探测包长度固定为64字节，故图中以探测包数表示探测量开销.图5中，ping是采取固定周期探测方式，故每次仿真试验中，ping的探测量开销也是固定的；BADABING和本文提出的asping则在测量过程中动态调整采样频率，故它们每次试验的探测量开销是变动的.由图5可知，ping有最小的探测量开销，asping探测量开销中等，而每次试验中，BADABING均具有最大的探测量开销.

实验序号

2.2.3 实验结果分析

表1给出了3种方法在10次仿真试验中的平均误差和平均探测量开销.由表1可知，总体而言，虽然ping的探测量开销最小，但其测量误差较大，平均绝对误差达到64%；BADABING测量误差最小，但是以较大的探测量开销为代价而取得的，其平均探测量开销为ping的2.82倍；本文提出的asping的测量误差接近了BADABING，同时增加的探测量开销小于BADABING，其平均探测量开销为ping的1.86倍.

从表1可以看到，asping方法的探测量要高于ping.这是因为ping的探测周期固定为5 s，而asping探测周期是随着测量过程动态调整的且最大探测周期为5 s，显然其探测量应高于ping.又由于asping对探测周期的调整是与网络状态相适应的，故其探测量小于BADABING.

对于测量精度，ping的固定周期探测方式意味着探测时不考虑网络状态的变化，故突发丢包时难以充分采样，从而精度不理想.而asping会以与网络状态变化相一致的动态来调整探测周期，在突发丢包时将密集采样，从而精度得到大幅提高.故可以认为asping在测量误差和探测量开销之间取得了较好的折中.

表1 测量的平均误差和平均探测量开销

3 结 论

由于过程简单，实现容易，ping是最常用的丢包率测量工具之一，但ping的固定周期探测方式会导致测量误差较大.本文提出的探测周期自适应调整的丢包率测量方法，在ping的基础上进行改进.其基本思想是利用时延-丢包及丢包-丢包相关性，根据大时延测量样本和丢包事件对网络突发丢包的指示作用来动态调整探测周期.仿真实验中，本文方法的测量误差相对ping有较大幅度的下降，但探测量开销却没有过多增加；而与较准确的工具BADABING相比，本文方法测量误差虽略有不如，但探测量开销明显较少.因此，本文方法在测量精度和探测量开销上有较好的折中，可以在实际的大规模网络测量中应用.

由于需要采集足够的测量样本，本文方法需要一定的测量时间来完成丢包率测量，故对于一些需快速测量丢包率的网络应用，本文方法不一定适用.下一步的研究将更深入的分析时延-丢包及丢包-丢包相关性，建立其量化模型，根据当前时延或丢包来估计丢包率，以实现快速而准确的丢包率测量.

[1] NADIM P, ANIRBAN M, CAREY W. An analytic throughput model for TCP New Reno[J]. IEEE/ACM Transactions on Networking, 2010, 18(2): 448-461.

[2] JIAN Y, HAN H, XI H,etal. Online buffer fullness estimation aided adaptive media playout for video streaming[J]. IEEE Transactions on Multimedia, 2011, 13(5): 1141-1153.

[3] WENG Y, SHIEH C, HUANG T,etal. Using P2P networks to repair packet losses in digital video broadcasting systems[C]//Proc of IEEE ICPADS’11. New York: IEEE, 2011: 765-769.

[4] BENKO P, VERES A. A passive method for estimating end-to-end TCP packet loss[C]//Proc of IEEE Global Telecommunications Conference 2002. New York: IEEE, 2002:2609-2613.

[5] ALES F, SVEN U, ALEXANDROS K,etal. Realistic passive packet loss measurement for high-speed networks[C]//Proc of Traffic Monitoring and Analysis Workshop 2009. New York: ACM, 2009:1-7.

[6] ZHANG D, LONECU D. A new method for measuring packet loss probability using a Kalman filter[J]. IEEE Transaction on Instrumentation and Measurement, 2009, 58(2): 488-499.

[7] ATHINA M, FOUAD T, MANSOUR K. Loss and delay measurements of internet backbones[J]. Computer Communications, 2006, 29(10):1590-1604.

[8] BARFORD P, SOMMERS J. Comparing probe- and router-based packet-loss measurement[J]. IEEE Internet Computing, 2004, 8(5):50-56.

[9] ADAMS A, MAHDAVI J, MATHIS M,etal. Creating a scalable architecture for internet measurement[C]//Proc of INET’98. New York: IEEE, 1998:9-16.

[10]SAVAGE S. Sting: A tool for measuring one way packet loss[C]//Proc of IEEE INFOCOM ’2000. New York: IEEE, 2000:1157-1165.

[11]SOMMERS J, BARFORD P, DUFFIELD N,etal. A geometric approach to improving active packet loss measurement[J]. IEEE/ACM Transactions on Networking, 2008, 16(2): 307-320.

[12]FRANCOIS B, SRIDHAR M, DARRYL V,etal. Probing for loss: the case against probe trains[J]. IEEE Communications Letters, 2011, 15(5): 590-592．

[13]PAXSON V, ALMES G, M AHDAVI J，etal. Framework for IP performance metrics[S]. RFC2330, 1998.

[14]BACCELLI F, MACHIRAJU S, VEITCH D,etal. The role of PASTA in network measurement[C]//Proc of ACM SIGCOMM’06. New York: ACM, 2006:231-242.

[15]张大方,沈永坚,黎文伟.一种基于历史记录的网络流量数据采样方法[J]. 湖南大学学报：自然科学版, 2005,32(6):102-105.

ZHANG Da-fang, SHEN Yong-jian, LI Wen-wei. A network flow data sampling method based on history memory[J]. Journal of Hunan University：Natural Sciences, 2005,32(6):102-105.(In Chinese)

[16]HUNG X, MATTHEW R. Rigorous statistical analysis of internet loss measurements[J]. SIGMETRICS Performance Evaluation Reviewm, 2010, 38(1): 361-362.

[17]黎文伟，张大方，曾彬，等．端到端最小包时延可测性的排队分析与仿真[J]．湖南大学学报；自然科学版，2007，34(4)：73-77.

LI Wen-wei,ZHANG Da-fang,ZENG Bing,etal. Queuing analysis and simulation of the measurability of end-to-end minimum packet delay[J]．Journal of Hunan University:Natural Sciences，2007，34(4)：73-77．(In Chinese)

[18]MANISH J, CONSTANTINOS D. End-to-end available bandwidth: measurement methodology, dynamics, and relation with TCP throughput[J]. IEEE/ACM Transactions on Networking, 2003,11(4): 537-549.

[19]UYEDA F, FOSCHINI F, BAKER F,etal. Efficiently measuring bandwidth at all time scales[C]//Proc of NSDI’11. Berkeley, CA, USA: USENIX Association, 2011:6-19.

[20]黎文伟,王俊峰,谢高岗,等.基于包对采样的IP网络时延变化测量方法[J].计算机研究与发展,2004,41(8):1352-1360．

LI Wen-wei, WANG Jun-feng, XIE Gao-gang,etal. An IPDV measurement method based on packet pair sampling[J]. Journal of Computer Research and Development, 2004, 41(8):1352-1360．(In Chinese)