王 冕,劉成耀

(重慶郵電大學(xué) 重慶高校光纖通信技術(shù)重點實驗室,重慶 南岸 400065)

目前,單纖可以支持 Tb/s業(yè)務(wù)速率,任何鏈路或者節(jié)點的失效將導(dǎo)致巨大損失.據(jù)美國 FCC報告顯示,每兩天就有一次影響 30 000名客戶的網(wǎng)絡(luò)故障發(fā)生,而故障修復(fù)的平均時間是 5～10 h.此外,若傳輸容量達(dá) Tb/s的單根光纖失效,將影響 1 200萬對以上的電話業(yè)務(wù)[1],因此網(wǎng)絡(luò)的故障容忍策略則為重中之重[2-3].動態(tài)業(yè)務(wù)量疏導(dǎo)已經(jīng)開始成為故障容忍策略的研究熱點.文獻(xiàn)[4]研究了業(yè)務(wù)量疏導(dǎo)過程中建立可靠業(yè)務(wù)連接的問題;文獻(xiàn)[5]提出 2種基于固定備選路由的動態(tài)業(yè)務(wù)量疏導(dǎo)算法,在預(yù)計算過程中考慮疏導(dǎo)業(yè)務(wù)的均衡;文獻(xiàn)[6]設(shè)計多層網(wǎng)狀網(wǎng)絡(luò),在滿足各種業(yè)務(wù)帶寬要求和保護(hù)要求的同時,最小化全網(wǎng)費用,并提出一個數(shù)學(xué)模型和相關(guān)算法;文獻(xiàn)[7]研究了在異構(gòu) WDM網(wǎng)狀網(wǎng)中動態(tài)地為具有不同帶寬粒度的單播業(yè)務(wù)請求建立連接的問題,通過擴(kuò)展文獻(xiàn)[8]中的通用圖模型,進(jìn)行有效的業(yè)務(wù)量疏導(dǎo),達(dá)到不同的業(yè)務(wù)量工程(Traffic Engineering)目標(biāo);為了減小網(wǎng)絡(luò)中OXC端口費用,文獻(xiàn)[9]研究了具有不同交換粒度 OXC的WDM網(wǎng)絡(luò)設(shè)計問題,提出了一種業(yè)務(wù)量疏導(dǎo)算法自動決定采用網(wǎng)絡(luò)節(jié)點中的某種類型的 OXC;文獻(xiàn)[10]研究了節(jié)點具有波長變換能力情況下,動態(tài)業(yè)務(wù)量疏導(dǎo)策略.但是,上述文獻(xiàn)沒有考慮網(wǎng)絡(luò)故障的疏導(dǎo)策略將會產(chǎn)生負(fù)面效應(yīng),因此,設(shè)計有效的、合理的故障感知業(yè)務(wù)量疏導(dǎo)策略非常迫切.

1 問題描述

1.1 探測圈覆蓋

探測圈覆蓋的主要思想是把網(wǎng)絡(luò)分解為圈的集合,使得網(wǎng)絡(luò)上的每個節(jié)點和每條鏈路至少被集合中的一個圈所覆蓋,稱為“探測圈”,每個圈被分配一套探測模塊等監(jiān)測設(shè)備.探測圈實際上是閉合的波長通路,網(wǎng)狀光網(wǎng)絡(luò)可以建模為一個有限的無向連通無橋圖G(V,E).

圖1 探測圈覆蓋示例圖

任何無橋連通圖G(V,E)都有它的圈覆蓋C,但不唯一,其中 C中的元素用 c表示.c1和 c2構(gòu)成了圖1所示拓?fù)涞娜Ω采w[11].有 3種圈覆蓋算法[12]用于發(fā)現(xiàn)網(wǎng)絡(luò)的圈覆蓋,即啟發(fā)式深度優(yōu)先搜索(HDFS)、最短路徑匹配(SPEM)和啟發(fā)式生成樹圈覆蓋算法(HST).本文擬采用啟發(fā)式生成樹圈覆蓋算法(HST),如圖2.

圖2 基于HST啟發(fā)式算法的圈覆蓋

如前所述,探測圈覆蓋方式使得物理拓?fù)鋵觾?nèi)的所有節(jié)點和鏈路至少都被一個探測圈所覆蓋,其中圈內(nèi)的監(jiān)測節(jié)點通過探測包對其它節(jié)點以及節(jié)點之間鏈路的性能進(jìn)行監(jiān)測.顯然,在這種情況下,可以認(rèn)為網(wǎng)絡(luò)存在兩類節(jié)點,每類相同的節(jié)點組成各自的邏輯層,這樣,探測圈將網(wǎng)絡(luò)從邏輯上分解為多個圈的集合,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出現(xiàn)分簇情況,每個監(jiān)測節(jié)點和其所管理的節(jié)點構(gòu)成一個簇.與傳統(tǒng)的分簇方式不同,采用這種方式之后,業(yè)務(wù)量疏導(dǎo)問題可以進(jìn)一步劃分為 2個子問題,分別為簇內(nèi)業(yè)務(wù)量疏導(dǎo)和簇間業(yè)務(wù)量疏導(dǎo).顯然,簇間業(yè)務(wù)量疏導(dǎo)需要由簇頭節(jié)點負(fù)責(zé),而簇內(nèi)業(yè)務(wù)量疏導(dǎo)則按照傳統(tǒng)方式執(zhí)行.按照這種方式,整個業(yè)務(wù)量疏導(dǎo)過程需要增加網(wǎng)絡(luò)分割、簇內(nèi)業(yè)務(wù)量疏導(dǎo)和簇間業(yè)務(wù)量疏導(dǎo) 3個過程,其與通常情況下動態(tài)業(yè)務(wù)量疏導(dǎo)策略的流程區(qū)別如圖3所示.

圖3 業(yè)務(wù)量疏導(dǎo)問題流程描述

2 仿真及結(jié)果分析

2.1 網(wǎng)絡(luò)仿真環(huán)境

為了充分驗證疏導(dǎo)策略的性能,且便于網(wǎng)絡(luò)分割,本文采用了如圖4所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).該拓?fù)湓贜SF網(wǎng)絡(luò)的基礎(chǔ)上新增了 2個節(jié)點,即 16個節(jié)點,24條鏈路.各節(jié)點之間由 WDM鏈路連接,每條 WDM鏈路包括 9個速率為 2.5Gbit/s的波長信道,固定其中的一個波長信道作為控制信道,每個節(jié)點都具有完全的波長轉(zhuǎn)換能力.業(yè)務(wù)源所產(chǎn)生的數(shù)據(jù)包大小服從均值為 500 B的負(fù)指數(shù)分布,數(shù)據(jù)包的最小長度設(shè)為 40 B,最大長度設(shè)為 1.5 KB;數(shù)據(jù)包的到達(dá)時間間隔服從均值為 8μs的負(fù)指數(shù)分布;簇頭節(jié)點的光交換矩陣的配置時間為 2μs.

圖4 增加2個節(jié)點的 NSF網(wǎng)絡(luò)拓?fù)?/p>

結(jié)合圖2,本文將網(wǎng)絡(luò)分割(如圖5),按節(jié)點連通度高并同時考慮簇頭節(jié)點到各成員節(jié)點距離最小來選取簇頭,則拓?fù)?1)(2)(3)可選取的簇頭節(jié)點為節(jié)點 11,節(jié)點 4,節(jié)點 9.

圖5 網(wǎng)絡(luò)分割后的仿真拓?fù)?/p>

2.2 性能評價指標(biāo)

簇頭節(jié)點(Cluster-head)成功調(diào)度的突發(fā)數(shù)據(jù)用 NB表示,用 SN表示光交換矩陣的開關(guān)次數(shù),定義光交換矩陣的交換效率 SW為:

阻塞率[13](Blocking Probability,BP):在給定的網(wǎng)絡(luò)拓?fù)浜蜆I(yè)務(wù)量需求情況下,沒有成功建立的業(yè)務(wù)連接請求數(shù)與總的業(yè)務(wù)連接請求數(shù)之比.阻塞率越小,說明被拒絕的業(yè)務(wù)請求越少,算法性能越好.

2.3 仿真結(jié)果分析

對于采用業(yè)務(wù)疏導(dǎo)的節(jié)點,無須為被疏導(dǎo)突發(fā)配置光交換矩陣,因此數(shù)據(jù)疏導(dǎo)成功的比例越高,光交換矩陣的交換效率也越高.

對于未采用疏導(dǎo)的節(jié)點,每成功傳輸一個數(shù)據(jù)突發(fā),光交換矩陣將開關(guān)一次,因此光交換矩陣的交換效率為 0.

簇頭節(jié)點 4(CH 4)的光交換矩陣在不同負(fù)載下的交換效率如圖6所示,其中節(jié)點 4的負(fù)載取 0～0.9最小間隔為 0.01的 17個不同值.圖6中,當(dāng)簇頭結(jié)點 4的負(fù)載等于 1.75時,光交換矩陣的交換效率達(dá)到最大值 0.27.

圖6 簇頭節(jié)點 4光交換矩陣交換效率示意圖

對于無時延突發(fā)疏導(dǎo),當(dāng)網(wǎng)絡(luò)負(fù)載較小時,數(shù)據(jù)突發(fā)之間的間隔較大,滿足疏導(dǎo)條件的數(shù)據(jù)突發(fā)(可疏導(dǎo)數(shù)據(jù))較少,從而成功疏導(dǎo)的數(shù)據(jù)較少,光交換矩陣的效率也較低;隨著網(wǎng)絡(luò)負(fù)載的增加,數(shù)據(jù)突發(fā)數(shù)量增多,相鄰數(shù)據(jù)突發(fā)之間的間隔減小,可疏導(dǎo)數(shù)據(jù)突發(fā)的數(shù)量隨之增加,從而簇頭節(jié)點能疏導(dǎo)更多的數(shù)據(jù)突發(fā),提升了光交換矩陣的交換效率.

當(dāng)網(wǎng)絡(luò)負(fù)載增大到一定程度時,雖然滿足疏導(dǎo)條件的突發(fā)數(shù)據(jù)數(shù)量繼續(xù)增加,但由于簇頭節(jié)點有限的波長信道資源,能被成功調(diào)度的數(shù)據(jù)比例必然減少,也降低了數(shù)據(jù)突發(fā)疏導(dǎo)成功的比例,此時簇頭節(jié)點的交換效率不會一直提升.圖6說明了這種情形.光交換矩陣的交換效率在簇頭節(jié)點 4的負(fù)載等于 1.75時達(dá)到最大值 0.27,隨著負(fù)載的增加,光交換矩陣的交換效率持續(xù)下降;當(dāng)負(fù)載增加到一定程度時,可疏導(dǎo)突發(fā)數(shù)量的增加對光交換矩陣交換效率的提升作用大于簇頭節(jié)點丟包率的增大對交換效率的降低作用,光交換矩陣的交換效率繼續(xù)提高.簇頭節(jié)點 4的負(fù)載從 0.4繼續(xù)增加,此時節(jié)點丟包率的增大對交換效率的降低作用大于可疏導(dǎo)突發(fā)數(shù)量的增加對光交換矩陣交換效率的提升作用,光交換矩陣的交換效率又重新降低.

圖7為核心節(jié)點采用業(yè)務(wù)疏導(dǎo)的網(wǎng)絡(luò)系統(tǒng)(TG)和沒有采用業(yè)務(wù)疏導(dǎo)算法的網(wǎng)絡(luò)系統(tǒng)(NTG)隨著網(wǎng)絡(luò)負(fù)載增加,數(shù)據(jù)包丟失概率的變化曲線.

圖7 數(shù)據(jù)包丟失概率曲線

當(dāng)網(wǎng)絡(luò)負(fù)載較低時,可疏導(dǎo)的數(shù)據(jù)突發(fā)較少,而節(jié)點有合適的信道資源調(diào)度數(shù)據(jù),所以兩者丟包率都維持在較低的數(shù)值;當(dāng)網(wǎng)絡(luò)負(fù)載增加時,數(shù)據(jù)突發(fā)的數(shù)量增加,節(jié)點可用的數(shù)據(jù)信道空隙長度減小,在相同的網(wǎng)絡(luò)負(fù)載下,采用業(yè)務(wù)疏導(dǎo)技術(shù)的系統(tǒng)丟包概率肯定低于未采用業(yè)務(wù)疏導(dǎo)技術(shù)的系統(tǒng)丟包概率.如圖7所示,當(dāng)網(wǎng)絡(luò)負(fù)載為 0.35～0.55時,采用業(yè)務(wù)疏導(dǎo)算法的丟包概率明顯小于未采用業(yè)務(wù)疏導(dǎo)技術(shù)的系統(tǒng)丟包概率.當(dāng)網(wǎng)絡(luò)增加到一定程度時,數(shù)據(jù)突發(fā)數(shù)量的增多,使得每個節(jié)點都沒有足夠的波長信道資源調(diào)度數(shù)據(jù)突發(fā),所以此時兩者的丟包率都維持在較高的數(shù)值.

3 結(jié)語

疏導(dǎo)策略設(shè)計是 NP-Hard問題,除了需要考慮諸多約束條件,還必須針對廣義網(wǎng)絡(luò)故障進(jìn)行相應(yīng)調(diào)整.本文提出的面向故障容忍機(jī)制的業(yè)務(wù)疏導(dǎo)算法(FAA),在圈發(fā)現(xiàn)算法基礎(chǔ)之上建立層次型網(wǎng)絡(luò)以對業(yè)務(wù)量進(jìn)行疏導(dǎo),經(jīng)仿真證明,該算法是一種有效的業(yè)務(wù)疏導(dǎo)算法.與已知算法相比,本文提出的算法既考慮了動態(tài)業(yè)務(wù)量疏導(dǎo)的復(fù)雜性,又考慮了網(wǎng)絡(luò)突發(fā)故障,對今后的工程開發(fā)具有指導(dǎo)意義.

[1]宋鴻升,吳耀輝,顧碗儀.多層網(wǎng)絡(luò)中的生存性策略[J].光通信技術(shù),2004(4):33-36.

[2]GerstelO,Ramaswami R.Optical layer survivability:a services perspective[J].IEEEComm.Mag.,2000,38(3):104-113.

[3]Bhatia R S,Kodialam M,Lakshman T V.Bandwidth guaranteed routing with fast restoration against link and node failures[J].IEEE/ACM Transactions on Networking,2008,16(6):1321-1330.

[4]何榮希,溫海波,王光興,等.WDM網(wǎng)狀網(wǎng)中基于共享風(fēng)險鏈路組限制的業(yè)務(wù)量疏導(dǎo)算法[J].電子與信息學(xué)報,2004,26(4):549-555.

[5]黃善國,羅沛,薄明霞,等.WDM網(wǎng)狀網(wǎng)中的動態(tài)流量疏導(dǎo)策略[J].北京郵電大學(xué)學(xué)報,2006,29(2):26-29.

[6]Chen B S,Rouskas G N,Dutta R.On hierarchical traffic grooming in WDM networks[J].IEEE/ACM Transactions on Networking,2008,16(6):1226-1238.

[7]Zhu K,Zhu H,Mukherjee B.Traffic engineering in multi-granularity heterogeneous optical WDM mesh networks through dynam ic traffic groom ing[J].IEEE/ACM Transactions on Network,2007,17(2):8-15.

[8]Zhu H,Zang H,Zhu K,et al.A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks[J].IEEE/ACM Transactions on Networking,2003,11(2):285-299.

[9]Zhu H,Zhu K,Zang H,et al.Cost-effective WDM backbone network design with OXCs of different bandwidth granularities.IEEE[J].Journal on Selected Areas in Communications,2003,21(9):1452-1466.

[10]Xin CS.Dynam ic traffic grooming in op tical networks with wavelength conversion[J].IEEE Journal on Selected Areas in Communications,2007,25(9):50-57.

[11]王汝言,常交法,隆克平,等.基于圈覆蓋的光突發(fā)交換網(wǎng)狀網(wǎng)故障監(jiān)測方案[J].北京郵電大學(xué)學(xué)報,2007,30(4):111-112.

[12]Zeng Hong-qing,Huang Chang-cheng,Vukovic A.Span-ning-tree based monitoring-cycle construction for fau lt detection and localization in mesh AONs[M].Proceedings of IEEE ICC'05.Seoul:IEEE Press,2005:1726-1730.

[13]溫海波.WDM網(wǎng)狀網(wǎng)中的業(yè)務(wù)量疏導(dǎo)算法[D].成都:電子科技大學(xué),2003:24-25.