網(wǎng)絡(luò)丟包在線檢測(cè)算法研究

左延智，王 娟，吳訓(xùn)吉，張宗鵬

（1.北京跟蹤與通信技術(shù)研究所，北京 100094；2.北京新宇航星科技有限公司，北京 100080）

0 引言

在網(wǎng)絡(luò)通信中，網(wǎng)絡(luò)丟包是最常見的故障之一。丟包會(huì)引起網(wǎng)速降低甚至造成網(wǎng)絡(luò)中斷。網(wǎng)絡(luò)運(yùn)維人員在日常的網(wǎng)絡(luò)維護(hù)過程中，必須做到“早發(fā)現(xiàn)”、“早解決”。通常會(huì)借助各種儀器儀表或網(wǎng)絡(luò)性能監(jiān)測(cè)系統(tǒng)檢測(cè)網(wǎng)絡(luò)丟包，檢測(cè)方法大致可分為兩類：主動(dòng)測(cè)試和被動(dòng)測(cè)試。主動(dòng)測(cè)試是指測(cè)試設(shè)備向被測(cè)網(wǎng)絡(luò)中注入一定數(shù)量的網(wǎng)絡(luò)數(shù)據(jù)包，在接收端判斷是否丟包，各類網(wǎng)絡(luò)測(cè)試儀表都可以實(shí)現(xiàn)主動(dòng)測(cè)試；被動(dòng)測(cè)試是指測(cè)試設(shè)備通過捕獲網(wǎng)絡(luò)數(shù)據(jù)包，通過算法判斷丟包。主動(dòng)測(cè)試遵循RFC2544測(cè)試標(biāo)準(zhǔn)，測(cè)試儀表廣泛應(yīng)用。本文只探討被動(dòng)測(cè)試算法，即在線丟包檢測(cè)算法及其解決方案，通過橫向比較和應(yīng)用場(chǎng)景分析，發(fā)現(xiàn)這些算法的長(zhǎng)處和局限。

1 網(wǎng)絡(luò)丟包及檢測(cè)方式

1.1 網(wǎng)絡(luò)丟包的定義

網(wǎng)絡(luò)丟包（Packet lost）在百度百科中有比較準(zhǔn)確的定義[1]：

定義1：丟包是指一個(gè)或多個(gè)數(shù)據(jù)包的數(shù)據(jù)無法透過網(wǎng)上到達(dá)目的地。

1.2 網(wǎng)絡(luò)丟包的涵義

接收方可以直觀感覺到丟包，例如：圖像出現(xiàn)“馬賽克”或者報(bào)文顯示錯(cuò)誤。但僅僅從通信結(jié)果來判斷是否丟包又是不夠嚴(yán)格的。例如：TCP 協(xié)議發(fā)現(xiàn)丟包時(shí)會(huì)自動(dòng)請(qǐng)求重發(fā)，使得通信完整，掩蓋了丟包。本文補(bǔ)充了上述定義：

定義2：丟包是相鄰的兩個(gè)數(shù)據(jù)包在一定時(shí)間范圍內(nèi)無法透過網(wǎng)絡(luò)都到達(dá)目的地，或者不能保持原有次序。

定義2首先增加了時(shí)間限制，如果數(shù)據(jù)包不能在指定的時(shí)間期限內(nèi)到達(dá)目的地，也被定義為“丟包”。其次增加了先后次序限制。在網(wǎng)絡(luò)傳輸中路由器可以自主選擇最合適的路由，數(shù)據(jù)包到達(dá)目的地時(shí)有可能前后顛倒形成“錯(cuò)序”。

圖1 舉例說明丟包和錯(cuò)序示意圖

例如：源方發(fā)送了6個(gè)數(shù)據(jù)包，目的方實(shí)際接收次序是：第一、第二、第四、第六、第六、第五、第三包，如圖1所示。操作系統(tǒng)會(huì)在協(xié)議棧中自動(dòng)調(diào)整次序，通信成功。從用戶角度似乎沒有丟包。但是根據(jù)定義2，我們認(rèn)為出現(xiàn)了2次“丟包”，2次“錯(cuò)序”，1次“重包”。

在航天業(yè)務(wù)網(wǎng)中，實(shí)時(shí)通信是最常見的通信方式，例如：觀測(cè)設(shè)備連續(xù)獲得了目標(biāo)的6個(gè)位置數(shù)據(jù)，傳送給接收方。如果在通信過程中次序錯(cuò)亂，即使在接收方收滿了這6個(gè)位置數(shù)據(jù)，也恢復(fù)了先后次序，但已經(jīng)延誤了接收方的實(shí)時(shí)狀態(tài)獲取。因此，必須監(jiān)測(cè)這些特殊意義的丟包。

1.3 丟包檢測(cè)算法的分類

丟包檢測(cè)算法分為離線檢測(cè)和在線檢測(cè)兩大類：

（1）離線檢測(cè)就是主動(dòng)測(cè)試，計(jì)算公式如下：

例如：傳統(tǒng)的ping 命令發(fā)送3個(gè)ICMP 協(xié)議數(shù)據(jù)包給目的地設(shè)備，經(jīng)對(duì)方反饋可以得到丟包情況和時(shí)延參數(shù)。更精細(xì)的是用測(cè)試儀表，指定包頻、包長(zhǎng)、發(fā)包數(shù)量或時(shí)間等參數(shù)，模擬網(wǎng)絡(luò)通信場(chǎng)景，檢測(cè)丟包和測(cè)量時(shí)延。

（2）在線檢測(cè)為被動(dòng)測(cè)試。需要搭建一套丟包監(jiān)測(cè)系統(tǒng)，即網(wǎng)絡(luò)性能監(jiān)測(cè)系統(tǒng)，包括了一個(gè)管理中心和若干臺(tái)探針，探針會(huì)遠(yuǎn)程部署在各個(gè)重要的節(jié)點(diǎn)，例如核心交換機(jī)、路由器等處。

本文對(duì)各種在線丟包檢測(cè)算法進(jìn)行探討，分析彼此優(yōu)劣，為實(shí)際工作中的丟包檢測(cè)提供建議。

2 第一類在線丟包檢測(cè)算法（中心匯總判斷）

根據(jù)判斷丟包的位置算法可分為兩類：第一類在管理中心匯總和判斷；第二類由探針直接檢測(cè)。

2.1 算法一：最佳在線丟包檢測(cè)算法

最理想的檢測(cè)算法基于特殊的部署方案。

2.1.1 監(jiān)測(cè)設(shè)備的部署

算法實(shí)現(xiàn)需要部署至少3-4臺(tái)探針和1套管理中心，部署示意圖如圖2所示：

探針1部署在源端的第一臺(tái)交換機(jī)處，探針2部署在目的端的最后一臺(tái)交換機(jī)處；在沿途的第i 臺(tái)交換機(jī)部署探針3、第j 臺(tái)交換機(jī)部署探針4；部署一個(gè)管理中心，用于接收各臺(tái)探針上報(bào)的監(jiān)測(cè)結(jié)果，綜合處理得到丟包檢測(cè)結(jié)果。

2.1.2 算法核心步驟

（1）每臺(tái)探針都按照一定時(shí)間間隔將捕獲的數(shù)據(jù)包摘要列表上報(bào)到管理中心。

圖2 算法一監(jiān)測(cè)設(shè)備部署示意圖

（2）在管理中心從探針1的列表1中依次取出一個(gè)數(shù)據(jù)包，在探針2的最終序列2中檢查是否包含。

如果未包含，則表示丟失了該數(shù)據(jù)包，檢查探針3、探針4的列表中是否包含，從而確定丟失位置；

說明：此處丟包采用了定義2 中的時(shí)間限制（時(shí)間間隔）。超出這個(gè)間隔，即使探針2收到了，也被判為丟包。

2.1.3 算法特點(diǎn)

（1）算法優(yōu)勢(shì)：丟包檢測(cè)完整，不會(huì)遺漏；各種協(xié)議均適合。

（2）算法劣勢(shì)：對(duì)部署位置有嚴(yán)格要求。如果需要同時(shí)監(jiān)視多組源端和目的端，就難以滿足。

2.2 算法二：通用協(xié)議在線丟包檢測(cè)算法

為了去除部署位置的嚴(yán)格要求，提出了通用協(xié)議在線丟包檢測(cè)算法（簡(jiǎn)稱“算法二”）。在圖3中，舉例描述了一個(gè)應(yīng)用部署場(chǎng)景，選擇網(wǎng)絡(luò)中任意3臺(tái)交換機(jī)或路由器的鏡像端口部署3臺(tái)探針。

圖3 算法二監(jiān)測(cè)設(shè)備部署示意圖

本算法用到了IP 協(xié)議頭結(jié)構(gòu)中的ID（16位標(biāo)識(shí)）字段。例如：圖4顯示了算法二的一個(gè)應(yīng)用場(chǎng)景。

圖4 算法二各個(gè)探針I(yè)D序列示意圖

可以大致推測(cè)路由器的順序是探針1、探針3、探針2，因?yàn)橥粋€(gè)ID 值（122，123，125，135，137等），時(shí)間戳滿足這個(gè)順序的概率最大；推測(cè)發(fā)送方的ID 序列為左側(cè)的列表；ID 值=129的數(shù)據(jù)包在序列2中丟失。

2.2.1 算法的核心步驟

（1）每臺(tái)探針都按照一定間隔將捕獲的數(shù)據(jù)包ID 值及時(shí)間戳序列上報(bào)管理中心。

（2）在管理中心按照時(shí)間戳先后出現(xiàn)的概率大小排出路由先后次序。時(shí)間戳越小的越靠前。

（3）從排序最靠前的序列中依次取出一個(gè)數(shù)據(jù)包，在排序最靠后的序列中檢查是否包含該數(shù)據(jù)包。如果未包含，則表示丟失了該數(shù)據(jù)包，繼續(xù)確定丟失位置。

2.2.2 算法特點(diǎn)

（1）算法優(yōu)勢(shì)：各種協(xié)議均適合；對(duì)部署位置無要求，自動(dòng)推導(dǎo)路由順序。

（2）算法劣勢(shì)：占用帶寬較大，源端每發(fā)送一個(gè)數(shù)據(jù)包，探針都需要上報(bào)一個(gè)數(shù)據(jù)項(xiàng)，有多少探針就擴(kuò)大多少倍；無法做到檢測(cè)每一個(gè)丟包。因?yàn)樗惴ɑ谕茖?dǎo)的最早路由探針，如果最早探針已經(jīng)丟包就無法檢測(cè)。

2.3 算法三：改進(jìn)型重點(diǎn)丟包檢測(cè)算法

考慮到丟包是一種小概率事件，具有偶發(fā)性的特點(diǎn)，提出了改進(jìn)型重點(diǎn)丟包檢測(cè)算法（算法三）。

2.3.1 算法三由三個(gè)部分組成

（1）重點(diǎn)在線檢測(cè)（自動(dòng)模式）。由網(wǎng)絡(luò)管理人員圈定一個(gè)重點(diǎn)監(jiān)測(cè)范圍，監(jiān)測(cè)系統(tǒng)對(duì)此重點(diǎn)監(jiān)測(cè)，檢測(cè)方法是算法二。

（2）人工檢索丟包信息（手動(dòng)模式）。如果在重點(diǎn)監(jiān)測(cè)范圍之外用戶反饋丟包了，則由管理中心下發(fā)命令，各個(gè)探針將丟包附近時(shí)間段內(nèi)的所有數(shù)據(jù)上報(bào)，在管理中心進(jìn)行逐個(gè)比較，得到丟包的位置等信息。

（3）輔助查找丟包（半主動(dòng)模式）。“無一遺漏”地全面檢查所有的測(cè)試流，按照一定策略例如：優(yōu)先檢索流量大的測(cè)試流；或者優(yōu)先檢索包頻最快的測(cè)試流等，依次對(duì)測(cè)試流進(jìn)行“全覆蓋”。

2.3.2 算法的核心操作

（1）選擇任何一個(gè)探針作為輔助者，上報(bào)過去一段時(shí)間內(nèi)該測(cè)試流的ID 序列、時(shí)間戳及數(shù)量等信息。

（2）管理中心將包數(shù)量、第一個(gè)ID 值及時(shí)間戳、最后一個(gè)ID 值及時(shí)間戳下發(fā)給其他探針；

（3）各個(gè)探針比較兩個(gè)ID 值間的包數(shù)量，如果相同，則沒有丟包；如果不同，則上報(bào)本地的ID 值及時(shí)間戳序列。

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

“輔助查找丟包”還可以調(diào)整檢索策略，先加大檢索的時(shí)間范圍，類似于快速粗掃描。如果某臺(tái)探針發(fā)現(xiàn)了丟包，再縮小時(shí)間范圍，進(jìn)入精細(xì)掃描，采用算法二，確定丟包位置。對(duì)于每一個(gè)測(cè)試流，在網(wǎng)絡(luò)上只上傳一次ID 值序列，向其他探針下發(fā)的命令和上報(bào)的結(jié)果都很小，對(duì)網(wǎng)絡(luò)影響不大。

2.3.3 算法三的特點(diǎn)

一是自動(dòng)模式下可以在線監(jiān)測(cè)重點(diǎn)測(cè)試流，數(shù)量、范圍可控；二是手動(dòng)模式下可以較快地相應(yīng)用戶的關(guān)切；三是半主動(dòng)模式下算法以粗掃描方式盡最大可能覆蓋所有的測(cè)試流，盡最大努力跟上網(wǎng)速。

3 第二類在線丟包檢測(cè)算法（探針實(shí)時(shí)處理）

在很多實(shí)時(shí)傳輸協(xié)議中都有包序號(hào)字段，連續(xù)發(fā)送的數(shù)據(jù)包其包序號(hào)也連續(xù)，可以充分利用此特點(diǎn)。

3.1 算法四：實(shí)時(shí)在線丟包檢測(cè)算法

實(shí)時(shí)在線丟包檢測(cè)算法（算法四）在捕獲數(shù)據(jù)包的同時(shí)就能檢測(cè)出是否丟包。

如果序號(hào)差等于1，表示沒有丟包；否則丟包，計(jì)算丟包數(shù)。探針檢測(cè)到丟包后上報(bào)管理中心，管理中心匯總就可以知道最早丟失數(shù)據(jù)包的位置在哪一臺(tái)探針處。

3.2 算法五：特殊實(shí)時(shí)在線丟包檢測(cè)算法

在航天信息網(wǎng)中，為了通信安全在源端和目的端之間增加了編碼設(shè)備和解碼設(shè)備，例如：保密機(jī)。如圖5所示。探針1處在編碼之前，探針2處在解碼之后，可以解析得到包序號(hào)。探針3、探針4處都已編碼（加密），不能解析，無法執(zhí)行算法四判斷是否丟包。

圖5 算法五監(jiān)測(cè)設(shè)備部署示意圖

算法五的核心操作：一是如果探針2發(fā)現(xiàn)丟包，上報(bào)管理中心；二是由管理中心下發(fā)命令給4臺(tái)探針，要求上報(bào)丟包時(shí)間前后的所有數(shù)據(jù)包的ID值序列；三是在管理中心逐個(gè)比較4個(gè)ID值序列，就可以確定丟包的數(shù)量、丟包位置等信息。

3.3 算法六：分片包的丟包檢測(cè)算法

在 TCP/IP 分 層 中， 數(shù) 據(jù) 鏈 路 層 用 MTU（Maximum Transmission Unit，最大傳輸單元）來限制所能傳輸?shù)臄?shù)據(jù)包大小。當(dāng)發(fā)送的IP 數(shù)據(jù)報(bào)的大小超過了MTU 時(shí)，IP 層就需要對(duì)數(shù)據(jù)進(jìn)行分片[3]。探針可以根據(jù)標(biāo)志位、片偏移之間的關(guān)系直接判斷是否丟失了分片包或者是第一包。

算法六的特點(diǎn)：一是算法很簡(jiǎn)單，在探針就可以完成，判斷是否丟包；二是如果丟失最后一個(gè)分片，就會(huì)導(dǎo)致接收超時(shí)，需要特殊處理；三是如果丟失第一個(gè)分片，偏移量不能從0開始，不能解析應(yīng)用層協(xié)議。

4 算法比較

以上提出了6個(gè)在線檢測(cè)丟包的算法，比較如表1所示：

表1 算法比較

由此得出如下結(jié)論：一是在RTP 之類實(shí)時(shí)協(xié)議占多數(shù)的網(wǎng)絡(luò)中，使用算法四和五，用包序號(hào)判斷丟包，快速可靠；二是如果網(wǎng)絡(luò)帶寬足夠，建議使用算法二，對(duì)任何協(xié)議均可判斷丟包，適合復(fù)雜網(wǎng)絡(luò)；三是如果網(wǎng)絡(luò)帶寬比較緊張，可以使用算法三，粗掃描與細(xì)掃描相結(jié)合；四是如果網(wǎng)絡(luò)中有大包，則必須使用算法六，檢測(cè)分片丟包。由此可見，還是應(yīng)當(dāng)根據(jù)網(wǎng)絡(luò)實(shí)際情況和應(yīng)用需求，靈活選擇丟包檢測(cè)算法。