（计算机科学与技术专业论文）自适应路由策略控制技术研究与仿真实现.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外论文中不 包含其他入已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处，奉人承担一切相关责任 本人签名： 堡幽上一日期：2 弦旦：丝：翌2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期问论文工作的知识产权单位属北京邮电大学学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书菲保密论 文注释：本学位论窑不属于保密范围，适用本授权书。 本人签名：簦丝勉日期：圭里1 2 ：丝：2 2 导师签名： 日期：趁 q ：丛：之2 一 北京邮电大学硕士研究生毕业论文 自适应路由策略控制技术研究与仿真实现 摘要 随着固定网络基础设施战略地位的日益提高，增强其在战争、大 规模自然灾害等极端环境下的网络生存能力成为一项亟待解决的战 略任务。“快速重构的抗毁路由技术研究 项目组的目标是在现有i p 网络框架中设计种自适应路由策略控制技术( c o n g n i t i v er o u t i n g t e c h n o l o g y ，c r ) ，用于监控网络实际状况，并根据实际网络状况选择 对应策略，对运行的路由协议进行调整来改变路由收敛速度，使其具 备更强的自适应网络状态变换能力，从而提高网络的生存能力。 本论文课题内容是研究自适应路由策略控制技术，并实现该技术 的仿真系统，以及基于该仿真系统进行不同网络规模、故障类型场景 下的仿真试验，对其产生的网络性能进行定量分析。另外，通过基于 该仿真系统的仿真试验，可为平台开发提供优化设计方案，同时，该 仿真系统也是日后研究该技术的仿真基础平台。 本文工作价值主要体现在两个方面：第一，为了对自适应路由策 略控制技术进行可行性和可扩展性验证，以及为日后研究该技术和平 台开发提供优化设计方案，设计并开发出了相应的仿真系统。第二， 基于该仿真系统进行不同网络规模、故障类型场景下的仿真试验，并 分析和评估了自适应路由策略控制技术对网络性能的影响，最终验证 了自适应路由策略控制技术具有良好的可行性和可扩展性。 本文主要工作内容包括： ( 1 ) 对o s p f 工作原理，故障处理机制和路由收敛进行分析。 ( 2 ) 深入分析s s f n e t 仿真平台以及o s p f 协议模块实现。 ( 3 ) 介绍项目组提出的自适应路由策略控制技术，并给出基于 s s f n e t 平台下有关该技术的仿真系统设计和实现的详细内容。 ( 4 ) 在极端网络环境下，进行是否加载该控制技术模块的对比 仿真试验，并对仿真结果做出了深入分析。 关键词：路由策略网络生存性s s f n e t 仿真自适应控制 北京邮电人学硕士研究生毕业论文 一一- n 北京邮电大学硕士研究生毕业论文 r e s e a r c ha n ds i m u i 汀i o ni m p l e m e n t 盯i o no f s e l f a d a p t i v er o u t i n gp o l o c yc o n t r o l t e c h n o l o g y a b s t r a c r w i t ht h ei n c r e a s i n gi m p o r t a n c eo ft h ef i x e dn e t w o r ki n f r a s t r u c t u r e ，i t h a sb e e nas t r a t e g i ct a s kt oi m p r o v et h en e t w o r ks u r v i v a b i l i t yi nt h ew a r ， l a r g e - s c a l e n a t u r a ld i s a s t e r s ”s u r v i v a b i l i t yr o u t i n gr e s e a r c ho f f a s t r e c o n s t r u c t i o n p r o j e c tt e a m sg o a li st od e s i g n ，i nt h ef r a m e w o r k o ft h e e x i s t i n gi pn e t w o r k ，as e l f - a d a p t i v er o u t i n gp o l i c yc o n t r o lt e c h n o l o g y ， w h i c hi su s e dt om o n i t o rt h ea c t u a ls i t u a t i o no ft h en e t w o r k , a n dt h e n s e l e c tt h ec o r r e s p o n d i n gp o l i c yt oc o n t r o lr o u t i n gp r o t o c o l st oa d j u s tt h e r o u t i n gc o n v e r g e n c ep r o c e s s ，i n o r d e rt o i m p r o v e t h en e t w o r k s u r v i v a b i l i t y t h ed i s s e r t a t i o ns t u d i e dt h es e l f - a d a p t i v er o u t i n gp o l i c yc o n t r o l t e c h n o l o g ya n dd e v e l o p e d ap r o t o t y p es i m u l a t i o ns y s t e mb a s e do n s s f n e tm o d e l s a d d i t i n a l l y ，s i m u l a t i o ne x p e r i m e n t sa r ec a r r i e do u t ， w h i c hv e r i f yt h ef u n c t i o n a l i t ya n dp e r f o r m a n c eo ft h i st e c h n o l o g y t h em a i nc o n t e n t so ft h i sd i s s e r t a t i o na r ea sf o l l o w i n g ： ( 1 ) ad e e pa n a l y s i so ft h ef a u l t h a n d l i n gm e c h a n i s m sa n dr o u t i n g c o n v e r g e n c eo fo s p f i sc a r r i e do u t ( 2 ) ad e t a i l e di n t r o d u c t i o ni sm a d et ot h ei m p l e m e n t a t i o nm e c h a n i s m o fs s f n e ts i m u l a t o r ，a sw e l la so s p fp r o t o c o lm o d u l ei ni t ( 3 ) t h es e l f - a d a p t i v er o u t i n gp o l i c yc o n t r o lt e c h n o l o g yw a ss t u d i e d a n dt h ec o r r e s p o n d i n gs i m u l a t i o ns y s t e mw a sd e v e l o p e do ns s f n e t ( 4 ) s i m u l a t i o ne x p e r i m e n t si nt h es c e n a r i o so fd i f f e r e n tn e t w o r ks i z e a n df a i l u r et y p ew e r ec a r r i e do u tt ov e r i f yt h ef u n c t i o na n dp e r f o r m a n c e o ft h es e l f - a d a p t i v er o u t i n gp o l i c yc o n t r o lt e c h n o l o g y m 北京邮电大学硕l 上研究生毕业论文 一一一 k e y w o r d s ：r o u t i n gs t r a t e g y ，n e t w o r ks u r v i v a b i l i t y ，s s f n e t s i m u l a t o r ，s e l f - a d a p t i v ec o n t r o l i v 北京邮电大学硕上研究生毕业论文 第一章绪论1 1 1 研究背景1 1 2 本文研究工作。2 1 3 章节介绍3 第二章o s p f 路由协议研究4 2 1o s p f 路由协议概述。4 2 1 1o s p f 路由协议产生背景一一4 2 1 2o s p f 路由协议特性。5 2 2o s p f 基本工作原理6 2 2 1 层次化路由设计。7 2 2 2o s p f 工作过程9 第三章o s p f 故障处理机制与路由策略控制技术研究1 0 3 1o s p f 故障处理机制研究1 0 3 1 1o s p f 故障处理概述1 0 3 1 2o s p f 故障检测机制1 l 3 1 3o s p f 故障信息处理1 2 3 1 4o s p f 路由收敛特性及局限性1 3 3 2 自适应路由策略控制技术研究1 5 3 2 1 基于网络破坏度的自适应路由策略控制技术1 5 3 2 2c r 系统功能需求分析。1 7 3 2 - 3c r 系统实现策略分析1 8 第四章网络仿真工具s s f n e t 介绍2 4 4 1s s f n e t 仿真器概述。2 4 4 2s s f n e t 层次结构模型。2 4 4 3s s f n e t 源代码组织结构。2 5 4 3 1s s f ：o s 。2 6 4 3 2s s e n e t 。：7 4 4o s p f 在s s f n e t 中的实现。2 8 4 4 1 网络类型支持。2 8 4 4 2 组播功能支持2 8 4 4 3 分组发送触发条件2 8 v 北京邮电大学硕： 研究生毕业论文 4 4 4 接口状态支持2 8 4 4 5 区域范围支持2 9 4 4 6 定时器时间参数2 9 第五章自适应路由策略控制技术仿真系统设计与实现3 3 5 1c r 仿真系统开发运行环境3 3 5 2c r 仿真系统概要设计3 4 5 2 1c r 仿真系统功能模块介绍3 5 5 2 2c r 仿真系统接口功能介绍3 6 5 3c r 仿真系统详细设计与实现3 6 5 3 1c r 详细设计与实现说明。3 7 5 3 2c r 基本工作流程设计3 8 5 3 3c r 主模块设计与实现4 0 5 3 4 故障检测模块设计与实现。“ 5 3 5 破坏度计算模块设计与实现5 1 5 3 6 链路状态数据库同步模块设计5 4 5 3 7 策略选择模块设计5 7 5 3 8c r 仿真系统接口设计与实现5 8 第六章自适应路由策略控制技术仿真试验与结果分析。6 1 6 1 仿真试验环境6 1 6 2 仿真试验目的及场景设置6 1 6 3c r 仿真试验策略库6 2 6 4 仿真试验结果统计与分析6 3 6 4 1 仿真试验一6 3 6 4 2 仿真试验二6 5 6 4 3 仿真试验三6 8 6 5 仿真试验总结。6 9 第七章结束语和工作展望。7 0 7 1 总结7 0 7 2 下一步工作方向7 0 参考文献7 3 致谢7 6 个人简历及攻读硕士期间发表的文章。7 7 个人简历7 7 攻读硕士期间发表和录用文章7 7 v i 北京邮电大学硕士研究生毕业论文 1 1 研究背景 第一章绪论 随着计算机和通信技术的不断发展，i n t e m e t 互联网已经成为当今社会生存 发展的重要基础设施和关系国计民生的重要战略资源，然而作为一个复杂系统， 互联网生存能力面临着来自外界以及自身的各种因素威胁。 网络的生存能力是通过各种处于不同协议层次的故障处理机制来保证的。口 层通过路由协议技术自身的路由收敛来实现对故障的处理：路由协议( 链路状态 协议) 通过对链路状态信息的洪泛来确保全网所有路由器拥有一致的拓扑，并以 此通过最短路径算法计算路由，从而绕过发生故障的链路。可见，这种方式具有 很好的实用性( 几乎可以处理任何故障) 和灵活性。 在固定网上，路由结构的稳定性至关重要，为了避免由于信息不精确而造成 的误判、误操作，路由器通常延迟对链路失效和目的地不可达信息的处理，以牺 牲反应速度为代价规避风险。另外，鉴于在和平时期，固定网络的故障率被控制 在极低的水平，因此，传统路由协议采用固定运行速度来检测网络故障，传播和 维护路由信息的方式完全能够满足一般运营维护的要求。但从时间角度考虑，存 在明显的局限：当网络发生故障后大约需要十几秒钟网络才能收敛。另外，随着 职语音、视频会议和在线交易等实时应用的普及，以及网络的传输速率提高， 凭借m 路由协议自身的故障处理能力来处理各种故障的局限性与日凸显。 根据快速故障处理的需求，以及结合i p 故障建模研究结果：文献【1 2 】对s p r i n t 骨干网口链路故障进行了研究，其研究发现大多数故障属于持续时间较短的单 链路故障，研究人员提出了各种快速故障处理技术【孓1 7 】，这些技术可以分为两类： 反应式技术( r e a c t i v e ) 1 3 - 9 1 和先应式技术( p r o a c t i v e ) 1 0 - 1 7 】。反应式技术在检测 到故障后重新计算新的路由，适合处理持续时间长、影响范围广的故障，但需要 较长的恢复时间。先应式技术的特点是根据可能的故障提前计算备份路径，作为 路由收敛期间的过渡性措施，以保证网络状态迁移期间网络性能不受影响，因此 适用于对瞬时故障的处理。 虽然上述方法一定程度上为提高网络故障处理能力提供了保证，但这些方法 主要是针对常见的单链路故障，下面仍有两个问题需要亟待解决： ( 1 ) 极端环境下的故障处理：在极端情况下( 如地震、战争) ，即出现的攻 击、故障、意外事件在时间和空间上对网络的破坏范围比较大的一类故障场景， 这时多条链路或多节点会同时出现故障，并且故障具有间隔时间短，并发性强的 第1 页 北京邮电火学硕上研究生毕业论文 特征，那么，通过提前计算备份路径的方法由于扩展性问题在处理此类故障时候 存在局限。而通过只具有单一路由策略的反应式动态路由也无法有效处理这种复 杂多变的网络故障类型，因为，传统路由协议以固定速度来维护路由信息，并不 能参考网络的实际状况来调整路由信息收敛速度，这就导致在网络遭受到极大破 坏后也不能加快其路由收敛速度使网络快速恢复到一个稳定状态，从而增大了故 障恢复时间，降低了网络故障处理能力，使其不能适应网络故障类型多变的极端 环境。 ( 2 ) 网络故障评估机制：为了实现快速路由收敛，现有加快网络故障处理 技术的方式多以缩短影响路由收敛速度的时间延迟为优化目标，如将路由协议的 一些计时器值调低。但是，一味地加快路由收敛速度，并不能为整个网络带来好 处，因为不同的故障处理都需要一定程度的系统资源来做保证，并且路由结构的 动态变换会导致网络性能的降低，因此，应该根据网络故障对整个网络的影响程 度来调整路由收敛。也就是说，网络系统需要一个能够对网络故障破坏程度进行 有效评估的机制，根据不同的评估结果，选择对应的路由策略来调整路由协议收 敛速度，从而使路由协议拥有在快速收敛和系统稳定性之间做出权衡的能力。 “快速重构的抗毁路由技术研究 项目组的目标就是在现有口网络框架中 设计一种自适应路由策略控制技术，用于监控网络实际状况，并根据实际网络状 况选择对应策略，对运行的路由协议进行调整来改变路由收敛速度，使路由协议 具备更强的动态自适应网络状态变换的能力，从而提高网络的生存能力。因此， 在该技术可行性论证阶段，除了需要相关理论定性论证外，还需要通过仿真系统 建模手段实现与其相应的网络仿真系统，进而利用仿真手段对其进行定量分析验 证其可行性，同时也可为平台系统设计打下坚实的基础；另外，通过该系统仿真 平台还可以进行网络模型试验为系统设计提供优化设计方案。此外，该仿真系统 也是日后研究该技术在大规模、复杂环境中网络性能等的必要基础性平台。 1 2 本文研究工作 论文是本人在参加国家自然科学基金项目“快速重构的抗毁路由技术研 究”工作的基础上，总结本人在项目研究和开发过程中的工作内容而成，论文以 项目组提出的自适应路由策略控制技术，s s f n e t 仿真框架下协议模块设计与实 现机制，以及o s p f 路由协议快速故障处理机制为研究内容，主要包括如下几个 部分： ( 1 ) 收集、翻译和阅读国内外大量有关网络故障类型，快速路由收敛技术 等研究文献资料，对固定口网o s p f 路由协议工作原理，故障处理机制，路由 收敛过程，路由收敛影响因素进行了深入分析。 第2 页 北京邮电大学硕士研究生毕业论文 ( 2 ) 研究具有良好可扩展性的s s f n e t 仿真框架，以及所包含的o s p f 路由 协仿真模块，归纳总结该模块在仿真系统中所支持的影响o s p f 收敛的定时器时 间参数，为自适应路由策略控制技术调整o s p f 路由收敛做前期准备。 ( 3 ) 研究项目组所提出的自适应路由策略控制技术，基于s s f n e t 仿真框架 设计并实现其仿真系统。 ( 4 ) 利用所实现的自适应路由策略控制技术仿真系统进行大规模网络、并 发链路故障场景下的仿真试验，验证其实施的可行性和可扩展性，以及研究其在 不同网络损伤情况下的网络性能。 本文内容主要基于如下网络场景： ( 1 ) o s p f 路由协议采用分层路由设计思想，将自治系统进一步化为若干 个区域( a r e a ) ，本文除非特殊说明，否则文中网络指一个o s p f 区域范围网络。 ( 2 ) 虽然o s p f 将物理连接划分为多种类型，本课题假定节点间网络的类 型为点对点型。 ( 3 ) 在各种网络故障发生条件下，网络始终保持连通。 1 3 章节介绍 论文的第一章是绪论，第二章内容对作为自适应路由策略控制技术控制实体 的o s p f 路由协议的产生背景，协议特性以及基本工作原理进行研究性介绍。第 三章在第二章研究基础之上，对o s p f 故障处理机制和路由收敛缺陷进行详细分 析，然后，结合传统路由策略控制机制，对项目组提出的自适应路由策略控制技 术，以及实现策略做出了进行介绍。第四章对s s f n e t 仿真框架设计和实现进行 分析，为在s s f n e t 平台下实现自适应路由策略控制技术仿真系统提供前期设计 和实现基础准备。第五章则给出了基于s s f n e t 仿真框架的自适应路由策略控制 技术仿真系统设计和实现有关的详细内容。第六章设计仿真试验，并对仿真试验 结果进行统计和分析，研究自适应路由策略控制技术在大规模网络环境下的可实 施性，以及在不同网络规模，相同网络毁伤场景下的可扩展性和在相同网络规模 下，该技术能够正确实施路由策略控制的正确性。第七章对本论文进行总结，提 出了未来研究的方向。 第3 页 琴二 北京邮电大学硕上研究生毕业论文 第二章o s p f 路由协议研究 o s p f 路由协议代表了路由协议领域多年研究和实践的最高水平【3 l 它不仅 克服了r i p 的所有限制，最重要的是o s f p 拥有比r i p 更快的路由收敛速度，并 且现在被广泛应用于实际商用运营网络，所以本课题选取o s p f 作为自适应路由 策略控制技术的路由协议控制实体进行研究。 正如绪论中所述，本章主要是研究o s p f 路由协议的基本工作原理，下一章 首先就o s p f 故障检测机制，路由收敛特性进行分析，总结出其路由收敛局限性， 接着深入分析“快速重构的抗毁路由技术研究 项目组为了有效解决这个问题而 提出的自适应路由策略控制技术。 本章研究内容顺序安排如下：首先介绍o s p f 路由协议产生背景，然后对 o s p f 协议特性进行说明，最后对o s p f 基本工作原理进行介绍，以期通过本章 内容达到对为什么要设计o s p f 协议，o s p f 协议是什么以及o s p f 协议如何工 作的深入认识。 2 1o s p f 路由协议概述 随着i n t e r a c t 网络规模的不断扩大， 持，到目前为止，o s p f 逐渐取代r i p ， 网广泛采用的路由协议之一。 以及大部分厂商对o s p f 路由协议的支 已经成为i n t e r a c t 广域网和i n t r a n e t 企业 为了更好地研究o s p f 协议路由技术，本章节就其产生背景，协议特性，基 本工作原理进行介绍，以期达到对o s p f 协议产生的背后原因和路由协议技术发 展过程中代表最高理论和实践水平的o s p f 设计和优势的认知目的。 2 1 1o s p f 路由协议产生背景 任何网络技术的诞生都不是随意而为的，都是来源子真实网络世界的需求驱 动，o s p f 路由协议的产生也不例外。 网络路由协议与i n t c m e t 一样经历了一个持续不断的变化过程，而o s p f 产生的根本原因是i n t e r a c t 发展需求推动的结果。o s p f 路由协议产生的直接原 因是当时r i p 路由协议已经不能满足i n t e r a c t 的发展。 8 0 年代中期，由于r i p 协议与生俱来的固有缺点在大规模网络互联中表现 得越来越突出，其缺点主要表现在以下5 个方面： ( 1 ) 采用跳数( h o p ) 作为路由度量，忽略其它一些应考虑的因素，并且最大 第4 页 北京邮电 被限制 大小和 ( 不适应 ( 表所为 路由得不到及时的收敛。另外，在许多路由器共享一个广播网络时，路由更新容 易产生广播风暴现象。 ( 4 ) 在r i p 协议中，网络是一个“扁平网络，无层次和边界等概念，所 以当无类型域问路由( c l a s s l e s si n t e r - d o m a i nr o u t i n g ，c i d r ) 出现后，使得r i p 更加不适应大型网络的需求。 ( 5 ) r i p 由于是距离向量协议，而距离向量协议无法获知网络拓扑，也不 知道路由器是如何相连接的，使得自身无法确保无环路的路由结构。 因此，这时就需要一种新的并可完全克服r i p 协议的所有缺点的协议出现， 而o s p f 正是在这样的条件下产生的。 为了解决r i p 路由协议缺陷，1 9 8 8 年i n t e m e t 工程任务组成立了o s p f 工作 组，开始着手o s p f 协议研究和规范制定工作。有关o s p f 协议第一个版本 r f c l l 3 1 1 7 1 是在1 9 8 9 年公布的。另外，在1 9 9 1 年所公布的第二个版本基本将 o s p f 内容确立了，其后随着i n t e m e t 的发展而出现的一些新技术，比如，为了 减缓因i n t e m e t 规模不断扩大所导致的核心路由器存储路由表内存空间不足的发 展趋势而引入的c i d r 寻址方式，对o s p f 规范又做了修订，1 9 9 8 年4 月，o s p f 路由协议第二版本【1 8 l ( o s p f v 2 ) r f c 2 3 2 8 标准形式出现。又是因为i n t e m e t 的 发展，即随着i p v 卜下一代网络标准协议的产生和应用，在1 9 9 9 年1 2 月正t f 公布了r f c2 7 4 0 1 9 】协议规范o s p ff o ri p v 6 ，即o s p f 的第三个正式版本。 主要内容是基于o s f f v 2 所做的扩展修改，以对i p v 6 协议进行良好支持。 2 1 2o s p f 路由协议特性 o s p f 路由协议作为一种支持层次化路由，利用链路状态通告路由信息和最 短路径优先算法实现的自治系统内的动态路由协议，其协议特性如下： ( 1 ) 口分组封装传送闭j ：从实现的角度，o s p f 直接运行在口层，也就是 说，它并不直接使用数据链路层，u d p 或t c p 。因为这样o s p f 可以利用i p 层 分段与重组技术，从而避免了直接运行在数据链路层上所带来的麻烦，同时也减 少了利用u d p 实现而引起的附加额外消耗的8 字节头部，以及通过自身的数据 传输保证能力避免了使用t c i 实现而带来的因连接引入的较大资源开销。 第5 页 北京邮电大学硕士研究生毕业论文 ( 2 ) 层次化路由选择技术支持：o s p f 使用“区域 概念实现了一种两层 的层次化路由选择方案，可以减少a s 中路由信息扩散对网络带宽消耗和路由器 路由表体积。所以，在规划合理的前提下，它能够支持各种规模的网络，可以为 拥有数千台路由器的网络提供可靠稳定的路由选择服务； ( 3 ) 路由收敛速度快：o s p f 由于拥有完整的网络状态数据库，使得当网 络发生变化时，其收敛速度要比距离向量路由协议快，如r i p 。 ( 4 ) 无自环：o s p f 所采用的链路状态算法可以保证路由不产生自环现象。 ( 5 ) 灵活的度量值支持：o s p f 对不同的链路可根据i p 分组服务类型的不 同而将t o s 设置成不同的度量值，因此，o s p f 对于不同的数据业务类型计算出 不同的路由，这种灵活性是r i p 所不具有的，这意味着对于任何目的，可以有多 个路由表表项，每个表项对应着一个口服务类型。 ( 6 ) 良好的负载均衡支持：当对同一个目的地址存在着多个相同度量值的 等价路由时，o s p f 可以利用这些路由实现流量分配。我们称之为流量负载均衡。 ( 刀支持所有类型地址编制：o s p f 支持变长子网掩码，c i d r 以及汇总功能。 ( 8 ) 组播发送：在支持组播发送能力的链路上以组播发送方式发送路由通告 信息，最大程度地节省网络带宽，减少与上层数据业务对网络资源的争用。 2 2o s p f 基本工作原理 o s p f 是一种支持层次化路由选择，建立在链路状态算法和s p f 算法基础之 上的自治系统内部的自适应路由协议。链路状态路由协议要求每个路由器都维护 一个用于描述整个网络拓扑结构的分布式、冗余的链路状态数据库( 1 i n k s t a t e d a t a b a s e ，l s d b ) 。它是路由器进行路由计算的输入。l s d b 存储的内容是由每 一个路由器创建的用于描述其局部连接拓扑的链路状态通告( l s a ) 组成，而这 些l s a 是通过一个。可靠的泛洪过程 分发到特定区域其它路由器上获得的。 一个区域内的路由器需要达成对l s d b 的同步，只有这样，链路状态协议的路由 计算才能保证路由结构是正确，且无环的。o s p f 依靠h e l l o 协议，e x c h a n g e 协 议和f l o o d i n g 协议来完成路由器之间信息交互，最终实现同一区域内所有路由器 之间的l s d b 同步。 另外需要说明的是，随着互联网络规模的增长，用于网络管理和控制所需要 的资源也会随之增长。那么，在口网络中，与路由协议相关的资源包括： ( 1 ) 路由表和其他路由协议数据所占用的路由器内存空间。在o s p f 网络 中，“其他路由协议数据 包括o s p f 链路状态数据库。 ( 2 ) 用于计算路由表及实现其他路由协议功能所使用的路由器计算资源。 在o s p f 网络中，这些资源包括计算最小路径树所需要的c p u 时间。 第6 页 北京邮电大学硕士研究生毕业论文 ( 3 ) 分发路由协议数据所用链路带宽。在o s p f 网络中，这些资源包括o s p f 数据库同步过程所消耗的带宽。 本章节会从o s p f 用于处理网络规模发展与资源需求之间平衡问题所采用 的层次化路由设计方案和o s p f 工作过程两方面来概述o s p f 基本工作原理。 2 2 1 层次化路由设计 当o s p f 网络规模达到上千台路由器互联时，相应的路由器的l s d b 也将存 储成千上万的l s a 路由信息。同时假如o s p f 还采用“扁平网络 的路由选择 方案，即在原有网络中每增加一个网段，路由表就会增加一个表项，那么路由器 路由表长度将会呈线性趋势增长，最终会使网络增长所需要的资源得不到满足。 世界范围的i n t c m e t 采用层次化路由选择来解决这一棘手问题。因为层次化 路由方案能避免“扁平网络”的弱点：在一个扁平网络结构中，网络中的每个交 换节点都需要维护一个有关整个路由域，甚至多个路由域的网络拓扑路由表。这 对于大型网络来说几乎是不可能的，而路由分层的概念能够将路由表的增长速度 降到与网段数目对数成正比的水平，进而大大改善了这种大型网络的伸缩能力。 i p 子网化和c i d r 编址方式是实现球网层次化路由的主要工具。o s p f 作为 路由协议，为了适应i n t e r a c t 的发展需要，它除了支持c i d r 编码方式外，还通 过“区域 的概念实现了具有层次化的路由选择功能。 l s 1 s 图2 - 1 典型o s p f 层级路由 如上图2 - 1 所示为一典型o s p f 协议分层结构，它通过配置区域实现两层的 层次化路由选择方案。 第7 页 北京邮电人学硕士研究生毕业论文 o s p f 通过区域机制实现将一个大型网络( a s ) 分割成多个小型网络( a r e a ) 的能力被称为分层路由，这些被分割出来的小型网络就称为“区域 ( a r e a ) ，并 且区域之间的网络拓扑结构对于自治系统的其余区域部分是不可见的，从而减少 了网络中路由信息量的扩散范围。同时，域内的路由只由区域本身的网络拓扑结 构决定，而不受域外的错误信息的影响。 随着区域概念的引入也带来了o s p f 的路由器类型的多样性和复杂性。 基于区域的不同分类将路由器划分为如下四种类型： ( 1 ) 内部路由器：所有接口同处于一个区域内的路由器称之为内部路由器 ( i n t e r n a lr o u t e r ，瓜) ，该类路由器只需要维护一个有关本区域的l s d b 即可。 ( 2 ) 区域边界路由器( a r e ab o r d e rr o u t e r ，a b r ) ：将属于多个区域的路由 器称为区域边界路由器，一般作为一个区域的出口。它需要为每个所连接的区域 建立l s d b ，同时，还负责将所连接区域的路由汇总信息发送到骨干区域，而骨 干区域上的a b r 则负责将这些信息发送到各个区域。o s p f 路由协议对a b r 有 如下规定：至少有一个接口配置到区域o ，并至少有一个接口配置到非0 区域内 中的路由器。并且a b r 需要为每个区域存储一个l s d b 。 ( 3 ) 骨干路由器：o s p f 定义了一个比较特别的区域，该区域编号为0 ，我 们称之为骨干区域( b a c k b o n e ) ，并且要求所有的区域都与骨干区域相连，骨干 负责向所有的非骨干区域分发路由信息。另外就是，骨干必须在逻辑上是连续的。 与其他区域一样，在主干之外的拓扑结构是不可见的。我们将具有连接主干区域 接口的路由器称之为骨干路由器。骨干路由器包括所有的区域边界路由器，但是 并非所有的骨干路由器都是区域边界路由器。 ( 4 ) 自治域系统边界路由器( a u t o n o m o u ss y s t e mb o u n d a r yr o u t e r ，a s b r ) ： o s p f 是一种i g p ，当需要与某一a s 中的路由器通信时，就要求o s p f 路由域 中的路由器与该a s 中的路由器交换路由信息，我们将承担该任务的路由器称为 自治系统边界路由器。o s p f 对a s b r 有如下规定：在区域o 内至少有一个路由 器专门和本自治域以外的其它自治域系统交换信息的路由器。 如上所述，从中抽取出下列在以后讨论中会用到的简短性结论： ( 1 ) 不同的区域的链路状态数据库是各自独立的。 ( 2 ) 所有在同一个域中的路由器的链路状态数据库的内容是一致的。 ( 3 ) 不同的域的链路状态数据库的最短路径优先算法是分开运算。 ( 4 ) 区域限制链路状态通告传送的范围。 ( 5 ) 路由器的路由器标识在同一个o s p f 路由协议网络中必需唯一。 第8 页 北京邮电大学硕上研究生毕业论文 2 2 2o s p f 工作过程 与大多数p 协议一样，o s p f 路由器以协议分组的方式进行通信。当路由器 接收到一个婵协议号为8 9 的i p 分组时，路由器就知道该分组包含了o s p f 数 据，然后剥去口首部，路由器就得到了一个o s p f 分组。 o s p f 协议总共有如下五种分组： ( 1 ) h e l l o 分组，其功能是用于发现邻居，并保持邻居关系。 ( 2 ) 数据库描述分组( d a t a b a s ed e s c r i p t i o np a c k e t s ，d d ) ，其功能是用于 描述本地链路状态数据库( 1 i n ks t a t ed a t a b a s e s ，l s d b ) 的情况。 ( 3 ) 链路状态请求分组( l i n k s t a t er e q u e s tp a c k e t s ，l s r ) ，其功能是用于 向对端请求链路状态通告分组。 ( 4 ) 链路状态更新分组( l i n k s t a t eu p d a t ep a c k e t s ，l s u ) ，其功能是用于 承载一个或多个链路状态通告分组，然后向对方发送更新链路状态通告分组。 ( 5 ) 链路状态应答分组( l i n k s t a t ea c k n o w l e d g m e n tp a c k e t s ，l s a c k ) ，其 功能是用于对收到的链路状态更新分组进行确认。 实际上，o s p f 路由协议整个工作过程按照功能可划分为四部分：h e l l o 协议， 交换协议，扩散协议和最短路径计算算法。 下面是有关o s p f 三个子协议和最短路径优先算法的描述性介绍。 ( 1 ) h e l l o 协议：所有路由协议都为路由器提供一种发现、建立和保持邻居 关系的方法。在o s p f 中，路由器可以通过周期性地向其所有接口发送h e l l o 分 组来实现该功能。默认情况下，路由器每1 0 秒向接口发送一个h e l l o 分组，并 且这个发送间隔可以通过o s p f 参数h e l l o i n t e r v a l 来设置。 ( 2 ) 交换协议：又称之为e x c h a n g e 协议。相邻路由器之间通过h e l l o 协议 刚建立完邻接关系后，就要通过交换协议来交换l s d b ，以实现两相邻路由器之 间数据库的最初同步。 ( 3 ) 扩散协议：又称之为f l o o d i n g 协议。当一个路由器希望更新自己所产 生的l s a 时，它会将更新后的l s a 在整个路由域中泛洪，从而实现整个o s p f 区域内所有路由器l s d b 同步。而实现这种同步的方式被称为“可靠泛洪过程”。 ( 4 ) 最短路径优先算法：o s p f 以l s d b 作为d i j k s t r a 算法的输入来计算最 短路径树。由于l s d b 中既包含区域内l s a ，又包含区域间l s a ，还包含有关 a s 相关的信息的l s a 。所以其计算过程通常分为三步进行。 第9 页 北京邮电大学硕j ：研究生毕业论文 第三章o s p f 故障处理机制与路由策略控制技术研究 故障处理技术可以在网络的不同层面中实现，i p 层实施故障处理具有较低 的成本，以及灵活性等方面的优势【2 1 l i 勿。这其中的主要原因是口层的路由协议 自身可以通过动态性的路由收敛实现对故障的处理。但是口路由协议自身在故 障处理方面速度缓慢，因此，近些年来，国际学术界对如何提高故障恢复速度成 为学术界研究的热点问题，并将加快m 路由收敛列为缩短故障恢复时间的一种 直接有效的解决途径。 为了提高网络的故障处理能力，通过调整影响o s p f 快速收敛速度的时间参 数配置来实现对故障的快速处理是一种较好的选择，但是，有关这种方法的研究 主要是在单链路，单节点故障场景下，而对于多链路多节点故障的并发故障场景 的研究比较少。 本章首先研究o s p f 路由协议故障处理机制，然后对o s p f 路由收敛过程进 行分析，总结其在故障处理时存在的问题，最后就“快速重构的抗毁路由技术研 究 项目组提出的自适应路由策略控制技术进行分析和研究。 3 1o s p f 故障处理机制研究 3 1 1o s p f 故障处理概述 o s p f 路由收敛( r o u t i n gc o n v e r g e n c e ) 是指在一个a s 中，当网络状态改 变时，所有路由器都获知这以改变并更新其各自l s d b ，并进行s p f 计算和完成 更新路由表以及转发表的过程。简单地说就是，o s p f 路由收敛是指o s p f 路由 域中的各个路由器从一个路e h 转发状态到另个路由转发状态之间的转换。 一般来讲，当网络发生故障时，o s p f 路由收敛时间不包括故障检测时间， 而仅指从首次发现故障时刻到o s p f 路由域内所有路由器都重计算路由避开故 障以及更新完转发表之间的时间间隔。为了讨论的简单性，本文将故障检测过程 看做路由收敛过程的一部分。 o s p f 路由协议通过路由收敛过程能够在口层处理网络中出现的各类故障， 其处理过程按时间先后顺序可分为三个阶段：故障发现阶段，故