（计算机应用技术专业论文）基于信息栅格的网络重构技术研究.pdf

沈阳理一f 大学硕士学位论文 摘要 所谓信息栅格是指全球互连的端到端的信息能力、相关程序及人员的集合， 它对用户所需的信息进行收集、处理、存储、分发和管理。信息栅格网络是把所 有不同的信息系统部分连成一个由众多网络构成的公共网，使信息能及时流畅地 流向任何需要它的位置。 信息栅格中的网络不单指通常的计算机网络，其已经扩展成为了包含传感器、 网络交换机、路由器、光端机等各种设备的网络，因此对信息栅格中各种网络进 行高效的管理已成为一项迫切的任务。网络重构作为网络管理的一项关键技术能 够提高网络的性能和服务质量，保证信息的安全和可靠传输。网络重构技术能够 对故障的网络进行快速重构，恢复网络的逻辑结构，保证网络通信的正常进行。 根据信息栅格网络的系统特性、网络结构、应用环境、使用目的及需求，对 网络重构进行了研究。结合信息栅格体系结构的特点分析了当前常用的网络重构 技术，以重路由为研究重点，在原有的区域路由协议基础上提出了一种基于信息 栅格的增强型区域路由算法，对于分群后的信息栅格实现了网络重构，并满足了 对节点资源和链路资源低占用的要求；解决了原有算法使网络性能降低并且不适 合信息栅格的分层分布式分群体系结构的问题。 在算法的理论基础上，设计并实现了仿真实验系统，对网络运行机制进行了 有效的模拟，性能分析表明改进后的算法从用户数据传输业务角度出发，提高了 分组的成功传输率，同时降低了端到端的平均时延。 关键词：信息栅格；网络重构；重路由；群 沈阳理_ 丁大学硕士学位论文 a b s t r a c t t h ei n f o r m a t i o ng r i dr e f e r st ot h eg l o b a li n t e r c o n n e c t e de n d - - t o e n di n f o r m a t i o n a b i l i t y , t h ec o r r e l a t e dp r o c e d u r ea n dp e r s o n n e l ss e t ，w h i c hc o l l e c t s ，d i s p o s e s ，s t o r e s ， d i s p a t c h e sa n dm a n a g e st h ei n f o r m a t i o nu s e r sn e e d i n f o r m a t i o ng r i di s an e t w o r k c o m p o s e db ya l lk i n d so fi n f o r m a t i o ns y s t e m sw h i c hc a l ld i s p a t c hi n f o r m a t i o nt o a n y w h e r en e e d e d t h ei n f o r m a t i o ng i l dr e f e r sn o to n l yt ot h ec o m m o nc o m p u t e rn e t w o r k ，b u ta l s ot o t h eo n e st h a ti n c l u d e ss e n s o r s ，n e t w o r ks w i t c h e s ，r e u t e r s ，a n df b e ro p t i ct r a n s m i s s i o n e q u i p m e n t s s ot h ee f f e c t i v em a n a g e m e n to fi n f o r m a t i o ng i l di ss t r o n g l yn e e d e d 。a sa k e yt e c h n o l o g yo ft h en e t w o r km a n a g e m e n t ，n e t w o r kr e c o n f i g u r a t i o nc a ni m p r o v et h e n e t w o r kp e r f o r m a n c ea n dq u a l i t yo fs e r v i c e ，s oa st om a k eas e c u r ea n dr e l i a b l e i n f o r m a t i o nt r a n s m i s s i o n t h en e t w o r kr e c o n f i g u r a t i o nt e c h n o l o g yc a nc a l t yo naf a s t r e c o n f i g u r a t i o nt ot h eb r e a k d o w nn e t w o r kt or e s t o r et h en e t w o r k sl o g i c a lo r g a n i z a t i o n ， a n dg u a r a n t e et h en e t w o r kw o r k sn o r m a l l y t h ep a p e rd o e ss o m er e s e a r c h e so nt h en e t w o r kr e c o n f i g u r a t i o nc o n s i d e r i n gt h e c h a r a c t e r i s t i c s ，n e t w o r ks t r u c t u r e ，a p p l i c a t i o ne n v i r o n m e n ta n dd e m a n d so fi n f o r m a t i o n g i l d a i d e ra n a l y z i n gt h ef o r m e ra l g o r i t h m ，a ne n h a n c e dz o n er o u t i n ga l g o r i t h mi s p r e s e n t e d ，w h i c h b a s e so nt h e r e r o u t i n gt e c h n o l o g y i t c a ni m p l e m e n tt h e r e c o n f i g u r a t i o no fi n f o r m a t i o ng r i d ，w h i c hi sp a r t i t i o n e di n t os e v e r a lc l u s t e r s t h e a l g o r i t h mt a k e sl e s sn o d ea n dl i n kr e s o u r c e st h a nt h ef o r m e ra l g o r i t h mw h i c hc a nn o t s u i tf o rt h ei n f o r m a t i o ng r i d sh i e r a r c h i c a la n dd i s t i l b u t e ds t r u c t u r eb a s e do nc l u s t e r a c c o r d i n gt ot h ea l g o r i t h mp r e s e n t e df o r m e r , as i m u l a t i o ns y s t e mi sd e s i g n e da n d i m p l e m e n t e d t h er e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mc a ne n h a n c et h er a t eo f s u c c e s s f u lp a c k e tt r a n s m i s s i o na n dr e d u c et h ee n d t o e n dd e l a yo nt h ea s p e c to fu s e r s d a t at r a n s m i s s i o n 沈阿1 理i ：人学硕十学位论文 k e yw o r d s ：i n f o r m a t i o ng r i d ；n e t w o r kr e c o n f i g u r a t i o n ；r e r o u t i n g ；c l u s t e r 沈阳理工大学 硕士学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本 人独立完成的。有关观点、方法、数据和文献的引用已在文中指出， 并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任 何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要 贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本 声明的法律结果由本人承担。 售者p ：驾垡尹日 日期 ：d 留年弓月7 日 学位论文版权使用授权书 本学位论文作者完全了解沈阳理工大学有关保留、使用学位论文 的规定，即：沈阳理工大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权沈阳理工 大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：榭指导教师签名：( 张附。 1 3 期：口7 、孑f 7 日 期：d 乡；。，夕 第1 章绪论 1 1 课题背景 第1 章绪论 信息栅格是构筑在互联网上的一组新兴技术，它将高速互联网、高性能计算 机、大型数据库、传感器、远程设备等融为一体，为科技人员和普通百姓提供更 多的资源、功能和交互性。因此，可以通过信息栅格实现计算资源、数据资源、 知识资源、专家资源的全面共享，从而把整个因特网整合成为一台巨大的虚拟的 超级计算机。 信息栅格是实现网络中心站的物质基础，是赢得信息优势的关键所在。信息 栅格的目标就是获取一体化水平及联合程度更高的指挥、控制、通信和计算机能 力。 信息栅格是新时期、新战略、新思想下的产物，它有力地促进了世界新军事 变革的发展。信息栅格网络只在概念中提出，其运行方式和通信方式类似于移动 自组网网络。这种网络是一组带有无线收发装置的移动终端组成的一个多跳的临 时性自治系统，网络中的节点相互作为邻居的路由器，通过节点转发实现节点间 的通信。网络中的节点可以动态、频繁地加入或者离开网络，不需要事先通知， 也不会中断其他节点间的通信。网络中的节点可以高速移动，从而使节点群快速 变化。信息栅格网络是一种可以快速建立，不需要预先存在固定的网络底层构造 的网络体系结构，一般采用分布式控制结构，即完全分布式网络结构和分层分布 式控制结构。本文借鉴自组网的研究成果来研究信息栅格网络，能够更好的对网 络进行管理控制。 考虑到网络各节点的自治性、扩充性、抗毁性和开放性问题，信息栅格的特 点主要有以下几点。 ( 1 ) 动态变化的拓扑结构 网络节点的运动具有很大的随机性，加上无线发信装置发送功率的变化、无 沈阳理1 ：大学硕十学位论文 线信道间的互相干扰以及地形等因素对无线链路的影响，网络拓扑结构可能随时 发生变化，并且这种变化的方式和速度难以预测。 ( 2 ) 分布式网络结构 不需要基站等核心通信设施的支持，各节点地位平等，节点可以随时加入和 退出网络。与集中式网络结构相比，具有很强的鲁棒性和抗毁性。 ( 3 ) 多跳传输方式 分组采用多跳传输方式，经中间节点转发，到达目的节点。可有效扩展网络 的覆盖范围。 ( 4 ) 移动节点局限性 移动节点具有小巧、便携的特点，但一般c p u 计算能力低、内存小，这限制 了网络和应用程序的设计。特别是许多移动节点靠电池等易耗能源供电，能量有 限。 ( 5 ) 网络安全性低 与有线通信相比，通信更容易遭受被动窃听、主动入侵、拒绝服务、伪造等 网络安全攻击。 ( 6 ) 网络的自治性 信息栅格网络相对于常规网络而言，最大的好处就是可以在任何时刻、任何 地点不需要现有网络基础设施( 包括有线和无线网络) 的支持，快速构建起一个 移动通信网络。 ( 7 ) 非对称信道 由于采用无线信道通信，受地形环境、发射功能和接收灵敏度等因素的影响， 可能产生单向无线信道。 ( 8 ) 带宽有限，容量可变的无线链路 由于信息栅格网络采用无线传输技术作为底层的通信手段，而无线信道本身 的物理特性使得它所能提供的网络带宽相对于有线信道要低得多。除此之外，考 虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰、信道间的干扰等多种 因素，移动节点最终可得到实际带宽远远小于理论上的最大带宽值。 在信息栅格中，以上的这些特点必定会造成网络中拓扑不断地发生着改变。 对于信息栅格本身的要求，在可靠性和安全性方面必须包括如下几方面的内容。 第1 章绪论 ( 1 ) 及时发现系统本身的故障能力； ( 2 ) 及时发现人为的入侵、破坏和信息窃取行为的能力； ( 3 ) 发现问题后的快速反应能力； ( 4 ) 在系统受损情况下，如何对系统进行重新优化，以便最大限度降低负面影 响的能力； ( 5 ) 在信息系统遭到破坏后，恢复以及确定数据合法性的能力； ( 6 ) 终止被怀疑已泄密的通信线路的能力； ( 7 ) 在网络内部建立仅包括某些成员或不包括某些成员的子网的能力。 由此可以看出，必须研究针对于信息栅格网络的重构机制“。3 ，、方式、方法和 策略来保证网络的可靠、安全和有效地运行。 本研究由国家“十一五 预研项目资助，通过分析信息栅格的特点，在其分 层分布式分群体系结构的基础上，重点研究信息栅格的网络重构技术。在分析原 有算法的基础上，本文提出一种改进网络重构算法，实现了网络重构并满足了对 节点和链路资源低占用的要求；解决了在节点数目众多时网络重构速度慢、网络 资源占用率高的问题。 1 2 国内外研究现状 现今国内外对于网络重构主要是基于网络自愈技术及网络生存性等的相关研 究。 网络自愈技术的研究是在1 9 8 7 年由加拿大的w g r o v e r 提出的，前3 年主要 集中在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 y 同步数字体系) 自愈技术方面，a t m 自恢复算法m 5 ，的研究始于1 9 9 0 年，目前仍处于探索和实验中；i t u 也正在积极开 展这方面的研究工作，并已初步制定了有关支持和保护环形结构的s d h 建议初稿 ( g 8 4 1 ) 和环互连标准( g 8 4 2 ) ，并于1 9 9 7 年1 2 月定稿。自愈环目前己经实用 化，对于网状网的分布式自愈算法有几个实验室产品，分别是：f l o o d i n g ， f i t n e s s ，t r a n s ，t p l r p 和d s s h a 。 与此同时，美国、欧洲、日本等电信公司的研究机构也正致力于网络生存性 方面的研究。欧共体的r a c e 计划为此设立了i m m u n e 项目( 专门研究宽带网的 端到端生存性，1 9 8 8 1 9 9 6 ) ，从1 9 9 4 年到1 9 9 6 年，已先后有6 个研究机构参；0 1 - 1 沈刚理 大学硕十学位论文 b t l a b ( 英国) 、i m e c 大学研究中心( 比利时) 、p t t 研究中心( 荷兰) 、a l c a t e l 标准机制( 西班牙) 、p h i l i l 研究实验室( 德国) 和a l c a t e lb e l l ( 比利时) 。1 9 9 6 年 r a c e 计划结束，i m m u n e 项目则由a c t s 计划a c 2 0 5 p a n e l 项目继续研究工 作，而尤以i m e c 大学研究中心的信息技术系和b tl a b 的研究最为活跃。美国 n s f 资助的n e t w o r kd e s i g na n dt r a f f i cr e c o v e r yp r o c e d u r e sf o rs u r v i v a b i l i t yw i d e a r e ap a c k e tn e t w o r k s ( 9 5 年8 月至9 8 年6 月) ，主要侧重网络生存性的两个方面： 拓扑设计模型和算法、网络恢复算法及其管理。另一个由d a r p a r a t o 资助的 c u s m o s 项目( 9 7 年6 月至2 0 0 0 年6 月) ，主要研究多层网络生存性设计及综合 控制策略并建立实验，最近开始研究网络生存性问题。 在网络生存性的研究过程中，提出了大量的网络重构算法。r r o m 和 n s h a c h a m 提出了双环令牌环局域网的重构算法哺，。c h a k r a b o r t 等提出了由于链路 失效导致拓扑改变的双环网的重构算法n ，。在研究f d d i 网络生存性时，g a g r a w a l ， s k a m a t 和w z h a o 等提出了基于f d d i 的可重构网络结构f b r n t “，以及发生故 障时找到最大可用带宽的重构算法旧】。i m e c 大学的m a r i op i c k a v e t 和p i e td e m e e s t e r 在研究s d h 网络生存性时提出了网络重构的启发式算法“。在n s f 资助下i l i a b a l d i n e 研究w d m 网络时，提出了旨在负载均衡和调整收发机数量最小的广播 w d m 网络重构算法，。 国内从事这方面研究以北京邮电大学通信网国家重点实验室最早，最初是中、 比合作项目“a t m 网络生存性策略”，然后是于2 0 0 0 年底结束的国家自然科学基 金项目“b i s d n 网络生存性策略的研究。总体来说，我国在这个领域的起步较 晚，与其他先进国家相比还有很大的差距。 1 3 论文研究内容 本文研究的主要内容有： ( 1 ) 增强型区域路由算法的研究及验证 在分析网络重构技术的基础上，针对于重路由进行深入研究。在分析区域路 由协议的基础上，提出了一种基于信息栅格的增强型区域路由算法。该算法在信 息栅格分群的体系结构基础上，采用以群为单位，群内外采用不同的路由策略。 实验证明，在相同的网络结构中，与区域路由协议相比改进的增强型区域路由算 4 第1 章绪论 法在时延和分组成功传输率方面都有所改进。 ( 2 ) 网络重构系统的设计与实现 根据本文提出的增强型区域路由算法，设计实现了网络重构系统。本系统在 信息栅格分群的基础上，对网络中需要通信的节点进行选路。在网络中实现了群 内路由和群问路由两种不同的选路算法；群内路由算法的使用大大减少了路由寻 找所需的时间，同时在一个群内通信的信息量占较大比例时，各个群之间可以互 不干扰地进行通信。 1 4 论文结构 本文首先介绍了此课题提出的背景，分析了国内外网络重构技术的研究现状。 本文第二章中先分析了信息栅格的体系结构和当前的网络重构的三种关键技 术即冗余备份、自愈环技术和重路由。并将网络重构的重点研究方向定为重路由。 第三章在网络重构中以重路由技术为研究方向，根据信息栅格的体系结构特 点，分析了区域路由协议。区域路由协议涵盖了主动路由协议的特点和按需驱动 路由协议的特点，是一种较为适合信息栅格网络的路由协议。但信息栅格网络结 构和特点也使区域路由协议有其不适应之处，基于此，本文在区域路由协议思想 基础之上根据信息栅格的结构和特点提出了一种增强型区域路由算法，并通过性 能分析证明了在信息栅格网络中增强型区域路由算法的优势。 第四章在信息栅格的仿真平台的基础上，对本文所提出的算法进行了设计与 实现。 最后是对本文的总结，并提出今后的工作安排。 沈| j 1 1 理t ：人学硕七学位论文 第2 章网络重构技术的研究 2 1 信息栅格体系结构 信息栅格是一种可以快速建立并且不需要预先在固定的网络底层上构建的网 络，它具有动态拓扑、网络资源受限、多跳、移动等特点。具有分层分布式体系 结构的信息栅格是一种新型的网络，它不仅具有传统网络的一般特性，而且其规 模庞大和层次性又为网络管理提出了新的要求。 本课题的信息栅格体系结构采用的是群首动态选举的分层分布式分群体系结 _ 0 - - _ 构，如图2 1 所示。 图2 1 分层分布式分群体系结构 该体系结构是从网络管理的角度对网络中的各个节点进行分群，同层的节点 采用最大连接度和最小资源占有率相结合的算法进行横向一次分群；然后从上下 层的角度，采用最小资源占有率的算法进行纵向二次分群。通过对网络中的各个 第2 章网络重构技术的研究 节点进行分群，可将网络中原本大量的节点划分成若干个小的区域进行自治管理， 提高了网络管理的效率，降低了网络带宽资源的占用率。 在此基础上为了防止单一节点故障，造成资源管理和监控系统失效，采用选 举技术，保障系统的安全运行，提高系统可靠性。纵向群首减轻了群首接收下级 节点传来的信息的处理负担，并采用捎带技术将收集来的信息传给群首，降低带 宽的占用，避免使群首成为通信的瓶颈，进一步减小网络系统的带宽占用。此外， 通过划分纵向群，对上下级节点进行统一管理，解决了上下级的注册问题，尤其 是上级对下级的注册问题，当节点出现故障时，加快了重构的速度，提高了网络 管理的效率。纵向群的群首为其所在群的普通节点，纵向群首与下级的群首相连。 以下为相关术语。 ( 1 ) 群首，根据节点性能及与其它节点的连接度情况动态选举生成，主要管理 本群节点，监控节点的动态入群和出群，并负责与上级群的通信。 ( 2 ) 纵向群首，主要负责与下级群的通信，以减少群首工作量。 ( 3 ) 节点，即普通节点，是被管理对象。 ( 4 ) 邻接群，不属于同一个群，但隶属于同一个纵向群。 结合信息栅格的体系结构，重构算法由“直接连接”( 启用备用通信链路) 、 “中继连接 ( 重路由) 、“越级连接( 重新划分网络周边界) 三种构成。如图2 2 所示。 图2 2 网络重构算法示意图 沈阳理_ 丁= 大学硕士学位论文 ( 1 ) 直接连接：利用启用备用链路的方法重构节点之间的通信链路； ( 2 ) 中继连接：采用重路由方法来恢复链路通信。其综合考虑传输时延、线路 负载和链路出错率等因素以提高网络服务的性能； ( 3 ) 越级连接：越级连接是网络重构算法中重新划分网络周边界的体现。划分 网络周边界的思想是：将可靠性和安全性问题划分到最小的网络区域里，利用该 区域外的唯一直接上级节点对该区域进行各种恢复尝试以决定是否要把该区域重 新划分，是否隔离不可信( 失效) 移动节点。针对于信息栅格网络，就是对网络 进行全局或部分群的划分。 2 2 网络重构的关键技术 网络重构技术最早起源于配电网的网络重构。配电网在馈线上装有分段开关， 馈线间装有联络开关，系统调度人员可根据系统运行目标的要求对网络中的开关 进行优化组合开合操作，这种开关的开合过程，就是网络重构。正常情况下，通 过网络重构，可达到降低网损、消除过载、平衡负荷的目的；在故障情况下，网 络重构可迅速隔离故障，恢复对非故障区用户的供电。配电网网络重构技术最早 是由m e r l i n 和b a c k 于1 9 7 5 年提出来的，至今仍有大量学者从事这一领域的研究。 随着计算机网络的迅速发展，人们对计算机网络的依赖性越来越大，因而由 网络故障带来的损失也越来越严重，这样计算机网络重构技术的研究和发展越来 越引起业内人士高度重视。所谓计算机网络重构技术是指采用各种重构技术使网 络在网元出现故障或失效的情况下，恢复到可接受的性能指标的水平，或重构成 另一网络，以保证整个网络的不间断运行。可见计算机网络重构技术是保证网络 生存性的一个重要内容，其目的是为了提高计算机系统的性能，提高网络的容错 能力和通信的可靠性。现有的网络重构的关键技术有冗余设置、自愈环技术和重 路由三种。 2 2 1 冗余设置 冗余，意思是“不必要的重复，对于一个正常的系统来说，冗余的部件并不 能带来好处，可以说是不必要的，但从可靠性的角度来说冗余却是必要的。 第2 章网络重构技术的研究 通过系统冗余设置的方式提供可靠性的保证应该算是一种最简单也是最重要 的重构能力的体现，即设置备用通信链路或设备，在正常链路或设备发生故障后， 启用备用链路或设备来恢复通信，如图2 3 所示。 2 2 2 自愈环技术 图2 3 冗余设置 自愈技术是提高网络生存性的一种行之有效的手段，由于能迅速恢复故障而 日益显示出其重要性。所谓自愈就是指在发生传输线路中断、节点故障或出现系 统服务性能降低的情况下，网络能够采取一定的措施对业务进行自动恢复，保护 对用户进行业务提供的连续性。其基本原理就是使网络本身具备发现替代传输路 由并重新确立通信的能力，其概念只涉及重新确立通信，而不管具体失效元部件 的修复或更换，后者仍然需要人工干预完成。 根据再选路径的指定时间，可以分为预先计算再选路径和实时计算再选路径 两大类。前者针对常见故障，如单链失效，由节点预先计算再选路径，在出现故 障时，切换到再选路径上。后者则在出现故障时，启动拓扑更换算法，通过节点 间交换( 广播) 消息实时地查找空闲容量，建立再选路径。对于前者，其再选路 径的容量可以事先指定，也可以是在故障发生后捕获。一般地说，实时恢复机制 具有强的适应性，不需要预先计算工作，但恢复时需要进行较多消息交换，比预 先恢复机制恢复时间长。预先恢复机制恢复速度快，但要节点预先计算并且进行 有关数据存储，消耗资源较多。此外，根据再选路径的范围以及施行再选路径的 节点划分，恢复机制可分为链路恢复和路径恢复。根据重新路由选择再选路径的 方式可分为最大流路径和k 条最短路径方式。不同的机制在恢复的程度、速度、 处理的开销等各方面表现不尽相同。需要说明的是恢复机制成功实施的必须条件 是有空闲容量来容纳需要重新路由的流量，进一步的说也就是取决于故障发生时 网络中工作流量和空闲容量的分布及大小，因而，必须进行有效的资源管理，才 能保证快速故障恢复机制的实现，提高网络生存性。 沈刚理t 大学硕十学位论文 由于具有共享带宽和高存活性的特点，环形网络体系结构得到了广泛的应 用。自愈环( s h r ：s e l f - h e a l i n gr i n g ) 就是一种环形网络体系结构。s d h 自愈环 体系结构可分为两类：双向s h r ( b s h r ) 和单向s h r ( u s h r ) 。环的类型决定 于由每对节点问的双工信道的方向。双工信道的两个方向相反( 一个为顺时针， 另一个为逆时针) 的s h r ，被称为b s h r ，而双工信道的两个方向相同( 同为顺 时针，或同为逆时针) 的s h r 被称为u s h r 。图2 4 和图2 5 描述了b s h r 的例 子，图2 6 描述了u s h r 的例子。在图2 4 和图2 5 的节点2 和节点4 之间的双工 信道中，节点2 到节点4 的信息方向为顺时针( 2 3 4 ) ，节点4 到节点2 的信道 方向为逆时针( 4 3 2 ) 。在图2 6 的节点2 到节点4 之间的单工信道中，节点2 到节点4 的信道方向为逆时针( 2 一 1 4 ) ，节点4 到节点2 的信道方向为逆时针 ( 4 3 2 ) 。因此b s h r 需要两条工作光纤承载一个双工信道。为了对节点失效 和光缆切断提供保护能力，b s h r 可以使用4 条光纤( 即一对工作光纤和一对保 护光纤) ，或2 条光纤( 即所有的工作光纤都具有用于保护的备用容量) ；u s h r 只需两条光纤( 即一条工作光纤，一条保护光纤) 。 每种类型的环，都可以采用两种s d h 自愈控制模式：线路切换和通道切换。 线路切换模式使用s d h 线路开销信道进行保护切换，( 在s d h 中有通道、线路、 以及段边界3 个层次，每个层次上都提供开销信道，一边进行分层维护) ，恢复由 设备故障引起的线路要求；而通道切换模式使用s d h 通道丌销信道，恢复各个端 到端服务通道。 另外，通道切换以环中每个通道的质量为基础保护业务量；而线路切换时以 每对节点间的线路的质量为基础的。当一条线路发生故障时，在故障的边界处整 个线路都被切换到保护环路上。 一工作链路 + 一- 保护链路 图2 4 双向4 纤白愈环 第2 章网络重构技术的研究 2 2 3 重路由 一工作链路i 一一一保护链路 图2 5 双向2 纤自愈环 一工作链路_ 一一一保护链路 图2 6 单向自愈环 为了信息可靠性传输的重路由技术也可以被看作是一种重构方法n “1 ，因为它 提供了在发生故障时，旁路掉失效或已失去自愈能力的网络设备或节点，从而保 证网络通信的安全可靠的能力。重路由指将失效的原中继节点旁路掉，重新计算 生成新路由，恢复源节点到目的节点的正常通信，路由计算方法有b e l l m a n f o r d 、 s p f 、遗传算法等，按其生成方式又分为源路由方式和驱动路由方式，源路由生成 方式即在源节点计算产生到目的节点的完整路径，而驱动路由方式则由转发节点 根据具体的环境变化动态选路。很多科研机构都将重路由作为实现网络重构的重 点工作n ”。 沈刚理r ：大学硕十学位论文 2 2 3 1b e l l m a n f o r d 算法 b e l l m a n f o r d 算法6 1 ，也称为反向搜索算法或距离矢量算法，它是从目的点出 发反向计算的。在该算法中，每个路由器维持着一张子网中每个以其他路由器为 索引的路由选择表，表中的每一个项目都对应于子网中的每一个路由器。此表中 包括两个部分，即希望使用的到目的地的输出线路和估计到达目的地所需要的时 间或距离。它是找到一个从给定的源顶点出发的最短路径，限制条件是路径上最 多只有一条链路；然后再找到一些最短路径，限制条件是路径上最多只有2 条链 路，其余类似这个算法也是分步骤执行的，其形式描述如下。 s = 源顶点； w ( i ，j ) = 从顶点f 到顶点的链路耗费；如果两个顶点之间不直接相连，则 w ( i ，j ) = 0 0 ，如果两个顶点之间直接相连，则w ( i ，j ) 0 ； 日= 在算法和当前步骤中路径的最大链路数； p ( n ) = 从顶点s 到顶点的最小耗费路径的耗费，限制条件是路径的链路数 不超过。算法的步骤如下：其中步骤2 重复执行，直至路径的耗费不再变化为 止： 第1 步初始化： p o ( n ) = o o ，对所有n s ；名( s ) = 0 ，对所有日； 第2 步更新： 对于每个h 0 ，且，z s ，计算昂+ ，( 胛) = m i n 易( ) + w ( j ，z ) 】找到符合最 小条件的顶点，将与该前趋顶点相连，删除与所有其它前趋顶点的连接，这 些连接是在前面的迭代中产生的； 从s 到的路径以到n 的链路结束； 将b e l l m a n f o r d 算法应用到图2 7 中网络中，每个节点都维护着通向其它节点 的最省线路信息，它包括线路开销以及那条线路上的第一个节点。表2 1 至表2 2 分别显示了信息b e l l m a n f o r d 算法前两轮运算得到的结果。表中每行对应两个源 节点，每列对应一个目标节点，每一个表中的条目包含了路径的第一个节点和线 路刀= 销。 1 2 第2 章网络重构技术的研究 图2 7b e l l m a n f o r d 算法网络 初始时，每个节点只知道到邻居节点的开销。如表2 1 所示。 表2 1 初始状态 abcdef a ( b ，1 )( c ，1 )( d ，2 )( 未知，时( 未知，哟 b ( a ，1 )( 未知，哟( 未知，哟( e ，5 )( 未知，哟 c ( a ，1 )( 未知，o c 9( d ，4 )( 未知，呻( 未知，呻 d ( a ，1 )( 未知，哟( c ，4 )( e ，1 )( f ，6 ) e ( 未知，哟( b ，5 )( 未知，哟( d ，1 )( f ，4 ) f ( 未知，哟 ( 未知，的( 朱知，哟( d ，6 )( e ，4 ) 表2 2 第一次向量信息交互后 abcde f a ( b ，1 )( c ，1 )( d ，2 )( d ，3 )( d ，8 ) b ( a ，1 )( a ，2 )( a ，3 )( e ，5 )( e ，9 ) c ( a ，1 )( a ，2 ) ( a ，3 )( d ，5 )f d ，1 0 ) d ( a ，2 ) ( a ，3 )( a ，3 )( e ，1 )( f ，6 ) e ( d ，3 )( b ，5 )( d ，5 )( d ，1 )( f ，4 ) f ( d ，8 )( e ，9 )f d ，1 0 ) ( d ，6 )( e ，4 ) 可以看到，正是由于邻居节点不断的定期广播消息，最终网络节点和连接的 有关信息可以传遍整个网络。使得每个路由器可以通过这些广播的信息选择出一 个最佳的路径。 b e l l m a n f o r d 算法中每个节点的路由选择要依靠网络的当前状态信息来决定， 沈研i 理下大学硕十学位论文 以设法适应网络流量、拓扑的变化。由于此算法中节点仅仅记录较好路径的变化， 所以若一条链路崩溃或者过载，节点并没有办法了解到这些变化。因此该算法要 频繁刷新每个节点的路由表，以便适应不断变化的网络。b e l l m a n f o r d 算法是反向 学习算法，节点从每个邻居处得知到达某节点的最省路径以及路径上的第一个节 点。 b e l l m a n f o r d 算法，有路由协议算法简单，路由器配置简易等优点；缺点是网 络中的过时路由不能及时被删除造成网络不稳定，大规模网络需要很长的收敛时 间，最大跳数限制了网络规模，数据库没有变化时需要周期发送距离向量表等。 2 2 3 2s p f 算法 s p f ( s h o r t e s tp a t hf i r s t ) 算法，也称d i j k s t r a 算法1 ，是依据图论基础来发现 两点之间的最短路径。当通信网络中的路由器和链路可以被模拟为有向图中的顶 点和边时，s p f 算法便可以用来计算图中节点间的最佳路径。 ( 1 ) s p f 算法概要 _ 网络中的顶点集合； s = 源顶点； m = 算法中用到的临时顶点集合； w ( i ，j ) = 从顶点f 到顶点_ ，的链路耗费。如果两个顶点之间不直接相连，则 w ( i ，j ) = o o ；如果两个顶点之间直接相连，则w ( i ，j ) 0 ； p ( n ) = 从顶点s 到顶点的最小耗费路径的耗费，算法执行过程中是知道的； 算法结束时，也就是s 到n 的最小耗费路径的耗费。 算法总共有3 个步骤：步骤2 和步骤3 要重复执行，直至胙。也就是说， 步骤2 和步骤3 一直重复到网络中所有顶点都已经找到最终路径为止。 第1 步初始化： 胙 研，即临时顶点集合中只有源顶点； 以以) = 瞅f ，力，对所有n s ，即到相邻顶点的初始路径耗费就是链路耗费。 第2 步取下个顶点： 找到不在m 中且到顶点s 有最小耗费路径的相邻顶点，把它加入到临时集合 第2 章网络重构技术的研究 m 中；把依附于该顶点m 中某顶点构成路径的边也加入到m 中。 第3 步更新最小耗费路径 p ( n ) = m i n p ( n ) ，p ( 工) + w ( x ，刀) 对于所有x 叠m 如果第二项小，则从s 到的路径从现在起就是从s 到x 再加上x 到之间 的边。 当所有的顶点都加入到m 以后，算法结束。结束后，每个顶点x 的值p 就 是从s 到x 的最小耗费路径的耗费( 长度) 。 在图中决定任意两个顶点之间的最短距离的算法与在数据通信网络中发现任 意两个节点之间最短路径的算法类似。路由选择协议的功能就是在网络中依据优 化的评价标准( 经常用最小开销或者最小度量) 来决定节点之间的最短路径。以 此类推，通信网络中的路由器类似于图中的节点，链路或邻接边类似于弧线。由 于网络中通信流量是双向的，每一个网络链路类似于一对相反方向的弧线。通常。 网络中的链路被耗费称为开销或者度量的权值。许多实际网络使用数字标示链路 开销，与带宽成反比。因此，最快速的链路分配最小的开销值。因此决定网络中 节点之间最短路径也就是决定最小开销路径。 ( 2 ) 运行s p f 算法的开销 s p f 算法开销的计算与节点数和包括的链路数目有关。在大型网络中s p f 运： 算非常消耗资源，要求的计算完成时间达到2 ，是网络中节点数目。对于有 个节点的网络，计算的复杂性可以直接考虑得到，为了决定图中参考顶点到其他 所有节点的最短路径，需要1 次迭代。每一次迭代，决定最小开销顶点所需要 的运算次数与成比例。 一般来说，如果图中有个节点和条链路，可以看出，s p f 的计算时间与 链路数成比例：网络中链路数三的对数倍。这就是s p f 的计算代价的阶数 o ( l l o g l ) 。 例如，在简单的网络里，所有节点以尽可能少的链路互连，线性排列，这时 l = n - 1 。l l o g l 就可以表示成l l o g l ( n - 1 ) ，与l l o g n 是等价的。简要的说，可以用 o ( l t o g n ) 来估算s p f 算法的计算复杂度，这里三是网络中总的链路数。是总的 节点数。 s p f 算法要求先构造最短路径树，然后根据最短路径树形成路由表。构造最短 1 5 沈刚理t 大学硕十学位论文 路径树的过程需要整个网络的拓扑信息，即网络中所有链路的费用。s p f 算法的优 点是简单，适合于在一个负载稳定，拓扑变化不大的网络中运行。但是它的灵活 性较差，无法对网络拥塞和故障作出反应。s p f 算法是一种正向学习算法，可作为 集中式路由策略来实现。 2 2 3 3 遗传算法( g a s ，g e n e t i ca l g o r i t h m s ) 遗传算法是在解集合的一个子集内进行搜索最优解或近似最优解的搜索算 法，它可在解的质量和求解效率上达到一种较好的平衡，对求解n p 复杂性问题n 町 比较有效。 遗传算法是基于生物学的算法，一般步骤为： ( 1 ) 编码及随机产生初始群体，遗传算法的初始群体随机产生，群体中的每个 成员代表一个候选解，通常称为染色体，染色体以二进制码串的形式进行编码。 ( 2 ) 评估适应度，每个解( 染色体) 由适应度函数来评价。 ( 3 ) 选择、交叉和变异，选择的目的是从当前群体中选择优良的个体，使它们 有机会作为父代为下一代繁殖子孙。适应性越强的个体被选择的几率就越大。交 叉操作把两个父代个体的部分结构加以替换重组而生成新个体，新个体继承了父 代的特性。变异允许下一代的变化，为新个体的产生提供了机会。遗传算法作为 一种快捷、简便、容错性强的算法，在解决优化问题方面显示出良好的效果。 常用的遗传算子有以下三种n ( 1 ) 选择算子( s e l e c t i o no p e r a t o r ) 选择算子是用来选择群体中适应度高的个体以构成新的一代群体。其中每个 个体被选中的概率取决于个体对环境的适应值，最常用的选择方法是适应度比例 方法，也称为轮盘赌选择。 ( 2 ) 交叉算子( c r o s s o v e ro p e r a t o r ) 交叉算子通常作用在两个基因串上。交叉算子是把两个基因串中的某部分互 换，产生两个新的个体。交叉部分的选择是随机的。因此交叉算子是以一定的概 率发生作用的。 ( 3 ) 变异算子( m u t a t i o no p e r a t o r ) 变异算子是在遗传算法中用来模拟生物在自然界的遗传环境中由于各种偶然 第2 章网络重构技术的研究 因素引起的基因突变而引入的一种算子。变异算子是把基因串中的某一基因以概 率取反运算( 仅仅适用于二进制) 。同自然界一样，每一个基因发生变异的概率很 小。变异算子可以对交叉算子起辅助作用以增加算法的全局性。长度为l 的p 个 二进制串b ，( f _ 1 ，2 ，p ) 组成了遗传算法的初解群，也称为初始群体。在每 个串中，每个二进制位就是个体染色体的基因。变异过程就是指将个体编码串中 的某些基因座上的基因值用该基因座上的其他等位基因来替换，从而形成新的个 体。如在串b f 中，如果某位基因为1 ，产生变异时就是把它变成0 ；同理，如果某 位基因为0 ，产生变异时就是把它变成1 。 遗传算法的原理可以简要概括如下： c h o o s ea ni n t i a lp o p u l a t i o n d e t e r m i n et h ef i t n e s so fe a c hi n d i v i d u a l p e r f o r ms e l e c t i o n r e p e a t p e r f o r mc r o s s o v e r p e r f o r mm u t a t i o n d e t e r m i n et h ef i t n e s so fe a c hi n d i v i d u a l p e r f o r ms e l e c t i o n u n t i ls o m e s t o p p i n gc r i t e r i o na p p l i e s 作为一种随机优化与搜索方法，遗传算法具有如下特点啪“，。 ( 1 ) 遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码。 ( 2 ) 遗传算法仅使用由目标函数变换来的适应度函数值，就可以确定进一步的 搜索方向和搜索范围，无需其他辅助信息，适用于大规模，高度非线性问题的求 解，具有很强的通用性。 ( 3 ) 遗传算法同时对包含多个个体的群体进行搜索，具有一种隐含并行性。 ( 4 ) 很多传统的优化算法认为好的解是两两“邻近 的，因此容易陷入局部最 优。 ( 5 ) 遗传算法是收敛的。