TCP協議亂序數據包處理算法綜述

摘要:TCP協議是互聯網中最為重要的協議之一。然而，由于諸如多路由，并行處理，鏈路層重傳等原因，亂序數據包成為互聯網中不可避免的現象。本文首先分析了亂序數據包對于TCP協議的影響，然后分析比較了目前國內外學者提出各種解決方案，指出了各種方案的優點與不足，指明了TCP協議中亂序數據包處理算法的研究方向。

關鍵詞:TCP;擁塞控制;亂序數據包;快速重傳

1 引言

作為互聯網上最為核心的通信協議之一，TCP協議最早于1974年由Vinton Cerf和Robert Kahn共同提出。最初，TCP協議設計的主要目的是如何在異構的主機之間可靠地傳輸數據，因此主要包括基于窗口的流量控制，丟包恢復等功能。上個世紀80年代，由于互聯網用戶和流量的激增，互聯網經歷了多次嚴重的擁塞崩潰事件。為了解決這一問題，上世紀80年代后期，Van Jacobson等人首次把擁塞控制應用到TCP協議當中，從而極大地改善了Internet上端到端連接的性能和穩定性，保證了整個互聯網的穩定運行[1]。TCP是目前互聯網中使用最廣泛的傳輸協議。非常多的應用，如FTP，Web，Email等，都采用了TCP協議。根據2009年11月份的最新統計，互聯網總字節數的90%和總報文數的87%均使用TCP協議進行傳輸[2]。

隨著互聯網的飛速發展，各種新技術被應用到互聯網中，如多路由技術，并行處理技術，鏈路層重傳技術等。這些技術在提升互聯網性能的同時，也導致了傳輸層亂序數據包的出現。大量的研究表明，亂序數據包會使位于傳輸層的TCP協議性能大幅下降。國內外眾多學者已經提出了各種不同的方法來提高TCP協議在面臨亂序數據包時的性能。

本文首先分析了亂序數據包造成TCP性能下降的主要原因，然后討論了各國學者所提出的不同解決方案;在此基礎上給出了在面臨亂序數據包時，提高TCP協議性能的幾個研究方向。

2 亂序數據包對TCP協議的影響

TCP協議擁塞控制的基本原理是:當網絡發生擁塞時，發送端應減小發送速率。實際上，位于通信連接末端的TCP擁塞控制算法無法了解網絡中究竟是否真的發生了擁塞，只能根據接收端收到的信息推測網絡狀態。因此設定了一個假設前提，即分組丟失意味網絡擁塞。即使這樣，TCP協議還是無法確切了解是否真的發生了分組丟失事件，只能根據確認指示推測分組是否丟失。現行的TCP協議可以通過兩種方式來判定數據包的丟失[3]。

(1)重傳定時器超時。

(2)接收端收到一定數量的重復應答(通常為3個)。

TCP通過數據包的序列號來保證數據包的正確，按序交付。假設序列號為 的數據包丟失，接收端每收到一個序列號大于 的數據包都會認為這是一個亂序數據包，在數據包 被正確接收之前，每收到一個這樣的數據包，都將產生一個對于 的重復應答。如果發送端收到一定數量的重復應答，將認為該數據包丟失，并由此推測網絡發生了擁塞。此時，重傳丟失的數據包，并將擁塞窗口減半。

這種丟包判定方式有效的前提是:網絡結構穩定，同屬一個連接的所有數據包按照同一路徑到達接收端，并且中間路由采用先到先服務和FIFO的原則。在以上條件成立的情況下，數據包的到達遵循“先發先到”的原則。數據包如果沒有按序到達則意味著丟失。然而，這種丟包判定方式容易受到網絡中持續的亂序數據包的影響。

亂序數據包是一種數據包到達順序與發送順序不一致的網絡現象。許多針對網絡中數據包的亂序問題的觀察、測量和本質研究指出:數據包的亂序并不是網絡的病態行為，而是作為一種普遍現象伴隨著網絡一直存在。統計顯示約有0.1%-2%的數據包會經歷亂序事件[4]。

亂序數據包的出現會給TCP協議帶來很大影響:(1)不必要的傳輸層重傳，浪費帶寬;(2)擁塞窗口不必要的減小，降低網絡利用率。

3 現有的解決方案分析

針對亂序數據包對于傳輸層TCP協議的影響，眾多學者提出了不同的解決方案，主要包括以下三種。

3.1 增大觸發快速重傳的門限值

一些學者指出，將觸發快速重傳的門限值(dupthresh)固定為3，會使得TCP協議對于亂序數據包的容忍程度太低，容易誘發不必要的重傳。因此提出改變dupthresh的取值[5]。目前主要有三種dupthresh設定算法:

(1)當亂序數據包出現時，通過固定參數K增大dupthresh的取值。

該算法的主要思路是:當亂序數據包出現時，將快速重傳門限值dupthresh增大為dupthresh+K。為此，需要在接收端檢測亂序數據包事件。檢測過程如下:如果數據包在dupthresh之后到達，即，已經被判定為丟失的數據包到達接收端，則認為這是一個亂序數據包事件。此時，將dupthresh增大為dupthresh+K。此后，將按照新的dupthresh進行丟包判斷。

這種方法的優點是實現簡單，缺點也很明顯，接收端可能需要多個周期，才能將dupthresh設定為合理值。這個收斂過程和整個算法的性能依賴于K的選擇。

(2)將dupthresh動態設定為當前值與亂序數據包長度和的一半。

該算法的主要思路是:當接收端檢測到數據包缺失時，開始記錄亂序到達的數據包數量，稱為亂序數據包長度，記為L，直到缺失的數據包到達。此時，將快速重傳的門限值dupthresh修改為(dupthresh+L)/2。

這種方法的優點是，它能夠較第一種算法更為迅速地使dupthresh根據網絡狀態收斂于理想值。缺點在于一個偶然的較大的亂序數據包長度可能造成dupthresh過大，影響TCP協議的性能。

(3)根據亂序數據包長度，利用指數加權移動平均算法設定dupthresh。

為了克服上述兩種算法的缺陷，Leung等人在文獻[6]中提出利用指數加權移動平均算法(EWMA:Exponentially Weighted Moving Average)動態設定dupthresh。同第二種設定算法一樣，當接收端檢測到數據包缺失時，開始記錄亂序數據包的長度L，直到缺失的數據包到達。此時，根據以下公式，計算平均亂序數據包長度:

if L > avg

avg = (1-α)*avg + α*L

else

avg = (1-α*x)*avg + (α*x)*L

其中，α為EWMA因子，通常取1/3，x為乘性因子，通常取4。

隨后，將dupthresh設定為平均亂序數據包長度avg。這種算法的優點在于dupthresh可以根據網絡狀態動態更新，并且，避免了第二種算法中單個過大的亂序數據包長度對dupthresh造成的過大影響。缺點在于接收端需要增加統計變量，并且隨時更新亂序數據包長度也會對接收端的性能造成一定影響。

3.2 Eifel算法

R. Ludwig和R. Katz提出使用Eifel算法來減少由亂序數據包引發的偽超時與偽重傳對TCP協議的影響[7]。Eifel的原理如圖1所示，發送端在T1時刻發送報文S時，將時間戳插入TCP頭部。在T2時刻，發送端檢測到S丟失，重傳S，并執行擁塞控制算法。重傳的S與原始發送的S相比，包含不同的時間戳T2。當接收端收到原始的S后，發送應答時，包含原始S的發送時間T1。當此應答到達發送端時，發送端發現此應答包含的時間信息T1小于存儲與Retransmit TS變量中的T2，由此判斷此重傳為假重傳。當檢測到假重傳時，發送端會將擁塞窗口和慢啟動門限值恢復到錯誤重傳前的值，然后如同沒有發生錯誤重傳一樣繼續發送數據分組。

Eiefl算法的優點在于能夠在很短的時間內檢測出假重傳，從而避免了后續不必要的重傳和擁塞回退機制。Eiefl算法還可以解決分組亂序、分組重復等問題。Eifel算法的缺陷在于，Eifel算法必須使用TCP協議的數據段參數來進行錯誤重傳判斷，并且Eifel算法僅僅是在檢測到偽重傳時避免了擁塞窗口的減小，并不能減少偽重傳的數據包數量，因此不能減少偽重傳對帶寬的消耗。

3.3 DSACK機制

重復選擇確認機制(DSACK)通過擴展TCP協議的SACK選項來克服亂序數據包的影響[8]。

DSACK算法的原理如圖2所示，發送端發送S1-S4數據包。由于網絡原因造成S1數據包亂序，它在S4數據包之后到達接收端。因此S2，S3，S4數據包均會產生對S1的重復應答。在收到這3個重復應答后，發送端將重傳S1。當重傳的S1到達接收端后，會產生一個對于S5的重復應答，同時SACK信息會指明此重復應答是由S1引起的。當此應答到達發送端后，發送端就可以判斷出剛才對于S1的重傳是假重傳。

DSACK算法要求發送端維護檢測到分組丟失時的擁塞窗口和慢啟動門限值等信息，發送端根據DSACK信息檢測到假重傳時，將擁塞窗口和慢啟動門限值恢復到錯誤重傳前的值。雖然沒有增加分組的開銷，但是它無法解決網絡中的分組重復和ACK丟失等問題。如果包含DSACK信息的應答丟失，則接收端無法進行恢復。并且，由于DSACK信息在丟失恢復結束后才到達發送端，因此發送端在丟失恢復階段無法檢測到假重傳。

4 結束語

本文總結了目前國內外學者提出的幾種典型的TCP協議亂序數據包處理算法，并對這些算法進行了詳細的分析和比較。綜上所述，該領域仍存在著一些亟待解決的問題，未來的研究可以考慮從以下方面展開:

(1)充分利用TCP數據包頭部的閑置字段，描述鏈接及網絡狀態，接收端可以利用這些狀態參數，判斷缺失的數據包是否是由于網絡擁塞導致。

(2)設計更加合理的快速重傳門限值設定算法，使其能夠以較快的速度收斂于真實網絡狀態，同時算法應盡量減輕接收端的計算量和存儲空間開銷。

(3)利用接收端已知參數，如往返時延，重傳超時時間等，在不增加接收端開銷的基礎上，判斷亂序數據包的出現。

參考文獻

[1] Nagle J. RFC896: Congestion control in IP/TCP Internet works. Internet Engineering Task Force， 1984.

[2] Internet2 NetFlow: Weekly reports. http://netflow.internet2.edu/weekly/. 2009， 11.

[3] Allman M， Paxson V， Stevens W. RFC 2581: TCP Congestion Control. Internet Engineering Task Force， 1999.

[4] Bennett J C R， Partridge C， Shectman N. Packet Reordering is Not Pathological Network Behavior [J]. IEEE/ACM Transactions on Networking， 1999， 7 (6): 789-798.

[5] Chaudhary R， Jacob L. Corruption and Reordering Robust TCP-Friendly Rate Contro l [J]. Computer Communications， 2005， 28: 97-107.

[6] Leung K C， Ma C. Enhancing TCP Performance to Persistent Packet Reordering [J]. Journal of Communication and Networks， 2005， 7(3):385-393.

[7] Ludwig R， Katz R. The Eifel Algorithm: Making TCP Robust Against Spurious Retransmissions [J]. Computer Communication Review， 2000， 30(1): 30-36.

[8]Floyd S， Mahdavi J， Mathis M. RFC 2883: An Extension to the Selective Acknowledgement (SACK) Option for TCP， Internet Engineering Task Force， 2000.