（通信与信息系统专业论文）ip+over+wdm光网络中业务流新型疏导与选路算法研究.pdf

摘要 i po v e rw d m 光网络体系结构是未来通信的主流发展方向。由于网络中结点配 置收发器数和链路波长数均是受限的，因而为每个子波长颗粒度带宽的业务都建 立端到端的光路连接是不可能的。因此为有效地利用网络资源，需引入业务流疏 导机制。本文结合国家高技术研究发展计划( 8 6 3 计划) 项目“基于p c e 的多层多域 光网络关键技术研究与试验系统 ，针对在i m m 光网络中的静、动态疏导问题 分别进行了研究。 针对预先规划动态业务，提出以最小化阻塞率为疏导目标的混合整数线性规 划模型；针对持续时间已知动态业务，提出区分权重的持续时间已知的疏导算法， 该算法考虑链路的剩余生存期和未来拥塞度这两个因素，与已有算法相比，降低 了阻塞率性能。 本文对同时优化光路拥塞和业务平均时延的静态虚拓扑的双目标优化设计问 题进行了研究。首先，提出虚拓扑设计数学模型，之后利用s 约束方法求解多个 p a r e t o 最优解。另外，本文提出新的多目标优化方法基于遗传的联合时延和拥塞的 强度p a r e t o 算法( s p d c g a ) 一来解决虚拓扑设计问题。s p d c g a 算法可以在任意时 间内结束，给出当前确定的p a r e t o 最优解集，这些解决方案不但可以确定出静态逻 辑拓扑，而且也解决了光路的路由和波长分配问题，因此s p d c 羽a 方法计算的逻 辑拓扑设计方案可以嵌入到实际的光网络中去。 为验证、评估本文提出的算法性能，给出了m ，w d m 光网络中业务量疏导算法 的软件设计流程。最后是全文总结。 关键词：业务疏导虚拓扑设计启发式方法多目标遗传算法持续时间已知 i po v e r 、v d m a b s t r a c t i po v e rw d m o p t i c a l 饿舸f k sa r c l l i t e c t u r el e a d sm ew a yo fd e v e l o p m e n ti nt l l e 翕l t l l i ec o m m u n j c a t i o n ，o r l d f o fm el i l n i t a t i o ni nt h en u m b e ro fn 嗣n s c e i v e r s c 0 i l f i g 唧e di i l 廿l en o d e 锄dl i i l l ( w a v e l e n 舀h s ，i t si i i l p o s s i b l et 0e s t a 由l i s ho m 衄d - t 0 e n d l i g l l t p a ：c hf j 河e a c hs i l ：b - w a v e l e n g t l l 删撕哆b a n d 谢d t l lr e q u e s t t h e r e f o r c ，蠡竹t h e e 衔c i e n tu t i l 汤t 伽o fm 似的r kr e s o u 鹏e s ，缸a f j f i c 伊。锄i i l gn e e d st 0b em e d s p o n s o 川b y 廿地k c y1 k h n o l o 舒r e s e 鲫c h 锄de x p e r 吼e n ts y s t e mb a s e do np c e i i l m u l t i l a y e fm u l t i r e 西o no p t i c a ln e t w o r l 【s 五r o m 妇1 es t a t eh i 曲t e c h n o l o g yr e s e a r c h a n dd e v e l o p m e n tp 啊e c t ( 8 6 3p r o j e c t ) ，s t a t i c 锄dd y n a 面ct r a 腼cg r o o m i n gp r o b l e i 璐 i l li po v e rw d m o 曲c a ln 咖o r k sa r es t i l d i e ds 印锄t e l yi i lt l l i sp a p e r f o rt 1 1 es c h e d u l e d 仃蕊cm o d e l ，w ep r o p o am 奴e di i l t e g e rl 证e a rp r o 罂卸n m i n g i n o d e l ；f o rt h ed y n a 觚c 位商cm o d e l 诵mk n o w nd u r a t i o 璐，w ep r o p 0 ad i 侬爬i i t i a l l y w e i g m e da n dh o l “i l i l e 一孙a r eg o o m i i l ga l g o d m mw i l i c hc o i l s i d e r s t l l er e s i d i 脚 l i f e t i m ea n d 如t i c o n g e s t i o no fn 幽0 r kl i n l 【s ，锄dn l i sa l g o r i m ma c l l i e v e ss i 印i f i c a n t 川u c t i o n mb l o 凼n g p r o b a b i l 时c o m p a r e d 、析me x i s t i n ga 1 9 0 r i m m s 1 ks t a t i cv i m l a lt o p o l o 舒sd o u b l eo 场e c t i v eo p t i i i l i z a t i o nd e s i 印p r o b l e mi s s t u d i e di nt b j sp a p e r 诵t l l 廿l ea i mo fm i i l i 珈妇i n gb o t l lt l l ec o n g e s t i o n 趾dt h ee n d - t 0 - e n d d e l a y f i r s n y t h em a m e m a t i c a lm o d e lo fv i r t u a lt o p o l o g yd e s i g np 悦锄i sp r o p o s e d 锄d 廿l e nm u l 矗p l ep a r e t o0 1 ) t i m a ls o l u t i o i 塔a c a l c u l a t e dn l o l l g h l e 一陀s t r i c t e d m e t i l o d h la d m t i o i l a 鹏wm u l t i - o b j e c t i v eo p t i i n i z a t i o nm 池d - t l l e 如e n g mp a r e t o m e t h o dj o i l 血gd e l a y 锄dc o n g e s t i o nb 弱e do ng e n e t i ca l g o r i t l m ( s p d c - g a ) - i s p r o p o s e di nt l l i sp a p e rt 0s o l v ev i n u a lt o p o l o 科d c s i 印p r o b l 锄s p d c g aa l g o r i t l l i n c a nb ef i l l i s h o da t 锄yt i m e 锄do u 印u t 廿l ec u n e n tp a r e t 0o p t i i i x a l l u t i o ns e tw 量l i c hn o t o n l y 西v 髓m es t a t i cl o 西c a lt o p o l o g yb u ta l l v e st h er o u t i i l ga n dw 孙，e l e n g t l l 弱s i 印m e n tp b l e mo fl i g h 印a ：i h 觚d t 1 1 el o 西c a lt o p o l o g yd e s i 盟s 0 l u t i o 璐 s p d c - g ac a l c u l 锄e dc a nb ee m b e d d e di i lt l l ep r a c t i c a lo p t i c a ln e t w o r k 1 1 圮s o f h a d e s i 伊p r o c e s so fn l e 位曲c 伊o o m i n ga l g o r i t l l i 璐i i lm 0 v e rw d m 0 p t i c a l 玳棚o r k si si n 佃汕c e dt 0e v a l u a 【t e l ea l g o r i t l l m sp e r f - o 姗锄c ei nt h i sp a p e r f i i l a l l y ，t l l e 觚lt e x t 翻j m m 珊i z a t i o ni s 舀v e l l k e y w o r d s ：硒cg m o m i n g v i r t l i a it o p o l o 科d 鹤i 驴h e u r i s t i cm e t h o d m u m - o b j 佻t 扣eg e n e t i ca i g o r i t h mh o l d i n g _ t i m e - a w a 聆 i p w 盯w d m 第一章绪论 第一章绪论 在信息时代，随着因特网和万维网业务的高速发展，要求以低成本来建设高 带宽的网络。业务需求日益趋于多样性，数据、图像、视频等各种专业的传输要 求，不断地向服务提供商提出新的挑战。为了实现网络能够提供更多的带宽和新 业务这一目标，需要一种新技术可以建立一个具有巨大带宽容量的网络结构，而 光纤网络技术就是可满足要求的新技术。波分复用技术w d m ( w 打e l e n g md i 、，i s i m u l t i p l e x i n g ) 和光交换技术以其独有的技术优势和多波长特性，使得光网络通信技 术成为现在和未来宽带通信网络中的主导技术。由于m 业务本身的突发、多变、不 确定、不可预见性等特点，这要求光网络能够为各种带宽颗粒业务来动态分配网 络资源，同时也要求网络具有快速故障恢复能力，因而促使智能光网络应运而生。 1 1i p 智能与光层技术的融合趋势一m 佩m 随着自动交换光网络a s o n ( a u t o m a t i cs 谢t i c h0 忱i c a ln i 哪哪k ) 智能标准的逐 步完善，i p 和光网络技术的相互融合将成为可能。口技术具有众多优点，它简单， 灵活，控制粒度细，可扩展性好，极具智能性。更重要的是，随着e t 业务的 爆炸性增长，传统网络在向多业务网络的方向发展，而综合近几年网络的发展趋 势来看，i p 称为适合于各种业务的首选技术。i p 与光网络的融合可实现优势互补： 结合光层和i p 层的路由功能，能提供动态的波长路由；结合光层的保护功能和m 层的恢复功能，能提供多种保护恢复方案，提高网络生存性；i p 智能控制协议丰富 而且标准化程度高，又有多年实践经验等等，而在光网络中，w d m 技术提供了巨 大的带宽，已经无可争议地称为骨干网络中最主要的传输技术。显然i po v e rw d m 的应用与发展势在必行l l j 。 i po v e rw d m 技术使i p 数据流直接进入了光通道，有利于充分综合w d m 技术 大容量与i p 技术统计复用的优势。从图1 1 可以看出，由于中间省略了御眦层和s d h 层，它能充分利用光纤的带宽资源，极大提高了带宽和相对传输速率，并在i p 层与 光层之间实现流量工程、保护恢复、服务质量q o s ( q i j a l 畸o f s e r v i c e ) 和网络管理等 的优化配置，整个网络体系结构简单而高效。 2 口o v e rw d m 光网络中业务流新型疏导与选路算法研究 电图数 话 像据 i p a t m 层 s d h 层 w d m 层 电图数 话像 据 i p m p l s 、d m o t n 图1 1m o v e r w d m 协议栈的发展 目前的i po v e rw d m 解决方案实际上提供了一种简单的数据接口。它引入了一 个适配层，提供i p 包在w d m 上传输的组帧操作，以及数据网运行维护与管理信息 到光网络信息的相应映射。这样简化了适配过程，减少s d h 、朋m 和i p 等各层间 的功能重叠，避免了多层映射的重复操作与开销浪费，从而大大减少了网络运营 成本。显然，这是一种最直接、最简单和最经济的网络体系结构，非常适用于超 大型i p 骨干网。由于i po v e rw d m 的传输码率、数据格式及调制方式均是透明的， 它可以传送不同码率的a t m 、s d h s o n e t 和千兆以太网格式的业务，因而m 佩d m 这种体系不仅可以与现有通信网络相兼容，还可以支持未来的宽带业务网及进行 网络升级。波分复用w d m 网络在网络部件失效时可能遭受比传统网络更大的损 失，比如一根光纤断裂会使经过它的所有光路同时失效，则i p 厂w d m 要具有高度生 存性的特点。随着通用多协议标记交换g m p l s ( g e n e m l i z e dm u l t i - p r o t i d c o ll a b e i s 谢t c l d 技术作为一种优秀的光网络控制平面技术得到快速发展，则m 佩巾m 光网络 必将是智能的光网络，其基本要求是动态资源配置和提供、统一的网络控制和资 源管理。总之，i p 爪巾m 被业界人士认为是下一代光网络的主流基础结构。本文是 在i po v e rw d m 网络体系下来研究业务流疏导问题。 1 2mo v e rw d m 光网络体系结构 i po v e rw d m 技术和网络体系结构的发展过程大致可划分为三个阶段【2 l ：i p o v e r 点到点w d m 光网络、mo v e r 可重构w d m 光网络和i po v e r 分组交换w d m 光网 络。 1 1 1i po v e r 点到点w d m 光网络 在光交叉连接器o x c ( o p t i c a lc r o s s - c o 加删及光分插复用器o a d m ( o 面c a l a d d d r o pm u l t i p l e x e r ) 成熟之前，w d m 网络为点到点方式，如图1 2 所示。口o v e r 点到点w d m 光网络为第1 代i p 瓜，d m 系统，又称为b f 脚“钡r o u t e r ) 模型【3 l 。在此 第一章绪论 模型中，w d m 系统仅作为相邻i p 路由器之间的带宽管道，口分组利用p a c k e to 、，盯 s o n e t 协议被封装到s o n e t 帧中，这仍是一个三层体系结构。在口o v e r 点到点的 w d m 体系中，网络拓扑是固定的，网络配置是静态的传统集中式网络管理。 图1 2 疋o v e r 点到点的w d m 体系 这类系统的主要缺点是：( 1 ) 由于光层基本不具备智能功能，控制要由管理系 统承担，则需要通过多层协议栈来承载i p 业务，而协议栈中的任何一层都可能限制 整个系统的发展；( 2 ) w d m 系统仅充当点到点的高带宽传输通道，不能提供直通光 路，则口分组的交换和路由仍依赖于高吞吐量的核心路由器来完成，但光技术的发 展快于电子技术，路由器的处理速度必将成为限制此类系统发展的瓶颈；( 3 ) 光层 不具备智能，其资源调度策略不能与i p 业务的统计特点相匹配。 1 1 2i p0 v e r 可重构w d m 光网络 i p 0 v 盯w d m 波长交换光网络为第二代i 啪m 系统，如图1 3 所示。光网络由 光交叉连接器或光分插复用器组成。这些网络结点在分布式控制平面的控制下， 具有波长交换功能，可为边缘路由器动态提供端到端的光通道。通过适当配置o x c 的交叉连接状态，任何一个路由器均可与网内任何其他路由器的任何端口相连， 从而实现路由器之间相邻关系的任意配置。所以，i po v e rw d m 波长交换光网络也 称为i po v e r 可重构w d m 光网络。 图1 3m o v e f 可重构的w d m 体系 4 p0 v e rw d m 光网络中业务流新型疏导与选路算法研究 在口o v e r 可重构w d m 光网络中，根据i p 网络和光网络之间的相互作用关系， 可将网络业务划分为两种l 】：分域业务模型和统一业务模型。分域业务模型是指 把i p0 v e rw d m 光网络划分成i p 网络和光网络两个独立的实体，光网络主要为客户 请求简单地提供高带宽的传输通道；统一业务模型是将i p 网络和光网络看作成一个 整体，光交换设备o x c 和路由器之间并没有区别。基于不同的业务模型，相应的 即有不同的路由机制，从而可以把i p o v e r 可重构w d m 光网络划分为3 种架构【九重 叠( o v e r l a y ) 模型，对等( p e e r ) 模型和增广( a u g m e n t e d ) 模型。 ( 1 ) 对于重叠模型，如图1 4 ( a ) 所示。在这种模型下，i p 的路由协议与光网络的 路由及信令协议是相互独立的。光网络层独立地实施其特定的智能控制，m 层和光 网络层成为两个基本独立的智能网络层。客户层的路由器通过u n i 向光网络提出光 路请求，光网络向客户端提供点到点的连接路径。采用这种机制的好处是对用户 屏蔽了网络拓扑，但缺点是i p 层上不知道光层的资源信息，很难自动实现高层的流 量工程能力，可升级性能不好。 ( 2 ) 对于对等模型，如图1 4 所示，又称集成模型( i n t e g m t e dm o d e l ) ，是i e t f 支持的网络演进结构。路由器和光交换设备是对等的，i p 层和光层由统一的路由协 议进行资源调配。光传送层的控制智能转移到了i p 层，突破了光网络传输平台和客 户层平台之间的明显界限，因此光传送网和i p 网集成为一个网络。光交换设备和路 由器有一个共同的地址分配和寻址机制，它们之间运用内部网关协议i g p ( i n t 耐o r g a t e w a yp r o t o c 0 1 ) 或中间系统到中间系统i s i s ( i n t e 肌e d i a l es y s t e m i n t e l l i l e d i a ：c e s y s t e m ) 协议来交换各层的网络拓扑信息，因而业务请求者可以看见光网络的结构， 进而可以做出优化的路由决策。采用这种模型的好处在于：改善了可升级性能： 易于沿袭或采用目前路由器的路由协议。但也有下列问题：将两层结合在一起， 难于进行路由选择、波长分配及资源预留；单一不分级的( f l a t 1 l i e 黜h y ) 模型无法 进行大规模的i p 光域的“联合；对路由器开放了光网络内部的属性，如拓扑细节， 路由行为等等。 统一的i p 控制平台 ( a ) 重叠模型 ( b ) 对等模型 图1 4m o v 日可重构w d m 光网络模型 ( 3 ) 对于增广模型，它是将上述两个模型进行有机的结合，在这种模型下，运 营商可以对自己内部的i p 网和光网络采取对等模型来构建，对于其它运营商网络和 第一章绪论 5 其他客户层信号可以采用重叠模型来构建，则这种模型结合了前述两种模型的优 点。d 域和光域的控制面在功能上相互分离，它们运行各自的路由协议，但两个域 之间需通过运用标准协议的u n i 交换全部可获得性信息。增广模型可能会采用以下 两种方法在碑光的u n i 接口处进行路由信息交换：( 1 ) 采用域间i p 路由协议( b g p ) ， 可以在口和光域间交换路由信息；( 2 ) 使用o s p f 域( 此时o s p f 可以支持两级路由机 制) ，在两个域间交换路由信息。 i po v e rw d m 波长交换光网络结构简化了层间管理与控制，提高了操作效率， 增加了结点吞吐量，并使光层能够快速响应口层的带宽需求。但为了实现带宽适配， 边缘路由器往往需要进行大量的复用和解复用操作，以便把高速光信号变换成可 处理的低速电信号，增加了设备的复杂性和成本。另外波长交换本质上是一种光 层的电路交换，它的带宽分配策略并不适合承载突发性的i p 业务。所以，i po v e r w d m 波长交换光网络有逐渐向i p0 v e r 光分组交换网方向发展的趋势。 1 1 3i po v e r 分组交换w d m 光网络 在i po v 盯分组交换的w d m 系统中，w d m 层直接提供分组级的交换能力，即 光分组交换，这是第3 代咖m 系统。光分组交换是指在光域实现分组交换的智 能光网络技术，每个光分组由一个光分组头和一个光分组净荷组成，光分组头中“ 包含源地址、宿地址、生存时间与寿命( t t l ) 等信息。光分组交换由于动态共享、 统计复用带宽资源，则可以极大提高网络带宽资源利用率，并使网络具有很好的 灵活性；由于采用高速净荷、低速分组头，从而可解决p 路由器的电子瓶颈问题； 而且，在光分组交换中，g m p l s 协议可实现流量工程以及服务质量( q o s ) 保证。因 而光分组交换必将是m ，w d m 网络的最终理想方案。由于当前缺乏光子存储器和光 子集成芯片，光分组交换的实用化非常遥远，所以两种不需光缓存的替代方案一 光突发交换与光流交换以及口波长路由器方案【o 】，可能成为较早实用化的i po v e r 分组交换w d m 系统。 对于上述口0 v e rw d m 光网络发展的三个阶段，mo v e r 点到点的w d m 系统因 无法克服结点电子瓶颈问题而不是主要方向。mo v e r 分组交换的w d m 系统因关键 器件不成熟而导致其实用化非常困难。i po v e f 可重构w d m 系统则是正在或即将实 用化的方案，因而也是目前的研究热点。本文主要针对这类系统讨论业务流疏导 问题。 1 3 删w d m 光网络中的几个研究方向 在i p w d m 光网络中研究的问题主要包括以下几个方面： ( 1 ) 光网络规划与优化设计问题 6 mo v e rw d m 光网络中业务流新型疏导与选路算法研究 光网络规划与优化设计是为适应网络负载的改变而进行的预先准备。在考虑 特定约束( 如链路的必经必不经约束) 和最小化目标函数( 通常为组网的费用) 的前 提下，并给定传输带宽需求( 即业务量矩阵) ，光网络规划主要解决以下两个问题： ( 1 ) 若已知网络拓扑，则计算承载业务所需最少的网络资源；( 2 ) 若未知网络拓扑， 则需要设计出满足业务需求的最小费用的网络。 ( 2 ) 路由和波长分配 路由和波长分配是指：在给定一组需要在网络上建立的光通道，和给定最大 可用波长数量限制的情况下，如何来决定具体的路由和分配合适的波长以使可建 立的光连接最多( 或使所需的波长数量最少) 。在波长通道和虚波长通道的情况下， 这个问题又有不同的解决方案，如在波长通道网络中，由于必须满足波长连续性 的原则，即对任意一条全光路径，在它经过的所有链路上必须占用同一个波长， 相邻通道分配不同的波长，因此路由选择和波长分配问题可以分解成两个独立的 子问题：选路问题和波长分配问题。选路问题是指按照某种优化目标寻找从源结 点到目的结点的路由；波长分配问题则是在满足一定优化性能的情况下为这些路 由分配波长。而在虚波长通道网络中，采用波长转换技术可以在同一个路由上分 配不同的波长，故不存在波长分配问题，这样的路由波长分配问题就可简化为只 考虑选择路由的问题。 ( 3 ) 虚拟拓扑重构 由于光网络中的器件具有上下波长( 如光分插复用器) 和在输入输出端口之间 交换波长( 如波长路由器) 的功能，一条光通道能被建立也能被拆除，使得波分复用 光网络具有重构其虚拓扑的功能。另一方面，重构虚拓扑在下面两种情况下变得 必要：1 ) 由于一个具体的虚拓扑总是针对某个具体的业务模式和物理拓扑设计的， 因而当作用于虚拓扑的业务模式改变时，网络的性能会下降甚至变得不可接受， 此时光通道需要重新安排以便在新的业务模式下取得合理的性能；2 ) 当底层的物 理拓扑由于光器件故障或其他原因发生改变时，在受影响光通道上的业务必须重 新路由，但是在这个受影响的虚拓扑上并不一定总能找到具有足够空闲容量的替 代路由。在这两种情况下对虚拓扑进行重构都是必需的。波分复用光网能够重构 其虚拓扑提供了对业务模式改变的自适应能力、对网络部件故障的自愈能力和网 络的升级能力。 ( 4 ) 光组播 通信网络正朝着综合业务的方向发展。新出现的多媒体通信带来了组播的需 求，计算机会议、计算机协同工作等具有组播要求的业务日益增多，并受到广泛 重视。组播支持多点通信，它要寻找连接源结点和一组目的结点的一棵组播树， 信息可沿这棵树确定的路径进行发送，信息只需在树的分支处进行复制，以便节 省网络资源。当有大量的数据包需要进行点对多点的传送时，组播将是很好的选 第一章绪论 7 择。 ( 5 ) 网络生存性 网络生存性( n 曲0 呔s u r v i v a b i l i 动是指网络在受到各种故障( 如链路、结点等 失效) 后能够维持可接受业务质量的能力。w d m 技术在大大提高链路传输容量的同 时，也使网络的生存性问题日渐突出。实现网络生存性一般有两类方法：网络保 护与网络恢复，而保护策略可以分为通道保护0 a l l lp r o t e c t i o l l ) 和链路保护( s p a l l l i i l l 【 p r o t e c t i o n ) 。通道保护是指，在源结点和宿结点之间寻找两条不重边或不重结点的 路由分别作为工作通道和保护通道。而链路保护是指，针对工作通道上的每一段 链路采用不同的保护。通道保护的特点是，资源利用率高，但恢复时间稍慢；而 链路保护的特点是，恢复时间快，但资源利用率较低。 ( 6 ) 通信量疏导问题 为了解决删d m 光岫t 中低于波长粒度的带宽请求路由问题，提出了通信 量疏导的概念，这一问题也是本文所研究的主要问题，将在以后的内容中作详细 的介绍。 1 4 本文内容安排及意义 随着网络业务量的爆炸性增长以及高性能的w d m 光网络设备的出现，波分复 用技术成为下一代骨干网络的核心技术。光网络中的每个波长可以以相当高的速 率传输例如o c _ 4 8 、o c 1 9 2 、o c 7 6 8 ( 对应的速度为2 5 g 1 ) s 、l o g b ，s 、4 0 g b ，s ) ，然 而在实际应用中，每个业务的通信速率往往远远低于一个波长的最高传输速率，” 例如o c 1 、o c 3 、o c 1 2 ( 对应的速度为5 1 8 4 m b ，s 、1 5 5 5 2 m b s 、6 2 2 0 8 m b s ) 。显 然，为每个业务提供一个专用波长，资源利用率低且不经济。业务量疏导是用于 解决w d m 光网络中高带宽光路和低速业务间的优化设计技术。本文在通用多协议 标记交换的框架下研究了i p 、加m 光网络中的业务量疏导问题，涉及到动态业务量 疏导、静态业务量疏导。本文的研究内容围绕以下几个方面展开： 1 针对网络中o x c 结点具有光域全波长变换能力且结点处光收发器数目和光 纤中波长数目均受限的情况，我们研究了动态业务量疏导问题： ( 1 ) 本文研究m 佩，d m 网络模型的o x c 结点是具有多跳疏导能力的，在此基础 上引入辅助图模型来解决动态业务量疏导问题。辅助图模型包含了每个结点光收 发器可利用信息、光纤上波长通道使用信息和光路的剩余带宽信息等。 ( 2 ) 针对预先规划的动态业务流，提出混合整数线形规划m i l p ( m i x e d g e r l i i 圮a rp r o g 陷m m i n g ) 数学模型，此数学模型显示地考虑到注入网络中业务连接请求 的到达时间、持续时间和带宽请求信息，为持续时间感知或随机的动态业务流模 型的疏导算法提供一个理论的上界。 8 妒o v e rw d m 光网络中业务流新型疏导与选路算法研究 ( 3 ) 针对随机动态业务流，分别分析了四种优化目标一最小化虚拓扑上业务流 的跳数、最小化物理拓扑上业务流的跳数、最小化光路的数目和最小化波长链路 数目的疏导策略。 ( 4 ) 针对持续时间已知动态业务流，提出一种新算法，此算法考虑光路、w d m 层内链路和i p 瓜，d m 层间收发器链路的剩余生存期和预期拥度，以保证在尽量减少 资源消耗的基础上，还应使流量负荷均匀分配到网络中，提高网络吞吐量。 2 静态业务量疏导是一种特殊网络优化设计问题，从以下两方面研究了静态 业务量疏导问题： ( 1 ) 在o x c 结点具有波长连续一致性约束且结点处光收发器数日和光纤中波 长数目均受限的情况下，给出静态逻辑拓扑设计的数学模型，该模型考虑了两个 优化目标最小化业务平均时延和光路拥塞。同时，给出多目标数学模型的求解方 法g 约束方法。 ( 2 ) 针对静态逻辑拓扑的多目标设计问题，提出一种新的多目标方法确定 p a r e t o 最优解集。该算法分别在逻辑拓扑设计的染色体编码、染色体聚合适应度值 计算、进化操作、非劣解集更新和外部种群非劣解集规模控制方法等方面进行阐 述，最后给出该算法的详细流程。 总之，本文在了解国内外研究现状的基础上，为光网络中的动态业务流疏导 和静态逻辑拓扑的多目标设计提供切实可行、有效的解决方案。 本文共分为五章，各章内容安排如下： 第一章：介绍i p 智能与光层技术的融合趋势、i p 、d m 网络体系结构的发展过 程和i p 愚，d m 光网络中的几个研究方向，然后给出本文研究的内容及意义，并概括 了论文内容的组织结构。 第二章：描述光网络中业务量疏导问题和r w a 问题，并对光网络中静、动态 业务流疏导算法的研究现状进行了分析。 第三章：主要进行i po v e rw d m 光网络动态业务量疏导算法研究：首先，描述 光网络o x c 结点结构模型，在此之上引入辅助图模型；其次，针对预先规划的动 态业务流，提出多层网络中业务流疏导问题的m i l p 数学模型；然后，针对随机动 态业务流，引入几种不同的疏导策略；最后，针对持续时间已知动态业务流，提 出一种新算法来进行业务流疏导。 第四章：主要进行i po v e rw d m 光网络静态业务量疏导算法研究：首先提出静 态逻辑拓扑多目标设计的数学模型，并引入s 约束方法来求解数学模型；其次， 提出新的多目标算法来寻求满足业务平均时延和光路拥塞两者指标的p 卸咖最优 前端，即虚拓扑的多目标优化设计方案集合。 第五章：描述算法的软件功能及其设计与实现，并进行算法的性能仿真。 第二章伊o v e rw d m 光网络的业务疏导算法原理与现状 9 第二章i po v e rw d m 光网络的业务疏导算法原理与现状 2 1m 哪d m 光网络中业务流疏导问题和础眦问题 2 1 1 业务疏导问题的产生 业务疏导问题来源于光网络。近年来波分复用w d m 技术的开发和应用使得光 通信网络中的信息传输容量得到了很大提高，在w d m 光网络系统中，光纤的带宽 己不再是限制光网络中传输容量进一步提高的主要因素，而网络终端的路由器、 交换机和复用器等电子设备的处理速度限制了光网络传输业务的能力。在w d m 层 各结点上，采用光学旁路技术来处理低速业务量可以解决电子设备瓶颈问题，而 业务疏导就是一种典型的旁路机制，其目的是研究如何将不同速率、不同类型的 子波长颗粒度的业务请求复用到一个波长中去。业务量疏导是g l 旧l s 中的一项关 键技术，它的正式提出始于1 9 9 8 年，现在己经引起业界的广泛关注与研究，尤其 是在近些年中关于疏导问题的研究不断深入，由最初的环网络向m e s h 结构网络发： 展。业务量疏导问题描述【l l 】为给定物理网络配置，包括物理链路连接矩阵、每个 网络结点配置的光收发器数目、每个结点的波长转换和疏导能力、每根光纤的波 长数目和波长容量等，为一组具有各种低速带宽粒度的业务连接请求建立光路以 有效地为这些连接请求分配路径和波长，同时优化网络的性能，使得连接建立的 总成本最低。 p 2 1 2 复用技术在通信量疏导中的作用 光网络中的业务量疏导可以在智能光网络的统一控制平面g m p l s 下实现，主 要涉及到三个模块：( 1 ) 资源发现协议，使用o s p f t e 或者i s i s ；等通过链路状态 通告网络资源状态；( 2 ) 路由计算，根据网络资源状态和疏导策略，为低速业务连 接请求选路，并建立端到端的连接。疏导策略反映了网络运行者资源分配意图， 是一种重要的流量工程方法；( 3 ) 信令协议，通过i 峪v p t e 或c r l d p t e 通知相应 网络结点预约资源并配置路由【1 2 】。 利用g m p l s 标签堆栈技术将低层次的l s p ( 对应于低速业务流) 汇聚到高层次 的l s p 中来实现网络业务的疏导，其中使用的复用技术包括【1 3 - 1 4 】： ( 1 ) 空分复用s d m ( s p a c e d i v i s i o nm u l t i p l e x i i l g ) 技术：将物理空间分区以达到 提高传输系统的容量。例如，将多根光纤捆绑到一根光缆上，或者多个光缆作为 一个链路连接网络中相邻两结点。 ( 2 ) 频分复用f d m ( f r e q u e n c y - d i v i s i o nm u l t i p l e ) 【i | ：1 9 ) 技术：将频谱分成不重叠 l o po v e rw d m 光网络中业务流新型疏导与选路算法研究 的一系列独立的通道。光网络中的波分复用w d m 或者密集波分复用d w d m 技术就 是采用了f d m 技术。 ( 3 ) 时分复用t d m ( t i r 一d i v i s i o nm u l t i p l e x i n g ) 技术：在时域内将带宽分成固 定长度的时隙。使用t d m 技术，多路信号只要在时间上不重叠可以共享一个波长。 ( 4 ) 动态统计复用技术：在i po v e rw d m 的体系结构中，一个w d m 波长通道可 以被多个i p 业务流通过“虚电路 方式共享。 低速业务连接请求可以是静态的，可以是动态的，因而业务疏导根据业务静 态与否可以分为静态业务流疏导和动态业务流疏导。 2 1 3 光网络的路由和波长分配 在w d m 光传送网中，给定一组光路连接需求，通过选路和波长分配算法来建 立相应光路的问题称为路由波长分配r 、 後( r o u t i n g 锄dw a v e l e n g t l la s s i 印m e n t ) 问 题。r 、凇问题是一类n p 完全问题，也就是说还没有找到任意复杂度r 、凇问题的时 间算法。由于计算资源有限，只能对规模有限的网络优化做出r w a 问题的解答。 本节讲述的重点内容就是w d m 光网络中的r 、凇问题，即介绍了r w a 问题的基本概 念和常见求解算法。 ( a ) 基本概念 根据业务请求的静、动态特性可以把r 、凇问题分为静态r 、凇问题和动态r 、 问题两类。 静态r 、凇问题相对静态业务请求而言的，静态业务请求是指预先给定且不随 时间变化的，一旦所有连接建立好后，连接将保持不变。静态r 、凇问题对各个连 接的路由和波长分配是非实时计算的，其目的是在尽可能少占用波长和收发器等 网络资源的情况下，为所有静态业务建立光通道以生成逻辑拓扑，也称为虚拓扑。 动态r 、m 问题是相对动态业务而言的，动态业务是动态到达的，在网络中维 持一段时间就会被拆除连接。动态r 、凇问题需要即时为刚到达的连接请求建立光 通道，并在通信结束后拆除光通道，其任务是根据连接请求建立光通道并分配波 长以使连接阻塞概率最小。动态r 、凇问题求解比较复杂，通常采用启发式算法。 ( b ) 常见路由与波长分配算法 则队问题通常被分解为路由子问题和波长分配子问题。通常先为光网络选路， 即先解决路由子问题，然后逐一为光通道分配波长。有时选路与分配波长的过程 要反复进行，直到使网络最优化为止。 1 ) 选路策略【l j ( 1 ) 固定路由选择策略( f i x e dr o u t i n 曲 固定路由选择策略是最直接最简单的选路算法。它的基本思想是是在网络业 第二章mo v e rw d m 光网络的业务疏导算法原理与现状1 1 务到达之前，为任意结点对问按照标准最短路径算法确定一条固定的可用路径， 即选路是离线进行的。当业务到达时，按照波长分配准则在预定好的路径上分配 波长。这种方案的优点是简单和快速；缺点是在动态流量情况下，如果出现波长 冲突，则会导致严重的流量阻塞。因为没有替代路由，所以这种算法下的网络不 具备链路故障恢复能力。 ( 2 ) 固定的备用路由选择策略( f i x e d 砧t e n l a t e dr o u t i n g ) 网络中每个结点维护一张路由表，里面存储着它到其他结点的一系列路由， 其中包括作为工作光通道的最短路由和一些作为备用光通道的路由，备用路由的 个数可根据网络性能指标要求确定。备用路由一般不跨越工作路由的链路段，即 它们在物理上是分离的，这种机制又叫做链路分离或边分离机制。当业务选择路 径时，先按照工作路由建立光路，若工作路由已被占用或失效，则在备用路由中 选择次最短路由。这种选路方法的优点是简单且比固定最短路由选择策略的阻塞 率大大降低，同时，由于引入备用路径，则这种策略还具有链路故障恢复机制。 ( 3 ) 自适应的备用路由选择策略( a d a p t i v es h o n e 小c o s t p a t l lr 0 u t i l l g ) 自适应的备用路由选择策略是根据网络状态而动态选路的方法，它为业务的 源、宿结点对间确定多条备用路由。当业务到达时，根据网络的优化目标将在多 条可选备用路由上自适地应选取一条最优径，并分配带宽。适应性路由方案有两 类方法来实现：第一种是在业务到达前预先为结点对间确定多条备用路由，当连 接请求到达时，从备用路由中依据网络状态动态选择某一路由，这与固定备用路 由方案类似；第二种是不预先为结点对确定备选路由，当连接请求到达时，根据舡 全网状态实时计算出一条相对某优化目标最优的路由，这种方式比第一种方式阻 塞率性能更优，因为它的自适应的路经计算是基于全网的，而第一种方式的自适 应只是针对离线计算的几条固定备选路径，显然，这种方式的时间计算复杂度要 高，尤其是在大规模的网络拓扑下，为每个业务都实时计算出一条最佳路径耗费 的时间有时是不可被接受的，因此要根据网络性能指标和时间复杂度来综合考虑 选择哪种方式来进行选路。 2 ) 波长分配策略i l 习 在波长总数固定的条件下，波长分配策略的目的是最大化业务连接数或最小 化阻塞率，常用的波长分配算法有： 波长随机分配算法：首先搜索所有波长的集合找出可用波长子集，再从中随 机选取波长分配给光路。这种算法最简单，并且不需要知道整个网络的状态信息。 f i i 吼一f i t ( f f ) 算法：将所有波长编号，按编号从小到大的顺序搜索可用波长， 将最先找到的可用波长分配给光路。与随机分配法相比，f f 算法的计算量较小， 分配速度也较快。 l e a 昏u s e d ( l u ) 算法：根据波长资源的占用情况，优先选取被最少链路占用的 1 2 po v e rw d m 光网络中业务流新型疏导与选路算法研究 波长。这种算法计算复杂，而且需要设置专门的存储单元记录波长的使用信息， 因此很少被采用。 除了以上三种算法，还有m o s t - u s e d ( m u ) 算法、m i n - p r o d u c t ( m p ) 算法、最轻 承载法l l ( l e a s t l o a d e d ) 、最大和算法( m a x s u m ) 、和相对容量损失算法( r c l ) 等，针对不同的优化目标选择适合的波长分配算法，有助于快速有效地解决业务 的选路问题。 2 2 动态业务流疏导算法研究现状 在动态业务量疏导中，低速动态业务请求按照某种分布顺序到达网路中，要 求进行实时疏导、路由与波长分配g r 、丙，a ( g o m 协g ，r o u t i n g 锄dw r a v e l e n g t l l 勰s i 鲫m e n t ) 计算，但维持一段时间后动态业务连接请求会离开网络，释放路径占用 的资源。动态业务流疏导的优化目标一般都是如何有效选择疏导路径和合理分配 网络资源以使得业务连接请求的全网阻塞率性能最低。传统的动态业务方法是使 用波长路由方式建立一个相对静态的虚拓扑，然后在虚拓扑上为这些低速业务连 接选路，但由于低速业务请求是动态变化不可预知的，则原先建立的静态虚拓扑 可能并不适应当前业务源分布形式，因此这种虚拓扑方式为低速连接选路会导致 网络资源利用率低。如果为每一个新到达的子波长颗粒度业务都建立一条新光路， 这样会消耗过多的链路波长和收发器，从而导致网络资源的不合理利用，同时由 于网络资源受限很可能不能建立新光路，但此业务可能会利用己有光路的剩余带 宽来成功建立路由，因此需要研究动态业务量疏导算法来高效地解决动态业务选 路问题。国内外主要研究了三种动态业务流模型：( 1 ) “传统”随机动态业务流模 型。( 2 ) 持续时间已知的动态业务流模型。( 3 ) 到达时间和持续时间完全确定的动态 业务流( 预先时间规划动态业务) 模型。 2 2 1 传统动态业务流模型的疏导算法分析 完全随机动态业务流模型是指业务到达网络的时间和在网络中驻留的时间是 不确定的，一般服从某种分布例如普遍假设到达服从泊松分布，持续时间服从负 指数分布。“