王 冕,劉成耀

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

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

1 問(wèn)題描述

1.1 探測(cè)圈覆蓋

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

圖1 探測(cè)圈覆蓋示例圖

任何無(wú)橋連通圖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ā)式生成樹(shù)圈覆蓋算法(HST).本文擬采用啟發(fā)式生成樹(shù)圈覆蓋算法(HST),如圖2.

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

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

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

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

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

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

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

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

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

2.2 性能評(píng)價(jià)指標(biāo)

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

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

2.3 仿真結(jié)果分析

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

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

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

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

對(duì)于無(wú)時(shí)延突發(fā)疏導(dǎo),當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí),數(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é)點(diǎn)能疏導(dǎo)更多的數(shù)據(jù)突發(fā),提升了光交換矩陣的交換效率.

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

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

3 結(jié)語(yǔ)

疏導(dǎo)策略設(shè)計(jì)是 NP-Hard問(wèn)題,除了需要考慮諸多約束條件,還必須針對(duì)廣義網(wǎng)絡(luò)故障進(jìn)行相應(yīng)調(diào)整.本文提出的面向故障容忍機(jī)制的業(yè)務(wù)疏導(dǎo)算法(FAA),在圈發(fā)現(xiàn)算法基礎(chǔ)之上建立層次型網(wǎng)絡(luò)以對(duì)業(yè)務(wù)量進(jìn)行疏導(dǎo),經(jīng)仿真證明,該算法是一種有效的業(yè)務(wù)疏導(dǎo)算法.與已知算法相比,本文提出的算法既考慮了動(dòng)態(tài)業(yè)務(wù)量疏導(dǎo)的復(fù)雜性,又考慮了網(wǎng)絡(luò)突發(fā)故障,對(duì)今后的工程開(kāi)發(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)險(xiǎn)鏈路組限制的業(yè)務(wù)量疏導(dǎo)算法[J].電子與信息學(xué)報(bào),2004,26(4):549-555.

[5]黃善國(guó),羅沛,薄明霞,等.WDM網(wǎng)狀網(wǎng)中的動(dòng)態(tài)流量疏導(dǎo)策略[J].北京郵電大學(xué)學(xué)報(bào),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)測(cè)方案[J].北京郵電大學(xué)學(xué)報(bào),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.