TCP協(xié)議亂序數(shù)據(jù)包處理算法綜述

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

關(guān)鍵詞:TCP;擁塞控制;亂序數(shù)據(jù)包;快速重傳

1 引言

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

隨著互聯(lián)網(wǎng)的飛速發(fā)展，各種新技術(shù)被應(yīng)用到互聯(lián)網(wǎng)中，如多路由技術(shù)，并行處理技術(shù)，鏈路層重傳技術(shù)等。這些技術(shù)在提升互聯(lián)網(wǎng)性能的同時，也導(dǎo)致了傳輸層亂序數(shù)據(jù)包的出現(xiàn)。大量的研究表明，亂序數(shù)據(jù)包會使位于傳輸層的TCP協(xié)議性能大幅下降。國內(nèi)外眾多學(xué)者已經(jīng)提出了各種不同的方法來提高TCP協(xié)議在面臨亂序數(shù)據(jù)包時的性能。

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

2 亂序數(shù)據(jù)包對TCP協(xié)議的影響

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

(1)重傳定時器超時。

(2)接收端收到一定數(shù)量的重復(fù)應(yīng)答(通常為3個)。

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

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

亂序數(shù)據(jù)包是一種數(shù)據(jù)包到達(dá)順序與發(fā)送順序不一致的網(wǎng)絡(luò)現(xiàn)象。許多針對網(wǎng)絡(luò)中數(shù)據(jù)包的亂序問題的觀察、測量和本質(zhì)研究指出:數(shù)據(jù)包的亂序并不是網(wǎng)絡(luò)的病態(tài)行為，而是作為一種普遍現(xiàn)象伴隨著網(wǎng)絡(luò)一直存在。統(tǒng)計顯示約有0.1%-2%的數(shù)據(jù)包會經(jīng)歷亂序事件[4]。

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

3 現(xiàn)有的解決方案分析

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

3.1 增大觸發(fā)快速重傳的門限值

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

(1)當(dāng)亂序數(shù)據(jù)包出現(xiàn)時，通過固定參數(shù)K增大dupthresh的取值。

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

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

(2)將dupthresh動態(tài)設(shè)定為當(dāng)前值與亂序數(shù)據(jù)包長度和的一半。

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

這種方法的優(yōu)點是，它能夠較第一種算法更為迅速地使dupthresh根據(jù)網(wǎng)絡(luò)狀態(tài)收斂于理想值。缺點在于一個偶然的較大的亂序數(shù)據(jù)包長度可能造成dupthresh過大，影響TCP協(xié)議的性能。

(3)根據(jù)亂序數(shù)據(jù)包長度，利用指數(shù)加權(quán)移動平均算法設(shè)定dupthresh。

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

if L > avg

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

else

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

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

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

3.2 Eifel算法

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

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

3.3 DSACK機制

重復(fù)選擇確認(rèn)機制(DSACK)通過擴展TCP協(xié)議的SACK選項來克服亂序數(shù)據(jù)包的影響[8]。

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

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

4 結(jié)束語

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

(1)充分利用TCP數(shù)據(jù)包頭部的閑置字段，描述鏈接及網(wǎng)絡(luò)狀態(tài)，接收端可以利用這些狀態(tài)參數(shù)，判斷缺失的數(shù)據(jù)包是否是由于網(wǎng)絡(luò)擁塞導(dǎo)致。

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

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

參考文獻

[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.