動態令牌分配的TCSN多級令牌桶流量監管算法

趙晉南,, ,

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

0 概述

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

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

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

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

1 多級令牌桶流量監管算法

1.1 應用背景

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

1.2 多級令牌桶流量監管方案

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

圖1 TCSN流量監管方案總體結構

1.3 設計思路與系統實現

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

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

2 兩級令牌分配

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

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

2.1 一級令牌分配

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

if η<20%,網絡處于輕載狀態

S1=S2

else if η<80%,網絡處于中載狀態

S1=(1-η)S2

else 網絡處于重載狀態

if RA

RT=RA

else

RT=S1

2.2 二級令牌分配

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

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

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

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

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

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

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

W2i=Xi·M

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

則有:

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

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

W3i=Yi·N

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

則有:

2.2.2 權值因子動態調整

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

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

if 網絡處于輕載狀態

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

else if 網絡處于中載狀態

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

else if 網絡處于重載狀態

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

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

算法2權值因子連續調整算法

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

α=δ1=1-η

δ2=η

將δ2分配到時延優先級和包丟棄優先級,得到:

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

γ=ηδ2=η2

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

W=αW1+βW2+γW3

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

3 仿真結果與分析

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

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

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

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

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

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

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

4 結束語

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