基于路徑估計的網絡接納控制研究

邱恭安，徐晨，章國安,2，包志華

(1. 南通大學 電子信息學院，江蘇 南通 226019；2. 東南大學 移動通信國家重點實驗室，江蘇 南京 210096)

1 引言

未來寬度網絡將綜合承載語音、多媒體和數據業務，在為時延敏感業務提供時延保障的基礎上，為非實時彈性業務提供基本吞吐量。要在相同網絡上提供不同業務的差異化性能，可通過鏈路資源冗余方式，或應用接納控制策略[1]。然而，要在整個網絡中保持較低的端到端阻塞率，帶寬冗余是極其浪費的，網絡接納控制是有效方式[2,3]。通常鏈路接納控制僅計算下游鏈路對接入業務的資源保障，而不考慮網絡路徑后端瓶頸鏈路狀態，不能有效保障實時業務的端到端時延要求。網絡接納控制(NAC,network admission control)[4]評價既定網絡傳輸路徑資源能夠支持多少可保證QoS (quality of service)請求的應用，在多條鏈路構成的路徑上提供一致的接納判決。因此，網絡接納判決的準確性取決于傳輸路徑狀態信息的有效性，然而傳輸延遲或網絡資源節省使得基于測量或路由表獲取的路徑狀態信息具有陳舊性[5]，不再能描述網絡的真實狀態[6]，因此，獲取實時或準實時的傳輸路徑狀態信息成為網絡接納控制的關鍵。

2 相關工作

根據接納判決方式，網絡接納控制分為基于預算的網絡接納控制(BNAC, budget based network admission control)和基于反饋的網絡接納控制(FNAC, feedback based network admission control)兩大類[7]。其中BNAC應用虛擬的路徑容量預算策略進行接納判決，而FNAC則根據返回的路徑測量信息作出判決，共同特點是基于流進行接納控制。FNAC首先從源端發送一個或幾個探測分組測量傳輸路徑負載狀態，根據返回分組的QoS指標判斷是否接納請求業務流，存在著測量準確性和網絡狀態陳舊性問題。而且，需要占用一定的網絡資源用于測量，鏈路資源效率存在著瓶頸上限。

BNAC需要與路徑相關所有鏈路虛擬容量預算均滿足業務請求時才接納該業務，由于網絡承載狀態的動態變化，BNAC容量預算不能準確反映路徑當前狀態，容易導致鏈路資源效率低下或后端瓶頸鏈路擁塞。根據容量預算類型不同，BNAC分為基于鏈路預算的網絡接納控制(LB NAC, link budget based network admission control)、基于輸入端輸出端預算的網絡接納控制(IB/EB NAC, ingress and egress budget based network admission control)和基于邊到邊預算的網絡接納控制(BBB NAC, border to border budget based network admission control)3種方法。LB NAC在路徑上的每條鏈路上執行接納判決，狀態信息在沿途各個路由器中保留，存在可擴展性問題。IB/EB NAC在業務流路徑兩端執行接納判決，實現了核心無狀態，但可能會因網絡中間鏈路失效而引起擁塞。BBB NAC在輸入端執行判決，不要網絡內部狀態，但使用虛擬通道進行資源預留，網絡節點額外開銷過多。

基于業務識別的流感知策略利用協議上層隱性的連接建立過程執行業務接入判決，而公平調度算法本身的隱性測量功能可獲取本地鏈路實時狀態，結合路由廣播信息中的陳舊路徑狀態信息，可應用證據理論[8]推理出網絡路徑狀態的準實時狀態值。以此估計的準實時狀態作為網絡接納控制的判決條件，可以提高判決結果的準確性。

3 基于證據理論的網絡路徑態勢估計

對于網絡路徑態勢估計來說，命題即是網絡可能呈現的不同承載狀態。設網絡路徑態勢集為{輕載、重載、過載}3種假設，而本地狀態指標和陳舊路徑狀態指標對網絡態勢的估計作為證據體。因此，路徑態勢估計的實質就是在當前態勢分類的條件下，將本地狀態指標和陳舊路徑狀態指標的不同估計值合成一個證據體，完成對態勢集中樣本進行識別的過程。

3.1 證據體及其基本概率賦值

在流感知網絡中，本地鏈路狀態指標為優先隊列隊長和當前鏈路公平速率，分別描述優先業務和彈性業務的承載狀態，而路由算法中的路徑參量則描述了網絡路徑的陳舊狀態。因此，本地鏈路狀態和陳舊路徑狀態指標合成后的基本概率賦值描述了網絡路徑態勢的估計，則可將最大置信度命題作為備選命題。可見，由兩類狀態指標推理得到對不同態勢類的基本概率賦值是路徑態勢估計的關鍵。

鑒于多業務區分過程中的模糊性，模糊流感知[9]將業務區分界值模糊化為邊界區間來處理此模糊性，以適應網絡狀態的動態變化。設鏈路狀態指標對鏈路態勢的估計為{O,H,L}，分別表示鏈路處于{過載，重載，輕載}3種態勢類，則狀態指標的模糊子集可以使用三角形和梯形實現對事件狀態的量化，如圖1所示。

圖1 鏈路狀態指標的模糊子集

設優先隊列隊長為Q，擁塞門限為QT，隊列轉發門限為QFT，最大緩存容限為B，若取隊長Q=x,QT=xL, QFT=xU，并取x上限為B，則使用隊長模糊子集的隸屬函數對隊列指標的基本概率賦值函數mQ={q3, q2, q1}進行量化，如式(1)～式(3)，其中qi,i=3,2,1分別表示鏈路當前{O, H, L}3種狀態的基本概率賦值，且xM=(xU-xL)/2。

同樣，設節點下游鏈路當前公平速率為RF，擁塞門限為RT，擁塞告警門限為RCT，鏈路速率為C，若取變量RF=x, RT=xL, RCT=xU，并取x上限為C，則隸屬函數(1)～(3)能夠對公平速率指標的基本概率賦值函數mR={R1, R2, R3}進行量化，其中Ri, i=1, 2,3分別表示鏈路當前{O, H, L}3種承載狀態的基本概率賦值。于是，本地鏈路狀態的基本概率賦值函數 mL由優先隊列指標和公平速率指標的正交和得到如下：

多業務網絡中，時延敏感實時業務通常選擇最短路徑優先策略以減少路徑傳輸時延，而路徑有效帶寬最大化作為第二路由規則，即使用最寬最短路由算法(W-S, widest-shortest path algorithm)。由于所有選擇路徑均為最短路徑，傳輸路徑上的有效帶寬反映了實時業務的最優路徑擁塞狀態，故可用有效帶寬描述實時業務的路徑擁塞度。路徑有效帶寬定義為傳輸路徑上所有鏈路有效帶寬的最小值。若鏈路容量為C，鏈路進程承載的優先業務流和彈性流分別為(Ns, Ne)，優先業務流平均恒定速率為Rs，則有效帶寬r為鏈路彈性流的平均有效速率：

對響應時間敏感的彈性流希望選擇有效帶寬最大路徑傳輸數據，而路由跳數最短作為次要條件，即使用最短最寬路由算法(S-W, shortest-widest path algorithm)，則路由跳數差Δh可以描述彈性流的路徑擁塞度，其中Δh為流當前選擇路徑的路由跳數與最短路徑路由跳數之差，路由跳數可由路由算法本身測量獲得。根據不同類型業務的路徑擁塞指標，定義如下路徑效用函數(utility function)[10]對網絡的路徑擁塞狀態進行描述。

其中，G∈(0,∞)為比例增益常數，默認為1，r為路徑P的有效帶寬。效用函數U隨有效帶寬r遞增而增大，隨路由跳數差Δh增加而線性遞減，當G=0時，效用函數退化為彈性流的有效帶寬最大路由算法(widest path algorithm)的選路標準；當G=∞時，效用函數又變為優先業務流的最短路徑路由算法(minimum-hop path algorithm)的選路標準。因此，效用函數能夠反映多業務網絡傳輸路徑的擁塞狀態。

由效用函數得到的路徑狀態是過時的，僅作為網絡路徑態勢估計的路徑狀態基本概率賦值函數的輸入值。當r≤RT時，路徑處于擁塞狀態，路由算法選擇最短路徑有效，即Δh=0，效用函數僅是有效帶寬的對數值，定義為效用函數的擁塞門限UT=lnRT。當r∈(RT, RCT]時，路徑處于重載狀態，為減小網絡阻塞率，彈性流盡量選擇最短路徑傳送分組，定義為效用函數的擁塞告警門限UCT=lnRCT。當r＞RCT時，路徑處于輕載，彈性流將優先選擇S-W路由算法，路徑P的效用函數為UP=lnr-Δh, G=1。若路徑指標對路徑態勢的估計為{O, H, L}3種態勢，則路徑指標的模糊子集可量化實現為圖2所示，其中UM=(UCT-UT)/2。

圖2 效用函數的模糊子集

設路徑態勢估計的基本概率賦值函數為mP={A1, A2, A3}，其中Ai, i=1, 2, 3分別表示鏈路當前{O, H, L}3種態勢的基本概率賦值{μO(u), μH(u),μL(u)}，由模糊子集可分別量化為

3.2 網絡路徑態勢估計

網絡路徑態勢估計結果的正確性依賴于本地鏈路狀態和路徑狀態指標的周期性測量與更新，在測量本地鏈路狀態指標的基礎上，量化得到鏈路狀態的基本概率賦值 mL和路徑效用函數的基本概率賦值mP后，根據圖 3推理過程對網絡路徑態勢進行估計。

圖3 路徑態勢估計中的信息融合

設路徑態勢估計的辨識框架共有 3個命題，本地L表示本地鏈路狀態在t時刻對不同命題的判斷結果集。路徑P表示陳舊路徑狀態在t時刻對不同命題的判斷結果集，mL(Ai)/mP(Ai), i=1,2,3為對命題Ai的基本概率賦值，m(Ai)為經過Dempster合成后得到網絡路徑的新基本概率賦值m(Ai), i=1,2,3，且有：

路徑狀態的新基本概率賦值 m(Ai)描述了根據最新測量數據推理得到的網絡路徑不同態勢的置信度（概率值）。路徑狀態的更新則隨路徑指標的周期性測量而由預計算模塊進行更新，但在同一測量周期內路徑態勢集中樣本保持不變。

對于估計的網絡路徑態勢集及相應態勢樣本的概率賦值，設集合中不確定性概率 ()mΘ大于門限ε2，若某態勢A1具有最大概率賦值，且與其他態勢樣本的概率賦值差大于門限ε1，則取態勢A1作為傳輸路徑的準實時態勢值。即：

若態勢集樣本A1同時滿足下列不等式：

其中，ε1、ε2是預先設定的門限值。則路徑態勢計算模塊判決輸出 A1為路徑下一周期準實時路徑承載狀態。

4 基于路徑估計網絡接納控制算法

基于估計的當前路徑狀態，算法執行兩級接納判決。首先進行粗粒度的路徑接納判決，并根據其判決結果決定是否進行本地鏈路接納判決。

4.1 路徑接納判決

當估計路徑態勢為過載時，節點直接丟棄業務請求分組而無需進行二次判決；當路徑態勢為重載時，為降低優先業務的阻塞率并保證其低時延性能，本地網絡節點直接丟棄感知為彈性流的業務請求分組，僅對優先業務流執行本地鏈路判決。當路徑態勢為輕載時，所有業務流均被無區分接入，無需進行二次接納判決，僅由調度機制對接入的業務流進行區分轉發。

其中，Reject為對請求業務流的拒絕判決，Accept為接納請求業務流，而LD則是對請求業務流的本地鏈路接納判決(LD, local decision)，僅在路徑重載時對具有優先權的優先業務進行區分控制。

4.2 鏈路接納判決

本地鏈路接納判決僅在優先隊列小于其擁塞門限，且網絡路徑重載時執行。當優先業務重載而彈性業務輕載時，優先業務的接入必然增大優先隊列長度，則以與隊長相關的概率拒絕優先業務的接入。設拒絕概率為P1，且定義為

其中，隊長敏感指數k1描述了拒絕概率P1對隊長Q變化狀態的敏感程度。若k1較小，則增加隊長會顯著地增大拒絕概率，能有效抑制網絡路徑過載發生。同時，冗余了更多的網絡資源，將降低路徑資源利用率，因此，k1取值可根據實際應用要求進行設置。

當優先業務輕載而彈性業務重載時，接入優先業務會降低鏈路公平速率，惡化彈性流的基本吞吐量，因此，以與鏈路公平速率相關概率接納優先業務。設接納概率為P2，且：

其中，速率敏感指數 k2描述了接納概率 P2對鏈路公平速率R變化的敏感程度。若k2較大，則接納概率能較快地響應鏈路公平速率的變化，有益于鏈路效率的提高。但是P2頻繁地改變增大了鏈路流量的動態性。

當所有類型業務均處于重載時，上述兩類影響均存在，因此，接入概率為

則在網絡路徑重載時，可得網絡接納控制二次本地接納判決集為

與IB/EB NAC不同，基于路徑估計的網絡接納控制(PA NAC, path assessment based network admission control)雖然僅在網絡輸入端執行本地接納判決，但在路徑判決時考慮了構成網絡路徑的所有鏈路狀態，能以高概率避免網絡后端鏈路瓶頸遺漏問題。與BBB NAC不同，PA NAC雖然需要路徑狀態信息，但不需要網絡內部鏈路參與，通過增加邊緣節點的預計算來實現網絡核心狀態無關。

5 算法復雜度分析

設網絡輸入輸出端節點數分別為 D、E，網絡中鏈路總數為N，則由IB/EB NAC算法原理可知，其分別在業務接入端和輸出端各執行一次接納判決，故接納判決過程中需要兩次計算條件表達式是否滿足要求。針對每個判決條件，節點需要計算鏈路資源預算。對于每一個可能的路徑，需要獨立計算各節點及相應鏈路的預算資源，因此總共計算量為(D+E)+N，而且預算資源的計算量會隨源/宿端的增加而增加。

PA NAC僅在業務輸入端進行接納判決，對于被拒絕的業務流僅作出一次判決，因此為每個業務流作出判決的平均次數小于兩次。在一個允許接入的完整接納判決過程中，算法先后需要進行兩次搜索查表工作，而兩次獨立查表復雜度均為O(1)，故一次判決過程的計算復雜度為O(1)，但計算量不會隨端點增加而增加。

PA NAC計算量在兩級判決過程中均有不同程度地減少，簡化了接納控制模塊的復雜度。系統所增加的路徑態勢推理和本地鏈路狀態測量的計算由額外的模塊獨立進行，這正是應用并行計算減小網絡操作機制計算量的目的。

6 仿真計算

網絡接納控制機制在網絡重載時保護承載業務請求性能限，防止網絡過載的發生。在網絡輕載時，鏈路冗余本身能夠滿足接入業務端到端請求的性能限，執行嚴格的接納判決導致業務性能的提高非常有限，因此仿真僅在重載條件下進行。

網絡模型使用簡單的多跳網絡仿真拓撲，如圖4所示，路徑鏈路參數如圖4所示。為簡化計算，取敏感指數 k1=k2=1，仿真比較了 PA NAC與IB/EBNAC算法統計結果。PA NAC僅在源端網絡節點上進行判決，而IB/EBNAC則同時在源端和宿端 2個節點上使用各自的判決條件不等式進行決策，其網絡路徑資源的占用統計使用 Kaufman-Roberts algorithm (KRA)計算[11]。網絡態勢估計預計算和本地鏈路狀態測量分別由額外模塊輔助預計算，而預計算得到的狀態變量則由節點負責維護更新，其計算周期、狀態參數及路徑態勢估計更新周期與公平調度算法的測量周期同步，優先業務和彈性業務路由分別使用WSP和SWP算法[12]。

圖4 多跳網絡仿真拓撲

仿真統計了低速語音流的阻塞率指標和鏈路效率曲線，分別如圖5和圖6所示。語音流阻塞率曲線顯示 PA NAC在重載時的阻塞率一直小于IB/EB NAC算法，因為在路徑態勢估計下的一次接納判決僅僅允許速率較低的優先業務流接入網絡，進行了多業務的接入區分。而IB/EB NAC算法同等對待所有請求業務流，但這并不能實質性地增加彈性流的吞吐量，因為鏈路重載時進一步接納高速業務會惡化網絡路徑狀態，增大分組丟失率，造成大量分組重傳，浪費了網絡資源。

圖5 64kbit/s語音流阻塞率

圖6 鏈路效率曲線

圖6中2種算法的鏈路效率證明了上述結論，鏈路效率定義為統計時間內接收端完成流傳輸字節數與源端發送字節數之比的均值。在路徑鏈路重載時，IB/EBNAC算法鏈路效率低下，最大約為26%左右，而PA NAC明顯具有較高的鏈路效率，最大可達 67%左右，因為它不僅對多業務進行了接入區分，還進行了轉發區分，對網絡資源進行了相對嚴格的管理。當然，IB/EBNAC算法的資源利用率在3種BNAC算法中本身也是最低的，但其他算法付出的代價是要進行更多的判決決策，需要節點具備高性能計算能力和高效的資源分配策略。其中 LBNAC算法計算復雜度會隨源/宿端節點增多呈非線性增大，從而不能應用于實際的大規模網絡管理和控制。BBBNAC算法則增大了網絡路徑狀態信息的維護和更新開銷，路徑狀態信息的傳播時延和鏈路效率將隨網絡節點的增多而惡化。相反，當網絡節點增多時，PA NAC僅僅增加了路徑態勢估計的預計算量和節點管理路徑狀態的緩存開銷，但在二級本地接納判決時，它簡化了判決計算復雜度。

7 結束語

為保障不同業務差異化的端到端性能，平滑和抑制潛在的隨機擁塞，需要網絡接納控制實現業務接入區分。而待傳輸路徑的實時狀態信息決定了網絡接納控制的有效性，通過邊緣節點智能計算得到的路徑態勢估計有效減少了網絡核心狀態的復雜度。在估計的路徑狀態下執行一級網絡接納判決，以判斷網絡是否需要進行二級接納判決。二級判決僅在鏈路重載時執行，由本地鏈路狀態實現業務區分接入。PA NAC算法通過分解網絡接納判決過程實現計算簡化和網絡核心狀態無關，克服了BNAC計算繁雜和應用可擴展性問題，仿真顯示其更適合共同承載不同速率分布的多業務網絡。

[1] WRIGHT S. Admission control in multi-service IP networks: a tutorial[J]. IEEE Communications Surveys & Tutorials, 2007, 9(2):72-87.

[2] CHO I K, OKAMURA K. A centralized resource and admission control scheme for NGN core networks[A]. International Conference on Information Networking[C]. Chiang Mai, Thailand, 2009. 1 - 5.

[3] MARTIN R, MENTH M, CHARZINSKI J. Comparison of border-to-border budget based network admission control and capacity overprovisioning[A]. The 4th International IFIP-TC6 Networking Conference[C]. Waterloo, Canada, 2005. 1056-1068.

[4] MENTH M, KOPF S, MILBRANDT J. A performance evaluation framework for network admission control methods[A]. IEEE/IFIP Network Operations and Management Symposium[C]. Seoul, Korea,2004. 307- 320.

[5] 徐恪, 吳建平, 徐明偉. 高等計算機網絡——體系結構、協議機制、算法設計與路由器技術[M]. 北京: 機械工業出版社, 2005.175-235.XU K, WU J P, XU M W. Advanced Computer Network-System Ar-chitecture, Protocol, Algorithm and Router Technology[M]. Beijing:Machine Industry Press, 2005. 175-235.

[6] CHENG G, ANSARI N. Minimizing the impact of stale link state information on QoS routing[A]. IEEE Global Telecommunications Conference[C]. Missouri, USA, 2005.5 - 9.

[7] MENTH M. Efficient Admission Control and Routing for Resilient Communication Networks[D]. University Wuerzburg, 2004.

[8] 賁可榮, 張彥鐸. 人工智能[M]. 北京: 清華大學出版社, 2006.142-181.BEN K R, ZHANG Y D. Artificial Intelligence[M]. Beijing: Tsinghua University Press, 2006. 142 - 181.

[9] 邱恭安, 張順頤, 胡雋. 基于模糊流感知的動態優先公平調度算法[J]. 電子與信息學報, 2009, 31(2): 467-471.QIU G A, ZHANG S Y, HU J. Fuzzy flow awareness based dynamical priority fair scheduling algorithm[J]. Journal of Electronics & Information Technology, 2009, 31(2): 467-471.

[10] OUESLATI S, ROBERTS J. A new direction for quality of service:flow-aware networking[A]. Next Generation Internet Networks[C].Roma, Italy, 2005. 226-232.

[11] TOELLE D, KNORR R. Performance evaluation of potential and management based network admission control methods[A]. IEEE International Conference on Communications[C]. Istanbul, Turkey, 2006.754-759.

[12] HORNG M F, KUO Y H. An effective approach to adaptive bandwidth allocation with QoS enhanced on IP networks[A]. The 3rd International Conference on Ubiquitous Information Management and Communication[C]. Suwon, South Korea, 2009. 260-264.