ＡＩＭＤ算法在公平性收斂中的應用分析

（西北工業大學 自動化學院， 西安 710072）



摘要：

系統地分析了AIMD(addictive increase multiplicative decrease)算法在擁塞控制過程的公平性收斂中的應用，包括分布式動態資源分配模型、公平性指標函數、應用于公平性收斂的AIMD算法以及公平性收斂動力學分析等問題。

關鍵詞：擁塞控制； 公平性； 動態資源分配； 加增乘減算法； 公平性收斂； 動力學分析

中圖分類號：TP311文獻標志碼：A

文章編號：10013695(2009)03106303



Analysis of AIMD algorithm to fairness convergence



DAI Hang， MU Dejun， ZHANG Huixiang



(College of Automation， Northwestern Polytechnical University， Xi’an 710072， China)



Abstract:

This paper analyzed the application of AIMD(addictive increase multiplicative decrease) algorithm to the fairness convergence of congestion control process systematically， including the model of distributed dynamical resource management， the fairness index function， AIMD algorithm for the fairness convergence and the dynamical analysis of fairness convergence.

Key words：congestion control; fairness;dynamical resource management; AIMD algorithm;fairness convergence;dynamical analysis



Internet的擁塞控制協議主要有兩種性能指標，即有效性和公平性[1]。對于Internet這樣的開放巨系統，廣大用戶的公平性是非常重要的；再者，Internet的公平性問題是與Internet的QoS保障問題密切相關。因此，近年來對Internet公平性問題的研究日益增多[2~4]。文獻[2]較早地提出了采用AIMD算法處理公平性問題，但僅限于靜態分析，對于更為重要的公平性收斂的動態分析未予涉及。文獻[3]采用MIMD(multiplicative increase multiplicative decrease)算法處理公平性問題。本文系統地分析了AIMD算法在擁塞控制過程的公平性收斂中的應用。

1分布式動態資源分配模型

設有n個用戶共享網絡資源，其第i個用戶的發送窗口尺寸為wi(t)(i=1，2，…，n)。系統n維的狀態向量為W(t)=[w1(t)，w2(t)，…，wn(t)]T。應指出，在基于窗口的描述中，取發送數據包w(t)為狀態變量；而在基于速率的描述中，取發送速率x(t)為狀態變量。實際上，兩者之間的關系為x(t)=Mw(t)/rtt。其中：M為每個數據包的位數(bit)，rtt(round trip time)是往返時間。

圖1是分布式動態資源分配的反饋控制系統的示意圖。設瓶頸鏈路所能提供的總資源量為B，路由器中的數據包計數器檢測各用戶所發送的數據總和y(t)=∑ni=1wi(t)；路由器將y(t)與可被分配的總資源量B相比較，然后給出反映擁塞狀態的反饋信號z(t)。通常，z(t)是二值信號：

z(t)=0y(t)＜B1y(t)≥B(1)

其中：z(t)=0是非擁塞反饋信號；z(t)=1是擁塞反饋信號。z(t)反饋到用戶的端系統，各端系統采用一定的擁塞控制算法fi(g)(i=1，2，…，n)，控制其發送窗口的尺寸，使總的系統達到有效性和公平性的控制目標。

本文采用離散時間模型，各端系統i的擁塞控制算法可用下列差分方程來描述：

wi(t+rtt)=fi(wi(t)，z(t))；i=1，2，…，n(2)

其中：rtt是往返時間。對于二值反饋信號z(t)，算法fi(g)可分解為下列兩個算法：

wi(t+rtt)＝gi(wi(t))y(t)＜Bhi(wi(t))y(t)≥B(3)

其中：gi(g)與hi(g)分別為非擁塞狀態與擁塞狀態的控制算法，i=1，2，…，n。

對于上述分布式動態資源分配的反饋控制系統模型，有下列幾點說明：

a)集中檢測，二值反饋信號。路由器集中檢測各端系統發送的總的數據包∑ni=1wi(t)，并給出二值反饋信號。之所以取二值反饋信號，在于其簡單性。

b)分布式控制。從原理上講，各端系統的擁塞控制算法可以不同，如式(3)；但從工程上講，在某個擁塞控制協議下，各端系統的擁塞控制算法是相同的。

wi(t+rtt)=g(wi(t))y(t)＜Bh(wi(t))y(t)≥B(4)

其中：g(g)與h(g)分別為非擁塞狀態和擁塞狀態的控制算法，i=1，2，…，n。再者，還可以根據QoS策略對不同權限的用戶組選擇幾組不同的算法，或者在相同算法下調節幾組不同的參數。

c)不完全信息。各端系統i僅有局部信息wi(t)以及部分全局信息z(t)，而不掌握大部分的全局信息，如狀態W(t)=[w1(t)，w2(t)，…，wn(t)]T、用戶數n、資源總量B等。各端系統的擁塞控制算法只能根據不完全信息作出反應，因此這是一種分散化決策機制(decentralized decisionmaking)。

d)同步擁塞反饋機制。在圖1中，路由器將擁塞反饋信號z(t)反饋到所有流i(i=1，2，…，n)上，稱之為同步反饋機制，如VCP擁塞控制協議就采用這種機制[5]。另一方面，TCP擁塞控制協議采用異步擁塞反饋機制，即擁塞狀態信號z(t)=1僅反饋到發生marking/dropping的流上。

e)時延問題。實際網絡中，路由器所產生的反饋信號z(t)要經過大約rtt的時延才能傳送到各端系統。對于擁塞控制的有效性收斂問題，主要研究小信號下線性化閉環系統的動力學，此時必須考慮rtt量級的時延的影響；而對于擁塞控制的公平性收斂問題，由于收斂過程的時間尺度遠大于rtt，暫不考慮rtt并不影響收斂動力學的主要特征。

f)同質rtt的情況。為簡化起見，本文假定了各流往返時間rtt大致相同的同質rtt的情況。對于各流rtt有較大差異的異質rtt的情況，可以對擁塞控制算法中的有關參數進行補償[5，6]。同樣，即使異質rrt的情況，也不影響公平性收斂動力學的主要特征。

2公平性指標函數

對于資源分配的公平性問題需要有適當的指標函數，以定量地描述分配的公平性。本文采用maxmin公平性準則[6]。該準則指出，具有相同權限的用戶均勻享有網絡資源。于是，本文選擇公平性指標函數為[7]

F(W)=∑ni=1wi)2/（n∑ni=1w2i）(5)

上述指標函數有下列性質：

a)F(W)是W=[w1，w2，…，wn]T的連續函數。

b)F(W)∈(0，1]。當w1=w2=…=wn，即當資源完全公平分配時，F(W)=1；當全部資源只分配給一個用戶時，F(W)=1/n，且當N→∞時，F（W）→0；當全部資源僅公平分配給k(k＜n)個用戶時，則F(W)=k/n。

c)F(W)與變量wi(t)(i=1，2，…，n)的標度無關，即若βW=[βW1，βW2，…，βWn]T，則F(βW)=F(W)。這里β是常數。

3應用于公平性收斂的AIMD算法

目前正在應用或研發的擁塞控制協議中，在擁塞控制過程的公平性收斂階段廣泛采用AIMD算法。此時，對i=1，2，…，n，式(4)變為

AI: wi(t+rtt)=g(wi(t))=wi(t)+αy(t)＜B(6)

MD: wi(t+δt)=h(wi(t))=βwi(t)y(t)≥B(7)

這是一種簡單的雙模態線性擁塞控制算法。其中：δt→0+，α＞0，0＜β＜1。例如在VCP擁塞控制協議中[5]，α=1(與TCP擁塞控制協議相同)，β=0.875。

圖2表示了一個擁塞周期中基于AIMD算法的wi(t)(i=1，2，…，n)的變化過程。圖中，從tk開始是y(t)＜B的非擁塞狀態，按AI算法（式(6)），wi(t)每隔rtt增加α個數據包；到tk+1瞬間有y(tk+1)=∑ni=1wi(k+1)=B，此時按MD算法（式(7)），各端系統在收到擁塞反饋信號z(tk+1)=1后，立即將wi(t)減少β倍，然后進入下一個擁塞周期。因此可得

wi(k+1)=βwi(k)+α(tk+1-tk)； i=1，2，…，n(8)

其中：時間間隔tk+1-tk是以rtt為度量的。

很明顯，在AIMD算法的各轉換時刻tk(k)，有

y(tk)=∑ni=1wi(k)=B；(9)

將式(8)從i=1，2，…，n相加有

∑ni=1wi(k+1)=β∑ni=1wi(k)+nα(tk+1-tk)

將式(9)代入上式可得

tk+1-tk=[(1-β)B]/nα

再將上式代入式可得

wi(k+1)=βwi(k)+[(1-β)B]/n； i=1，2，…，n(10)

差分方程（式(10)）反映了基于AIMD算法，端系統i的窗口尺寸wi(t)在一個擁塞周期前后的變化關系。

4公平性收斂的動力學分析

由式(5)，在AIMD算法的各轉換時刻tk(k)，有

F(W)(k))=(∑ni=1wi(k))2/（n∑ni=1w2i(k)）；k(11)

其中：F(W(k))∈(0，1]。將式(9)代入式(11)可得

F(W(k))=（B2/n）(∑ni=1w2i(k))-1；k

即F(W(k))=（B2/n）(‖(k)‖2)-1；k(12)

其中：‖W（k）‖是向量W(k)=[w1(k)，w2(k)，…，wn(k)]T的模。

基于AIMD算法的公平性收斂的目標是使公平性指標函數F(W(k))為最大。由式(12)可知，這相當于使向量W(k)的模‖W(k)‖為最小。

圖3表示了二維平面中，基于AIMD算法的向量W=[w1，w2]T在一個擁塞周期中的變化過程。圖中，W的非擁塞域是{(w1，w2)|w1+w2≤B，w1，w2＞0}；直線段w1+w2=B稱為效率線，在該直線段上，用戶獲得資源的最大利用率；直線段w1+w2=βB稱為回退線；直線段w1=w2稱為公平線，在該直線段上，用戶獲得資源的完全公平分配。

由圖3可見，向量OP(W(k))經MD算法，按反方向回退為向量OQ(βW(k))；再經AI算法，沿45°線增加為向量OR（W(k+1)）。很明顯，‖W(k+1)‖＜‖W(k)‖。于是，在AIMD算法的不斷作用下，向量W(k)逐漸收斂到穩態OT(W(∞)=Ws)。這里，Ws=[ws1，ws2]T，而ws1=ws2=B/2。

下面將上述二維結果推廣到任意n維的情況。事實上，由式(10)可得

w2i(k+1)=β2w2i(k)+[2β(1-β)B]/n×wi(k)+[(1-β)2B2]/n2;i=1，2，…，n

上式從i=1，2，…，n相加有

∑ni=1w2i(k+1)=β2∑ni=1w2i(k)+[2β(1-β)B/n]×∑ni=1wi(k)+(1-β)2B2/n

代入式(9)，經整理可得

‖W(k+1)‖2=β2‖W(k)‖2+B2(1-β2)/n

即(‖W(k+1)‖2-B2/n)=β2(‖W(k)‖2-B2/n)(13)

其中：0＜β＜1。

式(13)描述了在AIMD算法作用下，‖W(k)‖2的動力學差分方程。由式(13)可知：

a)由于0＜β＜1，上述差分方程是穩定的，亦即在AIMD算法的不斷作用下，上述資源分配是公平收斂的。

b)每經過一個擁塞周期，向量W(k+1)的模‖W(k+1)‖相對于向量W(k)的模‖W(k)‖而言是在減小，其收斂速度主要取決于β。

c)公平性收斂動力學的穩態為‖W(∞)‖=‖WS‖=B/n，此時達到完全公平分配資源，亦即wi(∞)=wis=B/n(i=1，2，…，n)。相應地，有F(WS)=1。

5結束語

本文系統地分析了AIMD算法在擁塞控制過程的公平性收斂中的作用，歸納起來是：

a)MD算法。由公平性指標函數F（W）的性質(c)（即F（βW）=F(W)）可知，MD算法的回退過程對公平性收斂并無

貢獻。然而，參數β對公平性收斂的速度起著至關重要的作用：β越小，則公平性收斂的周期數越少，從而收斂越快速;另一方面，β越小，則用戶在公平性收斂階段的平均吞吐量亦越小，這不利于有效性的要求。因此，在各種采用AIMD算法的擁塞控制協議中，必須謹慎地選取參數β，以兼顧有效性和公平性的雙重要求。

b)AI算法。公平性的收斂依賴于AI算法。如圖3所示，狀態向量W沿45°線增加的過程才是縮小資源分配差異的公平性收斂過程。在一定rtt下，α越大，W趨于效率線也越快，從而收斂過程也越快。

需要進一步研究的一些問題如下：a)對異步擁塞反饋機制的研究；b)對非線性擁塞控制算法的研究；c)對非二值信號的研究；d)對不同權限用戶組的幾組不同的擁塞控制算法的研究；e)考慮擁塞反饋信號z(t)具有時延rtt的更精確的分析；f)考慮異質rtt情況的更精確的分析。

參考文獻：

[1]LOW S H， PAGANINI F， DOYLE J C. Internet congestion control [J]. IEEE Control Systems Magazine， 2002，32(1):2843.

[2]CHIU D M， JAIN R. Analysis of the increase and decrease algorithms for congestions avoidance in computer networks [J]. Journal of Computer Networks and ISDN Systems， 1989，17(1):114.

[3]ALTMAN E， AVRACHENKOV K E， PRABHU B J. Fairness in MIMD congestion control algorithms[C]//Proc of the 24th Conference on Computer Communications. Piscataway: IEEE Press， 2005:13501361.

[4]HASEGAWA G， MURATA M， MIYAHARA H. Fairness and stability of congestion control mechanisms of TCP [J].Telecommunication Systems， 2000，15(1):167184.

[5]XIA Yong， SUBRAMANIAN L， STOICA I， et al. One more bit is enough[C]//Proc of Conference of the Special Interest Group on Data Communication. New York: ACM Press， 2005:3748.

[6]JAFFE J M. Bottleneck flow control [J]. IEEE Trans on Communication， 1981，29(7): 954962.

[7]JAIN R， CHIU D M， HAWE H. A quantitative measure of fairness and discrimination for resource allocation in shared systems[R]. [S.l.]:Digital Equipment Corporation， 1984.