WDM全光网中的多播路由算法研究

[ 1 ]
WDM 全光网中的多播路由算法研究


(嘉兴学院信息工程学院 , 浙江嘉兴 314001 )
邓 昶 , 刘小晶 , 龚迅炜
摘 要 : 研究了 WDM 全光网中多播路由的问题 , 并给出一种满足时延约束的多播路由与波长分配算法 ,
此算法是在 Ch lam tac
[ 2 ]
等人提出的波长图的基础上 , 将路由与波长分配统一进行 , 构造了时延受限低代价多
播树 , 克服了将寻径和波长分配分步进行的弊端 , 具有较低的时间复杂度 , 避免了同类算法的较高复杂性 。
关键词 : WDM (波分复用 ) ; 多播路由 ; 时延受限 中图分类号 : TN929111
The M u lt ica st Rou t in g A lgor ithm in W DM O p t ica l Ne twork s
D EN G Chang, L IU X iao - jing, GON G Xun - we i
( Schoo l of Info rm a tion Enginee ring, J iaxing U n ive rstiy, J iaxing, Zhe jiang 341001 )
A b stra c t: Th is a rtic le stud ie s the que stion of M u ltica st Rou te in the WDM a ll - op tica l ne two rk s, and a rou ting
and wave length a ssignm en t in WDM a ll - op tica l ne two rk s is p re sen ted. B a sed on the wave length grap h tha t Ch lam tac
p re sen ts, th is a lgo rithm dea ls w ith rou ting and wave length a ssignm en t a s a un ified p roce ss, con struc ts a m in im a l co st
m u ltica sting tree sa tisfying de lay bound con stra in t. Mo reove r, the a lgo rithm avo id s h igh comp lexity common to mo st de2
lay - con stra ined heu ristic s.
Key word s: WDM ; M u ltica st Rou ting; Ste ine r Tree D e lay Con stra in ts
文献标识码 : A1 文章编号 : 1008 - 6781 ( 2007 ) 03 - 0064 - 04
0 前言
多播 (M u ltica st) 是一种允许同时向多个目的的主机传送信息的通信方式。当今随着计算机网络
技术的发展 , 多播技术是多媒体应用的关键技术。许多分布式实时应用如远程教育、视频会议、分布
式数据库更新等均涉及多个参与者 , 不仅要求有严格的时延限制 , 还需要大量的数据资源 , 为了有效
地支持和实现这些应用 , 网络在满足这些应用服务请求的同时 , 应尽可能地降低资源消耗 , 这就是网
络上称为具有约束限制的多播路由算法问题 。随着光纤技术中 WDM 技术的发展和多播应用的日益流
行 , 使得数据的传输速率空前提高 , 从而在 WDM 层支持多播路由成为一个重要而又具有挑战性的
课题。
[ 3 - 5 ]
1 问题的提出
WDM 全光网络的物理拓扑结构可以形式化为一个赋权有向图 G (V , E, Λ , N ) ,
[ 6 - 7 ]
其中 V 表
示物理节点 (路由器 ) 集合 , | V | = n; E 表示由一对方向相反的单向光纤构成的双向链路的集
合 ; Λ 表示光纤上的可用波长的集合 , 其中包括 k 个波长 , 可用波长集合记为 Λ = {λ
1
,λ
2
, ,λ
n
} ;
N 表示物理节点中具有波长转换能力的结点集合 ; D = { d
1
, d
2
, , d
m
}表示多播目的节点的集合 。
在图 G (V , E,Λ , N )的每条链路 e = ( i, j) ∈E上定义了两个非负数 , 链路代价 C ( e) > 0 , 可以包
括价格、距离、带宽占用量等 ; 链路时延 D ( e) > 0 , 链路时延为数据包经过链路的度量 , 包括排队、
发送和传输时延等。假定每个节点具有无限光信号分裂能力 , 即任一输入光信号可以被分裂成多个光
信号 , 并在相应链路上输出。网络中有给定数量的波长转换器分布在给定节点上 , 每个波长转换器能
收稿日期 : 2005 - 12 - 011
作者简介 :邓昶 ( 1963 - ) ,男 ,江西南城人 , 嘉兴学院信息工程学院副教授 ,研究方向为信息系统与计算机网络。