一種基于網(wǎng)絡(luò)編碼的新型TCP協(xié)議傳輸系統(tǒng)

本項(xiàng)目針對(duì)現(xiàn)有TCP協(xié)議在丟失率較高的網(wǎng)絡(luò)環(huán)境下所表現(xiàn)出的糟糕性能，提出基于網(wǎng)絡(luò)編碼的改造，以TCP-Vegas為基礎(chǔ)通過修改其源代碼(邏輯上在TCP層與IP層之間加入全新的網(wǎng)絡(luò)編碼層)實(shí)現(xiàn)在發(fā)送方對(duì)原始TCP報(bào)文段編碼，在接收方解碼，并針對(duì)網(wǎng)絡(luò)實(shí)時(shí)丟失率調(diào)整編碼報(bào)文段的發(fā)送冗余，以達(dá)到向TCP層掩蓋丟失的目的;同時(shí)加入處理器共享技術(shù)，該技術(shù)旨在用一個(gè)合適的初始速率來代替TCP的慢啟動(dòng)過程。最終提高網(wǎng)絡(luò)吞吐量和可靠性，縮短數(shù)據(jù)流完成時(shí)間。

1.網(wǎng)絡(luò)編碼：

2000年，以香港中文大學(xué)信息工程系為主的研究人員針對(duì)通訊網(wǎng)絡(luò)的瓶頸問題，提出了網(wǎng)絡(luò)編碼理論，以網(wǎng)絡(luò)編碼器取代路由器，在網(wǎng)絡(luò)中傳輸包的線性組合，在接收端通過解碼恢復(fù)出原始數(shù)據(jù)包。

網(wǎng)絡(luò)編碼的概念可以通過蝴蝶拓?fù)?/strong>圖來進(jìn)行簡單的說明，如圖1-1所示：

假設(shè)上圖中每條路徑單位時(shí)間內(nèi)只能傳輸1比特，則采用路由方式，UV鏈路會(huì)成為傳輸瓶頸，即只能傳輸a和b中的一個(gè)信息。若UV鏈路傳輸消息b，則信宿P能收到消息a和b，而信宿Q只能收到消息b;若UV鏈路傳輸消息a，則信宿Q能收到消息a和b，而信宿P只能收到消息a。兩者情況下，平均每個(gè)信宿節(jié)點(diǎn)的吞吐量為1.5比特。

同樣的條件下，若采用網(wǎng)絡(luò)編碼，即UV鏈路上傳輸?shù)氖窍和b的編碼，則信宿P可以接受消息a且譯碼出消息b，信宿Q可以接受消息b且譯碼出消息a。這樣，平均每個(gè)信宿節(jié)點(diǎn)的吞吐量為2比特。

從中可以得出，網(wǎng)絡(luò)編碼可以達(dá)到多播網(wǎng)絡(luò)的最大容量，而路由卻可能達(dá)不到。

網(wǎng)絡(luò)編碼自誕生以來，得到了迅速的發(fā)展。短短幾年，發(fā)表了幾百篇學(xué)術(shù)論文，并對(duì)許多相關(guān)學(xué)科產(chǎn)生了深遠(yuǎn)的影響，NC的理論研究范圍包括信息論及通信的幾乎每個(gè)領(lǐng)域，如隨機(jī)編碼，線性編碼，非線性編碼，靜態(tài)碼，群碼，卷積碼，Alphabet碼，算法協(xié)議，碼構(gòu)建，有環(huán)網(wǎng)絡(luò)，鏈路失效及其網(wǎng)絡(luò)管理，無向網(wǎng)絡(luò)，分離理論，密碼學(xué)，錯(cuò)誤檢測和糾錯(cuò)碼，多信源編碼，Cost Criteria，多-單播編碼，非均勻需求，最大流/刮集界，關(guān)聯(lián)信源編碼，疊加編碼，網(wǎng)絡(luò)互連，路由尋找，無線及衛(wèi)星網(wǎng)絡(luò)，Ad hoc網(wǎng)絡(luò)，傳感網(wǎng)絡(luò)，數(shù)據(jù)存儲(chǔ)及分布，矩陣?yán)碚?，?fù)雜性理論，圖論，隨機(jī)圖論，，多種物流(Multicommodity flow)，游戲理論，矩陣胚理論(Matriod theory)，信息論不等式，排隊(duì)論分析，樹裝箱(Tree Packing)率失真(rate-distortion)可逆網(wǎng)絡(luò)，多用戶信道，聯(lián)合網(wǎng)絡(luò)信道編碼，P2P網(wǎng)絡(luò)等。

國外多所著名大學(xué)如普林斯頓大學(xué)、麻省理工、瑞士EPFL 學(xué)院等和多家IT 公司的研究中心,包括微軟研究院、貝爾實(shí)驗(yàn)室、AT &T 的香農(nóng)信息實(shí)驗(yàn)室等都在積極開展對(duì)網(wǎng)絡(luò)編碼理論和應(yīng)用的研究。最近國內(nèi)學(xué)者也開始研究網(wǎng)絡(luò)編碼，如清華大學(xué)、西安電子科大、電子科技大學(xué)、北京郵電大學(xué)、中國科學(xué)技術(shù)大學(xué)、復(fù)旦大學(xué)、上海大學(xué)等。

2.TCP協(xié)議：

傳輸控制協(xié)議(TCP)是一種面向連接的、可靠的、基于字節(jié)流的運(yùn)輸層(Transport layer)通信協(xié)議。在簡化的計(jì)算機(jī)網(wǎng)絡(luò)OSI模型中，它完成第四層傳輸層所指定的功能。

TCP使用端口號(hào)，提供進(jìn)程到進(jìn)程的通信，是一種面向流的協(xié)議(如圖1-2)。它把在每一個(gè)方向傳送的數(shù)據(jù)字節(jié)都進(jìn)行編號(hào)。編號(hào)不一定從0開始，而是在之間產(chǎn)生一個(gè)隨機(jī)數(shù)作

為第一個(gè)字節(jié)的號(hào)碼。當(dāng)字節(jié)都被編上號(hào)后，TCP就給每一個(gè)報(bào)文段指派一個(gè)序號(hào)(該序號(hào)為報(bào)文段中第一個(gè)字節(jié)數(shù)據(jù)的編號(hào)，見圖1-3)。接收方接到報(bào)文后，要使用確認(rèn)號(hào)對(duì)它已收到的字節(jié)進(jìn)行確認(rèn)，確認(rèn)號(hào)是累計(jì)的，在數(shù)值上等于期望接收的下一個(gè)字節(jié)的編號(hào)。

在實(shí)際傳輸中，為了避免信道擁塞，我們完全可以只發(fā)送一個(gè)字節(jié)的數(shù)據(jù)，然后在發(fā)送下一個(gè)字節(jié)之前等待確認(rèn)。但如果信源和信宿之間的距離很大，那么信源就要在等待確認(rèn)時(shí)一直處于空閑狀態(tài)，信道吞吐率很低。為了完成流量控制，TCP使用滑動(dòng)窗口協(xié)議。

滑動(dòng)窗口如圖1-4所示，它可以展開、合攏和收縮，但這三種運(yùn)動(dòng)受接收端而不是發(fā)送端控制。

展開窗口表示窗口右沿向右移動(dòng)，允許從緩存中發(fā)送更多新的字節(jié)。合攏窗口表示窗口左沿向右移動(dòng)，某些字節(jié)已經(jīng)被確認(rèn)，發(fā)送端可以不必再保留?？s回窗口表示窗口右沿向左移動(dòng)，一般在現(xiàn)實(shí)情況中不被允許。

在現(xiàn)實(shí)情況中，常常會(huì)遇到報(bào)文段丟失，為了重傳丟失的報(bào)文段，TCP使用了重傳計(jì)時(shí)器，來處理重傳超時(shí)。當(dāng)TCP發(fā)送一個(gè)報(bào)文段時(shí)，它就創(chuàng)建這個(gè)特定報(bào)文段的重傳計(jì)時(shí)器。這可能會(huì)發(fā)生兩種情況[1]：

若計(jì)時(shí)器截止時(shí)間到之前收到了對(duì)這個(gè)特定報(bào)文段的確認(rèn)，則撤銷這個(gè)計(jì)時(shí)器。

若在收到了對(duì)這個(gè)特定報(bào)文段的確認(rèn)之前計(jì)時(shí)器截止期到，則重傳這個(gè)報(bào)文段，并把計(jì)時(shí)器復(fù)位。

TCP處理擁塞的一般策略是基于三個(gè)階段：慢開始，擁塞避免和擁塞檢測。在慢開始階段，發(fā)送端從非常慢的發(fā)送速率開始，但很快就把速率增大到一個(gè)門限。當(dāng)?shù)竭_(dá)門限時(shí)，數(shù)據(jù)率的增長就放慢以避免擁塞。最后如果檢測到擁塞，發(fā)送端就又回到慢開始或擁塞避免階段。

3.FPGA及Linux系統(tǒng)：

Spartan-6具有USB2 port，VGA，10/100 Ethernet端口和設(shè)備，滿足本項(xiàng)目對(duì)網(wǎng)絡(luò)環(huán)境設(shè)置的要求。

Linux操作系統(tǒng)具有開源、高效、移植性強(qiáng)等特點(diǎn)，可以通過修改其源碼把新型的TCP協(xié)議潛入其中，最終通過硬件實(shí)驗(yàn)直觀的展現(xiàn)新協(xié)議的優(yōu)點(diǎn)。

二. 項(xiàng)目可行性分析

本項(xiàng)目團(tuán)隊(duì)成員具有長時(shí)間的網(wǎng)絡(luò)編碼研究經(jīng)驗(yàn)，并各有所長，分別精通用戶界面設(shè)計(jì)、Linux源碼開發(fā)、FPGA與嵌入式系統(tǒng)設(shè)計(jì)，因此具備了人員基礎(chǔ)。指導(dǎo)老師李揮教授是網(wǎng)絡(luò)編碼理論研究的專家，在整個(gè)項(xiàng)目過程中會(huì)給我們悉心指導(dǎo)。

1.理論條件：

本項(xiàng)目組在網(wǎng)絡(luò)編碼與TCP協(xié)議融合方面已有了一定的研究基礎(chǔ)，形成了自己的一套理論，并已經(jīng)在NS-2仿真平臺(tái)上進(jìn)行了初步試驗(yàn)。Linux操作系統(tǒng)的獨(dú)特優(yōu)點(diǎn)可以把理論運(yùn)用到實(shí)際的點(diǎn)到點(diǎn)傳輸環(huán)境中。

2.軟硬件條件：

實(shí)驗(yàn)室已具備相關(guān)軟硬件條件：

NS-2仿真平臺(tái);

裝載CentOS 5.5操作系統(tǒng)的主機(jī)若干臺(tái);

NetFPG若干;

網(wǎng)線;

USB-UART數(shù)據(jù)線;

三. 設(shè)計(jì)原理

本項(xiàng)目研究對(duì)象為點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)通信，主要?jiǎng)?chuàng)新點(diǎn)為采用了網(wǎng)絡(luò)編碼和新型的TCP傳輸協(xié)議，最終目標(biāo)是實(shí)現(xiàn)網(wǎng)絡(luò)傳輸在數(shù)據(jù)丟失情況下的高可靠性和高吞吐量。項(xiàng)目的整理架構(gòu)如下(圖3-1)。

兩臺(tái)主機(jī)分別充當(dāng)通信系統(tǒng)的信源和信宿，其中的傳輸協(xié)議已改為新型的TCP協(xié)議。界面會(huì)顯示相應(yīng)的網(wǎng)絡(luò)傳輸參數(shù)以及直觀的展現(xiàn)傳輸數(shù)據(jù)(如視屏)的效果。傳輸網(wǎng)絡(luò)由FPGA組搭建而成，主要實(shí)現(xiàn)網(wǎng)絡(luò)丟失環(huán)境設(shè)置，數(shù)據(jù)存儲(chǔ)轉(zhuǎn)發(fā)，信號(hào)顯示等任務(wù)。

1.網(wǎng)絡(luò)編碼層設(shè)計(jì)：

網(wǎng)絡(luò)編碼層設(shè)計(jì)是本項(xiàng)目的核心，是整個(gè)系統(tǒng)的靈魂。

各模塊說明如下：

報(bào)文段仲裁器1

位于TCP與NC層之間的仲裁器。具備判斷2種類型數(shù)據(jù)的能力：

1.來自TCP的數(shù)據(jù)報(bào)文段;

2.來自TCP的用于連接等控制信號(hào)的報(bào)文段。

如果是1，則將其放入輸入緩存;如果是2則直接送往IP層。報(bào)文段仲裁器2

位于IP與NC層之間的仲裁器。具備判斷3種類型數(shù)據(jù)的能力：

1.來自IP的已編碼報(bào)文段;

2.來自IP的用于連接等控制信號(hào)的報(bào)文段;

3. NC_ACK信號(hào)。

如果是1，則將其放入輸入緩存;如果是2則直接送往TCP層;如果是3，則交由NC_ACK判決器。

編碼模塊

NC_ACK判決器

用于判決NC_ACK信號(hào)，告訴編碼窗口應(yīng)刪除哪一個(gè)或哪幾個(gè)原始報(bào)文段，同時(shí)其負(fù)責(zé)“偽造”ACK發(fā)給上層TCP。

輸入緩存

保存來自TCP的數(shù)據(jù)報(bào)文段，因?yàn)榫幋a窗口每次僅讀取一個(gè)原始報(bào)文段，輸入緩存用來保存還未來得及處理的原始報(bào)文段。

編碼窗口

保存原始報(bào)文段，每次從輸入緩存讀取一個(gè)原始報(bào)文段，收到NC_ACK判決器發(fā)來的信號(hào)后即刪除相應(yīng)報(bào)文段。

隨機(jī)數(shù)產(chǎn)生器

產(chǎn)生0~255的隨機(jī)系數(shù)，不過在使用時(shí)應(yīng)避免0。

編碼器

利用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)系數(shù)對(duì)編碼窗口中存在的報(bào)文段編碼，若當(dāng)前編碼窗口只有一個(gè)報(bào)文段，則直接交給合成器，不進(jìn)行編碼。

合成器

將包頭產(chǎn)生器傳來的NC包頭和已編碼的報(bào)文段合成一個(gè)完整的NC層報(bào)文段，交給輸出緩存。

輸出緩存

接收合成器傳來的NC報(bào)文段，在此處設(shè)置輸出緩存也可起到控制發(fā)送速率的作用。

系數(shù)表

收發(fā)雙方在建立連接時(shí)由發(fā)送方傳遞給接收方的系數(shù)表，整個(gè)會(huì)話過程中系數(shù)表不變。根據(jù)系數(shù)偏移讀出相應(yīng)的系數(shù)。

包頭添加模塊

報(bào)文段編碼情況

即本次有多少報(bào)文段參與了編碼，這個(gè)在解碼時(shí)必須知道。

系數(shù)偏移

指示本次所使用的系數(shù)在系數(shù)表中開始的位置。

包頭產(chǎn)生器

將報(bào)文段編碼情況模塊和編碼系數(shù)模塊傳來的信息封裝成規(guī)定格式的NC包頭，再由合成器與相應(yīng)已編碼報(bào)文段組成NC報(bào)文段。

解碼模塊

輸入緩存

保存來自IP的數(shù)據(jù)報(bào)文段。

包頭處理

將包頭和負(fù)載分離，通過包頭中的系數(shù)偏移和編碼情況恢復(fù)出編碼系數(shù)。

系數(shù)緩存

存放編碼系數(shù)，并執(zhí)行高斯消元，確定新看見的報(bào)文段，若發(fā)現(xiàn)新的報(bào)文段則向NC_ACK產(chǎn)生器發(fā)送信號(hào)，否則丟棄這一組編碼系數(shù)并通知解碼緩存及報(bào)文段編碼模塊一并刪除這一組數(shù)據(jù)。

報(bào)文段編碼情況

和包頭添加模塊中一樣，存儲(chǔ)報(bào)文段參與的信息。

解碼緩存

存放編碼報(bào)文段數(shù)據(jù)，執(zhí)行與系數(shù)緩存相同的高斯消元，在解碼時(shí)從報(bào)文段編碼情況模塊獲取報(bào)文段編碼情況信息。

NC_ACK產(chǎn)生器

NC層獨(dú)有的ACK，收到系數(shù)緩存?zhèn)鱽淼男盘?hào)，便產(chǎn)生一個(gè)ACK并把它傳遞給編碼模塊的輸出緩存，用來告知發(fā)送方自己所看到的報(bào)文段情況，同時(shí)向ACK產(chǎn)生器發(fā)送信號(hào)。

輸出緩存

解碼的報(bào)文段按原來的順序存放在這里，然后傳給TCP，同樣可以進(jìn)行速率控制。

2.處理器共享技術(shù)的融合：

對(duì)于短流持續(xù)時(shí)間比其所需時(shí)間更長的情況，處理器共享(Processor Sharing)機(jī)制可以很好應(yīng)對(duì)，它的核心思想就是模擬處理器的資源在各線程間公平分配的特點(diǎn)，把路由器每個(gè)線卡的輸出鏈路帶寬平均分配給那些正在進(jìn)行的所有信息流。在建立連接時(shí)，每一跳路由根據(jù)當(dāng)前線卡使用情況及發(fā)送方的期望發(fā)送速率分配給其一個(gè)合適的初始速率，縮短以慢啟動(dòng)方式達(dá)到合理共享速率的時(shí)間。