一種基于控制平面測量的光突發交換網絡動態偏置時間算法

牛大偉 彭來獻 于衛波 米志超 趙文棟 王 海

(解放軍理工大學通信工程學院 南京 210007)

1 引言

光突發交換(OBS)是一種在光層直接進行報文級交換的技術，具備DWDM系統中波長資源的統計復用能力，在向全光交換演進的過程中，OBS網絡被認為是一種較為中肯的、可實現性較強的方案[1]。

偏置時間作為OBS網絡中最重要的參數，直接影響網絡吞吐量和時延性能。如果偏置時間設置過小，將引入早到丟棄(Insufficient Offset Time,IOT)，如果設置過大，將在邊緣節點引入過多的時延。目前，光突發交換網絡中最常見的偏置時間選取方法為固定偏置時間設置法。即邊緣節點根據預先假設核心節點的最大電處理時延為d，則入口邊緣節點為相距N跳的出口邊緣節點預設的偏置時間為N×d。動態偏置時間方面如文獻[2-4]，主要是針對網絡在偏射路由過程中引入時延抖動從而加劇早到丟棄的情況，通過邊緣節點和核心節點對網絡狀態的監測，動態調整偏置時間。文獻[2]利用核心節點實時采集的流量信息等知識計算額外偏置時間，克服可預見的偏置時間耗盡效應。文獻[3]在邊緣節點和核心節點之間引入交互信令，利用端口剩余時間和擁塞狀態作為轉發度量，從而實現本地的負載均衡。文獻[2]和文獻[3]需要核心節點與邊緣節點緊耦合，不利于網絡擴展，并且這一類方法在核心節點引入過多邏輯操作，進一步增加了核心節點負擔和核心節點電處理的隨機性。印度學者在文獻[4]中基于網絡穿越時延為正態分布的假設下，利用控制論的強化式學習方法，提出利用邊緣節點對控制突發(Burst Control Packet, BCP)歷史時延檢測結果估算未來額外偏置時間的方法。這類方法利用邊緣節點觀測值對網絡未來狀態進行預測，由于缺乏核心節點狀態信息，是一種完全的黑箱預測，算法存在對初始值敏感，預測值誤差大的問題。另外，BCP在核心節點的排隊時延和核心節點擁塞會嚴重影響網絡性能，而前述的各種檢測方法均忽略了此因素。本文從控制突發在核心節點的排隊和處理時延入手，研究BCP在核心節點排隊所引入的IOT概率，提出利用邊緣節點探測突發丟失率的歷史統計信息感知和預測網絡瓶頸核心節點背景流量，同時邊緣節點以探測突發的測量結論為依據動態調整偏置時間的方法。理論分析和仿真證明，該算法在目標IOT約束下能夠獲取較為中肯的偏置時間值，從而達到IOT和時延的性能折中。文章第2節描述核心瓶頸節點的排隊模型并以此為依據提出一種利用邊緣節點感知瓶頸核心節點負載的測量算法；第3節提出基于核心節點負載測量的動態偏置時間算法；第 4節利用仿真驗證的方法對所提出的兩種算法進行了驗證；最后是結束語。

2 控制平面排隊模型

2.1 模型假設

為分析簡單，后續的分析均假設網絡中僅存在單一瓶頸節點，BCP僅在該節點存在排隊可能。這種近似已經被文獻[5]等使用過，并被證實能夠較好地近似現實網絡的情況。對于擴展的多瓶頸核心節點排隊，可以利用模擬單節點排隊的方法進行分析。

根據文獻[6]，雖然OBS網絡邊緣節點整形并未改變突發流量的長程相關性，但是在一定時間尺度之內(例如組裝時延TB)，從突發到達間隔的角度分析，整形后流量仍近似服從泊松分布。因此，本文假設網絡中控制平面的流量符合泊松模型。

不失一般性，假設瓶頸節點處理時延為任意分布，即排隊為M/G/1/N模型，其中M表示 possion到達；N為控制平面緩存大小；G代表處理時延符合任意分布。另外引入如下符號和定義：L表示瓶頸節點平均隊長；PN表示瓶頸節點阻塞概率；W表示瓶頸節點平均排隊時延；r表示瓶頸節點歸一化負載；1/m與2s分別代表 BCP電處理時延的均值和方差。

2.2 瓶頸節點排隊模型

根據 Little定理[7]，可得到平均排隊時間W的表達式如(1)。而對M/G/1/N穩態的精確解析是相當困難的，通用的做法是對其進行一定程度的近似。本文利用文獻[7]結論(采用diffusion近似方法)，在N的數值為有限大的情況下，其排隊模型近似結論如式(2)。

式(1)和式(2)中Ks為 BCP 處理時間的方差系數；Pn為到達突發發現隊列長度為n的概率；W和m的定義與2.1 節相同。根據式(1)可知，在穩態條件下，如果r已知，則可以推算出W和PN(記為r→ {W,PN})。反之，如果能在邊緣節點利用采樣獲取W和PN的觀測值并進而反推出r(記為{W,PN}→r)，則可實現瓶頸節點狀態檢測。

式(2)表明PN和W的理論數值受方差系數Ks和穩態負載r的影響。圖 1表明在不同r的激勵下W和PN隨Ks變化趨勢的數值仿真結果。W曲線的單位為核心節點處理時延Δt(實驗中為 0.01)的倍數。當Ks大于10時，W曲線的差異性快速消失，而PN曲線除Ks極小外(小于5)，區分度較強。這說明，PN受核心節點控制平面結構和算法差異性的影響較小，適合作為網絡狀態估計的觀測變量。

圖2為PN隨r的變化規律的數值仿真結果。各條線對應的Ks由0到100。當Ks大于5時，PN可近似為r的線性增函數，斜率由Ks決定。圖3為Ks= 1 0時PN隨r的變化關系。通過對式(2)中的PN泰勒級數展開后，可得到式(3)，PN隨r以斜率q=1/exp(10/Ks)單調遞增。其近似程度較高(r接近于1時，近似偏差稍大)。圖 4為針對不同Ks參數的計算機仿真結論，3條曲線分別為Ks=5,10和50情況下核心節點統計的背景歸一化流量相對于丟失率的最小二乘擬合曲線，散點為仿真采樣數據。由于計算機統計精度誤差和有限樣本約束的原因，圖 4中的擬合曲線并非如圖3一樣穿越圓點，而是存在截距(約0.2)。可以認為，在歸一化負載低于0.2時，丟失率極小，以至于在有限樣本條件下大部分可近似為零。并且圖中不同Ks的擬合曲線的截距均趨近于0.2附近，說明方差系數Ks的變化并不影響歸一化負載r對控制突發丟失率PN擬合曲線的截距(均可近似以0.2取值)。

綜上可以認為：W受控制平面的固有屬性影響較大(Ks主要由節點結構和算法決定)，PN則相反，且PN是r的線性增函數，適合做瓶頸節點狀態的觀測值使用。且以PN為自變量對歸一化負載進行一階最小二乘擬合后的直線斜率與Ks相關，但是其縱軸截距均趨于固定值。

2.3 控制平面背景流量估計方法

圖1 W, PN 與Ks的關系

圖2 PN 與r的關系

圖3 PN與r的關系(Ks=10)

圖4 歸一化負載與丟失率

2.2節表明，W受控制平面固有屬性影響較大。并且根據文獻[7]的結論，即便到達流量是泊松分布，小尺度的排隊時延采樣仍然體現多重分形特性，所以不適合利用W估計核心節點背景流量。本節利用邊緣節點探測突發的PN作為觀測值，估計核心節點控制面負載。網絡運行時，由入口節點按照設置的步長Δl周期地增量發送探測控制突發(本文實驗中步長參數采用 Δl= 1 0 burst/s)，探測突發中攜帶發送序列號和時間戳，則出口節點可以根據探測突發流量和丟失率估算出網絡背景流量。設Si為入口節點第i個單位采樣周期it內BCP發送數目；Ri為出口節點收到的BCP數目；li為采樣周期i內探測突發負載；Avgλ為入口節點探測突發的滑動平均供給負荷向量；yi為出口節點在周期i針對探測突發采樣的丟失率，Avgy為滑動平均丟失率向量，則有式(4)：

式中b為記憶因子，范圍在(0,1)區間。此時的Avgy就是第3節中PN采樣值的滑動平均，而Avgλ是經過瓶頸節點的特定的探測流量采樣值的滑動平均。出口節點以探測突發丟失率向量(n個采樣值)作為自變量，以負荷向量(n個采樣值)作為因變量并利用一階最小二乘法估計其斜率和截距參數。設此時估計的擬合截距為dp而核心瓶頸節點的總流量的先驗擬合截距為dc,le為待估背景流負載，則利用式(5)可以計算出背景流量負荷。式(5)中，q1為未知參數，表示探測突發絕對負荷隨丟失率變化的斜率，該斜率由方差系數Ks決定，polyfit代表調用最小二乘擬合算法。式(5)說明，出口節點根據探測突發的負荷和丟失率估算出的擬合直線是圖4所示的經驗擬合直線的平行下移曲線，下移的距離即為當前背景流量。

3 動態偏置時間調整算法

文獻[8]已經證明：當負載接近于1時，偏置時間至少需要100倍于平均處理時延方能保證較小的IOT。而如此大的偏置時間勢必帶來較大時延損傷。根據背景流量的變化實時動態地調整偏置時間，在流量較小時入口節點為突發指派較小的偏置時間，在流量較大時入口節點為突發指派較大的偏置時間，將能夠有效地減小端到端的時延損傷。本節以第3節的流量測量結果為依據，根據背景流量的變化動態調整偏置時間，期望能夠在目標IOT約束下取得較合適的偏置時間值。

根據式(1)，單個控制突發(后文稱為當前突發)到達瓶頸節點隊列時看到的隊列長度為M，其概率為PM，隊列中第i個控制突發的處理時延為Xi( 1≤i≤M),Xi的均值為mi，方差為di。則當前突發的忙期等待時間為

式(6)中的XB為當前控制突發的處理時延，Xw為排隊等待時延。在N值有限的情況下，要得到準確的概率分布較為困難。本節利用文獻[9]中的分析方法，給出排隊時延Xw的近似尾部概率分布如式(7)。式(7)中的第 1個公式代表排隊超過x的概率等于e，而

為平均排隊時間，對于M/G/1/N模型即為式(1)中的W。假設式(2)中的核心節點處理時延u和隊列長度N先驗已知或可通過一些測量手段[10,11]進行測量。式(6)中右側的XB的尾部分布概率如式(8)(其分布取Γ分布)。XB,M的尾部概率分布為Xw和XB尾部概率的卷積。為克服卷積計算的復雜性，本文利用式(9)對X的尾部概率進行簡化和近似(其中P0為到達空系統的概率)。式(9)的概率相對于準確的聯合概率分布誤差存在一個平衡點e'，當e＜e'時，計算的概率誤差為正，且隨e減小而遞增(D→0)。當e＞e'時，計算的概率誤差為負且隨e的增大而減小。因此，本文在式(9)的基礎上引入調整因子g(e,r)修正誤差。g(e,r)的約束條件為：當目標IOT概率e＜e'時，g(e,r) ＜ 0 且隨e減小而遞減；當e＞e'時，g(e,r)＞0且隨e增大而增大，即g(e,r)為目標 IOTe的增函數且零點位于平衡點e'處。該調整因子根據處理時間分布的不同，可以有多種選擇。本文提出的調整因子如式(10)所示，其中e'= 1 0d1,d2為常數，主要是調整修正因子的幅度。d1和d2與網絡配置和參數有關，其精確值較難獲取，本文在仿真環境中通過一部分探測報文的訓練序列得出的結果，不斷調整，從而得到大體的數值。另外，g(e,r)中的1-r是為了補償式(7)在較大r條件下的誤差。

由式(9)和式(2)可知，要實現IOT丟棄概率≤e的目標，則只要設定偏置時間≥x即可。而x求解中的a和b參數可以采用基于測量的方法，利用 2.3節中所描述的背景流量測量方法來估算。綜上，動態偏置時間調整算法的偽代碼如表1所示。

表1 調整算法的偽代碼

上述算法中，step1為初始化過程：input為獲取輸入參數，OT0為初始偏置時間。Step2為偏置時間動態調整過程，其中的estimate()為調用2.3節中的背景流量測量算法，該算法每次調用耗時M·t;INV為調用式(10)的反函數；OTi為依據第i次測量的背景流量所估算的偏置時間。邊緣節點根據上述算法動態調整偏置時間，可以預期在保證目標IOT概率的基礎上，獲取到較適中的偏置時間。

4 仿真和性能分析

本小節利用仿真首先驗證測量算法以及基于測量算法的動態偏置時間調整算法，并分析該算法的精確性，同時分析了該算法在IOT丟棄率和時延方面的性能指標。

4.1 背景流量估計算法的性能分析

仿真環境為：背景流負荷為50 burst/s(即平均歸一化背景流量為 0.5)。入口節點以恒定速率的流量模型發送探測突發，其負載以10 burst/s的步長從10 burst/s遞增至50 burst/s(即背景流量與探測流量疊加后的總的流量負載為50-100 burst/s)。滑動平均窗口M=100，弱化因子b= 0 .75，核心節點平均處理速率為100 burst/s，處理時間符合Γ分布，且方差系數為10。

圖5 探測流與背景流

圖6 總負荷與探測負荷的最小二乘擬合

圖5中的曲線表明核心節點統計的總流量負載隨丟失率的變化的分段平均(虛線)與出口節點統計的探測突發負載隨丟失率的變化分段平均曲線(實線)相似度極大。散點區域為核心節點統計的背景流量負載(約為50 burst/s)。圖6所示的曲線為圖5中的分段平均曲線的最小二乘擬合，可以看到兩條曲線的斜率基本一致，底部的曲線為出口節點統計的探測流，其截距為dp=-2 2.6，上部的曲線為核心節點統計的背景流與探測流疊加的總流量，其截距為26.2(算法中設為20)。根據圖4所揭示的規律，邊緣節點可以先驗地假設核心節點的截距為dc= 2 0，因此此處存在估計誤差。我們看到，核心節點與邊緣節點統計的截距之差為48.8 burst/s。而邊緣節點根據當前統計的探測突發的負載擬合的截距和先驗假設的背景流量擬合截距差值估算當前的背景流量為42.6 burst/s，估計誤差約為6 burst/s。

4.2 動態偏置時間算法的性能分析

本小節對比了動態偏置時間算法仿真輸出、最小匹配偏置時間以及基于強化學習方法的RL算法[4]輸出結果的差異性。RL算法與本文提出的動態算法一樣，通過邊緣節點對核心節點狀態的預測為依據調整輸出偏置時間，不同處在于其采用純粹的黑箱預測方法，而不考慮核心節點的排隊特性。另外，此處引入的最小匹配偏置時間的概念如下：

圖7中比較了在不同目標IOT丟棄概率約束下的基于測量的動態偏置時間算法輸出、最小匹配偏置時間以及RL算法的輸出偏置時間(限于篇幅，僅列出 1 0-2和 1 0-5條件下的圖示)。本文動態算法參數取值為u= 1 00,d1= 2 ,d2= 1 0; RL算法對參數較為敏感，經過多次試驗，選用一組性能較為理想的參數即m0= 0 .2(20倍平均處理時延)，s0= 0 .1,g'=0.15,w=0.9,am=as= 0 .005。圖7中縱坐標為偏置時間(單位為核心節點平均電處理時間的倍數)。在大部分負載范圍內，基于測量的算法輸出的偏置時間始終保持略大于最小匹配偏置時間。負載較大時的誤差表明調整因子g此時所帶來的調整力度尚有所欠缺。RL算法由于對參數初值敏感并且其黑箱預測機制無法準確跟蹤核心節點控制平面流量的變化，所以其輸出的偏置時間無法實現較大范圍的動態調節，其性能相對本文的算法較差。

表2中列出了在不同目標IOT概率約束條件，動態偏置時間算法輸出的偏置時間和相同仿真條件下最小匹配偏置時間之間的對比，單位為核心節點平均處理時延的倍數。表中的后3列記錄是在歸一化流量由0.1到0.9變化的過程中動態偏置時間算法輸出的最小偏置時間，最大偏置時間和平均偏置時間；而第1列為相同仿真條件下的最小匹配偏置時間。可以看到，在大部分目標IOT概率約束下，動態偏置時間算法輸出偏置時間的平均值(第 5列)和最小匹配偏置時間值基本一致。并且，結合圖8的曲線可知：本文的動態偏置時間算法擁有比目標IOT丟棄率(也即偏置時間選取最小匹配偏置時間)低得多的實際IOT概率。而付出的代價僅僅是平均偏置時間略高于最小匹配偏置時間。這得益于動態算法以背景流量為依據的較大動態范圍的偏置時間調整能力(表2的后3列)。RL算法由于跟蹤核心節點控制平面負載的能力較弱，估算的偏置時間遠低于實際需要的偏置時間，所以其達到的實際IOT丟棄率比目標丟棄率要高得多。

5 結束語

圖7 不同目標IOT約束條件下各算法輸出偏置時間與負載關系

圖8 各種算法獲取的實際IOT概率

表2 動態算法仿真輸出的偏置時間

本文通過研究光突發交換網絡控制平面的排隊模型，提出了一種以探測突發丟失率為觀測變量的瓶頸核心節點背景流量估計算法，并在該估計算法的基礎上提出了一種基于測量的動態偏置時間指派算法。該算法以邊緣節點對瓶頸核心節點背景流量的測量結果為依據，根據瓶頸核心節點的負載，動態指定偏置時間。仿真和理論分析證明，該算法能夠在接近最小匹配偏置時間的條件下取得較低的IOT丟棄率。文章后續的研究重點將集中在小樣本觀測變量條件下的快速背景流量測量方法以及依據流量測量結果動態調整邊緣節點組裝門限算法方面。

[1]Abdeltouab Belbekkouche, Jihene Rezgu, and Abdelhakim Hafid. Wireless mesh and optical burst switching convergence for a novel metropolitan area network architecture [J].Computer Networks, 2011, 55(1): 159-172.

[2]Coutelen T and Jaumard B. An efficient adaptive offset mechanism to reduce burst losses in OBS networks [C]. IEEE GLOBECOM, ST Louis MO, 2005: 2053-2056.

[3]Amit Kumar Garg and Kaler R S. Feedback based load balancing, deflection routing and admission control in OBS networks [J].Journal of Networks, 2010, 5(11): 1290-1299.

[4]Amit Kumar Garg and Kaler R S. An efficient routing scheme to reduce packet loss in all optical networks [J].Journal of Microwaves Optoelectronics and Electromagnetic Applications, 2010, 9(2): 113-122.

[5]Seung Yeob Nam, Kim Sunggon, and Sung Dan Keun.Measurement-based admission control at edge routers [J].IEEE/ACM Transactions on Networking, 2008, 16(2):410-423.

[6]Izal M and Aracil J. On the influence of self-similarity on optical burst switching traffic [C]. IEEE. GLOBECOM,Taipei, 2002: 2308-2312.

[7]孫韓林. 互聯網流量、時延性質及預測模型研究[D]. [博士論文], 北京郵電大學, 2010.

[8]Hassan M, Sarker R, and Atiquzzaman M. Modeling IP-ATM gateway using M/G/1/N queue [C]. IEEE GLOBECOM,Sydney, 1998: 465-470.

[9]劉劍平. 光突發交換網絡邊緣節點關鍵技術研究[D]. [博士論文], 西安電子科技大學, 2006.

[10]Edmond W W, Luo Xiapu, and Li Weichao. Measurement of loss pairs in network paths [C]. Annual Conference on Internet Measurement, New York, 2010, 10: 88-101.

[11]Edmond W W, Luo Xiapu, and Chang K C. A minimumdelay-difference method for mitigating cross-traffic impact on capacity measurement[C]. International Conference on Emerging Networking Experiments and Technologies, Rome,Italy, 2009, 5: 1-4.