（通信与信息系统专业论文）sdh网络性能优化算法研究.pdf

摘要 摘要 随着信息技术的高速发展，用户对图像、音频、视频等多媒体信息的需求量 急剧上升，对网络带宽的需求和对网络的高速互联正在成为令人瞩目的问题。光 传送网( o p t i c a lt r a n s p o r tn e t w o r k ，o t n ) 由于能够提供大量的带宽和高速的传输 速率而得到了快速的发展和广泛的应用。对光传送网的网络规划也成为了一个研 究的热点。光传送网是个多层的网络，在各个层次有不同的网络技术。其中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 ，同步数字体系) 是光传送网使用的主要技术。如 何优化s d h 网络的性能成为网络规划的一个重点。 本文针对s d h 网络资源的优化配置、路径恢复优化以及时隙分配问题进行了 相关研究。 在本文第二章，研究了网络中如何给业务分配资源，减少阻塞同时最优化资 源利用，提高网络性能。提出了一种双重迭代的启发式算法，以及一种链路权重 的设置方法。该链路权重的设置方法可以在业务的路由选择阶段，尽可能避开已 经负载很重的链路，提前避免链路拥塞的出现。双重迭代的算法，从全网所有业 务到局部业务的迭代调整，使得网络能够找到最优的资源配置策略。 在本文第三章，研究了如何在不中断业务的前提下，将业务的当前路径恢复 到原始路径上的问题。提出了一个冲突集的概念以及一种中间态过渡的方法，最 大可能的达到不中断的路径恢复。 在本文第四章，研究了s d h 网络中业务的时隙分配问题。无论是环网业务、 网状网业务，还是专用保护、共享保护、无保护业务，以及有各种属性的业务， 如级联业务、虚级联业务、带约束业务，所提出的时隙分配算法都可以应对。同 时该算法还能达到减少资源碎片，提高资源利用率的效果。 最后是全文总结。 本文对所提出的算法都进行了仿真，仿真结果表明这些算法性能良好。 关键词：资源分配，网络规划，路径恢复，时隙分配 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , p e o p l e sd e m a n d so fm u l t i m e d i a i n f o r m a t i o ns u c ha sg r a p h i c s ，a u d i oa n dv i d e oi n c r e a s ei na h i g h l ys p e e d h o wt os a t i s f y t h en e e df o rh u g en e t w o r kb a n d w i d t hi sn l li m p o r t a n tp r o b l e m f o rt h i sr e a s o n ，o t n ( o p t i c a lt r a n s p o r tn e t w o r k ) 谢也h u g eb a n d w i d t hd e v e l o p sr a p i d l y h o wt op l a no t n i na l le c o n o m i ca n de f f e c t i v ew a yi sah o ts p o ti nr e s e a r c hf i e l d a sam u l t i l a y e r n e t w o r k , o t ni n c l u d e sd i f f e r e n tt e c h n o l o g i e so nd i f f e r e n tn e t w o r kl a y e r s ，e g ，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 ) i no t nn e t w o r kp l a n n i n g ，h o wt oo p t i m i z et h e p e r f o r m a n c eo fs d h n e t w o r ki sap r i o r i t yi nn e t w o r kp l a n n i n g i nt h i sp a p e r , t h ea u t h o rs t u d i e st h r e ec a s e si ns d hn e t w o r kp l a n n i n g ：t h er e s o u r c e a l l o c a t i o n ，p a t hr e c o v e r ya n dt i m e s l o ta s s i g n m e n t i nc h a p t e r2 ，t h ea u t h o rs t u d i e sh o wt oa l l o c a t er e s o u r c e sa n dr e d u c ec o n g e s t i o n w h i l eo p t i m i z i n gr e s o u r c eu t i l i z a t i o na n di m p r o v en e t w o r kp e r f o r m a n c e a u t h o r p r o p o s e sad u a li t e r a t i v ea l g o r i t h ma n dal i n kw e i g h ts e t t i n gm e t h o d s t h el i n kw e i g h t s e t t i n gm e t h o dc a na v o i dt h ea p p e a r a n c eo fl i n kc o n g e s t i o na sp o s s i b l ew h e nr o u t i n g t h ed u a li t e r a t i v ea l g o r i t h mo p t i m i z e st h ep e r f o r m a n c eo ft h en e t w o r kb yg l o b a l i t e r a t i o nf o ra l ld e m a n d sa n dl o c a la d j u s t m e n tf o rs o m ed e m a n d s i nc h a p t e r3 ，t h ea u t h o rs t u d i e sh o wt or e c o v e r yt h ec u r r e n tp a t h st om e i ro r i g i n a l o n e sw i t h o u tt h ei n t e r r u p t i o no fd e m a n d s i ti so f t e na ne n g i n e e r i n gp r o b l e m a u t h o r p r o p o s e sac o n c e p to fac o n f l i c ts e t , a n da ni n t e r m e d i a t es t a t et r a n s i t i o nm e t h o d ，t h e m a x i m u mp o s s i b l et oa c h i e v en o n d i s r u p t i v ep a t ht or e c o v e r y i nc h a p t e r4 ，t h ea u t h o r ss t u d i e dt h et i m e s l o ta s s i g n m e n ti ns d hn e t w o r k t h e t i m e s l o ta s s i g n m e n ta l g o r i t h mt h ea u t h o rp r o p o s e dc a nd e a lw i t ha l m o s ta l ld y n a m i c d e m a n d si nm e s hn e t w o r k so rr i n gn e t w o r k s ，s u c ha ss p e c i a lp r o t e c t i o nd e m a n d s ，s h a r e d p r o t e c t i o nd e m a n d s ，n o n p r o t e c t i o nd e m a n d s i na d d i t i o n ，t h ea l g o r i t h mc a nd e a lw i t h d e m a n d sw h i c hh a v ec o n s t r a i n s t h ea l g o r i t h mc a nr e d u c et h er e s o u r c ef r a g m e n t a t i o n a n di m p r o v er e s o u r c eu t i l i z a t i o nr e s u l t s i nt h i s d i s s e r t a t i o n ，s i m u l a t i o n r e s u l t si n d i c a t et h e p r o p o s e da l g o r i t h m s p e r f o r m a n c ew e l l 1 i a b s t r a c t k e y w o r d s ：r e s o u r c ea l l o c a t i o n ，n e t w o r kp l a n n i n g ，p a t hr e c o v e r y , t i m e s l o t a s s i g n m e n t i i i 缩略语表 l s p s b p p 口 i t u i l p i e t f o t n p d h s t m s o n e t s d h 缩略语表 l a b e ls w i t c h e dp a t h s h a r e db a c k u pp a t hp r o t e c t i o n i n t e r n e tp r o t o c o l i n t e r n a t i o n a lt e l e c o m m u n i c a t i o nu n i o n i n t e g e rl i n e a rp r o g r a m m i n g i n t e r n c te n g i n e e r i n gt a s kf o r c e o p t i c a lt r a n s p o r tn e t w o r k p l e s i o c h r o n o u sd i g i t a lh i e r a r c h y s y n c h r o n o u st r a n s f e rm o d e s y n c h r o n o u so p t i c a ln e t w o r k 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 v i 标签交换路径 共享备份路径保护 网际协议 国际电信联盟 整数线性规划 i n t e m e t 工程任务组 光传送网 准同步网 同步转移模式 同步光网络 同步数字体系 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 墨墨壹日期：z 口矽年月z 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：断导师签名：虚竖茎 日期：2 吖汐年占月2 日 第一章绪论 1 1 引言 第一章绪论 随着通信的快速发展，以话音为主的传统电信网络在带宽、服务质量、网络 速率等方面，已经无法满足互联网迅速增长的用户需求，也无法满足图像、视频、 v o d 、i n t e r n a 介入等日益多样化的业务。人们希望现代传送网能够有效、快速且 经济地提供各种服务，而传统电信网络不仅业务单调、带宽局限，而且扩展复杂。 由于光传送网( o p t i c a lt r a n s p o r tn e t w o r k ，o t n ) 可以满足大容量、高速率和 长距离的信息传输，所以得到了迅速的发展。而光传送网使用的主要技术是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 ) 技术。s d h 技术可以满足高传输速率、高质量信 息服务的要求，以及灵活组网的要求。 如今s d h 技术已经是一种成熟、标准的技术，其巨大的带宽优势和技术优势 在光传送网中得到了非常广泛的应用。本章首先简要介绍了s d h 网络，然后叙述 了s d h 网络的性能优化问题，最后是全文的组织结构和在s d h 网络性能优化方 面的研究贡献。 1 2s d h 网络简介 当今人类进入到高度发达的信息社会，要求高质量的信息服务与之相适应， 也就是要求现代通信网向着数字化、综合化、宽带化、智能化和个人化方向发展。 随着互联网的迅速发展，用户对多媒体信息的需求急速上升，使得网络的带宽、 速度和服务质量成为优化通信网性能的主要问题。传统的准同步网( p l e s i o c h r o n o u s d i g i t a lh i e r a r c h y ，p d h ) 自身的一些局限性，使其已经不能满足当今以光纤为代 表的大容量传输技术，无法适应现代通信网的发展要求。 高速的容量光纤通信技术和智能网技术的迅猛发展加速了传输网体制的变 革。1 9 8 4 年，美国b c u c o r e 实验室的美籍华人金耀周先生最早提出了同步光网络 ( s y n c h r o n o u so p t i c a ln e t w o r k i n gs o n e t ) 的概念。1 9 8 5 年，美国国家标准协会 ( a n s i ) 提出了构建全同步数字传输网的想法。1 9 8 7 年，s o n e t 成为北美的标 准。一年后，国际电报电话咨询委员会( c c i t t ，后来改成i t u 国际电信联盟) 电子科技大学硕士学位论文 接受了s o n e t 的概念，并将其重新命名为同步数字体系( s y n c h r o n o u sd i g i t a l h i e r a r c h ys d h ) ，使之不仅仅可以应用于光纤通信，也可以应用在微波和卫星的传 输中。 自1 9 8 8 年1 1 月批准的第一个s d h 标准至今，已经通过了数十个s d h 的标 准。这些标准涉及到几乎所有的网络应用：比特率、光接口、复用结构、网络节 点接口、复用设备、线路系统和网络管理，以及s d h 网络结构、信息模型、误码 性能、抖动性能和环形网等。 s d h 传输技术能够提供非常灵活且经济的通信网络基础结构，是大容量同步 光通信网络的国际标准。s d h 的特点主要体现在如下几个方面【1 】： 1 ) 有全世界统一的网络节点接口和光接口标准：实现了横向兼容和不同厂家 生产的设备在光线路上的互通； 2 ) 良好的兼容性：s d h 网络不仅仅可以同p d h 网络完全兼容，还可以容纳 各种新业务信号，成为公共的传输平台； 3 ) 传输速率高，传输容量大：通过将s t m ( 同步传送模块) 信号按码块或者 字节间插同步复用成为高速的s d h 信号； 4 ) 灵活的复用结构：s d h 采用指针技术，可以直接从s t m - n 中灵活的上下 支路信号，不需要通过逐级复用就能够实现分插的功能，节约了设备； 5 ) 拥有完善的保护和恢复机制：s d h 设备可以组成有自愈保护功能的环网， 以此有效地避免传输媒介被切断所造成的业务终止，从而提高网络的可靠性： 6 ) 强大的网络管理能力：s d h 帧结构中丰富的开销比特可以满足网络运行、 管理和维护得需求； 7 ) 组网灵活：s d h 有多种网络拓扑结构，可以灵活的组成各种网络。 基于s d h 体制所开发的各种传输设备，已经可以从根本上解决网络中所要面 临的关于质量、容量、安全、网管等问题。由于s d h 设备类型多种多样、电路调 度管理灵活、网络管理能力强等优点，使得在网络组织上有了更多的选择空间。 降低维护成本和改善服务质量一直是电信运营商追求的根本目标。电信部门对 于新入网设备，在操作的灵活性、设备的可靠性及维护的自动化程度等方面都较 以往有了更高的要求。作为电信基础网的s d h 传送网，完善的s d h 管理系统对 与全网的成本维护与服务质量有着深刻的意义。和以往的p d h 传输系统相比，s d h 技术在帧结构中设置了非常丰富的开销字节( 大约占信号的5 ) 用于网络管理。 2 第一章绪论 由于以上所述的s d h 技术的众多优势，使其在广域网领域和专用网领域也得 到了巨大的发展。电信、联通、广电等电信运营商都已经大规模建设了基于s d h 的骨干光传输网络。利用大容量的s d h 环路来承载a t m 业务、p 业务或者直接 以租用电路的方式出租给企、事业单位。另外，一些大型的专用网络也采用了s d h 技术来架设系统内部的s d h 光环路，以承载各种业务。比如电力系统中，就是利 用s d h 环路来承载内部的视频、语音、数据、远控等业务。 而对于那些组网更加迫切、又不可能架设专用s d h 环路的单位，大多都采取 租用电信运营商电路的方式。因为s d h 技术是基于物理层的，单位可在租用的电 路上面承载各种业务同时不会受到传输的限制。承载的方式多种多样，不仅仅可 以利用基于t d m ( t i m ed i v i s i o nm u l t i p l e xa n dm u l t i p l e x e r ) 技术的综合复用设备 来实现多业务的复用，还可以利用基于口的设备来实现多业务的分组交换。s d h 技术能够真正的实现租用电路的带宽保证，在安全性方面也优于v p n ( v i r t u a l p f i v a t en e t w o r k ) 等方式。对于政府机关和对安全性非常重视的企业来说，s d h 租 用线路得到了非常广泛的应用。并且在价格方面，也已经被大部分的单位所接受。 随着网络的发展，s d h 已经成为传送网的重要组成部分。s d h 技术与其他一 些先进技术的结合，比如i n t e m e t 技术( i po v e rs d h ) 、光波分复用技术( w d m ) 等等，使得s d h 网络的作用逐渐增大，不可或缺。 1 3s d h 组网及保护 1 s d h 组网 s d h 传输网是由一些不同类型的基本网元设备与光缆线路连接形成的拓扑结 构组成的。与传统的p d h 系统构成的网络相比，s d h 传输网具有控制简单、组网 灵活、生存性强等突出优势。而s d h 网络灵活的组网能力是通过如数字交叉连接 设备、分插复用器这些基本的网元设备实现的。 s d h 组网的基本网元有终端复用器、分插复用器、再生中继器以及数字交叉 连接设备。终端复用器的主要功能是将s d h 的1 5 5 m b s 电信号这些支路端口的低 速信号复用进s t m - n 帧结构中，并且经过电一光转换为s t m - n 光线路信号【2 1 。终 端复用器同时还可以完成上述过程的逆过程。分插复用器在s d h 网络中占有重要 地位，是最具有特色并且最被广泛使用的基本网元设备。它可以将标准中规定的 各种接口信号s t m n 信号接入s t m m ( m n ) 内作任何支路的能力。在环网应 电子科技大学硕士学位论文 用中，利用分插复用器组成的自愈环网极大提高了网络的生存性，这使得它倍受 青睐。再生中继器用用来恢复经长距离传输而衰减变形的信号。数字交叉连接设 备也是s d h 网络中的重要基本网元，它的主要功能是完成多个s t m - n 信号的交 叉连接，是实现传输网有效管理、可靠的网络保护恢复、自动化配线盒监控的重 要手段。 ， 常用的s d h 网络拓扑主要有两种形式：环状拓扑和网状网拓扑。图1 。1 所示 的是有分插复用器组成的环状拓扑，该拓扑最大的优点是可靠性高。即使这种网 络拓扑中的任何一点发生断裂，网络都可以依靠自身的自愈功能迅速恢复业务。 这种特性可以满足现代大容量光纤网络对高可靠性的要求，所以环状拓扑在s d h 网络中得到了最广泛的应用。同时，环状拓扑有存在一个主要缺点：至少需要1 0 0 的冗余保护容量，这个不得不导致网络资源使用效率低。图1 2 所示的是由数字交 叉连接设备直接互连行程的网状网拓扑。如果所有的节点都直接互连时则成为理 想网状网拓扑。网状网拓扑结构的优点表现在不受节点瓶颈问题和失效的影响， 两节点间有多种路由可选，可靠性很高，但是它的缺点就是结构复杂、成本较高。 图1 - 1 环状拓扑 图i - 2 网状网拓扑 2 s d h 保护 当今高速发展的信息社会中，入们对信息交换的依赖性日益增大。通信网络 的可靠性和安全性是保障全世界每天信息海量交换的必要条件。如果出现网络故 障，可能会造成网络瘫痪的严重后果，使得整个社会蒙受巨大的经济损失。因为， 4 第一章绪论 网络的保护是网络运营商和用户最为关注的问题。 s d h 保护分为线路保护和共享环状保护两种。线路保护主要是指路由备用线 路保护。线路保护系统包含主用、备用两套光纤。工作原理是：当工作光纤的业 务传输中断或系统性能劣化到一定程度后，系统倒换设备将主信号自动转至备用 光纤传输，即工作通道倒换到保护通道，使业务能够继续传输。按照业务通路和 保护通路的利用情况，可分为1 + 1 保护方式和l ：n 保护方式，也就是专用保护和 共享保护。共享环状保护是利用自愈环，在网络发生故障时，不需要人为干预， 可在极短的时间内自动从故障中恢复所携带的业务。 3 s d h 与m p l s 相结合 s d h 是基于o s i 网络模型一、二层的传输协议。s d h 采用光纤做为传输介质， 其吞吐量大，基于此原因，i s p 及其用户比较倾向于采用s d h 来互连路由器。s d h 将很多路光信号调制复用成不同波长的一路光信号，在另一端再解复用回来，从 而实现多路信号在一条光纤上传播。s d h 核心就是应用了波分多路复用技术，s d h 网络是a t m ，d d n 等中继网络服务的承载网。 m p l s ( m u l t i p r o p o c o ll a b e ls w i t c h i n g ) 即多协议标记交换，位于传统的第二 层和第三层协议之间，其上层协议与下层可以是当前网络中的各种协议。如：i p x ， i p ，a p p l e t a l k 等。m p l s 使用标签的方式进行快速转发，将p 地址映射为简 单的具有固定长度的标签。 s d h 与m p l s 相结合，在网络上能更有效的提高传输效率。在使用视频会议 系统中能保障各个会场之间数据之间的快速转发，并且能应对网络上出现的各种 突发状况，m p l s 的运作原理是提供每个d 数据包一个标记，并由此决定数据包 的路径以及优先级。与m p l s 兼容的路由器( r o u t e r ) ，在将数据包转送到其路径 前，仅读取数据包标记，无须读取每个数据包的口地址以及标头( 因此网络速度 便会加快) ，然后将所传送的数据包置于f r a m er e l a y 或a t m 的虚拟电路上，并迅 速将数据包传送至终点的路由器，进而减少数据包的延迟，同时由f r a m er e l a y 及 a t m 交换器所提供的q o s ( q u a l i t yo f s e r v i c e ) 对所传送的数据包加以分级，因而 大幅提升网络服务品质提供更多样化的服务。 1 4s d h 网络性能优化问题 s d h 网络的性能优化问题包含两个方面：一个是网络拓扑的优化，也就是对 电子科技大学硕士学位论文 网络的节点、网络连接以及链路容量进行合理的配置，以达到在最少的网络投资 下，能够获得更好的网络连通性、更可靠的网络性能以及更优的网络服务质量； 另一个方面是，对网络中的业务进行优化，也就是在已知的网络拓扑( 包含已定 的节点和物理连接，以及链路容量、可用带宽等) 中，为业务请求寻找合理的传 输路径和所需的相应带宽，从而能够获得更高的网络资源利用率，同时业务也能 获得更优的服务质量。本文中的s d h 网络性能优化问题是指，在给定的网络拓扑、 给定的网络容量下，根据不同的目标，求解最优的资源配置，满足业务的各种要 求，最大程度上优化网络性能。 本文研究的不仅是全网的流量分配，还包含链路上的时隙分配。除此之外， 作者还研究了业务路径恢复的问题。这三个问题都属于业务的优化问题，通过有 效的算法，提高了网络的性能，使得业务得到的服务质量更高，同时也节约了网 络资源，减少了网络代价。 s d h 网络中的业务类型可分为级联业务和虚级联业务，每个业务的保护类型 又可以分为专用保护( 1 + 1 保护) 、共享保护( 1 ：n 保护) 和无保护。每个业务的 大小可以使不同的。每个业务需要考虑路径约束、分离约束和路由约束。其中业 务的多约束限制包括：1 ) 同一业务的工作路和保护路之间需要满足的约束( 比如 链路分离) ；2 ) 工作路或者保护路的单条路由需要满足的约束( 比如必经约束、 跳数约束等) ；3 ) 关联业务工作路与工作路之间需要满足的约束。 业务优化中的约束条件一般从以下几个方面考虑：网络的拓扑结构；节点对 之间的业务流量需求；网络的总容量限制。优化目标主要是才用适当的路由算法， 在满足业务带宽需求、可靠性和服务质量的前提下，尽可能的使用最少的网络资 源，使用最简单快捷的算法。 s d h 网络性能优化问题的几个难点： 1 级联业务和虚级联业务、网状网业务和环网业务的混合存在：级联业务需要 捆绑寻路，且在同一光纤上分配连续的时隙；虚级联业务允许将业务拆分，被拆 分的部分可以选择不同路由，并且虚级联业务不要求占用的时隙具有连续性。需 要根据这两种类型业务的特点，处理资源碎片。所以非级联业务的时隙分配很好 处理，但级联业务的时隙分配就需要仔细设计。网状网业务不要求路径上所有链 路所占时隙的一致性，但是环网业务要求路径上，在相邻且同环的链路上占用相 同编号的时隙。如何给已经选好路径的环网业务，分配合适的时隙，也需要详细 设计。 6 第一章绪论 2 专用保护、共享保护、无保护业务混合存在：如何充分利用共享保护资源， 达到最节约网络资源，同时又能提供更多的共享保护，是资源优化配置的一个技 术难点。网络中又同时存在三种类型的业务，以及这些业务本身还有级联和虚级 联的属性，使得优化资源配置，提高网络性能变得非常复杂。在路由选择上，要 考虑工作路和保护路的分离；在时隙分配上，不仅要考虑共享时隙的最优化利用， 还要顾及到级联业务的时隙连续性要求。 3 业务带宽的不一致：网络中的业务可能存在带宽不一致的情况，再加上各种 业务类型，对于共享保护资源分配来说更加困难，可能存在不同带宽的共享保护 业务，共享保护资源的情况。另外，业务带宽的不一致，会导致网络中存在更多 的资源碎片，如何减少资源碎片，优化资源分配变得更加复杂。 4 链路容量的不一致性以及多种光纤类型的混合存在：由于级联业务在一条链 路上占用时隙资源时，只能占用一根光纤上的连续时隙，所以链路的部分空闲容 量，对于级联业务来说，可能并不能使用。增加了级联业务在时隙分配时的复杂 度。 s d h 网络资源优化配置中，对共享资源的分配是值得关注的，目前共享资源 配置问题的解决方案主要有两种：一种是在工作路由已定的前提下，计算业务的 共享保护路，使得共享保护占用的网络资源最少；另一种是同时计算工作路由和 保护路由，使得两条路径所占用的网络资源最少。具体的解决方法有三种：1 ) 基 于整数线性规划( i l p ，i n t e g e rl i n e a rp r o g r a m m i n g ) 求解；2 ) 基于整数规划松弛 或分解；3 ) 启发式算法求解。第一种方法要求写出精确的数学模型，所以得出 的结果最优，但是实际网络中存在的约束条件较多，网络规模通常也较大，这些 都会导致i l p 模型异常复杂，求解速度非常慢，甚至很难求出解。第二种方法是 第一种方法的改进，将复杂的目标函数分解成若干子目标函数，然后通过不断的 迭代，得出最优解或者接近的最优解，这种方法虽然在一定程度上将问题划分求 解，但是面对随网络规模增长成指数增长的约束条件和变量，这种分解算法的求 解速度也并不理想。所以，快速简单的启发式算法成为解决s d h 网络资源优化配 置的理想解决方案。本文中，作者将路由问题和时隙分配问题分开解决，简化了 问题的复杂度。 除了s d h 网络的资源分配问题，在s d h 网络的实际应用中，也会遇到业务的 一些其他需求。本文中，作者解决的是业务的路径恢复问题。网络故障导致业务 的路由发生改变，当故障恢复后，业务需要不中断的回到其原始路径上。因为此 7 电子科技大学硕士学位论文 时网络中所需要路径恢复的业务可能有很多个，而且这些业务原始路径上的资源 可能已经被一些业务占用了，如何挪开这些业务，且不中断任何网络中已存在的 业务，是一个复杂的难题。尤其是，当网络中存在的业务包含了专用保护、共享 保护这些业务时，为业务重路由的时候，所要重新计算的可能是很多条路径( 比 如挪动共享保护路) 。 1 5 本文的主要贡献及内容安排 本文研究了s d h 网络的性能优化问题，提出了多个新算法。本文的主要创新 点如下： 1 s d h 网络资源优化配置的双重迭代启发式算法 该算法的目的在于，满足尽可能多的业务请求，并且占用更少的网络资源， 使得网络的性能最大化。文中提出了在s d h 网络中，对于给业务分配带宽资源的 问题中，关于业务的路由选择、业务的重路由的双重迭代启发式算法。该算法通 过设置链路权重门限值，来避免链路堵塞；然后从不同门限值的迭代中，选择最 合适的门限值。除此之外，通过局部业务的微调整，进一步优化链路带宽的分配。 本文中，作者建立了网络资源优化配置的i l p 模型，并且将该算法的仿真结 果与i l p 模型的求解结果进行了对比。对比结果中，文中所提出的算法在几十秒 之内，就可解决的大规模网络中的资源优化配置问题，得出最接近最优解的结果。 而i l p 模型求解的过程却需要几十个小时，甚至更长时间。 2 业务路径恢复的冲突集创建和中间态过渡 文中提出了冲突集的概念，为所有需要路径恢复的业务建立冲突集，冲突集 包含所有当前占用了该业务原始路径资源的业务。当需要恢复一个业务到原始路 径时，只要把其冲突集里的业务移走，空出该业务原始路径上的资源，就可以把 这个业务恢复到原始路径上。 在上述过程中，作者还提出了中间态路径。在路径恢复的倒换过程中，有些 业务可能无法从直接当前路径直接切换到其原始路径上，如果为这些业务在网络 中暂时算一条路径( 中间态路径) ，等调整了其他业务之后再来恢复，成功率将会 大大增加。 3 快速、高效、节约资源的时隙分配算法 时隙分配算法中，将连续的空闲时隙当作空白块。利用空白块为动态业务找 第一章绪论 到最匹配的时隙资源，不但利用了网络资源，还尽可能地避免了资源碎片的产生， 对于后继的业务也尽可能地留下更充分的时隙资源。 同时，对于比较特殊的共享保护业务，作者提出了共享集的概念。用共享集 来存放可以共享的业务。共享集将时隙资源划分成一个个具有共享属性的资源块， 使得共享资源分配更清晰，给一个业务分配共享保护资源时，查找更迅速，资源 利用率更高。 作者提出了可以针对几乎所有s d h 网络业务类型的时隙分配算法，包括专用 保护业务、共享保护业务、无保护业务，以及带约束业务和虚级联、级联业务。 快速有效的解决了时隙的优化分配问题。提出的空白块和共享集的概念，极大程 度上减少了资源碎片、链路阻塞、资源共享优化的问题，大大提高了网络性能。 4 可以应用于多种业务类型 文中作者提出的算法，可以针对多种业务类型，包括专用保护业务、共享保 护业务、无保护业务，以及带约束业务和虚级联、级联业务，还有环网和网状网 业务。 本文的内容安排如下：第二章s d h 网络中资源优化配置算法；第三章研究业 务的路径恢复算法；第四章研究s d h 网络时隙分配算法；最后是全文总结。 9 电子科技大学硕士学位论文 2 1 研究背景 第二章基于双重迭代的资源配置算法 随着可生存网络的重要性和因特网流量的急速增长，对于成本效益和可生存 性的传统服务要求已经变得更加复杂，尤其是对动态流量进行快速有效地资源分 配。同时，各种移动终端已具备连接因特网功能以进行信息散播与获取，例如手 机互动，车载实时信息系统1 3 等，这进一步增大了网络流量，同时使得网络热点区 域因终端移动性而连续变化。光网络的故障保护是一种通过预先建立备用路径的 方法来实现网络的可生存性，并且为工作路径和备用路径都分配网络资源。当前， 基于共享备用路径保护( s b p p ) 的可生存性服务受到极大的关注，并且获得了i e t f 的广泛支持【4 】。假如不同业务的工作路径是相互分离的，那么s b p p 允许保护路径 共享某些网络资源。因此，如何给工作路径和保护路径分配资源，是一个资源分 配( r a ) 问题。这个问题直接关系到网络的代价和性能。 共享风险链路组( s r l g ) 【5 】是一个链路的集合，这个集合中的链路共享同一 种资源风险。为了避免这种情况的发生，同一个业务的工作路径和备用路径不能 共享同一个s r l g 标记。为了确保业务在网络故障发生时的可生存性，非常有必 要考虑s r l g 分离的约束条件，这种约束比链路分离和节点分离的约束更加常规。 在文献【6 】中，提出了一种s b p p 配置方法和一个连续的可生存路由( s u c c e s s i v e s u r v i v a lr o u t i n g s s r ) 算法，这两种方法基于一个剩余储备矩阵( s p a r ep r o v i s i o n m a t r i x s p m ) ，通过不断迭代的路由更新备用路径来给备用路径分配最少的剩余网 络资源。但是，在s s r 算法中，所有业务的工作路径在算法运行之前己存在于网 络中，并且网络中所有物理链路的容量都没有上限。因此，s s r 算法不能保证所 有业务在网络中都能找到备用路径。并且，存在这样一种情况：当网络容量无法 承载所有业务请求以及所有业务的保护请求时，如果所有业务的工作路径已经占 用了全部的网络资源，那么s s r 算法将无法为任何一个业务算出任何一条备用路 径，这样，所有业务都将失败。此外，s s r 算法并没有考虑到工作路径所占资源 的资源优化问题。在文献【6 】中，作者考虑到了拓扑陷阱【_ 7 】【8 】问题，这个问题在与独 立失效的路径恢复机制中会出现，所以s s r 算法在路径恢复中选择备用路径是非 独立失效的。在本文研究中，作者通过计算关键路径，避免了独立失效路径恢复 1 0 第二章基于双重迭代的资源配置算法 机制中的拓扑陷阱。 文献【9 】中提出了另一种算法，该算法基于所有既定的工作路径。对于一条链路 来说，它在网络中作为n 条工作路径的备用链路。如果知道这n 条工作路种的m 条失效的概率( m _ 厶 | ”弋沙竺竺罗 早 毫 将l s p ( i ) 的冲突 对象中，所有 将恢复发起业务冲突 移走的全部恢 集中，所有被移走的 将l s p ( i ) 恢复回 复回移动前 冲突对象恢复回移动 其原始路径 前 l ll 发起业务恢复 镌，发起业务的所有需恢复 l s p ( i ) 恢复失败 失败lc 且丕，蕾埔址寸m c 目 ，-警们碰僦9 ) ： 继续恢复发起 业务的下一条 lsp r 发起业务恢复 完成 图3 5 模块1 0 3 恢复发起业务子模块 第三章路径恢复优化算法 步骤1 0 3 1 ：从发起业务的l s p 集合中取一个需要进行路径恢复、还没有进行 过恢复操作的l s a j ir u n ，继续步骤1 0 3 2 。若所有l s p 都执行过恢复操作，开始执 行模块1 0 4 。 步骤1 0 3 2 ：从l s p j in l n 的冲突对象集合中，取一个目前占用了l s p j i 耐资 源的冲突对象c il s p n m 。若所有冲突对象都已经移走，转到步骤1 0 3 4 ；否则， 考虑两种情况： ( a ) c il s p n m 在失败集合f 中，则c il s p n m 是无法恢复回其原始l s p 的， 因此，l s p j ir u n 路径恢复不成功，转到步骤1 0 3 5 , ( b ) c il s p n m 不再失败集合f 中，继续步骤1 0 3 3 。 步骤1 0 3 3 ：给c il s p n m 重新计算一条路。由于预处理模块已经追加过禁忌 信息，如果能为其重新算出一条暂时的可用路径，则该新路径一定不与l s p j im 的l s p j i _ o f i 冲突。其中，为c i _ l s p n m 重新计算路径分为两种情况考虑： 若业务d m 为共享保护业务，c il s p n m 为该业务的工作路径，则不但要为 c il s p n m 重新计算一条暂时的可用路径c il s p j it m p ，还需要对d m 的共享保 护l s p 计算一条暂时的可用路径。 若c il s p n m 不为共享业务的工作路径，则只需要为c il s p n m 重新计算一条 暂时的可用路径c il s p j it m p 。 如果重新计算路径成功，将c i l s p n m 从当前路径移至c i _ l s p j i _ t m p ( 若为 情况a ，还需移动相应的共享保护l s p ) ，转到步骤1 0 3 2 ；如果重新计算路径失败， 转到步骤1 0 3 5 。 步骤1 0 3 4 ：将l s p j i _ r u n 移至其原始路径l s p j i _ o n 上，转到步骤1 0 3 1 。 步骤1 0 3 5 ：恢复l s p j i失败，此时考虑两种情况：run 如果l s p ir u n 为共享业务的工作l s p ，则业务d i 路径恢复失败，将业务d i 的工作l s p 和保护l s p 都放入失败集合f 中，将冲突集c i 中已经移走的冲突对象 全部恢复到移动之前的路径上。将其冲突集c i 从冲突关系表c 中删除，开始执行 模块1 0 2 。 如果l s p j ir u n 不为共享业务的工作l s p ，则将l s p j ir u l l 放入失败集合f 中； 将l s p j i 蕊的冲突对象中，已经移走的冲突对象全部恢复到移动之前的路径上。 步骤10 3 6 ：判断是否对业务d i 继续进行路径恢复操作，考虑以下两种情况： 若业务d i 中所有需要恢复的l s p 全部恢复失败，则业务d i 进行路径恢复失 电子科技大学硕士学位论文 败，将其冲突集c i 从冲突关系表c 中删除，开始执行模块1 0 2 。 若业务d i 中还有没有进行过恢复操作、需要恢复的l s p ，转到步骤1 0 3 1 。 将发起业务恢复至其对应的原始路径后，导致其他业务产生了暂态的l s p ， 还需要把这些暂态l s p 恢复到其各自的原始l s p 上，此时执行模块1 0 4 ( 暂态路 径恢复模块) 来完成。如图3 - 6 流程所示，模块1 0 4 由以下两个步骤实现： 否 统计全网所有具有暂 态l s p 的业务 络中是否有具有 态l s p 的业务 是 取一个具有暂态l s p 的业务作为路径恢复 发起业务 1r 调用模块1 0 3 ，对该发 起业务进行路径恢复 图3 - 6 块1 0 4 暂态路径恢复模块 步骤1 0 4 1 ：统计全网所有具有暂态l s p 的业务。统计分两种情况考虑： ( a ) 如果全网没有这样的业务，则本次路径恢复成功，转向执行模块1 0 2 ， 3 2 第三章路径恢复优化算法 进行下一次路径恢复； ( b ) 如果全网中还有这样的业务，取一个业务，继续步骤1 0 4 2 。 步骤1 0 4 2 ：调用模块1 0 3 的算法，将该业务作为模块1 0 3 中的发起业务，将 其路径恢复回相应的原始路径。根据执行模块1 0 3 的结果，分两种情况考虑： 若该业务恢复成功，转向步骤1 0 4 1 ： 若该业务恢复失败，本次路径恢复失败。把本次路径恢复过程中，所有移动 过的l s p 全部恢复到移动前，即将全网的业务状态恢复至本次路径恢复中，执行 模块1 0 2 时的状态。将本次路径恢复的发起业务d i 下需要恢复的l s p 放入到恢复 失败集合f 中，删除该发起业务d i 在冲突关系表c 中的冲突集c i 。转向执行模块 1 0 2 ，进行下一次路径恢复。 按照图木所示，每个需恢复业务都执行过路径恢复后，流程结束。 3 4 仿真和分析 为了证明本算法的功能与性能，作者在几种特殊的小网络中对该算法进行了 功能验证。另外，在2 0 节点和5 5 节点的网络中，将该算法与无中间态无排序、 无中间