（通信与信息系统专业论文）用整数线性规划方法解决wdm光网络中问题.pdf

摘要 摘要 本文研究的是和w d m 光网络的有关问题，主要有以下三个方面的内容： w d m 网络里各种保护手段的线性规划模型，一种新的基于l i n k - p a t h 方式的w d m 网络中稀疏波长转换的线型规划模型，以及光迹( 1 i g h tt r a i l ) 中的整数线型规划 设计。 第一章是绪论和本文研究背景的介绍，以及本论文的章节安排。 第二章研究了光网络的抗毁设计。 常见的保护手段包括专用保护和共享保护。本章主要的研究方向是共享保护 和p - c y c l e ，因此，针对目前己提出的多种共享保护机制( 共享通路保护，共享链路 保护，共享子通路以及p - c y c l e ) 进行了建模，仿真以及性能比较。其中，尝试和 探讨了一种改良过后的子通路保护的模型。通过仿真验证了这个模型的正确性和 可靠性。 第三章将通过线性规划方法解决部分波长转换光网络中的波长路由分配 ( r o u t i n ga n d w a v e l e n g t h a s s i g n m e n t ) 问题。 鉴于目前具备全波长转换能力的波长路由节点仍然相当昂贵，因此实际应用 中为所有网络节点装配全波长转换器的作法并不现实。因此，研究网络节点无波 长转换能力和只有部分节点具有波长转换能力情况下的路由设计问题是很有必要 的。 本章探讨了一种新的基于链路通路( 1 i n k p a t h ) 方式的线性规划方法来解决 该问题，并且把这个模型与过去文献中提出的分层图模型进行了复杂度比较以及 在实验拓扑里面进行了仿真和性能分析。证明了这个模型的正确性和可靠性，并 且具有良好的可扩展性。 第四章重点介绍了一种新的设计方案光迹( 1 i g h tt r a i l ) 的概念，协 议及其优化模型。 光迹是区别于光路的设计。与光路不同，它可以被看作是一条光总线，其上 的中间节点都能仲裁的接入这条光总线，因此，光迹能承载多个节点对的通信。 由于光迹是较新的一种设计方案，现有的光迹模型只是最基本最简单的模型，还 是很粗糙的，并且还没有涉及波长致性约束，因此，本章在改进了光迹模型描 述的基础上，增加了考虑到波长一致性条件时光迹及其保护模型的描述，建模和 电子科技大学硕士论文 仿真。 作者在对本文研究的各种模型进行测试和比较时，首先用c + + 代码获得数据 源，对数据源进行必要的处理，然后用工具软件建立整数线性规划模型，将代码 得到的数据代入模型中进行求解。 最后是全文总结。 关键词：波分复用光传送网，选路和波长分配算法，生存性，保护设计，线性 规划 i i a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r k i n gt e c h n o l o g i e sa n dn e ws e r v i c e so fi n t e m e t ， t h e r ei sa ne x p l o s i v eg r o w t ht r e n do fi n t e r n e tt r a f f i c ，w h i c hn e e d st r e m e n d o u sn e t w o r k b a n d w i d t h s o m et r a d i t i o n a li pb a c k b o n en e t w o r k sa r ei p a t m s o n e ta r c h i t e c t u r e c u r r e n tt r a n s p o r tr a t eo fs o n e to rs d hi sm o s t l y2 5 g b sa n d10 g b s i ti sd i f f i c u l t t oi n c r e a s et r a n s p o r tr a t eo fs o n e tf n r t h e rb e c a u s eo ft h el i m i t a t i o no fe l e c t r o n i c d o m a i n a sw ek n o w , as i n g l ef i b e rc a ns u p p o r tm o r et h a n5 0 t h zl o w e r - l o s s b a n d w i d t hi nt h e o r y t h e i rb a n d w i d t hi ss t i l lu n d e m t i l i z e d w a v e l e n g t h d i v i s i o n m u l t i p l e x i n g ( w d m ) i sap r o m i s i n ga p p r o a c ht h a tc a n1 s et h ee n o r l n o u sb a n d w i d t ho f t h eo p t i c a lf i b e r as i n g l ef i b e rc a nb ee m p l o y e df o rm u l t i p l ed a t as t r e a m s s i m u l t a n e o u s l y a l l o p t i c a ln e t w o r k se m p l o y i n gt h ec o n c e p to fw d m a n dw a v e l e n g t h r o u t i n ga r ec o n s i d e r e da st h et r a n s p o r tn e t w o r k sf o rt h ef u t u r e i nt h i sd i s s e r t a t i o n ， w ec o n s i d e rf o l l o w i n gp r o b l e m s ：p r i o r i t y - b a s e dw a v e l e n g t ha s s i g n m e n ta l g o r i t h mi n r e s t o r a b l ew d m t r a n s p o r tn e t w o r k sb yi l pm e t h o d ，d e s i g no fr e s i l i e n tw d m m e s h n e t w o r k sa n d p r o t e c t i o n f o rw d mn e t w o r k sw i t h o u t c o n s i d e r i n gw a v e l e n g t h c o n t i n u i t yc o n s t r a i n tv i ae f f i c i e n t l yi n s t a l l i n gp - c y c l e s c h a p t e r1 ：w d mn e t w o r kw i l lp l a yi m p o r t a n tr o l ei nf u t u r eb a c k b o n en e t w o r k s i ti sn e c e s s a r yt h a tw d mn e t w o r k sh a v et h ec a p a b i l i t ya g a i n s tc o m p o n e n tf a i l u r ea n d o fs u p p o r t i n gq o s ，o u rd i s c u s s i o nc o n s i s t so f3m a i nc o m p o n e n t s ：t h ei n s t a l l a t i o no f p r o t e c t i o n s ，i l po fr w ai s s u ea n dan e wo p t i m i z a t i o nm e t h o di nw d mn e t w o r k s ， w h i c hi sc a l l e dl i h g tt r a i l c h a p t e r2 ：s e v e r a lp r o t e c t i o nm e t h o d sw o u l db ed i s c u s s e di nt h i sc h a p t e r , i no d e r t om a k eac o n c l u s i o na m o n gt h e i rp e r f o r m a n c e t w os c e n a r i o sa r ep r o p o s e di nt h i s c h a p t e r ：s u p p o r t i n g q o s a n d j o i n t e dr o u t i n g o p t i m i z a t i o n i n t h e g r a n u l a r i t y o f f i b e r i ti sn o tp r a c t i c a lt os u p p l yf u l lw a v e l e n g t hc o n v e r t e ri nan e t w o r kb e c a u s eo fs o m e p r o b l e ms u c ha sl o n gp r i c ea n dc o m p l e xt e c h n i q u e s s on ow a v e l e n g t hc o n v e r t e r f n w c ) a n ds p a r ew a v e l e n g t hc o n v e r t e r ( s w c ) a r ec o n s i d e r e di no u rf o l l o w i n g c h a p t e r c h a p t e r3 ：p r o t o t y p eo fi l pm o d e lo fs t a t i cr w ai s s u ei sp r o p o s e dh e r e t h e p r o t o t y p ec a nb ee x p a n d e de a s i l yf o rm a n yu s a g e ss u c ha sm u l t i c o n s t r a i n t sr o u t i n g 1 1 1 电子科技大学硕士论文 a n dp r o t e c t i o n c h a p t e r4 ：an e ws o l u t i o nf o ri pb u r s ts e r v i c ei si n t r o d u c e da n di n s t a l l e di t so w n i l pm o d e li nt h i sc h a p t e r a l s oi t ss u r v i v a b l ed e s i g ni sd e m e n t i o n e d w ep r o t e c t i i g h t t r a i li nac o n e c t i o nb a s e d w a y 2m a i nm e t h o d sa r eu s e di no u rs i m u l a t i o n s ：l i n 9 0 8a n dc + + t h er e s u l t so f c h a p t e r2c 0 1 t i ef r o mc + + a n dl i n 9 0 8 ，p r o t o t y p e sa r ed e s i g n e do nl i n g o8 0 ，s od o e st h e o u t c o m i n go f 卫 a n dt h el a s ti ss u m m a r i z i n go f t h i sd i s s e r t a t i o n k e y w o r d s ：w d mo n ，r w a ，s u r v i v a b i l i t y , p r o t e c t i o n ，i l p i v 简略字表 简略字表 d w d m d e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g 密集波分复用技术 w d m o x c i e t f i s p o b s q o s s d h i l p r 纬z s r l g s p w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g 波分复用技术 o p t i c a lc r o s sc o n n e c t 光交叉连接 i n t e m e te n g i n e e r i n gt a s kf o r c e因特网工程任务组 i n t e m e ts e r v i c ep r o v i d e r 因特网服务提供商 o p t i c a lb u r s t - s w i t c h i n g q u a l i t yo f s e r v i c e s 光突发交换 服务质量 s y n c h r o n o u sd i g i t a lh i e r a r c h y 同步数字系列 i n t e g e rl i n e a rp r o g r a m m i n g 整数线性规划 r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t 路由与波长分配 s h a r e dr i s kl i n kg r o u p s 共享风险链路组 s h a r e d p r o t e c t i o n d pd e d i c a t e d p r o t e c t i o n v i i i 共享保护 专用保护 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。； 签名：龛螽& 日期：声石年f 月弗日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：越导师签名： 日期：川与年，月“日 第一章绪论 第一章绪论 1 1 w d m 光传送网出现的历史背景 全球网络用户的大量增长和大容量业务的发展使得带宽需求量成线性增长， 如何有效地增加骨干网的传输能力成为众多i n t e m e t 服务提供商( i n t e r n e ts e r v i c e p r o v i d e r ，i s p ) 必须面对的重要问题。虽然目前的骨干网多数己使用光纤链路来传 输数据，但是传统的s d h s o n e t ( s y n c h r o n o u sd i l g i t a lh i e r a r c h y s y n c h r o n o u s o p t i c a ln e t w o r k ) 技术只能以特定的传输速率( 如2 5 g b i t s ) 在光纤中的单个波长 通道上传输数据。单纯依靠增加单波长传输速率的方法，例如使用更高速的时分 复用( t i m ed i v i s i o nm u l t i p l e x i n g ，t d m ) 技术，将碰到诸如因传输速率逼近电层 处理极限而使设备成本迅速增加等问题。波分复用( w a v e l e n g t hd i v i s i o n m u l t i p l e x i n g ，w d m ) 技术可以充分利用光纤的低损耗带宽，在一根光纤中的不同 波长上异步、高速传输多种格式的信号。使用光分插复用器( o p t i c a la d d d r o p m u l t i p l e x e r ，o a d m ) 和光交叉连接( o p t i c a lc r o s s c o n n e c t ，o x c ) 的w d m 光传 送网将逐渐在骨干网中占据主导地位 1 ，2 】。 w d m 首先是作为一种传输技术提出的，它可以充分利用光纤的巨大带宽资 源( 多于5 0 t h z 的理论可用带宽【1 1 ) ，使一根光纤的传输容量比单波长传输时的 容量增加几倍、几十倍甚至几百倍。光纤链路中的波长通道对它承载数据的格式 是透明的，即与承载信号的速率和电调制方式无关，因此可以在一根光纤中的不 同波长上同时传输不同协议的数据( 包括模拟信号) ，这也是w d m 网络最重要的 特性之一，通常称为光透明性( o p t i c a l t r a n s p a r e n c y ) 。在网络扩充和发展中，w d m 技术是理想的扩容手段，也是引入宽带新业务的方便途径，即通过增加波长就可 以引入新业务或新容量【2 】。 目前点到点的w d m 传送技术已经成熟，并已应用于长途干线和海底光缆系 统。w d m 技术虽然能极大地增加线路的传输容量，但同时也对交换系统提出了 更高的要求。目前的电子交换的发展已逼近电子速率的极限，为解决电层交换瓶 颈的制约问题，引入光交换已成为必然。相对光分组交换( o p t i c a lp a c k e ts w i t c h i n g ) 而言，采用光路交换( o p t i c a lc i r c u i ts w i t c h i n g ) 的w d m 光传送网比较容易实现， 电子科技大学硕士学位论文 其特有的波长重用( w a v e l e n g t hr e u s e ) 能力也使之具有良好的可扩展性。因此采 用波长分配和路由选择的w d m 光传送网( o t n ，o p t i c a lt r a n s p o r t n e t w o r k ) 技术 被认为是未来骨干通信网向宽带、大容量发展的首选方案。 9 0 年代以来，w d m 光传送网已成为网络界的研究热点。早在9 0 年代初， 欧洲就已经在其r a c e ( 欧洲先进通信方式的研究与技术开发) 计划中将多波长 传送网列为研究目标。在后续的a c t s ( 先进的通信技术和服务) 计划中，又在欧 洲各地建立了一系列实验性的w d m 光传送网，如o p e n ，p h o t o n 和m e t o n 等 3 1 。美国在d a r p a ( 国防部高级研究计划局) 的资助下，组建了多个研究团 体，建立了一系列光传送实验网，如由a t & t 、b e l l c o r e 和朗讯科技牵头建设的 m o n e t ( 多波长光网络) 实验网，用于实验和验证各种新技术。1 9 9 7 年开始建设 并由加拿大政府资助的加拿大研究和教育i n t e m e t 骨干网( c a n a d ar e s e a r c ha n d e d u c a t i o ni n t e m e tb a c k b o n e ) c a + n e t 3 采用高速路由器和w d m 设备直接相连的 i p o v e r - w d m 结构，开创了光互联网( o p t i c a li n t e m e t w o r k i n g ) 建设的先例【4 】。国 际标准化组织i t u t 也正在积极制定有关光传送网的建议 5 1 。我国的一些研究机 构也开展了光传送网的研究工作【1 ，”。1 9 9 8 年5 月，国家自然科学基金委员会发 布了重大项目“w d m 全光网基础研究”，由我国的一些知名高校，如清华大学、 北京大学、北京邮电大学、上海交通大学和电子科技大学，以及其它一些单位共 同承担，将为我国全面推广w d m 光传送网技术奠定坚实的理论基础。1 9 9 9 年6 月，国家高技术项目智能计算机主题、光电子主题和通信主题联合提出实施“中 国高速信息示范网( c a i n o n e t ) ”研究开发项引”，建立一个基于光因特网技术 的高速信息网实验环境，为以光因特网技术为代表的先进网络技术的研究、开发 和测试提供一个实验平台。 从以上国内外的研究进展情况可以看出，基于w d m 技术的光传送网已在世 界范围内引起了广泛关注。在未来的一段时间里，人们将继续对光传送网的关键 技术进行全面、深入研究。这些关键技术包括：业务接入和一体化技术 ( i p o v e r - w d m ，s d h o v e r - w d m 等) ；光分插复用技术；光交叉连接技术；光放大 技术；全光的波长转换技术；波长选路和波长分配技术；光网络重构技术以及光 网络的管理和控制技术等。 1 2w d m 技术实现简述 单模光纤的低损耗波长范围大约在1 2 岫一1 6 9 m ，对应相当于5 0 t h z 以上 笙二雯笪笙 的光纤带宽。如果端用户的光收发器( 1 a s e rt r a n s c e i v e r s ) 足够稳定并且发射的光 信号的波长不会漂移标称操作波长太多，那么相邻信道的间隔可以做得相当小， 其最小值和信道间的信号串扰( c r o s s t a l k ) 特性有关。采用d f b ( d i s t r i b u t e d f e e d b a c k ) 、d b r ( d i s t r i b u t e d b r a g g r e f l e c t o r ) 或者其它窄线宽的激光 器，可以获得小于或等于1n l t l 的信道间隔，这样的波分复用系统通常称为密集 波分复用( d e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ，d w d m ) 系统。如没有特别说 明，本文中的w d m 都是指密集波分复用d w d m 。 w d m 技术的一个重要特性是各个波长信道可以独立地进行路由、交换，互 不影响。为了建造一个高效的w d m 网络，端用户必须具备向多个w d m 信道注 入信号或从多个w d m 信道中抽出期望信号的能力。因此，工作范围大、调节速 度快的可调光收发器的设计和实现显得尤为重要。目前已有的可调光收发器可 以基于激光的机械调节、热调节、声光调节、电调节和注入电流调节。热调节光 收发器的波长可调范围为1n r n ，机械调节的光收发器的波长可调范围可以达到 1 0 0m t l 。这些光收发器的信道切换速度在几个毫秒，利用调节注入电流来选择信 道的半导体光收发器可以有更快的信道切换速度，但是可调节的波长范围不是太 宽。可调光滤波器可以分为无源滤波器和有源滤波器。无源滤波器的优点是容易 实现、可以进行很精细的滤波( 特别是f a b r y - p e r o t 滤波器) ，存在的主要缺点是调 节速度太慢( 达到毫秒的数量级) 。基于发光二极管放大器的有源滤波器可以获得 纳秒级的调节速度，但是能够分辨的波长信道数有限。设计和建造光通信网的另 一种重要器件是光放大器，它们可以直接再生光信号而无需光一电转换，并且可以 同时对数条波长信道的信号放大而无需解复用。工作在1 5 岫，带宽达到3 5n l n 的掺铒光纤放大器( e r b i u m d o p e df i b e ra m p l i f i e r s ，e d f a s ) 使长距离传送光信号 领域发生了重大变革一光信号可以传送很远的距离。有实验报道，2 0 信道、每信 道容量5 g b s 的w d m 系统的传输距离达到了9 1 0 0 k m 。 如果是构建基于w d m 技术的光网络，而不仅仅只是点到点的传输系统，最 重要的还是具备波长选路和交换功能的节点设备，如装配光交叉连接设备的波长 路由节点。有关这方面的细节将在本文下面关于光传送网的章节中近一步阐述。 1 3w d m 光传送网概述 光纤目前被广泛认为是长距离、大容量传送信息最有效的物理介质。最近掺 铒光纤放大器( e r b i u m d o p e df i b e ra m p l i f i e r s ，e d f a s ) 技术方面的新进展使得在 电子科技大学硕士学位论文 长距离上波分复用地透明传送大容量的数据成为可能。到目前为止，多家已投入 商用的w d m 产品都是用于点到点的数据传输，主要都是针对骨干网。但是，这 种w d m 的点到点应用只能单纯地增加光纤链路的传输容量，而不能增加全网的 吞吐能力，原因是数据的路由和交换仍然是在电领域中完成的，当网络承载的数 据量很大时，这种路由方式很容易使某些网络节点中的电层设备成为数据传输的 瓶颈。因此，在光领域中完成路由和交换的思想应运而生。直接在光领域中完成 分组级的交换，目前仍然受成本和技术方面的一些问题制约，最主要的问题是 缺少光随机访问存储介质，并且光分组头的同步也很困难【“】。因而有望在短时期 内商用的是基于光路交换的w d m 光传送网。 w d m 光传送网目前主要有两种形式：广播与选择网( b r o a d c a s t a n d s e l e c t o p t i c a ln e t w o r k s ，b s o n s ) 和波长选路网( w a v e l e n g t hr o u t e do p t i c a ln e t w o r k s ， w r o n s ) 。b s o n s 的物理拓扑是星形，中心节点使用无源光耦合器0 a s s i v eo p t i c a l c o u p l e r ) 进行光信号的复合和分离( c o m b i n a t i o na n ds p l i t ) ，其它每个网络节点和 中心节点之间都有一条光纤链路相连。节点间进行通信时，源节点产生的信号会 被中心节点向其它所有节点广播，目的节点使用光滤波器选择出希望接收的信号。 因为固有的星形结构，使得b s o n s 缺乏波长重用( w a v e l e n g t hr e u s e ) 的能力， 全网需要的波长数n x 等于需要建立的光通道数，通常与网络中节点的数目n ( 不 包括中心节点) 相当。当网络节点数n 增加时，b s o n s 会暴露出以下弱点：( 1 ) 中心节点只有广播信号的能力，因而信号接收端需要在所有到达的信号中选择希 望得到信号，这使系统对激光器和光滤波器的稳定性要求会很严格；( 2 ) 由于中 心节点对光信号的分路和广播，每个接收节点收到的信号功率只有原信号的1 n ， 当n 较大时会使节点收到的信号功率大大下降；( 3 ) 虽然收发信号节点的失效不 会危及全网的通信，可是中心节点的失效会使网络陷于瘫痪并且无法自动恢复。 基于这些限制，b s o n s 只适用于节点数较少并且对网络生存性的要求不是特别高 的局域网或城域网。主要用于长距离、大范围骨干网的w r o n s ，考虑到铺设光 纤的高成本，网络节点之间一般用点到点的光纤链路任意相连而构成连接度较低 的网状网。波长选路机制支持网络节点间建立端到端的光领域通道，一般称为光 路( 1 i g h t p a t h ) 。在这种情况下，波分复用带来的巨大好处可以通过光领域中的波 长选路得到充分体现：( 1 ) 在w r o n s 中，光路信号不会被广播，而是沿选定的 路由传送信号，这样同一波长可以应用在网络的不同部分，全网使用的波长数n k 大大减少，而的大小和网络的建设成本密切相关；( 2 ) 消除了b s o n s 中存在 的1 n 倍功率分离问题，接收端对光滤波器性能的要求也可以降低不少，因为只 第一章绪论 有特定光路的信号抵达接收节点；( 3 ) 高层网络( 如s d h 、a t m 或i p ) 的数据将 在光路中尽可能远地传送，只有在必要的时候才进行电层的存储转发或交换( 例 如通信的源目的节点对之间没有光路直接相连) ，这样可以大大提高网络的数据 吞吐能力、简化网络管理和减少电层的网络设备；( 4 ) w r o n s 可以在光层提供基 于光路的保护恢复机制以防止物理网络的链路节点失效，这样做的好处是只需 要在网络中预留少量的大容量光路资源就可以构建具备相当抗毁能力的传送网 络，而毋需象传统数据网络在电层重新配置大量低带宽的数据通道，从而恢复速 度快( 几十毫秒以内) 和恢复效率高，网络配置的复杂性也降低了。因此基于光 路交换的w r o n s 非常适合于在覆盖区域较大的广域骨干网中使用。本文的研究 都是针对这种具有波长选路功能的w r o n s 。在现阶段，这种w d m 光网络主要 作为各类数据业务( 如s d h 帧、a t m 信元或i p 分组) 的传送平台，因此也被称 为w d m 光传送网。 图1 1 波长选路的w d m 光传送网示意图 图1 - 1 所示是波长选路的w d m 光传送网示意图。网络节点被称为波长路由 节点( w a v e l e n g t h r o u t e dn o d e s ，w r n s ) 或光交叉连接( o p t i c a lc r o s s c o n n e c t ， o x c ) 。若将输入波长信号转换到不同的输出波长上，称为波长转换( w a v e l e n g t h c o n v e r s i o no rw a v e l e n g t ht r a n s l a t i o n ) ，波长转换需要引入额外的代价，技术实现 也比较复杂。无波长转换能力的路由节点称为波长选择交叉连接器 ( w a v e l e n g t h s e l e c t i v ec r o s s c o n n e c t ，w s x c ) ，有波长转换能力的路由节点叫波长 转换交叉连接器( w a v e l e n g t hi n t e r c h a n g i n gc r o s s c o n n e c t ，w k x c ) 。路由节点x 、 y 通过光纤互连，接入节点a b c d e 通过光纤连接到路由节点。在接入节点，多 个端用户( e n d u s e r ) 可复接到同一波长信道。通常情况下我们将路由节点和与之相 连的接入节点看作一个整体，通称为网络节点。图1 2 所示为一种w s x c 的原理 图。任一输入光纤上的任一波长信号可以经过解复用器( d e m u l t i p l e x e r ) 解复用、 电子科技大学硕士学位论文 相应波长的光空分交换器交换，最后复用( m u l t i p l e x i n g ) 输出到任一输出光纤的 同一波长上。利用w s x c 就能在不同的端用户之间建立端到端的光路。当路由节 点没有波长转换能力时，光路必须在其路由经过的光纤链路上使用同一波长，如 图1 1 中a 到c 的光路采用九2 ，d 到e 和a 到b 采用九l ，这一限制称为波长连续 性限制( w a v e l e n g t hc o n t i n u i t yc o n s t r a i n t ) 。波长连续性限制也是波长路由网络区 别于传统的电路交换( c i r c u i ts w i t c h e d ) 网络的特性之一。 输入光纤 2 n 2 输出光纤 n 图1 2 波长选择光交叉连接器结构示意图 在很多文献中【1 3 ，1 2 ，这种含有不同波长的光路被称为虚光路( v i r t u a l w a v e l e n g t hp a t h ，v 、p ) ，而相应的遵守波长连续性限制的光路则被称为w p ( w a v e l e n g t hp a t h ) 。在w s x c 的光空分交换器的输入或输出端口配置波长变换器， 就可以得到具有波长变换能力的w i x c 。如果路由节点都是w l x c ，并且都能实 现任意输入波长到任意输出波长的全范围波长变换( f u l l r a n g ew a v e l e n g t h c o n v e r s i o n ) ，则相应的w d m 网络模型等价于传统的电路交换网络。 ( a ) 无波长变换 ( b ) 有波长变换 第一苹绪论 图1 - 3 波长连续性限制造成的波长冲突 除o x c 外，目前已广泛使用的一种具有波长选路功能的w d m 设备是光分 插复用器( o p t i c ma d d d r o pm u l t i p l e x e r , o a d m ) 。o a d m 的作用是从光纤的众多 波长中解出任意一路，或者向光纤中加入新的波长，其结构如图1 4 所示。o a d m 为w d m 光传送网提供了异步接入的功能，使得光网络设备可以提供与各种业务 的直接接口。 卒分交换 图1 - 4o a d m 功能框图 光传送网是在光领域对客户信号提供传送、复用、选路、监控和生存性功能 的综合实体。i t u tg 8 7 2 建议( 草案) 已明确在光传送网加入光层( o p t i c a l l a y e r ) ，按照建议，光层由光信道层、光复用段层和光传输段层组成 1 4 1 ，如图 1 5 所示。光信道层( o p i t c a lc h a n n e ll a y e r ，o c h ) 负责为来自电复用段层的各种 电路层电路层 虚通道 p d h 通道层s d h 通道层虚通道 电复用段层电复用段层( 没有) 光信道层o c h 光复用段层o m s 光传输段层o t s 物理层( 各种光纤，如g 6 5 2 ，g 6 5 3 ，g 6 5 5 等) 图1 - 5 光传送网分层结构示意图 格式的客户信号( 如s d h 、a t m 、i p ) 建立端到端的光信道连接( 光路) ，包 7 电子科技大学硕士学位论文 括选路和波长分配，处理光信道开销，提供光信道层的检测和管理功能，并在故 障发生时，通过重选路由或直接把工作业务切换到预留的保护路由来实现保护倒 换和网络恢复。光复用段层( o p f i c a lm u l t i p l e x i n gs e c t i o n l a y e r , o m s ) 保证相邻两 个波长复用传输设备间多波长复用光信号的完整传输，为多波长信号提供网络功 能，包括：为灵活的多波长网络选路重新安排光复用段功能：为保证多波长光复 用段适配信息的完整性处理光复用段开销；为网络的运行和维护提供光复用段的 检测和管理功能。光传输段层( o p t i c a lt r a n s m i s s i o ns e c t i o nl a y e r , o t s ) 为光信号 在各种类型的光传输媒质( 如g 6 5 2 ，g 6 5 3 ，g 6 5 5 光纤等) 上提供传输功能，同时 实现对光放大器或中继器的检测和控制功能等。 1 4w r o n s 研究中关注的问题 1 4 1 选路和波长分配算法 给定一组光路连接，通过波长选路和波长分配算法来建立相应光路的问题称 为选路和波长分配( r o u t i n ga n dw a v e l e n g t h a s s i g n m e n t ，r w a ) 问题。最典型的连 接请求有三种业务类型：静态类型( s t a t i c ) 、增长类型( i n c r e m e n t a l ) 和动态类型 ( d y n a m i c ) 。静态业务是指节点间的所有连接请求已事先知道，此时r w a 问题需 要解决的是从全局优化的角度为所有连接请求建立光路，优化的准则可以是在满 足所有连接请求的前提下使用最少的波长或光纤，或者在波长光纤数目给定的前 提下满足尽可能多的连接请求。对应于静态业务的r w a 问题也被称为静态光路 建立( s t a t i cl i g h t p a t he s t a b l i s h m e n t ，s l e ) 问题。增长型业务是指连接请求顺序到 达网络，建立的光路和连接请求一一对应，光路一旦建立将永远存在。对于动态 业务，连接请求随机、顺序到达网络，光路建立后维持一段有限时间后会拆除。 增长型业务和动态业务下的r w a 问题的目标一般是有效地选择光路路由和合理 分配波长资源，以使光路的阻塞率最低。此时的r w a 问题也称为动态光路建立 ( d y n a m i cl i g h t p a t he s t a b l i s h m e n t ，d l e ) 问题。 静态r w a 算法 在s l e 问题中，因为需要满足哪些光路需求是预先知道的，所以光路的选路 和波长分配都是用离线( o f f - l i n e ) 方式完成。典型的优化目标可以是：在物理拓 扑和所有连接请求给定的情况下，使用最少的波长或光纤建立光路，以满足所有 第一章绪论 的连接请求。优化目标也可以是：在物理拓扑和网络中可用的波长数给定的情况 下，建立尽可能多的光路以使连接请求的阻塞率最低。在解决后优化问题的时 候，可能会引发“公平性”的问题，即得到的解可能会更多地满足短距离的连接 请求( 短距离一般指经过的物理链路少) ，而长距离的连接请求在波长资源不足时 可能总是被阻塞，这一附加问题往往需要加入公平性策略来解决。 静态r w a 问题还可以根据不同准则进一步分类，根据虚拓扑支持的上层业 务可以分为两类：支持电路交换业务的静态r w a 问题和支持分组交换业务的虚 拓扑设计问题。前者的业务需求矩阵给出了每对节点间需要支持的光路数，而后 者的业务需求矩阵中存放的则是节点对间归一化的平均分组业务强度。虚拓扑 ( v i r t u a lt o p o l o g y ) 是指静态r w a 问题求解之后得到的所有光路路由构成的一个 逻辑上的网络拓扑，文献中也常称为w d m 网络的逻辑拓扑( l o g i c a lt o p o l o g y ) 。 虚拓扑设计问题可能的优化目标可以是平均分组延时最小或网络的扩展因子 ( s c a l e u pf a c t o r ) 最大。在为连接请求建立光路或进行虚拓扑设计时，很多时候必 须考虑网络的抗毁能力，尤其在设计大型的骨干网时更是如此。因此这一问题和 r w a 问题是密切相关的。 支持电路交换业务的静态r w a 算法 考虑波长连续性限制的s l e 问题通常可以用整数线形规划( i n t e g e rl i n e a r p r o g r a m m i n g ，r a p ) 的方法来描述。典型的目标函数可以是全网使用的波长数最少 等。静态r w a 问题的正式描述已经在很多文献中给出，s l e 问题也已被证明是 n p c 问题，换句话说就是当网络规模较大时，使用直接求解的方法无法在合理 的时间内得到最优解，所以我们不得不使用各种各样的启发式算法( h e u r i s t i c ) 来 得到问题的次最优解。同时解决选路和波长分配问题一般比较困难，通常的做法 是将r w a 问题拆分成选路子问题和波长分配子问题，然后分别解决。 静态选路算法一般分为两类：固定选路( f i x e dr o u t i n g ) 算法和备用选路 ( a l t e r n a t er o u t i n g ) 算法。前者在为给定源目的节点的连接建立光路时，只选择 一条相同的固定路由，通常是使用d i j k s t r a 算法或b e l l m a n f o r d 算法根据代价最 小( 物理链路的代价根据关心的指标不同可以有多种定义方式) 准则得到的最短 路径f s h o r t e s t - p a t h ) 。后者在一对节点之间建立光路时，会考虑这对节点之间存 在的多条可能的路由，通常是k 条最短路由，然后根据链路的可用波长资源情况 和优化目标选择其中的一条作为待建立光路的路由。 固定选路算法实现起来最简单，因为路由在求解r w a 问题之前已经可以确 定，此时网络性能主要受波长分配算法的影响。固定选路算法存在的缺点也是显 电子科技大学硕士学位论文 而易见的，如果固定路由经过的物理链路上没有可用资源( 波长) ，就只有依靠增 加链路上的可用波长来解决建立光路的问题，这会使链路需要支持的可用波长数 比较大，另一个潜在问题是波长的利用率很低，原因是网络在建设时，往往选用 同样波长数的光纤链路，而固定选路算法的负载均衡能力很差，最后的结果是某 些链路的波长都被使用，而其它一些链路上存在大量的未使用波长。备用选路算 法比固定选路算法灵活很多，可以应付多种情况。最简单的波长分配算法是随机 波长分配算法：从空闲波长集中随机挑选一条可用波长分配给光路，不考虑光路 的长度( 经过的物理链路数) 和网络的状态。但是如果存在波长连续性限制( 网络 节点缺乏波长转换能力) ，该方法会导致长光路较短光路更易被阻塞。文献 1 5 中 提出了“长路优先”策略：按光路长度递减的顺序，反复尝试将已有波长分配给 所有可能的不相邻光路( 不相邻指不经过公共的物理链路) ，当且仅当无法用已 有的波长建立光路时才增加新的波长。通过对长光路的优先处理，可以提高波长 的重用率，降低支持给定光路集所需的波长数。对于每条链路支持的光纤数都相 同的多光纤w d m 网，为了减少所需的光纤数，文献 1 6 】在分