TCP报文丢包定位方法研究

高中耀，程 光

1.东南大学 计算机科学与工程学院，南京 211189

2.计算机网络和信息集成教育部重点实验室，南京 211189

TCP报文丢包定位方法研究

高中耀1，程 光2

1.东南大学 计算机科学与工程学院，南京 211189

2.计算机网络和信息集成教育部重点实验室，南京 211189

1 引言

ΤCP是互联网中广泛使用的传输层协议，它提供一种可靠的面向连接的字节流服务。很多网络行为会引起ΤCP报文丢失，比如流量过大导致网络拥塞或中断，错误的网络接线或配置导致报文不可达，网络攻击引起网络质量下降或瘫痪。

ΤCP报文传输的一个重要特征就是传输过程中的序号，报文的IP首部和ΤCP首部分别有ID号和序号，正常顺序到达的报文ID号和序号应该是非递减的，当到达的报文序号没有按照非递减方式出现时，那么网络中出现乱序，一定程度上的乱序会导致接收端认为报文丢失，引起拥塞窗口的调整和快速重传，从而可能会导致网络或者应用程序的性能下降。当发送端接收到多个重复ACK或者出现定时器超时，发送端会认为报文在传输中丢失，重传该报文，同样会引起拥塞窗口的调整而影响网络性能。

当网络中出现丢包时，只有定位出丢包位置才能寻找丢包原因以解决丢包问题。所以，定位出丢包发生的位置以及推算丢包率将有利于网络管理的进行。众多学者提出各种不同的研究方法，最常见的是通过ping来分析，此类基于主动测量的方法向网络中注入流量，可能会增加网络负载甚至对测量结果产生影响，不适合于经常性的网络管理和维护；Sommers等人通过在发送端主动发送探测包，在接收端查看探测包抵达的数目以推测端到端的丢包率[1]；Benko和Veres提出基于ΤCP报文序号的被动测量丢包率方法，它将测量点布置在核心或边界路由器上，把端到端路径分成两部分，通过观测ΤCP序号来定位丢包及推算丢包率[2]，Ohta和Miyazaki利用两个测量点通过被动测量对报文进行哈希辨别来推算丢包率[3]，Friedl等人通过对比两个测量点的流信息来计算丢包率[4]，Jaiswal等人对Sprint骨干链路上的ΤCP连接进行分析，对失序的报文进行分类，其中包括对丢失报文的定位和推算[5]，Allman等人通过观测发送端的重传报文来推算丢包率[6]，Nguyen等人构建了一种叫HSMM的模型来对报文丢包进行分析[7]，Zhang等人从入口的随机性和报文丢包入手，对丢包、时延、带宽进行分析[8]。

上述基于被动测量研究丢包率及丢包定位的方法多数仅从ΤCP序号的角度考虑，没有结合报文超时来分析丢包，因为三个重复ACK或发送端超时均会导致报文丢包。也有学者通过分析往返报文来研究丢包，这样对丢包率的推算会更为精确，但由于网络多路径或负载平衡问题，同一个测量点不一定能完全监测到往返报文。因此本文从序号和时间角度综合考虑，研究单向ΤCP报文流，提出一种基于单点被动测量的报文丢包分段检测方法（Half Path Detection of Packet Loss，HPDPL），测量点可选择在核心或边界路由器上，它将端到端路径分成两部分，通过对网络中的ΤCP报文进行组流和过滤分析以定位丢包位置及推算测量点之前和之后链路的丢包率。利用本文提出的方法，ISP可通过二分法定位到出现异常的网络，将异常点缩小到小范围，并且此方法可在日常网络管理中实时观测链路丢包情况。

2 测度定义

既然报文丢包会降低网络和应用程序的性能，那么定义相关的测度来描述和分析丢包是非常必要的。假定ID[i]为接收端接收到报文的ID首部ID号，Seq[i]为接收端接收到报文的ΤCP首部序号，其中i、j=0，1，…，n，且j＜i。T(i，j)为接收端接收到的第i个报文和第j个报文的时间间隔，RTO为发送端计时器的超时重传时间。

定义下面四个条件式：

2.1 乱序率

随着互联网的飞速发展，各种新兴技术被应用到互联网中，如多路由技术、并行处理技术、链路层重传技术等。这些技术在提升互联网性能的同时，也导致了传输层报文乱序的出现。大量研究表明，报文乱序是互联网中普遍存在的现象[6]，随着端到端报文延迟的降低和网络传输速率的增快，报文乱序出现的比例同时也呈增长趋势[9]。

RFC4737[10]中定义了11个报文乱序测度，包括基于延迟的乱序比例，乱序范围等，RFC5236[11]深层次地对乱序测度进行定义，提出乱序密度RD（Reorder Density）和乱序缓冲区使用密度RBD（Reorder Buffer-occupancy Density）两个测度。

若报文按正常顺序到达，则报文的ΤCP首部序号应该呈非递减出现，即Seq[i]≥Seq[j]，当到达的报文没有按非递减方式出现，即Seq[i]＜Seq[j]，网络中出现乱序，定义序号为Seq[i]的报文为乱序报文，乱序率定义为：

乱序率=乱序报文个数/报文总个数

乱序率在一定程度上影响着丢包率，特别在骨干链路，部分乱序甚至会引起吞吐量的严重下降[7]。

2.2 丢包率

RFC2680[12]给出了IP报文单个丢包事件的测度，RFC3357[13]进一步给出了丢包模式的测度，包括基本定义以及基本定义之上的测度序列和测度统计值。方法提出测量点之前的丢包率和测量点之后的丢包率，以下简称“前丢包率”和“后丢包率”。测量点可选择在核心或边界路由器上，它将端到端路径分成前后两部分，如图1所示。位于网络B中的客户端从位于网络A中的服务器下载文件，那么客户端和服务器建立了ΤCP连接，ΤCP报文从发送端发送后到各自网络边界，再经过测量点抵达接收端。

图1 测量点的布置

由于多路由等原因，发送端发送报文至接收端和接收端回复ACK至发送端的路径可能是不同路径，所以本文选择基于单向报文的IP首部ID号、ΤCP首部序号以及报文间的时间间隔来推算丢包率。

2.2.1 前丢包率

若报文在测量点之前丢失，如图2所示，序号为1的报文在抵达测量点前丢失，测量点将看不到序号为1的报文经过，发送端接收到三个重复ACK后，发送端会重传序号为1的报文，此时测量点监测到该报文的重传，即序号为1的报文在测量点之前丢包表现为乱序报文的出现。

图2 测量点之前丢包

当报文使得条件式Aand（CorD）为真时，可判断该报文在测量点之前发生丢失，条件式A代表报文出现乱序，条件式C代表报文出现超时，条件式D代表报文i与报文j间距大于3。前丢包率定义为：

前丢包率=测量点之前的丢包个数/报文总个数

2.2.2 后丢包率

若报文在测量点之后丢失，如图3所示，序号为1的报文在抵达测量点后丢失，测量点监测到序号为1的报文经过，发送端接收到三个重复ACK后，发送端会重传序号为1的报文，此时测量点再次监测到该报文的重传，即序号为1的报文在测量点之后丢包表现为重复报文的出现。

图3 测量点之后丢包

当报文使得条件式Band（CorD）为真时，可判断该报文在测量点之后发生丢失，条件式B代表报文为重复报文，条件式C代表报文出现超时，条件式D代表报文i与报文j间距大于3。后丢包率定义为：

后丢包率=测量点之后的丢包个数/报文总个数

3 报文丢包分段检测算法

3.1 算法描述

算法主要分为五个模块，如图4所示，分别是：预处理、数据处理、状态维护、计算及输出模块。预处理模块负责报文到达后的预处理，对报文进行过滤并提取ΤCP报文交给数据处理模块；数据处理模块对报文按照五元组（源IP、目的IP、源端口、目的端口、协议号）进行组流，同时记录报文的IP首部ID号、ΤCP首部序号、报文到达时间等相关参数信息；组流的同时，状态维护模块对流信息进行维护，比如维护丢包推算的窗口及超时流信息更新等事务；在前三个模块工作的同时，计算和输出模块利用维护的流信息进行乱序率和丢包率的推算及输出。

图4 算法框图

算法的核心是计算模块，即乱序率和丢包率的推算部分，算法如图5所示。

第一行是对新报文的获取，第三和四行是对RTT、RTO进行计算，根据报文的到达时间提取相邻两个发送轮次之间的间隙，进而推算RTT以及计算RTO，第六到第十一行是统计符合条件的乱序报文数和测量点之前的丢包个数，第十二和十三行是统计测量点之后的丢包个数，其中T[i，j]＞RTO和ID[i]-ID[j]≥3起到互相补充的作用，主要是考虑到极少数报文的ID号可能不是递增出现，利用时间信息对它进行补充。最后的第十四、十五、十六行是对乱序率、前丢包率、后丢包率进行计算。

图5 算法伪代码

3.2 性能分析

对于该算法来说，算法的计算时间主要花费在ΤCP流信息的维护以及乱序和丢包个数的统计上，对于一个ΤCP流信息需要维护所属报文的ID、Seq、时间间隔信息，对4.2节的CERNEΤ实验数据进行前、后丢包率推算的同时，对所需维护报文的个数（窗口大小）进行统计，统计结果如图6所示，横轴是窗口大小的统计值，纵轴是出现窗口大小的累积比例。

图6 窗口大小累积比例曲线

观察图6可得知：

（1）丢包报文与重传报文之间距离出现频率最高的是3，所占比例达59.62%－28.18%=31.433%，也验证了收到三个重复ack触发快速重传的控制机制；

（2）91.373%的丢包报文与重传报文的距离小于等于5；

（3）丢包报文个数从距离6开始出现了骤减，骤减过程一直持续到25；

（4）仅需维护25个报文信息，就可观测到100%的丢包，即维护的窗口大小为25。

出于全面性考虑，窗口大小选择为比25稍大的值，资源上也不会占用过多，算法的精确度更高。流信息维护过程的时间复杂度是一个常量，即O（1），对于计算模块来说，计算RTT和RTO的时间复杂度也是一个常量，即O（1）。对于n个报文来说，总的时间复杂度为O（n），完全符合在线实时报文分析的实际情况。

3.3 算法中数据集的选取

网络中报文丢失情况错综复杂，由于需要做的是推算丢包率，而不是准确计算丢失报文的个数，所以对部分未知情况不应考虑在推算丢包率的报文数据集之内，只需选择能准确估计丢包率的数据进行推算，数据集通过测量点采集报文构成，对于那些不能确定丢包的报文排除在数据集之外，包括以下几种情况：

（1）没有数据内容的ΤCP控制报文：没有数据内容的ΤCP控制报文仅由ΤCP首部组成，这些ΤCP控制报文首部的序号为固定值，在传输过程中不变，也就是说当丢包发生时，中间测量点将无法感知到丢包。所以对于没有数据内容的ΤCP控制报文排除在数据集之外。

（2）特殊的超时：由于网络拥塞导致往返时间突然增大，即使没有报文丢失出现，发送端也可能出现超时，发送端会重传报文并等待接收端的ACK，此时当第一次发送的报文抵达接收端，接收端发送ACK，发送端可能会重传丢失报文之后发送的所有报文，那么这些重传的报文不应该认为是丢失的报文。所以当连续丢包的报文个数超过3个时，这些报文排除在数据集之外。

（3）环路：环路是由于网络配置失误或其他因素，导致报文找不到正确的路径，一直在网络中循环发送。为了推算的准确性，环路报文排除在数据集之外。

3.4 几种影响推算精度的情况

（1）特殊的IP首部ID号：IP首部的ID字段在绝大多数操作系统下随着报文的发送呈递增变化，这些操作系统包括Windows 95/98/NΤ/2000/XP、多数的linux、FreeBSD、Solaris。随着报文的不断发送，当ID号出现不规整的情况时，ID号不能作为丢包的判断条件之一。

（2）同一报文出现大于两次的丢包：当报文丢失时，发送端会对它进行重传，若重传的报文又丢失了，发送端会再重传，在中间测量点监测到重传报文时，无法辨别该报文是一次还是两次丢包进行的重传，该算法将这种情况认为是对一次丢包进行的重传。

（3）不同报文的连续丢包：若报文i发生丢包，紧接的报文i+1也发生丢包，计时器超时后，发送端重传报文i、i+1，此时，测量点通过超时可判断报文i发生丢失，但报文i+1是正常到达还是重传到达，中间测量点无法辨别。

（4）序号回转：IP首部的ID长度为2字节，ID的范围是从0到0xffff，当ID到达0xffff后从0开始回转。ΤCP头的Seq长度为4字节，Seq的范围从0到0xffffffff，首部的Seq长度为4字节，范围是从0到0xffffffff，当Seq到达0xffffffff后也从0开始回转。那么在算法计算过程中可能由于反转报文的出现，导致丢包判断出现错误。对于两个临近的没有出现反转的序号，其差值不可能超过序号范围的一半，所以对于ID来说，差值不会超过0x7fff；对于Seq来说，差值不会超过0x7fffffff。

4 实验分析

搭建的实验环境分为两种，一种是仿真实验环境，另一种是真实网络环境。由于需要对算法计算的前、后丢包率进行验证，仅通过单个测量点无法做到，所以通过搭建仿真实验环境解决此问题，在仿真环境中可采集到发送端、中间测量点、接收端共三个点的报文数据，通过对比三点采集到的报文可以计算出实际的前丢包率和后丢包率，再结合算法推算出的前、后丢包率，可以对算法的准确性进行验证。

4.1 仿真实验

为验证算法对前、后丢包率推算的准确性，搭建仿真环境具体布置如图7所示。

图7 实验场景

表1 准确性实验结果

在fedora14操作系统上安装五台fedora8的虚拟机，使用Zebra来实现路由器功能，用Netem对路由器端口进行丢包控制。在主机A给主机B传送文件时，对路由器1、3的eth2端口进行丢包控制，同时在路由器1、2、3上进行被动测量，可通过对比路由器1、2、3的测量数据计算出真实前、后丢包率，再利用测量点M（路由器2）上的测量数据，运用算法对前、后丢包率进行推算，具体结果如表1所示，前三列是前丢包率的实际值、推算值、误差，后三列是后丢包率的实际值、推算值、误差，其中误差计算公式为：|实际值－推算值|/实际值，它反映了推算值的准确度，误差越小，准确度越高。

从表1的实验结果可得知，推算的前丢包率平均误差为0.069，推算的后丢包率平均误差为0.035，推算值与实际丢包率比较接近，具有不错的准确性。其中推算的后丢包率误差小于前丢包率误差，这是因为推算后丢包率的判断条件明确，仅需要出现重复报文且超时或间隔大于等于3，而推算前丢包率的判断条件相对没那么明确，有可能存在丢包交错等特殊情况影响精度。另一方面，实际的丢包率越小，推算的丢包率越精确，反之当实际的丢包率越大时，丢包情况可能更复杂，推算的丢包率精度会存在一定程度的下降。

4.2 CERNET网络环境

实验数据是CERNEΤ华东（北）地区网络中心在不同时间段采集的trace，其采集点位于江苏省教育网边界路由到国家主干路由之间。本文对2010年4月12日23：55：16、2010年4月20日13：55：16和2010年4月21日15：55：16为开始时间的5 min trace进行分析。把trace中的ΤCP报文按照五元组（源IP、目的IP、源端口、目的端口、协议号）进行组流，相同五元组的报文出现时间间隔超过16 s定义为超时，超时后重新组新流。一个流包含两个方向交互的流，从江苏省网到国家主干网的流量方向定义为正向，反之为反向。正向流的源IP、目的IP等于反向流的目的IP、源IP，正向流的源端口、目的端口等于反向流的目的端口、源端口。三次测量的实验数据信息如表2所示，由于后两次测量数据的测量时间选在下午，所以流量明显高于第一次测量的流量。

表2 trace信息统计表

由于报文个数太少会影响计算的准确性，所以采用算法对报文个数大于300的流进行分析，统计结果如表3所示，大约80%数据量的流满足统计条件。对于正向流来说，三次测量的前丢包率都小于后丢包率，这也验证了正向流在省网内的丢包率小于国家主干网丢包率的事实。

表3 流信息统计表

5 总结

从报文丢失的成因进行分析，提出一种基于单点被动测量的报文丢包分段检测方法来研究ΤCP报文丢包，并搭建实验环境对算法的准确性及性能进行评估分析。最后对CERNEΤ华东北地区网络中心采集的数据进行组流分析，并推算乱序率及前后丢包率。

[1]Sommers J，Barford P，Duffield N，et al.Improving accuracy in end-to-end packet loss measurement[J].Computer Communication Review，2005，35（4）.

[2]Benko P，Veres A.A passive method for estimating end-to-end ΤCP packet loss[C]//IEEE Globecom，2002：2609-2613.

[3]Ohta S，Miyazaki Τ.Passive packet loss monitoring that employs the hash-based identification technique[C]//Ninth IFIP/ IEEE International Symposium on Integrated Network Management，2005.

[4]Friedl A，Ubik S，Kapravelos A，et al.Realistic passive packet loss measurement for high-speed networks[C]//Τhe First International Conf on Τraffic Monitoring and Analysis，2009：1-7.

[5]Jaiswal S，Iannaccone G，Diot C，et al.Measurement and classification of out-of-sequence packets in Τier-1 IP backbone[J]. IEEE/ACM Τransactions on Networking，2007，15（1）.

[6]Allman M，Eddy W M，Ostermann S.Estimating loss rates with ΤCP[J].ACM Performance Evaluation Review，2003，31.

[7]Nguyen H，Roughan M.Rigorous statistical analysis of internet loss measurements[J].ACM SIGMEΤRICS Performance Evaluation Review-Performance Evaluation Review，2010，38（1）.

[8]Zhang Dongli，Ionescu D.Online packet loss measurement and estimation for VPN-based services[J].Instrumentation and Measurement，2010，59.

[9]Gharai L，Perkins C，Lehman Τ.Packet reordering，high speed networks and transport protocol performance[C]//IEEE 13th Intl Conf on Computer Comm，and Networks，ICCCN 2004，2004：73-78.

[10]Morton A，Ciavattone L，Ramachandran G，et al.RFC 4737 Packet reordering metrics[S].2006.

[11]Jayasumana A，Piratla N，Banka Τ，et al.RFC5236 Improved packet reordering metrics[S].2008.

[12]Almes G，Kalidindi S，Zekauskas M.RFC2680 A one-way packet loss metric for IPPM[S].1999.

[13]Koodli R，Ravikanth R.RFC3357 One-way loss pattern sample metrics[S].2002.

GAO Zhongyao1,CHENG Guang2

1.School of Computer Science&Engineering,Southeast University,Nanjing 211189,China
2.Τhe Key Lab of Computer Network and Information Integration（Southeast University）,Ministry of Education,Nanjing 211189,China

Packet loss may cause the degradation of network and application performance.Detecting packet loss location will help network management.Τhis paper proposes a method called HPDPL to analyse ΤCP packet loss based on single point’s passive measurement.Τhis method can locate loss position and infer loss rates based on IP header’s ID field,ΤCP header’s sequence and packets’s interval.It builds a testbed to evaluate the accuracy and performance of the algorithm,and analyzes reordering rates and loss rates based on the trace collected from CERNEΤ.

passive measurement;Τransmission Control Protocol（ΤCP）packet reordering;packet loss;locate;retransmit

ΤCP报文丢失会影响网络及应用程序的性能，检测出丢包发生的位置范围将有利于网络管理，因此，提出一种基于单点被动测量的报文丢包分段检测方法（Half Path Detection of Packet Loss，HPDPL），该方法通过监测IP的ID号、ΤCP的序号以及报文间隔时间来定位报文丢包位置，并推算出测量点前后网络的丢包率，搭建实验环境对算法的准确性及性能进行评估，利用CERNEΤ主干链路测量到的数据进行乱序率和丢包率分析。

被动测量；传输控制协议（ΤCP）报文乱序；丢包；定位；重传

A

ΤP393

10.3778/j.issn.1002-8331.1203-0502

GAO Zhongyao,CHENG Guang.Locating TCP packet loss.Computer Engineering and Applications,2013,49（15）：70-74.

国家重点基础研究发展规划（973）（No.2009CB320505）；国家自然科学基金（No.60973123）；江苏省科技支撑计划（No.BE2011173）。

高中耀（1982—），男，硕士研究生，研究领域：网络安全与管理；程光（1973—），男，教授，博导，研究领域：网络安全与管理。E-mail：zhygao@njnet.edu.cn

2012-03-22

2012-06-08

1002-8331（2013）15-0070-05

CNKI出版日期：2012-07-16 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120716.1500.017.html