潘凱，李揮

（北京大學 深圳研究生院 深圳市融合網絡播控工程實驗室 深圳市云計算關鍵技術和應用重點實驗室，廣東 深圳 518055）

1 引言

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

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

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

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

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

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

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

2 TCP-NCDR協(xié)議

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

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

這里

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

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

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

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

圖2 數據分組編碼方式和系數使用

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 冗余系數R更新算法

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

正如上面所提到的，loss隱含了為完成解碼發(fā)送方仍需重傳的編碼分組數量。若loss為0，則表示在收到上一個 ACK時沒有數據分組丟失，不需要重傳。當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 更新冗余系數R的例子

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

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

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

4 仿真測試

4.1 TCP-NCDR的公平性

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

圖5 仿真拓撲

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

其中，n是連接的數量，xi表示第i條連接的吞吐量。F越接近1則說明公平性越好。圖6為Reno和TCPNCDR公平性的測試結果?？梢钥闯?，圖中TCP-NCDR的f值在不同場景下均接近1，說明其公平性較好。

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

4.2 TCP-NCDR的有效性

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

其中，TNCDR和TReno分別為TCP-NCDR和Reno的平均吞吐量。實驗中數量不等的流（從 1～10條）將共享網絡帶寬，顯然，Tn越大對吞吐量的提升就越顯著。

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

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

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

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

4.3 TCP-NCDR的適應性

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

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

圖9 流完成時間對比

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

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

表1 丟失率隨時間變化關系

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

表2 通過權重計算得出吞吐量

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

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

5 結束語

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

下一步計劃將TCP-NCDR的機制在Linux內核中修改并用實際PC搭建測試網絡。此外，還打算將注意力放在傳輸對用戶主觀感受產生的影響，而不僅僅是客觀性能數據的測量。

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