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

潘凱，李揮

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

1 引言

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

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

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

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

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

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

作為網(wǎng)絡(luò)編碼和 TCP協(xié)議結(jié)合的原型TCP-NC，其必然有諸多缺陷，于是文獻[6]對縮短解碼時延做了一些改進。不過，關(guān)于冗余該如何確定始終未在文獻[3]和文獻[6]中提及。為此，本文設(shè)計了一個計算冗余的算法，并且對可能存在的系數(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ù)量的編碼分組來恢復原始信息。因此，通常存放于網(wǎng)絡(luò)編碼層分組頭中的編碼系數(shù)[7,8]成了解碼的關(guān)鍵信息。由于編碼操作在大小為256的有限域上進行，故域中每個元素將占用1 byte的空間。因特網(wǎng)中傳輸?shù)牡湫蛿?shù)據(jù)分組約為1400 byte，根據(jù)實驗中的設(shè)置，盡管帶寬并不大，參與編碼的原始數(shù)據(jù)分組也能夠很輕易地超過60，而這一數(shù)字已經(jīng)大大超過了TCP分組頭和IP分組頭的長度，因而勢必會影響到有效載荷的使用率，并且隨著帶寬的增大這一數(shù)字還會進一步增加。

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

這里

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真測試

4.1 TCP-NCDR的公平性

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

圖5 仿真拓撲

公平性是指某種相同的流應(yī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ù)量不等的流（從 1～10條）將共享網(wǎng)絡(luò)帶寬，顯然，Tn越大對吞吐量的提升就越顯著。

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

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

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

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

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

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

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

圖9 流完成時間對比

為了驗證TCP-NCDR的適應(yīng)性，人為將丟失率模仿現(xiàn)實環(huán)境做劇烈變化，如表1所示。吞吐量的值為每個2.5 s計算得出，仿真時間為1000 s，此實驗中n=1。為了清晰地顯示個協(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%時向傳輸層成功掩蓋丟失。如圖10(b)所示，在20～250 s時，TCP-NC的性能與TCP-NCDR相當，因為此時的R可滿足網(wǎng)絡(luò)需求，同樣700～800 s和950～100 s也可滿足需求。但在其他時候，R由于太小而無法掩蓋丟失，致使超時重傳經(jīng)常發(fā)生進而導致吞吐量較低。表2還給出了該環(huán)境下通過權(quán)重計算得出的吞吐量理論最大值。

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

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

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

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

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

5 結(jié)束語

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

下一步計劃將TCP-NCDR的機制在Linux內(nèi)核中修改并用實際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.