摘 要：隨著網(wǎng)絡(luò)技術(shù)的不斷提高，一些新型的高速網(wǎng)絡(luò)投入使用，產(chǎn)生了一系列如TCP擁塞控制算法，其中Reno協(xié)議、Vegas協(xié)議、RED協(xié)議以不同的方式解決了網(wǎng)絡(luò)擁塞的問題。通過在以上3種協(xié)議模型下對F、G函數(shù)進(jìn)行推導(dǎo)，用對偶方程求解的方法，比較3種協(xié)議的優(yōu)劣，為網(wǎng)絡(luò)模型的建立打下基礎(chǔ)。

關(guān)鍵詞：Reno；Vegas；RED；F、G函數(shù)；網(wǎng)絡(luò)模型

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1004373X(2008)1811303

Research of F/G Function under Several TCP Protocols

WANG Lin，YANG Liu

(Guilin University of Technology，Guilin，541004，China)

Abstract：With the improvement of network technology，a lot of newtype fast networks are realized，and series of TCP congestion algorithms are found.The Reno protocol，Vegas protocol and RED protocol can all solute the problem of network congestion.This paper focuses on those three algorithms，argues the F，G functions under the protocol model，compares the advantages through those three protocols using the method of duality equation，and makes the groundwork for establishing the network model.

Keywords：Reno;Vegas;RED;F/G function;network model

1 引 言

Internet的普及為現(xiàn)代生活注入了活力，信息被更迅速、更有效的傳播成為當(dāng)今時代的主題。然而，隨著個人用戶的增多，隨機(jī)的接入與實(shí)時的傳輸變得更加分散、更加無序。而網(wǎng)絡(luò)帶寬擴(kuò)充相對落后，其常成為網(wǎng)絡(luò)發(fā)展的“瓶頸”，信息“高速路”上時有“堵車”現(xiàn)象，嚴(yán)重影響著信息的有效傳遞。

TCP/IP協(xié)議是現(xiàn)行Internet上運(yùn)行的主干協(xié)議，其關(guān)鍵在于TCP/IP能夠適應(yīng)不同的網(wǎng)絡(luò)體系結(jié)構(gòu)和不同的傳輸鏈路，并且為客戶端服務(wù)器模式提供了很好的支持，這已經(jīng)成為網(wǎng)絡(luò)應(yīng)用的標(biāo)準(zhǔn)模式。

2 TCP擁塞模型

TCP/IP協(xié)議的網(wǎng)絡(luò)擁塞問題同樣是計算機(jī)領(lǐng)域一個由來已久的問題，產(chǎn)生擁塞的原因概括來說就是網(wǎng)絡(luò)資源的分析不平衡。做一個簡單的比喻，網(wǎng)絡(luò)中的路由就像是一個技能不甚過關(guān)的發(fā)報員，當(dāng)少量電報到達(dá)時，他總是盡最大努力的發(fā)報，但卻不能保證一定能正確（事實(shí)證明，他時常出錯），出錯的發(fā)報會使用戶白白浪費(fèi)時間去等待，而最后又不得不重新發(fā)報。同時，發(fā)報員的工作間也沒有足夠的空間暫時存放大量的電報，所以當(dāng)他的工作間放滿時，他就將新來的電報丟棄。很顯然，被丟棄的電報比出錯更要不幸。而在計算機(jī)網(wǎng)絡(luò)中，也存在著這樣的一個（其實(shí)是多個）發(fā)報員，這就是路由，正是由于路由的不完美，才使得必須分出一些精力來處理擁塞問題。

理解擁塞問題及擁塞控制問題，應(yīng)與流量控制相區(qū)分。后者是因?yàn)樵诙藢Χ司W(wǎng)絡(luò)中，發(fā)送端的發(fā)送速率與接收端的接收速率不匹配造成的，它是在假設(shè)鏈路可以完好的傳輸數(shù)據(jù)包的基礎(chǔ)上的。而擁塞問題產(chǎn)生的原因，是由于異構(gòu)網(wǎng)絡(luò)的共存。不同協(xié)議下，不同物理線路下的異域網(wǎng)絡(luò)，它們本身的傳輸速率是不相同的，如果不把它們之間相連接，這當(dāng)然是沒有任何問題的，但是Internet的誕生使得越來越多的異構(gòu)網(wǎng)絡(luò)加入進(jìn)來，于是不同速率的數(shù)據(jù)包匯集到路由那里。而當(dāng)路由某一端口的數(shù)據(jù)流太快，而另一輸出端口相對較慢時，就會產(chǎn)生數(shù)據(jù)包的排隊，當(dāng)隊伍長到不得不產(chǎn)生丟包時，網(wǎng)絡(luò)性能就會急速下降，這也就是要討論的擁塞問題。

3 在TCP協(xié)議中的F、G函數(shù)的初步分析

針對擁塞的發(fā)生機(jī)制，不難建立起它的數(shù)學(xué)模型。S.H.Low在2003年提出一種TCP/AQM的對偶模型^［1］。假設(shè)網(wǎng)絡(luò)由L個節(jié)點(diǎn)（或鏈路）組成，每個節(jié)點(diǎn)的容量為Cl(l∈L) ，s 個源組成集合S，每個源使用L中L×S個節(jié)點(diǎn)。定義這個L×S矩陣：Rls=1(L∈LS)

0(LLS)

首先，擁塞是由發(fā)送端發(fā)送過多的數(shù)據(jù)包造成的，由此可以得出影響擁塞的一個因子——發(fā)送終端發(fā)送速率，設(shè)其為xS，則第t時刻發(fā)送速率即為xs(t)。并可以由此列出對偶模型主方程或者源方向：xS(t+1)=F(xS(t)，pl(t))，表示第t+1時刻的發(fā)送速率，是由第t時刻的發(fā)送速率所決定的。

然后，考慮擁塞發(fā)生的癥狀是在路由端出現(xiàn)排隊和丟包現(xiàn)象，于是又找到另一個因子——節(jié)點(diǎn)的擁塞量，設(shè)為pl，則第t時刻擁塞量為pl(t)。顯然，對偶方程（或者鏈路方程）就可列為：pl(t+1)=G(xS(t)，pl(t))。

再因?yàn)樵趯ε寄Ｐ椭?，主方程的結(jié)果會影響到對偶方程，而對偶方程以反饋的形式對主方程起作用，于是兩個方程應(yīng)分別改寫為：xS(t+1)=F(xS(t)，pl(t))

pl(t+1)=G(xS(t)，pl(t)) 4 TCP協(xié)議解決擁塞問題的不同算法下的F、G函數(shù)

此時必須要說明一個很重要的參數(shù)RTT（往返時間），定義為傳輸時間與隊列延時之和，在以下討論中假設(shè)它為常量。對于RTT有^［2］：SourceRate=W/RTT(packets/sec)。

上面公式用記號表示為：xS(t)=wS(t)/RTT其中wS(t)表示t時刻的發(fā)送窗口值。

4.1 Reno協(xié)議

Reno協(xié)議是一條源算法協(xié)議，可以簡單描述為：慢啟動、擁塞避免和FR/FR，如圖1所示。對于趨于平衡的狀態(tài)，只考慮擁塞避免，則可以把慢啟動和FR/FR的環(huán)節(jié)省略。假設(shè)鏈路l的丟包率在t時刻為ql(t)，在ql很小時，可近似地認(rèn)為源發(fā)送數(shù)據(jù)的成功率為qi=ql，于是可知，發(fā)送源在t時刻的單位時間內(nèi)收到xi(t)×(1－qi(t))個確認(rèn)幀。按照AIMD的算法思想^［3］，每收到一個確認(rèn)幀，wi(t)就增加一個1wi(t)，同時，有丟包的存在，每個丟包使wi(t)減小為0.5wi(t)。在這2部分的共同作用下，在t時間內(nèi)，窗口的變化為：xs(t)×(1－qs(t))1wS(t)－xS(t)×qS(t)×

12×4wS(t)3圖1 Reno協(xié)議即：(1-qS (t))RTT-2×qS (t)×x×s2i (t)3于是可得到在Reno算法下F的表達(dá)式：xS (t + 1) = xS (t) + 1 + qS (t)D2S -23qS (t)x2S (t)3其中DS即為往返時間RTT。

因?yàn)镽eno協(xié)議中是用丟包率來評價鏈路，所以用pl(t)表示鏈路l在t時刻的丟包率，當(dāng)pl(t)很小時，qS(t)=1－∏l∈lS(1－pl(t))∑l∈lSpl(t)。

這樣，前面的公式就可變換為：FS (p(t)，x(t)) = xS (t) + 1-p(t)D2S -x2S (t)2p(t)4.2 Vegas協(xié)議

基于TCP 的Vegas協(xié)議相對于Reno有了很多改變，它的主要目的是在超時以前檢測到丟包并且盡快恢復(fù)丟失的數(shù)據(jù)包。Vegas主要修改TCP擁塞避免的算法，算法的關(guān)鍵就是檢測即將發(fā)生的擁塞并設(shè)法避免。

在Vegas協(xié)議中發(fā)送端需要設(shè)定2個門限α和β，通過以下公式計算擁塞窗口：

cwnd(t+t0)=cwnd(t)+1，Diff<αBaseRTT

cwnd(t)，βBaseRTT>Diff>αBaseRTT

cwnd(t)－1，Diff>βBaseRTT

其中Diff表示窗口變化值，為簡單起見，建立模型時使α和β相等，這樣上式就可以不考慮βRTT>Diff>αRTT的情況。則當(dāng)Diff<αRTT時，說明還有多余帶寬，wS(t+1)=wS+1RTT；當(dāng)Diff>αRTT時，說明網(wǎng)絡(luò)負(fù)載太重，ws(t+1)=ws(t)－1RTT；當(dāng)Diff=αRTT時，ws不變化，ws(t+1)=ws(t)。

于是可計算源發(fā)送率xs，即為Vegas協(xié)議下的F公式如下：xs(t+1)=xs(t)+1RTT2(Diff<αRTT)

xs(t+1)=xs(t)－1RTT2(Diff>αRTT)

Vegas協(xié)議的G函數(shù)，存在二元問題，可以用梯形公式來解決，此時認(rèn)為Vegas模型是有間斷點(diǎn)的。設(shè)xs(p(t))表示單一源的發(fā)送速率；又設(shè)xl(p(t)) = ∑s∈S(l) xs(p(t))表示鏈路l上的總發(fā)送速率。則鏈路l可以按以下公式計算pl(t)：pl(t+1)=［pl(t)+υθl(xl(p(t))－Cl］這里υ和θl為大于0的常數(shù)；而xl(p(t))表示t時刻鏈路上的流量；Cl表示鏈路l的最大容量。于是就得到了Vegas算法中的G。

值得指出的是，在Vegas算法中，評價鏈路擁塞狀態(tài)的pl已不再是像Reno算法中使用的丟包率，而是使用路由端的隊列延遲。

4.3 RED協(xié)議

RED協(xié)議又稱隨機(jī)檢測協(xié)議，描述的是一條鏈路算法，它根據(jù)衡量路由隊列的長度，來評價擁塞情況。它的做法是，隨著鏈路負(fù)載加重，當(dāng)路由隊列達(dá)到一定長度時，對隊列中的數(shù)據(jù)包進(jìn)行隨機(jī)標(biāo)注或者隨機(jī)丟包，以提醒源減小發(fā)送速率，而當(dāng)負(fù)載進(jìn)一步增加超過量大隊列容量的時候，就施行全標(biāo)注或者隊尾丟包（DropTail）。用曲線來表示RED算法的標(biāo)注情況如圖2所示。RED根據(jù)以下算法不斷更新2個內(nèi)部變量：t時刻隊列長度bl(t)與平均隊列長度rl(t)：bl(t+1)=bl(t)+yl(t)－Cl

rl(t+1)=(1－al)rl(t)+albl(t) 其中al∈(0，1)。

RED協(xié)議以概率pl(t)隨機(jī)丟包或者標(biāo)注。pl(t)定義為：pl(t)=0，rl(t)≤bl

ρ1(rl(t)bl)，bl≤rl(t)≤bl

ρ2(rl(t)－bl)+ml，bl≤rl(t)≤2bl

1，rl(t)≥2bl

這里，ρ1=mlbl－bl，ρ2=1－mlbl，這個函數(shù)稱為RED的ρ線性概率函數(shù)。于是，對于下一時間的平均隊列長度：pl(t+1)=pl(t)+xl(t)－Cl

其中xl(t)表示鏈路流量，Cl表示鏈路容量。

圖2 RED算法的標(biāo)注情況5 結(jié) 語

通過將線性動力學(xué)中的二元化理論，應(yīng)用到網(wǎng)絡(luò)擁塞過程的研究當(dāng)中，為網(wǎng)絡(luò)擁塞問題建立起一個較為完整的二元動力學(xué)模型，從而描述擁塞問題，完成擁塞避免。研究當(dāng)中，通過對線性問題的描述，并在3種協(xié)議下推導(dǎo)F、G函數(shù)，得出了基于3種不同網(wǎng)絡(luò)協(xié)議的避免擁塞的鏈路公式中參數(shù)的求解辦法，為完整的Internet網(wǎng)絡(luò)模型的建立打下基礎(chǔ)。

參 考 文 獻(xiàn)

［1］Low S H.A Duality Model of TCP and Queue Management Algorithms\\.IEEE/ACM Transactions on Networking，2003，11(4):525536.

［2］Steven Low.CS EE，Caltech.Equilibrium Dynamics of TCP/AQMcalt Sigcomm，2001.

［3］Steven Low，Larry Peterson，Wang Limin.Understanding TCP Vegas:A Duality Model，2001.

［4］李振，李紅濱，張冰.因特網(wǎng)擁塞控制機(jī)制的研究\\.西安：西安電子科技大學(xué)，2003.

［5］廖敬萍.TCP擁塞控制機(jī)制及性能分析\\.現(xiàn)代電子技術(shù)，2006，29(18):8688.

［6］曹書生.網(wǎng)絡(luò)業(yè)務(wù)流的自相似性\\.現(xiàn)代電子技術(shù)，2007，30（16）:152154.

作者簡介 王 林 女，1959年出生，河北，桂林工學(xué)院，助理實(shí)驗(yàn)師。研究方向?yàn)橛嬎銠C(jī)網(wǎng)絡(luò)。

楊 柳 男，1983年出生，河北石家莊，碩士研究生。研究方向?yàn)橛嬎銠C(jī)網(wǎng)絡(luò)、擁塞控制。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文