動態(tài)令牌分配的TCSN多級令牌桶流量監(jiān)管算法

趙晉南,, ,

(西南交通大學 信息科學與技術學院,成都 611756)

0 概述

列車控制與服務網絡(Train Control and Service Network,TCSN)[1]是列車控制業(yè)務與服務業(yè)務一體化傳輸的新型列車通信網絡。針對列車網絡復雜而多樣的業(yè)務特性,TCSN采用區(qū)分服務的模式。DiffServ[2-3]網絡與用戶之間定義了服務等級合約(Service Level Agreement,SLA),內容主要包括控制與服務業(yè)務流的流量特性和傳輸特性。如果用戶的業(yè)務流違反了SLA,則其訂購的服務質量需求將不能得到保證,甚至會遭到拒絕服務。在DiffServ網絡中,流量監(jiān)管是提供QoS保證的一項重要技術,其作用是通過監(jiān)督進入網絡的流量速率來對超出部分的流量進行“懲罰”,從而使進入的流量被限制在一個合理的范圍內。

在TCSN網絡中,關鍵業(yè)務控制列車的正常運行,其必須得到優(yōu)先傳輸。除關鍵業(yè)務外的控制和服務業(yè)務在傳輸時需要一定程度的服務質量保證,同時不能對關鍵業(yè)務的傳輸產生影響。逐跳行為(Per Hop Behavior,PHB)[4-5]規(guī)定在網絡傳輸中采用AF(Assured Forward)轉發(fā)除關鍵業(yè)務外的控制業(yè)務和服務業(yè)務,AF業(yè)務主要包括除關鍵業(yè)務外的控制業(yè)務、音頻流業(yè)務、視頻流業(yè)務、交互類業(yè)務、高保證業(yè)務、一般Web業(yè)務和P2P業(yè)務。在TCSN實際工作中,AF業(yè)務流量的實際到達率與SLA規(guī)定的速率并不相符,其容易對關鍵業(yè)務的傳輸產生影響,因此,必須對AF業(yè)務流量進行監(jiān)管。

傳統(tǒng)的流量監(jiān)管方式[6-7]通過令牌桶[8-10]來實現,但在列車網絡交換機中,令牌桶自身的參數和結構通常是靜態(tài)的,對流量的監(jiān)管也是靜態(tài)的,這容易導致服務等級高的流量越來越大,而服務等級低的流量越來越小,同時,高等級業(yè)務流對應令牌桶的令牌最終會因溢出而丟棄。

TCSN網絡在實際工作中,網絡狀態(tài)是不斷變化的,靜態(tài)的監(jiān)管方案并不合理。為此,本文提出一種TCSN多級令牌桶流量監(jiān)管算法,通過兩級令牌動態(tài)分配來實現AF業(yè)務流量的動態(tài)監(jiān)管,并通過實驗驗證該方法的可行性。

1 多級令牌桶流量監(jiān)管算法

1.1 應用背景

對于TCSN網絡,有時某一業(yè)務流會在乘車高峰期大量突發(fā),造成過多的數據流流入網絡并長期占用網絡帶寬,致使其他業(yè)務得不到及時服務,特別是對一些時延、抖動及丟包敏感的實時數據,會造成較大的負面影響。有一些旅客服務業(yè)務流本身的流量變化較大,如VBR視頻流和P2P業(yè)務流,其峰值速率比平均速率高出數倍,在傳輸過程中更易占用網絡帶寬。用戶規(guī)模和業(yè)務種類的擴大,要求TCSN網絡設備不僅能進一步細化業(yè)務流量,而且還能夠對多個用戶、多種業(yè)務、多種流量等傳輸對象進行統(tǒng)一管理[11]。為支持TCSN多業(yè)務的QoS要求,限制各業(yè)務流對網絡資源的過度占用,需要對網絡資源進行合理劃分,即設計TCSN多級令牌桶流量監(jiān)管算法。

1.2 多級令牌桶流量監(jiān)管方案

多級令牌桶流量監(jiān)管方案是TCSN多級令牌桶流量監(jiān)管算法實現的基本框架,其主要包括令牌桶、一級令牌分配模塊、二級令牌分配模塊、分類著色模塊和入隊管理模塊。當AF業(yè)務流進入隊列時,首先由分類模塊對業(yè)務流進行分類,將AF業(yè)務流歸入不同的服務類,每個AF子隊列對應一個令牌桶,一級令牌分配模塊按SLA定義的令牌添加速率監(jiān)管AF業(yè)務流的傳輸速率。二級令牌分配模塊根據一級令牌分配模塊的結果重新分配富余令牌。AF業(yè)務流經過令牌桶著色后被標記為綠、黃、紅三色流量,入隊管理模塊根據標記結果將AF業(yè)務流歸入下一個優(yōu)先級隊列。TCSN多級令牌桶流量監(jiān)管方案總體結構如圖1所示。

圖1 TCSN流量監(jiān)管方案總體結構

1.3 設計思路與系統(tǒng)實現

在TCSN網絡中,各類AF業(yè)務流具有不同的流量特性和傳輸特性,對應SLA中定義的服務等級也不相同。傳統(tǒng)的單獨令牌桶只能應用于單一服務等級的流量,在TCSN多業(yè)務存在的情況下,需要使用多個令牌桶對AF業(yè)務流進行更精細的流量監(jiān)管[12-16]。在TCSN網絡實際工作中,不同AF業(yè)務的實際流量到達率可能與SLA允許到達的流量不相符,當AF業(yè)務流量違反SLA合約時,需要通過令牌桶限制業(yè)務流的傳輸速率。但隨著網絡負載的不斷增大,應當適當降低SLA允許到達的流量,并調節(jié)令牌添加速率,以避免出現網絡擁塞。AF業(yè)務流的實際流量到達率不同,按照令牌添加速率來添加令牌,會導致各令牌桶的令牌存在富余或欠缺,即某些AF業(yè)務流量速率一直維持在很大或很小的狀態(tài)。為確保令牌分配比例的公平性,需要重新分配隊列的富余令牌。

流量監(jiān)管采用令牌桶技術來控制流量,每傳輸一個報文則令牌桶減少相應數量的令牌。SLA定義了各AF業(yè)務流的流量特性,由此可以計算出各AF子隊列對應令牌桶的令牌添加速率。一級令牌分配模塊按照令牌添加速率為每個令牌桶添加令牌,同時根據網絡負載狀態(tài)調整SLA允許到達的流量。二級令牌分配模塊根據一級令牌分配后各AF子隊列令牌的富余或欠缺情況,重新分配令牌桶的富余令牌。為進一步避免網絡擁塞,針對區(qū)分服務網絡,通過采用TWSTCM算法[17]比對平均流量到達率來標記監(jiān)管后的AF業(yè)務流量。同時對RIO-C算法[18-19]進行改進,標記后的三色流量按轉移概率將AF業(yè)務流歸入下一級AF隊列和BE隊列,而不是直接丟棄業(yè)務報文。

2 兩級令牌分配

傳統(tǒng)的令牌桶機制為每個服務隊列配置一個令牌桶,各業(yè)務流的輸出速率由令牌桶控制,令牌桶自身的參數設置決定了流量的輸出速率和帶寬占有率。但網絡設備中令牌桶自身的參數配置和結構通常是靜態(tài)的,一旦配置完成后一般不會進行較大改動,而TCSN的實際應用情況是動態(tài)變化的,特別是AF業(yè)務流量,其在不同時間段網絡流量的業(yè)務組成可能會有很大差距,有可能出現一些業(yè)務帶寬剩余,而另一些業(yè)務得不到滿足的情況。流量超負荷時會引起網絡擁塞,導致系統(tǒng)帶寬利用率下降[11]。

在令牌桶監(jiān)管的基礎上,本文增加一級令牌分配模塊,其根據系統(tǒng)的信道利用率來估算網絡負載狀態(tài),以此提高或降低當前按SLA允許到達的流量,進而動態(tài)調整令牌桶的令牌添加速率,并將AF業(yè)務流量的輸出速率控制在合理的范圍內。一級令牌分配模塊按照令牌添加速率為令牌桶添加令牌,但流量到達速率與SLA允許到達的流量不匹配時,會使不同AF子隊列的令牌桶令牌存在富余或欠缺。二級令牌分配模塊對一級令牌分配后的令牌進行重新分配,累計每個AF子隊列的令牌富余或欠缺情況,計算欠缺令牌子隊列的令牌分配配額,然后等比例公平地將富余令牌分配給欠缺令牌隊列,從而為不同業(yè)務流提供一定程度上的帶寬動態(tài)分配[20],提高網絡帶寬利用率。

2.1 一級令牌分配

一級令牌分配模塊按照令牌添加速率為AF業(yè)務流對應的令牌桶添加令牌。SLA定義了各類AF業(yè)務流的流量特性,對應令牌桶的令牌添加速率為各類AF業(yè)務流的平均報文間隔。在網絡帶寬一定的情況下,網絡的平均信道利用率反映了網絡的負載狀態(tài)。根據網絡的輕載或中載狀態(tài)來逐漸降低當前按SLA允許到達的AF業(yè)務流量,重載時,為避免加重網絡擁塞,只允許AF業(yè)務中優(yōu)先級較高的業(yè)務流量進入隊列。通過指數平均來計算每個AF子隊列的平均流量到達率,并與當前按SLA允許到達的流量進行比對后,調節(jié)各個令牌桶的令牌添加速率。一級令牌分配模塊的動態(tài)令牌分配實現了AF業(yè)務流量的初步監(jiān)管,它能夠將流量的傳輸速率控制在合約允許的范圍內。設平均信道利用率為η,當前依據SLA允許到達的流量計算得到的監(jiān)管后實際允許的流量為S1,SLA允許到達的流量為S2,AF子隊列的空余隊列長度為q*,平均流量到達率為RA,當前令牌添加速率為RT,令牌添加速率的動態(tài)調整算法描述如下。

if η<20%,網絡處于輕載狀態(tài)

S1=S2

else if η<80%,網絡處于中載狀態(tài)

S1=(1-η)S2

else 網絡處于重載狀態(tài)

if RA

RT=RA

else

RT=S1

2.2 二級令牌分配

一級令牌分配后各令牌桶的令牌存在富余或欠缺的情況,二級令牌分配統(tǒng)計每個AF子隊列令牌的富余和欠缺情況,將所有富余令牌等比例公平地分配給欠缺令牌的AF子隊列。當AF子隊列的平均流量到達率小于當前按SLA允許到達的流量時,該隊列富余令牌,此時累計所有AF子隊列的富余令牌;反之,該隊列欠缺令牌,此時記錄每個隊列的欠缺令牌數量。二級令牌分配的依據是AF欠缺令牌子隊列的富余令牌分配配額。

2.2.1 富余令牌重分配配額計算

在DiffServ服務網絡中,富余令牌分配配額應由AF業(yè)務流的傳輸服務質量需求來決定,AF業(yè)務流的傳輸服務質量需求包括時延優(yōu)先級和包丟棄優(yōu)先級。但當網絡處于輕載狀態(tài)時,系統(tǒng)的時延和丟包率都較小,對AF欠缺令牌子隊列的富余令牌分配配額影響也較小,此時隊列的欠缺令牌數在較大程度上影響富余令牌的分配。綜上,AF欠缺令牌子隊列的富余令牌分配配額由隊列的欠缺令牌數、時延和丟包率共同決定,3個影響因子對應的富余令牌分配配額之和即為每個AF子隊列的富余令牌分配配額。基于3個影響因子的富余令牌分配配額計算方法如下。

1)基于欠缺令牌數的富余令牌重分配配額W1為:

其中,W1i為AF子隊列i的基于欠缺令牌數的富余令牌重分配配額,Qi為AF子隊列i的欠缺令牌數,K為欠缺令牌子隊列個數,P為AF隊列總的富余令牌數。

2)基于時延的富余令牌重分配配額W2

設時延優(yōu)先級級數為X,最低優(yōu)先級欠缺令牌的AF子隊列的富余令牌重分配配額為M,按優(yōu)先級高低等比例重分配富余令牌給各欠缺隊列,則時延優(yōu)先級為Xi的欠缺令牌子隊列i分配到的富余令牌重分配配額為:

W2i=Xi·M

所有欠缺令牌AF子隊列的富余令牌重分配配額之和等于富余令牌數量,即:

則有:

3)基于丟包率的富余令牌重分配配額W3

設包丟棄優(yōu)先級級數為Y,最低優(yōu)先級欠缺令牌的AF子隊列的富余令牌重分配配額為N,按優(yōu)先級高低等比例地分配富余令牌給各欠缺隊列,則包丟棄優(yōu)先級為Yi的欠缺令牌子隊列i分配到的富余令牌重分配配額為:

W3i=Yi·N

所有欠缺令牌AF子隊列的富余令牌重分配配額之和等于富余令牌數量,即:

則有:

2.2.2 權值因子動態(tài)調整

在網絡處于輕載時,AF欠缺令牌子隊列時延和丟包率較小,富余令牌重分配配額主要由隊列的欠缺令牌數決定。隨著AF業(yè)務流量的不斷增大,網絡逐漸處于中載狀態(tài),系統(tǒng)時延增大,AF子隊列的時延優(yōu)先級成為富余令牌重分配配額的關鍵影響因素。在網絡處于重載時,系統(tǒng)不斷丟包,AF欠缺令牌子隊列的丟包優(yōu)先級開始主導隊列的富余令牌重分配配額。網絡狀態(tài)不同,3個影響因素對AF欠缺令牌子隊列富余令牌重分配配額的影響程度各不相同。TCSN多級令牌桶流量監(jiān)管算法提供2種基于網絡狀態(tài)的權值因子動態(tài)調整算法。算法描述如下。

算法1權值因子分段調整算法

if 網絡處于輕載狀態(tài)

then (α=0.80,β=0.15,γ=0.05)

else if 網絡處于中載狀態(tài)

then (α=0.01,β=0.98,γ=0.01)

else if 網絡處于重載狀態(tài)

then (α=0.1,β=0.1,γ=0.8)

其中,α、β、γ分別為欠缺令牌數、時延、丟包率的權值因子,且α+β+γ=1。

算法2權值因子連續(xù)調整算法

權值因子連續(xù)調整主要依據AF子隊列的欠缺令牌數和隊列的傳輸服務質量需求,假設其相應的權重分別為δ1和δ2。其中,α=δ1,隊列的傳輸服務質量需求特性包括時延優(yōu)先級和包丟棄優(yōu)先級。在TCSN網絡中,δ1隨著信道利用率的增加而遞減,δ2隨著信道利用率的增加而遞增,則:

α=δ1=1-η

δ2=η

將δ2分配到時延優(yōu)先級和包丟棄優(yōu)先級,得到:

β=(1-η)δ2=(1-η)η

γ=ηδ2=η2

綜上,AF子隊列的富余令牌重分配配額為:

W=αW1+βW2+γW3

當AF業(yè)務流量經過多級令牌桶流量監(jiān)管模塊時,二級令牌分配模塊根據每個AF子隊列的富余令牌重分配配額為其分配令牌,進而對AF流量進行監(jiān)管。

3 仿真結果與分析

TCSN多級令牌桶流量監(jiān)管算法的關鍵在于兩級令牌分配的實現。一級令牌分配根據令牌添加速率控制AF業(yè)務流傳輸速率,其分配結果由AF子隊列的平均流量到達率和令牌桶的令牌添加速率決定。本文主要對二級令牌分配進行仿真分析。二級令牌分配統(tǒng)計每個AF子隊列令牌的富余和欠缺情況,將所有富余令牌等比例公平地分配給欠缺令牌的AF子隊列。富余令牌分配為基于欠缺令牌數、時延優(yōu)先級和包丟棄優(yōu)先級的富余令牌重分配配額之和?？紤]到網絡狀態(tài)不同,3個影響因子對富余令牌重分配配額的影響權重不同,在仿真時分別計算分段權值和連續(xù)權值下的富余令牌重分配配額。隨著仿真時間的延長,網絡的平均信道利用率不斷增大,網絡負載也隨之增大。仿真中AF子隊列參數設置如表1所示。3種富余令牌重分配配額的權值因子如表2所示。

表1 AF子隊列仿真參數設置

表2 富余令牌重分配配額權值因子

富余令牌重分配配額變化趨勢如圖2所示,實線為3個欠缺令牌子隊列的欠缺令牌增長曲線,虛線為欠缺令牌子隊列的富余令牌重分配配額,加粗線為網絡平均信道利用率的變化曲線。

圖2 富余令牌重分配配額變化趨勢

圖2(a)為分段權重下AF欠缺令牌子隊列的富余令牌重分配配額,從中可以看出,網絡處于輕載時,網絡的時延和丟包都較小,欠缺令牌越多,則分得的令牌越多,富余令牌重分配配額由隊列欠缺令牌數決定;網絡處于中載時,網絡時延不斷增大,隊列時延優(yōu)先級越高,富余令牌重分配配額越大,時延優(yōu)先級成為富余令牌重分配配額的主要影響因素;網絡處于重載時,網絡不斷丟包,子隊列的包丟棄優(yōu)先級越高,則分得的富余令牌越多,包丟棄優(yōu)先級開始主導子隊列的富余令牌重分配配額。但是,隨著網絡不斷丟包,AF子隊列的欠缺令牌越來越多,富余令牌越來越少,導致每個AF子隊列的富余令牌配額越來越小。圖2(b)為連續(xù)權重下的AF欠缺令牌子隊列的富余令牌重分配配額。同樣地,網絡負載狀態(tài)不同,決定富余令牌重分配配額的影響因子不同,連續(xù)權值是隨著平均信道利用率而不斷變化的。因此,其富余令牌重分配配額的變化趨勢與圖2(a)有所不同。

由上述實驗結果可知,每個AF子隊列所傳輸的AF業(yè)務具有不同的流量特性,所對應的令牌添加速率由流量特性決定。當網絡處于輕載、中載或重載狀態(tài)時,AF欠缺令牌子隊列的欠缺令牌數、時延優(yōu)先級和包丟棄優(yōu)先級對富余令牌重分配配額的影響程度不同。兩級令牌分配算法根據每個AF子隊列的流量特性和傳輸特性,公平地為子隊列分配令牌,從而實現AF業(yè)務流量的動態(tài)監(jiān)管。

4 結束語

列車控制業(yè)務的復雜化和旅客服務業(yè)務的多樣化,使得在列車控制與服務業(yè)務一體化傳輸的TCSN網絡中的流量監(jiān)管極其重要。傳統(tǒng)的流量監(jiān)管方式是靜態(tài)的,不宜直接應用于TCSN網絡。為此,本文提出一種動態(tài)令牌分配的多級令牌桶流量監(jiān)管算法。在令牌桶流量監(jiān)管的基礎上,采用兩級令牌分配模塊實現對AF業(yè)務流對應令牌桶令牌添加速率的動態(tài)調節(jié)和富余令牌的重新分配。仿真結果表明,該方法具有可行性,可為動態(tài)監(jiān)管列車控制與服務業(yè)務流量提供一種新思路,對TCSN網絡設備的設計具有一定的參考借鑒意義。下一步將根據實際應用情況對算法參數進行優(yōu)化。