基于嵌入式ＴＣＰ／ＩＰ協(xié)議棧的擁塞控制研究

摘要：結(jié)合計(jì)算機(jī)網(wǎng)絡(luò)和嵌入式系統(tǒng)軟件的發(fā)展現(xiàn)狀，總結(jié)了嵌入式TCP/IP協(xié)議棧的一般特點(diǎn)和處理過(guò)程，進(jìn)一步詳細(xì)地討論了協(xié)議棧中的擁塞控制機(jī)制，特別是TCP擁塞控制機(jī)制和IP擁塞控制機(jī)制的分類(lèi)，以及它們的實(shí)現(xiàn)算法，做出了詳細(xì)的分析和比較。明確地給出了當(dāng)前嵌入式TCP/IP協(xié)議棧中的擁塞控制解決方法。

關(guān)鍵詞：互聯(lián)網(wǎng)；嵌入式系統(tǒng)；協(xié)議棧；數(shù)據(jù)；報(bào)文；擁塞

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-3044(2008)31-0860-03

Research of Congestion Control Based on Embedded TCP/IP Protocol Stack

LI Chao1，2， HE Xian-bo1， WANG An-zhi1， HUANG Miao3

(1.Computer College， China West Normal University， Nanchong 637002， China; 2.Nanchong Tourism School， Nanchong 637000， China; 3.Software Engineering School， Pingdingshan University， Pingdingshan 467003， China)

Abstract: This paper according to the present development condition of the computer network and embedded system software， summing up the general characteristics and procecing of the embedded TCP/IP protocol stack. Furthermore， discussing Congestion Control mechanism of the protocol stack in detail， especially analyzing and comparing sorts and implement algorithm of TCP Congestion Control mechanism and IP Congestion Control mechanism.Finally， setting up present Congestion Control solving methods of embedded TCP/IP protocol stack.

Key words: Internet; embedded system; protocol stack; data; message; congestion

1 引言

計(jì)算機(jī)網(wǎng)絡(luò)的飛速發(fā)展，已經(jīng)改變了人們的生產(chǎn)和生活方式。數(shù)字化信息家電的日益普及，使嵌入式系統(tǒng)連接到網(wǎng)絡(luò)成為了可能。互聯(lián)網(wǎng)采用的是無(wú)連接的端到端數(shù)據(jù)包交換，提供“盡力而為”服務(wù)模型的設(shè)計(jì)機(jī)制。這種機(jī)制的最大優(yōu)勢(shì)是設(shè)計(jì)簡(jiǎn)單，可擴(kuò)展性強(qiáng)。然而隨著互聯(lián)網(wǎng)用戶(hù)數(shù)量的膨脹，網(wǎng)絡(luò)的擁塞問(wèn)題也越來(lái)越嚴(yán)重。據(jù)統(tǒng)計(jì)，互聯(lián)網(wǎng)上95%的數(shù)據(jù)流和90%的報(bào)文數(shù)使用的是TCP/IP協(xié)議，因此，嵌入式TCP/IP協(xié)議棧的擁塞控制機(jī)制對(duì)控制網(wǎng)絡(luò)擁塞更具有特別重要的意義。

2 嵌入式TCP/IP協(xié)議棧概述

TCP/IP協(xié)議是由很多協(xié)議組成的協(xié)議族[1]。嵌入式系統(tǒng)引入互聯(lián)網(wǎng)支持所需的主要協(xié)議為ARP、RARP、IP、ICMP和TCP協(xié)議。ARP和RARP協(xié)議提供網(wǎng)絡(luò)地址的解析；ICMP協(xié)議提供網(wǎng)絡(luò)診斷功能；TCP和IP協(xié)議提供網(wǎng)絡(luò)傳輸和網(wǎng)絡(luò)互聯(lián)[1-2]。在網(wǎng)絡(luò)接口層，系統(tǒng)需實(shí)現(xiàn)ARP應(yīng)答協(xié)議，該協(xié)議用于將IP地址映射成以太網(wǎng)MAC地址；在網(wǎng)際層，需要實(shí)現(xiàn)IP協(xié)議，主要負(fù)責(zé)IP報(bào)文報(bào)頭的正確性，并且對(duì)TCP和ICMP報(bào)文實(shí)行分流，此外，為了能夠測(cè)試系統(tǒng)與網(wǎng)絡(luò)的連接，在網(wǎng)際層還需要實(shí)現(xiàn)ICMP協(xié)議中的Ping應(yīng)答協(xié)議，主要用于檢查網(wǎng)絡(luò)在傳輸層是否連通。

2.1 TCP/IP協(xié)議棧處理流程

TCP/IP協(xié)議棧接收數(shù)據(jù)包的過(guò)程就是解析數(shù)據(jù)包的過(guò)程。首先當(dāng)一個(gè)數(shù)據(jù)幀到達(dá)時(shí)，網(wǎng)絡(luò)接口控制程序?qū)⑵渥x入緩沖區(qū)，檢查協(xié)議類(lèi)型字段，如果值依次為0X0800，表示數(shù)據(jù)域內(nèi)為IP包；如果值依次為0X0806，表示數(shù)據(jù)域內(nèi)為ARP包[3]。由此以確定使用那種協(xié)議模塊來(lái)處理此分組。去掉以太網(wǎng)幀首部的數(shù)據(jù)包將被分配到IP緩存或者ARP緩存。接著，由IP協(xié)議處理模塊或ARP協(xié)議處理模塊繼續(xù)解析。在IP協(xié)議模塊處理數(shù)據(jù)包的過(guò)程，它要通過(guò)調(diào)用ARP協(xié)議獲得對(duì)方主機(jī)的物理地址。

2.2 嵌入式TCP/IP協(xié)議棧的特點(diǎn)

嵌入式系統(tǒng)一般都是為了滿(mǎn)足某一特定的需求，對(duì)網(wǎng)絡(luò)支持的要求相對(duì)比較低，不需使用完整的TCP/IP協(xié)議。嵌入式TCP/IP協(xié)議棧的特點(diǎn)如下：

1) 開(kāi)放的協(xié)議標(biāo)準(zhǔn)，獨(dú)立于特定的計(jì)算機(jī)硬件、操作系統(tǒng)和網(wǎng)絡(luò)硬件，可以運(yùn)行在局域網(wǎng)，廣域網(wǎng)和互聯(lián)網(wǎng)中。

2) 統(tǒng)一的網(wǎng)絡(luò)地址分配方案，使得整個(gè)TCP/IP設(shè)備在網(wǎng)中都具有唯一的地址；標(biāo)準(zhǔn)化的高層協(xié)議，可以提供多種可靠的用戶(hù)服務(wù)。

3) 代碼比較簡(jiǎn)潔，占用的存儲(chǔ)空間盡可能小，盡可能為應(yīng)用程序節(jié)省系統(tǒng)資源。

4) 便于裁剪和擴(kuò)展，對(duì)于面向不同應(yīng)用的嵌入式系統(tǒng)應(yīng)當(dāng)根據(jù)特點(diǎn)對(duì)協(xié)議進(jìn)行簡(jiǎn)化或擴(kuò)展。

TCP/IP協(xié)議棧具有層次特性，各個(gè)協(xié)議都有自己的數(shù)據(jù)格式，每次發(fā)送數(shù)據(jù)都要進(jìn)行上下層協(xié)議的數(shù)據(jù)交換，進(jìn)行打包和拆包的過(guò)程。在嵌入式系統(tǒng)中，往往無(wú)法建立數(shù)據(jù)傳遞的緩沖區(qū)，需要采用“零拷貝”技術(shù)來(lái)解決各層協(xié)議間的數(shù)據(jù)傳遞，以提高系統(tǒng)的實(shí)時(shí)性能。網(wǎng)絡(luò)協(xié)議層次模型如圖1所示。

3 擁塞控制概述

描述擁塞現(xiàn)象有許多不同的度量，如傳輸延時(shí)、數(shù)據(jù)吞吐量、隊(duì)列長(zhǎng)度和網(wǎng)絡(luò)效率等，但是沒(méi)有哪個(gè)度量能在局部和全局意義上完全滿(mǎn)足擁塞評(píng)判要求，因此人們對(duì)擁塞控制并無(wú)嚴(yán)格定義，甚至對(duì)擁塞的定義都無(wú)法完全統(tǒng)一。

3.1 基本概念

定義1：若因?yàn)榫W(wǎng)絡(luò)負(fù)載增加而導(dǎo)致用戶(hù)的滿(mǎn)意度降低，用戶(hù)則認(rèn)為網(wǎng)絡(luò)發(fā)生擁塞。

形象地說(shuō)，當(dāng)網(wǎng)絡(luò)中存在過(guò)多的報(bào)文時(shí)，網(wǎng)絡(luò)的性能會(huì)下降，這種現(xiàn)象稱(chēng)為擁塞[4，5]。擁塞導(dǎo)致的直接結(jié)果是分組丟失率提高，端到端時(shí)延加大，甚至整個(gè)系統(tǒng)發(fā)生崩潰。當(dāng)發(fā)生擁塞崩潰時(shí)，微小的負(fù)載增量將使網(wǎng)絡(luò)的有效吞吐量急劇下降（如圖2所示）。

定義2：當(dāng)負(fù)載達(dá)到網(wǎng)絡(luò)容量時(shí)，吞吐量開(kāi)始緩慢增長(zhǎng)，而響應(yīng)時(shí)間急劇增加，這一點(diǎn)稱(chēng)為膝點(diǎn)(Knee)。

定義3：如果負(fù)載繼續(xù)增加，路由器開(kāi)始丟包，當(dāng)負(fù)載超過(guò)一定量時(shí)，吞吐量開(kāi)始急劇下降，這一點(diǎn)稱(chēng)為崖點(diǎn)(Cliff)。

定義4：擁塞控制就是采用某種策略或機(jī)制，保持網(wǎng)絡(luò)工作在正常的狀態(tài)下，也就是使網(wǎng)絡(luò)經(jīng)常工作在崖點(diǎn)左側(cè)的區(qū)域內(nèi)。從而避免擁塞的發(fā)生或者對(duì)擁塞的發(fā)生做出反應(yīng)。擁塞控制的目標(biāo)就是使網(wǎng)絡(luò)在Knee附近工作。

3.2 產(chǎn)生擁塞的原因

網(wǎng)絡(luò)擁塞是“盡力而為”服務(wù)模型的一個(gè)固有屬性。用戶(hù)間無(wú)法相互協(xié)作共享資源，多個(gè)用戶(hù)對(duì)同一網(wǎng)絡(luò)資源提出請(qǐng)求時(shí)，就可能發(fā)生擁塞。網(wǎng)絡(luò)擁塞產(chǎn)生的原因有很多，直接原因主要有三個(gè)方面：1) 存儲(chǔ)空間不足；2) 帶寬容量不足；3) 處理器間處理能力和速度不一致。

3.3 擁塞控制算法的設(shè)計(jì)目標(biāo)

由于擁塞控制算法性能的好壞會(huì)影響整個(gè)網(wǎng)絡(luò)系統(tǒng)，因此在設(shè)計(jì)和評(píng)價(jià)算法時(shí)，應(yīng)該站在整個(gè)系統(tǒng)的角度來(lái)考查。對(duì)于任何一種擁塞避免或控制方案，人們希望它能同時(shí)滿(mǎn)足以下幾點(diǎn)要求：高效性、公平性(魯棒性)、穩(wěn)定性、可擴(kuò)展性。

4 TCP擁塞控制機(jī)制

TCP協(xié)議[6]是目前Internet上使用最廣泛的一種傳輸層協(xié)議。TCP的主要目的是為了解決Internet的穩(wěn)定性、異質(zhì)性(接受端緩沖區(qū)大小，網(wǎng)絡(luò)帶寬及延遲等)、各流之間享用帶寬的公平性，使用效率及擁塞控制等問(wèn)題，從而為Internet提供可靠健壯的端到端通訊。TCP擁塞控制策略主要包括以下四個(gè)過(guò)程：

1) 慢啟動(dòng)階段[7]：保證了連接建立初期進(jìn)入網(wǎng)絡(luò)的突發(fā)數(shù)據(jù)的流量不會(huì)過(guò)大。

2) 擁塞避免階段：當(dāng)數(shù)據(jù)發(fā)送速率超過(guò)一定閾值時(shí)，算法進(jìn)入此階段，而后發(fā)送速率緩慢線(xiàn)性增長(zhǎng)，避免了網(wǎng)絡(luò)擁塞的發(fā)生。

3) 快速重傳階段[9]：當(dāng)網(wǎng)絡(luò)發(fā)生擁塞造成數(shù)據(jù)丟失或者重傳超時(shí)時(shí)，用該策略重傳丟失的分組。

4) 快速恢復(fù)階段：把網(wǎng)絡(luò)從擁塞狀態(tài)中恢復(fù)出來(lái)。

4.1 TCP擁塞控制的主要參數(shù)

1) 擁塞窗口(cwnd)：描述源端在擁塞控制情況下一次最多能發(fā)送的數(shù)據(jù)包數(shù)量。

2) 慢啟動(dòng)閾值(ssthresh)：擁塞控制中慢啟動(dòng)階段和擁塞避免階段的分界點(diǎn)。初始值設(shè)為65535bytes或awnd的大小。

3) 回路響應(yīng)時(shí)間(RTT)：一個(gè)TCP數(shù)據(jù)包從源端發(fā)送到接收端、源端收到接受端確認(rèn)的時(shí)間間隔。

4) 超時(shí)重傳計(jì)數(shù)器(RTO)：描述數(shù)據(jù)包從發(fā)送到失效的時(shí)間間隔，是判斷數(shù)據(jù)包丟失與否、網(wǎng)絡(luò)是否擁塞的重要參數(shù)。通常設(shè)為2RTT和5RTT。

4.2 TCP擁塞控制算法

4.2.1 Reno算法

1990年Jacobson在Tahoe的基礎(chǔ)上提出了Reno算法。Tahoe算法是最早被提出來(lái)的TCP源算法，但至今仍然被大多數(shù)TCP實(shí)現(xiàn)所采用。Reno算法對(duì)Tahoe的改進(jìn)主要體現(xiàn)在兩個(gè)方面。第一，收到連續(xù)三個(gè)dupACK，算法不經(jīng)過(guò)慢啟動(dòng)，而直接進(jìn)入擁塞避免階段。第二，增加了快速重傳/快速恢復(fù)(FR/FR)機(jī)制，具體過(guò)程為：

1) 收到三個(gè)dupACK進(jìn)入FR/FR。ssthresh=max(cwnd/2，2)；

2) 重發(fā)去失的數(shù)據(jù)包；

3) 窗口膨脹。cwnd=ssthresh+ndupndup為收到的重復(fù)ACK數(shù)；

4) 當(dāng)min(awnd，cwnd)足夠大時(shí)，發(fā)送新的數(shù)據(jù)包；

5) 當(dāng)收到非重復(fù)的ACK時(shí)，cwnd=ssthresh；

6) 轉(zhuǎn)入擁塞避免階段。可見(jiàn)，Reno在收到三個(gè)dupACK后，就轉(zhuǎn)入FR/FR，而遇到超時(shí)，Reno和Tahoe一樣進(jìn)入慢啟動(dòng)階段。可從Reno狀態(tài)轉(zhuǎn)換圖直觀地看到Reno的整個(gè)數(shù)據(jù)傳輸過(guò)程(如圖3所示)。

Reno目前被廣泛采用，以其算法的簡(jiǎn)單、有效和魯棒性成為T(mén)CP源算法的主流。

4.2.2 NewReno算法

NewReno算法對(duì)Reno算法的改進(jìn)是通過(guò)盡量避免Reno在快速恢復(fù)階段的許多重傳超時(shí)，利用一個(gè)ACK來(lái)確定部分發(fā)送窗口，立即重傳余下的數(shù)據(jù)包，從而提高網(wǎng)絡(luò)性能。目前，在因特網(wǎng)中使用最廣泛的是NewReno算法。然而NewReno算法也存在著不足，它在高速遠(yuǎn)距離網(wǎng)絡(luò)中不能有效利用帶寬。

4.2.3 Sack算法

Sack算法也是對(duì)Reno算法的改進(jìn)，當(dāng)檢測(cè)到擁塞后，不用重傳數(shù)據(jù)包丟失到檢測(cè)到丟失時(shí)發(fā)送的全部數(shù)據(jù)包，而是對(duì)這些數(shù)據(jù)包進(jìn)行有選擇的確認(rèn)和重傳，從而避免不必要的重傳，減少時(shí)延，提高網(wǎng)絡(luò)吞吐量。由于使用選擇重傳，所以在一個(gè)窗口中數(shù)據(jù)包多包丟失的情況下，Sack算法優(yōu)于NewReno算法。但是Sack算法的主要缺點(diǎn)是要修改接收端TCP。

5 IP擁塞控制機(jī)制

隨著Internet業(yè)務(wù)的迅猛發(fā)展，僅依靠單一的端到端的擁塞控制機(jī)制不可能有效地解決擁塞問(wèn)題，另外期望所有用戶(hù)在Internet應(yīng)用中都遵守這種端到端的擁塞控制也是不現(xiàn)實(shí)的，這要求網(wǎng)絡(luò)本身也必須參與對(duì)資源的管理與控制。基于此，提出了IP擁塞控制機(jī)制。

5.1 IP擁塞控制算法

5.1.1 隨機(jī)及早檢測(cè)(RED)算法

RED(Random Early Detective)算法在路由器監(jiān)控隊(duì)列長(zhǎng)度，一旦發(fā)現(xiàn)擁塞迫近，就通知源端調(diào)整擁塞窗口。它也是通過(guò)丟包的方式使源端發(fā)現(xiàn)超時(shí)或重復(fù)應(yīng)答，隱式通知源端擁塞情況。RED算法包含兩部分：如何監(jiān)控隊(duì)列長(zhǎng)度和何時(shí)丟棄數(shù)據(jù)包。首先，RED使用類(lèi)似TCP計(jì)算超時(shí)時(shí)使用的權(quán)值Weight來(lái)計(jì)算平均排隊(duì)長(zhǎng)度：Qe=(1-Weight)×Qe+Weight×SampleQe其中，0

5.1.2 顯示擁塞指示(ECN)算法

ECN(Explicit Congestion notification)算法在源端數(shù)據(jù)包中嵌入ECN，由路由器根據(jù)網(wǎng)絡(luò)情況設(shè)置CE(Congestion Experienced)比特位，源端從網(wǎng)絡(luò)中接收反饋回來(lái)的已被CE置位的數(shù)據(jù)包，再將隨后發(fā)出的數(shù)據(jù)包標(biāo)記為“可丟棄”的數(shù)據(jù)包。改進(jìn)算法NewECN可通過(guò)調(diào)整擁塞窗口cwnd大小，糾正了有長(zhǎng)時(shí)間RTT的TCP連接的偏差，改進(jìn)了共享瓶頸處帶寬的公平性。

5.1.3 加權(quán)公平排隊(duì)(WFQ)算法

WFQ(Weight Fair Queue)是公平排隊(duì)(FQ)算法的改進(jìn)算法。WFQ算法對(duì)每個(gè)流即每個(gè)排隊(duì)分配一個(gè)權(quán)值。這個(gè)權(quán)值決定了路由器每次轉(zhuǎn)發(fā)該隊(duì)列的比特?cái)?shù)量，從而控制數(shù)據(jù)流得到的帶寬。將所有權(quán)值看成1，那么FQ也是一種特殊的WFQ。權(quán)值的分配往往對(duì)應(yīng)不同優(yōu)先級(jí)的數(shù)據(jù)流，例如用IP包頭中TOS域指定流的優(yōu)先級(jí)，排隊(duì)時(shí)再按優(yōu)先級(jí)分配權(quán)值。總之，WFQ根據(jù)不同數(shù)據(jù)流應(yīng)用的不同帶寬要求，對(duì)每個(gè)排隊(duì)隊(duì)列采用加權(quán)方法分配緩存資源，從而增加了FQ對(duì)不同應(yīng)用的適應(yīng)性。

6 結(jié)論

討論了嵌入式TCP/IP擁塞控制領(lǐng)域的研究熱點(diǎn)。近年來(lái)，非線(xiàn)性規(guī)劃和系統(tǒng)控制理論被引入擁塞控制研究中來(lái)，一些研究者使用數(shù)學(xué)模型來(lái)描述端系統(tǒng)和網(wǎng)關(guān)組成的系統(tǒng)，這對(duì)擁塞控制研究有很大的推動(dòng)作用。然而，對(duì)于Internet這樣一個(gè)復(fù)雜系統(tǒng)的分析與控制，只有通過(guò)通信、控制和數(shù)學(xué)等多學(xué)科的共同努力，才有望獲得突破性成果。

參考文獻(xiàn)：

[1] W.Richard STEVEN. TCP/IP詳解 卷1：協(xié)議[M].范建華，胥光輝，張輝，等譯.北京：機(jī)械工業(yè)出版社，2000：170-269.

[2] Jon C.SNADER. 高級(jí)TCP/IP編程[M]. 劉江林譯.北京：中國(guó)電力出版社，2001:251-286

[3] Adam DUNKELS.Design and Implementation of the TCP/IP Stack[M]. Swedish:Institude of Computer Science，2001.

[4] Gevros P， Crowcroft J， Kirstein P， etal.Congestion control mechanisms and the best effort service model[J].IEEE Network，2001，15(3):16-26.

[5] Steves W.TCP Slows Start， Congestion Avoidance， Fast Retransmit and Fast Recovery Algorithms.RFC，2001[S]， 1997.

[6] 陳崗，張會(huì)生.基于IPv6的移動(dòng)互聯(lián)網(wǎng)絡(luò)研究與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2006，23(2):40-42

[7] 張明龍，趙巍，馮博琴，等.主動(dòng)網(wǎng)絡(luò)中的分層組播擁塞控制策略[J].微電子學(xué)與計(jì)算機(jī)，2005，22(11):3-5.

[8] Hsiao A Hsufeng， Hwang Jenqneng. A max-min fairness congestion control for layered streaming of scalable video[J]. IEEE transactions on circuits systems for video technology，2006，16(9):1074-1085.