張建芳 楊 陽 郝 娟

(河北建筑工程學(xué)院 信息工程學(xué)院，河北 張家口 075000)

1 引 言

隨著信息技術(shù)及互聯(lián)網(wǎng)的飛速發(fā)展，資源的利用成為必不可少的研究課題，盡管傳統(tǒng)的波分復(fù)用(WDM)網(wǎng)絡(luò)有很多優(yōu)勢，但WDM網(wǎng)絡(luò)缺點也比較明顯.WDM網(wǎng)絡(luò)是固定柵格，對于各種速率的業(yè)務(wù)，波分復(fù)用網(wǎng)絡(luò)需要將整個波長分配給連接，即使有的業(yè)務(wù)連接請求并不需要如此大的帶寬，這就造成了頻譜利用率降低，此外，波分復(fù)用可擴展性很低，因此基于正交頻分復(fù)用(orthogonal frequency division multiplexing，OFDM)的彈性光網(wǎng)絡(luò)應(yīng)用而生.彈性光網(wǎng)絡(luò)可以提供更細(xì)的頻譜粒度并且在分配調(diào)制格式時采用距離自適應(yīng)調(diào)制格式，不僅實現(xiàn)了頻譜的高效利用也可以在一定程度上節(jié)省頻譜資源.隨著光網(wǎng)絡(luò)向著靈活柵格方向發(fā)展，網(wǎng)絡(luò)資源的實體由波長向著頻譜轉(zhuǎn)變.使得資源管理與調(diào)控問題的復(fù)雜性提高，路由計算和頻譜資源的分配策略則變得復(fù)雜多樣.

與傳統(tǒng)的點到點通信方式相比，多播是一種有效利用現(xiàn)有帶寬的技術(shù)，如視頻會議，遠(yuǎn)程教學(xué)等帶寬密集型業(yè)務(wù).多播可以高效率的完成業(yè)務(wù)的傳送，并且可以節(jié)約大量的頻譜資源，但是隨著網(wǎng)絡(luò)業(yè)務(wù)需求的急速增加，出現(xiàn)越來越多的業(yè)務(wù)阻塞問題，或許只是工作路徑上某段鏈路頻譜資源不足就造成整個多播業(yè)務(wù)請求失敗.由此可見，頻譜資源的合理利用和負(fù)載均衡就變得尤為重要.

2 問題描述

彈性光網(wǎng)絡(luò)提供了更細(xì)的頻譜粒度和距離自適應(yīng)調(diào)制格式，可以實現(xiàn)頻譜的有效分配.隨著光網(wǎng)絡(luò)向著靈活柵格方向發(fā)展，網(wǎng)絡(luò)資源的實體由波長向著頻譜轉(zhuǎn)變，使得資源管理與調(diào)控問題的復(fù)雜性提高，路由計算和頻譜資源的分配策略則變得復(fù)雜多樣.

與傳統(tǒng)的點到點通信方式相比，多播是一種有效利用現(xiàn)有帶寬的技術(shù)，如視頻會議，遠(yuǎn)程教學(xué)等帶寬密集型業(yè)務(wù).多播不僅可以高效率的傳輸業(yè)務(wù)，也可以節(jié)省頻譜資源，但是隨著網(wǎng)絡(luò)業(yè)務(wù)需求的急速增加，出現(xiàn)越來越多的業(yè)務(wù)阻塞問題，或許只是工作路徑上某段鏈路頻譜資源不足就造成整個多播業(yè)務(wù)請求失敗.由此可見，頻譜資源的合理利用和負(fù)載均衡就變得尤為重要.

(a)樹形網(wǎng)絡(luò)結(jié)構(gòu) (b)網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)

在彈性光網(wǎng)絡(luò)中，現(xiàn)有的研究都是基于頻譜連續(xù)的業(yè)務(wù)傳輸方式，為了更好的利用頻譜資源，降低業(yè)務(wù)阻塞率，本節(jié)提出分子帶多播路由算法，該算法的核心思想是在頻譜領(lǐng)域?qū)⑦B續(xù)頻譜槽分成若干子帶在相干光OFDM光通道經(jīng)過不同路由進行傳輸，最終在接收端將子帶整合成連續(xù)頻譜.

2.1 基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法

彈性光網(wǎng)絡(luò)中常見的網(wǎng)絡(luò)有樹形和網(wǎng)狀網(wǎng)結(jié)構(gòu)如圖2.1，該算法適應(yīng)于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)，因為需要源節(jié)點和接收點的節(jié)點度(節(jié)點度是指和該節(jié)點相關(guān)聯(lián)的邊的條數(shù)，又稱關(guān)聯(lián)度)至少為2，才能找到至少兩條鏈路不相交的路由來承載子帶的傳輸.

(a)網(wǎng)絡(luò)拓?fù)鋱D (b)多播請求及當(dāng)前頻譜狀態(tài) (c)子帶傳輸

如圖2.2，網(wǎng)絡(luò)拓?fù)淙鐖D2.2(a)，多播請求及當(dāng)前頻譜資源占用狀態(tài)如圖2.2(b)，多播請求為r=(a,{g,i,f}).請求的源節(jié)點為a，目的節(jié)點為g,i,f，多播請求的帶寬為280Gb/s.選用Segment-based multicast tree algorithm為多播請求選路.

圖2.3 子帶分割方法

首先根據(jù)源-目的節(jié)點的最遠(yuǎn)距離確定調(diào)制格式，最遠(yuǎn)距離為a-e-g1100Km，自適應(yīng)調(diào)制格式為8QAM，需要4個頻譜槽承載業(yè)務(wù).由當(dāng)前的多播工作路徑頻譜狀態(tài)可知，鏈路a-e上的頻譜資源不足4個頻譜槽，因此該多播業(yè)務(wù)將會阻塞，此時利用基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法將所需的帶寬分成若干個子帶在鏈路不相交的不同路由上進行信息傳輸，在目的節(jié)點處將所有子帶頻譜重組即可.每個子帶的連續(xù)頻譜槽個數(shù)有多種分割方法如圖2.3，要依據(jù)當(dāng)前的頻譜使用狀態(tài)決定，為了降低算法復(fù)雜度，本文選用同種粒度的子帶.

本例將4個頻譜槽的帶寬分成兩個子帶，子帶1包含兩個頻譜槽，子帶2包含兩個頻譜槽.如圖2.2(c)，在多播工作路徑上占用頻譜槽6-7傳送子帶1.在與工作路鏈路不相交的a-b-g-i和a-c-f上傳送子帶2，最后在目的節(jié)點g、i、f將子帶1和子帶2的頻譜信息進行重組，基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法不僅降低了網(wǎng)絡(luò)阻塞率，也實現(xiàn)了網(wǎng)絡(luò)的負(fù)載均衡.

2.2 算法具體流程

基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法的核心思想是將請求的帶寬資源分為若干子帶在不同路由上傳輸，在目的節(jié)點將子帶資源重組.因此首先要解決的問題是為每一對節(jié)點對找到不同的路由.本文采用改進的迪杰斯特拉Dijkstra最短路徑算法，該算法實質(zhì)是為每對節(jié)點對根據(jù)鏈路權(quán)重找到所有鏈路不相交的路徑，從而為子帶路由提供多種選擇，也可以平衡網(wǎng)絡(luò)負(fù)載.

定義鏈路權(quán)重w，鏈路距離為h(km)，[x]為不小于x的最小整數(shù)，則鏈路權(quán)重定義為式(1).

W=[h%10]

(1)

網(wǎng)絡(luò)節(jié)點定義為ni,i=1,2,3…兩個節(jié)點間的鏈路定義為lni,nj,i=1,2,3…，j=1,2,3,…i≠j兩節(jié)點間鏈路距離為h(lni,nj)，權(quán)重為w(ni,nj)=[h(lni,nj)%10].定義兩個節(jié)點集合P，Q.

改進的Dijkstra最短路徑算法如下：

步驟1 首先令集合P={n1}，集合Q={n2,n3,n4…}.

圖2.4 節(jié)點對遍歷方式

步驟2 圖2.4為節(jié)點對的遍歷方式.首先令i=1,j=2.

步驟3 將ni和nj作為節(jié)點對(i,j)，根據(jù)式(2.1)為所有鏈路計算鏈路權(quán)重，找到節(jié)點對(i,j)之間鏈路權(quán)重加和最小的路徑.

步驟4 將步驟3中找到的路徑從拓?fù)鋱D中刪除，更新拓?fù)鋱D，并將該路徑加入節(jié)點對(i,j)的路徑列表中.從更新的拓?fù)鋱D中繼續(xù)找出權(quán)重和最小的鏈路，從拓?fù)鋱D刪除，并將該路徑加入節(jié)點(i,j)的路徑列表中.重復(fù)以上步驟，直到節(jié)點對(i,j)間的全部鏈路不相交路徑全部添加到節(jié)點對(i,j)的路徑列表中.

步驟5 恢復(fù)初始拓?fù)?，令j=j+1重復(fù)步驟3-5為節(jié)點對n1與n3，n1與nk的節(jié)點(1,3)…(1,k)更新路徑列表.

步驟6 如圖2.4將n1從集合P中刪除，n2從集合Q中移到集合P，即P={n2}，Q={n3,n4…}，然后令i=i+1，j=j+2重復(fù)步驟3-5直到所有節(jié)點對的全部路徑被找到.

對于基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法，核心思想是將請求的帶寬資源分為若干子帶在不同路由上傳輸，定義每個子帶的頻譜槽個數(shù)相同的子帶為SUB-F(x)，其中x為子帶的連續(xù)頻譜槽個數(shù).若多播請求需求的頻譜槽個數(shù)為k，則需要k/x個子帶，需求的子帶個數(shù)為整數(shù)，所以對結(jié)果取不小于k/x的最小整數(shù)即[k/x].本節(jié)研究的內(nèi)容是基于同種粒度的，即每個子帶的頻譜槽個數(shù)相同.當(dāng)然子帶的粒度是可以不同的，如將5個頻譜槽分為子帶1包含3個頻譜槽，子帶2包含2個頻譜槽，這種子帶的分割方法將會增加算法復(fù)雜度，因此不同粒度的子帶分割將在未來研究.

基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法如下：

輸入：彈性光網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)銰(V,E)，多播請求r=(sr,Dr,Cr).

輸出：彈性光網(wǎng)絡(luò)中多播業(yè)務(wù)請求的工作路徑以及它們的頻譜分配.

步驟1 檢測當(dāng)前網(wǎng)絡(luò)頻譜資源使用狀態(tài).

步驟2 利用Segment-based multicast tree algorithm為多播請求尋找工作路徑.

步驟3 檢測當(dāng)前多播工作路徑的鏈路上是否有足夠頻譜資源滿足多播需求的帶寬.若剩余頻譜資源充足，則該多播請求選路成功.若工作路徑經(jīng)過的某條鏈路頻譜資源不足，則跳到步驟4.

步驟4 確定工作路徑所經(jīng)過的所有鏈路，找到鏈路剩余頻譜槽最少的數(shù)目，將該數(shù)目定義為j.則子帶為SUB-F(j)，本文采用同種粒度的子帶傳輸方式，若多播請求需求的頻譜槽個數(shù)為k，需要的子帶個數(shù)為[k/j].

步驟5 運行改進的Dijkstra算法，找到相關(guān)源目的節(jié)點對的鏈路不相交的路徑列表.該列表是按權(quán)重和從小到大排列的，從列表中依次選取[k/j]條路徑承載子帶業(yè)務(wù).在目的節(jié)點將子帶業(yè)務(wù)重組即可完成多播請求.

3 結(jié)束語

論文針對彈性光網(wǎng)絡(luò)中的多播路由及負(fù)載均衡問題進行了研究.為了更好的提高頻譜利用率，降低網(wǎng)絡(luò)阻塞率，本文將重點放在路由選擇及頻譜資源的分配調(diào)度上，采用基于網(wǎng)狀網(wǎng)絡(luò)的分子帶多播路由算法解決頻譜資源有限時利用足夠光收發(fā)器解決多播業(yè)務(wù)請求阻塞以及頻譜的利用率問題，所提算法通過改變信號調(diào)制格式，靈活運用鏈路上的頻譜碎片，可以有效降低網(wǎng)絡(luò)的阻塞率，提高網(wǎng)絡(luò)的頻譜利用率.