网络丢包在线检测算法研究

左延智，王 娟，吴训吉，张宗鹏

（1.北京跟踪与通信技术研究所，北京 100094；2.北京新宇航星科技有限公司，北京 100080）

0 引言

在网络通信中，网络丢包是最常见的故障之一。丢包会引起网速降低甚至造成网络中断。网络运维人员在日常的网络维护过程中，必须做到“早发现”、“早解决”。通常会借助各种仪器仪表或网络性能监测系统检测网络丢包，检测方法大致可分为两类：主动测试和被动测试。主动测试是指测试设备向被测网络中注入一定数量的网络数据包，在接收端判断是否丢包，各类网络测试仪表都可以实现主动测试；被动测试是指测试设备通过捕获网络数据包，通过算法判断丢包。主动测试遵循RFC2544测试标准，测试仪表广泛应用。本文只探讨被动测试算法，即在线丢包检测算法及其解决方案，通过横向比较和应用场景分析，发现这些算法的长处和局限。

1 网络丢包及检测方式

1.1 网络丢包的定义

网络丢包（Packet lost）在百度百科中有比较准确的定义[1]：

定义1：丢包是指一个或多个数据包的数据无法透过网上到达目的地。

1.2 网络丢包的涵义

接收方可以直观感觉到丢包，例如：图像出现“马赛克”或者报文显示错误。但仅仅从通信结果来判断是否丢包又是不够严格的。例如：TCP 协议发现丢包时会自动请求重发，使得通信完整，掩盖了丢包。本文补充了上述定义：

定义2：丢包是相邻的两个数据包在一定时间范围内无法透过网络都到达目的地，或者不能保持原有次序。

定义2首先增加了时间限制，如果数据包不能在指定的时间期限内到达目的地，也被定义为“丢包”。其次增加了先后次序限制。在网络传输中路由器可以自主选择最合适的路由，数据包到达目的地时有可能前后颠倒形成“错序”。

图1 举例说明丢包和错序示意图

例如：源方发送了6个数据包，目的方实际接收次序是：第一、第二、第四、第六、第六、第五、第三包，如图1所示。操作系统会在协议栈中自动调整次序，通信成功。从用户角度似乎没有丢包。但是根据定义2，我们认为出现了2次“丢包”，2次“错序”，1次“重包”。

在航天业务网中，实时通信是最常见的通信方式，例如：观测设备连续获得了目标的6个位置数据，传送给接收方。如果在通信过程中次序错乱，即使在接收方收满了这6个位置数据，也恢复了先后次序，但已经延误了接收方的实时状态获取。因此，必须监测这些特殊意义的丢包。

1.3 丢包检测算法的分类

丢包检测算法分为离线检测和在线检测两大类：

（1）离线检测就是主动测试，计算公式如下：

例如：传统的ping 命令发送3个ICMP 协议数据包给目的地设备，经对方反馈可以得到丢包情况和时延参数。更精细的是用测试仪表，指定包频、包长、发包数量或时间等参数，模拟网络通信场景，检测丢包和测量时延。

（2）在线检测为被动测试。需要搭建一套丢包监测系统，即网络性能监测系统，包括了一个管理中心和若干台探针，探针会远程部署在各个重要的节点，例如核心交换机、路由器等处。

本文对各种在线丢包检测算法进行探讨，分析彼此优劣，为实际工作中的丢包检测提供建议。

2 第一类在线丢包检测算法（中心汇总判断）

根据判断丢包的位置算法可分为两类：第一类在管理中心汇总和判断；第二类由探针直接检测。

2.1 算法一：最佳在线丢包检测算法

最理想的检测算法基于特殊的部署方案。

2.1.1 监测设备的部署

算法实现需要部署至少3-4台探针和1套管理中心，部署示意图如图2所示：

探针1部署在源端的第一台交换机处，探针2部署在目的端的最后一台交换机处；在沿途的第i 台交换机部署探针3、第j 台交换机部署探针4；部署一个管理中心，用于接收各台探针上报的监测结果，综合处理得到丢包检测结果。

2.1.2 算法核心步骤

（1）每台探针都按照一定时间间隔将捕获的数据包摘要列表上报到管理中心。

图2 算法一监测设备部署示意图

（2）在管理中心从探针1的列表1中依次取出一个数据包，在探针2的最终序列2中检查是否包含。

如果未包含，则表示丢失了该数据包，检查探针3、探针4的列表中是否包含，从而确定丢失位置；

说明：此处丢包采用了定义2 中的时间限制（时间间隔）。超出这个间隔，即使探针2收到了，也被判为丢包。

2.1.3 算法特点

（1）算法优势：丢包检测完整，不会遗漏；各种协议均适合。

（2）算法劣势：对部署位置有严格要求。如果需要同时监视多组源端和目的端，就难以满足。

2.2 算法二：通用协议在线丢包检测算法

为了去除部署位置的严格要求，提出了通用协议在线丢包检测算法（简称“算法二”）。在图3中，举例描述了一个应用部署场景，选择网络中任意3台交换机或路由器的镜像端口部署3台探针。

图3 算法二监测设备部署示意图

本算法用到了IP 协议头结构中的ID（16位标识）字段。例如：图4显示了算法二的一个应用场景。

图4 算法二各个探针ID序列示意图

可以大致推测路由器的顺序是探针1、探针3、探针2，因为同一个ID 值（122，123，125，135，137等），时间戳满足这个顺序的概率最大；推测发送方的ID 序列为左侧的列表；ID 值=129的数据包在序列2中丢失。

2.2.1 算法的核心步骤

（1）每台探针都按照一定间隔将捕获的数据包ID 值及时间戳序列上报管理中心。

（2）在管理中心按照时间戳先后出现的概率大小排出路由先后次序。时间戳越小的越靠前。

（3）从排序最靠前的序列中依次取出一个数据包，在排序最靠后的序列中检查是否包含该数据包。如果未包含，则表示丢失了该数据包，继续确定丢失位置。

2.2.2 算法特点

（1）算法优势：各种协议均适合；对部署位置无要求，自动推导路由顺序。

（2）算法劣势：占用带宽较大，源端每发送一个数据包，探针都需要上报一个数据项，有多少探针就扩大多少倍；无法做到检测每一个丢包。因为算法基于推导的最早路由探针，如果最早探针已经丢包就无法检测。

2.3 算法三：改进型重点丢包检测算法

考虑到丢包是一种小概率事件，具有偶发性的特点，提出了改进型重点丢包检测算法（算法三）。

2.3.1 算法三由三个部分组成

（1）重点在线检测（自动模式）。由网络管理人员圈定一个重点监测范围，监测系统对此重点监测，检测方法是算法二。

（2）人工检索丢包信息（手动模式）。如果在重点监测范围之外用户反馈丢包了，则由管理中心下发命令，各个探针将丢包附近时间段内的所有数据上报，在管理中心进行逐个比较，得到丢包的位置等信息。

（3）辅助查找丢包（半主动模式）。“无一遗漏”地全面检查所有的测试流，按照一定策略例如：优先检索流量大的测试流；或者优先检索包频最快的测试流等，依次对测试流进行“全覆盖”。

2.3.2 算法的核心操作

（1）选择任何一个探针作为辅助者，上报过去一段时间内该测试流的ID 序列、时间戳及数量等信息。

（2）管理中心将包数量、第一个ID 值及时间戳、最后一个ID 值及时间戳下发给其他探针；

（3）各个探针比较两个ID 值间的包数量，如果相同，则没有丢包；如果不同，则上报本地的ID 值及时间戳序列。

（4）在管理中心采用算法二确定是否丢包，以及丢包位置。

“辅助查找丢包”还可以调整检索策略，先加大检索的时间范围，类似于快速粗扫描。如果某台探针发现了丢包，再缩小时间范围，进入精细扫描，采用算法二，确定丢包位置。对于每一个测试流，在网络上只上传一次ID 值序列，向其他探针下发的命令和上报的结果都很小，对网络影响不大。

2.3.3 算法三的特点

一是自动模式下可以在线监测重点测试流，数量、范围可控；二是手动模式下可以较快地相应用户的关切；三是半主动模式下算法以粗扫描方式尽最大可能覆盖所有的测试流，尽最大努力跟上网速。

3 第二类在线丢包检测算法（探针实时处理）

在很多实时传输协议中都有包序号字段，连续发送的数据包其包序号也连续，可以充分利用此特点。

3.1 算法四：实时在线丢包检测算法

实时在线丢包检测算法（算法四）在捕获数据包的同时就能检测出是否丢包。

如果序号差等于1，表示没有丢包；否则丢包，计算丢包数。探针检测到丢包后上报管理中心，管理中心汇总就可以知道最早丢失数据包的位置在哪一台探针处。

3.2 算法五：特殊实时在线丢包检测算法

在航天信息网中，为了通信安全在源端和目的端之间增加了编码设备和解码设备，例如：保密机。如图5所示。探针1处在编码之前，探针2处在解码之后，可以解析得到包序号。探针3、探针4处都已编码（加密），不能解析，无法执行算法四判断是否丢包。

图5 算法五监测设备部署示意图

算法五的核心操作：一是如果探针2发现丢包，上报管理中心；二是由管理中心下发命令给4台探针，要求上报丢包时间前后的所有数据包的ID值序列；三是在管理中心逐个比较4个ID值序列，就可以确定丢包的数量、丢包位置等信息。

3.3 算法六：分片包的丢包检测算法

在 TCP/IP 分 层 中， 数 据 链 路 层 用 MTU（Maximum Transmission Unit，最大传输单元）来限制所能传输的数据包大小。当发送的IP 数据报的大小超过了MTU 时，IP 层就需要对数据进行分片[3]。探针可以根据标志位、片偏移之间的关系直接判断是否丢失了分片包或者是第一包。

算法六的特点：一是算法很简单，在探针就可以完成，判断是否丢包；二是如果丢失最后一个分片，就会导致接收超时，需要特殊处理；三是如果丢失第一个分片，偏移量不能从0开始，不能解析应用层协议。

4 算法比较

以上提出了6个在线检测丢包的算法，比较如表1所示：

表1 算法比较

由此得出如下结论：一是在RTP 之类实时协议占多数的网络中，使用算法四和五，用包序号判断丢包，快速可靠；二是如果网络带宽足够，建议使用算法二，对任何协议均可判断丢包，适合复杂网络；三是如果网络带宽比较紧张，可以使用算法三，粗扫描与细扫描相结合；四是如果网络中有大包，则必须使用算法六，检测分片丢包。由此可见，还是应当根据网络实际情况和应用需求，灵活选择丢包检测算法。