（计算机应用技术专业论文）ason中基于单亲遗传算法的动态多业务恢复研究.pdf

江苏大学硕士学位论文 摘要 a s o n a u t o m a t i c a l i ys w i t c h e do p t i c a ln e t w o r k 自动交换光网络 赋予了传统 光网络前所未有的灵活性和可扩展性 代表了下一代光网络的发展方向 对多种 恢复机制的支持是a s o n 的一个重要特点 也是目f i fa s o n 研究的一个重点 在 网络容量同益增长的今天 智能化动态恢复算法的研究对提高a s o n 的生存性具 有重要意义 一个良好的恢复算法能够合理高效地提高网络空闲资源的利用率和 受损业务的恢复率 从而有效减少因网络故障而造成的社会影响和经济损失 a s o n 的多业务承载能力要求网络具有快速 多样化的故障恢复能力 但是 h fa s o n 中一系列新技术如波长转换 分布式呼叫与连接管理 光交换技术等 的应用 使得a s o n 的计算环境远比传统的光传送网要复杂 这就使得基于传统 光传送网设计的一系列恢复机制不能满足a s o n 对生存性的要求 主要体现为不 能全面考虑网络空闲资源的合理分配 不能满足业务恢复的多样化 算法可扩展 性不够等一系列问题 单亲遗传算法 p g a p a r t h e n o g e n e t i ca l g o r i t h m l 是一种改进后的遗传算 法 g a g e n e t i ca l g o r i t h m z l 它通过改进传统遗传算法的遗传算子来简化遗传操 作过程 提高搜索效率 具有使用简单 鲁棒性强 易于并行化等特点 特别适 川于解决基于序号编码的组合优化问题 而光网络的恢复问题本质上也是组合优 化问题 因此作为尝试性的研究 本文基于单亲遗传算法基本原理设计了一种适 合于a s o n 的动态多业务恢复算法 目标是更合理地利用网络空闲资源 以满足 故障发生后对多受损业务的同时快速恢复 从而有效提高恢复率 降低业务中断 率 论文研究分析了a s o n 中动态恢复问题的相关技术体系 包括a s o n 的路由 体系 动态路由和波长分配技术以及单亲遗传算法的基本思想 提出并构建了基 于单亲遗传算法的动态多业务恢复算法模型 并设计了基于上述相关技术的仿真 平台 基于仿真平台对算法进行了仿真测试和改进 主要成果如下 1 分析和归纳了a s 0 n 网络的路出体系和相关动态路由和波长分配技术 包括路由模式 分布式波长分配 路由分发拓扑 不同实现方式 集中式或分布 式 等与恢复问题有关的功能模块 以及a s o n 中实现动态恢复的相关影响因素 及关键技术 2 研究了单亲遗传算法的基本思想 创新性地将单亲遗传算法应用到a s o n 动念多业务恢复问题中 该算法在运行中能综合考虑网络资源状态和不同受损业 i 江苏大学硕士学位论文 务恢复的优先等级 较之传统基于最短路径的动态恢复策略 该算法能取得更好 的恢复率和网络资源利用率 3 分析了单亲遗传算法在运行中由于系统随机性引起的不稳定因素对算法 e v i d e n t l y c o n s i d e r i n gt h em u l t i s e r v i c e sc a r r y i n gc a p a c i t yi na s o n t h e r ei sah i g hd e m a n d f o rt h ef a s ta n dm u l t i s e r v i c e sr e s t o r a t i o na b i l i t yo fn e t w o r k b u t b e c a u s eo ft h e a p p l i c a t i o no fs e r i e sn e wt e c h n o l o g i e s s u c ha sw a v e l e n g t hc o n v e r s i o n d i s t r i b u t e dc a l l a n dc o n n e c t i o nm a n a g e m e n t o p t i c a le x c h a n g ee t c t h ec a l c u l a t i o ne n v i r o n m e n to f a s o ni sf o r t h e rc o m p l i c a t e dt h a nt r a d i t i o n a lo p t i c a lt r a n s p o r tn e t w o r k s oas e r i e so f r e s t o r a t i o ns t r a t e g y w h i c ha l ed e s i g n e df o rt r a d i t i o n a lo p t i c a lt r a n s p o r tn e t w o r k c a n n o t s a t i s f yt h es u r v i v a b i l i t yr e q u e s to fa s o n i th a se x p o s e da s e r i e so fq u e s t i o n s u c ha s c o n s i d e r i n g r e a s o n a b l e s p a r e r e s o u r c e a s s i g m n e n tp a r t l y m e e t i n g m u l t i f o r m r e s t o r a t i o nd e m a n di n s u f f i c i e n t l y d e f i c i e n te x p a n s i b i l i t yo f a l g o r i t h m s e t c a sa ni m p r o v e dg a g e n e t i ca l g o r i t h m p g a p a r t h e n og e n e t i ca l g o r i t h m s i m p l i f yt h eg e n e t i co p e r a t i o na n di n c r e a s et h es e a r c he f f i c i e n c yf r o mi m p r o v i n g g e n e t i co p e r a t o r so ft r a d i t i o n a lg e n e t i ca l g o r i t h m w i t hc h a r a c t e r ss u c ha ss i m p l e n e s s s t r o n gr o b u s t n e s sa n dp a r a l l e l i s me t c p g ai se s p e c i a l l ys u i t a b l e f o rs o l v i n gt h e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sb a s e do no r d i n a ls t r i n g s c o n s i d e r i n gr e s t o r a t i o n p r o b l e mi si ne s s e n c eac o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m o nt h eb a s i so f p r i n c i p l eo f p g a t h i st h e s i sd e s i g n san e wd y n a m i cr e s t o r a t i o na l g o r i t h ma d a p tt om u l t i s e r v i c e s w h i c hi ss u i t a b l ef o rt h ee n v i r o n m e n to f a s o nn e t w o r k s 1 r t l ef o c u so f t h ea l g o r i t h mi s t oa s s i g nt h es p a r er e s o u r c ei nn e t w o r k sm o r er a t i o n a l l yw i t ht h eo b j e c t i v eo fs a t i s f y i n g t h ed e m a n dt h a td i f f e r e n tb u s i n e s s e si n j u r e dc a nb er e s t o r e df a s t l ya n dp a r a l l e l l y t h u s t h ef a i l u r er e s t o r a b i l i t yc a nb ei n c r e a s e de f f i c i e n t l ya n dt h es e r v i c ed i s r u p t i o nr a t i oc a n b ed e c r e a s e de v i d e n t l y t h et h e s i ss t u d i e sa n da n a l y s e st h er e l e v a n tt e c h n o l o g yo fd y n a m i cr e s t o r a t i o n m o d u l ei na s o n i n c l u d i n gt h er o u t i n ga r c h i t e c t u r eo f a s o n t h ed y n a m i cr o u t i n ga n d w a v e l e n g t ha s s i g n m e n tt e c h n o l o g yi na s o na n dt h ep r i n c i p l eo fp g a a n dam o d e i i l l 江苏大学硕士学位论文 a b o u td y n a m i cr e s t o r a t i o na l g o r i t h ma d a p tt om u l t i s e r v i c e si na s o ni sp r e s m z da n d 蛐m c t u r e db a s e do i lp g a w i t ha b o v e m e n t i o n e dr e l e v a n tt e c h n o l o g y as i m u l a t i o n p l a t f o r mi sd e s i g n e dt ot e s ta n di m p r o v et h ea l g o r i t h r m1 n l em a i na c h i e v e m e m s 批雒 f o l l o w s 1 t h er o u t i n gt e c h n o l o g ya n da r c h i t e c t u r eo fa s o nn e t w o r ka r ca n a l y z e da n d s u m m e du p w h i c hi n c l u d er o u t es c h e m e d i s t r i b u t e dw a v e l e n g t ha s s i g n m e n t s i g n a l i n g r o u t i n gp r o t o c o la n dr o u t i n gd i s t r i b u t i n gt o p o l o g y e t c t h ei n f l u e n c ef a c t o ra n dk e y t e c h n o l o g yr e l e v a n tt or e a l i z ed y n a m i cr e s t o r a t i o na l g o d t h mi na s o n a r ea l s oa n a l y z e d i nd e t a i l s 2 b ys t u d y i n gt h ep r i n c i p l eo fp g a ad y n a m i cr e s t o r a t i o na l g o r i t h ma d a p tt o m u l t i s e r v i c e sb a s e do np g ai sf i r s t l yp r e s e n t e d i nt h ea l g o r i t h m d i f f e r e n tb u 萄n e s s e s i n j u r e d c a nb e p r o c e s s e dp a r e l l e l l y a n dp r o c e s s i n go fm 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 ts u b p r o b l e mc a l lb ep a r a l l e l e da saw h o l e i ti sa b l et oc o n s i d e rn e t w o r k r e s o u r c ea n dp r i o r i t yo fd i f f e r e n tb u s i n e s s e si n j u r e ds y n t h e t i c a l l y c o m p a r e d i m t r a d i t i o n a ld y n a m i cr e s t o r a t i o na l g o r i t h mb a s e do i lo s p f o p e ns h o r t e s tr o u t ef i r s t t h ea l g o r i t h mc a na c h i e v eb e t t e rf a i l u r er e s t o m b i l i t ya n dr e s o u r c eu t i l i z a t i o n c 3 t h ed e s t a b i l i z i n g f a c t o r sw h i c hi n f l u e n c et h ee x e c u t i o ne f f i c i e n c yi np g a p r o c e s s i n ga r ea n a l y z e da n ds u m m e du p a c c o r d i n g t ot h ef a c t o r s t h eg e n e t i co l 圮q r a t o r s o fa l g o r i t h ma r ei m p r o v e dt oa d v a n c es e a r c h i n ge f f i c i e n c ya n dc o n v e r g e n c et i m e n 坨 i m p r o v e da l g o r i t h mi st e s t e do ns i m u l a t i o np l a t f o r m s i m u l a t i o nc o m p u t i n gs h o w e d t h a t t h ei m p r o v i n gm e a s u r ec a ni m p r o v et h ep 廿f o r m a n c eo f a l g o r i t h mt oc e r t a i ne x t e n l 4 p r o g r a m m i n gi sd o n et or e a l i z ep g a b a s e dd y n a m i cr e s t o r a t i o n 姆d t h m a d a p tt om u l t i s e r v i c e si na s o n t h e c a l c u l a t i o ne n v i r o n m e n to f n e t w o r ki ss i m u l a t e d b a s e do nt h es i m u l a t i o ns y s t e m p g ai sc o m p a r e dw i t l lo t h e ra l g o d t h m sm e m i o a e di n r e f e r e n c e st ov e r i f yt h ep e r f o r m a n c eo f d i f f e r e n ta l g o r i t h m s 5 1 1 忙p e r f o r m a n c eo fr e s t o r a t i o na l r o t i t h mb a s e d 蚰p g ai s s i m u l a t e d a c c o r d i n gt ot h er e s u l t s p a r a m e t e r so fg e n e t i co p e r a t o r sa l e 越l 卸i t e d w h i c hm a k e t h e a l g o r i t h mg e tb e t t e rr e s u l ta tt h ee q u a i r e s o u r c ee x p e n s e s k e yw o r d s a s o n d y n a m i cr e s t o r a t i o n m u l t i s c r v i c e s p a r t h e n og e n e t i c a l g o r i t h m r e s o u r c ed i s t r i b u t i n g r e s t o r a b i l i t y 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 保密口 在年解密后适用本授权书 不保密瓯 学位论文作者签名 驶至巾 2 0 0 歹年1 2 月 日 指导教师签名 学岬 獬年p 月膨1 3 独创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独 立进行研究工作所取得的成果 除文中已注明引用的内容以外 本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果 对本文 的研究做出重要贡献的个人和集体 均己在文中以明确方式标明 本 人完全意识到本声明的法律结果由本人承担 学位论文作者签名 段互书 日期 2 年j 2 f j 日 江苏大学硕士学位论文 第一章绪论 本章按以下节结构展开 1 1 研究背景 i 2 论文研究意义 1 3 论文的研究 内容和关键技术 1 4 论文的组织安排 1 1 研究背景 随着信息化进程的加快 以i p 为主的i n t e m e t 数据业务的呈爆炸式增长 用 户对带宽需求和服务质量的要求日益提高 传统的静态光网络传输网已难以满足 要求 在这种需求下 传统光网络向下一代能支持多信道 高容量 可配置 智 能型的网络演进 在这种演进过程中 点到点的w d m 3 j 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 波分复用 系统在2 0 世纪9 0 年代中期以后得到了广泛的应用 其基 本原理是在发送端将不同波长的光信号通过复用器组合起来 复用 并耦合到单 模光纤中进行传输 在接收端再通过解复用器将组合波长的光信号分开 解复用 恢复出原始光信号后送入不同的终端 系统构成如图1 1 所示 雷胴础 区蓝巧 i i t m i i 图i iw d m 系统构成 在具备了w d m 能力之后 光传送网络第一次拥有了在光层直接交叉组网的 能力 而随着光网络技术的迅速发展 传统的w d m 光通信网也随之向以a s o n a u t o m a t i c a l l ys w i t c h e do p t i c a ln e t w o r k 自动交换光网络 为代表的新一代智能 化光网络的方向发展 a s o n 在i t u t 的文献中定义为 通过能提供自动发现和 动态连接建立功能的分布式 或部分分布式 控制平面 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 光传送网 或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 同步数字序列 网 络之上 可实现动态的 基于信令的策略驱动控制的一种网络 与传统的光传送 网相比 a s o n 突破性地引入了更加智能化的控制平面 将i p 的效率 s d h 的保 护能力以及w d m 的容量通过分布式网络管理系统有机地结合在一起 从而赋予 了传统光网络更多的智能控制 a s o n 不仅提高了网络资源的利用率 同时也提 供了更加完善的保护和恢复功能 并增强了网络的互操作性和可扩展性等 其体 系结构主要表现在具有a s o n 特色的3 个平面 3 个接口以及所支持的3 种连接 类型上 体系结构如图l 2 所示 麓蕊 江苏大学硕士学位论文 器 0 m k th q t l m u 一 t 图i 2a s o n 体系结构 目前a s o n 正处于快速发展期 国际标准化组织i t u t i e t f o i f o d s i 相继将智能光网络相关研究内容纳入了议事日程 国外主要的研究项目有欧盟资 助的i s t 的l i o n 4 1 欧洲电信研究与开发组织e u r e s c o m 的f a s h i o n 以及 商业公司的努力 主要有s y c a m o r e l 6 公司的s n 8 0 0 0 s n l 0 0 0 0 s n l 6 0 0 0 s i l v x o n m s c i e n a 公司的智能光网络架构l i g h t w o r k s 7 l n o r t e l 公司的o p t e m 8 1 l u c e n t 公司用于全光智能网的o p t i c a ln e t w o r kn a v i g a t o r 和先进传输平台l a m b d au n i t e m s s 网络管理系统n a v i so m s t g l n e c 公司的三位一体综合管理系统n m s 1 0 l a 1 c a t e l 的a b s i 1 c i s c o 公司的完整光多业务边缘和传输c o m e t t l 2 1 在国内主要 有2 0 0 3 年启动的中国8 6 3 计划重大专项3 t n e t i b l 核心技术有太比特级智能光网 络系统 太比特级多颗粒度路由交换系统和太比特级网络应用支撑环境 a s o n 的发展代表了智能光网络的主流方向 光网络的恢复 4 1 r e s m r 砒i o n 是指在工作业务发生故障的情况下 不是专门 预先为其留有保护通路 而是按照一定的优化算法 依据网络当时的空闲资源为 其选择一条合适的替代路由 a s o n 的恢复算法是实现a s o n 生存性 s u r v i v a b i l i t y 的关键技术之一 随着光传输技术的飞速发展 o t n 承载的业务 需求正呈爆炸式增长 网络故障带来的影响越来越严重 此外 光网络由点到点 环网逐步向a s o n 格状网演变 这也增加了网络故障情况的复杂性 因此 能综 合各种优化目标 如 恢复时间 可恢复性 资源利用率等 的动态多业务恢复 算法就显得尤为重要 在光网络的恢复算法中 路由恢复和资源调度不仅仅要了解线路或者通道的 好坏 而且需要了解各链路和通道的资源使用情况 基于这些备用信息 才能依 据一定的优化算法进行资源的合理调配 所依据的优化算法通常为r w a l 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 问题是 n p c 问题 文献 睁1 9 中大多将r w a 问题拆分成路由和波长分配两个子问题分别 江苏大学硕士学位论文 加以解决 这类算法大多建立于传统电路交换网络无向多图 u n d i r e c t e dm u l t i g r a p h 模型1 2 0 l 上 恢复路由策略常用最短路径算法 波长分配策略则有f i r s t f i t 最先适 用 l 1 l e a s t i n f l u e n c e 最小影响 l l r 1 e a s t 1 0 a d e dr o u t i n g 最小负载路由 等 路由选择和波长分配同时进行的算法则建立在一种新的模型一分层图模型2 目前在该模型中找最佳路由只是通过简单地对请求的光路采用最短路径算法 i 得 到解决 尽管这些传统算法已经得到了广泛的应用 但随着网络环境的日益复杂 它们已逐渐无法满足a s o n 的灵活 快速 多样化的恢复要求 例如 由于传统 算法每次执行只能处理一条路由 这可能造成多个受损业务的恢复路由发生拥塞 进而导致恢复时延的增加 针对上述问题 本文提出了一种基于单亲遗传算法的 a s o n 多业务恢复算法 遗传算法 o a g e n e t i ca l g o r i t h m 2 3 2 珂是目前三种典型的拟生态算法f 2 6 1 之一 其他两种是蚁群算法 2 7 i 和免疫算法 2 s 1 由美国j h o l l a n d 教授于1 9 7 5 年提出 2 9 l 是一种模拟达尔文的自然选择学说和自然界的生物进化过程的计算模型 它采用 简单的编码技术束表示各种复杂的结构 并通过对一组编码表示进行简单的遗传 操作和优胜劣汰的自然选择来指导学习和确定搜索的方向 与传统的搜索和优化 算法相比 遗传算法主要具有以下特点 1 自组织 自适应和自学习性应用遗传算法求解问题时 算法可利用进 化过程中获得的信息基于 优胜劣汰 的策略自行组织搜索 从而产生更适应环 境的后代 这种特性使遗传算法具有能根掘环境变化来自动发现环境的特性和规 律的能力 一 2 并行性遗传算法的操作对象是一组可行解 而非单个可行解 且可同 时搜索解空 日j 的多个区域 因而具有良好的并行性 3 通用性遗传算法不需要求导或其它辅助知识 而只需要影响搜索方向 的目标函数和相应的适应度函数 因此就有很强的通用性 4 全局优化性遗传算法从一组初始解开始搜索 得到的是一组优化解 给设计者更大的选择余地 它能在解空问内充分搜索 因此具有良好的全局优化 能力 5 简单性遗传算法中 目标函数解释为可行解的适应值 可以更加直接 地应用 由以上特点可以看出 遗传算法是一种通用而有效的求解最优化问题的方法 针对光网络恢复问题 相对于蚁群算法 免疫算法来说 遗传算法更易于满足恢 复问题对实时性 灵活性和多样化的要求 江苏大学硕士学位论文 然而 仅用传统的遗传算法在许多情况下容易产生早熟现象以及局部寻优能 力较差等问题 2 3 因此提出了各种变形的遗传算法 如 采用混合遗传算法p o 采用并行遗传算法 3 i i 采用非标准的遗传操作算予圈 采用动态自适应技术鲫等 改进方法 单亲遗传算法1 3 4 3 5 j p g a p a r t h e n o g e n e t i ca l g o r i t h m 是一种基于序号编码的 遗传算法 于2 0 世纪9 0 年代末由我国学者李茂军和童调生等人首先提出的 主 要用于组合最优化问题的求解 它通过改进传统遗传算法的遗传算子 来简化遗 传操作过程 提高搜索效率 单亲遗传算法不仅具有传统遗传算法的操作过程简单 鲁棒性强 并行性 全局优化和自适应性等优点 而且解决了传统遗传算法在解决组合优化问题中常 见的序号编码中交叉操作较难实现等问题 单亲遗传算法近年来已成功地应用于许多组合优化问题的解决 如 q o s 路 由优化策吲3 酣 f l o w s h o p 3 r l t s p 3 8 等 在光网络的动态恢复问题中 所采用的 优化算法 r w a 算法本质上也是组合优化问题 因此相对于传统遗传算法 单 亲遗传算法更适合应用于动态多业务恢复问题的解决之中 1 2 论文研究意义 较之传统光网络 a s o n 的最大特点在于控制平面的引入 具有智能控制功 能的g m p l s l 3 9 1 g e n e r a l i z e d m u l t i p r o t o c o l l a b e ls w i t c h i n g 通用多协议标签交换 协议族的使用 使得a s o n 的恢复具有智能化的特点 在2 0 0 3 年初的会议中 m 1 已经将恢复的相关问题添加到g 8 0 8 0 自动交换光网络体系结构 之中 珥t f 关于 g m p l s 中有关恢复的讨论一直在进行并不断更新相关草案 一些研制a s o n 设备 的厂商也将恢复作为宣传的重点 可见 如何设计可靠的恢复算法是目前a s o n 的研究重点之一 目前 对a s o n 恢复问题的研究还处于一种相对起步的状态 其中欧盟资助 的i s t 的l i o n 研究计划在a s o n 的恢复研究方面处于业界领先地位 全球数据 业务的爆炸式增长要求光传送网提供更加灵活的网络指配和高效快速的网络恢复 能力 由于光网络中建立的宽带连接通常用于承载重要的用户数据 因此网络的 可靠性对于运营商和客户都很重要 一根光纤的断裂或一个节点的失效将造成经 过它的所有光路失效 引起大量连接业务的中断 对网络产生严重的影响 因此 a s o n 在能够极大地提高网络传输容量的同时也使其恢复问题日益突出 所以在 通信日益发展的今天 对a s o n 的恢复算法进行深入研究 为其设计灵活 高效 4 江苏大学硕士学位论文 可靠的恢复算法不仅具有重要的实用价值 而且具有深远的理论意义 1 3 论文的研究内容和关键技术 本文在广泛研究了国内外相关的演化计算和a s o n 恢复问题的基础上 针对 a s o n 传送平面的故障 设计了基于通道恢复的恢复算法 算法综合考虑了故障 情况下多受损业务恢复的时效性和网络空闲资源的合理利用 以提高a s o n 格状 网的生存性 论文的主要研究内容包括以下几个方面 i 研究分析a s o n 恢复方案中的影响因素 相对传统光网络 a s o n 的最大特点就是从传统的传输节点设备和管理系统 中抽象分离出了控制平面 实现了网络的分布式智能 论文在剖析a s o n 路由架 构 恢复机制以及r w a 算法的基础上 研究分析了a s o n 中恢复问题的新特点 总体上把握了恢复问题应该考虑的优化目标及影响因素 为后文设计a s o n 中基 于单亲遗传算法的动态多业务恢复算法提供参考 2 研究和设计a s o n 中基于单亲遗传算法的恢复算法 在广泛研究国内外遗传算法的基础上 首次将单亲遗传算法引入到光网络恢 复问题中 研究利用单亲遗传算法的序号编码和易于并行化的特点 对a s o n 动态 多业务恢复算法建立数学模型 设计了算法步骤和分析了算法的收敛性能 并将 a s o n 网络构造成分层图模型 以实现路由选择和波长分配的统一考虑 从而全局 优化选择网络链路与波长资源 提高对网络资源的利用 3 构建算法仿真平台及对算法性能进行测试 编程模拟网络环境 设计恢复算法仿真平台 同时对本文设计的算法以及其 他的一些算法进行性能测试 分析比较测试结果并调整本文算法参数 运用各种 参数组合进行仿真实验 以优化算法性能 资源利用率 可恢复率 业务中断率 等 找出算法性能最佳时的参数组合 4 分析和改进算法 在仿真实验的基础上 分析影响算法性能的因素及算法存在的问题 根据仿 真结果改进基本算法 并仿真测试了改进效果 本文所设计的基于单亲遗传算法的动态多业务恢复算法经系统仿真证明 能 有效降低故障引起的业务中断时间 提高对受损业务的恢复率 同时能够优化网 络资源分配 维持高效的带宽利用率和适应业务流的变化 算法对提高a s o n 的 实用性有重要的影响 同时 将单亲遗传算法的应用范围扩大到a s o n 恢复问题 的计算对遗传算法的发展也具有重要意义 江苏大学硕士学位论文 1 4 全文的组织安排 本文第一章为绪论 说明了本文的研究背景 意义 内容和本文架构 第二章首先剖析了a s o n 的路由体系结构 着重阐述了a s o n 的路由功能结 构 路由方式和路由消息分发拓扑等 然后在此基础上进一步对a s o n 中的恢复 问题及其新特点进行了分析 最后在以上分析的基础上 研究了a s o n 中的优化 恢复算法 以及波长转换约束 波长连续性约束等一般光网络中影响恢复算法设 计的因素 并对a s o n 恢复算法中需要额外考虑的动态计算 资源分配等问题进 行了阐述 第三章研究了单亲遗传算法的基本思想 定义了光网络的两种矩阵模型 并 扩展了原始的分层图模型使之支持波长转换 在分层图模型和光网络矩阵模型的 基础上 基于单亲遗传算法构建了动态多业务恢复算法模型 模型中主要考虑了 恢复通道的各性能优化目标 以便基于受损业务的优先级进行适当的选路从而完 成更有效的恢复 针对遗传操作中可能出现的问题 设计了简单直观的染色体编 码方式 描述了算法具体流程 并对算法的性能进行了分析 第四章阐述了恢复算法仿真平台的构建过程 并提供了主要模块的伪代码以 供参考 第五章在仿真平台上对本文算法及文献中提出的算法进行了测试 提供了测 试得出的各种结果 包括受损业务恢复率对比 资源利用率对比 对算法影响因 素的各种分析结果等 6 江苏大学硕士学位论文 第二章a s o n 中的恢复问题及相关技术分析 国 同磊硐 i 菇i i l i t l 蹁 h 鼻 翟 i 一 鲨 卜 图2 1 路由功能组件关系图 a s o n 路由功能体系结构中各个功能组件的作用如下 7 江苏大学硕士学位论文 1 路由控制器 r c r c 的功能主要包括与对端r c 交换交换路由信息 并通过对路由信息数据包 的操作回复路由查询 路径选择 对从连接控制器发出的为建立连接所需的通道 信息做出回应 为达到网络管理目的 对拓扑信息请求做出相应回应 r c 与具体 的协议无关 2 路由信息数据库 i t d b r d b 负责存储本地拓扑 网络拓扑 可达性 路由策略配置和其他通过路由 信息交换获得的信息 还可以包括配置的信息 r d b 可以包含多个路由域的路由 信息 r c 可以接入r d b 的一个视图 并获得相应的信息 图2 1 的虚线框表示 了这种关系 由于r d b 可以包含多个路由域的路由信息 因此接入r d b 的r c 可共享路由信息 如图2 2 所示 r d b 与具体协议无关 图2 2r d b 与多路由域中r c 的关东 3 链路资源管理器 u t m l r m 负责对子网端点池 s n p p 链路进行管理 包括对子网点 s n p 链路 进行分配和拆除 并将其控制的链路资源的任何状态的改变情况告诉r c 4 协议控制器 p c p c 将路由原语转换成特定路由协议的协议消息 因此p c 是与协议相关的 p c 还处理和路由协议相关的控制信息 这些控制信息用于路由信息交换的管理和 维护 为达到控制一个连接建立的目的 a s o n 控制平面需要在多个组件之问进行 信息交互 与连接过程相关的组件主要包括连接控制器 c c 以及上面提到的r c 和l r m 2 1 2 路由方式 针对多域网络环境中动态光通道的建立 a s o n 智能光网络中提出了三种路 由模式 层次路由 h i e r a r c h i c a lr o u t i n g 源路由 s o u r c er o u t i n g 和逐跳路由 s t c p b y s t 印r o u t i n g 下面主要介绍层次路由及其实现 8 江苏大学硕士学位论文 在a s o n 中 从水平方向来说 一般可划分成不同的路由域 每个路由域又 可分为不同的子网 而子网之问可以互相嵌套 一个大的予网 上层子网 内部 可包含若干个小的子网 下层子网 形成层次结构 每个子网都知道本身的拓扑 结构并能进行动态连接控制 但不了解层次结构中的上层或者下层子网的拓扑结 构 在层次路由中 子网层次的每一级都有一个包含r c c c 和l r m 的主节点负 责本级子网的选路 每级主节点之间按照层次结构的关系互相作用来选择路由 如图2 3 所示 连接请求首先到达最上层予网主节点a 由它计算出在源和目的节 点之问的路径需要经过的下一层子网 包括b f 和c 控制的子网 和它们之间的 链路连接 然后就通知相关的下层子网主节点b f 和c 分别建立在自己子网内部 对应的连接 这样由上到下逐级子网进行分段的选路 最终将得到整个连接的路 由 由图中可以看出 路由建立过程中 子网也被看作是一个节点 因此 分级 路由在本质上就是寻找两点间的连接通路 一墓 蕾辜一 t 鲁 直 一 r l t mo 图2 3 层次路由模式中的连接建立信令流程 由以上层次路由模式的特点可知 a s o n 中基于层次路由模式选路时 每级 主节点之间按照层次结构的关系互相作用来选择路由 由上到下逐级子网进行分 段的选路 最终得到整个连接的路由 其过程具有分布性的特点 每次得到的路 由不是一条从起始节点到目的节点的完整的路由 而是针对不同的路由域分别计 算得到的路由 这使得一方面 基于路由域的路由选择具有灵活性高 网络负荷 小 计算效率高的优点 另一方面 虽然各路由域内得到最优结果 但对于整条 路由而言 并不是从全网出发的最优结果 对于这一缺点 在实际应用时可以先 保证经过尽量少的路由域 然后再在各路由域内选择最佳路由的方式来完成路由 选择 这样一方面可以得到近似全网最优的结果 同时由于经过的路由域减少 需要交互的信令信息也会相应减少 由以上分析可知 层次路由模式具有以下优点 1 使得运营商能够屏蔽内部 的网络细节 并且可以任意配置内部网络结构提高网络的安全性 2 便于划分网 络管理权限和职责 3 在大规模网络中 可有效减少网络路由负荷 4 使整个网 9 江 苏大学硕士学位论文 络具有高度的灵活性和可扩展性 2 1 3 路由属性和路由消息分发拓扑 由路由协议传送的路由属性可分为节点属性和链路属性 另一个重要的路由 属性包括资源的属性 它用于表示由于连接的建立和删除而带来的资源变化的信 息 当网络中的连接建立和拆除频繁发生时 这些属性需特别对待 1 节点属性 节点的主要路由属性是可达性和多样性 节点完全控制着它所享有的信息 1 可达性属性 可达性属性提供了通过特定节点可到达的节点集合 它通过显示的或者摘要 的地址列表的形式给出 可达地址前缀用于指示路径信息 地址必须和s n ip 子 网关联 2 多样性属性 代表节点用于限制路径选择的所有权 一个例子是共享风险组 s r g 该属 性可用节点共享风险的标识列表给出 用于确定哪些节点有共同风险 3 其他属性信息 对节点有用的其他属性可能包括附加能力信息和存在于一个子r a 内的拓扑 信息的子集 前者与特定的传送业务能力相关 而后者可用于多样化业务的提供 多样的起始业务和终止业务 并可用于流量工程和全网资源优化中 2 链路属性 而链路属性的最小集合是链路状态和相关多样性 其中 链路状态信息由存 在 链路权重 容量表示 而链路相关多样性属性与节点相关多样性属性相似 1 存在 是最基本的链路属性 在r d b 里指示两个节点间是否存在链路 据此可以得 到网络基本的拓扑信息 2 链路权重 链路权重是由策略或限制等多个因素确定产生的 个属性 其值可用于路径 选择时链路之间的比较 一般来说 优先选取较低的链路权重所指示的路径 3 容量 对给定的层网络来说 本信息主要与链路连接数量有关 散布的容量信息的 数量与操作者的策略有关 根据路由功能 a s o n 路由消息主要可分为路由功能消息和携带网络路由的 消息 路由信息是网络相关信息 节点和链路属性 抽象代表 在两个邻接路由 江苏大擘硕士学位论文 控制器 r c 之间交换 这些消息被选路算法用于计算通过网络的连接请求的路 由 路由信息交互的范围限制在r a 内 是通过本地逐跳交换或者网络洪泛机制实 现传播的 当路由域中的路由执行器作为一组分布式的r c 被实现时 关于网络拓扑和可 达端点的路由信息必须被传播和用于与其它r c 协商 在对等r c 之间传送路由信 息的方法与路由源位置和路由信息用户无关 因此 路由信息传送机制可以采用 不同的网络拓扑 以下我们主要介绍一致拓扑 集中拓扑和定向拓扑三种路由信 息分发的拓扑结构 1 一致拓扑 c o n g r u e n tt o p o l o g y 图2 4 显示了一个包括了一个网络的r a 所有的节点对都由一条或者多条链 路连接 并且在相关的r c 之间有路由邻接关系 这里路由邻接拓扑与传送网络的 拓扑相同 当传送网拓扑是完全的格状拓扑时 传送的冗余路由信息的数量就会 大大增加 t 麝由每接母喀由控捌霹 图2 4 一致拓扑信息流示例 7 i j 2 集中拓扑 h u b b e dt o p o l o g y 图2 5 显示了一个在网络中包含有一个和多个路由消息服务器的r a 网络中 每个r c 都会和一个消息服务器保持着联系 消息服务器反过来又将从一个r c 接 收到的路由消息传递给路由域中其它与自己关联的r c 结果 当一个i 配加入网 络时 和路由消息服务器相关联的r c 数目线性增加 由于所有消息的发送都要经 过路由消息服务器 因此可以通过在路由消息服务器上设置路由信息分布策略加 以控制 但这种方法会造成路由信息在相同的d c n 链路上传送多次 在这种结构 下