彈性光網(wǎng)絡(luò)中多播業(yè)務(wù)負(fù)載均衡的研究

張建芳 楊 陽 郝 娟

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

1 引 言

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

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

2 問題描述

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

與傳統(tǒng)的點(diǎn)到點(diǎn)通信方式相比，多播是一種有效利用現(xiàn)有帶寬的技術(shù)，如視頻會(huì)議，遠(yuǎn)程教學(xué)等帶寬密集型業(yè)務(wù).多播不僅可以高效率的傳輸業(yè)務(wù)，也可以節(jié)省頻譜資源，但是隨著網(wǎng)絡(luò)業(yè)務(wù)需求的急速增加，出現(xiàn)越來越多的業(yè)務(wù)阻塞問題，或許只是工作路徑上某段鏈路頻譜資源不足就造成整個(gè)多播業(yè)務(wù)請(qǐng)求失敗.由此可見，頻譜資源的合理利用和負(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)過不同路由進(jìn)行傳輸，最終在接收端將子帶整合成連續(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)，因?yàn)樾枰垂?jié)點(diǎn)和接收點(diǎn)的節(jié)點(diǎn)度(節(jié)點(diǎn)度是指和該節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，又稱關(guān)聯(lián)度)至少為2，才能找到至少兩條鏈路不相交的路由來承載子帶的傳輸.

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

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

圖2.3 子帶分割方法

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

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

2.2 算法具體流程

基于網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)的分子帶多播路由算法的核心思想是將請(qǐng)求的帶寬資源分為若干子帶在不同路由上傳輸，在目的節(jié)點(diǎn)將子帶資源重組.因此首先要解決的問題是為每一對(duì)節(jié)點(diǎn)對(duì)找到不同的路由.本文采用改進(jìn)的迪杰斯特拉Dijkstra最短路徑算法，該算法實(shí)質(zhì)是為每對(duì)節(jié)點(diǎn)對(duì)根據(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é)點(diǎn)定義為ni,i=1,2,3…兩個(gè)節(jié)點(diǎn)間的鏈路定義為lni,nj,i=1,2,3…，j=1,2,3,…i≠j兩節(jié)點(diǎn)間鏈路距離為h(lni,nj)，權(quán)重為w(ni,nj)=[h(lni,nj)%10].定義兩個(gè)節(jié)點(diǎn)集合P，Q.

改進(jìn)的Dijkstra最短路徑算法如下：

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

圖2.4 節(jié)點(diǎn)對(duì)遍歷方式

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

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

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

步驟5 恢復(fù)初始拓?fù)?，令j=j+1重復(fù)步驟3-5為節(jié)點(diǎn)對(duì)n1與n3，n1與nk的節(jié)點(diǎn)(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é)點(diǎn)對(duì)的全部路徑被找到.

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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