（物理电子学专业论文）roadm光环网流量疏导技术.pdf

东南大学硕士学位论文 摘要 i p 数据、语音和新型业务迅速增长，对互联网提出巨大的带宽需求。尽管波分复用 ( w d m ) 技术可满足光网络容量、距离、传输质量的大部分要求，但网络构建尚不够灵活， 运行维护费用价位仍比较高。可重构光上下路复用器( r o a d m ) 及其网络可在不影响 和不破坏已有设施和服务的同时，提供远端配置，具有灵活可重构能力和可扩展性，受 到运营商的青睐。与此同时i 接入类型的多样化使得网络带宽与典型业务链接间存在巨 大的带宽差距，如何统筹规划网络，将不同速率、不同类型的低速业务打包成高速数据 流，在最低费用下满足各类用户需求，实现有效的流量疏导具有重要意义。本文主要研 究基于r o a d m 的w d m s d h 光环网可重构、多线速及多粒度流量疏导技术。 第一章回顾了第二代光网络发展状况，介绍了目前常用的主流r o a d m 器件及其 性能，介绍了常见的流量疏导方法。 第二章针对流量疏导组合优化问题，比较了几种主要智能优化算法的性能，在此 基础上，分别建立了基于遗传算法、贪婪算法的流量疏导模型，详细讨论了两模型的 具体实现方案。 第三章主要研究r o a d m 光环网业务流量的可重构疏导问题。介绍了可重构流量 疏导概念，给出了采用数学规划方程描述该问题的数学模型。设计了较符合实际变化 情况的业务模型，基于所提出的遗传算法、贪婪算法流量疏导模型，数值分析了 r o a d m 光环网的流量疏导，证明了该环网比o a d m 环网具有更大的优势。 第四章主要研究静态业务的多线速疏导问题。因为不同线速电器件的费用不同j 对于不同的业务需求，选取适当的单线速可以降低网络费用；采用多线速获得不高于 单线速的s a d m 费用。对于该问题提出有效的解决方案，数值模拟结果证明了多线速 疏导的优势。 第五章主要研究波带、波长两级粒度的环流量疏导，以端口数目为优化目标，设计 了合理的疏导方案，最后对算法进行模拟，并对模拟结果进行了分析。 在论文最后，对所研究的问题进行了总结，并讨论了流量疏导问题进一步研究方向 和未来光网络的发展方向。 关键词：可重构光上下路复用器光环网可重构流量疏导多线速流量疏导多级 粒度流量疏导 i v 东南大学硕士学位论文 a b s t r a c t t h ed r a m a t i ci n c r e a o fi pd a t a , v o i c e ，a n dn e ws e r v i c ei ni n t e m e ti n d u c e sv a s tb a n d w i d t h d e m a n d s a l t h o u g hw d mt e c h n o l o g yc a ns a t i s f yt h er e q u i r e m e n to fo p t i c a lc o m m u n i c a t i o ni n c a p a b i l i t y , d i s t a n c e ，w a n s m i s s i o nq u a l i t ya n ds oo n , t h en e t w o r k si ss t i l ln o tf l e x i b l es u f f i c i e n t l y t h eo p e r a t i o na n dm a i n t e n a n c ec o s ti ss t i l lh i g hi nc u r r e n tw d mn e t w o r k r e c o n f i g u r a b l e o p t i c a la d d d r o pm u l t i p l e x e r ( r o a d m ) ，a t t r a c t i n gt h ea t t e n d a n c eo fc a r r i e r s ，c a np r o v i d et h e r e m o t ec o n t r o lw i t h o u td e s t r o y i n gc u r r e n tf a c i l i t i e sa n ds e r v i c e s t h et r a d i t i o n a lb a n d w i t h s e x c e e de x t e n s i v et h a nt h et y p i c a ll i n gb e c a u s eo ft h ed i v e r s i t yo ft h ea c c e s sn e t w o r k t h e r e f o r e , i th a si m p o r t a n ts i g n i f i c a n c et op a c kd i f f e r e n ts p e e da n dt y p eo fl o ws p e e dt r a f f i ci n t oh i g h e r s p e e dt r a f f i c ，w h i c hc a nm e e tc u s t o m e r s r e q u i r e sa tl e a s tc o s tt or e a l i z ee f f i c i e n tt r a f f i cg r o o m i n g n et r a f f i cg r o o m i n go fr o a d mr i n gn e t w o r k s ，i n c l u d i n gd y n a m i ct r a f f i cr e c o n f i g u r a t i o n , m u l t i - l i n es p e e da n dm u l t i - g r a n u l a r i t yt r a f f i cc o l l o c a t i o n , a r cs t u d i e di nt h i st h e s i s i nt h ef i r s tc h a p t e r , t h eh i s t o r yo fs e c o n dg e n e r a t i o no fo p t i c a ln e t w o r k si sr e v i e w e df o l l o w e d b yd i s c u s s e do fr o a d m f u r t h e r m o r e ，c o m m o ng r o o m i n gm e t h o d sa r ei n t r o d u c e di nt h i s c h a p t e r i nt h es e c o n dc h a p t e r , t h ep r i n c i p l e so fc o m m o ni n t e l l i g e n ta l g o r i t h m sw h i c hh a v eg o o d p e r f o r m a n c e si ns e a l i n gt r a f f i cg r o o m i n ga r ed i s c u s s e da n dt h ea p p l i c a t i o n so ft h e s ea l g o r i t h m s a r ei n t r o d u c e d a f t e rt h a t , t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa r ea n a l y z e d t h er e a l i z a t i o n so f g e n e t i ca l g o r i t h ma n dg r e e d ya l g o r i t h mi nt r a f f i cg r o o m i n ga r ed i s c u s s e di nt h ee n do ft h i s c h a p t e r i nt h et h i r dc h a p t e r , t h er e c o n f i g u r a b l et r a f f i cg r o o m i n go fr o a d m r i n g si sd i s c u s s e da n d a n a l y z e d t h ep a r t i c u l a r 位i 伍cm o d e l ，a c c o r d i n gt oa c t u a lt r a f f i c ，i se s t a b l i s h e dw i t hc o r r e c t w a y st os e t t l ei ta sm e n t i o n e di nf o r w a r d f i n a l l y , t h eg r o o m i n gr e s u l t s 躺a n a l y z e da n dt h e c o n c l u s i o n ss h o wr o a d m r i n g sh a v eg r e a t e ra d v a n t a g et h a no a d mr i n g s i i lt h ef o u r t hc h a p t e r , m u l t i - l i n es p e e dt l - a j 五cg r o o m i n gi si n v e s t i g a t e d b e c a u s eo fd i f f e r e n t l i n es p e e de q u i p m e n th a sd i f f e r e n tp r i c e ，t h ea p p l i c a t i o no fm u l t i - g r a n u l a r i t yw a v e l e n g t hc a n d e c r e a s et h ec o s td r a m a t i c a l l y a st h es a m er e a s o n , d i f f e r e n tw a v e l e n g t h sw o r ko nd i f f e r e n t w a v e b a n d sc a ns a v ee x p e n s eo fe l e c t r i c i t ye q u i p m e n t s t h em u l t i l i n es p e e dg r o o m i n go fs t a t i c t r a m ca r ea l s od i s c u s s e d e f f i c i e n ta l g o r i t h mi sp r o p o s e dt os e a l et h i sp r o b l e m n er e s u l t ss h o w t h a t s e l e c tp r o p e rl i n es p e e dc a nd e c r e a s et h ee x p e n s e , a n dt h ec o s to fm u l t i l i n es p e e dw i l ll o w e r t h a nt h a to fs i n g l el i n es p e e d i nt h ef i f t hc h a p t e r , t h et r a f f i cg r o o m i n go fr i n g s ，w h i c hh a v et w og r a n u l a r i t i e s ，w a v e b a n d a n dw a v e l e n g t h , i ss t u d i e d s e t t i n gt h en u m b e r so fo p t i c a lp o r t sa st h et a r g e t , o p t i m i z e dp l a no f t r a f f i cg r o o m i n gi sd e s i g n e d 1 f l 抡r e s u l t s 批a n a l y z e df i n a l l y f i n a l l y , t h ec o n c l u s i o n sa r ed r a w n k e yw o r d s ：r o a d m ；r e c o n f i g u r a b l et r a f f i cg r o o m i n g ；m u l t i - l i n es p e e dt r a f f i cg r o o m i n g ； m u l t i - g r a n u l a r i t yt r a f f i cg r o o m i n g v 东南大学硕：t 学位论文 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：垒垂叁 日 期z 理皇咄 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。 本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外， 允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文 的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：盔塞当导师签名：刍生薹刍 i i i 第一章绪论 第一章绪论 随着社会的不断进步，通信向大容量、长距离、高质量方向发展是必然的趋势。特 别是i n t e r n e t 的迅猛发展，使得用户对网络提出巨大的带宽需求，光通信特别是波分复用 技术( w a v e l g t l ld i v i s i o nm u l t i p l e x i n g ) 能够很大程度上满足容量、距离、传输质量的要 求，使光网络成为通信传送网的主要架构。因此，光通信技术的发展深深地影响着人们 的日常生活。 1 1 光网络的发展 光网络无论是在传输技术上还是在光传输网络的部署和应用上都日趋成熟，但随着 人们对网络服务质量、灵活性的要求不断加强及视频、数据等新业务的不断出现，各种 新技术不断涌现。我们简要回顾和展望一下光网络的发展历程。 第一代光网络以s d h ( 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 ，同步数字体系) 和w d m 技术为 代表，在s d h 出现之前，各国大多使用准同步数字体系p d h 技术。p d h 存在很大弊端： 缺乏统一标准、准同步复用上下路很不方便、网络管理能力弱、缺乏灵活性并且主要面 向的是语音业务。s d h 相比p d h 有了很大的进步，它具有全球统一速率、信号帧结构和 信号码型标准，以点到点波分复用w d m 传输系统为基础，能够提供大容量、长距离、 高可靠的业务传输。 但第一代光网络中，光纤仅仅单纯地取代铜质电缆成为传输媒质，而在网络节点数 据的处理和交换都是由低速的电子设备来完成的，低速业务流在每一个中间节点都要经 过光电光变换并进行处理。在第一代光网络中w d m 技术被仅仅用于点到点传输，它提 供了原始的传输带宽但不能实现灵活的组网。 第二代光网络在上世纪9 0 年代提出，它以光传送网o t n ( o p t i c a lt r a n s p o r tn e t w o r k ) 为代表，在光层上实现传输、再生、交换、选路和其他功能，成为真正意义上的“光”网 络。信号以光的形式穿过整个网络，中间不经过任何光电交换，实现在任意时间、任意 地点、任意帧格式信号的透明传输。节点能把非本节点的业务在光域中进行交换旁路掉， 从而大大减轻了节点上进行电处理的压力，消除了中间节点的电处理瓶颈。常用的光层 设备有光交叉连接器o x c ( o p t i c a lc r o s sc o n n 优- t i o ne q u i p m e n t ) 和光分插复用器 o a d m ( o p t i c a ia d d d r o pm u l t i p l e xo a d m ) 等。 图1 - 1 为第二代光网络中典型的w d m s d h 光环网结构，网络由2 个s d h 环构成，环 和环之间由o x c 来连接，环内由器件光分插复用器o a d m ( o p t i c a la d d d r o pm u l t i p l e x o a d m ) 来上下路本地业务，s d h w d m 环的具有很好的保护和倒换技术，提供各种保护 机制，当链路失效时可以提供小于5 0 m s 的业务恢复时间。 东南大学硕上学位论文 图l - ls d h w d m 光环网 下一代光网络以自动交换光网络( a s o n ) t l 】为代表，n u t 将自动交换光网络定义为 “通过能提供自动发现和动态连接建立功能的分布式( 或部分分布式) 控制平面，在o t n 或s d h 网络之上，实现动态的、基于信令和策略驱动控制的一种网络。” 2 1 能够满足网络 越来越高的智能化、自动化、多粒度交换、q o s 保证和流量工程方面的要求。 第二代光网络只涉及对信号的传送、复用、交叉连接、监控和保护恢复，是一个静 态的网络。由于口业务的动态特征，网络的业务需求呈现出很大的波动性，这种波动性 要求网络能够动态地进行调整，来适应业务的变动。人们对光网络的灵活性、可扩展性、 可重构性提出了更高的要求。 作为光网络重要节点之一的光上下路复用器( o a d m ) 以其灵活性和可扩展性受到 运营商的亲昧【3 】1 4 l 。o a d m 大致上可分为两类：固定式光分插复用器f o a d m ( f i x e ( i o a d m , ) 和可调式光分插复用器r o a d m ( r e c o n f i g u r a b l eo a d m ) 。 f o a d m 只能上下路某个或某些固定的波长信道，因此在很大程度上限制了光网络 的灵活性和可重构性。r o a d m 能动态上下路波长。在很大程度上满足这种灵活性和可 重构性。只需通过网管系统在远端配置，不必派遣技术人员到现场，极大地提高了对客 户新需求的反应速度；r o a d m 通过节点的重构能力，使得d w d m 网络也可以方便地重 构，应对突发事件的能力大大增强；可以根据网络需求进行动态的重配，在现有网络设 施上建立新业务，降低了网络费用；由于具有r o a d m 的节点可以通过软件进行操作， 为分布式控制打下基础。 锄i 翻口1 ) a k t z ) d p l 留1 ) 朋8 2 ) i i _ d d m 岱1 ) a 2 6 t 2 ) 跚 名l 留l 量2 ( r o 对于研究网络的流量疏导来说，各种o a d m ( 包括f o a d m 和r o a d m ) 无论实现 的方式怎样，都可以等效为如图1 2 所示，业务从左边进入，将本地业务通过d r o p 端口 2 第一章绪论 下路下来，同时将本地业务通过端 ：ia d d 上路到光纤中。r o a d m 和f o a d m 相比主要 的区别就是是，f o a d m 在不同时刻只能上下路同一波长，而r o a d m 可以在不同时刻 上下路不同的波长，通过各种调节机制来实现该功能。 蕞入晨 图1 - 3 城域光网络结构图 另一方面，光网络正在向城域发展，图1 3 是城域网的结构图，主要分三层即核心 层、汇聚层、和接入层。在城域网中电信网接入类型多样化，接入业务的带宽从几m b s 到几g b s 不等，网络带宽和典型业务链接之间在带宽上存在巨大差距，如何统筹规划网 络以最低的费用满足这些业务需求，具有很重要的意义。流量疏导技术就是研究如何将 不同速率的业务流、不同类型的低速率业务打包成高速数据流，复用到一个波长或波带 上，实现最小化网络费用或业务阻塞的过程。如何采用合理的疏导技术来降低网络费用 成为一个研究热点，迫切需要采用合理的疏导方案。 1 2 可重构光上下路复用器r o a d m o a d m 基本功能是从光纤中下载光通道中通往本地的业务，同时上载本地用户发 往其他节点的信号进入光纤通道，而不影响其他波长通道的传输。f o a d m 只能上下 路某个或某些固定的波长信道，在很大程度上限制了光网络的灵活性和可重构性。 r o a d m 采用光开关、滤波器等器件，能动态调节节点上下路的波长，提高网络的可 重构性。目前的研究主要为r o a d m 的各种实现技术、结构、调节限制、优化环网费 用问题等。 1 2 1 常见的r o a d m 及性能参数 r o a d m 结构主要有并联开关型、串联滤波型、波长阻断型、广播选择型等，其 关键器件为滤波器、光开关等。主要滤波和光开关技术有微机电系统m e m s 、液晶、 集成平面光波光路、光纤布拉格光栅、马赫一曾德尔干涉仪等；主要的调谐技术为热光 调谐、电光调谐等；按照r o a d m 上下路方向可分为单向r o a d m 、双向r o a d m ， 单向r o a d m 只能在一个方向上下路波长，双向r o a d m 在两个方向上都能上下路波 长，即在东向( e a s t ) 和西r 句( w e s t ) 两个方向都能上下路波长。 下面常见的三个r o a d m 分别为开关型【5 i ( 图1 4 ) 、f b g 滤波器型( 图l 一5 ) 、 波长阻断型f 6 1 ( 图1 - 4 ) 3 东南大学硕士学位论文 图l - 4 开关型r o a d m 图1 4 为开关型r o a d m ，首先用波分解复用器将光纤中波长解复用，每个2 x 2 光开关都为可调节光开关，通过调节装置决定该开关是直通还是交叉，决定该波长直 通还是下路，可重构能力通过每个光开关的调节来实现。当然也可以用光开关矩阵来 代替2 x 2 光开关。 光开关的插入损耗和响应时间是最关键的技术指标，这取决于具体的实现技术。目 前，人们可以采用微电机械( m e m s ) 、平面光波导( p l c ) 、液晶工艺等技术来实现 各种规模的光开关( 矩阵) 。其中，m e m s 光开关采用微电机械制造技术，易于集成， 且具有插入损耗小、响应速度快，信道串扰小，与波长和偏振无关、功耗低，性能优子 其它类型光开关，目前可实现l 2 、2 x 2 、l x n 、n x n 等功能配置。p l c 光开关借助于成 熟的介质波导技术，可实现器件的高度集成，结构紧凑，可靠性高，速度快。 除了光开关外，构成r o a d m 的关键器件还有分波器和合波器。分波器决定了 r o a d m 的串扰水平，一般采用隔离度较高的wdm 解复用器来实现。对于端口数( 如 8 信道以下) 较少的应用，可采用介质薄膜( tff ) 型wdm 解复用器，否则多采 用阵列波导光栅( awg ) 器件。合波器既可采用wdm 复用器来实现，也可采用耦 合器，但耦合器插入损耗高且串扰大，不适于密集信道配置应用。 图l - 5 f b g 滤波器型r o a d m 图1 5 为f b g 滤波器型r o a d m ，由环型器、f b g 滤波器、收发器组成，环型器 中波长只能沿一个方向传输，f b g 滤波器将某个波长沿原方向反射回去，该波长通过 调节装置调节，然后通过环型器下路。上路波长也通过环型器和f b g 来实现。 采用这种结构非常容易实现多波长信道操作，且结构简单，仅需在两个环形器之 4 第一章绪论 间插入多个可调谐滤波器或多个基本单元级联。其优势在于不需要满足类似于m z i 那 样的相位匹配条件。不利之处在于较大的插入损耗、串话和昂贵的环形器。 ， 图l _ 6 波长阻断型r o a d m 图1 - 6 为波长阻断型r o a d m ，从节点n o d e l 到节点n o d e 2 的波长首先经过一个 分路器，将一部分信号分路到波长阻断模块w b 中，另一部分则分路到滤波器f i l t e r 中，波长阻断模块将某特定波长阻断，阻断的波长和下路的波长相同，右去的波长中 去掉该波长，上路原理相似。可重构能力通过w b 的可调节阻断来实现。 w b 可以同时对多个波长通道的功率单独进行部分或全部衰减，容易实现动态增益均 衡和阻塞功能，多信道上下路操作方便。但由于采用光耦合器，下路信道的插入损耗较大， 较多信道配置需要采用光放大器来补偿，成本较高。 表l - i 主干网和城域网r o a d m 的实现方法和零件及系统供应商 实现方法零件供应商系统供应商 l u c e n t , c i e n a , h u a w e i ， 主干网波长阻塞 j d s u ，a v 卸e xd u p o n t , c o a d n a m a r c o n i ，s i e m e n s j d s u ，a v a n e 墨d u p o n t , c o a d n a ,a l c a t e t r o p i c ，m a h i ， 波长阻塞 l i g h t c o n n e c t , p o l y c h r o m i x , x t e l l u s l u c e n t m o v a z 小型开关 j d s u ，d u p o n t , o p m n , c h r o m u x , 城域网 c i s e o ，t e l l a b s ，h i t a c h i 阵列n e o p h o t o n i c s ，n e l 波长可选 j d s u ，d u p o n t , c o a d n a , e n g a n a , 择开关 m e t c o n n e x , c a p e l l a f u j i t s u , m e r i t o r t , n o r t e l 表1 1 为主干网和城域网络r o a d m 的实现方法和零件及系统供应商，可以看出波长 阻断型主要用在业务粒度大的情况，而小型开关阵列和波长可选择型开关用在带宽需求较 小的场合。另外还有广播选择( b r o a d c a s ta n ds e l e c t ) i r l 结构的r o a d m 、用于节省端1 2 1 数 目的波带、波长两级粒度的r o a d m s i 等。 1 2 2 波带、波长两级粒度的r o a d m 上节主要介绍的是常见的r o a d m 结构，这些结构共同点就是只能上下路一些波长。 由于上下路波长数目的增大，光端口数也将增加，为了节省网络的光端口数或光开关矩 阵的规模，提出了波带、波长两级粒度的r ( ) a d m 。 5 东南大学硕士学位论文 图1 7 为波带、波长两级粒度的r o a d m 结构图，波带交叉矩阵b x c 将光纤中的要下 路的波带下路到波长交叉矩阵中，而让其他波带中的业务直通过去，波长交叉矩阵再将 该波带中要下路的波长在本地下路，让其他波长直通过去。对于两级粒度的r o a d m ， 主要研究如何合理地选择波带交换矩阵b x c 和波长交换矩阵w x c 的规模，来减少所需 的光端口数目。 d d 弧o p 图l - 7 包含波带、波长两级粒度的r o a d m 对于波带、波长两级粒度的r o a d m ，另一个研究方向是如何采用合理的路由波 长分配算法及波长捆绑算法，在网络资源不变的情况下使业务阻塞率降低。由于采用 波带粒度，粒度大，业务请求找不到合适路由的几率增大，因此相对单级波长粒度， 网络阻塞率将会增加。如何采用合理的波长捆绑和业务选路算法来降低波带、波长两 级粒度网络的阻塞率成为一个研究热点。 1 2 3 光网络的节点结构 光网络最经典的结构是w d m s d h 环网，这是由于环网易于管理，且在链路失效 时可以很快地进行业务倒换。光网络节点的主要器件是上下路复用器a d m 和光交叉 设备o x c 。 图1 8 为包含波长、时隙( t g 称亚波长或子波长) 两级粒度的r o a d m 结构，光 纤中包含w l 、w 2 、w 3 三个波长，其中波长w l 中无业务在本地下路，o a d m 将其旁 路过去，w 2 、w 3 两个波长包含有本地业务，因此通过o a d m 将其在本地下路。电复 用器件a d m 将下路的波长w 2 和w 3 中包含本节点信息的时隙( 亚波长) 下路，而让 其他时隙旁路过去，数字交叉设备d c c 实现亚波长( 时隙) 量级信息的交换。 d m ： d m j l | l 图l - 8 典型的光环网节点结构 一个包含波带、波长两级粒度的o x c 结构如图1 9 所示，为了节省网络端口数目， 6 第一章绪论 先将光纤中的波长分为b 个波带，每个波带包含w 个波长，波带交换矩阵b x c 将包 含本地业务的波带在本地下路，而让其他波带旁路。波长交换矩阵w x c 将下路的波 带中包含本地节点信息的波长下路，而让其他波长旁路过去。 图1 - 9 为包含光纤、波带、波长三级粒度的o x c 结构1 9 】【l 们，分别通过f o x c 、 b o x c 、w - o x c 三个交换矩阵将包含本地业务的光纤、波带、波长下路，而让其他旁 路过去。采用多粒度的o a d m 和o x c 可以节省网络的端口数。 垒毯生垒垫坚- ? * 一一勰，o 嘲p 固h “ _ 誓? 7 l ： - o x c ”4 = = = i ti _ 。一 娜l t t t l u t 图1 - 9 包含光纤、波带、波长三级粒度的节点器件o x c 1 3 流量疏导技术 目前电信网络主要架构仍然是同步数字体系( s d h ) 光网络。随着波分复用( w d m ) 技术的应用，单根光纤通过波分复用( w d m ) 可承载更多波长，而每个波长又可通过时 分复用( t d m ) 的方式容纳许多低速业务流。 在s d h 环网中，终端设备s d ha d m ( s a d m ) 的成为网络的主要费用份额。在每个 节点处放置光上下路复用器o a d m 可以有选择地下路一些波长，而将其他波长直通过 去，通过恰当地疏导业务连接请求，可以在很大程度上减少整个网络的s a d m 数， 减 少网络的费用。 流量疏导( 1 l l f l 2 l 【”1 研究的就是如何将不同速率、不同类型的低速业务流打包成高速数 据流，复用到一个波长上，以最小化网络费用的过程。 图1 8 是s d h 环节点的结构图【1 4 1 ，光纤中有三个波长w 1 ，w 2 ，w 3 。通过光上下路复用 ：器r ( o a d m ) 将光纤中那些对本节点有用的波长w 2 , w 3 下路，而将其他波长w l 光学旁路， 然后利用s a d m 将下路的波长进行时分解复用，将那些对本节点有用的时隙( 子波长) 下路，将其余时隙直通过去，下路一个波长就需要一个s a d m ，该节点共需要2 个s a d m 。 也可以在本节点配置一个数字交叉设备d c c 将业务在不同波长中交叉，即将业务从一个 s a d m 交换至另一个s a d m 。 7 东南大学硕士学位论文 目前关于流量疏导已有很多研究，研究的业务类型从单一均匀业务至动态任意业 务，网络拓扑也从单h u b 环网到格状网( m e s hn e t w o r k s ) 1 1 5 1 1 6 1 、多播网( m u l t i - c a s t n e t w o r k s ) ! 】等，并和一些技术( 如业务分叉、可重构技术、业务交换、业务分解) 结合。 1 3 1 静态业务流量的疏导 在流量疏导中，根据网络中业务需求是否发生变化，把流量疏导分成两类：静态流 量疏导与动态流量疏导。 静态流量疏导是指对组己知且不随时间变化的业务需求进行疏导，其目的是使用 最少的s a d m 来支持这组业务。 静态业务疏导研究最早，业务类型从均匀单一业务到非均匀业务，网络拓扑从简单 环网到包含h u b 的环网，再到网状网( m e s hn e t w o r k ) 、树网( t r e e ) 等。 疏导算法由最早的对单一业务的算法，到环构造算法( c i r c l ec o n s t r u c t ) 、遗传算法、 模拟退火算法等现代启发式算法。优化目标一般是需要的s a d m 数，也有以收发器个数 为目标的。在追求最小化s a d m 数同时也追求最小化波长数o 静态业务流量的疏导是最基本的疏导，也是最简单的疏导。但是它是其他疏导问题 的基础，对疏导算法的要求也最严格。 1 3 2 动态业务流量的疏导 动态流量疏导是对一组随时间变化的业务需求进行疏导，其目的是使用最少的a d m 来支持这组变化的业务。近几年来，飞速发展的i p 业务是一种突发性很强的数据业务， 因而对于应用于此领域的动态流量疏导是很大的挑战，也进一步体现了应用于 p o 、他r - w d m 中的流量疏导的巨大商业价值。 动态流量疏导是目前光网络研究中的一个热点。网络可重构指的是在流量疏导过程 中，网络的虚拟拓扑或物理拓扑可根据需要进行重构。动态业务网络可重构疏导1 1 8 1 是指， 在原来网络业务分布基础上，为满足新的业务需求而对网络进行重构( 包括光通道拆卸 重建、节点的a d m 个数增减、业务分叉、网络粒度变化等) ，使其从一种拓扑结构转变 为另一种新的拓扑结构，从而实现业务的动态流量疏导的一种新型动态流量疏导模型。 目前有关动态业务的研究已经很多，研究的网络拓扑从环状网到树网、网状网等， 业务从单播到多播，疏导技术包括了业务分叉1 1 9 1 ( t r a f f i cs p l i t t i n g ) 、业务分解等等。 1 3 3 业务流量的多线速疏导 多线速( m u l t i p l el i n es p e e d s ) 是指在网络中采用多个业务粒度的波长来携带业务。 例如，在8 节点环网中有8 个波长可用，其中4 个工作在s t m _ 4 线速，而其他4 个工作在 s t m 1 6 线速。 由于不同规模的s a d m 的费用不同，例如，规模为s t m 1 6 的s a d m 是规模为s 刑一4 的s a d m 价格的2 3 倍。根据不同的业务需求情况，采用多线速或者选择恰当的线速可以 在很大程度上降低整个网络的费用。 文献1 2 0 1 第一次分析了双线速u p s r 环网的流量疏导问题，文酬2 1 】1 2 2 1 对单h u bu p s r 8 第一章绪论 环网的多线速流量疏导进行了分析，但未将波长个数作为约束条件，结果很多疏导结 果可能不能实现。文献【1 7 】对环网多线速流量疏导问题作了较为详细的分析，用整数非 线性规划描述了多线速流量疏导问题，并用整数非线性规划求解器对其直接求解，又 设计了启发式算法以减少求解时间；但其业务需求模型太过简单，而且未考虑业务在 不同线速问分叉的情况。本文采用与文献【1 7 】不同的方法对多线速流量疏导问题进行分 析，用一组更全面的整数非线性规划方程来描述多线速流量疏导问题，并设计了比较 好的启发式算法对其进行求解，最后对疏导结果进行了分析。 1 3 4 业务流量的多粒度疏导 对网络业务流量的研究表明，相当一大部分的业务( 占到业务总量的6 0 8 0 ) 在节 点无须进行较小等级粒度( 如子波长、波长) 的交换，而可以在较大的粒度层次( 如波带、 光纤) 上直通1 2 3 1 。因此，人们希望光网络中的节点能具有灵活的交换能力。伴随着智能 光网络( i o n ) 和通用多协议标签交换( g m p l s ) 控制技术的出现，多粒度交换技术应运而 生。通过在多个粒度( 子波长、波长、波带、光纤) 层次上进行有选择的分层交换，光节 点的结构可以大大简化，端口数减少，设备的成本随之显著降低。 业务流量的多粒度疏导根据业务类型可分为：静态业务的多粒度疏导和动态业务 的多粒度疏导。 多粒度疏导也称为波带交换技术( w a v eb a n ds w i t c h i n g ) 或波带疏导，目前静态业务 的多粒度疏导以节省网络端口数目为主要目标，而动态业务的多粒度疏导主要目标是 在已知网络资源时用最合理的疏导算法来使网络的阻塞率最小。静态业务的多粒度疏 导主要是用到波带交换技术1 2 4 1 。 流量疏导是一个重要的前沿和热点问题，是科技含量和商业价值并重的较新的研究 课题，高效疏导能能够很大程度上降低网络的建造成本( 主要是s a d m 个数) 。目前对它 的研究主要应用智能优化算法或是通过设计出各种启发性算法进行求解。 静态疏导主要用遗传算法、模拟退火算法等智能优化算法及启发式算法等。动态疏导 是在静态疏导的基础上对多个业务矩阵疏导，疏导结果要求满足一组业务。研究的网络拓 扑从环状网到树网、网状网等，业务从单播到多播，采用业务分叉( t r a f f i cs p l i t t i n g ) 、 业务分解、可重构疏导、多线速疏导和多粒度疏导等技术，总能够得到更低的网络费 用。 1 4 本文主要研究内容 本文的主要研究内容如下： 第二章介绍了解决组合优化问题的智能优化算法，并对各种算法性能做了比较。 介绍了遗传算法生物基础、原理及实现技术；提出流量疏导的遗传算法和贪婪算法的 解决方案；并介绍了贪婪算法原理及其在该问题中的应用。 9 东南大学硕士学位论文 第三章介了绍流量疏导概念、疏导方案和研究现状，结合r o a d m 光环网的特点 介绍了光环网业务流量的可重构疏导。以s a d m 为主要优化目标，设计环构造算法解 决环网的静态业务疏导；然后根据网络业务的变化情况，建立了动态业务流量模型， 在环构造算法的基础上设计启发式算法对l o 套业务进行疏导；证明了算法的有效性， 及用r o a d m 环网代替o a d m 环网能够节省网络费用，计算s a d m 数随业务变化的 情况。 第四章我们采用多线速对静态业务进行疏导，首先分析多线速流量疏导问题，然 后建立该问题的数学模型，接着对不同网络负载，分别设计了采用单线速和多线速疏 导的贪婪算法和环构造算法解决方案，分析了对于不同业务强度如何选取合理的线速 来降低网络费用，以及采用多线速可以降低网络费用。 第五章探讨了r o a d m 环网流量的多粒度疏导，以端口数为优化目标，设计合适 的疏导方案对单级粒度环网和两级粒度环网的静态业务进行疏导，证明波带波长两级 粒度较单级波长粒度更能节省端口数。 在文章的最后，对本文进行了总结，并指出了光网络的发展方向和流量疏导的研 究方向。 l o 第二章智能优化算法 第二章智能优化算法流量疏导模型 光环网流量疏导问题可归结为统筹学中的整数非线性数学规划问题，也是一个数 学优化问题，可转化为旅行商t s p 问题或是背包问题，解空间随业务的规模成指数增 长肿h a r d 问题) ，当节点个数增大时，简单地验证全部的解会浪费大量的时间。一般 都会根据实际问题，采用合理的启发式算法或者将问题分解开来解决。 由于遗传算法( g e n e t i ca l g o r i t h m ) 皿5 1 、模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ) 2 6 1 、贪婪算法( g r e e d ya l g o r i n l m ) 和禁忌搜索1 2 r l ( t a b us e a r c h ) 等现代智能优化算法特别 是遗传算法，能够很好地解决流量疏导问题。我们将在本章中介绍常用智能优化算法的 原理与优缺点，然后探讨遗传算法和贪婪算法的基本原理及在流量疏导中的应用。 2 1 智能优化算法 智能优化算法又称为现代启发式算法，具有全局优化性能、通用性强、且适合于 并行处理的算法。这种算法具有严密的理论依据，可以在一定的时间内找到最优解或 近似最优解，能够很好地解决组合优化问题。 2 1 1 常用的智能优化算法 常用的智能优化算法包括从局部搜索和爬山算法中发展而来的禁忌搜索、将统计物理 学中的退火思想应用于组合优化理论的模拟退火算法、将生物神经系统的工作原理应用于 机器学习、模式识别和组合优化领域的人工神经网络、从生物进化原理中获得启示的遗传 算法和人工蚁群算法网、以及用于提高局部搜索能力的贪婪算法等等。 1 遗传算法 遗传算法( g a ) 是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化、 并行搜索算法，模拟自然中的生命进化机制。g a 包含三个基本算子：选择；交叉； 变异。通过这三个算子的共同作用使群体经过一系列迭代得以朝着更好解的方向进 化。主要优点是：1 ) 以决策变量的编码作为运算对象，使得g a 不受函数约束条件限制； 2 ) 可以直接根据目标函数值进行搜索；3 ) 同时使用多个搜索点的搜索信息；4 ) 选择、 交叉和变异都是以概率的方式来进行，增加了其搜索的灵活性；5 ) 具有全局搜索能力。 6 ) 同其它启发式算法有较好的兼容性。 g a 能够解决大多数组合优化问题，但不能解决超大规模的优化问题，容易“早熟”、 爬山能力差等弱点。 2 模拟退火算法 模拟退火算法( s a ) 主要用于解决组合优化问题，是模拟物理中晶体物质的退火过 程而开发的一种优化算法。在对固体物质进行模拟退火处理时，通常先将它加温熔化， 使其中的粒子可自由运动，然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶 东南大学硕士学位论文 格。若在凝结点附近的温度