（通信与信息系统专业论文）wdm光网络中的路由和波长分配算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着网络技术的发展以及新的i n t e m e t 应用的出现，全球i n t e r n e t 业务呈现 出爆炸式增长的趋势，迫切要求扩大广域骨干通信网的容量。波分复用技术 ( w d m ) 允许在一根光纤中同时传输若干路不同波长的光信号，具有实现简单 和易于扩展的特点，是目前充分利用光纤容量的方法中最具吸引力的候选者。 优化光通道的选路和波长分配( r w a ) 是网络设计的核心问题，其主要任 务是寻找一条合适的光路并为之合理地分配波长，使有限的资源充分发挥作用， 以提供尽可能大的通信容量。本文首先介绍了r w a 问题的相关概念及常见算法； 其次通过对几种典型波长分配算法的优化目标表达式进行比较和分析，在无波长 转换条件下，对文献中现有的阻塞率性能最好的相对容量影响算法作了改进，并 给出了一种链路代价定义策略，仿真检验了使用这种链路代价定义策略的备选路 由及改进的波长分配算法的r w a 的有效性；最后分别对业务优先级和网络公平 性问题进行了研究，并且给出了一种基于优先级的波长分配算法及一种综合考虑 公平性和优先级的波长分配算法，这两种算法分别是对动态门限法的不同角度的 改进，所以能够在满足服务质量( q u a l i t yo f s e r v i c e ，q o s ) 约束的条件下降低网 络的阻塞率。 本文所提路由和波长分配算法通过均衡负载，取得了比文献中已有的部分算 法更低的网络阻塞率，支持业务的多优先级，通过适当增加短跳光路的阻塞率， 显著降低了长跳光路的阻塞率，改善了网络的公平性。 关键词：w d m 光网络；路由与波长分配；链路代价； 多优先级；公平性； 阻塞概率 西南交通大学硕士研究生学位论文第页 a b s t r a c t w i t l lt 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 r n 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 di ni n t e r a c tt r a f f i c ，w h i c hi s p r o m o t i n gt h e c o n s t r u c t i o no fb r o a d b a n db a c k b o n en e t w o r k 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 ( w d m ) i sap r o m i s i n g a p p r o a c ht h a tc a nu s et h ee n o r m o u sb a n d w i d t ho ft h eo p t i c a l t 胁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 ss 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 r r ec o n s i d e r e da st h et r a n s p o r t n e t w o r k sf o rt h ef u t u r e ak e yi s s u ei nn e t w o r k sd e s i g ni st oo p t i m i z er 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 ) f o rl i g h t p a t h s r w as o l v e sh o wt of r e do u ta l la p p r o p r i a t e l i g h t p a t ha n da s s i g naw a v e l e n g t hr e a s o n a b l yi no r d e rt om a k ef u l lu s eo f t h el i m i t e d r e s o u r c ea n dp r o v i d ec o m m u n i c a t i o nc a p a b i l i t ya sl a r g ea sp o s s i b l e i nt h i st h e s i s ， f i r s t l y , t h eb a s i cc o n c e p t i o n sa n de x i g i n ga l g o r i t h m sf o rr w ap r o b l e ma l ei n t r o d u c e d s e c o n d l y ，b yc o m p a r i n ga n da n a l y s i s i n gt h ee x p r e s s i o no fo p t i m i z i n go b j e c to f s e v e r a lc l a s s i c a lw 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 m s ，i m p r o v e dt h er e l a t i v ec a p a c i t y i n f l u e n c ea l g o r i t h mw h i c hi st h eb e s to nb l o c k i n gp r o b a b i l i t yp e r f o r m a n c en o wu n d e r t h ec o n d i t i o no fn ow a v e l e n g t hc o n v e r t e 墙an e wl i n kc o s td e f i n i t i o ns t r a t e g yi sa l s o b ep r o p o s e da n dt h ee f f e c to f r o u t i n gs e l e c t i o na l g o r i t h ma c c o r d i n gt ot h en e wl i n k c o s td e f i n i t i o ns t r a t e g ya n dt h ei m p r o v e dw a v e l e n g t ha s s i g n m e n t a l g o r i t h m a r e e v a l u e dj o i n t l yb ys i m u l a t i o n t h i r d l y , t r a f f i cp r i o r i t ya n df a i r n e s so fn e t w o r ka l e s t u d i e d ，ap 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 ma n do t h e ra l g o r i t h mi n w h i c hp r i o r i t ya n df a i r n e s sa l ec o n s i d e r e di n t e g r e t i l ya r ep r o p o s e d t h e s et w o a l g o r i t h mi m p r o v e dt h ed y n 锄i ct h r e s h o l da l g o r i t h mf r o md i f f e r e n ta n g l e s s ot h e y 西南交通大学硕士研究生学位论文第1 i i 页 c 龇d e c r e a s et h eb l o c k i n gp r o b a b i l i t ya n df i tt h eq o sc o n s t r a i n t s t h ep r o p o s e dr w aa l g o r i t h m si nt h i st h e s i sc a na c h i e v el o w e rb l o c k i n g p r o b a b i l i t yt h a ns o m ea l g o r i t h m se x i s t e di nl i t e r a t u r e sa n ds u p p o r tp r i o r i t i e so f t r a f f i c t h ea l g o r i t h mc a ni m p r o v et h ef a i r n e s so fn e t w o r k sb yi n c r e a s i n gt h eb l o c k i n g p r o b a b i l i t yo fs h o r t e rh o pl i g h t p a t h sa n dd e c r e a s i n gt h eb l o c k i n gp r o b a b i l i t yo f l o n g c r h o pl i g h t p a t h s k e yw o r d s = w d mo p t i c a ln e t w o r k s ；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 ； l i n kc o s t ；m u l t i p l ep r i o r i t i e s ；f a i r n e s s ；b l o c k i n gp r o b a b i l i t y 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1w d m 技术与w 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 i n 技术最为成熟“1 。 光波分复用是光纤通信中的一种传输技术，它利用了一根光纤可以同时传输 多个不同波长的光载波的特点，把光纤可能应用的波长范围划分成若干个波段， 每个波段用作一个独立的通道传输一种预定波长的光信号。 光波分复用的实质是在光纤上进行光频分复用，只是因为光波通常采用波长 而不用频率来描述、监测与控制。在波分复用技术高度发展，以及每个光载波占 用的频度极窄，光源发光频率极其精确的前提下，或许使用光频分复用来描述更 恰当些。波分复用技术的基本原理是在传输系统的发送端采用复用器将不同波长 的光信号组合起来进行复用，并把信号耦合到光缆线路的一根光纤中进行传输， 在接收端采用解复用器分离出不同波长的光信号，并把恢复出的信号送入不同的 终端。图1 1 为波分复用原理图。波分复用通信传输系统主要有双纤单向传输和 单纤双向传输两种结构。1 。在双纤单向传输系统中，所有的光通路同时在一根光 纤上沿同一方向传送，反方向通过另一根光纤传输。而在单纤双向传输系统中， 光通路在一根光纤上同时向两个不同方向传输，所有波长相互分开，以实现彼此 双方全双工的通信联络。单向的w d m 系统在开发和应用方面都比较广泛双 西南交通大学硕士研究生学位论文第2 页 向w d m 系统得开发和应用相对来说要求更高，这是由于双向w d m 系统在设 计和应用时必须考虑到几个关键的系统因素，如要抑制多通道干扰，同时要使用 双向光纤放大器。 图1 1 波分复用原理图 w d m 技术具有的主要特点0 1 ： 1 ) 可以利用光纤的巨大带宽资源，使一根光纤的传输容量比单波长传输增加几 倍至几十倍。w d m 技术可以充分利用单模光纤的巨大带宽，从而一劳永逸 地解决传输的带宽问题。 2 ) w d m 系统多用于大容量长距离传输，以便多信道复用光放大器，简化系统 结构和设计，减少投资和维护费用。 3 ) 使n 个波长复用起来在单模光纤中传输，则在大容量长途传输时可以节约大 量光纤。另外，对于早期安装的芯数不多的光缆，利用w d m 技术可以不必 对原有系统做较大的改动，进行扩容比较方便。 4 ) 由于同一光纤中传输的信号波长彼此独立，因而可以传输特性完全不同的信 号，完成各种电信业务的综合和分离，包括数字信号和模拟信号，以及p d h 信号和s d h 信号的综合与分离。 5 ) w d m 技术对数据格式是透明的，即与信号速率及电调制方式无关。一个w d m 西南交通大学硕士研究生学位论文第3 页 系统可以承载多种格式的“业务”信号，以及a t m 、i p 或者将来有可能出 现的信号。w d m 系统完成的是透明传输，对于“业务”层信号来说，w d m 的每个波长就像“虚拟”的光纤一样。 6 ) 在网络扩充和发展中，w d m 是理想的扩容手段，也是引入宽带业务的方便 手段，增加一个附加波长即可引入任意想要的新业务和新容量。 7 ) 利用w d m 技术选路来实现网络的交换和恢复，从而可以实现未来透明的， 具有高度生存性的光网络。 8 ) w d m 系统可方便地增加波长信道，既有利于实现网络的光交换和恢复，又 有利于网络扩容升级，从而可进一步实现适用未来需求的、透明的、有高度 生存性的光网络。 这里可以将一根光纤看作是一个“多车道”的公用道路，传统的e t d m 系 统只不过利用了这条道路上的一条车道，提高比特率相当于在该车道上加快行驶 速度来增加单位时间内的运输量。而使用w d m 技术，类似于利用公用道路上 尚未使用的车道，以获取光纤中未开发的巨大传输能力。 1 1 2w d m 光网络的产生背景 w d m 光网络的产生主要有如下几个原因： 1 ) 新型业务对光纤带宽的无限渴求。以i p 业务为代表的新型数据业务的急 剧增长，给传统的电信基础设施的通信容量造成巨大的压力，导致的直 接后果是出现了所谓“带宽耗尽”现象和对光纤带宽的“无限渴望“。 2 ) 现存网络中光纤带宽的极大浪费。由于“最后一千米”( 即所谓的接入网 部分，它是高速光缆骨干网和用户终端的桥梁) 现在依然处于相对原始的 阶段以及地下的光缆没有组成一种有效的结构形式使得对于新的带宽业 务无法充分利用它们的巨大带宽容量，因此虽然今天使用的大多数电信 网在某些地方拥有属于自己的光缆，但还不足以能够把它们建成光网络 西南交通大学硕士研究生学位论文第4 页 3 ) 商业驱动加快了光网络的发展。因特网业务和其他数据业务的爆炸式增 长，以及与目前这种网络发展趋势不相适应的电信产业都为电信网络运 营商提供了一种全新的商业机会和挑战。另一方面，通信业务的不断增 长和残酷的商业竞争所带来的压力，驱动了运营商必须以低成本来增加 带宽。因为采用w d m 技术对现有系统扩容与敷设新光缆增加通信容量 相比的费用，前者是后者的3 0 5 0 。所以波分复用技术对网络的升 级扩容、发展带宽新业务、充分挖掘和利用光纤带宽能力实现超高速通 信具有十分重要的意义。 4 ) 建设光网络的时代已经成熟。体现在支持光网络的技术正在飞快进步。 目前最重要的发展是掺饵光纤放大器( e d f a ) 的商用化和点到点w d m 系统己广泛应用于许多网络提供商。与波分复用传输系统相关的一个 迅速膨胀的市场需求已在运营者之间出现，运营商们都需要增加系统容 量来满足带宽业务日益增长的需求。多波长宽带网这种新型网络体系 架构正是支持“井喷式”增长i n t e m e t 业务和其他广域网( m 州) 业务所 必不可少的和必须依赖的理想网络结构体系 虽然光纤已渗透到了电信网的接入网、本地网、接入中继网、长途干线网( 骨 干网) 之中，但由于价格和用户所需带宽问题，目前光缆接入到户还做不到。在 这些网络中，光缆只是用来代替同轴电缆，单纯用做传输媒介即实现了节点之间 链路的光化，而节点对信号的处理、交换等还是采用电子技术，称这类网络为第 一代光网络即光电混合网。 当数据速率越来越高时，采用电子技术处理交换节点的数据速率是相当困难 的。节点处理的数据不仅有到达自身的，还有通过该节点到达其他节点的，如果 到达其他节点的数据能在光域选路由，则电子技术处理的数据速率就下降了，其 负担就小得多了，这导致了第二代光网络即全光网络的诞生。第二代光网络以在 光域完成节点数据的选路与交换为标志，实现了网络节点的部分光化鲫 西南交通大学硕士研究生学位论文第5 页 以波分复用为基础的光网络近几年内发展很快，被用于海底、陆地长途干线、 本地网甚至接入网，因此w d m 光网络已成了全光网络的代名词，提起光网络 都是指w d m 光网络。 光网络除了执行在光域上光选路由和光交换之外还需要执行信号检测、再 生、缓存和一些逻辑功能( 分组头识别等) ，以目前的技术在光域上执行这些操作 是困难的，因而这样的光网络使其透明性下降，这也是目前意义上的光网络。 1 1 3w d m 网络的结构体系 在大范围的w d m 全光网中，其总体网络结构一般由三级组成。0 级为数量 很大的光纤局域网；l 级为以城市或行政区为单位的光纤城域网，跨度一般为几 公里至几十公里；2 级为广域网或全国范围的骨干网，跨度一般为几百至几千公 里( 如图1 2 所示) 。其中不同级的网络拥有不同的波长集，同级但互不相交的子 网可使用相同的波长集。这与当前信号的状况是相适应的。各省问中心、省中心 可以构成2 级的长途传输网，而各地区中心则可构成1 级的本地网，在2 级与l 级的边界处利用波长转换技术，则可以提高网络波长的利用率。 o t ：光终端，：y 6 缆 图1 2w d m 全光网的分级结构 对于各级网络来说采用的结构也不尽相同。对0 级的局域网来说，一般网径 较小，传输延迟小，数据吞吐量要求高。因而常采用星形结构，网中用户可以采 西南交通大学硕士研究生学位论文第6 页 用单一波长，也可以采用多波长，用户间采用媒质控制协议来解决共享资源的问 题。对于l 级城域网，它要将许多0 级子网连接起来，网络中等，但传输速率要 求较高，一般采用环形结构较多。对于2 级广域网，它的网径大，传输延迟长， 一般采用网状结构。 按照g 8 0 5 建议的原则”，光传送网的主要功能是为用户传送高比特数据信 息。从功能角度，它可以分为电子层、光层和物理媒介层。电子层包含了电路交 换层和电子通道层。光层则包含了光信道子层、光段层。其中，光段层要进一步 细分为光复用段层和光传输段层，如图1 3 所示。 电路层 田 j痢 高电通道层 鹾 l 订 光信道( o c h ) 层 亦。 光复用段( o m s ) 层 i | | | 1 等 巷 ； 渝 质 光传输段( o t s ) 层 ；研 物理媒质层 图1 3w d m 光传送网的功能分层模块图 光信道层( o c h ) 网络为透明地传递各种不同格式的客户层信号的光通路提 供端到端的联网功能。光通路层的主要传送实体有网络连接、链路连接、子网连 接和路径。因此具有如下功能光通路连接的重组，以便实现灵活的网络选路： 光通路开销处理，以便确保光通路适配信息的完整性；光通路监控，以便实 现网络等级上的操作和管理功能，诸如连接指配、业务参数交换的质量以及网络 的生存性。 光复用段层( o m s ) 网络为多波长光信号提供联网功能，主要传送实体有网 络连接、链路连接和路径。因此具有如下功能光复用段开销处理，以便确保多 波长光复用段适配信息的完整性；光复用段监控功能，以便实现复用段层上的 西南交通大学硕士研究生学位论文第7 页 操作和管理功能，如复用段生存性等。 光传输段层( o t s ) 网络为光信号在各种不同类型光传输媒质上提供传输功 能，主要传送实体有网络连接、链路连接、子网连接和路径。因此具有如下功能 光传输段开销处理，以便确保光传输段适配信息的完整性：光传输段监控功 能，以便实现传输段层上的操作和管理功能，如传输段的生存性等 整个光传送网由最下面的物理媒质层网络所支持，物理媒质层网络是光传输 段的服务者，即为各种规定类型的光纤。 1 2w d m 波长路由网络 从光网络选路方式上划分有两种典型的网络结构忉：广播与选择网( b r o a d c a s t a n ds e l e c tn e t w o r k ) 以及波长选路网( w a v e l e n g t hr o u t e dn e t w o r k ) 或称其为波长 路由网。 广播与选择网是通过无源星型耦合器件将多个节点按星型拓扑结构连接起 来的。基本原理是以广播形式发送，接收端有选择地滤波接收。这种网络主要用 于高速局域网或广域网。有两种工作方式：固定波长光发送与可协调的光接收； 接收波长固定和可协调发送。广播与选择网有三个不足之处：其一是浪费了光功 率。发射的光功率送到所有的接收器，不管这个接收器是否是通信对象这样， 对实际通信节点来说，增加了光分流引起的损耗。其二是可扩展性差。n 个节点 至少需要n 个波长，增加一个节点就要增加一个波长，每一个接收器的可协调 范围也要相应增加一个波长，而且不能执行波长重用。其三就是带宽利用率低， 一般一个节点只能使用i n 带宽这种广播与选择网不适合建规模较大的网络。 波长路由光网络”1 是由可以进行波长路由的网络和一些点到点的光纤连接 而组成的。波长路由节点中最重要的器件就是光交叉连接器( 0 x c ) ，光交叉连 接器的输入输出端口分为中继栈( t r u c k ) 端口和本地( 1 0 c a l ) 端口，中继栈端口通过 光纤与其它波长路由节点相连，本地端口则用于本地业务的上下路。所有业务的 西南交通大学硕士研究生学位论文第8 页 起点和终点都在本地端口当光交叉连接器只含两个中继端口时，相应的节点被 称为光分差复用器( o a d m ) 。o a d m 可以看成o x c 结构的功能简化。光交叉连 接器由波长复用器，解复用器，交换矩阵组成，还有可能包含波长转换器。1 。 在波长路由网络中，o x c 与光链路互相连接组成任意的拓扑结构，如图1 4 所示。每个终端用户都通过光链路连接到o x c 上，终端用户与其相应o x c 的 组合就是一个网络节点。每个网络节点都配有可调协发射器和接收器。 口业务接入站：包含( - - i 调谐) 收发机。波长路由交换机：可能包含波长转换器 图1 4w d m 波长路由网络 波长路由网是通过光通道( 1 i g h t p a t h ) 来实现通信的。光通道就是网络节点之 间的全光通信信道，可以跨越多个光链路。一条光通道上中间节点处的o x c 负 责为光通道提供光域的路由。光通道的终端节点则把接收器或发射器调谐到特定 波长上，以建立波长信道。 在没有波长转换器的w d m 网络中，一条光通道输入端口和输出端口上的 波长应该相同，这一点被称为波长连续性限制，如图1 4 中由a 到c 的通道和 由b 到f 的通道就满足波长连续性条件。带有波长转换器的光网络不必满足这 一需求，如图1 4 中由d 到e 的通路 波长路由网络的基本要求是满足d c a 条件“”，即同一光纤链路上的不同光 通道必须具有不同波长，以免通道问互相干扰。如图1 4 所示，由于从a 到c 西南交通大学硕士研究生学位论文第9 页 的通道和由h 到g 的通道没有公共链路，所以两条连接都可以使用波长丑进行 传输。而从a 到c 的通道和由b 到f 的通道有公共链路，要满足d c a 条件就 必须分别使用波长 和波长如进行传输。 在这个例子中，四条通信光路只使用了两个波长，这说明波长选路网可以用 较少的波长支持较多节点间的通信。因此在w d m 网络中建立两点之间的连接， 若选择一条最佳路由和合适的波长，可极大地提高网络效率，减小波长的阻塞， 通过优化网络的路由和波长，还可减少节点设备的端口数，降低网络成本。 波长路由网络可以根据用户的请求建立或拆除光通道，这有点像传统电话网 中话路的建立和拆除，具有这样功能的波长路由网就是动态的波长路由网。当然 波长路由网也可以根据需要提供永久性的光通道，这就是静态的波长路由网。从 以上定义可以看出，在波长路由网络中，正是通过光通道为用户提供了一个类似 线路交换的带宽服务机制，路由和交换的粒度为一个波长，这也是波长路由光网 络得名的原因。 根据光通道中经过的节点是否具有波长变换的能力，光通道可以分成二类： 波长通道( w a v e l e n g t hp a t h ，w p ) 和虚波长通道( v m u a lw a v e l e n g t hp a t h , v w p ) 。对 于w p 来说，它所经过的网络节点不具备波长变换能力，光通道所经过的所有光 纤链路上必须被分配相同的波长，它必须遵守波长连续性条件v w p 则要灵活 得多在v w p 的各个路由节点上都配置了波长变换器因此可以在一个端到端的 连接中所经过的光纤链路上使用不同的波长，具体可以使用的波长由各个路由节 点上所配置的波长转换设备所具有的能力来决定。 1 3w d m 波长路由网络的优点 波长路由光网络能比传统的电信网提供更为巨大的通信容量，可使通信网具 备更强的可管理性，灵活性、透明性。其优点可以具体的列举如下： 西南交通大学硕士研究生学位论文第1 0 页 1 ) 波长路由网通过波长选择器来实现路由选择，即依据波长信号来选择路由， 对传输码率、数据格式以及调制方式均具有透明性，可以提供多种协议业务， 可不受限制地提供端到端业务。透明性是指网络中的信息在从源地址到目的 地址的过程中，不做任何的光一电一光转换。由于波长路由光网络中信号的 传输全在光域中进行，信号速率、格式等仅受限于接收端和发射端，因此波 长路由光网络对信号是透明的 2 ) 波长路由网络不仅可以与现有的通信网络兼容，而且还可以支持未来的宽带 综合业务数字网以及网络的升级。 3 ) 波长路由网络具备可扩展性，加入新的网络节点时，不影响原有网络结构和 设备，降低了网络成本。波长路由网络也可以通过增加所使用的波长来实现 扩容。 4 ) 波长路由网络结构简单，端到端通信采用透明光通道连接，沿途没有变换与 存储设备，因此降低了网络的成本，提高了信号的质量。网中许多光器件都 是无源的，可靠性高、可维护性好。 1 4w d m 技术的发展前景 以高速光传输技术、宽带光接入技术、节点光交换技术、智能光联网技术为 核心并面向口互联网的w d m 技术已构成了今天的光纤通信的研究热点，在未 来的一段时间里，人们将继续建设各种实验网络，并在验证有关新概念和新方案 的同时，对下一代光传送网的关键技术进行更全面、更深入地研究。从发展趋势 来看，w d m 传送系统将朝着更多的信道数、更高的信道速率和更密的信道间隔 的方向发展，光网络则朝着面向i p 互联网、能融入更多业务、能进行灵活的资 源配置和生存性更强的方向发展o ”。 目前，w d m 技术作为最引人注目的高速宽带传输技术，其应用已开始铺开。 无论是陆地线路、海底光缆线路，还是己建光缆线路、新建光缆线路，都在享用 西南交通大学硕士研究生学位论文第1 1 页 w d m 技术进行扩容。因此，w d m 产品的销售剧增。 另外，作为超高速、大容量的w d m 配套技术也己相当成熟，如多信道的 w d m 传输设备、采用衍射光栅精密控制电子来扫描的不同波长d f b l d 一次成 形的技术、宽带放大器、放大器的增益均衡器、增益功率的控制技术等已经完成， 宽带波长可变滤波器、光交叉连接等已取得了一定的成果，先进的数据编码技术 也已成功地应用于w d m 系统中，以提高传输距离。以上这些成果也为超高速、 大容量的w d m 技术全面应用打下了良好的基础。 采用w d m 技术来扩容是当前唯一现实的超大容量传输技术它不仅可以 节约大量光纤而迅速扩容，而且还可以节约大量再生中继器，以降低整个系统的 成本。从长远意义来看，它奠定了未来全光网络的基础。 未来的几年，将是w d m 技术迅速发展的时期，运营公司将大量采用w d m 光网络技术作为宽带网络的基础结构，基于波长选路及波长变换的光网络将大量 采用，以保证网络的快速恢复及高可靠性。同时，w d m 系统的价格将大幅度下 降，低费用的光设备将大批量生产，使用波长可调谐光源的s d h 终端将被采用， 平面波导技术也将成熟，这将有利于光波线路、可调谐激光器阵列、低费用的光 路由及交换机的产品发展。w d m 技术将进一步走向成熟。 w d m 网络是光纤通信技术发展的下一个目标，特别是对于我国这样一个幅 员辽阔、具有庞大干线网的国家。w d m 技术的建立将在干线网的交叉节点上引 入光交叉连接设备( o x c ) 、光分插复用设备( o a d m ) 和光波长变换，从而形成 端到端之间的“虚波长”通路，实现用户端到端的全光信号连接。这将使电路之 问的调配和转接变得简单和方便。从发展趋势看，形成一个真正的、以w d m 技 术及光交换技术为基础的光网络层，建立纯粹的w d m 光网，接入i p 等多种业 务信号已成为光通信发展的必然趋势，它完全符合“传送网”的分层化，并简化 了网络结构，提高了网络的可靠性，并且与业务和承载信号无关，尤其是自动交 换光网络( a s o n ) 技术的引入更是赋予了w d m 光网络优异的性能。 西南交通大学硕士研究生学位论文第1 2 页 当然，从整体看，w d m 光网络的发展目前还处于初级阶段，但它已显示了 良好的发展前景，已成为新世纪引人瞩目的新一代传送网。 1 5 本文的主要研究内容 本文首先介绍了光网络中路由和波长分配问题的相关概念和常见算法；其次 在波长分配算法方面，改进了文献中性能最好的相对容量影响算法，路由算法方 面，提出了一种链路代价定义策略；之后研究了路由和波长分配算法的优先级问 题和公平性问题，提出了一种支持优先级的波长分配算法和一种兼顾优先级和公 平性的波长分配算法；最后是全文总结。章节安排如下： 第l 章绪论。主要介绍了w d m 光网络的产生背景以及结构体系。 第2 章w d m 网络中常见的路由和波长分配算法简要总结了文献中已有 的路由和波长分配算法。 第3 章一种波长连续光网络中的r w a 算法。通过对文献中阻塞率性能最好 的相对容量影响波长分配算法的分析，指出了其不足并加以改进，提出了一种无 波长转换情况下的动态波长分配算法；提出了一种链路代价定义策略，将链路负 载以及路由跳数都作为选路的一个考量值，均衡了网络负载，降低了网络阻塞率。 第4 章一种支持优先级的波长分配算法。研究了光路连接请求具有不同优 先级的情况，提出了一种支持优先级的波长分配算法，此方法在支持优先级的同 时，考虑了链路负载均衡，因此有效地降低了网络的阻塞率。 第5 章一种公平的支持多优先级的波长分配算法。研究了网络公平性的问 题，提出了一种兼顾公平性与优先级的波长分配算法，此法在支持优先级的同时， 通过适当增加短跳光路的阻塞率，有效地降低了长跳光路的阻塞率，改善了网 络的公平性。 最后对全文进行了总结，提出了以后的研究方向。 西南交通大学硕士研究生学位论文第1 3 页 第2 章w d m 网络中常见的路由和波长分配算法 路由和波长分配( r w a ) 是w d m 光传送网中的重要问题，其主要解决任务 是确定一条建立连接的光路并为选择的光路分配波长。r w a 问题是一类n p 完 全问题“o ，也就是说还没有找到任意复杂度r w a 问题的时间算法由于计算资 源有限，只能对规模有限的网络优化做出r w a 问题的解答。本章讲述的重点内 容就是波长路由光网络中的r w a 问题，即介绍了r w a 问题的基本概念和常见 算法，并指出了r w a 领域需要进一步研究的问题。 2 1 基本概念 波长路由光网络( w r o n ) 的一大优点是它支持波长选路，从而使网络具有很 大的灵活性如前所述，光层可进一步细分为光信道层、光复用段层和光传输段 层。其中光信道可以看作是光信道层上的端到端的连接，它形成电路层的虚连接。 光信道层能为光信道选路和分配波长。电信号经过本地的接入设备转换为某一波 长的光信号，再经由多个o x c 节点的交叉连接建立起一条光通路。 根据o x c 节点是否提供波长转换功能光通路可以分为波长通路 ( w a v e l e n g t hp a t h ) 和虚波长通路( v i r t u a lw a v e l e n g t hp a t h ) 。波长通路是指o x c 节点没有波长转换功能，某一个光通路在不同波长复用段中必须使用同一波长， 即满足波长连续住限制。如果在它所经过的所有链路中，找不到一条有一个共同 空闲波长信道的路由，就会发生波长阻塞。虚波长通路是指0 x c 节点具有波长转 换功能，光通路在同一波长通路的不同波长复用段中可以占用不同的波长，从而 提高了波长的利用率，降低了阻塞发生的概率。 在有n 个节点的电路交换( c s ) 光网络中，若每个节点配置了n - l 套接收器 和发射器，且有足够的波长分配给所有链路，则每对节点都可通过专用的光通道 西南交通大学硕士研究生学位论文第1 4 页 互联，因此不存在互联问题。但是，如果因为收发器成本高而仅给每个节点配置 有限的收发器，又或由于技术限制不能给网络提供足够的波长，那么网络中的光 通道数目就有限了，进而路由受限。由于路由限制而不能建立某些光通道，因而 造成某些波长的“阻塞”，在此情况下就出现了互联问题，即在给定的光通道数 目和给定的波长数下，如何分配波长、如何建立通道以使光网络路由最优化。网 络优化就是要尽可能地减小“阻塞”概率，类似的问题就是所谓的路由和波长分 配( r w a ) 问题。本章讲述的重点内容就是基于电路交换w r o n 中的r w a 问题。 根据连接需求可以把r w a 问题分为静态光路建立( s l e ，s t a t i c l i g h t p a t h e s t a b l i s h m e n t ) 和动态光路建立( d l e ，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 ) 两类问题。求解r w a 问题时，可以把它分解为路由子问题和波长分配子问题。 s l e 问题是指整个网络的连接是事先已知的，对各个连接的路由和波长分 配是非实时的( o f f - l i n e ) 。s l e 问题归结为：在尽可能少占用波长和光纤等网络资 源的情况下，为已知的连接需求建立光通道。换句话说，就是在给定的光纤和波 长等网络资源上建立尽可能多的光通道。在s l e 问题中，通常用基于流量整数 线性规划( 1 l p ) 法求解路由子问题，再根据已有路由通过网络着色算法等求解波 长分配问题；另外一种途径是通过基于通道的i l p 法直接求解该问题。对s l e 问题的研究主要适用于长期稳定的连接请求，因此对传统的话音业务支持较好。 但随着i n t e m e t 的飞速发展，数据业务的带宽需求迅速增加，在这种情况下，连 接建立请求和连接拆除请求的到达会更加频繁。而由于目前传送网对突发数据业 务的支持不够灵活，使数据业务占用大量带宽，而由数据业务产生的利润却相对 较低。要解决这个问题，下一代传送网必须要有动态分配、释放资源的能力，因 此本文将着重讨论d l e 问题 d l e 问题是指连接需求不是预知的，网络需要即时为刚到达的连接请求建 立光通道，并在通信结束后拆除光通道。d l e 问题归结为：根据连接请求建立光 通道并分配波长，使连接阻塞概率最小或使连接数最大d l e 问题求解比较复 西南交通大学硕士研究生学位论文第1 5 页 杂，通常采用启发式算法。动态业务下的r w a 问题，是指在实时业务条件下的 路由选择和波长分配问题。此时连接请求是随机到达的，并且己建立的连接在维 持一段时间后会被撤销，故动态业务下的r w a 算法要求具有实时性。由于需要 建立的光连接的数量和位置是不固定的，并且随时不断地改变，因此以资源优化 为目标已不能反映实际情况的要求，一般是以降低业务的阻塞率作为动态r w a 问题的优化目标。 2 1 1 动态业务下r w a 问题的物理模型 光网络由光纤和节点设备组成，因此可以把网络抽象成数学中的图，图具有 很多种拓扑结构。在光网络研究方法学中，光网络具有物理拓扑和逻辑拓扑所 谓物理拓扑就是通常所说的拓扑结构，而逻辑拓扑是指当两个光网络节点可以直 接或间接地通过其他节点互相通信时，就称它们是逻辑相连的，这样形成的拓扑 就是逻辑拓扑 回椭口： ( a ) 物理拓扑 西南交通大学硕士研究生学位论文第1 6 页 ( b ) 逻辑拓扑( c ) 全逻辑连接 图2 i 物理拓扑与逻辑拓扑 图2 1 ( a ) 表示有6 个端系统的星型物理拓扑的光网络，6 个网络接入站 n a s ( n c t w o r ka c c e s ss t a t i o n ) 通过个星型藕合器相连，在光路上完全互连互通。 所以它们在逻辑上是全连接的，如图2 - l 所示图2 - l ( c ) 表示各个端系统到其 他端系统都是直接相连的。当在一个给定的透明的光的基础构架上完成了一套逻 辑连接之后，我们就认为逻辑拓扑己经嵌入到了物理拓扑中 为了方便研究和计算机模拟，我们对本论文将要研究的网络模型做如下规 定： 1 ) 光网络的物理拓扑为网格网，各节点在逻辑上全连通； 2 ) 网络的节点数为n ，节点之间如果直接相连，则称之为链路，链路可由 多根光纤组成，每根光纤可以双向传输，光纤最大复用波长数w 3 ) 网络中无波长转换器，即节点问建立的光连接采用单一波长建立波长通 道。 2 1 。2 动态业务下r w a 问题的数学描述 动态r w a 算法在实际的网络结构之上，为随机到达的业务选路和分配波长， 因此对于业务连接的快速建立具有重要意义。由于网络资源的有限性，不可能对 西南交通大学硕士研究生学位论文第1 7 页 所有的业务请求都能及时地提供波长通道，因此必然存在业务阻塞的问题。好的 算法可以充分地利用网络资源，尽可能地减小网络阻塞率。因此在动态的r w a 问题中，使网络平均阻塞率最小化就是算法的优化目标。整体算法的数学描述如 下： 给定条件： 1 ) 网络物理拓扑结构 2 ) 网络业务负载 3 ) 业务连接持续时间 约束条件： 1 ) 光纤数目的限制 2 ) 波长数目的限制 3 ) 波长连续性限制 目标函数：最小化网络平均阻塞率 2 2 路由选择算法 砒融问题经常被分解为路由子问题和波长分配子问题。通常先为光网络选 路，即先解决路由子问题，然后逐一为光通道分配波长路由选择从整体上讲划 分为基于全网信息和基于局部信息的两种方式。所谓基于全网信息是指做出路由 决策的节点维护有全网每一条链路的资源信息。这种方式既可适应于集中式控制 的网络，也可适应于分布式控制的网络。基于全网信息的路由策略是基于端到端 的通路来选择路由的，而基于局部信息的路由方式足以逐跳方式确定路由的。与 基于全局信息的路由策略相比，基于局部信息的路由策略更为灵活，具有很强的 可扩展性，但其缺点是连接建立的时间较长，信令过程比较复杂。目前，基于全 网信息的路由方式是一种较为成熟的路由策略，因此本文着重讨论这种路由策略 中的各种算法。 西南交通大学硕士研究生学位论文第1 8 页 固定路由( f i x e d r o u t i n g ，f r ) “”：这是最直接最简单的选路算法，网络为同 一节点对提供固定不变的光通道。选路是事先进行的，网络拓扑结构己知后，按 照标准最短路径算法( r e 如d i j k s t r a 算法和b e l l m a n f o r d 算法) 为每个节点对分配 固定的光通道。网络运行中，节点对之间的通信连接总是建立在预定好的路由上 如图2 2 所示，节点0 到节点2 的工作路由依次经过0 ，l ，2 节点。这种方法虽然 简单，但却需要较多的波长资源。在动态流量情况下，如果出现波长冲突，则会 导致严重的流量阻塞。因为没有替代路由，所以这种算法下网络不具备链路故障 恢复能力。 图2 2 固定选路算法图2 3 固定一备用选路法 固定一备用选路法( f i x e d a l t e r n a t er o u t i n g ，f a r ) “。棚：网络中每个节点维 护一张路由表，里面罗列着它到其他节点的一系列路由，其中包括作为工作光通 道的最短路由和作为备用光通道的路由。备用路由一般不跨越工作路由的链路 段，即它们在物理上是分离的，所以这种机制又叫做链路分离或边分离机制。当 节点收到连接请求时，按照工作路由建立光通路，若工作路由己被占用或失效， 则在备用路由中选择次短路由如图2 3 所示，节点o 到节点2 的备用路由依次 经过0 ，5 ，4 ，2 节点这种选路法的优点是简单且具有链路故障恢复机制，与固定 选路法相比，流量被阻塞的概率显著减小。 自适应选路法( a d a p t i v er o u t i n g ，a r ) “”：从性能上看，a r 是一种较好的 方案。f r 和f a r 方案都不能考虑到网络的当前状态，而a r 则可以根据当前的 网络状态动态地进行路由选择。a r 具体可以细分为两种，一种是受限a r ，另 一种是非受限a r 。所谓受限a r 与f a r 相似，同样是预先为每一对源宿节点建 西南交通大学硕士研究生学位论文第1 9 页 立备用路由集，集合中的路由排列是无序的，当需要建立连接时，根据当前的网 络状态选择最合适的一条路由，这种方案代表算法有l l r i 2 4 1 ，f p