網絡丟包在線檢測算法研究

左延智，王 娟，吳訓吉，張宗鵬

（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 之類實時協議占多數的網絡中，使用算法四和五，用包序號判斷丟包，快速可靠；二是如果網絡帶寬足夠，建議使用算法二，對任何協議均可判斷丟包，適合復雜網絡；三是如果網絡帶寬比較緊張，可以使用算法三，粗掃描與細掃描相結合；四是如果網絡中有大包，則必須使用算法六，檢測分片丟包。由此可見，還是應當根據網絡實際情況和應用需求，靈活選擇丟包檢測算法。