（电磁场与微波技术专业论文）ason中路由问题的研究与仿真.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名薹叠壹 蹶 2 汐f d f f o 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅：学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 本学位论文属丁保密范围，在一年解密后适用本授权书。 本人签名部垒 导师虢7 如整 日期：翌! ! ：! ：! ! k 。 气 北京邮电人学硕上学位论文 a s o n 中路由问题的研究与仿真 摘要 近年来，随着互联网业务的不断丰富多彩和用户的日益增多，对 网络的性能提出了越来越多的要求。从用户的角度来说，需要实时性 更好的即时通信、更大更清晰的多媒体资料、更好的网络稳定性等等。 从运营商来说，需要增大网络容量、采取新的机制来节约自己的运营 成本。这些，都给现今的网络提出了新的要求，因此各类网络都基于 目前的状况，提出了自己对下一代网络的解决方案。如移动通信中的 3 g 、l t e 等，计算机网络中的n g n 、f i n d 等，在光网络中，也有 类似的进展，先后有i po v e rw d m 、a s o n 等概念的提出。 作为网络中的一个非常重要的问题，本论文从本人硕士阶段的工 作出发，结合i po v e rw d m 、光网络规划软件等实际问题，先后从研 究、仿真等方面对光网络中的路由问题进行了分析与改进。 首先提出最短路径方法及应用，主要分两方面进行展开：点到点 最短一条路径和点到点最短多条路径。从时间复杂度、空间复杂度和 代码复杂度出发，结合数据结构对复杂度的影响，对已有的最短路径 方法进行了分析，特别是多条路径的三种方法。在此基础上，给出了 选择算法的建议，并给出了一种特殊情况下多条路径的求解方法。 接下来分析了联合路由问题，首先分析了i po v e rw d m 的发展， 介绍了i po v e rw d m 的三种模型。由此，引入了联合路由的问题，在 结合前人方法的基础上，依靠实验室的项目，参与提出了一种负载均 衡的联合路由算法，并进行了仿真验证。 最后，在网络规划仿真平台中，给出了规划研究小组对于网络规 划仿真平台的系统总体设计，并展示了如何以软件组件模型的方式进 行实现。对于软件中十分重要的业务分配与保护模块，给出了路由计 算与波长分配的详细实现方案及考虑业务等级的恢复容量分配方案。 关键词：a s o n ，最短路径方法，i po v e rw d m ，联合路由，网络规划仿 北京邮i 乜人学硕： ：学位论文 北京邮电人学硕l ：学位论文 s i m u l a t i o nr e s e a r c ha n di m p l e m e n to nr o u t i n gp r o b l e m s i no p t i c a ln e t w o r k s a b s t r a c t r e c e n t l y , w i t ht h ei n t e r n e ta p p l i c a t i o n sa n dt h eu s e r so ft h ei n t e r n e t i n c r e a s e ，t h eq u a l i t yo ft h en e t w o r ki sr e q u i r e dt ob eh i g h e r f r o mt h e a s p e c to ft h eu s e r s ，t h e yn e e db e t t e rr e a l - t i m ec o m m u n i c a t i o n ，m o r e d e t a i l e dm u l t i m e d i ad a t a ，a n dm o r es t a b l en e t w o r k f r o mt h ea s p e c to ft h e n e t w o r k s o p e r a t o r ，t h e yn e e dn e t w o r kw i t h m o r eb a n d w i d t h ，m o r e f l e x i b l e s t r a t e g i e s t o m a n a g et h en e t w o r kw i t h l e s sc o s t a l lt h e s e c h a l l e n g et h ed e s i g no ft h em o d e r nn e t w o r k a sar e s u l t ，m a n yn e w n e t w o r k sc o m eo u t ，s u c ha st h e3 gl t ei nt h em o b i l en e t w o r k ；n g n ， f i n di nt h ec o m p u t e rn e t w o r k ；a n di po v e rw d m ，a s o ni nt h eo p t i c a l n e t w o r k a so n eo ft h em o s ti m p o r t a n tp r o b l e mi nt h en e t w o r k ，id os o m e a n a l y s i sa n di m p r o v e m e n t sa b o u tt h er o u t i n gp r o b l e mo nt h eb a s eo f s o m ep r o j e c t s ，f o re x a m p l e ，t h er e s e a r c ho ft h ei po v e rw d m p r o b l e m s ， t h es o f t w a r es y s t e mo fn e t w o r kp l a n n i n ga n do p t i m i z a t i o n f i r s t ，ib e g i nw i t ht h ep r o b l e mt h es h o r t e s tp a t hp r o b l e mw h i c hi so n e c l a s s i cp r o b l e mi nt h er o u t i n gp a r t ia n a l y z et h i sp r o b l e mr e s p e c t i v e l y f r o mt h r e ep a r t ，t i m ec o m p l e x i t y , r o o mc o m p l e x i t ya n dc o d ec o m p l e x i t y w h i c ha r ea l s oc o m b i n e dw i t ht h ed a t as t r u c t u r e a c c o r d i n g l y , ig i v es o m e s u g g e s t i o no nh o w t oc h o o s et h em e t h o df r o mt h e s eio f f e ra n dia l s og i v e as p e c i a lm e t h o df o rt h es h o r t e s tp a t hp r o b l e m s e c o n d ，ia n a l y s et h ei n t e g r a t e dr o u t i n gs c h e m ei nt h ei po v e rw d m p r o b l e m t h ed e v e l o p m e n to ft h ei po v e rw d m a n dt h et h r e em o d e l s m u s tb ek n o w na saf o u n d a t i o n t h e n ，ig i v eal o a db a l a n c em e t h o da s o n e i n t e g r a t e dr o u t i n g s c h e m ew h i c hi p a r t i c i p a t e i nt h es c h o o l l a b o r a t o r y l a s t ，i nt h ep a r to ft h ep l a t f o r mo fn e t w o r kp l a n n i n ga n do p t i m i z a t i o n ， ig i v et h eg e n e r a ld e s i g no ft h es y s t e m a n dig i v eae x a m p l eo fh o wt o u s et h e c o m p o n e n tm e t h o d t or e a l i z et h es o f t w a r e s y s t e m f o rt h e 北京邮 乜人学硕1 ：学位论文 i m p o r t a n ts e r v i c ea n dw a v e l e n g t ha s s i g n m e n tp a r t ，ig i v et h ed e t a i l e d s t e p st oc o m p l e t et h er e q u i r e df u n c t i o n m e a n w h i l e ，ig i v et h em e t h o dt o r e s t o r et h ec a p a c i t yf o rd i f f e r e n tl e v e ls e r v i c e s k e yw o r d s ：a s o n ，t h es h o r t e s t p a t ha l g o r i t h m ，i po v e rw d m ， i n t e g r a t e dr o u t i n gs c h e m e ，n e t w o r kp l a n n i n ga n ds i m u l a t i o n 北京邮电人学硕i 二学位论文 目录 1 者论1 1 1 论文背景1 1 1 1a s o n 自动交换光网络1 1 1 2i po v e rw d m9 0 91 各：1 1 1 3 网络规划仿真平台2 1 2 论文结构及主要。1 作3 1 2 1 论文组织结构4 1 2 2 本人主要j ：作4 2a s o n 中最短路径方法6 2 1a s o n 路由理论基础6 2 1 1 路由理论概述6 2 1 2 光网络域内路由理论8 2 1 3 路由计算和路由选择一9 2 2 点剑点最短一条路径1 1 2 2 1d ij k s t r a 算法主要思想1 1 2 2 2 已有d i j k s t r a 算法实现。1 2 2 3 点到点最短多条路径1 2 2 3 1 构建子图法1 3 2 3 2 背离路径法1 4 2 3 3 分类布找法1 6 2 3 4 特殊情况中的方法。2 0 2 4 最短路径方法总结2 1 3 联合路由问题研究2 4 3 1i po v e rw d m 概j 苤。2 4 3 1 1i po v e rw d m 的发展2 4 3 1 2i po v e rw d m 三种模型2 9 3 2 负载均衡联合路由算法3 1 3 2 1 路由策略3 l 3 2 2 算法描述3 1 3 2 3 算法分析与结果3 4 4 网络规划仿真平台3 7 4 1 规划仿真平台设计。3 8 4 1 1 仿真系统总体设计3 8 4 1 2 软1 i ，l ：组件模型设计4 0 4 2 路由模块的设计4 5 4 2 1 路由计算与波长分配4 6 4 2 2 恢复容量分配4 8 5 结束语5 0 致谢! ；1 参考文献5 2 攻读硕十学位期间发表或录用的学术论文5 3 北京邮电人学硕一l ：学位论文 1 1 论文背景 北京邮电大学硕十学位论文 1 绪论 光网络【lj 本来被用于传输大容量的语音业务，如今，它不仅被用于传送语音 业务，还被用于传送数据业务，其中包括因特网业务。实际上，在过去几年中， 因特网是光网络空前扩张的驱动力。密集波分和智能交换机等新技术则成为了推 动各种宽带业务发展的技术基础。虽然光网络的迅速发展使得人们步入了一个可 以进行高速通信的新时代，但是它同时也引入了新的、值得研究的问题。 1 1 1a s o n 自动交换光网络 光网纠2 j 本来被用于传输大容量的语音业务，如今，它不仅被用于传送语音 业务，还被用于传送数据业务，其中包括因特网业务。实际上，在过去几年中， 因特网是光网络空前扩张的驱动力。密集波分和智能交换机等新技术则成为了推 动光网络发展的动力。虽然光网络的迅速发展使得人们步入了一个可以进行高速 通信的新时代，但是它同时也引入了新问题。 运营商常使用设备制造商开发的网元管理系统和自己开发的网络管理系统 来管理网络。他们都是使用专有技术且常常需要进行繁琐的手工配置。由于各厂 商独立开发管理系统，导致很难迅速并且有效地将新技术集成到现存的体系中。 管理系统所固有的手工配置特性增加了创建新业务的开销和开通时间，同时也加 重了误操作可能造成的风险。另外，光网络同益提高的复杂度使得这些问题变得 更加严重。 网络由处于网络系统中不同位置的多个子网组成的，网元扮演着不同的角 色，由不同的设备制造商生产，且通过设备制造商专有的系统来管理。这样便增 加了网络管理的复杂度。实际上网络运营支出的8 0 来自于管理支出。解决方案 便是利用技术创新来寻求出路，例如引入d w d m 和智能光交换机，同事也需要 有更好的控制和管理网络的方法。确切地说，我们需要将陈旧的、半手工方式的 网络管理体系逐渐改造成更加自动化的管理体系。 目前，许多运营商已经开始部署智能光网络和相关的光控制平面。然而，大 部分早期应用都使用厂家专用的协议和软件。i e t f 和o i f 所开发的控制平面标 准正在试验和初期应用阶段，因此，虽然这些专用技术发展缓慢，但是最终它们 北京邮电大学硕士学位论文 肯定会演变成为标准。该标准化过程正在加速进行，因为运营商在升级他们的运 营和管理体系来控制运营支出时，感到了更多的压力。 光控制平面很可能成为光网络的下一个发展方向。因此，对于运营商，设备 提供商和致力于传送网络的商业组织来说，它都是一个耳熟能详的话题。 、 1 1 2i p o v e rw d m 网络 近年来，随着i p 业务的迅猛发展，业务需求发生了显著的变化，从话音为 主变成以i p 数据为主。特别是，近年来随着i p t v 、视频点播、v o l p 、远程教育、 电子商务、电子政务等新型宽带电信数据业务的兴起，以i p 为承载协议的业务 已经迅速遍及电信业务的各个领域，业务网络的i p 化和承载网络的分组化转型 已经成为一个不可逆转的潮流。这些新型的电信业务与传统的电信业务相比，具 有更高的动态特性和不可预测性，因此需要传送网具有提供大容量、长距离传输 能力的前提下，还要提供更高的灵活性。然而，同步光网络同步数字体系 ( s o n e t s d h l 习) 是为传输话音业务所设计的，对以l p 业务为主的业务环境不 相适应。在效率方面，s d h 的环状结构对于长距离传送的l p 需求也被证明是低 效的。而且，传统骨干网却提供不了其他重要的需求，比如动态连接和业务需求 的快速建立、区分业务等级等。在这种趋势下，运营商的整个网络架构也在发生 着转变，业务的融合期待着光层作为基础承载层与i p 层的融合，使其成为更加 适宜于承载i p 业务以及电信级以太网业务的分组传送网。同时，波分复用 ( w d m ) 以及超长距离密集波分复用( d w d m ) 技术的成熟，使得网络业务的 真正瓶颈从带宽容量转移到带宽管理上，在核心的网络节点上，往往需要处理数 十个甚至在某些节点上需要处理上百个波长，而超长距离的传输能力，使得更多 的节点需要具备更多的上下波长能力。作为基础承载网络，在更为激烈的市场竞 争环境下，需要更快的业务提供以及各种层面的网络保护和恢复能力。因此随着 i p 数据业务的急剧增长，作为传送层的光网络，必须适应新一代承载网络的分组 化、业务化、带宽大颗粒化、动态化的组网需求。目前方兴未艾的w d m 技术与 其它传输技术相比具有明显的优势，在未来光网络的发展中，将会借助波长交叉 连接的w d m 技术在全网提供高容量连接，并且使网络运转从电路交换概念的租 用电路向以i p 技术为基础的按需分配带宽发展。 因此，采用w d m 网络承载数据业务( i po v e rw d m ) 的技术应运而生。 1 1 3 网络规划仿真平台 随着通信业务，尤其是数据业务的迅速发展，对电信传输网的需求也同益扩 2 北京邮电大学硕十学位论文 大，从业务层面对电信长途传输网的支撑能力提出了更高的要求，存在着网络组 网、容量、业务类型等不能满足当前或未来业务需求的情况；而w d m 技术、 a s o n 等传输新技术的发展成熟，则从技术层面推动者电信传输网向着更大容 量、更高速率、更智能化的方向不断演进。以上情况都造成电信运营商需要不断 对网络进行扩容、升级，那么如何有效的进行扩容、升级呢? 这就需要对网络的 发展进行规划设计。而新兴电信运营商在建设新的传输网络时也需要科学的规划 来指导。网络规划的制订直接影响到网络的平滑过渡、持续发展、业务需求的适 应性、服务质量等。 传输网络规划的工作核心是：根据业务、网络、以及相关技术的现状与发展 趋势，确定传输网的发展建设思路，远期目标结构，以及各年度工程项目，给出 一个“最优”的网络实现方案，包括定义网络拓扑和使用合适的路由和保护恢复 方式等。而且，工程人员根据这个方案能够实际地建设一个符合要求的光网络。 传输网作为各种业务的公共传送平台，其规划建设必须考虑各种约束和要求，不 仅要考虑传输网自身的结构特征、技术特点与演进方向，而且还需考虑业务的流 量流向、传输性能要求，以及各业务网的网络结构等。 考虑到传输网规模不断扩大，网络结构同趋复杂，网络规划工作的复杂性大 大增加。在传输网规划工作中，使用软件工具进行计算机辅助测算不仅可以节省 大量的人力资源，大幅度提高网络规划的效率，而且可有效提高规划方案的准确 性与科学性。一个好的规划软件工具至少应满足以下要求： ( 1 ) 软件工具应满足各类新业务、新技术对规划工作的要求。 ( 2 ) 可以对网络基础数据进行有效的管理，实现网络资源管理。 ( 3 ) 可进行多目标设计，在路由的选取方面可提供多种有效路由算法，根 据网络资源情况，灵活地改善。 ( 4 ) 在进行网络建模和网络模拟时充分考虑各种情况。 ( 5 ) 不只是单纯的算法工具，能支持多层网络联合规划、滚动规划等系统 性、连续性要求较高的工作。 ( 6 ) 尽量减少或消除复杂的手工处理步骤。 1 2 论文结构及主要工作 本项目的研究重点就是针对电信网网络规划所存在的问题，并结合电信网发 展对网络规划所提出的新要求，通过研究提出一套可行的数字化的网络规划方 法，并建立网络规划数据库和开发一个网络规划辅助系统，为网络规划设计人员 提供一套高效实用的规划工具，使其可以集中精力于实际的方案设计中，并进行 精确的定量分析以获得更准确的预测结果，提高网络规划的科学性、规范性。并 3 北京邮电人学硕十学位论文 把数据和结果存放在数据库中，便于查询统计和再利用。 1 2 1 论文组织结构 本论文共分5 章进行论述，分别为： 第一章：绪论。介绍与论文研究工作相关的背景知识。分别概要论述了本文 涉及的三方面：自动交换光网络、i po v e rw d m 网络网络、网络规划仿真的的 产生背景，解决的问题，和相关应用等。然后，总结了本文的主要工作。 第二章：光网络中路由问题。首先阐述了光网络中的路由问题的理论基础。 然后结合自己在中兴公司的研发工作，全面介绍了如何在实际设备中实现相关功 能，分别介绍了中兴公司自动交换光网络的总体设计和路由控制模块的设计。 第三章：联合路由问题的研究。本章主要介绍的内容i po v e rw d m 网络的发 展历程和相关理论，通过i po v e rw d m 的三种模型，提出了在此网络中，必须提 出和解决的联合路由问题。最后结合f j f 人的工作，提出了自己的联合路由方案。 第四章：网络规划仿真平台的介绍。本章主要介绍如何在微机仿真的环境下 实现一个规划仿真平台。从网络规划的相关概念谈起，然后介绍如何具体设计实 现，最后是如何使用网络规划的软件。 第五章：结束语。总结全文，并指出尚有待完善的问题。 1 2 2 本人主要工作 本人在读硕士期间，参与了如下项目：企业横向合作项目“网络规划仿真平 台”的开发、实验室研究项目“联合路由的研究”。依托以上项目的资助，本论 文分别这两个项目为出发点，分别从理论研究、电脑仿真两方面出发，对光网络 中的路由问题进行了深入的钻研，系统地总结了实际实现、电脑仿真、研究路由 问题的方法和流程。 在“最短路径方法及应用”的研究中，主要分两方面进行展开：点到点最短 一条路径和点到点最短多条路径。从时间复杂度、空间复杂度和代码复杂度出发， 结合数据结构对复杂度的影响，对已有的最短路径方法进行了分析，特别是多条 路径的三种方法。在此基础上，给出了选择算法的建议，并给出了一种特殊情况 下多条路径的求解方法。 在“联合路由”等问题的研究中，首先分析了i po v e rw d m 的发展，展开了 i po v e rw d m 的三种模型。由此，引入了联合路由的问题，在结合前人方法的基 础上，依靠实验室的项目，参与提出了一种负载均衡的联合路由算法，进行了仿 4 北京邮电人学硕士学位论文 真验证。 最后，“网络规划仿真平台”项目中，给出了规划研究小组对于网络规划仿 真平台的系统总体设计，并展示了如何以软件组件模型的方式进行实现。对于软 件中十分重要的业务分配与保护模块，给出了路由计算与波长分配的详细实现方 案及考虑业务等级的恢复容量分配方案。 北京邮电人学硕十学位论文 2a s o n 中最短路径方法 最短路径的算法作为各类网络中一个基本问题，被广泛地用于各类需要获得 线路的网络应用中。如在电子导航的应用中，利用最短路径的算法来获得一条或 多条可行路径；或者在各种管导网、线路的布局设计中也发挥了重要的作用。同 样，在通信网络中，如何获得最短路径也是十分重要的。 下面从点到点的最短一条路径的方法出发，到点到点的多条路径的求法。这 样安排不仅因为它们是同一类问题，而且前者同时也是后者的基础。 在本章中，首先给出了a s o n 路由的相关理论。然后，针对最短路径方法， 不仅给出算法的不同实现方式，而且分析了不同实现的效率问题，最后总结了算 法，并给出在实际中如何选择使用的建议。 2 1a s o n 路由理论基础 路由是指网络中某个发现一条或多条到达目的地的路径过程。路由过程由以 下几个部分组成：邻居发现，拓扑发现和路径选择。邻居发现是路由的第一部， 通过它，网络中的节点就可以发现与它们相邻的邻居节点并且可以了解其自身是 如何与这些邻居节点相连的。而拓扑发现的作用则是使得节点可以发现网络中的 其他节点，并且还能知道这些节点是如何连接的。一旦得到了网络的拓扑信息， 便可以使用路径计算算法来计算从源点到宿点的路径。 路由理论中，有两类路由是要区别对待的：一是同一个网络中有一个管理实 体控制的路由；另一个由不同管理实体控制的跨越网络的路由。前一种也称为域 内路由，后一种也称为域问路由。由于现阶段，域问路由尚未有统一标准，所以 本节将重点介绍域内路由。 2 1 1 路由理论概述 随着i n t e r n e t 的广泛使用，路由在今天已经变成了i p 路由或者i p ( 网络) 层路由的代名词。光网络和i p 网络在很多方面都不相同，但是，在将i p 路由协 议经过一些修改和扩展后，便可将其用于光网络中的动态路由连接了。光网络中 的路由也与电话网和a t m 网络中的路由有一定的联系。 现阶段最大的两个网络是电话网和i n t e r n e t 网络，电路交换电话网络中的 路由在很多方面与光网络中的路由连接类似，虽然基于分组交换的因特网中路由 6 北京邮电大学硕士学位论文 的某些部分和电话网、光网络中的路由相似，但是还是存在着许多的不同之处。 不同的标准化组织j 下在为光网络中的路由连接定义更加先进的以i p 为中心的路 由协议。 下面将分为两方面介绍路由方面的一些基本的问题，这里主要涉及到的网络 是电话网和因特网。 1 电话网与i p 网中的路由 ( 1 ) 电话网中的路由 下图为当今电话网的体系结构。在途中，它是一个由交换局c o 、本地交换电 信局l e c 和全相连的广域核心网组成的三层结构。l e c 可以连接到多个广域核心 网。如果两个终端之间的呼叫时在同一个c o 内，那么它们是直接连接的。如果 两个终端在不同的l e c 内，那么它们之间的呼叫是通过核心网进行路由的。 核心网中的路由使用单跳或者双跳路径。需要注意的是，核心网是全互连的。院 交换机和宿交换机之间的直接一条被认为是这两点之间的主路径。如果一对交换 机之间的主路径可用，那么通话的路由就经过那条路径。如果主路径不可用，那 么通话的路由就会选择可以用的双跳路径之一。也就是说，在主路径不可用的情 况下，路由问题可以通过使用双跳路径来解决。 早期的电话网依赖于核心网中的静态单跳路由。在这种机制下，源交换机和 宿交换机之间的路径与网络状态一直无关。为了能够处理峰值时的业务，在网络 中指配固定路由时需要留足够的余量。如果选择的路径业务繁忙，通话请求就会 被丢弃。因此，现在看来，电话网中的静态路由机制非常死板而且非常低效。 在引入了数字交换之后，核心网中的静态路由被动态路有所替代。动态路由不想 静态路由那么死板，它使得网络运营起来变得更加有效。由于允许基于每一个呼 叫进行路由计算和周期性地更新路由，动态路由提高了网络的灵活度。人们设计 了下面三种用于电话网饿动态路由机制：t d r 一时间相关路由，路由表通过随着每 同时间点或者每周工作同而变化的业务量来编制；s d r - 状态相关路由，路由表根 据网络的当前状态试试更新；e d r 时间相关路由，当链路拥挤或者链路阻塞而导 致失败时，便会触发路由改变。 ( 2 ) i p 网中的路由 和电话网不同，i n t e r n e t 的网络结构很灵活，它是由各个对等点相互连接组 成的网络集合，如图所示。这些网络有不同的i n t e r n e t 服务提供商( i s p ) 管理。 对等点是i s p 互相收发业务的地方。根据它们的网络规模和区域大小，i s p 可以 被分为不同的等级。 从更深的的技术角度来看，i n t e r n e t 是一个自治系统( a s ，a u t o n o m o u s s y s t e m ) 组成的集合。从控制平面的角度来看，a s 和后面将要提到的控制域类 7 北京邮电火学硕十学位论文 似，它是由单个组织管理的多个i p 网络组成的。组织的定义是很宽松的，它可 以使一个服务提供商、一家公司，或者一所大学。很多组织跨越多个a s ，一些 组织还会有它们自己的a s 。相邻的a s 通过私有或者公共i n t e r n e t 交换点对等 互连。当业务从一个a s 传送到另一个a s 的时候，这两个a s 可能存在一种消费 者和生产者的关系。相邻的a s 可以相互交换可达宿点的信息，然而，它们并不 交换内部拓扑信息。 2 因特网路由协议 在i n t e r n e t 领域中，术语“路由”被又来泛指控制和数据平面功能。然而， 区分这两个功能很重要。控制平面的作用是允许节点发现网络的拓扑并计算该节 点到其它节点的路由。这是通过运行某个路由协议来完成的，改协议会在整个网 络中广播拓扑和节点是否可达的信息，这些信息会被存储在每个节点的转发表 中，转发表中含有一个下一个节点的标志和将包转发到每个目的地索要经过的输 出接口。路由器中的路由平面含有这样的功能：根据转发表中的信息，将传入的 i p 包转发到它们的目的地。更加准确的说，钻发一个i p 数据表包含有以下步骤： 检查数据包的目的i p 地址，搜索转发表以确定下一条和相关输出接口，然后将 数据包转发到下一跳。转发也包含其他的功能，例如检查并且消减数据包中的 t t l 的值和检查并且调整报头中的校验和。如果实现了q o s 特性，传送功能还可 能回包括基于以下几个方面的数据包分类：源地址、目的地址、i p 头中的其他 域，甚至有可能是i p 有效净荷。需要注意的是，只有i p 路由控制平面才适合与 光网络。i p 路由的包传送功能和光网络并不相关。 i p 路由协议可以从整体上分为两类：距离向量和链路状态。使用距离向量路 由协议的节点，都维护这通过其各个邻居到达各个宿点的距离( 如跳数) 。使用 链路状态路由协议的节点，都具有网络拓扑的完整视图。为了确保视图不过时， 每个节点都会将它本地链路的详细信息广播给网络中的其他节点。 在距离向量路由算法中，经典的算法有分布式b e l l - f o r d 算法。路由信息协 议( r i p ) 是一种使用分布式b e l l m a n - f o r d 算法的协议。 在链路状态路由算法中，当链路状态改变时，节点讲义泛洪法向整个网络发 送一种被称为链路状态信息l s a 的消息。第一个链路状态协议，最短路径优先 ( s p f ) ，是为a p p a n e t 的分组交换网开发的。i n t e r n e t 任务组i e t f 在s p f 的基 础上，开发了公开最短路径优先o s p f 路由协议。 2 1 2 光网络域内路由理论 目前，如果要在传统的光网络中计算一条连接的路由，需要操作较多的步骤。 其中包括很多手工的操作，因此繁琐且容易出错。另外，此网络的路由信息会过 8 北京邮电大学硕士学位论文 于集中，整个网络拓扑的数据会保存在一个中心网元或者网络管理系统中。这些 数据的输入和更新往往也是通过手工操作来完成的。因此，网络运营商们已经渴 望能够从这种集中式的手工操作中解脱出来，使用更自动化的分布式路由系统。 本章，我们将讨论应用于光网络中的分布式路由体系，它已经得到了很多标准组 织和用户团体的承认。 虽然光网络中的路由协议是从i p 网络协议扩展而来，但是在基于电路交换 的光网络中使用的路由协议与基于分组交换的i p 网络中使用的路由协议相比还 是有很大差别的。这些差别如下。 ( 1 ) i p 路由包括控制和路由平面的功能。和其他电路交换网络一样，光网 络中的数据平面并不参与连接的路由。 ( 2 ) 在i p 网络中，路由协议和数据平面的转发过程关系密切。一旦出现故 障，就必然会有用户受到影响。在光网络中，由于控制平面和数据平面是分离的， 路由协议出现故障后，并不会影响到已经建立的连接。 ( 3 ) 在开始传输数据之前，必须建立连接和预留资源。光网络中的路由需 要知道网络中不同资源的可用性情况。为了路由光网络中的链接，我们需要进过 加强的路由协议来处理自愿的可用性信息。 ( 4 ) 另一个差别是i p 路由时逐跳计算的，而在光网络中，路由是由源节点 计算的。 ( 5 ) 最后，另一个重要的差别就是对于保护和恢复的需求。光网络中，一 个基本特性就是大量使用预先计算好的、也是常常预先指配好的设备设备分离备 份路径来实现连接的保护。 j 不同的标准组织，例如i e t f 、i t u t ，为了增强光或者电路交换网络中的路由 和拓扑发现功能，正在扩展一些协议，例如o s p f 和i s i s 。在i e t f 开始致力于 光网络路由协议时，用于支持m p l st e 的o s p f 扩展工作已经在进行中了。这使 得扩展m p l st e 遇到的需求与光网络路由所遇到的需求之间有较多相同之处。后 来，二者互相结合，都归到了g m p l so s p ft e 扩展协议的大旗之下，简称为g m p l s o s p f t e 。下面，就来讨论此项工作并看看它们是怎样处理光网络路由的需求的。 o s p f 的扩展首先体现在链路概念的扩展上。除了使用路由器l s a 广播常规的 点到点链路之外，o s p f t e 还允许节点广播t e 链路的信息。t e 链路可以使一条 带有关联属性的绑定链路。一旦检测到某条t e 链路可用时，就可以用o s p f 的 l s a 来泛洪它的信息。 2 1 3 路由计算和路由选择 如果要在光网络中建立连接，则需要为该连接计算相应的路由并选择路径。 9 北京邮电大学硕士学位论文 在i p 网络中，每台路由器会根据数据包的目的地址独自做出转发决定，然 而，每个网络节点独自做出的路由选择决定可能会导致路由循环。因此，为了避 免路由循环的出现，同一个网络中所有的路由器都需要拥有相同的拓扑信息并使 用相同的路由算法来进行路由计算。面向连接的网络中并不会出现路由循环，以 为其中连接的路由时显式指定的，比如基于m p l s - t e 协议来创建l s p 是，显示路 由对象的使用。因此，与无连接的网络相比，在面向连接的网络中，路径选择和 其他路由功能之间的耦合就小。这使得我们可以在面向连接网络中引入更多的路 由优化标准。 假设可以通过分布式路由心灵或者网络管理系统来获得某个光网络的拓扑 和资源信息，那么，在选择连接的路径是会受到下面好几个指标的影响：如期望 连接带宽、时延、稳定性、劣化、距离、分离、资源共享、网络优化等。 从上面几点可以看出，在未连接选择合适的路由时需要考虑多个方面的因 素。根据所选用光网络技术的不同，其中一些技术回避其他技术更重要。例如， 当今s o n e t s d h 网络中的误比特率很低，这样信号劣化就不应该成为路由选择的 标准。 在实际应用中，往往从最短路径出发考虑路由选择的问题。 已知某个网络的图中每条链路都分配有距离开销，则最短路径算法可以找出 给定节点和网络中所有其他节点之间开销最少的路径。下面将介绍两种最短路径 算法。 ( 1 ) b e l l m a n - f o r d 算法 b e l l m a n f o r d 算法是一个迭代算法，它用于计算从某个指顶节点到网络中所 有其他节点之间的最短路径。在进行地k 此迭代计算时，算法会付给每个节点j 一个标签。 ( 2 ) d i j k s t r a 算法 目前最流行的域间i p 路由协议o s p f 中采用了用于寻找最短路径的d ij k s t r a 算法。和b e l l m a n - f o o d 算法一样，d i j k s t r a 算法也会向每个节点i 分配一个标 签d i 。然而，d i j k s t r a 算法中并不去迭代计算这些标签，其采用了另外一种机 制，即将迭代过程中将要操作的候选节点存储在一个列表v 中。 ( 3 ) b e l l m a n f o r d 与d i j k s t r a 的比较 对于上面给出的两种算法，哪个更好? 问题的答案需要根据具体环境而定。 比如，r i p v 2 中使用了b e l l m a n f o r d 算法的分布式，异步版本，该算法会将最 短路径计算的工作分不到协议中各台路由器上进行。在因特网中，算法的健壮性 是个很重要的因素。不幸的是，如果采用b e l l m a n - f o r d 算法，在标签没有停止 改变之前，迭代计算会一直进行下去。而在d i j k s t r a 算法中，一旦所需的目标 1 0 北京邮电大学硕+ 学位论文 节点从被候选列表中删除，迭代过程就可以立即终止。当仅需要计算部分节点的 最短路径时，该特性十分有用。在不同的网络环境下，会有一些属性能够影响到 应该选择哪种路由算法。例如，在稀疏矩阵( 即链路数远小于n 2 的网络，其中 n 为节点的数量) 中，b e l l m a n f o r d 算法的计算速度会明显加快。当把 b e l l m a n f o r d 算法和d i j k s t r a 算法同时用于网络时，可以看出，前者迭代次数 较少。 2 2 点到点最短一条路径 点到点最短一条路径的经典算法是d i j k s t r a 算法，它是目前多数系统解决最 短路径问题采用的理论基础，只是不同的系统对此算法采用了不同的实现形式。 2 2 1d ij k s t r a 算法主要思想 d i j k s t r a 算法的基本思路【4 l 【5 】是：假设每个点都有一对标号( d j ，p j ) ，其中d j 是从起源点s 到点j 的最短路径的长度( 从顶点到其本身的最短路径是零路( 没 有弧的路) ，其长度等于零) ；p j 则是从s 到j 的最短路径中i 点的前一点。求解 从起源点s 到点j 的最短路径算法的基本过程如下： 1 ) 初始化。起始点设置为： d 。= 0 ，p 。为空：所有其他点：d i = 8 ，p i = ? ： 标记起源点s ，记k = s ，其他所有点设为未标记的。 2 ) 检验从所有已标记的点k 到其直接连接的未标记的点i 的距离，并设置： d j = m i n d j ，d k + l k j 3 ) 选取下一个点。从所有未标记的节点中，选取d j 中最小的一个i ： d i = m i n d i ，所有未标记的点j 点i 就被选为最短路径中的一点，并设为已标记的。 4 ) 找到点i 的前一点。从已标记的点中找到直接连接到点i 的点j ，作为前 一点。设置：l 一= j 5 ) 标记点i 。如果所有点已标记，则算法完全推出，否则，记k = i ，转到2 ) 再 继续。 北京邮电人学硕+ 学位论文 2 2 2 已有d i j k s t r a 算法实现 从上面可以看出，在按标记法实现d i j k s t r a 算法的过程中，核心步骤就是从 未标记的店中选择一个权值最小的弧段，即上面所述算法的2 ) 一5 ) 步。这是一 个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个 链表或数组中。那么要选择一个权值最小的弧段就必须把所有点扫描一遍，在大 数量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的 做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即 可取到符合条件的点，可大大提高算法的执行效率。 另外，要进行计算，就必须首先将其按节点和边的关系抽象为图的结构。如 果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要 讨论如何用一个简洁高效的结构表示网的拓扑关系。 网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般 而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和 十字链表表示，其优缺点的比较见表2 - 1 。 名称数据结构优点