幾種ＴＣＰ協議下Ｆ、Ｇ函數的研究

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

關鍵詞：Reno；Vegas；RED；F、G函數；網絡模型

中圖分類號：TP393 文獻標識碼：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的普及為現代生活注入了活力，信息被更迅速、更有效的傳播成為當今時代的主題。然而，隨著個人用戶的增多，隨機的接入與實時的傳輸變得更加分散、更加無序。而網絡帶寬擴充相對落后，其常成為網絡發展的“瓶頸”，信息“高速路”上時有“堵車”現象，嚴重影響著信息的有效傳遞。

TCP/IP協議是現行Internet上運行的主干協議，其關鍵在于TCP/IP能夠適應不同的網絡體系結構和不同的傳輸鏈路，并且為客戶端服務器模式提供了很好的支持，這已經成為網絡應用的標準模式。

2 TCP擁塞模型

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

理解擁塞問題及擁塞控制問題，應與流量控制相區分。后者是因為在端對端網絡中，發送端的發送速率與接收端的接收速率不匹配造成的，它是在假設鏈路可以完好的傳輸數據包的基礎上的。而擁塞問題產生的原因，是由于異構網絡的共存。不同協議下，不同物理線路下的異域網絡，它們本身的傳輸速率是不相同的，如果不把它們之間相連接，這當然是沒有任何問題的，但是Internet的誕生使得越來越多的異構網絡加入進來，于是不同速率的數據包匯集到路由那里。而當路由某一端口的數據流太快，而另一輸出端口相對較慢時，就會產生數據包的排隊，當隊伍長到不得不產生丟包時，網絡性能就會急速下降，這也就是要討論的擁塞問題。

3 在TCP協議中的F、G函數的初步分析

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

0(LLS)

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

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

再因為在對偶模型中，主方程的結果會影響到對偶方程，而對偶方程以反饋的形式對主方程起作用，于是兩個方程應分別改寫為：xS(t+1)=F(xS(t)，pl(t))

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

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

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

4.1 Reno協議

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

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

因為Reno協議中是用丟包率來評價鏈路，所以用pl(t)表示鏈路l在t時刻的丟包率，當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協議

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

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

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

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

cwnd(t)－1，Diff>βBaseRTT

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

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

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

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

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

4.3 RED協議

RED協議又稱隨機檢測協議，描述的是一條鏈路算法，它根據衡量路由隊列的長度，來評價擁塞情況。它的做法是，隨著鏈路負載加重，當路由隊列達到一定長度時，對隊列中的數據包進行隨機標注或者隨機丟包，以提醒源減小發送速率，而當負載進一步增加超過量大隊列容量的時候，就施行全標注或者隊尾丟包（DropTail）。用曲線來表示RED算法的標注情況如圖2所示。RED根據以下算法不斷更新2個內部變量：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協議以概率pl(t)隨機丟包或者標注。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，這個函數稱為RED的ρ線性概率函數。于是，對于下一時間的平均隊列長度：pl(t+1)=pl(t)+xl(t)－Cl

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

圖2 RED算法的標注情況5 結 語

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

參 考 文 獻

［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］李振，李紅濱，張冰.因特網擁塞控制機制的研究\\.西安：西安電子科技大學，2003.

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

［6］曹書生.網絡業務流的自相似性\\.現代電子技術，2007，30（16）:152154.

作者簡介 王 林 女，1959年出生，河北，桂林工學院，助理實驗師。研究方向為計算機網絡。

楊 柳 男，1983年出生，河北石家莊，碩士研究生。研究方向為計算機網絡、擁塞控制。

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