（计算机应用技术专业论文）基于d思想的ason动态均衡恢复策略研究.pdf

江苏大学硕士学位论文 摘要 随着i n t e m e t 的高速发展 全球数据业务呈爆炸式增长 数据业务动态 突 发等特性对传统的光传送网 o t n o p t i c a lt r a n s m i s s i o nn e t w o r k 提出了更高的 要求 自动交换光网络 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 作为一 项新的智能光网络技术的出现 赋予了光网络前所未有的灵活性和可扩展性 已 经成为下一代网络 n g n n e x tg e n e r a t i o i ln e t w o r k 的重要发展方向 其中 对 多种恢复机制的支持是a s o n 的一个重要特点 a s o n 上承载的多种业务要求网 络具有快速 智能和多样化的故障恢复能力 同时能够合理有效地分配网络资源 而目前基于传统光传送网设计的一系列恢复机制远远不能满足a s o n 对生存性的 要求 因此 对a s o n 恢复问题的研究已成为a s o n 研究的一个重点之一 d 宰算法 d s t a ra l g o r i t h m 是一种动态环境下的启发式 h e u r i s t i e 搜索算 法 应用于环境为未知 部分已知或不断变化的状态空间搜索中 具有智能 高 效 鲁棒性 易于实现分布式等优点 博弈论是研究具有斗争或竞争性质现象的 理论和方法 论文在研究探讨了a s o n 及其恢复相关问题的基础上 运用d 簟算 法 并结合混合策略博弈理论 设计了一种动态均衡的a s o n 恢复策略 通过路 由和波长分配 r w a 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 为受损业务提供恢复 通道 目的是在快速恢复故障的同时 合理利用网络资源 从而提高网络的故障 恢复率 增强网络的生存性 论文围绕a s o n 的动态恢复问题展开论述 主要完成的工作和取得的成果如 下 1 分析归纳了a s o n 控制平面的结构 功能 a s o n 路由体系结构 路 由方式 消息分发 a s o n 的生存性及恢复策略以及a s o n 动态路由和波长分配 r w a r o u t ea n dw a v e l e n g t h a s s i g n m e n t 技术等与a s o n 恢复问题相关的背景 知识和影响因素 2 研究了d 宰算法和混合策略博弈的相关理论 提出了一种基于d 幸思想的 a s o n 动态均衡恢复策略j 将网络中的路径代价与当前状态下的波长资源占用情 况综合考虑 运用混合博弈原理求解波长占用与路径代价之间的纳什均衡 n a s h e q u i l i b r a t i o n 并以此动态建立d 木算法的估计函数 使恢复策略能够在动态通道 恢复过程中尽量保证网络资源的合理分配 相对于传统的最短路径恢复策略和简 单的动态恢复策略 该策略能够取得更高的恢复率和更低的网络资源占用率 江苏大学硕士学位论文 3 根据恢复策略的思路 详细分析并设计实现了均衡d 木算法的原理 包 括建立数据结构和数学模型 以及流程设计和性能分析等 针对仿真实验时发现 由于求解纳什均衡非线性方程组而造成算法收敛较慢的不足 设计了一种结合 n e w t o n 迭代法和最小二乘法求解纳什均衡非线性方程组的方法 仿真实验证明 可以大大加快算法的收敛速度 4 采用c 群和m a t l a b 混合编程技术 自行开发了恢复策略的仿真系统 模拟实际网络环境对恢复算法性能进行了测试 并且 用传统的最短路径算法和 另行设计的简单d 水算法与之进行了比较 仿真结果表明 该算法在阻塞率 恢复 率以及资源占用率上都明显优于相比较的其他算法 且时间性能可以较好满足 a s o n 中恢复时间的要求 关键词 自动交换光网络 动态恢复 d 母算法 纳什均衡 路由和波长分配 江苏大学硕士学位论文 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fi n t e r n e t t h eg l o b a l d a t at r a f f i cg r o w t hi s e x p o n e n t i a l t h ed y n a m i c b u r s tc h a r a c t e r i s t i c so fd a t at r a f f i cp r e s e n tt h eh i g h r e q u i r e m e n tt ot r a d i t i o n a lo p 廿c a lt r a n s m i s s i o nn e t w o r k o t t o a s an e w t e c h n o l o g y o f i n t e l l i g e n to p t i m a ln e t w o r k t h ea p p e a r a n c eo fa u t o m a t i c a l l ys w i t c h e do p t i m a ln e t w o r k a s o n e n d u et r a d i t i o n a lo p t i m a lt r a n s p o r tn e t w o r kw i mu n p r e c e d e n t e df l e x i b i l i t ya n d e x p a n s i b i l i t y a s o nr e p r e s e n t e dt h ef 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 nn e t w o r k s n g n h e r e i n t o s u p p o r t i n gm a n yk i n d so fr e s t o r a t i o ns t r a t e g yi sa ni m p o r t a n t c h a r a c t e r i s t i co fa s o n m u l t i t r a f f i c sc a r r i e di na s o nd e m a n dt h ef a s ta n d m u l t i s c h e m e sr e s t o r a t i o na b m t yo fn e t w o r k s i m u l t a n e i t y r e a s o n a b l ya n de f f i c i e n t l y a s s i g nt h en e t w o r kr e s o u r c e s h o w e v e r a tp r e s e n t as e r i e so fr e s t o r a t i o ns t r a t e g yt h e r e a r ed e s i g n e df o rt r a d i t i o n a lo p t i m a lt r a n s m i s s i o nn e t w o r ka r eh a r d l ys a t i s f i e dw i t ht h e s u r v i v a b i l i t yr e q u e s to fa s o n t h e r e f o r e t h er e s e a r c ho na s o nr e s t o r a t i o np r o b l e m b e c a m eaf o c u si na s o ns t u d i e s d p s t a r a l g o r i t h m i sah e u r i s t i cs e a r c ha l g o r i t h mi nd y n a m i ce n v i r o n m e n t s r i sa p p l i e dt op a t h sp l a n n i n gi nu n k n o w n p a r t i a l l yk n o w n a n dc h a n g i n gs t a t es p a c e s 谢ma d v a n t a g e ss u c ha si n t e l l i g e n c e 一h i 曲e f f i c i e n c y r o b u s t n e s s a n de a s yt oa c t u a l i z e d i s t r i b u t i n g e t c g a m et h e o r y i st h em e t h o da n da r c h i t e c t u r et or e s e a r c ht h e p h e n o m e n aw i t hs t r u g g l i n go rc o m p e t i t i v ec h a r a c t e r s b a s e do nr e s e a r c h i n gt h e r e l a t i v ep r o b l e mo fa s o na n dr e s t o r a t i o ni na s o n t h ea r t i c l ed e s i g nad y n a m i c e q u i l i b r a t e dr e s t o r a t i o ns t r a t e g yi na s o nu s i n gd 掌a l g o r i t h ma n du n i t i n gg a m et h e o r y o fm i x e ds t r a t e g yt op r o v i d et h er e s t o r a t i o nc h a n n e lf o rf a i l e dt r a f f i cb yr 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 t h ep u r p o s ei st or e s t o r ef a u l tr a p i d l y s i m u l t a n e o u s l y t o a s s i g nt h en e t w o r kr e s o u r c e sr e a s o n a b l y a n dt h e nt oi m p r o v et h er a t eo fr e s t o r a t i o n a n de n h a n c es u r v i v a b i l i t yo fn e t w o r k i nt h i st h e s i s t h er e s e a r c hi sf o c u so nr e s t o r a t i o ni na s o n t h em a i nw o r k sa n d i n n o v a t i v er e s u l t sa r el i s t e da sf o l l o w 1 a n a l y z i n ga n ds u m m i n gu pt h eb a c k g r o u n dk n o w l e d g ea n di n f l u e n c ef a c t o r s r e l a t e dp r o b l e m so fr e s t o r a t i o no fa s o n w h i c hi n c l u d ef r a m e w o r ka n df u n c t i o n so f c o n t r o lp l a n e a r c h i t e c t u r ea n dm o d e so fr o u t e m e s s a g ed i s t r i b u t i o n t h es t r a t e g i e so f m 江苏大学硕士学位论文 s u r v i v a b i l i t ya n dr e s t o r a t i o n t h et e c h n i q u e s o fd y n a m i cr o u t ea n dw a v e l e n g t h a s s i g n m e n t r w a e t c i n a s o n 2 r e s e a r c h i n gt h er e l a t e dt h e o r i e so fd 宰a l g o r i t h ma n dg a m et h e o r yo fm i x e d s t r a t e g y a n dp r e s e n tad 霉p r i n c i p l e b a s e dd y n a m i ce q u i l i b r a t e dr e s t o r a t i o ns t r a t e g yi n a s o n c o n s i d e r i n g o ft h e p a t h c o s ta n dt h e o c c l l p 锄c y o fw a v e l e n g t h c o m p r e h e n s i v e l y u s i n gg a m et h e o r yo fm i x e ds t r a t e g yt os o l v en a s he q u i l i b r a t i o n b e t w e e no c c u p a n c yo fw a v e l e n g t ha n dp a t h c o s t a c c o r d i n gt h i s t h e e v a l u a t i o n f u n c t i o no fd a l g o r i t h mi sc o n s t r u c t e dd y n a m i c a l l y f o re n s u r i n gam o r ee q u i t a b l e d i s t r i b u t i o no fn e t w o r kr e s o u r c e si n t h ep r o c e s so fd y n a m i cc h a n n e lr e s t o r a t i o n c o m p a r e dw i t ht r a d i t i o n a lr e s t o r a t i o ns t r a t e g yb a s e do ns h o r t e s tp a t ha n ds i m p l e d y n a m i cr e s t o r a t i o ns t r a t e g y t h i sa l g o r i t h mc a l la c h i e v eh i g h e rr e s t o r a b i l i t ya n dl o w e r r e s o u r c eo c c u p a n c y 3 a c c o r d i n gt ot h ei d e ao f t h er e s t o r a t i o ns t r a t e g y t h ea r t i c l ed e t a i l e d l ya n a l y z e d e s i g na n dc a r r yo u tt h ep r i n c i p l eo fe q u i l i b r a t e dd 枣a l g o r i t h m w h i c hi n c l u d e c o n s t r u c t i n gd a t as t r u c t u r ea n dm o d e lo fm a t h e m a t i c f l o wd e s i g na n dc a p a b i l i t y a n a l y s i s e t c a g a i n s tt h ed i s a d v a n t a g eo fs l o wc o n v e r g e n c ef o u n d e di ns i m u l a t i o n e x p e r i m e n t d u et os l o v i n gn o n l i n e a re q u a t i o n so fn a s he q u i l i b r i u m t h ea r t i c l ed e s i g n am e t h o dw h i c hc o m b i n i n gn e w t o ni t e r a t i v em e t h o d 丽 ll e a s ts q u a r em e t h o dt os o l v e n o n l i n e a re q u a t i o n so fn a s he q u i l i b r i u m i tc a l lb ep r o v e dt oa c c e l e r a t ec o n v e r g e n t s p e e do ft h ea l g o r i t h mb ys i m u l a t i o n 4 u s i n gc 群a n dm a t l a bi n t e g r a t e dp r o g r a m m i n g t h e a r t i c l e d e s i g n s i m u l a t i o ns y s t e mo fr e s t o r a t i o ns t r a t e g yi n d e p e n d e n t l y a n dt e s tt h ep e r f o r m a n c eo f e q u i l i b r a t e dd 牛a l g o r i t h mb ys i m u l a t i n ga c t u a ln e t w o r ke n v i r o n m e n t i na d d i t i o n w e c o m p a r ee q u i l i b r a t e dd 木a l g o r i t h mw i ms h o r t e s tp a t ha l g o r i t h ma n ds i m p l ed 奉 a l g o r i t h mw h i c hd e s i g n e ds e p a r a t e l y i ts h o w st h a tt h eb l o c k e dr a t e r e s t o r a b l er a t ea n d r a t eo fr e s o u r c eo c c u p a n c yo fe q u i l i b r a t e dd 宰a l g o r i t h m a r ea l lo b v i o u s l yb e t t e rt h a n o t h e r c o m p a r a t i v ea l g o r i t h m s a n dt h ep e r f o r m a n c eo ft i m e o fe q u i l i b r a t e d d 宰 a l g o r i t h mc a l ls u f f i c i e n t l yf i tt h er e q u e s to fr e s t o r a t i o nt i m ei na s o n 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 d 宰a l g o r i t h m n a s he q u i l i b r i u m r w a i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借阅 本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 保密口 在年解密后适用本授权书 不保密邑 学位论文作者签名 钇红 岬年 z 其e s 日 指导教师签名 聋1 乃d 7 年 猬f 妇 独创性声明 本人郑重声明 所呈交的学位论文 是本人在导师的指导下 独 立进行研究工作所取得的成果 除文中已注明引用的内容以外 本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果 对本文 的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本 人完全意识到本声明的法律结果由本人承担 学位论文作者签名 日期 如声 二月 知阳 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 随着计算机和i n t e m e t 的日益普及 用户对口数据业务尤其是宽带口业务的 需求呈爆炸性增长 据统计 2 0 0 6 年我国通过专线或宽带上网的计算机数量已达 4 1 2 0 万台 l 而传统的基于同步数字序列 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 w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g 系统的静态光传送网 o t n o p t i c a lt r a n s p o r tn e t w o r k 由于业务配置时间长 实时业务提供能力差 网络资 源利用率低 缺少先进的保护恢复和路由选择功能 不能提供个性化服务等问题 已越来越不能适应用户数据业务对网络的需求 在此背景下 自动交换光网络 a s o n a u t o m a t i cs w i t c h e do p t i c a ln e t w o r k 应运而生 a s o n 是能够智能化地自动完成光网络交换连接功能的新一代光传送 网 所谓自动交换是指 在网络资源和拓扑结构的自动发现基础上 调用动态智 能选路算法 通过分布式信令处理和交互 建立端到端的按需连接 同时提供可 行及可靠的保护和恢复机制 实现故障情况下连接的自动重构 在 u t 的文献 中将a s o n 描述为 通过能提供自动发现和动态连接建立功能的分布式 或部 分分布式 控制平面 o t n 或s d h 网络之上 可实现动态的 基于信令的策略 驱动控制的一种网络 与传统的光传送网相比 a s o n 突破性地引入了更加智能化的控制平面 使 用接口 协议以及信令系统 直接在光层引入以口为核心的智能控制技术 将p 的效率 s d h 的保护能力以及w d m 的容量通过分布式网络管理系统有机地结合 在一起 从而赋予了传统光网络更多的智能控制 a s o n 不仅提高了网络资源的 利用率 提供了更加完善的保护和恢复功能 同时也增强了网络的互操作性和可 扩展性 它不仅可以适用于当前的环形 线性和点到点的网络拓扑结构 更适用 于连通度更高的网状拓扑结构 a s o n 体系结构的特点主要表现在三个平面 即 传送平面 t p t r a n s p o r tp l a n e 控制平面 c p c o n t r o lp l a n e 和管理平面 m p m a n a g e m e n tp l a n e 三个接v i 即连接控制接口 c c i c o n n e c t i o nc o n t r o l l e r i n t e r f a c e 网络管理接口a n m i a n e t w o r km a n a g e m e n ti n t e r f a c e a 和网络 管理接口t n m i t n e t w o r km a n a g e m e n ti n t e r f a c e t i 以及所支持的三种连接 江苏大学硕士学位论文 类型 即永久交换连接 p c p e r m a n e n tc o n n e c t i o n 软永久连接 s p c s o f t p e r m a n e n tc o n n e c t i o n 和交换连接 s c s w i t c h e dc o n n e c t i o n 上 a s o n 的体 系结构如图1 1 所示 图1 1a s o n 体系结构示意图 自1 9 9 9 年a s o n 概念的提出后 智能光网络技术得到众多国际标准化组织 设备制造商和运营商的极大关注 短短的几年中 a s o n 的研究取得了巨大的进 展 目前国际上诸多标准化组织 如国际电信联盟 r i u t 互联工程任务组 t f 和光互联网论坛 o 等组织都在对自动交换光网络的相关技术和标 准规范进行研究 并起草了有关a s o n 的许多标准 国内外许多网络设备制造商 也正在加紧对a s o n 设备的研发工作 许多国际知名的设备制造商 如n o r t e l s y c a m o r e c i e n a l u c e n t c i s c o a l c a t e l 等公司均制造出了支持a s o n 的智能 设备 国内的中兴 华为 烽火通信也在这方面投入了大量的研究 并研发出了 相关产品 目前 国内外的主要研究计划和试验网络有欧盟资助的i s t 的l i o n 2 1 欧洲电信研究与开发组织e u r e s c o m 的f a s h i o n 3 以及我国于2 0 0 3 年启动的 国家8 6 3 计划重大专项3 t n n e t 4 1 一些著名电信运营商也在一直关注着a s o n 的 发展 并积极投身于a s o n 的研究与应用 a t t 早在2 0 0 2 年就开通了覆盖全 美的智能光网络 a s o n 的发展代表了智能光网络的主流方向 是下一代光网络 n g n n e x tg e n e r a t i o nn e t w o r k 的重要组成部分 2 江苏大学硕士学位论文 网络生存性 s u r v i v a b i l i t y 是指网络在经受各种故障后仍能维持可接受的业 务传送质量的能力 5 1 光网络的生存性技术通常分为保护和恢复两种 其中自动 保护倒换 a p s a u t o m a t i cp r o t e c t i o ns w i t c h i n g 和自愈环 s h r s e l f h e a l i n gr i n g 是目前较常用的保护方法 但在大规模的网状网 如 a s o n 中 a p s 和s h r 会消耗大量的网络资源 同时也对网络规划带来极大困难 因此更好的解决方案 是使用动态恢复策略 而a s o n 控制平面的引入为高效快速的网络动态恢复研究 提供了有利的条件 光网络的恢复 r e s t o r a t i o n 是指在工作连接发生失效的情况下 不是通过 预先建立的冗余保护通道 而是按照一定的优化算法 依据网络现有的空闲资源 为其选择一条合适的替代通道来恢复受损业务 6 a s o n 的恢复算法是实现a s o n 生存性 s u r v i v a b i l i t y 的关键技术之一 在光网络的恢复算法中 路由恢复和资源调度不仅需要了解线路或者通道是 否正常 还需要了解各链路和通道的资源使用情况 基于这些信息 才能够依据 一定的优化算法对资源进行合理调配 所依据的优化算法通常为动态路由和波长 分配 瞅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 7 算法 由于动态r w a 问题是 n p 完备问题 因此一般将其拆分为路由选择和波长分配两个子问题求解 1 0 1 目 前这些算法已经得到了较广泛的应用 但由于他们基本采用最短路径路由或链路 最小负载路由策略 随着网络环境的日益复杂 已逐渐无法满足a s o n 的灵活 快速 多样化的恢复要求 另外 由于r w a 问题本身是一个不可分割的整体 把 r w a 分开考虑势必难以得到全局较优解 因此 c h i e n 和s u b m t a 提出了分层图 模型 m g m m u l t i l a y e rc r a p hm o d e l 1 1 将r w a 问题转化为纯路由问题求解 目前 在该模型中的路由选择通常是简单地采用最短路径算法 1 2 1 3 一些研究 者在分层图模型的基础上采用蚁群算法 遗传算法等仿生算法求解r w a 问题 1 4 1 5 可以得到较优解 但分层图模型使网络规模扩大了阿i 倍 而仿真算法的收敛 速度较慢 这无疑增加了业务分配的计算时间 不适合在动态业务频繁的大规模 网络环境下使用 针对上述问题 本文利用博弈论原理将网络中的各线路代价与当前状态下的 波长占用情况综合考虑 并结合d 毒算法 1 6 1 7 这种动态环境下的启发式 h e u r i s t i c 搜索算法 提出了一种基于d 毒思想的动态均衡恢复策略 甩以智能 快速 高效 地解决大规模网络环境下a s o n 的故障恢复问题 3 江苏大学硕士学位论文 1 2 研究意义 全球数据业务的爆炸式增长要求光传送网提供更加灵活的网络指配和高效快 速的网络恢复能力 而由于网络技术的快速发展 使得更多的业务量集中到更少 的网络元素上 一根光纤的断裂或一个节点的失效将造成经过它的所有光路的失 效 从而引起大量连接业务的中断 据美国f c c 联邦通信委员会 报告 每两 天就有一次影响3 0 0 0 0 客户的网络故障发生 而故障修复的平均时间是5 1 0 小 时 传输容量达 i b i 怕的单根光纤的失效 将影响1 2 0 0 万对以上的电话业务 随着人民生活水平的提高和信息化的普及 社会经济生活及个人日常生活越来越 依赖于通信网络 一旦网络出现故障而不能在短时间内排除 将会带来严重的后 果 不仅会造成巨大的经济损失 严重者甚至可能会引起社会的动荡 2 0 0 6 年1 2 月2 6 日 由于我国台湾南部海域发生地震 造成中美海缆 亚太 1 号等数条国际海底通信光缆发生中断 导致我国大陆至台湾地区 美国 欧洲 等方向的通信线路大量中断 互联网大面积瘫痪 除我国外 日本 韩国 新加 坡等国互联网服务均受到影响 在中国已经加入w t o 的今天 国内电信市场的垄断局面己被打破 随之而 来的激烈的市场竞争使得各电信运营商不得不考虑如何降低的运营成本并对客户 提供更好的服务质量 要在低成本运作的同时对客户提供优质可靠的通信服务 规划设计具有快速智能恢复能力的高生存性网络显得尤为重要 此外 光网络目前正由点到点 环网逐步向a s o n 网状网演变 网络拓扑结 构的变化更增加了网络故障情况的复杂性 使得传统的保护手段难以满足要求 因此 设计出能综合各种优化目标 如 恢复时间 恢复率 资源占用率等 的 a s o n 动态恢复算法就显得尤为重要 综上所述 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 传送平面的故障 提出一种基于d 木思想的动态均衡恢复a s o n 恢复策略 并设计了分布式解决方案 该策略综合考虑了故障情况下业务恢复的时效性和网 络空闲资源的合理分配 以提高a s o n 网状网的生存性 论文的主要研究内容包 括以下几个方面 1 研究分析a s o n 恢复的相关问题及其影响因素 相对于传统光网络 a s o n 的最大特点在于从传统的传输节点设备和管理系 统中抽象分离出了控制平面 使网络的分布式智能成为可能 本课题在剖析 a s o n 的控制平面技术 路由技术 生存性技术的基础上 根据a s o n 中恢复问题的特 点 探讨了a s o n 中的动态r w a 技术 并确定了恢复问题应该考虑的优化目标 及其影响因素 为后文设计基于d 堆思想的动态均衡a s o n 恢复策略确立了目标 2 研究和设计基于d 思想的动态均衡a s o n 恢复策略 在广泛研究a s o n 恢复相关问题以及深刻理解d 掌算法和博弈论相关知识的 基础上 首次将d 串算法的思想引入到光网络恢复问题中 利用d 辜算法快速智能 适用于未知环境以及分布式的特点 并结合网络的各线路代价和当前状态下的波 长占用情况 运用博弈论原理动态构造d 幸算法的估计函数 将路由选择和波长分 配的统一考虑 提出了一种基于d 牛思想的动态均衡a s o n 恢复策略 并通过建 立相关数学模型 从理论上对该算法的复杂度 收敛性进行了分析 3 构建算法仿真平台并对算法性能进行测试 模拟网络环境 设计和构建基于a s o n 恢复算法的仿真平台 运用不同网络 拓扑结构和各种参数对所设计的算法进行仿真实验 并通过与其他恢复算法的比 较 分析测试结果并调整算法参数 以优化算法性能 通过仿真结果可以看出 本文提出的算法在收敛时间 资源占用率 业务恢复率等主要性能指标方面上均 可达到较好的效果 4 算法的分析和改进 在理论分析和仿真实验的基础上 分析影响算法性能的主要因素 并针对仿 真实验时发现由于求解纳什均衡非线性方程组而造成算法收敛较慢的不足 对算 法进行了改进 设计了一种结合n e w t o n 迭代法和最小二乘法求解纳什均衡非线 5 江苏大学硕士学位论文 性方程组的方法 实验证明 此方法可以大大提高算法的收敛速度 1 4 论文结构安排 本文共分六章展开叙述 在本章中 介绍了本文的研究背景 对a s o n 的概念 结构以及光网络恢复 问题的研究现状作了简要说明 阐述了课题的研究意义和研究的主要内容及关键 技术 最后说明了本文的行文结构安排 第二章 首先 介绍了a s o n 中最有特色的控制平面的基本结构及其控制功 能 接着 在研究了a s o n 的路由体系结构和特点的基础上 进一步对a s o n 中 的生存性问题进行了阐述 并着重分析了a s o n 的恢复机制及其性能 最后 针 对a s o n 的恢复算法问题 研究了a s o n 中的动态r w a 技术 并对影响恢复算 法设计的波长转换约束 波长连续性约束 路由模式 控制信令等问题进行了简 单叙述 第三章 首先 在分别阐述了d 宰算法的基本思想和博弈论的相关背景知识的 基础上 对基于d 术思想的a s o n 动态均衡恢复策略进行了详细的描述和分析 给出了算法的主要数据类型 波长一代价均衡的实现方法 算法的数学模型 并 提供了具体的算法设计流程以及算法分布式实现的方案 接着 对算法的性能分 别从时间复杂度 空间复杂度以及收敛性三方面进行了详细的分析 最后 针对 算法时间性能上的不足给出了具体的改进措施 第四章 主要描述了利用饼和m a t i a b 混合编程方法构建的算法仿真平台 的基本结构 构建方法和功能实现 简要介绍了删和m a t l a b 混合编程技术 实验网络拓扑以及仿真系统的构成和运行流程 详细分析了仿真系统主要模块的 实现方法 并提供了关键算法的伪代码以供参考 第五章 在仿真平台上对实验网络拓扑结构进行了多种测试 举例显示了均 衡d 幸算法的仿真结果 分析了调节因子口对算法的影响 重点在阻塞率 恢复率 平均代价 资源占用率等方面与其他算法进行了比较 同时 比较了算法在波长 选择和波长转换网络中的性能 最后 根据算法的改进方案 对改进后的算法性 能进行了测试分析 第六章 总结全文 给出结论 并且叙述了本领域内有待于进一步研究和探 讨的问题 6 江苏大学硕士学位论文 第二章a s o n 相关技术分析 2 1a s o n 的控制平面技术 控制平面是a s o n 的核心层 它负责完成网络连接的动态建立以及网络资源 的动态分配 这也是a s o n 区别是于传统光网络的特点所在 控制平面的引入赋 予了a s o n 网络以智能性和生命力 给a s o n 带来了一些新特点 能实现流量工程 使网络资源能够动态分配给业务路由 能根据网络资源的实时使用情况 动态地进行故障恢复 支持各种新的业务类型 如带宽按需分配和虚拟专用网 v p n 具有快速的服务指配功能等 2 1 1 控制平面的基本结构 a s o n 中控制平面采用的是基于口的信令技术 控制平面的信令 路由协议 都是沿用原有的口网络协议 并在此基础上做了相应的扩展以适应在光网络中的 应用 可以说 a s o n 控制平面实际上就是一个以数据通信网 d c n d a t a c o m m u n i c a t i o n sn e t w o r k 为其物理支撑的用于控制传送平面设备的p 网络 息 出 图2 1a s o n 控制平面节点功能组件 控制平面由独立的或者分布于网元设备中 通过信令通道连接起来的多个控 制节点组成 而控制节点又由路由 信令和资源管理等一系统逻辑功能模块组成 在i i 玎 t 的建议中 把控制平面节点的核心功能组件分成六大类 连接控制器 c c c o n n e c t i o nc o n t r o l l e r 路由控制器 r c r o u t i n gc o n t r o l l e r 链路资源 管理器 l r m l i n kr e s o u r c em a n a g e r 流量策略 1 1 p t r a f f i cp o l i c i n g 呼叫 7 江苏大学硕士学位论文 控制器 c a u c c a l lc o n t r o l l e r 和协议控制器 p c p r o t o c o lc o n t r o l l e r 它们 之间的相互关系如图2 1 所示 连接控制器 c c 是整个节点功能结构的核心 它负责协调链路资源管理器 路由控制器以及对等或者下层连接控制器 以便达到管理和监测连接的建立 释 放和修改己建立连接参数的目的 路由控制器 i 圯 响应来自连接控制器对建立连接所需路由信息的请求 这 种信息可以是端到端的 也可是基于下一跳的 此外 还要响应用于网络管理的 拓扑请求信息 链路资源管理器 l r m 主要负责子网点池 s n p p s u b n e t w o r kp o i n tp 0 0 1 链路的管理 包括对子网点 s n p 链路连接进行分配和拆除 并提供拓扑和状 态信息 流量策略 t p 组件是策略端口的子集 其作用是检查输入的用户连接是否 按照约定的参数传输业务 当一个连接违反约定的参数时 皿就采取措施来纠正 上述情况 呼叫控制器 c a u c 的作用是完成连接建立开始的过程 有两种类型的呼叫 控制器组件 主n q 被叫方呼叫控制器和网络呼叫控制器 在一个呼叫过程中 主 叫控制器可通过一个或多个中间媒体网络呼叫控制器与被叫部分协调 协议控制器 p c 的作用是把上述控制组件的抽象接口参数映射到消息中 然后通过协议承载的消息完成接口的互操作 呼叫和连接是a s o n 实现自动交换功能最为关键的两个过程 当客户向网络 发起连接请求时 交换连接开始时由c a l l c 完成呼叫过程 当接收到一个链路连 接分配请求时 由l r m 决定是否还有足够的空闲资源以建立一条新连接 r c 组 件为l r m 提供所负责区域内的连接路由信息 皿组件检查进入的用户连接是否 根据约定参数来传输业务 p c 用承载方式完成各接口的通讯 各个组件协调工作 达到连接的自动建立 修改 维持及释放 2 1 2 控制平面的控制功能 一个设计良好的控制平面体系结构在支持更快和更精确的电路建立的同时 还应该为业务商提供以于其网络更好的控制功能 1 控制平面的自动配置功能 电信业已经认识到对高带宽链路自动配置的需要 基于运营商现有的基础设 8 江苏大学硕士学位论文 施 开发新产品的潜能和今后的策略 可选取三种不同的模型 软永久链路模型 s p cm o d e l 该模型中 终端系统 客户 和网络之 间没有网管或控制的互操作 居于控制平面上方的网管系统用于连接两端的节点 通信 用户网络接口模型 u mm o d e l 该模型中 服务由终端系统发起 但 终端系统并不了解光网络拓扑和资源状况 只是简单地要求建立或删除连接 对等模型 该模型中 连接发起者需要完全了解拓扑信息 通过这些信息 发起者可以按照一系列规则选取通过光网络的路由 2 控制平面的信令协议和分布式网络智能 信令网借助在用户与网络之间以及不同网络实体之间传递与业务相关信息的 方式来支持控制平面 a s o n 信令网应基于共路信令 它与用户通路的联系有三 种主要方式 随路方式 非随路方式和准随路方式 1 8 1 随路方式指两个网元之间 与业务量有关的信令信息直接在两个网元的信令通路上传递 非随路方式指两个 网元之间的信令信息可以随时间和网络条件在不同的信令通路上选路 而业务信 号直接在两个网元间选路 而准随路方式则是在随路方式上 增加了几个信令通 道以供选择 利用非随路方式可以极大改善网络弹性 在信令某些信令链路失效 的情况下也不会影响相关业务通路 光网络的分布式智能是把网络智能分布到网元上 而不是采用网管系统集中 对网元配置形成的智能 它主要体现在网络拓扑发现 电路自动配置 网络保护 恢复等方面 具有网元能直接感知网络物理情况 实施速度快 网络生存性强等 优点 光网络的分布式智能完全依赖于光路由和信令协议 与口路由不同的是 光路由不是路