WDM网络中满足延迟和延迟差约束的分布式组播路由与波长分配算法  

A Distributed Routing and Wavelength Assignment Algorithm Satisfying Delay and Delay Variation Bound for Multicast in WDM Networks

作　　者：黄传河[1] 陈莘萌[1] 贾小华[1] 张文涛[1] 

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机工程与应用》2003年第22期168-173,共6页Computer Engineering and Applications

摘　　要：在WDM网络中,由于每条链路上可用波长是动态变化的,在考虑波长转换延迟时间的条件下,实现实时组播连接的路由与波长分配是十分困难的。论文提出了一种用于建立满足延迟时限和延迟差要求的实时组播连接的分布式路由与波长分配算法。该算法假定每个节点没有全局路由信息,只根据关联链路的信息进行路由选择,且将路由与波长分配统一进行。组播路由算法以Prim最小生成树算法为基础,生成一棵满足给定延迟时限的最小成本树。对不满足延迟时限的目的节点,通过增加回路边构造回路再消除长延迟路径的方式,加入到组播树中。对不满足延迟差的目的节点,采用重构Steiner树的方法,使其满足延迟差的要求。波长分配使用最少波长转换和负载平衡策略。Routing and wavelength assignment for online real-time multicast connection setup is difficult due to the dynamic change of availabilities of wavelengths on links and the consideration of wavelength conversion delay in WDM networks.This paper presents a distributed routing and wavelength assignment algorithm for the setup of real -time multicast connections satisfying delay bound and delay variation bound.The algorithm assumes that each node does not have point-to -point routing information.It selects routes according to incident links only and integrates routing and wavelength assignment as a single process.The method is to add a minimal cost link to the tree at a time according to MST algorithm.For destinations not included in the tree,they are added to the tree by adding a link to the tree to make a cycle then to remove a longer delay path.Then delay variation is checked.If it is not satisfied,then the Steiner tree is reconstructed,and a longer-delay path is selected to replace the original low-delay path for the destinations not satisfying delay variation bound.The algorithm assigns wavelength according to the rule of least-conversion and load-balance.

关 键 词：路由与波长分配 组播路由 延迟限制路由 延迟差限制路由 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]