基于排隊系統的最佳擁塞控制比例研究

摘 要： 對控制報文和網絡擁塞間的平衡問題進行研究。通過一個單服務隊列模型來描述擁塞控制策略，利用排隊系統中的馬爾可夫過程，提出一種兩閾值的流量控制算法使其控制報文速率能滿足最好的擁塞概率。通過分析發現排隊系統中擁塞概率隨緩沖區大小變化發生指數衰變，并定義該衰變指數為大偏差指數用來描述控制報文與擁塞概率間的比例。最后通過帶寬共享模型，模擬并分析不同帶寬情況下控制報文與擁塞概率間的最佳比例及其大偏差指數。

關鍵詞： 控制報文和網絡擁塞間的平衡； 兩閾值流量控制算法； 擁塞控制； 馬爾可夫過程； 排隊系統

中圖分類號： TN911?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2016）12?0014?04

Abstract： 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 process to make the control message rate satisfy the optimal congestion probability. It is found by analysis that the congestion probability 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 analyzed with bandwidth sharing model.

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

擁塞控制是排隊系統的一個重要組成部分，緩解網絡擁塞的基本方式有兩種[1]：流量控制和資源分配。其中流量控制是根據隊列的擁擠程度控制進入隊列報文的速率，而資源分配是為擁堵的隊列提供更多的服務[2]。在傳輸控制協議（TCP）網絡中，緩沖區即將溢出時會丟棄數據包，這會導致窗口的大小和報文到達速率的減小[3]。像隨機早期檢測（RED）這樣的主動隊列管理算法即是通過在緩沖區達到溢出限制之前隨機丟棄一些報文來主動避免擁堵[4?5]。

如果流量控制器能獲得系統中非常準確的擁塞信息，那么即可通過調整輸入速率實現非常有效的擁塞控制。然而獲得準確的隊列長度需要傳送大量的控制信息，此外在TCP這樣的系統機制下也經常會發生意外的報文丟棄 [6?7]。

1 系統模型

1.1 系統說明

首先假設一個用于描述擁塞控制的簡單隊列模型。圖1是具有恒定服務速率β的單服務器隊列，觀察隊列的變化并發送控制報文給流量控制器從而改變輸入速率S（t）。為了簡化分析，假設任意時刻的輸入速率是兩個泊松分布中的一個，即S（t）∈{α1， α2}，其中α2<α1，α2<β。

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

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

2 兩閾值流控策略

兩閾值流控策略的輸入速率在兩個不同的閾值m和n間切換，其中n≥m+1，而m是通過最小吞吐量確定的。初始情況下，當隊列長度小于n時以輸入速率α1運行，當隊列長度超過n后，切換到較低輸入速率α2，直到隊列長度重新小于m后，輸入速率又切換為α1。

假設Q（t）表示時間t的隊列長度，且輸入速率S（t）∈{α1，α2}。定義Y（t）=（Q（t），S（t））表示時間t的系統狀態，顯而易見在兩閾值流控策略中，Y（t）是一個連續時間的馬爾可夫過程[9?10]，如圖2所示。

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

2.1 擁塞概率和輸入速率

定義1 擁塞概率被定義為隊列長度超過M的穩態概率，即[limt→∞P{Q（t）≥M}]，用P{Q≥M}表示。當閾值m固定，差值k增加時，擁塞概率會增大而輸入速率會減小。事實上，可以通過求解圖2中的穩態概率來描述兩閾值流控策略中的擁塞概率。

在此定義[ρ2=α2β]，[ρ1=α1β]，且[η2=1ρ1]，則ρ2<1，ρ1>ρ2 。用pj表示圖中的穩態概率，當j≤m或j≥n時，用[p（1）m+i（p（2）m+i）]表示狀態m+i（1）（m+i（2））的穩態概率，其中i=1，2，…，k-1，通過求解不同的穩態概率pm，發現：

pi=pmη1m-i， 0≤i≤m

[p（1）n-j=1-ηj11-ηk1pm， η1≠1jkpm， η1=1， j=1，2，…，k-1p（2）m+j=ρ11-ρj21-ρ2p（1）n-1， j=1，2，…，k-1pj=ρj-n2ρ11-ρk21-ρ2p（1）n-1， j≥n]

未知值pm可以通過概率歸一來確定：[pm=k（1-ρ2η1）η1（1-ηk1）（1-ρ2）-ηm+111-η1-1， η1≠1m+k+12+11-ρ1-1， η1=1] （1）

通過上面導出的穩態概率，可求得擁塞概率：

[P{Q≥M}=j≥Mpj=ρM-n2ρ11-ρk2（1-ρ2）2p1n-1] （2）

狀態從n-1（1）變化到n或從m+1（2）變化到m，則每秒控制報文速率：[R=α1p（1）n-1+βp（2）m+1]。

由對稱鏈，[α1p（1）n-1+βp（2）m+1]，則：

[R=2α1p（1）n-j=2α1（1-η1）1-ηk1pm， η1≠12α1pmk， η1=1] （3）

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

2.2 大偏差指數

在很多排隊系統中，擁塞概率隨緩沖區大小M變化發生指數衰變。當緩沖區變大時，指數項在決定衰變概率的過程中起決定作用。因此只需考慮衰變指數，而忽略緩沖區M對擁塞概率的其他影響，這就是所謂的大偏差指數。對特定的流控策略，定義其擁塞概率衰變的大偏差指數為：

[E=limM-m→∞-1M-mlnP{Q≥M}]

當Q≤m時， M-m越來越大。

命題1：假設k沿M線性變化，則[limM-m→∞k（M）M-m=0]的大偏差指數為：

[E=ln1ρ2] （4）

又由式（2），[ρM-n2（ρM-m-k2）]時，若k（M）=γ（M-m），常數γ> 0，則大偏差指數[E=（1-γ）ln1ρ2]。

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

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

能得到這個結論是由于在較低的輸入速率α2的情況下，兩閾值流控策略和M/M/1隊列的大偏差指數相同，且優于任何流控策略。

2.3 兩閾值流控策略和隨機早期檢測

即便在緩沖區并未溢出的情況下，隨機早期檢測也會隨機丟棄數據報文來防止擁塞。考慮兩個隊列長度閾值m和n，其中n>m。如果隊列長度不超過m，無論什么輸入速率也無報文被丟棄；而隊列長度達到或超過m，則報文總是被丟棄，并且會導致輸入速率降低。如果隊列長度在m和n-1之間，報文以概率q隨機丟棄。而兩閾值流控策略非常類似于上述隨機早期檢測的算法，如圖3所示。

圖3 隨機早期檢測算法對應的馬爾可夫過程

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

可以通過分析圖3中的馬爾可夫鏈得到擁塞概率和擁塞通知間的平衡性，在保證最小吞吐量的條件下一旦確定了閾值m，則輸入速率和擁塞概率間的平衡就由q和n來確定。此外，當隊列長度大于n時輸入速率降低為α2，這也實現了擁塞概率為[ln1ρ2]的最優大偏差指數。事實上，兩閾值流控策略也可用于模擬實際的隊列管理算法，如隨機早期檢測算法。

3 控制信號的帶寬分配優化

雖然控制信號消耗的帶寬不大，但是在無線網絡的情況下，不可能發送任意量的控制信號而不犧牲帶寬。通常需要發送控制信號糾正錯誤，但這樣也會降低可用服務帶寬。因此建立一個模型來描述服務速率和控制信號間的平衡關系，從而確定最好的擁塞概率衰變指數下的最優控制信號帶寬分配。

3.1 帶寬共享模型

假設隊列服務速率與控制報文重傳次數d-1成線性遞減，即：

[β（d）=β（1-d-1Φ）]

式中：β是無冗余控制報文（d=1）時的服務速率；控制信號所占帶寬與報文重傳次數d-1成正比；每個控制報文所占帶寬為[1Φ]，其中，Φ>0，為常量。

定義[f=d-1Φ]或d=Φf+1，β（f）=β[1-f]。由于并不限制控制報文的重傳次數，因此帶寬中用于控制報文的比例f對應的錯誤概率為[δΦf+1]。

3.2 用于控制報文的最優帶寬

給定的系統參數ρ1，ρ2，Φ，以及控制誤差δ∈[0，1），求解使擁塞概率的大偏差指數最大的最優帶寬比f*（δ）。定義：

[ρi（f）=αiβ（f）=ρi1-f， i=1，2] （5）

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

[δ*（f）=ρ2ρ11+ρ1-ρ21-f] （6）

為保持隊列穩定，需要比α2大的輸入速率，因此α2<β[1-f]或f<1-ρ2。接著計算大偏差指數對應的錯誤概率δ及控制帶寬比f。

命題2：對任意δ∈[0，1]，f∈[0，1-ρ2），對應的大偏差指數：

[E（δ，f）=ln1ρ2（f）， δΦf+1≤δ*（f）ln1s（δ，f）， δΦf+1>δ*（f）] （7）

[s（f，δ）=1+ρ1（f）-（ρ1（f）+1）2-4δΦf+1ρ1（f）2]

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

[f*（δ）=argmaxf∈[0，1-ρ2）E（δ，f）] （8）

由于[1Φ]表示每個重復報文所占帶寬，因此Φ決定了用于控制的最優帶寬。Φ有三種不同的情況確定最佳帶寬比例f*（δ），Φ≤Φ1；Φ≥Φ2；Φ1<Φ<Φ2，其中：[Φ1=ρ2-δ*ln（δ*）（1+ρ1-ρ2）， Φ2=1ρ1-1， ρ1>1∞， ρ1≤1] （9）

Φ的值由ρ1和ρ2確定，當ρ1≤1時，Φ≥Φ1不存在，即使Φ任意大仍然會存在Φ1<Φ<Φ2。下述定理給出了三種不同Φ的最佳帶寬比f*（δ）。

定理2 對于給定的ρ1和ρ2，最佳帶寬比[f*（δ）]根據Φ的值分別為：

（1） Φ≤Φ1時， [f*（δ）]=0，δ∈（0，1）。

（2） Φ≥Φ2時，[f*（δ）=0， δ∈[0，δ*]f（δ）， δ∈（δ*，1）]。

其中[f（δ）是]：

[δΦf+1=ρ2ρ1（1+ρ1-ρ21-f）] （10）

的惟一解。

（3） Φ1<Φ<Φ2時，存在δ′和δ″且δ*<δ′<δ″<1使：

[f*（δ）=0， δ∈[0，δ*]f（δ）， δ∈（δ*，δ′）f（δ）， δ∈（δ′，δ″）0， δ∈（δ″，1）]

其中[f（δ）]是由式（10）得到：

[δΦf+1[Φ（1-f）lnδ*+1]=s（f，δ）] （11）

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

3.3 最優解討論

（1） 錯誤概率小于δ*：f*（δ）=0，δ∈[0，δ*]，大偏差指數的最大值為-ln ρ2且任何控制冗余不會產生疊加。

（2） Φ≤Φ1時：擁塞概率的最佳大偏差指數可以通過發送控制報文調整輸入速率來獲得，然而比錯誤概率的增加更糟糕的是增加控制報文會擠占帶寬。

（3） Φ≥Φ2時：當δ>δ*時，由式（10）差錯概率為[δΦf+1]時取得最佳比例f*（δ）。若ρ1=1.2，ρ2=0.3，Φ=10，圖4中實線給出了δ對應的f值；圖5中實線給出了最佳大偏差指數的值[ln1-f（δ）ρ2]。

（4） Φ1<Φ<Φ2時：當δ>δ*時，如圖6所示最佳比例沿曲線增加，當到達特定錯誤概率δ′時的最佳比例開始急劇下降并在錯誤概率為δ″時達到零值，式（11）說明當δ在（δ′，δ″）時取得最佳比例，其對應的最佳大偏差指數如圖7所示。

4 結 論

本文的目的是研究控制速率和擁塞控制策略間的平衡關系，即研究控制報文發送頻率對擁塞控制效果的影響。由于很難在實際網絡中對這種平衡進行研究，因此構建了一個單一服務隊列的簡單的模型來進行分析。研究發現，可以通過一個簡單的帶寬共享模型的控制信號確定最佳錯誤保護量，不同于無誤差的系統，當差錯概率大于臨界值時，該系統帶寬的很大比例會被控制報文占用。同時，必須考慮控制報文消耗的帶寬及其可能對擁塞控制的影響。

參考文獻

[1] 任豐原，林闖，劉衛東.IP網絡中的擁塞控制[J].計算機學報，2003，26（9）：1025?1034.

[2] 任立勇，盧顯良.Internet擁塞控制研究[J].電子科技大學學報，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 constraints [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] 肖蕾，吳捷.大時延對擁塞控制系統性能的影響及補償方法[J].計算機測量與控制，2005，13（12）：1416?1418.

[7] 李曉宇，戴航，張慧翔，等.Internet擁塞控制系統校正控制器的一種新的設計方法[J].計算機測量與控制，2011，19（8）：1919?1921.

[8] 江菊花，孫金生.自適應PD主動隊列管理算法[J].中南大學學報（自然科學版），2013（s2）：188?194.

[9] 賴峻，張廣馳.基于延遲探測機制的網關隊列管理算法[J].系統工程與電子技術，2014（4）：764?768.

[10] 田波，楊宜民，蔡述庭.基于半馬爾科夫決策過程的視頻傳輸擁塞控制算法[J].通信學報，2014，35（8）：154?161.