有損網(wǎng)絡(luò)下的高性能傳輸控制協(xié)議研究

潘凱，李揮

（北京大學(xué) 深圳研究生院 深圳市融合網(wǎng)絡(luò)播控工程實(shí)驗(yàn)室 深圳市云計(jì)算關(guān)鍵技術(shù)和應(yīng)用重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518055）

1 引言

眾所周知，作為IP協(xié)議族核心協(xié)議之一的傳輸控制協(xié)議(TCP)為計(jì)算機(jī)端到端的通信提供了可靠保障。雖然其在因特網(wǎng)中扮演著如此重要的角色，但在有損網(wǎng)絡(luò)中卻由于外部干擾而表現(xiàn)得不盡如人意。導(dǎo)致這一問題的根源是其錯(cuò)誤地將所有數(shù)據(jù)分組丟失歸結(jié)為網(wǎng)絡(luò)擁塞而盲目減小擁塞窗口，事實(shí)上這一做法似乎僅在有線網(wǎng)絡(luò)中可行。于是，被強(qiáng)制減小的擁塞窗口由于必須經(jīng)歷擁塞避免階段的保守增加而導(dǎo)致鏈路使用率低下。

作為通信網(wǎng)絡(luò)（尤其是無線網(wǎng)絡(luò)）重要潛在技術(shù)之一的網(wǎng)絡(luò)編碼（network coding），其出現(xiàn)引起了世界范圍內(nèi)的極大關(guān)注。信息通常被看作是無法繼續(xù)壓縮的管道流水，而網(wǎng)絡(luò)編碼對其再次處理，從而得到了頑健性和有效性的進(jìn)一步提升。

以順序傳輸和順序響應(yīng)為特點(diǎn)的 TCP協(xié)議在某些極端情況下可能導(dǎo)致“隊(duì)頭阻塞”問題，即接收方已獲得序號較大的數(shù)據(jù)分組但遲遲未見序號較小的“隊(duì)頭”數(shù)據(jù)分組。網(wǎng)絡(luò)編碼能夠很好地解決這一問題，經(jīng)過編碼操作，編碼分組（原始數(shù)據(jù)分組的線性組合）的數(shù)量將代替原來的序號成為值得關(guān)心的重點(diǎn)。

網(wǎng)絡(luò)編碼和TCP協(xié)議相結(jié)合最早由MIT提出[3]。通過在收發(fā)雙方協(xié)議棧的傳輸層和網(wǎng)絡(luò)層之間加入獨(dú)立的網(wǎng)絡(luò)編碼層來實(shí)現(xiàn)上述結(jié)合思想。事實(shí)上，對傳輸層掩蓋數(shù)據(jù)分組丟失這一思想的普遍解決方法是通過鏈路層進(jìn)行重傳[4]，但這樣會使得鏈路層重傳和傳輸層重傳的交互過程變得異常復(fù)雜。新加入的網(wǎng)絡(luò)編碼層致力于通過冗余分組的方式向上層掩蓋丟失。一旦接收方收到數(shù)量足夠的編碼分組，便能通過解碼得到原始信息，上述思想可由圖1說明。

圖1 傳統(tǒng)TCP協(xié)議與帶有NC功能的TCP協(xié)議

冗余對于傳統(tǒng) TCP協(xié)議來說并不容易實(shí)現(xiàn)，因?yàn)榘l(fā)送方無法預(yù)先知曉將會丟失的數(shù)據(jù)分組。但如果發(fā)送的是經(jīng)過編碼的數(shù)據(jù)分組將會大不相同，因?yàn)槊總€(gè)數(shù)據(jù)分組均含有部分原始信息，一旦數(shù)量滿足解碼要求（編碼系數(shù)假定線性無關(guān)），傳輸便可視為提前結(jié)束。從圖1（a）可以看到，假設(shè)有3個(gè)數(shù)據(jù)分組需要傳輸，采用傳統(tǒng) TCP協(xié)議的發(fā)送方由于不能預(yù)知將會發(fā)生丟失的數(shù)據(jù)分組而無法輕易發(fā)送冗余分組，圖1（b）則僅需簡單地將原始數(shù)據(jù)分組多進(jìn)行一次編碼發(fā)送即可達(dá)到掩蓋丟失的目的。當(dāng)然上述過程必須建立在網(wǎng)絡(luò)狀況事先確定的情況下，比如圖中的丟失率就為33%。不過新問題隨之而來，即這個(gè)丟失率該如何獲知，因?yàn)樗鼘⒅苯記Q定冗余分組的數(shù)量：太少起不到作用，太多又容易阻塞網(wǎng)絡(luò)。

作為網(wǎng)絡(luò)編碼和 TCP協(xié)議結(jié)合的原型TCP-NC，其必然有諸多缺陷，于是文獻(xiàn)[6]對縮短解碼時(shí)延做了一些改進(jìn)。不過，關(guān)于冗余該如何確定始終未在文獻(xiàn)[3]和文獻(xiàn)[6]中提及。為此，本文設(shè)計(jì)了一個(gè)計(jì)算冗余的算法，并且對可能存在的系數(shù)開銷過大問題做了一些優(yōu)化。本文將這一使用網(wǎng)絡(luò)編碼并能夠動態(tài)調(diào)整冗余（dynamic redundancy）的新協(xié)議稱為TCP-NCDR。本文主要對比目前廣泛使用的Reno、Vegas[5]和Westwood[11]版本。

2 TCP-NCDR協(xié)議

與傳統(tǒng)TCP協(xié)議不同，在引入網(wǎng)絡(luò)編碼功能后接收方需要收集一定數(shù)量的編碼分組來恢復(fù)原始信息。因此，通常存放于網(wǎng)絡(luò)編碼層分組頭中的編碼系數(shù)[7,8]成了解碼的關(guān)鍵信息。由于編碼操作在大小為256的有限域上進(jìn)行，故域中每個(gè)元素將占用1 byte的空間。因特網(wǎng)中傳輸?shù)牡湫蛿?shù)據(jù)分組約為1400 byte，根據(jù)實(shí)驗(yàn)中的設(shè)置，盡管帶寬并不大，參與編碼的原始數(shù)據(jù)分組也能夠很輕易地超過60，而這一數(shù)字已經(jīng)大大超過了TCP分組頭和IP分組頭的長度，因而勢必會影響到有效載荷的使用率，并且隨著帶寬的增大這一數(shù)字還會進(jìn)一步增加。

雖然即使是在大小為256的域內(nèi)以隨機(jī)數(shù)作為編碼系數(shù)，其解碼成功率也能超過99.6%[13]，但直接這樣做在數(shù)據(jù)分組較多的情況下將顯得異常復(fù)雜。因此，事先選好編碼系數(shù)在一定程度上可以降低解碼的計(jì)算復(fù)雜度。考慮到如果參與編碼的原始數(shù)據(jù)分組“維度”不同（數(shù)據(jù)分組 a、b形成的編碼分組和a、b、c形成的編碼分組維度不同）可能會使得解碼稍顯容易的道理，本文提出的協(xié)議采用了預(yù)先選定的簡單系數(shù)。只要收發(fā)雙方深諳系數(shù)的使用規(guī)則，通信便可無障礙進(jìn)行。這里使用cod_num替代常規(guī)系數(shù)，其可以“告知”接收方當(dāng)前編碼分組中所含原始數(shù)據(jù)分組的數(shù)量。用向量nC表示第n次編碼所使用的系數(shù)向量

這里

假設(shè)pi表示索引為i的原始數(shù)據(jù)分組，Pn為第n次傳輸?shù)脑紨?shù)據(jù)分組列向量。當(dāng)沒有丟失發(fā)生時(shí)第n個(gè)發(fā)出的編碼分組ptx_n定義如下

簡單來說，seen能夠反映數(shù)據(jù)分組當(dāng)前是否可以被解碼。當(dāng)seen等于參與編碼的原始數(shù)據(jù)分組的個(gè)數(shù)時(shí)，接收方便可以通過解碼獲得原始數(shù)據(jù)。當(dāng)隨機(jī)丟失事件發(fā)生時(shí)，由當(dāng)前丟失引起的第n次重傳定義如下

這里假設(shè) ACK總能被發(fā)送方正確接收。顯然長度為1 byte的cod_num能夠表示256（28）個(gè)原始數(shù)據(jù)分組。loss的含義將在第3節(jié)介紹。

編碼系數(shù)和編碼方式如圖2所示，其中圖2（a）表示無丟失的情況，其他代表有丟失。這里并沒有將已被接收方確認(rèn)的數(shù)據(jù)分組從圖中刪除，而是保留下來形成一個(gè)下三角矩陣方便觀察，事實(shí)上可以通過高斯消元法得到符合現(xiàn)實(shí)情況的帶狀矩陣。圖2（b）反映了有一個(gè)數(shù)據(jù)分組丟失的場景，2個(gè)或多個(gè)數(shù)據(jù)分組丟失的情況與之類似。從圖中可以看出原本發(fā)送的第4個(gè)編碼分組發(fā)生了丟失，故從接收方對第5個(gè)編碼分組的響應(yīng)可以知道，接收方已經(jīng)“看見”4個(gè)原始數(shù)據(jù)分組，所以索引為5的數(shù)據(jù)分組需要重發(fā)。由此可見，如果ACK都能被正確接收，接收方就一定可以恢復(fù)出原始數(shù)據(jù)。

圖2 數(shù)據(jù)分組編碼方式和系數(shù)使用

證明 事實(shí)上總可以找到如圖2所示由正常傳輸分組ptx_i和重傳分組prtx_i構(gòu)成的可解碼塊。假設(shè)每個(gè)可解碼塊中僅有一個(gè)重傳分組prtx_i并且用 Rj表示接收方收到的除去ptx_j的系數(shù)矩陣

在上述假設(shè)下，當(dāng)正常傳輸分組 ptx_j+1到達(dá)時(shí)，接收方已收到j(luò)個(gè)編碼分組同時(shí)“看見”j個(gè)原始分組，所以索引為j+1的編碼分組需要重傳。因此，接收方便能獲得一個(gè)可解碼塊

3 動態(tài)冗余系數(shù)更新算法

本節(jié)將詳細(xì)描述 TCP-NCDR中掩蓋丟失的機(jī)制。

文獻(xiàn)[3]首次將冗余系數(shù) R用來彌補(bǔ)信道中的隨即丟失。顯然，R的值既不能太大也不能太小。因?yàn)樘o法向傳輸層掩蓋丟失致使重傳導(dǎo)致吞吐量低下，但如果太大過多的冗余分組又容易阻塞網(wǎng)絡(luò)。因此，理想的R值在理論上應(yīng)該等于成功接收率的倒數(shù)。然而，文獻(xiàn)[3]并沒有提及如何計(jì)算并且使R盡可能適應(yīng)網(wǎng)絡(luò)狀況。

文獻(xiàn)[6]為了不使用冗余系數(shù) R而引入了一個(gè)稱為loss的變量反映完成解碼還需發(fā)送編碼數(shù)據(jù)分組的個(gè)數(shù)，通過此變量，發(fā)送方可以較為準(zhǔn)確地確定編碼分組數(shù)量，但這種方法無法有效應(yīng)對重傳分組丟失的情況。

在每個(gè)編碼分組的頭部都有一個(gè)pktID的變量，這個(gè)變量與TCP頭部的序列號無關(guān)。序列號被用來確認(rèn)數(shù)據(jù)，并在最初的3次握手中由收發(fā)雙方識別及交換。而pktID表示編碼分組中所含原始數(shù)據(jù)分組的最大索引值。如一個(gè)編碼分組含有p2、p3和p4，則pktID便為4。傳輸過程中pktID每次增加1或者不變。當(dāng)一個(gè)編碼分組到達(dá)時(shí)，接收方首先檢查其是否有用，然后記錄下收到編碼分組的數(shù)量pktNUM并計(jì)算loss值

新的loss值將會附帶在ACK中傳給發(fā)送方。

注意到可解碼的條件是pktID和pktNUM相等，因此若loss為負(fù)則表示沒有意義，同時(shí)還必須注意是否存在線性相關(guān)的系數(shù)。

發(fā)送方收到ACK后開始計(jì)算diff_loss的值

這里loss_old是上一次 loss的值（loss初值為0）。如果 diff_loss小于 0，表示一個(gè)或多個(gè)重傳分組已經(jīng)被接收方確認(rèn)，則R應(yīng)減去相應(yīng)的值。否則，在發(fā)送diff_loss個(gè)編碼分組后R應(yīng)當(dāng)進(jìn)行調(diào)整

這里n是在傳輸方向鏈路上數(shù)據(jù)分組的個(gè)數(shù)。設(shè)鏈路帶寬為bw，時(shí)延為ld，n表示為

這里，R_old是前一次R的值（初值為1）。引入diff/n為的是能起到前一次重傳丟失后快速重傳的作用，因?yàn)檎Ｇ闆r下在這期間對前一次重傳響應(yīng)的ACK應(yīng)該已經(jīng)到達(dá)發(fā)送方。圖3是發(fā)送方更新冗余系數(shù)R的算法。

圖3 冗余系數(shù)R更新算法

圖4是冗余系數(shù)R更新過程的一個(gè)例子。

正如上面所提到的，loss隱含了為完成解碼發(fā)送方仍需重傳的編碼分組數(shù)量。若loss為0，則表示在收到上一個(gè) ACK時(shí)沒有數(shù)據(jù)分組丟失，不需要重傳。當(dāng)loss大于0，diff_loss為2個(gè)相鄰loss的差。若diff_loss大于0，則表示有新的丟失發(fā)生，那么冗余分組必須立即發(fā)送；若 diff_loss小于 0，表示diff_loss個(gè)冗余分組被接收方確認(rèn)；diff_loss等于0表示沒有新的丟失同時(shí)也沒有冗余分組被確認(rèn)。在此過程中，很有可能發(fā)生冗余分組丟失的情況，所以每次疊加的diff_loss/n便為先于RTO進(jìn)行重傳提供了契機(jī)。

圖4 更新冗余系數(shù)R的例子

通過上述算法，R在每次收到 ACK時(shí)都會得到更新。因此，R可以反映下層鏈路在RTT/2（通常以ms為單位）之前的情況。這使得發(fā)送方可以更精確地控制冗余系數(shù)，相比文獻(xiàn)[7]中的固定冗余系數(shù)是一個(gè)不小的改進(jìn)。

上面提到編碼分組的數(shù)量正比于帶寬和RTT。設(shè)帶寬為bw，信道丟失率為p，則未解碼的編碼分組個(gè)數(shù)N在數(shù)量級上有如下正比關(guān)系

這里將其看做為伯努利試驗(yàn)。bw·RTT/ pktsize表示收到第一個(gè) ACK時(shí)，在傳輸方向上數(shù)據(jù)分組的個(gè)數(shù)。考慮最壞的情況，假設(shè)穩(wěn)定傳輸狀態(tài)下某一個(gè)數(shù)據(jù)分組丟失，則其將導(dǎo)致在收到重傳數(shù)據(jù)分組以前的所有數(shù)據(jù)分組都無法解碼。此次傳輸可以看作是丟失發(fā)生時(shí)的“第一批”數(shù)據(jù)分組，因?yàn)榇@批數(shù)據(jù)分組發(fā)送出去后第一個(gè)返回的 ACK便會到達(dá)發(fā)送方，根據(jù)算法此時(shí)會進(jìn)行一次重傳。若此重傳數(shù)據(jù)分組不幸丟失，則將導(dǎo)致“第二批”數(shù)據(jù)分組無法解碼。不過此過程并不會一直持續(xù)下去，因?yàn)槠渫瑫r(shí)還會受到RTO的限制。故N的大小與重傳數(shù)據(jù)分組的接收情況有關(guān)，最壞的情況是重傳分組全部丟失。但只要有重傳分組到達(dá)接收方，就能使一部分編碼分組實(shí)現(xiàn)解碼。

4 仿真測試

4.1 TCP-NCDR的公平性

仿真所使用的拓?fù)浣Y(jié)構(gòu)如圖5所示，該結(jié)構(gòu)中通信雙方之間存在三段有線鏈路和一跳無線鏈路構(gòu)成，仿真采用NS2[12]軟件。

圖5 仿真拓?fù)?/p>

公平性是指某種相同的流應(yīng)當(dāng)能夠共享帶寬。仿真中分別建立了數(shù)量不等的（從1到10條）Reno以及 TCP-NCDR流。為了測試兩者的公平性，使用Jain公平性指數(shù)[9]

其中，n是連接的數(shù)量，xi表示第i條連接的吞吐量。F越接近1則說明公平性越好。圖6為Reno和TCPNCDR公平性的測試結(jié)果。可以看出，圖中TCP-NCDR的f值在不同場景下均接近1，說明其公平性較好。

圖6 協(xié)議公平性對比

4.2 TCP-NCDR的有效性

為了更好地凸顯TCP-NCDR對吞吐量的提升，使用歸一化吞吐量Tn

其中，TNCDR和TReno分別為TCP-NCDR和Reno的平均吞吐量。實(shí)驗(yàn)中數(shù)量不等的流（從 1～10條）將共享網(wǎng)絡(luò)帶寬，顯然，Tn越大對吞吐量的提升就越顯著。

從圖7可以看出，TCP-NCDR可以有效提升吞吐量，尤其在流數(shù)量比較少的情況下。隨著流數(shù)量的增加，網(wǎng)絡(luò)負(fù)載也變得更重，TCP-NCDR對吞吐量的提升也逐漸變小。這表明 TCP-NCDR尤其適用于負(fù)載較低的網(wǎng)絡(luò)。

圖7 協(xié)議有效性對比

因此，下面將在負(fù)載較低的情況下（設(shè)n=3）進(jìn)一步研究TCP-NCDR的性能。將S1-R1這條路徑作為目標(biāo)流量，其他2條作為背景流量。整個(gè)仿真時(shí)間設(shè)為3000 s。背景流量在5 s時(shí)開始，背景流量在10～15 s間隨機(jī)開始。實(shí)驗(yàn)重復(fù)10次，并計(jì)算出平均流量的95%置信區(qū)間，如圖8所示。從圖中可以看出，當(dāng)丟失率為0時(shí)，Reno的吞吐量要高于TCP-NCDR，這是受限于網(wǎng)絡(luò)編碼的編解碼速度。但是當(dāng)丟失率逐漸上升，Reno的性能也隨之下降，因?yàn)殡S機(jī)丟失使其擁塞窗口始終保持在相對較小的水平，而 TCP-NCDR由于冗余的存在而仍然保持較高的吞吐量。

接下來觀察在隨機(jī)丟失率20%的情況下2條流的完成時(shí)間。序列號和完成時(shí)間的關(guān)系如圖9所示。

4.3 TCP-NCDR的適應(yīng)性

TCP-Westwood不同于Reno的地方在于其在檢測到丟失之后通過將擁塞窗口設(shè)置為匹配當(dāng)前速率的大小，而非簡單使用常規(guī)的乘性減小方式[11]。因此，其相比Reno更適合用于無線網(wǎng)絡(luò)。

圖8 協(xié)議在低負(fù)載時(shí)的性能對比

圖9 流完成時(shí)間對比

為了驗(yàn)證TCP-NCDR的適應(yīng)性，人為將丟失率模仿現(xiàn)實(shí)環(huán)境做劇烈變化，如表1所示。吞吐量的值為每個(gè)2.5 s計(jì)算得出，仿真時(shí)間為1000 s，此實(shí)驗(yàn)中n=1。為了清晰地顯示個(gè)協(xié)議吞吐量隨丟失率的變化，將圖一分為二，如圖10(a)和圖10(b)所示。其中10(a)顯示了TCP-NCDR和Westwood吞吐量隨丟失率的變化，可以看到 TCP-NCDR可以對網(wǎng)絡(luò)環(huán)境的變化做出快速反應(yīng)，將吞吐量保持在較高的水平，提高信道利用率。而Westwood始終較低。

對于TCP-NC，將R固定為1.087（92%的倒數(shù)），也就是說，網(wǎng)絡(luò)編碼層可以在丟失率小于 8%時(shí)向傳輸層成功掩蓋丟失。如圖10(b)所示，在20～250 s時(shí)，TCP-NC的性能與TCP-NCDR相當(dāng)，因?yàn)榇藭r(shí)的R可滿足網(wǎng)絡(luò)需求，同樣700～800 s和950～100 s也可滿足需求。但在其他時(shí)候，R由于太小而無法掩蓋丟失，致使超時(shí)重傳經(jīng)常發(fā)生進(jìn)而導(dǎo)致吞吐量較低。表2還給出了該環(huán)境下通過權(quán)重計(jì)算得出的吞吐量理論最大值。

表1 丟失率隨時(shí)間變化關(guān)系

圖10 Westwood和TCP-NC與TCP-NCDR吞吐量對比

表2 通過權(quán)重計(jì)算得出吞吐量

下面不再固定信道丟失率，讓其在服從均值為μ的正態(tài)分布下隨機(jī)取值。考慮到丟失率不會為負(fù)，σ由 3σ原理計(jì)算得出。TCP-NC的冗系數(shù) R固定為μ的倒數(shù)。從圖 11中可以看出，由于丟失率不再固定，TCP-NC并不能很好地掩蓋隨機(jī)丟失。隨著μ的增大分布會變得更平，故TCP-NC的吞吐量也將下降得更快。

圖11 協(xié)議在丟失率服從正態(tài)分布下的性能對比

5 結(jié)束語

本文中提出了一種根據(jù)網(wǎng)絡(luò)狀況動態(tài)調(diào)整冗余系數(shù)R的方法，同時(shí)通過使用事先選定的系數(shù)來減少編碼分組首部的開銷。與固定冗余系數(shù)的TCP-NC相比，TCP-NCDR所發(fā)送的冗余分組更加準(zhǔn)確，同時(shí)能更好地向傳輸層掩蓋丟失。考慮到隨著參與編碼的原始數(shù)據(jù)分組數(shù)量增多而帶來的首部開銷增大，使用簡單系數(shù)并規(guī)定了系數(shù)使用原則。隨后，仿真從公平性、有效性和適應(yīng)性3方面對 TCP-NCDR和其他協(xié)議做了對比測試，結(jié)果顯示 TCP-NCDR在不失公平性的前提下，對于固定丟失率和動態(tài)丟失率的情況均能較好地向傳輸層掩蓋丟失。

下一步計(jì)劃將TCP-NCDR的機(jī)制在Linux內(nèi)核中修改并用實(shí)際PC搭建測試網(wǎng)絡(luò)。此外，還打算將注意力放在傳輸對用戶主觀感受產(chǎn)生的影響，而不僅僅是客觀性能數(shù)據(jù)的測量。

[1]AHLSWEDE R,CAI N,LI S Y,et al. Network information flow[J].IEEE Trans on Information Theory,2000,46(4):1204-1216.

[2]HO T. Networking from a Network Coding Perspective[D]. Massachusetts Institute of Technology,Dept of EECS,2004.

[3]SUNDARARAJAN J K,SHAH D,MEDARD M,et al. Network coding meets TCP[A]. Proceedings of IEEE INFOCOM[C]. 2009.280-288.

[4]PAUL S,AYANOGLU E,PORTA T F L,et al. An asymmetric protocol for digital cellular communications[A]. Proceedings of IEEE INFOCOM[C]. 1995.1053-1062.

[5]BRAMKO L S,S. MALLEY W O,PETERSON L L. TCP Vegas: new techniques for congestion detection and avoidance[A]. Proceedings of SIGCOMM ’94 Symposium[C]. 1994.24-35.

[6]CHEN J,TAN W,LIU L X. Towards zero loss for TCP in wireless networks[A]. Proceedings of IEEE IPCCC[C]. 2009.65-70.

[7]SUNDARARAJAN J K,SHAH D,MEDARD M,et al. Network coding meets TCP: theory and implementation[A]. Proceedings of IEEE[C]. 2011.490-512.

[8]CHOU P A,WU Y N,JAIN K. Practical network coding[A]. Proceedings of Allerton Conference on Communication,Control,and Computing[C]. 2003.

[9]JAIN R,The Art of Computer Systems Performance Analysis[M].New York: Wiley,1991.

[10]NS-2 network simulator[EB/OL]. http://www.isi.edu/nsnam.

[11]UCLA computer science department high performance internet lab TCP WESTWOOD home page[EB/OL].http://www.cs.ucla.edu/NRL/hpi/tcpw.

[12]ZANELLA A,PROCISSI G,GERLA M,et al. TCP westwood: analytic model and performance evaluation[A]. Proceedings of IEEE GLOBECOM[C]. 2001.1703-1707.

[13]WANG D,ZHANG Q,LIU J C. Partial network coding: theory and application for continuous sensor data collection[A]. Proceedings of IEEE International Workshop on Quality of Service’06[C]. 2006.93-101.