一種基于控制平面測量的光突發(fā)交換網(wǎng)絡(luò)動態(tài)偏置時間算法

牛大偉 彭來獻 于衛(wèi)波 米志超 趙文棟 王 海

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

1 引言

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

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

2 控制平面排隊模型

2.1 模型假設(shè)

為分析簡單，后續(xù)的分析均假設(shè)網(wǎng)絡(luò)中僅存在單一瓶頸節(jié)點，BCP僅在該節(jié)點存在排隊可能。這種近似已經(jīng)被文獻[5]等使用過，并被證實能夠較好地近似現(xiàn)實網(wǎng)絡(luò)的情況。對于擴展的多瓶頸核心節(jié)點排隊，可以利用模擬單節(jié)點排隊的方法進行分析。

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

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

2.2 瓶頸節(jié)點排隊模型

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

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

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

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

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

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

圖1 W, PN 與Ks的關(guān)系

圖2 PN 與r的關(guān)系

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

圖4 歸一化負載與丟失率

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

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

3 動態(tài)偏置時間調(diào)整算法

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

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

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

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

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

表1 調(diào)整算法的偽代碼

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

4 仿真和性能分析

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

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

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

圖5 探測流與背景流

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

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

4.2 動態(tài)偏置時間算法的性能分析

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

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

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

5 結(jié)束語

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

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

表2 動態(tài)算法仿真輸出的偏置時間

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

[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]孫韓林. 互聯(lián)網(wǎng)流量、時延性質(zhì)及預(yù)測模型研究[D]. [博士論文], 北京郵電大學(xué), 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]劉劍平. 光突發(fā)交換網(wǎng)絡(luò)邊緣節(jié)點關(guān)鍵技術(shù)研究[D]. [博士論文], 西安電子科技大學(xué), 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.