（电磁场与微波技术专业论文）稀疏分光wdm网络中基于遗传算法的组播业务研究.pdf

稀疏分光w d m 网络中 基于遗传算法的组播业务研究 摘要 在物理层即光层引入组播技术可以产生许多有价值的宽带实时 应用业务，例如视频点播，电视会议，远程医疗等。但是全光组播性 能的实现要求光网络的节点具有分光( l i g h ts p l i t t i n g ) 能力。具备此 能力的节点可以将一路输入光信号分成若干路发送出去，组播能力 ( m c ，m u l t i c a s tc a p a b l e ) 节点的引入使光域不必将组播拆解成若干 路单播来实现从而节省了光路资源。但是具备组播能力的节点本身成 本较高，因此一个有效的做法就是尽量减少组播能力节点的个数而换 以非组播能力节点，使用稀疏的分光节点( s p a r s es p l i t t i n g ) 。 目前在稀疏分光网络中的组播研究主要侧重于单个业务，对同时 存在多个业务的情况研究地还比较少。本文首先构造了适合于稀疏分 光网络中的组播路由和波长分配算法，较之以往的基于源的光树建立 方案，我们采用了基于组播节点的光树建立方案。同时引入遗传算法 对组播业务进行排序，然后按顺序构建组播树的一种启发式算法，试 图对全网使用的波长和链路数进行优化。对于使用的遗传算法，提出 了新的编码和译码方案，并用数值仿真的方法比较了几种不同的交叉 和变异算子的使用效果，在上述工作基础上，提出了双向译码和爬山 法的改进方案。 仿真结果表明：( a ) 考虑业务的不同放置顺序是合理的，用遗传 算法来进行排序是有效的。( b ) 采用双向译码并不能有效地改进原始 算法，而爬山法则对原始算法有一定的改进作用。( c ) 随着网络中所 使用的m c 节点数的增加，网络的性能能够得到明显的改善。( d ) m c 节点数只用占到全网节点数的一半就可合理地利用网络资源，而 不用全网节点均配置组播能力，这一结论对于网络设计将有着相当重 要的参考价值。 关键词：w d m 光网络，组播，稀疏分光，遗传算法，光树 t h er e s e a r c h0 fm u i j i c a s tt r a f f i c s b a s e d0 ng e n e t i ca l g o r i t h m i ns p a r s e s p l i t t i n g0 p t i c a l 1 d mn e t w o r k s a bs t r a c t i n t r o d u c i n gm u l t i c a s tt e c h n i q u ei no p t i c a ll a y e rc a nb r i n gm a n y v a l u a b l ew i d e b a n dr e a l t i m e a p p l i c a t i o n s ，s u c ha sv i d e od i s t r i b u t i o n ， t e l e c o n f e r e n c i n g ，d i s t a n tm e d i c a lt r e a t m e n t ，e t c ，b u tt h ei m p l e m e n t a t i o n o fa l l o p t i c a lm u l t i c a s t p e r f o r m a n c ea s k s t h en o d e si nt h e o p t i c a l n e t w o r k st ob ep r o v i d e dw i t ht h el i g h t - s p l i c i n gc a p a b i l i t y t h en o d ew i t h s u c hc a p a b i l i t yc a nf o r w a r da ni n c o m i n go p t i c a lm e s s a g et om o r et h a n o n eo u t p u t1 i n k t h ei n t r o d u c t i o no fm c ( m u l t i c a s tc a p a b l e ) n o d e d o e s n tn e e dt os e p a r a t et h em u l t i c a s tt r a f f i ci no p t i c a ll a y e ri n t om a n y u n i c a s tt r a f f i c ss oa st os a v eo p t i c a l p a t hr e s o u r c e s h o w e v e rt h ec o s to f m cn o d ei sv e r ye x p e n s i v e ，s oa ne f f e c t i v em e t h o di st h a to n l yas u b s e t o ft h en o d e sa r ea s s u m e dt ob es p l i t c a p a b l en o d e s ，w h i c hi sc a l l e d s p a r s e s p l i c i n g a tp r e s e n tt h em u l t i c a s tr e s e a r c hi ns p a r s e s p l i c i n go p t i c a ln e t w o r k i se m p h a s i z e do nt h es i n g l et r a f f i c ，t h es i t u a t i o no fe x i s t i n gm u l t i t r a f f i c s h a sg a i n e dl e s sr e s e a r c h i nt h i sd i s s e r t a t i o nam c r w r a a l g o r i t h ms u i t e d i ns p a r s e s p l i c i n go p t i c a ln e t w o r k si sf i r s tc o n s t r u c t e d ，c o m p a r e dw i t ht h e p r e v i o u sl i g h t t r e ee s t a b l i s h m e n ts c h e m eb a s e do nt h es o u r c en o d e ，w e a d o p tt h es c h e m eb a s e do nm cn o d e a tt h es a m et i m ew ei n t r o d u c et h e g e n e t i ca l g o r i t h mt oc o l l o c a t e t h em u l t i c a s tt r a f f i c s ，t h e nc o n s t r u c ta h e u r i s t i ca l g o r i t h mt oo p t i m i z et h en u m b e ro fw a v e l e n g t ha n d1 i n ku s e d i nt h en e t w o r k s a b o u tt h eg e n e t i ca l g o r i t h mw eh a v ep r o p o s e dan e w c o d i n ga n dd e c o d i n gs c h e m e ，a n dc o m p a r e dt h ee f f e c to fav a r i e t yo f c r o s s o v e ra n dm u t a t i o no p e r a t o r sw i t hn u m e r i c a ls i m u l a t i o n b a s e do n t h ea b o v ew o r kt h ei m p r o v e ds c h e m e so fb i d i r e c t i o n a l d e c o d i n ga n d h i l l c l i m b i n ga r ep r o p o s e d t h es i m u l a t i o ns h o w s ：( ，a 1t oc o n s i d e rt h ed i f f e r e n to r d e r o f a l l o c a t i n gt h et r a f f i c s i ss u i t e d ，a n da r r a n g et h eo r d e rw i t hg e n e t i c a l g o r i t h mi se f f e c t i v e ( b ) t oa d o p tb i d i r e c t i o n a ld e c o d i n gc a n ti m p r o v e t h eo r i g i n a la l g o r i t h me f f e c t i v e l y , w h i l et h eh i l l c l i m b i n gc a r ld oi t ( c ) w i t ht h ei n c r e a s eo ft h en u m b e ro fm cn o d eu s e di nt h en e t w o r k ，t h e c a p a b i l i t yo ft h en e t w o r kc a nb ei m p r o v e dc l e a r l y ( d ) m e nt h en u m b e r o fm cn o d ei sh a l fo ft h et o t a ln u m b e r , t h en e t w o r kr e s o u r c ec a nb eu s e d w e l l t h i sc o n c l u s i o nw i l lb ew e l lv a l u a b l ew h i l ed e s i g n i n gt h en e t w o r k s k e yw o r d s ：w d m o p t i c a ln e t w o r k ，m u l t i c a s t ，s p a r s e s p l i c i n g ， g e n e t i ca l g o r i t h m ，l i g h t - t r e e 稀疏分光w d mi 叫络中皋于遗传算法的组播业务研究 1 1w d m 网络 1 1 1w d m 技术及其主要特点 第一章绪论 随着人类信息化特别是i n t e m e t 的飞速发展，对于通信的需求呈现出加速增 长的趋势，而新出现的各种各样的业务也对通信网的容量和带宽提出了更高的要 求。光纤具有巨大的带宽和优异的传输性能。为了在一根光纤中传输更高速率的 数据，己提出了包括光时分复用( o t d m ) 、光波分复用( w d m ) 、光频分复用 ( o f d m ) 以及光码分复用( o c d m ) 等技术。而其中w d m 技术最为成熟。 光波分复用是光纤通信中的一种传输技术，它利用了一根光纤可以同时传输 多个不同波长的光载波的特点，把光纤可能应用的波长范围划分成若干个波段， 每个波段用作一个独立的通道传输一种预定波长的光信号。 光波分复用的实质是在光纤上进行光频分复用，只是因为光波通常采用波长 而不用频率来描述、监测与控制，在波分复用技术高度发展，以及每个光载波占 用的频度极窄、光源发光频率极其精确的前提下，或许使用光频分复用来描述更 恰当些。波分复用技术的基本原理【】是在传输系统的发送端采用复用器将不同波 长的光信号组合起来进行复用，并把信号耦合到光缆线路的一根光纤中进行传 输，在接收端采用解复用器分离出不同波长的光信号，并把恢复出的信号送入不 同的终端。 波分复用通信传输系统主要有双纤单向传输和单纤双向传输两种结构 2 1 。在 双纤单向传输系统中，所有的光通路同时在一根光纤上沿同一方向传送，反方向 通过另一根光纤传输。而在单纤双向传输系统中，光通路在一根光纤上同时向两 个不同方向传输，所有波长相互分开，以实现彼此双方全双工的通信联络。单向 的w d m 系统在开发和应用方面都比较广泛。双向w d m 系统的开发和应用相 对来说要求更高，这是由于双向w d m 系统在设计和应用时必须考虑到几个关键 的系统因素，如要抑制多通道干扰，同时要使用双向光纤放大器。 稀疏分光w d ml 劂络中暴于遗传算法的组播业务研究 w d m 技术具有的主要特点： 1 用光纤的巨大带宽资源：w d m 技术充分利用了光纤的巨大带宽资源( 低损 耗波段) ，使一根光纤的传输容量比单波长传输增加几倍到几十倍，从而增加光 纤的传输容量，降低成本，具有很大的应用价值和经济价值。所以w d m 技术可以 充分利用单模光纤的巨大带宽，从而在很大程度上解决了传输的带宽问题【3 1 。 2 同时传输多种不同类型的信号：由于w d m 技术中使用的各波长相互独立， 因而可以传输特性完全不同的信号完成各种电信业务的综合和分离，包括数字信 号和模拟信号，以及p d h 信号和s d h 信号，实现多媒体信号( 如音频、视频、数 据、文字、图像等) 混合传输【4 1 。 3 实现单根光纤双向传输：由于很多通道( 如：电话) 都采用全双工方式， 因此采用w d m 技术可节省大量的线路投资【4 j 。 4 具有多种应用形式：根据需要，w d m 技术可有很多应用形式，如长途干线 网，广播式分配网络，多路多址局域网络等，因此对网络应用十分重要。 5 降低器件的超高速要求：随着传输速率的不断提高，许多光器件的响应速 度已明显不足，使用w d m 技术可降低对一些器件在性能上的极高要求，同时又可 实现大容量传送。 6 具有高度的组网灵活性、经济性和可靠性：利用w d m 技术进行路由选择， 实现网络交换和恢复，从而实现未来透明、灵活、经济且具有高度生存性的光网 络【3 1 。 1 1 2w d m 波长路由网络 在网络内部以光纤为传输介质、使用w d m 方式传输信号、并以全光( a l l o p t i c a l ) 方式进行交换的网络称为w d m 全光网络，简称为w d m 网络。w d m 网络有两种基本 形式【5 j ，即广播与选择网络( b r o a d c a s t a n d s e l e c to p t i c a ln e t w o r k ) 和波长路由网 络( w a v e l e n g t h r o u t e do p t i c a ln e t w o r k ) 。 广播与选择网络是一种星型网络，如图1 - 1 所示。所有节点都连接到一个称 为无源星型耦合器的中心设备上，各节点所发送的信息被星型耦合器合并( 复用) 2 稀疏分光w d m 例络中幕十遗传算法的绁播业务研究 后，广播到所有节点，各节点只接收约定波长的信号，过滤掉其它波长的信号。 有两种工作方式：固定波长光发送与可协调的光接收；接收波长固定和可协调发 送。源节点和目的节点在通信前要通过某种机制确定通信所用的波长，并把发送 器、接收器调谐到给定的波长，从而实现通信的目的。 图1 1 广播与选择光网络基本结构组成 由于星型耦合器和光纤链路都是无源的，所以这种网络很可靠而且易于控 制。但是广播与选择网络有几个明显的缺点。其一是浪费了光功率。发射的光功 率送到所有的接收器，不管这个接收器是否是通信对象。这样，对实际通信节点 来说，增加了光分流引起的损耗。其二是可扩展性差。n 个节点至少需要n 个 波长，增加一个节点就要增加一个波长，每一个接收器的可协调范围也要相应增 加一个波长，而且不能执行波长重用。其三就是带宽利用率低，一般一个节点只 能使用1 n 带宽这种广播与选择网适合于局域网，但不适合建设规模较大的网 络。 波长路由光网络 6 1 是由可以进行波长路由的网络和一些点到点的光纤连接 而组成的。波长路由节点中最重要的器件就是光交叉连接器( o x c ) ，光交叉连 接器的输入输出端口分为中继栈( t r u c k ) 端口和本地( 1 0 c a l ) 端口，中继栈端口通过 光纤与其它波长路由节点相连，本地端口则用于本地业务的上下路。所有业务的 起点和终点都在本地端口。当光交叉连接器只含两个中继端口时，相应的节点被 称为光分差复用a ( o a d m ) 。o a d m 可以看成o x c 结构的功能简化。光交叉 连接器由波长复用器，解复用器，交换矩阵组成，还有可能包含波长转换器【4 1 。 稀疏分光w d m 嘲络中綦于遗传算法的组播业务研究 在波长路由网络中，o x c 与光链路互相连接组成任意的拓扑结构，如图所示。 每个终端用户都通过光链路连接到o x c 上，终端用户与其相应o x c 的组合就 是一个网络节点。每个网络节点都配有可调协发射器和接收器。 波长路由网络的基本通信机制是光路( l i 曲t p a t h ) t7 1 ，光路是源节点和目的节 点之间的一条全光通信通道，可以跨越多条光纤链路。光路的建立以可用波长为 基础，按给定的规则为每条链路分配一个可用波长，中间节点直接使用光交换而 不进行光电转换当在中间节点没有波长转换器( w a v e l e n g t hc o n v e r t e r ) 时，光路上 连续的多条链路必须使用同一波长，这种条件称为波长连续性约束。如图1 2 中 由a 到c 的通道和由b 到f 的通道就满足波长连续性条件。带有波长转换器的 光网络不必满足这一需求，如图中由d 到e 的通路。波长路由网络的基本要求 是满足d c a 条件【8 】，即同一光纤链路上的不同光通道必须具有不同波长，以免 通道间互相干扰。如图所示，由于从a 到c 的通道和由h 到g 的通道没有公共 链路，所以两条连接都可以使用波长a 进行传输。而从a 到c 的通道和由b 到 f 的通道有公共链路，要满足d c a 条件就必须分别使用波长丑和波长乃进行传 输。在这个例子中，四条通信光路只使用了两个波长，这说明波长选路网络可以 用较少的波长支持较多节点间的通信。因此在w d m 网络中建立两点之间的连 接，若选择一条最佳路由和合适的波长，可极大地提高网络效率，减小波长的阻 塞，通过优化网络的路由和波长，还可减少节点设备的端口数，降低网络成本。 h 图1 - 2 波长路由光网络结构示例 4 稀疏分光w d m 叫络中螭十遗传算法的组播业务研究 在波长路由网络中，特定波长上的信号被寻径到目的节点，而不是向全网广 播。这样就减少了不必要的光能损失，同时又能使一个波长在网络的非重叠部分 被多次使用。由于波长路由网络是一种更普遍的网络形式，也是骨干网络的主要 形式。更是未来骨干网络必然采用的通信方式，因此本文将这种网络作为研究的 对象，并将其简称为w d m 网络。 1 2 组播 1 2 1 组播技术引入的必要性 组播技术被认为是、v 、 m ，技术推广之后出现的最激动人心的网络技术之一 9 1 。组播的概念最早是在19 8 8 年由s t a n f o r d 大学的s t e v ed e e r i n g 发展起来的。 当时是为了促进i n t e m e t 上实时音频和视频的传输。i p 组播的核心思想是通过一 个i p 地址向一组主机发送数据( u d p 包) 。组播技术是通信网络将发起端的 信息复制多份同时传递给多个接收端的一种信息传递技术，即点对多点的通信。 与多个点对点通信方式相比它最主要的特点在于可以极大的节省带宽，避免广播 带来的全网范围的泛洪。因为它消除了从源端对每一个目的端都发送一个信息副 本的必要。 随着网络技术的不断发展和用户需求的不断变化，组播业务日益成为一种重 要的业务模式。需要组播技术支持的业务类型主要是一些带宽密集型的业务：如 视频会议、软件文件的传递和镜像站点的文件复制、虚拟现实游戏、互联网新 闻信息的传播和电子邮件列表、远端教学、电子商务、视频点播、光存储网络( o s a n ) 等等。组播在并行处理和电网络领域已经得到了广泛的研究。尽管对需 要组播技术支持的业务需求很大，但由于现有的网络都主要是面向点到点通信而 设计的，所以并不能有效地支持组播功能。 1 2 2 组播的应用 由于组播能有效减少网络和主机丌销，较单播和广播有其独特优越性，因此， 组播已经得到了广泛的应用。组播应用大致可以分为三类：点对多点应用，多点 稀疏分光w d mi 叫络中綦于遗传算法的组播业务研究 对点应用和多点对多点应用。 1 2 2 1 点对多点的应用 点对多点应用是指一个发送者，多个接收者的应用形式，这是最常见的组播 应用形式。典型的应用包括： 媒体广播：如演讲、演示、会议等按日程进行的事件。其传统媒体分发手段 通常采用电视和广播。这一类应用通常需要一个或多个恒定速率的数据流，当采 用多个数据流( 如语音和视频) 时，往往它们之间需要同步，并且相互之间有不同 的优先级。它们往往要求较高的带宽、较小的延时抖动，但是对绝对延时的要求 不是很高。 媒体推送：如新闻标题、天气变化、运动比分等一些非商业关键性的动态变 化的信息。它们要求的带宽较低、对延时也没有什么要求。 信息缓存：如网站信息、执行代码和其他基于文件的分布式复制或缓存更新。 它们对带宽的要求一般，对延时的要求也一般。 事件通知：如网络时间、组播会话日程、随机数字、密钥、配置更新、有效 范围的网络警报或其他有用信息。它们对带宽的需求有所不同，但是一般都比较 低，对延时的要求也一般。 状态监视：如股票价格、传感设备、安全系统、生产信息或其他实时信息。 这类带宽要求根据采样周期和精度有所不同，可能会有恒定速率带宽或突发带宽 要求，通常对带宽和延时的要求一般。 1 2 2 2 多点对多点的应用 多点对多点应用是指多个发送者和多个接收者的应用形式。通常，每个接收 者可以接收多个发送者发送的数据，同时，每个发送者可以把数据发送给多个接 收者。典型应用包括： 多点会议：通常音视频和自板应用构成多点会议应用。在多点会议中，不 同的数据流拥有不同的优先级。传统的多点会议采用专门的多点控制单元来协调 6 稀疏分光w d m 网络中幕十遗传算：泫的组播业务研究 和分配它们，采用组播可以直接由任何一个发送者向所有接收者发送，多点控制 单元用来控制当前发言权。这类应用对带宽和延时要求都比较高。 资源同步：如日程、目录、信息等分布数掘库的同步。它们对带宽和延时的 要求一般。 并行处理：如分布式并行处理。它对带宽和延时的要求都比较高。 协同处理：如共享文档的编辑。它对带宽和延时的要求一般。 远程学习：这实际上是媒体广播应用加上对上行数据流( 允许学生向老师提 问) 的支持。它对带宽和延时的要求一般。 讨论组：类似于基于文本的多点会议，还可以提供一些模拟的表达。 1 2 2 3 多点对点的应用 多点对点应用是指多个发送者，一个接收者的应用形式。通常是双向请求响 应应用，任何一端( 多点或点) 都有可能发起请求。典型应用包括： 资源查找：如服务定位，它要求的带宽较低，对时延的要求一般。 数据收集：它是点对多点应用中状态监视应用的反向过程。它可能由多个传感设 备把数据发回给一个数据收集主机。带宽要求根据采样周期和精度有所不同，可 能会有恒定速率带宽或突发带宽要求，通常这类应用对带宽和延时的要求一般。 网络竞拍：拍卖者拍卖产品，而多个竟拍者把标价发回给拍卖者。 信息询问：询问者发送个询问，所有被询问者返回应答。通常这对带宽的 要求较低，对延时不太敏感。 但是，通常定义的组播即为点到多点的应用形式。本文中，我们所研究的组 播业务如果没有特别注明，就是指的点到多点的形式。组播( m u l t i c a s t ) 是一种组 通信机制，它是一个源节点( 发送者) 将信息同时发送给多个目的节点( 接收者) 的 通信方式。当只有一个目的节点时，就变为单播( u n i c a s t ) ，即点到点通信。当目的 节点集包括网络中除源节点外的所有节点时，就是广播( b r o a d c a s t ) 。 按请求的性质，可以将组播分为静态组播和动态组播。所谓静态组播是指组 稀疏分光w d m 网络中璀十遗传算法的组播业务研究 播请求预先知道网络的全局状态，并且没有实时性要求，网络系统对一组请求统 一调度。与此相反，动态组播请求具有时间性，一旦达到，要求立即实现，也称 为实时组播，通常是针对单个请求进行调度。 组播是一种面向连接的通信方式，通信之前需要进行组播路由选择，建立从 源节点到所有目的节点的连接。所建立的组播连接是一棵以源节点为树根、包含 所有目的节点的树，称为组播树( m u l t i c a s tt r e e ) 。实时组播要求实时地建立组播 连接，建立组播连接就是寻找满足条件的树。我们称这样的树为s t e i n e r 树【1 0 】。 1 3w d m 网络中的组播业务 在新一代高速光纤通信系统中，最具代表性的就是波分复用( w d m ： w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ) 系统。其最突出的特点就是可有效地利用单模 光纤低损耗区所带来的巨大带宽资源，明显地提高系统的传输容量，同时将相应 的成本降低到很低的程度。同时，w d m 全光网还具有可重构性、可扩展性、透 明性、兼容性、完整性、生存性等优点，是目前光纤通信领域的研究热点和前沿。 此外，现有的网络大多采用点到点的传送方式即单播方式。在这种情况下， 发送方和接受方需要一单独的数据通道，从一台服务器送出的每个数据包只能传 送给一个客户机。如果有另外的用户希望顺路获得这个数据包的拷贝是不可能 的。对于需要将同一数据发送给位于网络中不同位置的多个接受端的服务来说， 这种方式将极大的加重服务器的负担并浪费大量带宽。解决的办法是构建一种具 有组播能力的网络，允许网络中的节点一次将数据包复制到多个数据通道上。组 播发送方只要发送一个信息包而不是很多个，所有目的地同时收到同一信息包， 更及时，更同步，可以把信息发送到任意不知名目的地，能减少网络上传输的信 息包的总量。可有效降低网络的通信成本，增大网络的通信能力。 目前，对w d m 网络进行了大量的研究，其中大多数集中于单播( 点到点) 通信。最近，w d m 网络中传输组播业务引起了大量的关注，考虑到组播( 一点 到多点) 在i n t e m e t 的应用越来越广泛，在w d m 网络上执行组播会话的研究就 显得很有必要。采用这一技术，可以充分结合w d m 网络高带宽和组播高效的优 点。 稀疏分光w d mj 劂络中皋十遗传算法的组播业务研究 在w d m 网络中实现组播可以通过三种方式，如图所示： 1 、图1 - 3 ( a ) 中，每个s t a t i o n 称为一个路由器，可通过让组播树中的每个路 由器生成一个数据包的多个拷贝，并将每个拷贝独立地传送到下行路由器来实现 组播。然而，这要求每个数据包都要在所有路由器上进行o e o 转换，这将是 低效( 对于延迟) 和无法接受的( 对于数掘透明性) 】。 2 、o e o 转换可通过使用包含光通路( l i g h t p a t h ) 的虚拟拓扑结构来加以避 免。如图1 - 3 ( b ) ，光通路是组播会话中从源到目的节点的一条虚拟通路。然而， 由于光通路的单播特性，在一个大型组播组中使用这一策略所消耗的网络带宽是 无法忍受的【l2 | 。 3 、如图1 - 3 ( c ) 所示，通过利用w d m 网络中节点的分裂能力，将同一输入 端口接收的光信号“复制”到不同的输出端口，从而使组播过程在w d m 层上完 成，这种方案应该是更加理想的，由于到不同目的地的传送可以在共同的链路上 共享带宽。w d m 组播可定义为利用w d m 网络中节点的分裂能力或者说是组播 能力，在w d m 层完成组播功能的组播通信。当然，如文献 13 】提出，一种可选 的方案是在光树上的每个分支建立一个标签交换通路( l s p ) ，利用光突发标签 交换( o b s o l s ) 技术。 9 稀疏分光w d mi 叫络中撼十遗传算法的纽播业务研究 w d w d ( b ) ( a ) w d 图1 - 3w d m n 络中的几种组播形式 ( c ) w d m 组播有许多潜在的优点。首先，由于知道物理层( w d m 层) 的拓扑 结构，而这一结构与它上面的电子层( i p 层) 不同，因此可以在w d m 层构建 更为有效的组播树( 对于带宽和延迟) 。第二，如果w d m 节点具有分裂能力， 而分裂能力比i p 层的拷贝对于实现组播更为有效。最后，对于位率和编码格式 来说，w d m 层组播提供了更高的数据透明性。 1 4 本文的研究目标 在全光网络罩，所有的光纤都通过光交换元件来连接，数据在光域里由源节 点( s o u r c e ) 向目的节点( d e s t i n a t i o n ) 透明地传输。近来，在广域全光网络里有 关在w d m 层的组播业务得到了一些研究【1 1 , 1 2 , 1 4 , 1 5 】，在这些文献里，光交换开关 都具备分光( 1 i g h ts p l i t t i n g ) 能力用来在光域转发从一个源节点到多个目的节点 l o 稀疏分光w d m 叫络中拱于遗传算法的组播业务研究 的数据。在【1 4 】里，波长路由全光网络中光树( 1 i g h t - - t r e e ) 的概念被首先引入。 一般来说，基于光树的虚拟拓扑也就是基于光路拓扑的延伸。在基于光树的方案 中，数据可以全光且同时地发送到多个目的节点，这样资源就可以在光树的公共 链路上得到共享。已经显示，相比于光路，采用光树可以获得更好的性能并且更 有效地支持广播业务，因为它们固有的点到多点的属性。相应的性能指标通过跳 数和全部的光电元件数目来衡量。 一棵光树就是根于源节点并扩展到所有目的节点的棵直接s t e i n e r 树，已 经证明，寻找s t e i n e r 树问题( s t p ) 为n p 难问题【1 6 , 1 7 】，也就是问题的时间复杂 度与问题规模的关系不能用多项式来表达。所以通常只能用一些启发式 ( h e u r i s t i c ) 的算法去求解近似最优解。在单播全光网络里的路由问题被称为路 由和波长分配问题，即r w a 问题【7 j ，并以被证明为n p 难问题。组播全光网络 里的路由问题被称为组播路由和波长分配，我们称之为m c r w a ，同样也是n p 难问题【1 5 j 。 通过节点的分光能力实现组播的方法必然导致功率的损耗，所以就需要额外 的光放大器。另外，因为其结构的复杂性，具备分光功能的设备必然是很昂贵的。 于是，提出了稀疏分光的概念【15 i 。在稀疏分光网络里，网络里的交叉连接设备 被分为两组【18 】：一组是具备分光能力，也就是具有组播能力，我们称之为 m u l t i c a s t c a p a b l e ( m c ) ；另一组是非组播能力节点，即m u l t i c a s t i n c a p a b l e ( m i ) 。 一个m c 交叉连接可以转发输入信号至任意的输出端口，而m i 交叉连接能将输 入信号转发至一个输出端口。 目前在w d m 全光网络里，在具备稀疏分光节点条件下，组播业务的r w a 问题得到了广泛的研究，但是大多数情况下仅局限于单个业务，对于同时承载多 个组播业务的研究甚少。本文试图利用遗传算法来对多个组播业务进行排序，然 后按顺序构建组播树的一种启发式算法，从而优化全网中被使用的波长数和链路 数。并寻找具备组播能力的节点在网络中的合理配置。 稀疏分光w d m1 ) 6 4 络中接于遗传算法的纽播业务研究 2 1 引言 第二章光组播原理及其节点结构 组播技术是通信网络将发起端的信息复制多份同时传递给多个接收端的一 种信息传递技术。基于组播技术可以产生许多价值的应用。基于p 层的组播需 要在路由器中对组播分组以电的方式进行复制，并不能实现在光层的组播。通过 把面向i p 层的组播技术推广到光层领域，可以突破“电子瓶颈”的限制，使得运 营商能够提高宽带实时应用如高清晰度电视、光存储区域n ( o s n a ) 等多媒体 业务的传输性能。尽管对需要组播技术支持的业务需求很大，但由于现有的网络 都是主要面向点到点通信而设计的，所以并不能有效地支持组播功能。由于组播 应用将越来越流行，同时用户对带宽有越来越强烈的需求，势必需要下层通信网络 提供组播通信能力。因此，研究在物理层( 光传输层) 的组播技术具有拓展该技术到 骨干网以至i n t e r n e t 的重大作用，将交换实时音像通信在更大范围内实现。如第 一章所阐述，具有组播能力的w d m 广域网不仅能够对组播业务提供有效的选路 支持，同时由于组播技术的引入使得网络具有更丰富的逻辑连接拓扑，因此它同时 也会大大增强网络对单播业务选路的灵活性。此外，还可以获得其它好处，如可实 现网络优化( 减少网络中收发机的数量、延长网络节点间的“虚 连接、减少波 长数目) 。由于以上优点使得对光层组播网络的研究越来越成为一个研究热点。 2 2 光组播原理及其节点结构 2 2 1 光组播原理 w d m 技术把光纤的巨大带宽( 达5 0 t h z ) 分成许多互不重叠的波长( w d m 信道) 。每一信道可以同步并行地工作于期望的速率上。为了理解w d m 网络区 别于其它的l e g a c y 网络，我们根据采用的物理层技术将l e g a c y 分为三代【1 9 列。 第一代网络在物理层不采用光纤技术，相反而是利用基于铜线或是微波技术。因 稀疏分光w d m 刚络中皋十遗传算泫的组播业务研究 此，数据的接收和发送都工作在电的领域。以太网就是第一代网络一个典型的例 子。在第二代网络里，铜线链路和微波链路被光纤所取代。现在，尽管数据发送 在光域执行，但是中间的交换仍然在电域。光纤分布数据接口( f d d i ) 是第二 代网络的一个例子。想想在光纤旱的可用带宽在5 0 t h z 量级上，因此，第二代 网络只占用了光纤可用带宽的极小部分。另一方面，第三代网络( 也就是w d m 网络) 通过把光纤的带宽分成许多不重叠的波长而利用了其大部分的可用带宽， 以至于每个信道工作于极限的电子速率。因此，w d m 网络成为下一代网络的最 理想方案并不奇怪。 2 2 1 1 光路( l i g h t p a t h ) 由于w d m 系统最初用来增加点对点关系链路的容量，导致形成了不透明的 光网络，在网络的中继节点中光信号需要经过光电光( o z o ) 的方式放大、再生。 随着光交叉连接器件( o x c ) 等更先进的器件的成熟和商用化，构建透明的光网络 ( 网络中不存在光电光转换) 成为下一步网络发展的目标。o x c 能够将一根输入 光纤中某一波长携带的光信号交换到输出光纤的同一波长中。光网络中的这种传 输方式叫光路【2 1 1 ，它是一条用来承载电路业务的全光通道，可能跨越多条光纤 链路。在缺乏波长转换器的情况下，一条光路将在它穿越的所有光纤链路上占用 相同的波长，这称为波长连续性约束。例如，在图2 1 ( a ) 中，从主机c a 2 到主机 n y 的光路( 虚线所示) 将要占用路上每一链路的同一波长。光路可以创建地理 上独立于实际网络的逻辑( 虚拟) 邻连接。利用光路通信，很多光路将被建立以 嵌入到逻辑拓扑中。许多光路通信的目的是为了减少光跳数( 光路) ，结果很大 程度上提高网络的吞吐量。在光路通信下，网络利用相同的接收器和发送器，因 为每条光路是基于点到点工作的。然而，这种方法可能是不能完全利用网络中所 有链路上的所有可用波长的；同时，它也不能完全利用每个w r s 的交换性能l 2 2 l 。 2 1 1 2 光树( l i g h t t r e e ) 基于光路通信的局限性，我们将采用光组播性能来扩展光路的概念。光组播 是将点到点的光路连接方式扩展为点到多点的光连接，这就形成了光层组播，点到 多点的光连接称为“光树”【1 4 1 。更准确地讲光树是点对多点没有环路的光通路。 稀疏分光w d mi ) 6 | i 络中某于遗传算法的组播业务研究 光树是一条点对多点的光通路的概念的归纳，波长路由网络中的组播，需要为每 个组播请求建立光树。 光树上的每一个上游节点有不止一个的下游节点。光树技术的应用能够使一 个节点中的一个发射机同时具有多个逻辑上的邻居节点，从而使原本物理连接关 系十分简单的一个网络的逻辑互联图变得复杂多样，而且使得原有的一些物理连 接的跳数大大降低。如果在一个w d m 光网络中嵌入一套光树连接，则可以增强 该网络的单播、组播和广播能力，但是相应地就需要网络具有支持组播的光交换 机和更高的功率阈值以弥补由于信号分割而造成的功率损耗。 图2 - 1 光路和光树示意图 在光网路中实现组播连接的实质就是建立一棵从源端到所有目的端的光树。 图2 1 ( a ) 我们给出一条光树( 如实线所示) ，它连接节点u t 至节点t x 、n e 、 i l 。于是，光信号由节点u t 发射，沿着光树传输至节点c o ，在这里信号被光 分路器分成两份，一份被路由至节点t x ，由接受器终结信号；另一份光信号被 路由至节点n e ，在此信号再一次被分为两份。在节点n e ，一份光信号被接收 器终结，而另一份被路由至节点i l ，最后光信号在节点i l 由接收器终结。因此， 被这条光树导出的虚拟拓扑由三条逻辑链路组成，如图2 1 ( b ) 所示。 一棵好的组播树应该具有如下的特性1 2 3 】： 低成本 低时延 1 4 稀疏分光w d mi 叫络中呆子遗传算法的组播业务研究 可扩展性( s c a l a b i l i t y ) 支持组播组成员的动态性 建立这样全光光树的解决方案包括找到从源端节点到所有的目的节点的路 由( 可能不是单棵的树) 并决定在这些路由上使用的波长，即所谓的m c r w a 问题。 2 2 2 具有组播能力的交叉节点结构 光层组播的实现是基于光器件可以实现光分束的固有特性的，而这种器件就 是光分路器( s p l i t t e r ) 。它可以将一路输入光信号分割成多路输出信号，而且各 路光信号的功率大小可以通过分路器的分波比来进行控制和管理。目前支持组播 的光交叉连接( m c o x c ：m u l t i c a s tc a p a b l eo p t i c a lc r o s s c o n n e c t ) 结构的研究 成果主要包括： 星型耦合器( s t a rc o u p l e r ) ：这种结构工作时需要波长转换器和可调谐 滤波器，主要用在广播选择网络中。 s p l i t t e r - c o m b i n e r ；两级的s p l i t t e r 乖1 - - 级f 拘c o m b i n e r 结构。 s a d ( s p l i t t e r a n d - d e l i v e r y ) 结构。 t a c ( t a p - a n d - c o n t i n u e ) 使用t a p 器件而不用光分路器。 这里主要介绍s a d 结构以及其几种改进的结构。 2 2 2 1s a d 结构 19 9 8 年w s h u 等人首次提出具有s a d 交换结构的m c - - o x c 24 | 。图2 2 给出了一种具有这种结构的n n 的m c o x c 。其中每一条链路支持n 路波 长信号，从每一条输入光纤链路上输入的光信号首先被解复用器( d e - - m u x ) 解 复用成n 分独立的波长信号，然后各路波长信号被s a d 交换结构进行交换。图 2 3 是一个p p 的s a d 交换结构，其中s p l i t t e r 用于进行输入光信号的分束，分 束后的每一路信号通过2 x1 的光交换交换到相关的输出端口。图中的g a t e 是可 选的，主要用于降低串扰( c r o s s - - t a l k ) 。这种交换结构的主要特点在于它的严格 无阻塞和组播能力。 稀疏分光w d ml 埘络中攮于遗传算法的组播业务研究 图2 2 基于s a d 结构的n nm c o x c 、 _ c ) _ _ ) ) j： 、 r ) _ () ) )： 、 r、r 单播连接 ： 将两种业务区别对待普通的单播业务不需要经过分束器，只有组播业 务才进行分束，以此来降低功率损耗。 h p -分路器共享组播业务交换到特定的端口共用同一个分束器。但与s a d 结构相比，原来的s a d 结构是严格无阻塞结构，改进之后的结构对单播 业务是严格无阻塞的，而对于组播业务来说这种结构不是严格无阻塞 的。同时这种新结构可以降低成本，减少信号损耗。在结构的阻塞性能 和成本以及分束功率损耗之间有一定的平衡( t r a d e o f f ) 。研究的数据结 果显示这种结构对网络的阻塞性能影响较小，可以忽略不计。 上面是针对交换结构对信号功率有效性的改进，另外一个改进方向则是针对 交换结构的制造成本。在s a d 结构中由于使用多个分束器，所以需要使用多个 光放大器。 文献】提出了一种合理的成本有效( c o s t e f f e c t i v e ) 的 t a c ( t a p a r i d c o n t i n u e ) 结构来实现光层的组播这种结构是基于t a p e 器件的，不需 要使用分路器。在这种结构中，一个o x c 可以t a p 输入信号的- - d , 部分( 如5 ) 功率到本地客户端，然后将剩余的信号功率交换到输出端口，