（计算机应用技术专业论文）ason中基于蚁群系统的动态路由和波长分配算法研究.pdf

江苏大学硕士学位论文 摘要 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 的核心技术之一 是体现a s o n 智能性的关 键所在 对智能化动态r w a 算法的研究对提高a s o n 的实用性具有重要意义 一个良好的r w a 算法能实时地探测网络状态 进而合理而高效地分配各种网络 资源 促进全网负载的均匀化 从而有效地降低全网平均阻塞率 提高网络的资 源利用率 a s o n 对网络资源调度的灵活性提出了很高的要求 同时又要保证满足实时 业务的低阻塞率要求 但是由于a s o n 中一系列新技术如波长转换 光交换 光存储的应用 使得a s o n 的计算环境远比传统的光传送网要复杂 这就使得 针对传统光传送网设计的一系列r w a 策略在a s o n 中表现不是很理想 主要体 现为不能全面考虑网络资源的合理分配 优化目标过于单一 算法灵活性不够等 一系列问题 蚁群算法a c a a n tc o l o n ya l g o r i t h m 来源于对自然界蚂蚁寻找从蚁巢到 食物的最短路径并找到回巢路径方法的研究 是一种启发式搜索算法 具有讵反 馈 较强的鲁棒性 分布式等特点 特别适用于解决组合优化问题 而动态r w a 本质上也是组合优化问题 因此作为试探性的研究 本文基于蚁群算法基本原理 设计了一种适合于a s o n 网络的动态r w a 算法 目标是使r w a 算法能充分考 虑a s o n 的要求 更合理地分配网络资源 从而降低网络业务的阻塞概率 论文研究分析了a s o n 中动态r w a 模块的相关技术体系 包括a s o n 的路 由体系 a s o n 中动态r w a 的影响因素以及蚁群算法的基本思想 提出并构建 了基于蚁群系统的动态r w a 算法模型 并设计了基于上述相关技术的仿真平台 以及基于仿真平台对算法进行了仿真测试和改进 主要成果如下 1 分析和归纳了a s o n 网络的路由体系和路由技术 包括多域分层路由 分布式波长分配 信令路由协议 路由分发拓扑等与r w a 有关的功能模块 以及 a s o n 中实现动态r w a 的相关影响因素及关键技术 2 研究了蚁群算法的基本思想 创新性地提出了一种基于蚁群系统的将 路由和波长分配结合考虑的动态r w a 算法 该算法在运行中能综合考虑网络资 源状态和不同业务的需求优先等级 较之传统基于最短路径的动态r w a 策略 江苏省自然科学基金0 4 k j b 5 2 0 0 2 7 资助项日 江苏大学硕士学位论文 该算法能取得更优异的全网平均阻塞性能 3 分析和归纳了蚁群算法在运行中的不稳定因素及执行效率的影响因素 引入了变异思想 局部搜索优化和调整信息量的更新策略 相应改进了原始算法 的搜索效率和收敛时间 防止算法陷于早熟陷阱 并在仿真平台上仿真测试了运 行性能 结果表明 改进措施能在一定程度上提高算法性能 4 为验证评估本文及文献中提出的各种算法的性能 自行开发了算法的 仿真软件 并进行了大量的仿真测试工作 5 仿真测试了蚁群算法的实际运行性能 并根据测试结构调整算法参数 使该算法在同等资源开销下取得了较好的效果 关键词 a s o n 动态r w a 蚁群算法 资源分配 阻塞率 江苏大学硕士学位论文 a b s t r a c t w i t he n d u i n gt 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 kw i t hu n p r e c e d e n t e df l e x i b i l i t y a n de x p a n s i b i l i t y 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 r e p r e s e n t e dt h e f u t u r ed i r e c t i o no fn e x tg e n e r a t i o no p t i c a ln e t w o r k s a so n eo ft h ec o r et e c h n o l o g yo f a s o n t h ed y n a m i cr 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 ta l g o r i t h mi st h ek e yf o r a s o nt or e f l e c t i n gi t si n t e l l i g e n c e u n d o u b t e d l y t h es t u d yo ni n t e l l i g e n td y n a m i c r w aa l g o r i t h mi ss i g n i f i c a n tt oi m p r o v et h ep r a c t i c a b i l i t yo fa s o n b yap e r f e c t r w aa l g o r i t h m t h es t a t eo fw h o l en e t w o r kc a nb er e a l t i m l ys u r v e y e d s e v e r a l n e t w o r kr e s o u r c e sc a nb ed i s t r i b u t e dm o r er a t i o n a l l ya n dt h en e t w o r kl o a d sc a nb e b a l a n c e dh i 曲一e f f i c i e n t l y t h u st h ew h o l en e t w o r kb l o c k i n gp r o b a b i l i t yw i l lb c r e d u c e de f f e c t i v e l ya n dt h er e s o u r c eu t i l i z a t i o nw i l lb ei m p r o v e de v i d e n t l y i na s o n t h e r ei sah i g hd e m a n df o rt h e t h ef l e x i b i l i t yo fr e s o u r c es c h e d u l i n go f n e t w o r k a tt h es a l n et i m e t h el o wb l o c k i n gp r o b a b i l i t yo fr e a l t i m eb u s i n e s ss h o u l d b eg u a r a n t e d b u tb e c a u s eo ft h ea 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 s w a v e l e n g t hc o n v e r s i o n o p t i c a le x c h a n g e o p t i c a ls t o r a g e e t c t h ec a l c u l a t i o n e n v i r o n m e n to fa s o ni sf u r t h e rc o m p l i c a t e dt h a nt h et r a d i t i o n a lo p t i c a lt r a n s p o r t n e t w o r k s oas e r i e so fr w as t r a t e g yw h i c ha r cd e s i g n e df o rt r a d i t i o n a lo p t i c a l t r a n s p o r tn e t w o r kc a nn o tw o r kw e l li na s o n i th a se x p o s e das e r i e so fq u e s t i o n s u c ha sc o n s i d e r i n gr e a s o n a b l er e s o u r c ea s s i g n m e n ti np a r t p u r p o s e o p t i m i z i n gg o a l s i n g l y i n s u m c i e n tf l e x i b i l i t yo f a l g o r i t h m s e t c a sah e u r i s t i cs e a r c ha l g o r i t h m a c a a n tc o l o n ya l g o r i t h m t a k e si n s p i r a t i o n f r o mt h eb e h a v i o ro fs e a r c h i n gr o u tf r o mn e s tt of o o do fr e a la n tc o l o n i e s i ti su s e dt o s o l v ec o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s w i t hi t sc h a r a c t e r i s t i c so fp o s i t i v e f e e d b a c k d i a r i b m a b l ea n ds t r o n g l yr o b u s t n e s s c o n s i d e r i n gd 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 t r w a 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 n p r o b l e m t h i sp a p e rd e s i g n san e wd y n a m i cr w as t r a t e g yb a s e do np r i n c i p l eo fa c a w h i c hi sa d a p t e dt ot h ee n v i r o n m e n to fa s o nn e t w o r k s t h ef o c u so ft h es t r a t e g yi s m o r er a t i o n a l l yr e s o u r c ea s s i g n m e n ti nn e t w o r k s i t l lt h eo b j e c t i v eo fm i n i m i z i n g c o n n e c t i o nb l o c k i n go f t h ed y n a m i cb u s i n e s s t h et h e s i ss t u d i e sa n d a 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 鼢m o d u l e i na s o n i n c l u d i n gt h er o u t i n gs y s t e mo f a s o n t h e i n f l u e n c i n gf a c t o ro fd y n a m i ci n a s o na n dt h ep r i n c i p l eo fa c a a n dad y n a m i cr w r aa l g o d t h mm o d e lb a s e do n a c 0 a n tc o l o n yo p t i m i z a t i o n i na s o ni sp r e s e n t e da n ds t r u c t u r e d w i t h a 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 np l a t f o r mi sd e s i g n e dt o t e s ta n d i m p r o v et h ea l g o r i t h m t h em a i na c h i e v e m e n t sa r e 觞f o l l o w s i 江苏大学硕士学位论文 1 t h er o u t i n gt e c h n o l o g ya n ds y s t e mo fa s o nn e t w o r ka l ea 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 em u l t i a r e ah i e r a r c h i c a lr o u t i n g d i s t r i b u t e dw a v e l e n g t h a s s i g n m e n t s i g n a l i n gr o u t i n gp r o t o c o la n dm 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 e i n f l u e n c ef a c t o ra n dk e yt 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 w ai na s o na r e a l s oa n a l y z e di 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 f a c a ad y n a m i cr w aa l g o r i t h mb a s e do na c o i 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 p r o c e s s i n go f 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 s u b p r o b l e mc a nb 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 kr e s o u r c ea n d p r i o r i t yo fd i f f e r e n tb u s i n e s ss y n t h e t i c a l l y c o m p a r e dw i t l lt r a d i t i o n a ld y n a m i cr w a s t r a t e g yb a s e do no 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 el o w e r b l o c k i n gp r o b a b i l i t y 3 t h ed e s t a b i l i z i n gf 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 na c 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 t oi m p r o v es e a r c h i n ge f f i c i e n c y s h o r t e nt h e p r o c e s st i m ea n dp r e v e n tt h ea l g o r i t h mf r o ms i n k i n gi n t oe a r l y m a t u r i n gt r a p t h e p r i n c i p l eo fa b e r r a n c ea n dl o c a ls e a r c ho p t i m i z a t i o ni na l g o r i t h mi sp r a c t i c e da n d i n f o r m a t i o nu p d a t es t r a t e g yi sa d a p t e d t h eo p e r a t i o np e r f o r m a n c eo fa l g o r i t h mi s t 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 dt h a tt h ei m p r o v i n g m e a s u r ec a ni m p r o v et h ep e r 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 t 4 s i m u l a t i o ns o r w a r ei sd e v e l o p e dt ov e r i f yt h ep e r f o r m a n c eo fd i f f e r e n t a l g o r i t h m sa n d al a r g ea m o u n to f t e s t j o b sa r cc a r r i e do n 5 t h ep e r f o r m a n c eo fa c ab a s e dr w aa l r o t i t h mi ss i m u l a t e d a c c o r d i n gt o t h er e s u l t p a r a m e t e r so fa l g o r i t h ma r ea d a p t e d a n d t h ea l g o r i t h mc a ng e tb e u e r r e s u l ta tt h ee q u a lr 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 w a a n tc o l o n ya 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 b l o c k i n gp r o b a b i l i t y 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学位保 留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借 阅 本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索 可以采用影印 缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 保密口 在年解密后适用本授权书 不保密区 学位论文作者签名 弱 海垒 如o 年6 月 1 日 指导溯签名 釉 砂 舜6 月 f 日 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独立进 行研究工作所取得的成果 除文中已注明引用的内容以外 本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果 对本文的研 究做出重要贡献的个人和集体 均已在文中以明确方式标明 本人完 全意识到本声明的法律结果由本人承担 学位论文作者签名 盈 晦生 日期 卫o o f 年6 月f f 日 江苏大学硕士学住论文 第一章绪论 本章按以下节结构展开 1 1 研究背景 1 2 论文研究意义 1 3 论文的研究 内容及关键技术 1 4 论文的组织安排 1 1研究背景 i p 业务的突发性和不确定性要求网络带宽动态分配 传统的静态光传输网 难以满足要求 在这种需求下 传统光网络向下一代能支持多信道 高容量 可 配置 智能型的网络演进 在这种演进过程中 点到点的w d m 2 1 w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g 波分复用 系统迈出了解决问题的第一步 其基本原理是在 发送端将不同波长的光信号通过复用器组合起来 复用 并耦合到单模光纤中 进行传输 在接收端再通过解复用器将组合波长的光信号分开 解复用 恢复 出原始光信号后送入不同的终端 系统构成如图1 1 所示 竺 f d f a 狂竺一 t f 謦哲先坪礁七鼍 7 型生 卜 卜 一 丽 弧i 一西运一移m z 一 二遗亘一 一 一 一 图1 1 点到 最波分复用系统 在具备了w d m 能力之后 光传送网络第一次拥有了在光层直接交叉组网的 能力 而现代光网络技术的发展可谓是一同千里 传统的w d m 光通信网也随之 向以a s o n a u t o m a t i c a l l y s w i t c h e d o p t i c a l n e t w o r k 自动交换光网络 为代表的 新一代智能化光网络的方向发展 i p 技术如何与光网相结合 如何赋予光网一 定的智能性 如何提供保证的q o s 服务等问题已摆在人们面前 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 tn 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 突破性地 引入了更加智能化的控制平面 从而使光网络能够在信令的控带0 下完成网络连接 的自动建立 资源的自动发现等过程 其体系结构主要表现在具有a s o n 特色 的3 个平面 3 个接口以及所支持的3 种连接类型上 体系结构如图1 2 所示 江苏大学硕士学位论文 h q c c i 4 n n m i f u n m i t h 4 t t m u 图1 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 l 3 1 欧洲电信研究与开发组织e u r e s c o m 的f a s h i o n i q 以及 商业公司的努力 主要有s y c a m o r e 5 j 公司的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 6 j n o r t e l 公司的o p t e r a l 7 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 i s n e c 公司的三位一体综合管理系统n m s 9 i a l c a t e l 的a b s vo c i s c o 公司的完整光多业务边缘和传输c o m e t 在国内主 要有2 0 0 3 年启动的中国8 6 3 计划重大专项3 t n e t 幢 核心技术有太比特级智能 光网系统 太比特级多颗粒度路由交换系统和太比特级网络应用支撑环境 动态路由和波长分配 r o u t i n ga n dw a v e l e n f t h a s s i g n m e n t r w a 技术是指 在实时业务情况下光通路的路由选择和波长分配的优化问题 它是构建a s o n 实现对全光网的智能化控制和管理的关键技术之一 a s o n 网络之所以是自动交 换光网络 体现在a s o n 网络第一次在光网络中实现了光信道建立的智能性 也即是a s o n 网能够根据用户的呼叫请求 在控制平面的路由与信令机制的引 导下 按照用户的业务要求 如服务等级协定s l a 自动完成源端用户与目的 端用户之间光传输通道的建立 由于o t n 承载的业务需求正呈爆炸式增长 而 可用资源 波长 光纤等 确实有限 因此能综合优化各种目标 如资源利用率 阻塞率 生存性等 的智能化动态r a 算法就显得尤为重要 出于r a 问题 是n p c 问题 文献d 3 t 6 1 中大多将r w a 问题拆分成路由和波长分配两个子问题 分别加以解决 这类算法大多建立于传统电路交换网络无向多图 u n d i r e c t e d m u l t i g r a p h 模型1 1 7 l 上 路由策略常用最短路径路由或链路最小负荷路由 波长分 配策略则有f i r s t f r 最先适用 l i l e a s t i n f l u e n c e 最小影响 l l r 1 e a s t l o a d e d r o u t i n g 最小负载路由 等 路由选择和波长分配同时进行的算法则建立在一种 江苏大学硕士擘位论文 新的模型 分层图模型 1 8 1 目前在该模型中找最佳路由只是通过简单地对请求的 光路采用最短路径算法 i9 得到解决 蚁群算法a c a a n tc o l o n ya l g o r i t h m 2 0 是目前三种典型的拟生态算法 2 1 1 之一 其他两种是遗传算法 2 2 1 2 4 1 和免疫算法 2 5 也8 1 受真实蚁群觅食行为的启发 而产生的由大量有限个蚂蚁的个体行为组成的多a g e n t 系统 是一种分布式 启 发式搜索算法 蚁群算法经历了如下发展历程 1 9 9 1 d o r i g o 等首次提出蚁群算法f 2 9 a 0 1 1 9 9 8 年 2 0 0 0 年 2 0 0 2 年在布鲁塞尔召开了三届国际蚁群算法工作会议 议题为从蚁 群仿生到人工蚁群 2 0 0 4 年在布鲁塞尔召开第四届国际蚁群算法工作会议 议题 为蚁群优化和蠕虫智能 s t u t z l e 和h o o s 在文献 l 中用蚁群算法对t s p 问题进行 集中求解p 2 3 9 g u t j a h r 的文掣3 3 1 给出蚁群算法收敛性的证明 w a g n e r l i n d e n b a u m 和b r u c k s t e i n 在文献 3 4 中报告了一个用于图覆盖问题的非常简单有效的算法收敛 性证明 m a n i e z z o 和c e b o n a r o 将蚁群算法应用到广播网的频率分配中 3 5 1 蚁群算法近年来已成功地应用于解决组合优化问题 如 t s p t r a v e l i n g s a l e s m a n p r o b l e m 旅行商问题 q a p q u a d r a t i c a s s i g n m e n t p r o b l e m 二次指 派问题 1 3 7 j s p j o b s h o ps c h e d u l i n gp r o b l e m 工作排程问题 3 8 等 而动态r w a 问题本质上也是组合优化问题 因此从解决问题的角度讲蚁群算法非常适合于解 决动态r w a 问题 蚁群算法具有很强的并行性和天生的分布式特性 而分布式的r w a 算法也是 解决大型网络r w a 问题的方向之一 并且连接请求的建立过程总是无预期的并发 进行的 蚁群算法的这些特性为解决r w a 问题提供了便利 蚁群算法具有很强的发现较好解的能力 由于算法本身的正反馈原理 加快 了进化过程 因此相对于遗传算法 免疫算法来说蚁群算法更符合r w a 问题对实 时性的要求 蚁群算法具有较强的健壮性 对初始化条件要求不高 运行过程中无需干预 的特点 这些特点使得蚁群算法在复杂的网络环境中更容易控制 因此蚁群算法非常适合应用于智能化的动态r w a 问题的解决之中 1 2 论文研究意义 尽管对动态r w a 算法的研究已经取得了很多成就 但是目前相对比较成熟 的算法在适应a s o n 的要求上仍然存在较大的差距 主要表现为把路由和波长 分配分开计算的算法忽略了r w a 问题本质上是一个整体 导致此类算法只能优 江苏大学硕士学位论文 化特定的有限个指标 无法达到全局优化的目的 而基于分层图的最短路径法需 要每个节点都具有全局的网络状态信息 并且信息必须频繁地刷新否则不能正确 地反映网络的变化 对于大规模网络需要大量的通信开销 当涉及多个限制时 可能造成源节点的计算开销过大 蚁群算法在完美解决动态r w a 问题的同时 还具有分布计算 并行执行 智能恢复和重构等优点 完全符合a s o n 智能化控制和管理的要求 但是 原 始的蚁群算法也存在算法收敛慢 容易早熟 停滞 求解时间过长 在特定条件 下难以得到全局最优解等不足 要想把蚁群算法真正运用于实际 则必须进一步 研究以克服原始蚁群算法的不足之处 蚁群算法在构建智能光网络中巨大的潜在 价值已引起国内外广泛的注意 相关的研究开发大多处于理论探讨阶段 目前国 际上还没有一种完全成熟的智能化的波长选路方法 如果能开发出有自主知识产 权的核心选路算法 就具有国际领先水平 鉴于以上分析 基于蚁群系统设计一种高效的智能化的动态r w a 算法 能 够全局优化各种指标 合理分配网络资源 并且能克服原始蚁群算法存在的一些 先天的不足 体现了将i p 技术和智能与光技术相结合的特色和创新之处 对于 建立实用的a s o n 促进光网络的进一步发展有着重要的意义 并将产生良好的 经济效益和社会价值 1 3 论文的研究内容及关键技术 本文在广泛研究国内外相关的仿生算法和a s o n 中动态r w a 问题基础上 首 次将蚁群算法引入动态r w a 问题求解中 在基于i po v e rw d m 的网络结构中 将 r w a 的选路子问题和波长分配子问题结合考虑 应用蚁群算法进行分布式求解动 态r w a 问题 同时以蚁群算法为核心策略合理分配网络资源 降低网络阻塞率 论文的主要研究内容包括以下几个方面 1 研究a s o n 中动态r w a 问题的影响因素 相对传统的w d m 光网络 a s o n 对动态r w a 问题的解决提出了新的要求 论 文在解析a s o n 路由架构的基础上 研究了a s o n 中动态r w a 问题的新特点 总体 上把握了r w a 算法应该考虑的优化目标及影响因素 为后文设计基于蚁群系统的 动态r w a 算法提供参考 2 研究和设计a s o n 中的蚁群算法 在深刻理解蚁群算法基本思想的基础上 研究利用蚂蚁具有找到最短路径及 不同种类蚂蚁具有互斥的天然特性 根据a s o n 网络的网络拓扑结构定义不同类型 江苏大学硕士学位论文 的蚂蚁即不同的荷尔蒙参数 网络的初始信息 网络各路径的权值定义等 建立 蚂蚁寻路的数学模型 设计计算方法和算法流程 并将a s o n 网络构造成分层图模 型 实现路由选择和波长分配的统一考虑 全局优化资源分配 提高网络性能 3 构建算法仿真平台及对算法性能进行测试 编程模拟网络环境 设计r w a 算法仿真平台 同时对本文设计的算法以及其 他的一些算法进行性能测试 分析比较测试结果并调整算法参数 运用各种参数 组合进行仿真实验 优化算法性能 阻塞率 执行时间 收敛路径是否最优 找出算法性能最佳时的参数组合 4 对基本算法进行改进 在仿真实验的基础上 分析影响算法性能的因素及算法存在的问题 根据仿 真结果改进基本算法 并运行仿真测试改进效果 本文所设计的基于蚁群算法的动态r w a 策略经系统仿真证明 能有效降低网 络阻塞率 同时能够优化网络资源分配 平衡网络负载 维持高效的带宽利用率 和适应业务流的变化 对优先级的支持也证明了算法用于o o s 的可能性 算法对 提高a s o n 的实用性有重要的影响 同时 将蚁群算法的应用范围扩大到动态r w a 的计算对蚁群算法的发展也具重要意义 1 4 全文的组织安排 本文第二章首先介绍了a s o n 的路由体系结构 接着对a s o n 的路由需求 和相关功能进行了分析 重点探讨了a s o n 中路由技术的新特点 然后在此基 础上 讨论了波长转换约束 波长连续性约束等一般光网络中影响r w a 问题解 决的因素 接着对a s o n 智能光网络中的路由技术中需要额外考虑的动态计算 资源分配等问题进行了阐述 最后分析了适合a s o n 的r w a 算法 第三章研究了蚁群算法的基本思想 并扩展了原始的分层图模型使之支持波 长转换 然后在分层图模型上 基于蚁群系统构建了动态r w a 问题的蚁群算法 模型 模型中主要考虑了对网络资源的合理分配 并支持网络业务的优先级 然 后分析了由蚁群思想带给算法的一些先天不足 并分别提出了交异 局部搜索 调整信息量更新方式等三种改进方式 第四章阐述了r w a 算法仿真平台的构建过程 并提供了主要模块的伪代码 以供参考 第五章提供了在仿真平台上对算法做测试得出的各种结果 包括阻塞率对 比 执行时问对比 对算法影响因素的各种分析结果等 江苏大学硕士学位论文 第二章a s o n 中的路由和波长分配 在传统的基于电路交换的电话网中 只涉及到为连接请求建立路由的问题 而在a s o n 网络中 由于其特殊性 在给定一个连接请求后 需要为之建立路 由并在路由上分配波长 这通常被称为路由和波长分配问题 r w a a 由于o t n 承载的业务需求正呈爆炸式增长 而可用资源 如波长 光纤等却是有限 因 此r w a 问题显得尤为重要 目前 有多种基于不同优化目标 如资源i 4 用率 嗣络 5 h 塞概率 生存性等 和适用范围的r w a 算法存在 在这些算法中 根据 不同的网络结构 业务特点以及不同的运营商的要求会有不同的选择 因此 我 们需要考虑r w a 问题在智能光网络环境中具体需要解决的问题 在本章中 首先对a s o n 的路由体系结构和各种路由技术进行分析 然后 在分析传统w d m 网络中r w a 问题的基础上 着重从多域分屠路由 分布式波 长分配和信令路由协议等几个方面对a s o n 中的r w a 问题进行了讨论 分析比 较了目前各种适用的r w a 算法以及存在问题 2 1a s o n 中的路由技术 21 1 s 0 n 的路由体系结构 在i t u t 的g 7 7 1 5 捌协议中对在a s o n 中建立交换连接和软永久连接选 路的功能结构和要求进行了描述 提出了a s o n 的路由体系结构 a s o n 路由 体系结构支持f i 9 0 8 0 1 4 0 协议定义的不同的路由方式一一层次路由方式 源路由 方式和逐跳路由方式 本文主要关注层次路由 a s o n 的路由功能体系结构主要由多种控制平面的功能组件组成 包括与协 议无关的组件 如链路资源管理器 l r m l i n kr e s o u r c em a n a g e r 路由控制 器 r c r o u t ec o n t r o l l e r 以及与协议相关的组件 如协议控制器 p c p r o t o c o l c o n t r o l l e r r c 主要用于处理路由的抽象信息 而p c 依据信息经过的参考点来 处理与协议相关的消息 并将路由原语传递给r c 图2 1 给出了路由功能组件 处理与协议相关的消息 并将路由原语传递给r c 图2 1 绘出了路由功能组件 之间的关系图 江苏大学硕士学位论文 第二章a s o n 中的路由和波长分配 在传统的基于电路交换的电话网中 只涉及到为连接请求建立路由的问题 而在a s o n 网络中 由于其特殊性 在给定一个连接请求后 需要为之建立路 由并在路由上分配波长 这通常被称为路由和波长分配问题 r w a 由于o t n 承载的业务需求正呈爆炸式增长 而可用资源 如波长 光纤等却是有限 因 此r w a 问题显得尤为重要 目前 有多种基于不同优化目标 如资源利用率 网络阻塞概率 生存性等 和适用范围的r w a 算法存在 在这些算法中 根据 不同的网络结构 业务特点以及不同的运营商的要求会有不同的选择 因此 我 们需要考虑r w a 问题在智能光网络环境中具体需要解决的问题 在本章中 首先对a s o n 的路由体系结构和各种路由技术进行分析 然后 在分析传统w d m 网络中r w a 问题的基础上 着重从多域分层路由 分布式波 长分配和信令路由协议等几个方面对a s o n 中的r w a 问题进行了讨论 分析比 较了目前各种适用的r w a 算法以及存在问题 2 1 a s o n 中的路由技术 2 1 1 a s o n 的路由体系结构 在l t u t 的g 7 7 1 5 3 9 1 协议中对在a s o n 中建立交换连接和软永久连接选 路的功能结构和要求进行了描述 提出了a s o n 的路由体系结构 a s o n 路由 体系结构支持g 8 0 8 0 4 0 协议定义的不同的路由方式一一层次路由方式 源路由 方式和逐跳路由方式 本文主要关注层次路由 a s o n 的路由功能体系结构主要由多种控制平面的功能组件组成 包括与协 议无关的组件 如链路资源管理器 l r m l i i l kr e s o u r c em a n a g e r 路由控制 器 r c r o u t ec o n t r o l l e r 以及与协议相关的组件 如协议控制器 p c p r o t o c o l c o n t r o l l e r r c 主要用于处理路由的抽象信息 而p c 依据信息经过的参考点来 处理与协议相关的消息 并将路由原语传递给r c 图2 1 给出了路由功能组件 之间的关系图 6 江苏大学硕士学位论文 图2 1 路由功能组件关系图 a s o n 路由功能体系结构中各个功能组件的作用如下 1 路由控制器r c r c 的功能主要包括与对等端的r c 交换路由信息 并通过对路由信息数据 库的操作来回复路由查询 路径选择 信息 r c 与具体的协议无关 2 路由信息数据库 i b r d b 负责存储本地拓扑 网络拓扑 可达性和其他通过路由信息交换获得 的信息 还可以包括配置的信息 r d b 可以包含多个路由域的路由信息 r c 可 以接入r d b 的一个视图 并获得相应的信息 图1 的虚线框表示了这种关系 r d b 与具体协议无关 由于r d b 可以包含多个路由域的路由信息 因此接入 r d b 的r c 可共享路由信息 如图2 2 所示 图2 2r d b 与多路由域中r c 的关系 3 链路资源管理器 l r m l r m 负责向r c 提供所有子网端点池 s n p p 链路信息 并将其控制的链 路资源的任何状态的改变情况告诉r c 4 协议控制器 p c p c 将路由的原语转换成特定路由协议的协议消息 因此 p c 是与协议相关 的 p c 还处理用于路由信息交换并与协议相关的控制信息 为达到控制一个连接建立的目的 a s o n 控制平面需要在多个组件之间进行 江苏大学硕士学位论文 信息交互 与连接过程相关的组件主要包括连接控制器 c c 以及上面提到的 r c 和l r m 针对多域网络环境中动态光通道 例如s c 的建立 a s o n 智能光网络中 提出了三种路由模式 层次路由 h i e r a r c h i c a l r o u t i n g 源路由 s o u r c e r o u t i n g 和逐跳路由 s t e p b u s t e pr o u t i n g 下面主要介绍层次路由及其实现 在a s o n 中 从水平方向来说 一般可划分成不同的路由域 每个路由域 又可分为不同的子网 而子网之间可以互相嵌套 一个大的子网 上层子网 内 部可包含若干个小的子网 下层子网 形成层次结构 每个子网都知道本身的 拓扑结构并能进行动态连接控制 但不了解层次结构结构中的上层或者下层子网 的拓扑结构 在层次路由中 子网层次的每一级都有一个包含r c c c 和l r m 的主节点 负责本级子网的选路 每级主节点之间按照层次结构的关系互相作用来选择路 由 如图2 3 所示 连接请求首先到达最上层子网主节点a 由它计算出在源和 目的节点之间的路径需要经过的下一层子网 包括b f 和c 控制的子网 和它 们之间的链路连接 然后就通知相关的下层子网主节点b f 和c 分别建立在自 己子网内部对应的连接 这样由上到下逐级子网进行分段的选路 最终将得到整 个连接的路由 由图中可以看出 路由建立过程中 子网也被看作是一个节点 因此 分级路由在本质上就是寻找两点间的连接通路 一连接请求溺皂 回 鲁 点 t i of h 图2 3层次路由模式中的连接建立信令流程 21 2 a s o n 的路由属性及路由消息分发拓扑 通过路由协议分发的路由信息可分为基于链路的和节点的信息 这里的节点 可表示一个r a 或子网 这是根据计算路由时路由层次的需要确定的 另一个重 要的路由属性包括资源的属性 它们可能因为连接的建立和拆除而改变 当网络 里的连接建立和拆除发生的较为频繁时 这些属性需要特别对待 1 节点属性 对一个节点来说