一種基于網絡編碼的新型TCP協議傳輸系統(tǒng)
一. 理論基礎
本項目針對現有TCP協議在丟失率較高的網絡環(huán)境下所表現出的糟糕性能,提出基于網絡編碼的改造,以TCP-Vegas為基礎通過修改其源代碼(邏輯上在TCP層與IP層之間加入全新的網絡編碼層)實現在發(fā)送方對原始TCP報文段編碼,在接收方解碼,并針對網絡實時丟失率調整編碼報文段的發(fā)送冗余,以達到向TCP層掩蓋丟失的目的;同時加入處理器共享技術,該技術旨在用一個合適的初始速率來代替TCP的慢啟動過程。最終提高網絡吞吐量和可靠性,縮短數據流完成時間。
1.網絡編碼:
2000年,以香港中文大學信息工程系為主的研究人員針對通訊網絡的瓶頸問題,提出了網絡編碼理論,以網絡編碼器取代路由器,在網絡中傳輸包的線性組合,在接收端通過解碼恢復出原始數據包。
網絡編碼的概念可以通過蝴蝶拓撲圖來進行簡單的說明,如圖1-1所示:
假設上圖中每條路徑單位時間內只能傳輸1比特,則采用路由方式,UV鏈路會成為傳輸瓶頸,即只能傳輸a和b中的一個信息。若UV鏈路傳輸消息b,則信宿P能收到消息a和b,而信宿Q只能收到消息b;若UV鏈路傳輸消息a,則信宿Q能收到消息a和b,而信宿P只能收到消息a。兩者情況下,平均每個信宿節(jié)點的吞吐量為1.5比特。
同樣的條件下,若采用網絡編碼,即UV鏈路上傳輸的是消息a和b的編碼,則信宿P可以接受消息a且譯碼出消息b,信宿Q可以接受消息b且譯碼出消息a。這樣,平均每個信宿節(jié)點的吞吐量為2比特。
從中可以得出,網絡編碼可以達到多播網絡的最大容量,而路由卻可能達不到。
網絡編碼自誕生以來,得到了迅速的發(fā)展。短短幾年,發(fā)表了幾百篇學術論文,并對許多相關學科產生了深遠的影響,NC的理論研究范圍包括信息論及通信的幾乎每個領域,如隨機編碼,線性編碼,非線性編碼,靜態(tài)碼,群碼,卷積碼,Alphabet碼,算法協議,碼構建,有環(huán)網絡,鏈路失效及其網絡管理,無向網絡,分離理論,密碼學,錯誤檢測和糾錯碼,多信源編碼,Cost Criteria,多-單播編碼,非均勻需求,最大流/刮集界,關聯信源編碼,疊加編碼,網絡互連,路由尋找,無線及衛(wèi)星網絡,Ad hoc網絡,傳感網絡,數據存儲及分布,矩陣理論,復雜性理論,圖論,隨機圖論,,多種物流(Multicommodity flow),游戲理論,矩陣胚理論(Matriod theory),信息論不等式,排隊論分析,樹裝箱(Tree Packing)率失真(rate-distortion)可逆網絡,多用戶信道,聯合網絡信道編碼,P2P網絡等。
國外多所著名大學如普林斯頓大學、麻省理工、瑞士EPFL 學院等和多家IT 公司的研究中心,包括微軟研究院、貝爾實驗室、AT &T 的香農信息實驗室等都在積極開展對網絡編碼理論和應用的研究。最近國內學者也開始研究網絡編碼,如清華大學、西安電子科大、電子科技大學、北京郵電大學、中國科學技術大學、復旦大學、上海大學等。
2.TCP協議:
傳輸控制協議(TCP)是一種面向連接的、可靠的、基于字節(jié)流的運輸層(Transport layer)通信協議。在簡化的計算機網絡OSI模型中,它完成第四層傳輸層所指定的功能。
TCP使用端口號,提供進程到進程的通信,是一種面向流的協議(如圖1-2)。它把在每一個方向傳送的數據字節(jié)都進行編號。編號不一定從0開始,而是在 之間產生一個隨機數作
為第一個字節(jié)的號碼。當字節(jié)都被編上號后,TCP就給每一個報文段指派一個序號(該序號為報文段中第一個字節(jié)數據的編號,見圖1-3)。接收方接到報文后,要使用確認號對它已收到的字節(jié)進行確認,確認號是累計的,在數值上等于期望接收的下一個字節(jié)的編號。
在實際傳輸中,為了避免信道擁塞,我們完全可以只發(fā)送一個字節(jié)的數據,然后在發(fā)送下一個字節(jié)之前等待確認。但如果信源和信宿之間的距離很大,那么信源就要在等待確認時一直處于空閑狀態(tài),信道吞吐率很低。為了完成流量控制,TCP使用滑動窗口協議。
滑動窗口如圖1-4所示,它可以展開、合攏和收縮,但這三種運動受接收端而不是發(fā)送端控制。
展開窗口表示窗口右沿向右移動,允許從緩存中發(fā)送更多新的字節(jié)。合攏窗口表示窗口左沿向右移動,某些字節(jié)已經被確認,發(fā)送端可以不必再保留??s回窗口表示窗口右沿向左移動,一般在現實情況中不被允許。
在現實情況中,常常會遇到報文段丟失,為了重傳丟失的報文段,TCP使用了重傳計時器,來處理重傳超時。當TCP發(fā)送一個報文段時,它就創(chuàng)建這個特定報文段的重傳計時器。這可能會發(fā)生兩種情況[1]:
若計時器截止時間到之前收到了對這個特定報文段的確認,則撤銷這個計時器。
若在收到了對這個特定報文段的確認之前計時器截止期到,則重傳這個報文段,并把計時器復位。
TCP處理擁塞的一般策略是基于三個階段:慢開始,擁塞避免和擁塞檢測。在慢開始階段,發(fā)送端從非常慢的發(fā)送速率開始,但很快就把速率增大到一個門限。當到達門限時,數據率的增長就放慢以避免擁塞。最后如果檢測到擁塞,發(fā)送端就又回到慢開始或擁塞避免階段。
3.FPGA及Linux系統(tǒng):
Spartan-6具有USB2 port,VGA,10/100 Ethernet端口和設備,滿足本項目對網絡環(huán)境設置的要求。
Linux操作系統(tǒng)具有開源、高效、移植性強等特點,可以通過修改其源碼把新型的TCP協議潛入其中,最終通過硬件實驗直觀的展現新協議的優(yōu)點。
二. 項目可行性分析
本項目團隊成員具有長時間的網絡編碼研究經驗,并各有所長,分別精通用戶界面設計、Linux源碼開發(fā)、FPGA與嵌入式系統(tǒng)設計,因此具備了人員基礎。指導老師李揮教授是網絡編碼理論研究的專家,在整個項目過程中會給我們悉心指導。
1.理論條件:
本項目組在網絡編碼與TCP協議融合方面已有了一定的研究基礎,形成了自己的一套理論,并已經在NS-2仿真平臺上進行了初步試驗。Linux操作系統(tǒng)的獨特優(yōu)點可以把理論運用到實際的點到點傳輸環(huán)境中。
2.軟硬件條件:
實驗室已具備相關軟硬件條件:
NS-2仿真平臺;
裝載CentOS 5.5操作系統(tǒng)的主機若干臺;
NetFPG若干;
網線;
USB-UART數據線;
三. 設計原理
本項目研究對象為點對點網絡通信,主要創(chuàng)新點為采用了網絡編碼和新型的TCP傳輸協議,最終目標是實現網絡傳輸在數據丟失情況下的高可靠性和高吞吐量。項目的整理架構如下(圖3-1)。
兩臺主機分別充當通信系統(tǒng)的信源和信宿,其中的傳輸協議已改為新型的TCP協議。界面會顯示相應的網絡傳輸參數以及直觀的展現傳輸數據(如視屏)的效果。傳輸網絡由FPGA組搭建而成,主要實現網絡丟失環(huán)境設置,數據存儲轉發(fā),信號顯示等任務。
1.網絡編碼層設計:
網絡編碼層設計是本項目的核心,是整個系統(tǒng)的靈魂。
各模塊說明如下:
報文段仲裁器1
位于TCP與NC層之間的仲裁器。具備判斷2種類型數據的能力:
1.來自TCP的數據報文段;
2.來自TCP的用于連接等控制信號的報文段。
如果是1,則將其放入輸入緩存;如果是2則直接送往IP層。[!--empirenews.page--]
報文段仲裁器2
位于IP與NC層之間的仲裁器。具備判斷3種類型數據的能力:
1.來自IP的已編碼報文段;
2.來自IP的用于連接等控制信號的報文段;
3. NC_ACK信號。
如果是1,則將其放入輸入緩存;如果是2則直接送往TCP層;如果是3,則交由NC_ACK判決器。
編碼模塊
NC_ACK判決器
用于判決NC_ACK信號,告訴編碼窗口應刪除哪一個或哪幾個原始報文段,同時其負責“偽造”ACK發(fā)給上層TCP。
輸入緩存
保存來自TCP的數據報文段,因為編碼窗口每次僅讀取一個原始報文段,輸入緩存用來保存還未來得及處理的原始報文段。
編碼窗口
保存原始報文段,每次從輸入緩存讀取一個原始報文段,收到NC_ACK判決器發(fā)來的信號后即刪除相應報文段。
隨機數產生器
產生0~255的隨機系數,不過在使用時應避免0。
編碼器
利用隨機數產生器產生的隨機系數對編碼窗口中存在的報文段編碼,若當前編碼窗口只有一個報文段,則直接交給合成器,不進行編碼。
合成器
將包頭產生器傳來的NC包頭和已編碼的報文段合成一個完整的NC層報文段,交給輸出緩存。
輸出緩存
接收合成器傳來的NC報文段,在此處設置輸出緩存也可起到控制發(fā)送速率的作用。
系數表
收發(fā)雙方在建立連接時由發(fā)送方傳遞給接收方的系數表,整個會話過程中系數表不變。根據系數偏移讀出相應的系數。
包頭添加模塊
報文段編碼情況
即本次有多少報文段參與了編碼,這個在解碼時必須知道。
系數偏移
指示本次所使用的系數在系數表中開始的位置。
包頭產生器
將報文段編碼情況模塊和編碼系數模塊傳來的信息封裝成規(guī)定格式的NC包頭,再由合成器與相應已編碼報文段組成NC報文段。
解碼模塊
輸入緩存
保存來自IP的數據報文段。
包頭處理
將包頭和負載分離,通過包頭中的系數偏移和編碼情況恢復出編碼系數。
系數緩存
存放編碼系數,并執(zhí)行高斯消元,確定新看見的報文段,若發(fā)現新的報文段則向NC_ACK產生器發(fā)送信號,否則丟棄這一組編碼系數并通知解碼緩存及報文段編碼模塊一并刪除這一組數據。
報文段編碼情況
和包頭添加模塊中一樣,存儲報文段參與的信息。
解碼緩存
存放編碼報文段數據,執(zhí)行與系數緩存相同的高斯消元,在解碼時從報文段編碼情況模塊獲取報文段編碼情況信息。
NC_ACK產生器
NC層獨有的ACK,收到系數緩存?zhèn)鱽淼男盘?,便產生一個ACK并把它傳遞給編碼模塊的輸出緩存,用來告知發(fā)送方自己所看到的報文段情況,同時向ACK產生器發(fā)送信號。
輸出緩存
解碼的報文段按原來的順序存放在這里,然后傳給TCP,同樣可以進行速率控制。
2.處理器共享技術的融合:
對于短流持續(xù)時間比其所需時間更長的情況,處理器共享(Processor Sharing)機制可以很好應對,它的核心思想就是模擬處理器的資源在各線程間公平分配的特點,把路由器每個線卡的輸出鏈路帶寬平均分配給那些正在進行的所有信息流。在建立連接時,每一跳路由根據當前線卡使用情況及發(fā)送方的期望發(fā)送速率分配給其一個合適的初始速率,縮短以慢啟動方式達到合理共享速率的時間。