WDM疏导网络中一种新的多播业务路由算法

光 电 子 ·激 光
J ou r n a l o f O p t oel ect r oni cs ·L ase r 第 18 卷 第 2 期 2007 年 2 月 Vol . 18 No . 2 Feb. 2007
3
WDM 疏导网络中一种新的多播业务路由算法
3

廖露华
1 3 3
, 温海波
2
, 王 晟
1
, 李乐民
1

(1. 电子科技大学宽带光纤传输与通信系统技术重点实验室 ,四川 成都 610054 ; 2. 上海贝尔阿尔卡特创新研究
中心 ,上海 201206)
摘要 :研究了波分复用(WDM) 网状网中动态多播业务量疏导 ,提出一种新的辅助疏导模型 ,其可以描述当前网
络资源状况和节点分光特点 ,并动态更新。进而提出一种有效的多播业务量疏导启发式算法(M GA) ,将业务的
多播选路和波长分配同时完成。仿真表明 ,该算法在波长连续性限制、网络波长和节点收发器数目有限的情况
下 ,具有较低网络阻塞率。
关键词 :波分复用(WDM) ; 多播路由 ; 业务量疏导 ; 辅助疏导模型
中图分类号 : TN929. 11 文献标识码 :A 文章编号 :100520086 (2007) 0220200204
A Novel Multicast Routing Algorithm f or WDM Groomed Net works

L IAO L u2hua
1 3 3
, WEN Hai2bo
2
, WAN G Sheng
1
, L I Le2min
1

(1. Key Lab. of Broadband Optical Fiber Transmission & Communication Netwroks , U ESTC , Chengdu 610054 ,
China ; 2. Research and Innovation Center ,Alcatel Shanghai Bell ,Shanghai 201206 ,China)
Abstract : This paper st udies t he dynamic multicast t raffic grooming problem and proposes a novel auxiliary grooming model .
The layered graph model can represent current network resource states and is modified adaptively. On t his grooming graph
model ,multicast routing and wavelengt h assignment can be realized at t he same time. We propose a multicast t raffic groo2
ming algorit hm( MGA) ,and t he simulations show it has lower network blocking probability under t he const raint s of wave2
lengt h continuity and limited wavelengt h and t ransceiver resources.
Key words :wavelengt h division multiplexing (WDM) ; multicast routing ; t raffic grooming ; auxiliary grooming model
集; L 是链路集 , 每条链路由 1 对方向相反的单向光纤组
成; W 为每根光纤支持的可用波长集。假设节点具有足够
的多播分光能力 , 无波长变换能力。节点具有疏导能力并
配备一定数目的光收发器 , 且假设光收发器可调谐到光纤
链路所支持的任意波长上。网络中节点数、链路数、波长数
和节点光收发器数目分别用| N | 、| L | 、| W | 、| T x | 和| R x |
表示。每条链路赋予一正权值 , 表示使用该条链路疏导业
务所需的代价。多播业务请求 r ( s , D , b ,Δ T) 动态随机地到
达和离开 , 其中 s ∈N 是源节点; D < N 是目的节点集合; b
是业务请求带宽;Δ T 是业务服务持续时间。WDM 网络
中 ,动态多播业务量疏导是根据当前网络资源状况 ,动态为
新到达的多播请求业务寻找可供该业务疏导的最优 ( 总代
价最小) 多播树路由 ,实现业务从源节点到所有目的节点的
传递。寻找疏导多播树有一些约束条件 ,如带宽大小、波长
连续性和光收发器数目等。若不能找到恰当路径 , 该业务
请求被阻塞。动态多播业务量疏导的目标就是降低业务阻
塞率 ,提高网络的吞吐量。
1 引 言

波分复用( WDM) 网络中 ,每个波长可能提供高达 Gbit
的传输容量 , 但实际很多业务请求都小于 1 个波长粒度。
为每个这样的业务请求分配单独的波长通道 ,资源利用率
低 ;甚至由于网络中波长链路和节点光收发器数目的限制 ,
不可能为每个低速业务请求建立连接。所以 ,有必要进行
业务量疏导( t raffic groo mi ng)
[ 1 ]
。过去 ,主要针对 WDM 环
网和网状网中单播业务量疏导问题进行探讨
[ 1～5 ]
。目前 ,
WDM 网络中多播业务量疏导开始受到关注 ,文献[ 6 ,7 ] 给
出该问题的 IL P 描述 , 旨在减少疏导所需的波长数目或
ADM 数目。因为 IL P 描述只适合小规模网络计算 , 文献
[ 8 ,9 ]讨论了多播业务量疏导方案 ,但均未考虑节点收发器
的限制。本文研究动态环境下 WDM 网络中多播业务量
的疏导 , 提出一种新的基于辅助疏导模型的有效启发式
算法。
2 问题描述

给定网络物理拓扑 Gp ( N , L , W ) , 其中 N 是网络节点
3 收稿日期 :2006204210 修订日期 :2006206223
3 基金项目 :国家自然科学基金资助项目(60472008) ;四川省青年科技基金资助项目(05ZQ0262002)
3 3 E2mail :liaoluhua @uestc. edu. cn