李　泰，王興偉，李福亮，黃　敏

東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819

多約束多播業(yè)務(wù)量疏導(dǎo)機(jī)制*

李泰+，王興偉，李福亮，黃敏

東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819

為了使WDM（wavelength division multiplexing）光網(wǎng)絡(luò)中的波長(zhǎng)資源利用率達(dá)到最大化，提出了一種多約束多播業(yè)務(wù)量疏導(dǎo)機(jī)制。該機(jī)制在考慮光收發(fā)器數(shù)約束、波長(zhǎng)轉(zhuǎn)換能力約束以及分光量約束等多約束的前提下，結(jié)合多約束光樹建立算法，可以有效地完成WDM光網(wǎng)絡(luò)中多播業(yè)務(wù)量疏導(dǎo)的任務(wù)。對(duì)美國國家自然科學(xué)基金網(wǎng)NSFnet和歐洲教育科研網(wǎng)GEANT的拓?fù)溥M(jìn)行了仿真實(shí)現(xiàn)。性能分析表明，該疏導(dǎo)機(jī)制不僅能夠有效完成多播業(yè)務(wù)量疏導(dǎo)工作，而且與多跳疏導(dǎo)機(jī)制相比，具有較低的阻塞率。

光網(wǎng)絡(luò)；多播路由；多約束；光樹；業(yè)務(wù)量疏導(dǎo)

1　引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速進(jìn)步，互聯(lián)網(wǎng)業(yè)務(wù)與人們的生活結(jié)合得越來越緊密，如何提升網(wǎng)絡(luò)性能已經(jīng)成為目前人們最關(guān)心的問題[1]。WDM（wavelength division multiplexing）光網(wǎng)絡(luò)可以提供巨大的網(wǎng)絡(luò)帶寬，單波長(zhǎng)容量可以達(dá)到幾十甚至幾百G，單根光纖可以容納上千個(gè)波長(zhǎng)。為增加網(wǎng)絡(luò)的吞吐量，業(yè)務(wù)量疏導(dǎo)技術(shù)已經(jīng)成為WDM光網(wǎng)絡(luò)必備的基本功能[2]。另外，隨著視頻會(huì)議、網(wǎng)絡(luò)電視以及網(wǎng)絡(luò)游戲等多播應(yīng)用規(guī)模的不斷擴(kuò)大，多播業(yè)務(wù)量疏導(dǎo)問題已然成為當(dāng)前的研究熱點(diǎn)之一[3]。

在WDM光網(wǎng)絡(luò)中，業(yè)務(wù)量疏導(dǎo)可以分為動(dòng)態(tài)[4-6]和靜態(tài)[7-8]兩類。前者表示業(yè)務(wù)連接請(qǐng)求在疏導(dǎo)前沒有預(yù)先給定的情形，而后者表示業(yè)務(wù)連接請(qǐng)求在疏導(dǎo)前已經(jīng)預(yù)先給定的情形。文獻(xiàn)[9]提出了一種基于光樹的靜態(tài)多播業(yè)務(wù)量疏導(dǎo)算法，實(shí)現(xiàn)了網(wǎng)絡(luò)開銷的優(yōu)化，提高了波長(zhǎng)資源的利用率；文獻(xiàn)[10]提出了一種靜態(tài)業(yè)務(wù)量疏導(dǎo)問題的整數(shù)線性規(guī)劃模型，可以通過改變模型中的參數(shù)來實(shí)現(xiàn)不同的優(yōu)化目標(biāo)；文獻(xiàn)[11]研究了WDM網(wǎng)狀網(wǎng)中的多對(duì)多多播疏導(dǎo)問題；文獻(xiàn)[12]研究了基于單跳和多跳的動(dòng)態(tài)多播疏導(dǎo)算法；文獻(xiàn)[13]提出了一種基于跨層優(yōu)化的聯(lián)合路由疏導(dǎo)算法，可以在多粒度網(wǎng)絡(luò)中實(shí)現(xiàn)較高能效；文獻(xiàn)[14]提出了一種新的多粒度疏導(dǎo)算法，通過改變模型中的不同因子，可以提高WDM光網(wǎng)絡(luò)的業(yè)務(wù)疏導(dǎo)效率。

然而，當(dāng)前WDM光網(wǎng)絡(luò)中的大多數(shù)多播疏導(dǎo)算法只針對(duì)單約束的情況，而沒有考慮收發(fā)器數(shù)量、波長(zhǎng)轉(zhuǎn)換能力以及分光量等多約束的情況。在考慮收發(fā)器數(shù)量、波長(zhǎng)轉(zhuǎn)換能力和分光量等多約束的前提下，本文基于波長(zhǎng)分層的思想[15]，設(shè)計(jì)了多約束多播光樹建立算法（multi-constrained multicast light-tree establishing，MMLE）和多約束多播業(yè)務(wù)量疏導(dǎo)算法（multi-constrained multicast traffic grooming，MMT-G）。其中MMLE算法用于在MMTG算法中建立新光樹。MMTG算法與MMLE算法相結(jié)合，可以很好地完成WDM光網(wǎng)絡(luò)中業(yè)務(wù)量疏導(dǎo)的任務(wù)。

2　問題描述

已知的網(wǎng)絡(luò)物理拓?fù)浔硎緸镚p(V,L,W)，網(wǎng)絡(luò)中的節(jié)點(diǎn)集、物理鏈路集和每條物理鏈路中的波長(zhǎng)集分別表示為V、L、W。已知的多播路由請(qǐng)求表示為r(vs,D,br)，源節(jié)點(diǎn)表示為vs，目的節(jié)點(diǎn)集合表示為D，業(yè)務(wù)請(qǐng)求帶寬表示為br，其中vs,D∈V。

通過MMLE算法，為業(yè)務(wù)請(qǐng)求建立一個(gè)滿足光收發(fā)器數(shù)、波長(zhǎng)轉(zhuǎn)換能力以及分光量的多約束光樹集合，之后通過MMTG算法，用建立的光樹對(duì)業(yè)務(wù)請(qǐng)求進(jìn)行疏導(dǎo)。

2.1約束描述

2.1.1光收發(fā)器數(shù)約束

在對(duì)網(wǎng)絡(luò)中的業(yè)務(wù)進(jìn)行疏導(dǎo)的過程中，當(dāng)通過現(xiàn)有的邏輯鏈路無法找到到達(dá)目的節(jié)點(diǎn)的路由時(shí)，就需要建立新的光路。因?yàn)楣饴菲鹩谠垂?jié)點(diǎn)的光發(fā)送器，止于目的節(jié)點(diǎn)的光接收器，所以新建一條光路，源節(jié)點(diǎn)和目的節(jié)點(diǎn)的光發(fā)送器和光接收器數(shù)量需要分別減1。邏輯鏈路必須記錄當(dāng)前可用的光發(fā)送器和光接收器的數(shù)量。若源節(jié)點(diǎn)的光發(fā)送器數(shù)量不足，或目的節(jié)點(diǎn)的光接收器數(shù)量不足，便無法建立光路。

2.1.2波長(zhǎng)轉(zhuǎn)換能力約束

對(duì)于vi∈V的所有節(jié)點(diǎn)，r表示其波長(zhǎng)轉(zhuǎn)換范圍，增加從節(jié)點(diǎn)到節(jié)點(diǎn)的虛鏈路，將這種虛鏈路稱為波長(zhǎng)轉(zhuǎn)換鏈路，其中。

2.1.3波長(zhǎng)節(jié)點(diǎn)分光量約束

波長(zhǎng)節(jié)點(diǎn)分光量表示一個(gè)波長(zhǎng)節(jié)點(diǎn)當(dāng)前已經(jīng)使用的分光次數(shù)。舉例來說，如果一個(gè)光樹上的波長(zhǎng)節(jié)點(diǎn)作為目的節(jié)點(diǎn)，它的分光量應(yīng)為其子節(jié)點(diǎn)數(shù)加1，因?yàn)槟康墓?jié)點(diǎn)需要對(duì)業(yè)務(wù)數(shù)據(jù)流進(jìn)行一次備份；而當(dāng)一個(gè)波長(zhǎng)節(jié)點(diǎn)為非目的節(jié)點(diǎn)時(shí)，這個(gè)波長(zhǎng)節(jié)點(diǎn)的分光量即為其子節(jié)點(diǎn)的個(gè)數(shù)。

當(dāng)一個(gè)波長(zhǎng)節(jié)點(diǎn)的分光量尚未達(dá)到該節(jié)點(diǎn)最大的分光能力，且該波長(zhǎng)節(jié)點(diǎn)的上一跳不是波長(zhǎng)轉(zhuǎn)換鏈路時(shí)，本文將這種節(jié)點(diǎn)定義為MC（multicast capable）波長(zhǎng)節(jié)點(diǎn)。如圖1所示，圖中方形節(jié)點(diǎn)表示非目的節(jié)點(diǎn)，圓形節(jié)點(diǎn)表示目的節(jié)點(diǎn)，箭頭表示業(yè)務(wù)數(shù)據(jù)流在多播樹上的傳輸路徑。假設(shè)圖中節(jié)點(diǎn)均具有波長(zhǎng)轉(zhuǎn)換能力，v1節(jié)點(diǎn)最大分光能力為4次。初始波長(zhǎng)為λ2的光信號(hào)首先到達(dá)v1，并在v1處進(jìn)行3次分光，之后分別到達(dá)v2、v3、v4，光信號(hào)到達(dá)v2和v4后進(jìn)行波長(zhǎng)轉(zhuǎn)換，由λ2轉(zhuǎn)換為λ1。在這種情形下，的最大分光能力為4次，目前已經(jīng)進(jìn)行了3次分光，仍小于其最大分光能力，因此是MC波長(zhǎng)節(jié)點(diǎn)。而圖中不是MC波長(zhǎng)節(jié)點(diǎn)，因?yàn)樗纳弦惶鵀椴ㄩL(zhǎng)轉(zhuǎn)換鏈路。

Fig.1　MC wavelength node圖1　MC波長(zhǎng)節(jié)點(diǎn)

2.2鏈路代價(jià)

本文為波長(zhǎng)轉(zhuǎn)換鏈路、邏輯鏈路、接納鏈路和波長(zhǎng)鏈路的代價(jià)設(shè)置了不同的權(quán)值，分別表示為αwcl、αll、αal、αwll。不同的權(quán)值可以區(qū)分不同代價(jià)的優(yōu)先級(jí)，上述順序按權(quán)值的數(shù)量級(jí)降序排列，波長(zhǎng)轉(zhuǎn)換鏈路代價(jià)的權(quán)值最高，路由時(shí)便會(huì)傾向于選擇波長(zhǎng)轉(zhuǎn)換鏈路較少的路徑。選擇其他鏈路的情況以此類推，這樣就可以較好地實(shí)現(xiàn)負(fù)載均衡。

2.2.1波長(zhǎng)轉(zhuǎn)換鏈路

波長(zhǎng)轉(zhuǎn)換鏈路對(duì)網(wǎng)絡(luò)負(fù)載幾乎不產(chǎn)生影響，因?yàn)樗鼉H僅在波長(zhǎng)轉(zhuǎn)換時(shí)產(chǎn)生一定時(shí)延。波長(zhǎng)轉(zhuǎn)換鏈路的代價(jià)可表示為：

2.2.2邏輯鏈路

WDM層的每一條光路都對(duì)應(yīng)一條邏輯鏈路，二者的帶寬相同。本文中光路即邏輯鏈路。在實(shí)際情況下，業(yè)務(wù)的個(gè)數(shù)無法準(zhǔn)確反映邏輯鏈路的負(fù)載情況，因?yàn)椴煌瑯I(yè)務(wù)所請(qǐng)求的帶寬是不同的?？梢杂卯?dāng)前不可用帶寬（工作占用或保護(hù)占用）與光路總帶寬之比來表示邏輯鏈路的負(fù)載。這個(gè)比值越高，代表鏈路負(fù)載越重，這時(shí)需要為該鏈路設(shè)置相對(duì)高的代價(jià)，使得選路時(shí)盡量回避該鏈路；相反地，比值較低時(shí)，應(yīng)為該鏈路設(shè)置較小的代價(jià)。

邏輯鏈路的總帶寬、工作帶寬、保護(hù)帶寬分別表示為bt、bw、bp，用戶請(qǐng)求帶寬表示為br，則該邏輯鏈路的代價(jià)為：

2.2.3接納鏈路

接納鏈路與節(jié)點(diǎn)當(dāng)前剩余的光收發(fā)器數(shù)量有關(guān)。剩余的光收發(fā)器越少，接納鏈路的代價(jià)越高。對(duì)于同一個(gè)節(jié)點(diǎn)，光發(fā)送器和光接收器的使用情況顯然是不相關(guān)的。

節(jié)點(diǎn)的總發(fā)送器、總接收器、可用發(fā)送器和可用接收器的數(shù)量分別表示為tt、rt、ta、ra，則該節(jié)點(diǎn)作為源節(jié)點(diǎn)時(shí)的接納鏈路代價(jià)如下：

該節(jié)點(diǎn)作為目的節(jié)點(diǎn)時(shí)的接納鏈路代價(jià)如下：

2.2.4波長(zhǎng)鏈路

波長(zhǎng)鏈路的代價(jià)與該波長(zhǎng)鏈路所在的物理鏈路的使用情況有關(guān)。可以用當(dāng)前不可用波長(zhǎng)數(shù)量（工作占用或保護(hù)占用）與物理鏈路總波長(zhǎng)數(shù)之比來表示物理鏈路的負(fù)載。本文為波長(zhǎng)鏈路定義4種狀態(tài)：用于保護(hù)，用于構(gòu)建光路，用于構(gòu)建光樹，空閑。

若波長(zhǎng)鏈路的資源已被完全占用，則其代價(jià)為∞；否則工作波長(zhǎng)的數(shù)量表示為ww，保護(hù)波長(zhǎng)的數(shù)量表示為wp。波長(zhǎng)鏈路代價(jià)如下：

3　多約束多播光樹建立算法

在考慮光收發(fā)器數(shù)量、波長(zhǎng)轉(zhuǎn)換能力以及分光量等多約束的前提下進(jìn)行多播業(yè)務(wù)量疏導(dǎo)之前，必須先建立滿足以上約束的光樹集合。將這樣的光樹集合表示為F，當(dāng)前正在創(chuàng)建的光樹表示為T，其上的MC波長(zhǎng)節(jié)點(diǎn)表示為Vmc，目前尚未處理的目的節(jié)點(diǎn)表示為D*，與D*中的節(jié)點(diǎn)相對(duì)應(yīng)的邏輯節(jié)點(diǎn)表示為D′。算法描述如下：

4　多約束多播業(yè)務(wù)量疏導(dǎo)算法

本算法同時(shí)利用網(wǎng)絡(luò)中的光路和光樹對(duì)業(yè)務(wù)進(jìn)行疏導(dǎo)。對(duì)于網(wǎng)絡(luò)中現(xiàn)有的光樹與到來的業(yè)務(wù)請(qǐng)求，二者的目的節(jié)點(diǎn)集可能存在交集。當(dāng)交集元素個(gè)數(shù)達(dá)到一定數(shù)量時(shí)，便用該光樹進(jìn)行疏導(dǎo)；當(dāng)光樹的源節(jié)點(diǎn)與業(yè)務(wù)請(qǐng)求的源節(jié)點(diǎn)不同時(shí)，可以讓業(yè)務(wù)流從源節(jié)點(diǎn)先通過已有光路到達(dá)某一光樹的源節(jié)點(diǎn)，再用該光樹進(jìn)行疏導(dǎo)。

4.1疏導(dǎo)可用率

光樹中可疏導(dǎo)的目的節(jié)點(diǎn)數(shù)ngrooming即為光樹的目的節(jié)點(diǎn)集Vst與到來的業(yè)務(wù)請(qǐng)求的目的節(jié)點(diǎn)集D的交集：

疏導(dǎo)可用率rgrooming即為光樹中可疏導(dǎo)的目的節(jié)點(diǎn)數(shù)ngrooming與光樹中所有目的節(jié)點(diǎn)數(shù)||Vst之比：

4.2子樹

在一次業(yè)務(wù)量疏導(dǎo)過程中，業(yè)務(wù)流可能由若干光樹負(fù)責(zé)疏導(dǎo)，每棵光樹負(fù)責(zé)疏導(dǎo)業(yè)務(wù)請(qǐng)求的一部分目的節(jié)點(diǎn)，且每棵光樹所負(fù)責(zé)的目的節(jié)點(diǎn)集互不相交。若業(yè)務(wù)請(qǐng)求的源節(jié)點(diǎn)與現(xiàn)有光樹都不相同，則在當(dāng)前網(wǎng)絡(luò)中查找從業(yè)務(wù)請(qǐng)求源節(jié)點(diǎn)到現(xiàn)有光樹源節(jié)點(diǎn)的邏輯鏈路。若找到這樣的邏輯鏈路，則讓業(yè)務(wù)流先通過該邏輯鏈路到達(dá)光樹，再用該光樹進(jìn)行疏導(dǎo)；若網(wǎng)絡(luò)中不存在這樣的邏輯鏈路，則新建一棵滿足該業(yè)務(wù)請(qǐng)求的光樹。由于業(yè)務(wù)請(qǐng)求由若干光樹所承載，本文將承載業(yè)務(wù)請(qǐng)求的某一棵光樹稱為子樹。

本文將子樹的帶寬定義為3種狀態(tài)，分別為空閑、工作和保護(hù)。在一棵光樹中，只有源節(jié)點(diǎn)可以作為業(yè)務(wù)請(qǐng)求的接入點(diǎn)，其他節(jié)點(diǎn)或?yàn)槟康墓?jié)點(diǎn)，或只能作為中間節(jié)點(diǎn)。如果光樹的rgrooming比較低，可能會(huì)出現(xiàn)光樹中只有少部分鏈路承擔(dān)了業(yè)務(wù)量疏導(dǎo)的情況，而由于該光樹已使用，導(dǎo)致其空閑鏈路并不能用于疏導(dǎo)其他業(yè)務(wù)，從而導(dǎo)致該光樹的帶寬利用率偏低。

如圖2所示。假設(shè)業(yè)務(wù)請(qǐng)求的目的節(jié)點(diǎn)集為{v4,v5,v6,v7,v8}，網(wǎng)絡(luò)中某光樹的目的節(jié)點(diǎn)集為{v3,v4, v5}，{v4,v5}為目的節(jié)點(diǎn)交集，表示v4和v5可以利用該光樹進(jìn)行業(yè)務(wù)量疏導(dǎo)，rgrooming=66.7%。假設(shè)一條鏈路的帶寬為br，該次疏導(dǎo)過程中鏈路v2→v3空閑，而v2只能作為中間節(jié)點(diǎn)，不能接受其他業(yè)務(wù)量疏導(dǎo)任務(wù)，因此該光樹會(huì)有br的帶寬浪費(fèi)。為避免這種帶寬浪費(fèi)，最理想的情況是只有當(dāng)某光樹的rgrooming= 100%時(shí)才使用該光樹進(jìn)行疏導(dǎo)。但是，這樣會(huì)導(dǎo)致網(wǎng)絡(luò)中現(xiàn)有光樹被用于新業(yè)務(wù)疏導(dǎo)的概率偏低，大部分業(yè)務(wù)量疏導(dǎo)都是通過新建光樹完成的，使得波長(zhǎng)鏈路資源消耗迅速，最終導(dǎo)致業(yè)務(wù)阻塞。因此，為rgrooming設(shè)置一個(gè)閾值是必要的。

Fig.2　Usage of light-tree bandwidth resources圖2　光樹帶寬資源的使用

本文將rgrooming的閾值表示為Qgrooming，只有當(dāng)光樹的 rgrooming≥Qgrooming時(shí)，才使用該光樹進(jìn)行業(yè)務(wù)量疏導(dǎo)。為Qgrooming設(shè)置一個(gè)合理的值，可以在資源利用率和業(yè)務(wù)阻塞率之間尋求一個(gè)平衡點(diǎn)。

子樹的總帶寬、工作帶寬、保護(hù)帶寬分別表示為bt、bw、bp，業(yè)務(wù)請(qǐng)求帶寬表示為br，則該子樹的代價(jià)為：

4.3算法描述

當(dāng)前網(wǎng)絡(luò)中的光樹集表示為Ta，業(yè)務(wù)量疏導(dǎo)使用的光樹集表示為T，為業(yè)務(wù)量疏導(dǎo)創(chuàng)建的光樹集表示為Tnew；當(dāng)前網(wǎng)絡(luò)中的邏輯鏈路集表示為L(zhǎng)a，業(yè)務(wù)量疏導(dǎo)使用的邏輯鏈路集表示為L(zhǎng)，為業(yè)務(wù)量疏導(dǎo)創(chuàng)建的邏輯鏈路集表示為L(zhǎng)new；尚未疏導(dǎo)的目的節(jié)點(diǎn)集表示為D*。算法描述如下：

5　性能分析

本文基于美國國家自然科學(xué)基金網(wǎng)NSFnet對(duì)該多播業(yè)務(wù)量疏導(dǎo)機(jī)制進(jìn)行拓?fù)浞抡鎸?shí)現(xiàn)。假設(shè)多播請(qǐng)求服從Poisson分布，業(yè)務(wù)流持續(xù)時(shí)間服從指數(shù)分布，并假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的分光能力相同。αwcl、αll、αal、αwll取值分別為1、100、10 000、1 000 000，促使選路時(shí)優(yōu)先選擇使用波長(zhǎng)鏈路最少的路徑，其次選擇接納鏈路數(shù)較少的路徑，即使用光收發(fā)器數(shù)較少的路徑，以減少新建光路的數(shù)量。仿真參數(shù)如表1所示。

圖3和圖4表示MMTG算法和多跳疏導(dǎo)算法在自變量為業(yè)務(wù)強(qiáng)度，因變量為阻塞率的設(shè)定下的對(duì)比情況。仿真實(shí)驗(yàn)中，閾值Qgrooming設(shè)為0.01，光發(fā)送器和接收器的數(shù)量均設(shè)為16。實(shí)驗(yàn)結(jié)果表明，阻塞率會(huì)隨著業(yè)務(wù)強(qiáng)度的增加而升高。在多跳疏導(dǎo)算法中，業(yè)務(wù)請(qǐng)求的目的節(jié)點(diǎn)集與光樹目的節(jié)點(diǎn)集完全相同時(shí)才使用該光樹進(jìn)行業(yè)務(wù)量疏導(dǎo)，大部分疏導(dǎo)任務(wù)都是通過新建光樹的方式完成的，使得網(wǎng)絡(luò)中現(xiàn)有光樹的復(fù)用率很低，導(dǎo)致光樹的資源利用率較為低下。因此多跳疏導(dǎo)算法的阻塞率要高于MMTG算法。

Fig.3　Variation of blocking rate with traffic intensity on NSFnet圖3　NSFnet拓?fù)渖献枞孰S業(yè)務(wù)強(qiáng)度變化

Fig.4　Variation of blocking rate with traffic intensity on GEANT圖4　GEANT拓?fù)渖献枞孰S業(yè)務(wù)強(qiáng)度變化

圖5和圖6表示MMTG算法在自變量為疏導(dǎo)可用率，因變量為阻塞率的設(shè)定下的情況。仿真實(shí)驗(yàn)中，光發(fā)送器和光接收器的數(shù)量均設(shè)為16，業(yè)務(wù)強(qiáng)度設(shè)置為500。實(shí)驗(yàn)結(jié)果表明，隨著閾值Qgrooming的增加，阻塞率先減小到一個(gè)最低點(diǎn)，而后緩慢增大，在Qgrooming>0.8后迅速增大。若閾值Qgrooming設(shè)置得當(dāng)，MMTG算法可以提供較低的阻塞率，并在資源利用率和業(yè)務(wù)阻塞率之間達(dá)到很好的平衡；若閾值Qgrooming設(shè)置過高，則大部分業(yè)務(wù)量疏導(dǎo)是通過新建光樹的方式完成的，導(dǎo)致網(wǎng)絡(luò)帶寬資源大量消耗，進(jìn)而使得阻塞率迅速升高。

Fig.5　Variation of blocking rate with grooming usable rate on NSFnet圖5　NSFnet拓?fù)渖献枞孰S疏導(dǎo)可用率變化

Fig.6　Variation of blocking rate with grooming usable rate on GEANT圖6　GEANT拓?fù)渖献枞孰S疏導(dǎo)可用率變化

圖7和圖8表示MMTG算法和多跳疏導(dǎo)算法在自變量為光收發(fā)器數(shù)，因變量為阻塞率的設(shè)定下的對(duì)比情況。閾值Qgrooming設(shè)為0.01，業(yè)務(wù)強(qiáng)度設(shè)置為500。實(shí)驗(yàn)結(jié)果表明，MMTG算法和多跳疏導(dǎo)算法的阻塞率均隨光收發(fā)器數(shù)量增加而降低，MMTG算法阻塞率一直低于多跳疏導(dǎo)算法，多跳疏導(dǎo)阻塞率下降明顯。由于多跳疏導(dǎo)算法中，大部分疏導(dǎo)任務(wù)都是通過新建光樹的方式完成的，導(dǎo)致光發(fā)送器和接收器的大量消耗。MMTG算法阻塞率在光收發(fā)器數(shù)大于8時(shí)趨于穩(wěn)定，因?yàn)樗惴▽?duì)網(wǎng)絡(luò)中已有光樹的復(fù)用率較高，很少新建光樹，所以對(duì)光發(fā)送器和接收器數(shù)量要求不高，這時(shí)波長(zhǎng)資源為算法的主要約束。

Fig.7　Variation of blocking rate with optical transmitters and receivers on NSFnet圖7　NSFnet拓?fù)渖献枞孰S光收發(fā)器數(shù)變化

Fig.8　Variation of blocking rate with optical transmitters and receivers on GEANT圖8　GEANT拓?fù)渖献枞孰S光收發(fā)器數(shù)變化

綜上所述，MMTG算法相比于多跳疏導(dǎo)算法，在不同情況下均具有較低的阻塞率，能夠較好地完成多播業(yè)務(wù)量疏導(dǎo)的工作。

[1]Wang Xingwei,Sun Jiajia,Li Hongxing,et al.A reverse auction based allocation mechanism in the cloud computing environment[J].Applied Mathematics&Information Sciences, 2013,7(1):75-84.

[2]Ajaykumar S,Ghosh S K.Traffic grooming in optical WDM mesh networks[C]//Proceedings of the 2008 IEEE Region 10 and the 3rd International Conference on Industrial and Information Systems,Kharagpur,India,Dec 8-10,2008.Piscataway,USA:IEEE,2008:1-6.

[3]Lin Rongping,Zhong Wende,Bose S K,et al.Leaking strategy for multicast traffic grooming in WDM mesh networks [J].Journal of Lightwave Technology,2012,30(23):3709-3719.

[4]Farahmand F,Zhang Qiong,Jue J P.Dynamic traffic grooming in optical burst-switched networks[J].Journal of Lightwave Technology,2005,23(10):3167-3177.

[5]Srinivasan R,SomaniAK.Dynamic routing in WDM grooming networks[J].Photonic Network Communications,2003,5 (2):123-135.

[6]Thiagarajan S,Somani A K.Traffic grooming for survivable WDM mesh networks[J].Optical Networks Magazine, 2002,3(3):88-98.

[7]Zhu Keyao,Mukherjee B.Traffic grooming in an optical WDM mesh network[J].IEEE Journal on Selected Areas in Communications,2002,20(1):122-133.

[8]Zhu Hongyue,Zang Hui,Zhu Keyao,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]Lin Rongping,Zhong Wende,Bose S K,et al.Design of WDM networks with multicast traffic grooming[J].Journal of Lightwave Technology,2011,29(16):2337-2349.

[10]Jaekel A,Bari A,Chen Ying,et al.New techniques for efficient traffic grooming in WDM mesh networks[C]//Proceedings of the 16th International Conference on Computer Communications and Networks,Honolulu,USA,Aug 13-16,2007.Piscataway,USA:IEEE,2007:303-308.

[11]Saleh M A,Kamal A E.Design and provisioning of WDM networks with many-to-many traffic grooming[J].IEEE/ ACM Transactions on Networking,2010,18(6):1869-1882.

[12]Khalil A,Hadjiantonis A,Assi C M,et al.Dynamic provisioning of low-speed unicast/multicast traffic demands in meshbased WDM optical networks[J].Journal of Lightwave Technology,2006,24(2):681-693.

[13]Wang Xingwei,Cheng Hui,Li Keqin,et al.A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks[J].Journal of Parallel and Distributed Computing,2013,73(6):807-822.

[14]Wang Xingwei,Hou Weigang,Guo Lei,et al.A new multigranularity grooming algorithm based on traffic partition in IP over WDM networks[J].Computer Networks,2011,55 (3):807-821.

[15]Chen C,Banerjee S.A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks[C]//Proceedings of the 15th Annual Joint Conference of the IEEE Computer and Communications Societies,Networking the Next Generation,San Francisco, USA,Mar 24-28,1996.Piscataway,USA:IEEE,1996:164-171.

LI Tai was born in 1991.He is an M.S.candidate at Department of Computer Application Technology,Northeastern University.His research interest is Internet routing.

李泰（1991—），男，遼寧大連人，東北大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)系碩士研究生，主要研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)路由。

WANG Xingwei was born in 1968.He received the Ph.D.degree from Northeastern University in 1998.Now he is a professor and Ph.D.supervisor at Northeastern University,and the member of CCF.His research interests include cloud computing and future Internet,etc.

王興偉（1968—），男，遼寧沈陽人，1998年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樵朴?jì)算，未來互聯(lián)網(wǎng)等。

LI Fuliang was born in 1986.He received the Ph.D.degree from Tsinghua University in 2015.Now he is a lecturer at Northeastern University.His research interests include next generation Internet and network security,etc.

李福亮（1986—），男，遼寧葫蘆島人，2015年于清華大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)講師，主要研究領(lǐng)域?yàn)橄乱淮ヂ?lián)網(wǎng)，網(wǎng)絡(luò)安全等。

HUANG Min was born in 1968.She received the Ph.D.degree in control theory from Northeastern University in 1999.Now she is a professor and Ph.D.supervisor at Northeastern University.Her research interests include modeling and optimization for logistics and supply chain system,etc.

黃敏（1968—），女，遼寧沈陽人，1999年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槲锪髋c供應(yīng)鏈管理，智能算法設(shè)計(jì)與優(yōu)化等。

Multi-Constrained Multicast Traffic Grooming Mechanism*

LI Tai+,WANG Xingwei,LI Fuliang,HUANG Min
College of Information Science and Engineering,Northeastern University,Shenyang 110819,China

E-mail:nfsfan@126.com

In order to fully utilize the wavelength resources of the WDM(wavelength division multiplexing)optical networks,this paper proposes a multi-constrained multicast traffic grooming mechanism.According to a multi-constrained multicast light-tree establishing algorithm,this mechanism provides an effective solution to multicast traffic grooming in WDM optical networks under multi-constraints,including the number of optical transceivers,wavelength conversion capability and wavelength splitting capability.This paper evaluates the proposed traffic grooming mechanism based on the topology of the National Science Foundation Network of USA(NSFnet)and Pan-European Research and Education Network(GEANT).The simulation results show that the proposed mechanism can not only accomplish multicast traffic grooming effectively,but also gain a lower blocking proportion compared with the multihop traffic grooming mechanism.

optical networks;multicast routing;multi-constrained;light-tree;traffic grooming

2015-08,Accepted 2015-10.

10.3778/j.issn.1673-9418.1509096

A

TP393

*The National Natural Science Foundation of China under Grant Nos.61572123,61502092(國家自然科學(xué)基金);the National Science Foundation for Distinguished Young Scholars of China under Grant Nos.61225012,71325002(國家杰出青年科學(xué)基金);the Specialized Research Fund of the Doctoral Program of Higher Education of China for the Priority Development Areas under Grant No.20120042130003(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金優(yōu)先發(fā)展領(lǐng)域資助課題).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-29,http://www.cnki.net/kcms/detail/11.5602.TP.20151029.1705.004.html

LI Tai,WANG Xingwei,LI Fuliang,et al.Multi-constrained multicast traffic grooming mechanism.Journal of Frontiers of Computer Science and Technology,2016,10(10)：1398-1406.