基于排隊(duì)系統(tǒng)的最佳擁塞控制比例研究

周馳岷，郭　兵，沈　艷，鄧立國(guó)

（1.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都　610065；2.四川廣播電視大學(xué) 信息技術(shù)中心，四川 成都　610073；3.成都信息工程大學(xué) 控制工程學(xué)院，四川 成都　610225；4.沈陽(yáng)師范大學(xué) 教育技術(shù)學(xué)院，遼寧 沈陽(yáng)　110034）

基于排隊(duì)系統(tǒng)的最佳擁塞控制比例研究

周馳岷1，2，郭兵1，沈艷3，鄧立國(guó)4

（1.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065；2.四川廣播電視大學(xué) 信息技術(shù)中心，四川 成都610073；3.成都信息工程大學(xué) 控制工程學(xué)院，四川 成都610225；4.沈陽(yáng)師范大學(xué) 教育技術(shù)學(xué)院，遼寧 沈陽(yáng)110034）

對(duì)控制報(bào)文和網(wǎng)絡(luò)擁塞間的平衡問(wèn)題進(jìn)行研究。通過(guò)一個(gè)單服務(wù)隊(duì)列模型來(lái)描述擁塞控制策略，利用排隊(duì)系統(tǒng)中的馬爾可夫過(guò)程，提出一種兩閾值的流量控制算法使其控制報(bào)文速率能滿足最好的擁塞概率。通過(guò)分析發(fā)現(xiàn)排隊(duì)系統(tǒng)中擁塞概率隨緩沖區(qū)大小變化發(fā)生指數(shù)衰變，并定義該衰變指數(shù)為大偏差指數(shù)用來(lái)描述控制報(bào)文與擁塞概率間的比例。最后通過(guò)帶寬共享模型，模擬并分析不同帶寬情況下控制報(bào)文與擁塞概率間的最佳比例及其大偏差指數(shù)。

控制報(bào)文和網(wǎng)絡(luò)擁塞間的平衡；兩閾值流量控制算法；擁塞控制；馬爾可夫過(guò)程；排隊(duì)系統(tǒng)

擁塞控制是排隊(duì)系統(tǒng)的一個(gè)重要組成部分，緩解網(wǎng)絡(luò)擁塞的基本方式有兩種［1］：流量控制和資源分配。其中流量控制是根據(jù)隊(duì)列的擁擠程度控制進(jìn)入隊(duì)列報(bào)文的速率，而資源分配是為擁堵的隊(duì)列提供更多的服務(wù)［2］。在傳輸控制協(xié)議（TCP）網(wǎng)絡(luò)中，緩沖區(qū)即將溢出時(shí)會(huì)丟棄數(shù)據(jù)包，這會(huì)導(dǎo)致窗口的大小和報(bào)文到達(dá)速率的減?。?］。像隨機(jī)早期檢測(cè)（RED）這樣的主動(dòng)隊(duì)列管理算法即是通過(guò)在緩沖區(qū)達(dá)到溢出限制之前隨機(jī)丟棄一些報(bào)文來(lái)主動(dòng)避免擁堵［4?5］。

如果流量控制器能獲得系統(tǒng)中非常準(zhǔn)確的擁塞信息，那么即可通過(guò)調(diào)整輸入速率實(shí)現(xiàn)非常有效的擁塞控制。然而獲得準(zhǔn)確的隊(duì)列長(zhǎng)度需要傳送大量的控制信息，此外在TCP這樣的系統(tǒng)機(jī)制下也經(jīng)常會(huì)發(fā)生意外的報(bào)文丟棄［6?7］。

1　系統(tǒng)模型

1.1系統(tǒng)說(shuō)明

首先假設(shè)一個(gè)用于描述擁塞控制的簡(jiǎn)單隊(duì)列模型。圖1是具有恒定服務(wù)速率β的單服務(wù)器隊(duì)列，觀察隊(duì)列的變化并發(fā)送控制報(bào)文給流量控制器從而改變輸入速率S（t）。為了簡(jiǎn)化分析，假設(shè)任意時(shí)刻的輸入速率是兩個(gè)泊松分布中的一個(gè)，即S（t）∈｛α1，α2｝，其中α2＜α1，α2＜β。

圖1　單服務(wù)器隊(duì)列

1.2吞吐量、擁塞概率、輸入速率

在擁塞控制策略的設(shè)計(jì)中，吞吐量、擁塞概率、輸入速率是三個(gè)關(guān)鍵參數(shù)，通常希望平衡吞吐量與擁塞概率，既能保證足夠高的吞吐量又能有效地控制擁塞［8］。本文中假設(shè)能夠滿足一個(gè)最小吞吐量，當(dāng)最小吞吐量α2為min（α1，β）時(shí)，則最小吞吐量是通過(guò)提高輸入速率α1并兼顧擁塞概率來(lái)實(shí)現(xiàn)的。首先考慮一個(gè)單閾值流控策略，當(dāng)隊(duì)列長(zhǎng)度小于等于閾值m時(shí)采用較高的輸入速率α1，當(dāng)大于m時(shí)則采用更低的輸入速率，這表明m較大時(shí)吞吐量更大，反之亦然。因此，給定最小吞吐量要求時(shí)，就可以確定對(duì)應(yīng)的閾值，這表明一旦閾值確定，單閾值流控策略能減少擁塞發(fā)生的概率。然而，由于需要頻繁發(fā)送控制信息，該系統(tǒng)可能在m和m+1之間波動(dòng)。因此將單閾值流控策略擴(kuò)展，使其能提供更大的控制靈活性，并保證吞吐量和良好的擁塞控制性能。

2　兩閾值流控策略

兩閾值流控策略的輸入速率在兩個(gè)不同的閾值m 和n間切換，其中n≥m+1，而m是通過(guò)最小吞吐量確定的。初始情況下，當(dāng)隊(duì)列長(zhǎng)度小于n時(shí)以輸入速率α1運(yùn)行，當(dāng)隊(duì)列長(zhǎng)度超過(guò)n后，切換到較低輸入速率α2，直到隊(duì)列長(zhǎng)度重新小于m后，輸入速率又切換為α1。

假設(shè)Q（t）表示時(shí)間t的隊(duì)列長(zhǎng)度，且輸入速率S（t）∈｛α1，α2｝。定義Y（t）=（Q（t），S（t））表示時(shí)間t的系統(tǒng)狀態(tài)，顯而易見(jiàn)在兩閾值流控策略中，Y（t）是一個(gè)連續(xù)時(shí)間的馬爾可夫過(guò)程［9?10］，如圖2所示。

圖2　兩閾值流控策略對(duì)應(yīng)的馬爾可夫過(guò)程Y（t）

定義k=n-m為兩個(gè)隊(duì)列長(zhǎng)度閾值之間的差值，使用m+i（1）和m+i（2）分別表示狀態(tài)（Q（t）=m+i，S（t）=α1）和（Q（t）=m+i，S（t）=α2），i=1，2，…，k-1。對(duì)于長(zhǎng)度小于m或大于n的隊(duì)列，輸入速率只能分別是α1和α2。注意，當(dāng)k=1時(shí)相當(dāng)于單閾值流控策略，當(dāng)k＞1時(shí)兩閾值流控策略的吞吐量不會(huì)比單閾值時(shí)更小，此時(shí)單閾值為m的流控策略同樣能滿足k＞1時(shí)兩閾值流控策略的要求。

2.1擁塞概率和輸入速率

在此定義ρ2=α2β，ρ1=α1β，且η2=1ρ1，則ρ2＜1，ρ1＞ρ2。用pj表示圖中的穩(wěn)態(tài)概率，當(dāng)j≤m或j≥n時(shí)，用表示狀態(tài)m+i（1（）m+i（2））的穩(wěn)態(tài)概率，其中i=1， 2，…，k-1，通過(guò)求解不同的穩(wěn)態(tài)概率pm，發(fā)現(xiàn)：

未知值pm可以通過(guò)概率歸一來(lái)確定：

通過(guò)上面導(dǎo)出的穩(wěn)態(tài)概率，可求得擁塞概率：

狀態(tài)從n-1（1）變化到n或從m+1（2）變化到m，則每秒控制報(bào)文速率：

由式（2）、式（3）可知k決定了擁塞概率和輸入速率之間的平衡性，當(dāng)k較大時(shí)輸入速率較小而概率擁塞較大，反之亦然。在兩閾值流控策略中，m決定了最小吞吐量，而k決定了擁塞概率和輸入速率之間的平衡性。

2.2大偏差指數(shù)

在很多排隊(duì)系統(tǒng)中，擁塞概率隨緩沖區(qū)大小M變化發(fā)生指數(shù)衰變。當(dāng)緩沖區(qū)變大時(shí)，指數(shù)項(xiàng)在決定衰變概率的過(guò)程中起決定作用。因此只需考慮衰變指數(shù)，而忽略緩沖區(qū)M對(duì)擁塞概率的其他影響，這就是所謂的大偏差指數(shù)。對(duì)特定的流控策略，定義其擁塞概率衰變的大偏差指數(shù)為：

當(dāng)Q≤m時(shí)，M-m越來(lái)越大。

由式（3），輸入速率可以任意小，若k（M）趨于無(wú)窮大。則k（M）隨M線性增長(zhǎng)為無(wú)窮大，那么大偏差指數(shù)為常量，即-ln ρ2。當(dāng)k變大時(shí)，擁塞概率增大，然而它僅在緩沖區(qū)內(nèi)線性增長(zhǎng)，因此大偏差指數(shù)保持不變。大家只對(duì)大偏差指數(shù)與擁塞概率的相對(duì)變化感興趣，而不是它的實(shí)際值，定理1確定了兩閾值流控策略具有最優(yōu)大偏差指數(shù)。

定理1兩閾值流控策略在任意輸入速率的所有流控策略中可能具有最好的大偏差指數(shù)。

能得到這個(gè)結(jié)論是由于在較低的輸入速率α2的情況下，兩閾值流控策略和M/M/1隊(duì)列的大偏差指數(shù)相同，且優(yōu)于任何流控策略。

2.3兩閾值流控策略和隨機(jī)早期檢測(cè)

即便在緩沖區(qū)并未溢出的情況下，隨機(jī)早期檢測(cè)也會(huì)隨機(jī)丟棄數(shù)據(jù)報(bào)文來(lái)防止擁塞。考慮兩個(gè)隊(duì)列長(zhǎng)度閾值m和n，其中n＞m。如果隊(duì)列長(zhǎng)度不超過(guò)m，無(wú)論什么輸入速率也無(wú)報(bào)文被丟棄；而隊(duì)列長(zhǎng)度達(dá)到或超過(guò)m，則報(bào)文總是被丟棄，并且會(huì)導(dǎo)致輸入速率降低。如果隊(duì)列長(zhǎng)度在m和n-1之間，報(bào)文以概率q隨機(jī)丟棄。而兩閾值流控策略非常類似于上述隨機(jī)早期檢測(cè)的算法，如圖3所示。

圖3　隨機(jī)早期檢測(cè)算法對(duì)應(yīng)的馬爾可夫過(guò)程

對(duì)于隊(duì)列長(zhǎng)度小于或等于m時(shí)，總是有較高的輸入速率；如果隊(duì)列長(zhǎng)度增大到n且輸入速率是α1，會(huì)觸發(fā)擁塞通知，輸入速率被降到α2；若輸入速率為α1且隊(duì)列長(zhǎng)度在m～n-1之間，則以概率q發(fā)送擁塞通知，并將輸入速率降低到α2。圖3是這種策略對(duì)應(yīng)的馬爾可夫過(guò)程。

可以通過(guò)分析圖3中的馬爾可夫鏈得到擁塞概率和擁塞通知間的平衡性，在保證最小吞吐量的條件下一旦確定了閾值m，則輸入速率和擁塞概率間的平衡就由q和n來(lái)確定。此外，當(dāng)隊(duì)列長(zhǎng)度大于n時(shí)輸入速率降低為α2，這也實(shí)現(xiàn)了擁塞概率為ln（1ρ2）的最優(yōu)大偏差指數(shù)。事實(shí)上，兩閾值流控策略也可用于模擬實(shí)際的隊(duì)列管理算法，如隨機(jī)早期檢測(cè)算法。

3　控制信號(hào)的帶寬分配優(yōu)化

雖然控制信號(hào)消耗的帶寬不大，但是在無(wú)線網(wǎng)絡(luò)的情況下，不可能發(fā)送任意量的控制信號(hào)而不犧牲帶寬。通常需要發(fā)送控制信號(hào)糾正錯(cuò)誤，但這樣也會(huì)降低可用服務(wù)帶寬。因此建立一個(gè)模型來(lái)描述服務(wù)速率和控制信號(hào)間的平衡關(guān)系，從而確定最好的擁塞概率衰變指數(shù)下的最優(yōu)控制信號(hào)帶寬分配。

3.1帶寬共享模型

假設(shè)隊(duì)列服務(wù)速率與控制報(bào)文重傳次數(shù)d-1成線性遞減，即：

式中：β是無(wú)冗余控制報(bào)文（d=1）時(shí)的服務(wù)速率；控制信號(hào)所占帶寬與報(bào)文重傳次數(shù)d-1成正比；每個(gè)控制報(bào)文所占帶寬為1/Φ，其中，Φ＞0，為常量。

3.2用于控制報(bào)文的最優(yōu)帶寬

給定的系統(tǒng)參數(shù)ρ1，ρ2，Φ，以及控制誤差δ∈［0，1），求解使擁塞概率的大偏差指數(shù)最大的最優(yōu)帶寬比f(wàn)（*δ）。定義：

類似β（f）的定義，在此定義：

為保持隊(duì)列穩(wěn)定，需要比α2大的輸入速率，因此α2＜β［1-f］或f＜1-ρ2。接著計(jì)算大偏差指數(shù)對(duì)應(yīng)的錯(cuò)誤概率δ及控制帶寬比f(wàn)。

命題2：對(duì)任意δ∈［0，1］，f∈［0，1-ρ2），對(duì)應(yīng)的大偏差指數(shù)：

定義2對(duì)任意給定的δ∈［0，1），最佳比例f（*δ）是式（7）中的E（δ，f）：

由于1/Φ表示每個(gè)重復(fù)報(bào)文所占帶寬，因此Φ決定了用于控制的最優(yōu)帶寬。Φ有三種不同的情況確定最佳帶寬比例f（*δ），Φ≤Φ1；Φ≥Φ2；Φ1＜Φ＜Φ2，其中：

Φ的值由ρ1和ρ2確定，當(dāng)ρ1≤1時(shí)，Φ≥Φ1不存在，即使Φ任意大仍然會(huì)存在Φ1＜Φ＜Φ2。下述定理給出了三種不同Φ的最佳帶寬比f(wàn)（*δ）。

定理2對(duì)于給定的ρ1和ρ2，最佳帶寬比 f*（δ）根據(jù)Φ的值分別為：

（1）Φ≤Φ1時(shí)，f*（δ）=0，δ∈（0，1）。

（2）Φ≥Φ2時(shí)，

的惟一解。

（3）Φ1＜Φ＜Φ2時(shí)，存在δ′和δ″且δ*＜δ′＜δ″＜1使：

在（0，1-ρ2）中的惟一解。

3.3最優(yōu)解討論

（1）錯(cuò)誤概率小于δ*：f（*δ）=0，δ∈［0，δ*］，大偏差指數(shù)的最大值為-ln ρ2且任何控制冗余不會(huì)產(chǎn)生疊加。

（2）Φ≤Φ1時(shí)：擁塞概率的最佳大偏差指數(shù)可以通過(guò)發(fā)送控制報(bào)文調(diào)整輸入速率來(lái)獲得，然而比錯(cuò)誤概率的增加更糟糕的是增加控制報(bào)文會(huì)擠占帶寬。

（3）Φ≥Φ2時(shí)：當(dāng)δ＞δ*時(shí)，由式（10）差錯(cuò)概率為 δΦf+1時(shí)取得最佳比例f（*δ）。若ρ1=1.2，ρ2=0.3，Φ=10，圖4中實(shí)線給出了δ對(duì)應(yīng)的f值；圖5中實(shí)線給出了最佳大偏差指數(shù)的值

圖4　Φ較大時(shí)的最佳比例

圖5　Φ較大時(shí)的最佳大偏差指數(shù)

（4）Φ1＜Φ＜Φ2時(shí)：當(dāng)δ＞δ*時(shí)，如圖6所示最佳比例沿曲線增加，當(dāng)?shù)竭_(dá)特定錯(cuò)誤概率δ′時(shí)的最佳比例開(kāi)始急劇下降并在錯(cuò)誤概率為δ″時(shí)達(dá)到零值，式（11）說(shuō)明當(dāng)δ在（δ′，δ″）時(shí)取得最佳比例，其對(duì)應(yīng)的最佳大偏差指數(shù)如圖7所示。

圖6　中等大小Φ的最佳比例

圖7　中等大小Φ的最佳大偏差指數(shù)

4　結(jié)論

本文的目的是研究控制速率和擁塞控制策略間的平衡關(guān)系，即研究控制報(bào)文發(fā)送頻率對(duì)擁塞控制效果的影響。由于很難在實(shí)際網(wǎng)絡(luò)中對(duì)這種平衡進(jìn)行研究，因此構(gòu)建了一個(gè)單一服務(wù)隊(duì)列的簡(jiǎn)單的模型來(lái)進(jìn)行分析。研究發(fā)現(xiàn)，可以通過(guò)一個(gè)簡(jiǎn)單的帶寬共享模型的控制信號(hào)確定最佳錯(cuò)誤保護(hù)量，不同于無(wú)誤差的系統(tǒng)，當(dāng)差錯(cuò)概率大于臨界值時(shí)，該系統(tǒng)帶寬的很大比例會(huì)被控制報(bào)文占用。同時(shí)，必須考慮控制報(bào)文消耗的帶寬及其可能對(duì)擁塞控制的影響。

［1］任豐原，林闖，劉衛(wèi)東.IP網(wǎng)絡(luò)中的擁塞控制［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（9）：1025?1034.

［2］任立勇，盧顯良.Internet擁塞控制研究［J］.電子科技大學(xué)學(xué)報(bào)，2002，31（1）：48?52.

［3］XU Changbiao，LONG Keping，YANG Shizhong.Allocating network resources by weight between TCP traffics［J］.Journal of computer science and technology，2003，18（2）：247?251.

［4］LAMA S S，WONGB J W.Queueing network models of packet switching networks part 2：Networks with population size con? straints［J］.Performance evaluation，1982，2（3）：161?180.

［5］TAN Liansheng，PUGHB A C，MIN Yina.Rate?based congestion control in atm switching networks using a recursive digital filter ［J］.Control engineering practice，2003，11（10）：1171?1181.

［6］肖蕾，吳捷.大時(shí)延對(duì)擁塞控制系統(tǒng)性能的影響及補(bǔ)償方法［J］.計(jì)算機(jī)測(cè)量與控制，2005，13（12）：1416?1418.

［7］李曉宇，戴航，張慧翔，等.Internet擁塞控制系統(tǒng)校正控制器的一種新的設(shè)計(jì)方法［J］.計(jì)算機(jī)測(cè)量與控制，2011，19（8）：1919?1921.

［8］江菊花，孫金生.自適應(yīng)PD主動(dòng)隊(duì)列管理算法［J］.中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（s2）：188?194.

［9］賴峻，張廣馳.基于延遲探測(cè)機(jī)制的網(wǎng)關(guān)隊(duì)列管理算法［J］.系統(tǒng)工程與電子技術(shù)，2014（4）：764?768.

［10］田波，楊宜民，蔡述庭.基于半馬爾科夫決策過(guò)程的視頻傳輸擁塞控制算法［J］.通信學(xué)報(bào)，2014，35（8）：154?161.

Research on optimal proportion of congestion control based on queuing system

ZHOU Chimin1，2，GUO Bing2，SHEN Yan3，DENG Liguo4
（1.College of Computer Science，Sichuan University，Chengdu 610065，China；2.Information Technology Center，Sichuan Radio and TV University，Chengdu 610073，China；3.Control Engineering College，Chengdu University of Information Technology，Chengdu 610225，China；4.College of Education Technology，Shenyang Normal University，Shenyang 110034，China）

The balance between control message and network congestion control is studied.The congestion control strategy is described with a single service queue model.A two?threshold flow control algorithm is put forward by utilizing Markov pro?cess to make the control message rate satisfy the optimal congestion probability.It is found by analysis that the congestion proba?bility occurs exponential disintegration with the buffer size，which is defined as the large deviation index to describe the ratio of control message and congestion probability.The ratio and large deviation index in different bandwidth are simulated and ana?lyzed with bandwidth sharing model.

balance between control message and network congestion control；two?threshold flow control algorithm；conges?tion control；Markov process；queuing system

TN911?34；TP393

A

1004?373X（2016）12?0014?04

10.16652/j.issn.1004?373x.2016.12.004

2015?11?13 基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目（61332001）；國(guó)家自然科學(xué)基金項(xiàng)目（61272104）；四川省教育廳科研項(xiàng)目（16ZB0102）；四川電大科研課題重點(diǎn)項(xiàng)目（KTGCJS2016002Z）

周馳岷（1975—），男，四川成都人，講師，碩士。主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)應(yīng)用。郭兵（1970—），男，四川成都人，教授，博士。主要研究方向?yàn)榍度胧綄?shí)時(shí)系統(tǒng)、軟件工程、綠色計(jì)算等。沈艷（1973—），女，四川成都人，教授，博士。主要研究方向?yàn)橛?jì)算機(jī)測(cè)量。鄧立國(guó)（1972—），男，遼寧沈陽(yáng)人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)模式識(shí)別。