（通信与信息系统专业论文）ason控制平面中分层路由的研究.pdf

论文题目： 专业： 硕士生： 指导老师： a s o n 控制平面中分层路由的研究 通信与信息系统 牛丽 王亚民 摘要 ( 签名)生亟 ( 签名) 三坐么 自动交换光网络( a s o n ) 被公认为下一代传送网络的基础，而分层结构a s o n 是 现阶段自动交换光网络理论与技术研究的重点。本文在对a s o n 体系中的域内路由协议 0 s p f 进行研究基础上，提出了一个基于g m p l s 扩展的0 s p f 协议实现模型，并实现 了仿真。同时本文对分层路由协议实现的关键技术进行研究，针对其中的网络拓扑聚合 提出了改进算法，借助于仿真验证了其性能。 本文主要内容包括以下几点： 1 研究g m p l s 协议对o s p f 协议的扩展，并对基于o s p f 的域内路由协议模块进 行了设计。其中包括接口状态机，邻居状态机的设计，链路状态数据库的维护及路由计 算模块的设计等，并通过仿真得以实现。 2 分析了分层路由协议设计的一些关键技术和难点，针对这些问题，提出了域问路 由模块的设计流程。 3 在对已有拓扑聚合算法研究的基础上，提出一种适用于分层波长路由光网路的拓 扑聚合方案。并借助仿真技术进行了算法性能研究，证明算法完成拓扑聚合的准确性高， 信令网负担小，链路状态广播( l s a ) 消息传输延时对分层网络连接请求阻塞率的影响轻。 关键词t 自动交换光网络；最短路径优先；通用多协议标签交换；分层路由； 拓扑汇聚；遗传算法 研究类型：理论研究 s u b j e c t ：r e s e a r c ho fh i e r a r c h i c a lr o u t i n gp r o t o c o li na s o n c o n t r o lp a n e l s p e c i a l t y ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e：n i ul i i n s t r u c t o r ：w a n gy a m i n g a b s t r a c t ( s i g n a t u r e ) ( s i g n a t u r e ) mh a sa u t o m a t i c a l l ys w i t c h e d o p t i c a ln e t w o r k ( a s o n ) h a sb e e nd e f i n e d a st h en e x t g e n e r a t i o n u n i v e r s a l t r a n s p o r tn e t w o r k ，t h et h e o r e t i c a la n dt e c h n o l o g i c a lr e s e a r c h o n t l i e r a r c h i c a la s o nb e c o m e so n eo ft h ek e yt o p i c sr e c e n t l y t h i st h e s i s p r e s e n t sa n d i m p l e m e n t st h em o d e lo ft h eo s p fb a s e do ng m p l s a t t h es a m et i m e ，t h r o u g ht h e o r e t i c a l a n a l y s i so ft h er o u t i n gp r o t o c o li nt l i e r a r c m c a ja s o n ，a ni m p r o v e dt o p o l o g ya g g r e g a t i o n s c h e m ei sp r o p o s e d ，w h i c hs h o w sb e t t e rp e r f o r m a n c eb ys i m u l a t i o n t h i st h e s i si so r g a n i z e da sf o l l o w s ： _ u n d e rt h ed e e ps t u d yo fo s p fb a s e do ng m p l s ，d e s i g n sa n di m p l e m e n t st h e f u n c t i o n so ft h eo s p fp r o t o c o li n c l u d i n ga d j a c e n tr e l a t i o n sm a i n t e n a n c e ，l s a f l o o d i n ga n dt h el s a d a t a b a s em a i n t e n a n c e f o c u so nt h ek e yp o i n t si nt h ed e s i g no ft h er o u t i n gp r o t o c o li n h i e r a r c h i c a la s o n ， ad e s i g nf l o wi sp r o p o s e d _ al 【i n do fi m p r o v e d t o p o l o g ya g g r e g a t i o na l g o r i t h ms u i t a b l e f o rh i e r a r c h i c a l w a v e l e n g t hr o u t i n go p t i c a ln e t w o r k si sp r o p o s e db a s e do nt h ea n a l y s i so fs e v e r a l c o m m o nk i n d so fa g g r e g a t i o na l g o r i t h m s i m u l a t i o n sw i t hr a n d o m l y g e n e r a t e d n e t w o r k ss h o wt h a tt o p o l o g yi n f o r m a t i o nc o m p r e s s i o nc a nb ea c h i e v e d 、析t hal i t t l e l o s so fi t sa c c u r a c y r e s u l t sa l s oi n d i c a t et h a tt h ea d v a n t a g eo ft h i sa l g o r i t h mi sa l s o b e h a v e do nr e d u c i n gt h ea m o u n to fl i n k - s t a t e a d v e r t i s e m e n tm e s s a g e sa n dm a k i n g n e t w o r k sl e s sv u l n e r a b l et ot h e p r o p a g a t i o nd e l a y o ft h e s e m e s s a g e s o v e r c o m m u n i c a t i o nl i n k s k e y w o r d ：a s o n o s p fg m p l sh i e r a r c h i c a lr o u t i n gt o p o l o g ya g g r e g a t i o ng a t h e s i s ：t h e o r yr e s e a r c h 妻料技夫学 学位论文独创性说明 本人郑重声明；所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：牟雨 日期： 2 o o q 占8 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：- k 丽 指导教师签名：二溉 卅年7 月厂p 日 1 绪论 1 1 论文的目的及意义 1 绪论 在当前以i p 为主的数据业务快速增长和电信市场竞争日趋激烈的形势下，传统的 光网络已经不能适应用户的需求，迫切需要一种能提供动态的连接管理，具有基于格状 拓扑的保护和恢复功能的，具有更强的抗毁能力的，能为用户提供不同带宽和不同q o s 的区分服务，以及能提供和快速部署多种增值业务的新型光传送网 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 ) t 1 1 。 a s o n 是一种“通过能提供自动发现和动态连接建立功能的分布式( 或部分分布式) 控制平面，在o t n 或s d h 网络之上，实现动态的、基于信令和策略驱动控制的网络。 它除继承了传统光网络的主要特点以外，还具备以下一些突出优点： ( 1 ) 智能光网络可实现流量工程要求，允许将网络资源动态、合理地分配给网络的 连接。 ( 2 ) 智能光网络具有灵活得多样的恢复能力，使网络出现故障是仍能维持一定质量 的业务，特别是能实现分布式快速恢复能力。 ( 3 ) 智能光网络能很好的利用光层资源满足数据业务动态、灵活的连接请求，提供 了一个响应快、成本低的智能化底层光传输网络。 ( 4 ) 智能光网络可提供多种新型的光层业务，如按需带宽分配( b o d ，b a n d w i d t ho n d e m a n d ) 和光虚拟专用网( o v p n ，o p t i c a lv i r t u a lp r i v a t en e t w o r k ) 业务等。 自从i t u t 提出a s o n 的概念以后，对于a s o n 的研究便迅速展开，不仅各国科研 单位组建了中、小规模的试验平台对a s o n 进行系统实验和功能验证，各大设备供应商 和网络运营商也不失时机的推出各自的a s o n 产品和a s o n 实施方案。在国内，国家 8 6 3 计划把“自动交换光网络”列入重要研究课题，中兴、华为、烽火通讯等电信设备 厂商也在进行支持a s o n 网络的产品研发，并实现了商用。 纵观a s o n 的发展历程和现状，可以发现：一方面，a s o n 体系结构的核心是其引 入的智能控制平面，确保该控制平面实现智能的关键是该平面中信令，路由和资源管理 三个主要模块的协调合作。另一方面，随着网络规模的不断扩大，为保证a s o n 网络的 可扩展性，采用分层的路由体系结构已成为必然。 本论文将对分层结构a s o n 中控制平面的一些关键技术，包括域内路由协议模块的 设计，拓扑聚合算法的设计，以及域问路由协议的设计等，进行了比较深入的研究。 西安科技大学硕士学位论文 1 2 国内外研究现状和进展 目前，对于a s o n 标准进行研究的国际标准组织和准标准组织主要有国际电信联盟 标准部( i t u n 、光互连论坛( o i f ) 、互联网工程任务组( i e t f ) 、光域业务互连( o d s i ) 等。 其中i t u t 、i e t f 、o i f 分别为智能光网络研究制订了一系列标准规范和草案，而且研 究也在不断的进行中。 i t u t 主要负责网络体系结构，网络性能和设备功能要求，以及物理层规范等的制 定，i t u t 也规范信令和协议。从标准的成熟度来看，在体系结构方面，i t u t 已经给 出了比较完善的a s o n 体系结构，对于控制平面，i t u t 关于信令的标准化已经基本完 成【2 1 。其标准化草案如图1 1 所示。 各标准具体内容如下表所示： 一一一一一一一一一一一一一具 蓁 图1 1a s o n 协议体系架构 表1 1 a s o n 标准和内容 详细 要求 虽然i t u t 制订了以上完善的规范，但却没有对实现控制平面各功能的具体细节进 行规定，这就给了科研机构以及设备提供商一定的自由发挥余地。在a s o n 的具体功能 2 1 绪论 实现方面。i e t f 和0 1 f 则做了大量的工作。到目前为止，i e t f 的广义多协议标签交换 ( g m p l s ) 协议族以及o i f 的用户一网络接口( l j n i ) 、网络一网络接l i ( n n i ) 规范已被用来 实现a s o n 的基本功能。如表12 所示： 表1 2a s o n 标准及可行的协议实现 a s o n 相麻标准 控制平面协议实现 标签分发协议l d p ，资源预留协议r s v p ，用户一 分布式呼叫和连接管理f g 7 7 l 圳)网络接口u n i 网络一网络接口n n i 自动拓扑以及资源发现( g 7 7 1 4 4 ) 链路管理协议l m p ，标签分发协议l d p 开放最短路优先算法o s p f 中间系统一中间系统 路由功能( g 7 7 1 5 t 5 b 协议i s i s 边界网关协议b g p ，域问路由协议 d d r p 对于a s o n 的研究正在全世界如火如荼地进行，各国的科研单位和电信运营公司也 搭建了各自的a s o n 试验平台，其中包括； 欧洲l i o n 计划1 6 】，该项目实现了不同厂家设备的互联，而且完成光网络交换设 备( o x c ，o a d m ) 与i p 网络吉比特路由器( g s r ) 的联合组网。该实验网络拓扑如图1 2 所示。 削12l i o n 网络拓扑 - 清华大学a s o n 试验平台1 7 1 ，宴现了从传统s d h + d w d m 光网络向智能光网络 a s o n 的过渡。该实验网络拓扑如图1 3 所示。 西安科技大学硕士学位论文 图1 3 清华人学a s o n 试验平台拓扑 o i f 组织的全球5 个国家7 大运营商的互联互通测试【歌9 】，完成了u n i 、n n i 接口 规范的测试，为不同厂商、不同运营商的a s o n 解决方案的无缝互联提供保障。 总的说来，a s o n 研究已经取得了很大的进展，已经验证了全光网络o x c 、o a d m 和i p 网络吉比特路由器( o s r ) 联合组网的可能性以及从传统光网络( s d h + d w d m ) 平滑过 渡到a s o n 的可行性。各大厂商推出的同趋成熟的a s o n 控制平面产品也预示着a s o n 必将取代传统光传送网，成为下一代智能光传送网的规范。但是，现有的a s o n 网络规 模都比较小( 几个或者十几个节点) ，离l t u t 的设计目标还相差甚远，国内外近期的研 究热点集中于分层a s o n 控制平面技术。随着网络规模的不断扩大，如果仍然采用单层 组网( f l a tn e t w o r k ) 方式，会产生诸如单个网络节点( l s r 或者路由器) 需要维护超大的路由 表，路由协议拓扑信息分发耗用太多信令网带宽以及网络拓扑收敛速度过慢等等，这些都 将成为大规模组建a s o n 网络的限制。针对这些问题，i t u t 提出了分层路由( h i e r a r c h i c a l r o u t i n g ) 的思想，分层路由首先在g 8 0 8 0 中提出，并在g 7 7 1 5 中进一步规范，其目的在 于解决前述的大规模组网时产生的问题。另外，i t u t 在2 0 0 3 年初对g 8 0 8 0 规范的最 新更新g 8 0 8 0 1 t 1 0 l 中，更是对分层网络和路由的内容进行了详细的论述，该最新规范中 对网络分域和分层实现时诸如拓扑抽象( t o p o l o g ya b s t r a c t i o n ) 和节点、链路汇聚( n o d ea n d l i n k a g g r e g a t i o l l ) 等技术提出了明确的建议，并规范了分层、分域网络中域内和域间控制 平面组件的接口和协调。实现分域、分层网络的关键在于域间( i m e r - d o m a i n ) 路由协议的选 取，目前在a s o n 网络中广泛得到使用的是i e t f 对o s p f 协议、i s - i s 协议和b g p 协议 的扩展，但是这些协议由于扩展性不好，对g 8 0 8 0 1 j 中提出的分层路由的支持性都不够 好，因此，对于分层路由问题的研究成为现今的热点。 1 3 本文各部分主要内容 对分层结构自动交换光网络中的一些关键技术的研究是现阶段a s o n 研究的重要 前沿。本论文将对于分层、分域a s o n 网络的域间和域内协议模块的设计，拓扑聚合算 4 = 圈f l 圈 1 绪论 法的设计等进行深入研究。本为的内容安排如下： 第1 章引言。主要介绍本课题的研究背景及现状，本文的主要安排。 第2 章a s o n 概述。对a s o n 的基本知识，关键技术，路由体系及路由协议进行 概述。 第3 章域内路由技术的研究与实现。主要研究g m p l s 协议对o s p f 协议的扩展， 并对基于o s p f 的域内路由协议模块进行了设计，并通过仿真得以实现。 第4 章域问路由技术的研究。分析了分层路由协议设计的一些关键技术和难点， 针对这些问题，提出了域问路由模块的设计流程。 第5 章拓扑聚合技术研究。在对已有拓扑聚合算法研究的基础上，提出一种适用 于分层波长路由光网路的拓扑聚合方案。并借助仿真技术进行了算法性能研究。 5 西安科技大学硕士学位论文 2a s o n 概述 2 1a s o n 网络的特点及关键技术 a s o n 由控制平面、传送平面、和管理平面组成。此前，光传送网只有传送平面和 管理平面，没有分布式智能化的控制平面，因此，a s o n 概念的提出，使得传输、交换 和数据网络结合在一起，实现了真正意义的路由设置、端到端业务调度和网络自动恢复 i l l 。a s o n 是一种分层结构，层与层之间、节点与节点之间通过相应的接口进行通信， 组成结构如图2 1 所示： r ain 1 r a ：代理请求 n n i t 内邵阿络节点援口e n ：外部州络节点接口 图2 1a s o n 的组成结构 控制平面包括一系列实现路由和信令交互等功能的特定组件。a s o n 控制平面的核 心功能之一就是可以在管理平面的控制下，利用信令功能实现端到端自动连接的建立和 删除以及其他操作的控制。控制平面是a s o n 技术的关键部分，控制平面的实现决定着 a s o n 智能化的程度。控制平面内的许多关键技术如路由技术、链路资源管理技术、生 存性技术等都是a s o n 技术研究的重点内容。 传送平面负责数据业务的传送。它具有各种粒度的交换和疏导结构，如光纤交叉连 接，波带和波长交叉连接；具有各种速率和多业务的物理接口，如s d h ，以太网接口， a t m 接口以及其他特殊接口等。传送平面实现的是一种物理数据的传输功能。控制平 面和管理平面通过相应接口与传送平面进行交互，通过这些接口，管理平面和控制平面 可以对传送资源进行统一的控制和管理。 管理平面负责传送平面、控制平面和整个系统的维护功能。它通过网络管理接口 6 2a s o n 概述 a ( n m i - a ) 管理控制平面，并协同控制模块的链路管理协议( l m p ) 完成对数据通信网 ( d c n ) 的管理。 在以上三个平面中，控制平面是网络的关键部分。在a s o n 网中，业务可以实现动 态连接，时隙资源也可以进行动态分配，还可以对底层网络进行实时控制，其原理就因 为控制平面的存在。 a s o n 的分布式智能所达到的网络拓扑发现、电路自动配置等，完全依赖与控制平 面链路资源管理、光路由和信令协议。链路管理协议( l m p ) 用于发现光网络邻居，管理 本地链路资源，并将光链路资源通过控制平面路由协议进行全网络泛洪；信令协议主要 用于控制和管理，当路由节点计算出路由后，通过信令协议进行端到端连接的建立；路 由协议的作用是在网内各个路由节点间泛洪光网络拓扑信息，使网络内部的每个路由节 点、或指定的路由节点具有全网的链路资源信息，用于条件约束路径计算。a s o n 控制 平面路由技术是整个a s o n 网络的核心技术之一。 2 2a s o n 的路由体系 2 2 1a s o n 的路由功能结构 a s o n 的路由结构由路由控制器( r c ) 、路由信息数据库( r d b ) 、链路资源管理器 ( l i 巩i ) 和协议控制器( p c ) 几部分构成f 1 2 1 ： 图2 2 路由功能组件关系 路由控制器r c 的主要功能为与对端r c 交换路由信息，并通过对路由信息数据包 的操作恢复路由查询，即路径选择。同时r c 也会对从连接控制器发出的为建立连接所 需的通道信息做出回应，对拓扑信息请求做出相应回应。 路由信息数据库r d b 主要用于存储本地拓扑，网络拓扑可达性，路由策略配置和 7 西安科技大学硕士学位论文 其他通过路由信息交换获得的信息。r d b 可以包含多个路由域的路由信息( 针对多层网 络) ，这些路由信息是进行路由计算的基础。 链路资源管理器l r m 主要功能为向r c 提供所有s n p p 链路信息，并将其控制的 链路资源的任何状态的改变告知r c 。 协议控制器p c 的功能为将路由原语转换成特定路由协议的消息，因此是与协议相 关的。 2 2 2a s o n 的路由模式 针对多域网络环境中动态光通道的建立，a s o n 路由结构提出三种路由模式：层级 路( h i e r a r c h i c a lr o u t i n g ) ，逐跳路i 扫( s t e p - b y - s t e pr o u t i n g ) 和源路 妇( s o u r c e - b a s e d r o u t i n g ) 。 ( 1 ) 层次路由模式 a s o n 从水平方向来说，一般可划分为不同的路由域( r a ) ，每个路由域又可分为不 同的子网。子网之间可以相互嵌套，一个大的子网( 上层子网) 内部可包含若干个小的子 网( 下层子网) ，形成层次的结构。每个子网都知道本身的拓扑结构并能进行动态连接控 制，但对层次结构中的上层或者下层子网的拓扑结构就不了解了。 在层次路由中，子网层次的每一级都有一个包含r c 、c c 、l r m 的主节点负责本 级子网的选路，每级主节点之间按照层次结构的关系相互作用来选择路由。如图2 3 所 示，连接请求首先到达最上层子网主节点a ，由节点a 计算出在源和目的节点之间所需 要进过的下一层子网( 包括b 、f 和c 控制的子网) 和它们之间的链路连接，然后就通知 相关的下层子网主节点b 、f 和c 分别在自己的子网内部建立对应的连接，这样由上到 下逐级子网进行分段的选路，最终得到整个连接的路由。 _ 建立连接消息 一 建立连接 ) 设备节点 n 子网 、 图2 3 层次路由模式中的连接建立信令流程 8 2a s o n 概述 ( 2 ) 源路由模式 源路由模式和层次路由有很多相似之处，但在源路由模式中，连接建立是通过分布 的节点中的c c 和r c 分段联合完成的。一条连接可能经过多个路由域，在源路由模式 中，从源节点开始连接所经过的每一个路由域，则连接的入口节点( 第1 个节点) 要负责 本路由域中的路由选择，并负责判断连接所需要进入的下一个路由域的入口节点，这样 逐个路由域进行选路，直到最终到达目的节点所在路由域。源路由模式的信令流程如图 2 4 所示。 连接建立请求 建立连接 。设备节点 路由选择模块 n 邻居管理模块 网络接口 图3 2 路由协议模块框图 路由协议模块中各子模块之间利用消息队列来进行通信。在本模块中需要创建两个 消息队列r e c e i v e d _ m a s g _ q u e u e 和s e n d _ p k _ q u e u e ，分别用来存放接收到的消息和将要 发送出去的消息。网络接口将接收到的消息放入r e c e i v e d _ m a s g _ q u e u e ，通知邻居管理子 模块进行相应的处理。邻居管理子模块把处理过程中产生的消息如链路状态通告、各种 协议分组等放入s e n d _ m a s g _ q u e u e 中，再通过网络接口发送出去。 3 2 1 邻居管理子模块的设计 邻居管理子模块实现的功能有：1 形成和维护邻居关系。通过h e l l o 协议建立自身 和其他节点的邻居关系( 包括n e i g h b o r 关系和a d j a c e n c y 关系) ，并在邻居节点之间进行链 路状态数据库的同步。同时还维护接口状态机和邻居状态机，为o s p f 路由协议模块中 其它子模块提供必要的接口和邻居状态。2 实现l s a 泛洪机制。发送和接收链路状态 更新分组，对链路状态数据库执行相应的操作，从而建立起完善的邻接关系。同时，还 提供l s a 重传机制，以利于链路状态的老化和更新。 ( 1 ) 接口状态机的实现 一个o s p f 接口可以看成是路由器与网络的一个连接，所有通过该接口的由路由器 产生的路由协议分组都印有该接口的区域i d 。路由器的一个接口可以包含一个或多个 邻接关系( a d j a c e n c i e s ) ，一个接口又可以有多种状态，接口在这些状态之间迁移，接口 1 3 西安科技大学硕士学位论文 状态的每一次变化都是由一些事件触发的。链路状态通告反映了该路由器的接口状态以 及它的邻接关系的状态。 接口状态列出如下： d o w n ：接口关闭。这是接口的初始状态。在这种状态下，接口是不可用的，所有 的接口参数都是初始值，接口定时器也是不可用的，该接口没有任何的邻接关系。 l o o p b a c k ：接口环回。在这种状态下，路由器到网络的接口是环回的，可以通过硬 件或软件对接口环回。这时，接口不能正常地接收数据。 p o i n t t o p o i n t ：点到点状态。这种状态下，接口处于激活的状态，接口与网络之间 已经建立起了点到点的物理连接，路由器将会通过定期发送h e l l o 协议分组试图与邻居 路由器建立邻接关系。 用于a s o n 的o s p f 接口的状态迁移如图3 3 所示。 图3 3 接口状态迁移图 接口状态机根据接口的当前状态和触发事件的组合形成不同的转移状态并执行不 同的操作，因此，在本文的设计中，接口状态机的入口将设计成由当前状态和接收事件 组成，出口为将导致的接口的新状态以及产生的一系列行为，如表3 1 所示。 表3 1 接口状态机函数 函数名 o s p f _ i n t e r f a c e _ m a c h i n e 输入参数1 输入参数2 功能描述 输出参数 s t r u c to s p f _ i n t e f a c e * ( - - 个指向接口状态信息的指针) o s p f _ e v e n t ( 触发事件) 根据接口状态机的当前状态和触发事件的组合，调用相应的执行函数进 行处理。 新的接口状态( 接口状态机置新状态) ( 2 ) 邻居状态机的实现 1 4 3 域内路由技术的研究与实现 邻居状态指的是本路由器与它的邻居路由器之间的关系，路由器与邻居路由器之间 最初是通过发送h e l l o 协议分组来建立邻居关系，之后进行数据库的交换，当两个节点 的数据库完全同步之后，两个节点才能建立起完全的邻接关系。o s p f 路由器的邻居状 态如表3 2 所示： 表3 20 s p f 路由器邻居状态 邻居状态表示含义 d o w n i n i t 2 - w a y e x s t a r t e x c h a n g e l o a d i n gd d f u l i 相邻连接关闭 单向通信建立 双向通信建立 协商主从关系 开始发送数据库交换分组 交换完毕 完全邻接 邻居间的状态转换也是由事件引起的，在r f c 2 3 2 8 协议规范中，定义了1 3 种引起 邻居状态转换的事件【l5 1 ，下面分别对这些事件进行描述： h e l l o r e c e i v e d收到来自邻居的h e l l o 分组 t w o w a y r e c e i v e d 双向连接建立 n e g o t i a t i o nd o n ed d分组交换过程中的主从关系协商已确定 e x c h a n g e d o n ed d分组交换完成 b a d l s r e q接收到错误的l s a 请求 l o a d i n g d o n e 数据库装载完成 a d j o k判断是否与该邻居建立邻接关系 s e q n u m b e r m i s m a t c h序列号不匹配 o n e w a y r e c e i v e d单向连接建立 k i l l n b r断绝邻居关系，邻居状态回到d o w n i n a c t i v i t y t i m e r 邻居不活动时间到 l l d o w n邻居不可达，邻居状态回到d o w n 邻居状态的变化是由事件触发的，对应不同的当前状态同一事件的触发可能产生不 同的结果。基于这一原理，邻居状态机的入口将设计成由当前状态和接收事件组成，出 口为将导致的邻居新状态以及产生的一系列行为。图3 4 是邻居状态的迁移过程，表3 3 7 是邻居状态机的实现函数。 1 5 西安科技大学硕士学位论文 图3 4 邻居状态迁移图 表3 3 邻居状态机的实现函数 函数名 o s p f _ n e i g h b o r m a c h i n e 输入参数l 输入参数2 s t r u c t _ o s p f _ n e i d h b o r * ( - - 个指向邻居状态信息的指针) o s p f _ e v e n t ( 触发事件) 功能描述根据邻居状态机的当前状态和触发事件的组合，调用相应的执行函数进 行处理。 输出参数 新的邻居状态( 邻居状态机置新状态) ( 3 ) 邻居处理子模块的处理流程 h e l l o 分组的o s p f 分组类型为1 。o s p f 路由器的所有接口都会周期性地发送h e l l o 分组来建立和维护邻居关系。为了保证邻接节点之间的双向通信，h e l l o 分组包含了一 个路由器的列表，列出了最近在网上“看到”的路由器。路由器以h e l l o i n t e r v a l 指定的 时间为周期向其邻居节点发送h e l l o 分组。h e l l o 分组的发送流程如图3 5 所示，接收流 程如图3 6 所示。 1 6 3 域内路由技术的研究与实现 ，、 ( 开 始 ) 山 按照接口配置参数填写分组，设置 h e l l oi n t e r v a l , r o u t e r d e a d i n t e r v a l 山 按照区域配置参数设置选项域中的 e - b i t 山 填写邻居列表 山 向每个邻居发送h e l l o 分组 l 山 ，、 f 结束 ) 图3 5h e l l o 分组的发送流程 1 7 西安科技大学硕士学位论文 图3 6h e l l o 分组的接收流程 1 8 3 域内路由技术的研究与实现 当路由器之间通过h e l l o 分组形成邻接关系以后，就要进行邻居链路状态数据库的 同步。路由禚通过发送数据库描述分组( d d p ) 来向它的邻居描述自己的数据库，即进行 链路状态通告。数据库描述分组描述了本路由器数据库中的一组l s a 的情况，当邻居 发现接收的数据库描述分组中的l s a 比自己数据库中的新，它就会向发送该分组的路 由器请求这些更新的l s a ，直至两个路由的数据库完全同步，继而通过泛洪机制实现域 内的路由信息同步，泛洪过程可保证同域内的所有路由器都具有相同的o s p f 数据库， 进而实现路由计算。 下面的这些事件将触发新的l s a 实例产生： ( 1 ) 路由器产生的l s a 中l s 的年龄到达了l s r e f r e s h t i m e 时限。 ( 2 ) 接口状态发生改变。 l s a 的产生流程图如3 7 ： 图3 7l s a 产生流程图 上图中指定路由器是指与所有o s p f 路由器建立相邻关系的路由器，可以通过h e l l o 数据包选出i d 最大的路由器作为指定路由，并产生n e t w o r k - l s a ，用来描述域内所有路 由器的状态信息。r o u t e r - l s a 是用来描述与路由器相连的链路信息和端口状态信息， 所有的o s p f 路由器都会产生。t e l s a 是对o s p f 协议原有的l s a 进行扩展，可以通 过表3 4 中的主要函数实现： 1 9 西安科技大学硕士学位论文 表3 4 主要函数列表 函数功能 o s p e _ _ m p l s t e l s a n e w ( ) o s p f _ m p l s t e l s a _ o r i g i n a t e ( ) o s p f _ m p l s _ t e _ l s a _ b o d y _ s e t ( ) 创建新o p a q u el s a 根据链路属性信息生成l s a 内容 构造r o u t e rt l v 和l i n kt l v 3 2 2 数据库管理模块的设计 数据库管理模块实现链路状态数据库的维护和更新。链路状态数据库存放着本区域 内所有的l s a ，经常要对这些l s a 进行查找、更新和删除，在进行数据库同步和l s a 泛洪的过程中，需要频繁地查找本地数据库以确定是否存在某个l s a ，为了提高程序的 运行效率，采用平衡二叉树来存储链路状态数据。 基于链路状态数据库构造的拓扑表应该准确的反映网络拓扑，为此需要定期更新链 路状态数据库，所以数据库中的每个l s a 都有一个l s 年龄，每隔一秒l s 就增加一秒， 当到达l s r e f r e s h t i m e 时限，该l s a 就会从链路状态数据库中被清除，路由器又会发起 新的链路状态请求分组。 在本文的设计中，将通过设置定时器来实现l s a 的老化。每个l s a 在被装入链路 状态数据库时，数据库管理进程会为其启动一个老化计数器，每隔一秒，计数器自动减 一，数据库管理进程会将计数器值为0 的l s a 从数据库中清除出去。 在前面我们提到触发新的l s a 实例产生的事件，除了l s a 的l s 到达l s r e f r e s h t i m e 时限外，还包括接口状态改变。因此在数据库管理进程中还需通过设置链路状态广播门 限值来实现新的l s a 的发起和广播。只是在此设计中忽略l s a 中的其他信息，只考虑 路由器每个出口链路的可用波长数。 首先做如下假设： 捌：链路的全波长数 w a v a i lp r i o ，：变化前链路的可用波长数 w a y 。i la f t e r 变化后链路的可用波长数 t h r e s h o m ：链路状态广播门限值 若以下满足条件，则发起并广播一个新的l s a 。 i 鲨型= 坐二鲨竺! = 丝l 砀，础。肘 ( 3 1 ) 删 2 0 3 域内路由技术的研究与实现 3 2 3 路由计算模块的设计 路由计算模块负责路由的计算及路由表的维护。在本设计中，路由表的计算采用 c s p f 算法，c s p f 是一种改进的最短路径优先算法，它是一种在计算通过网络的最短路 径时，将特定的约束( 比如，带宽需求，最大跳转数，和管理策略需求等) 也考虑进去的 算法。路由表的数据存储结构采用双链表实现，以方便维护。路由表数据结构如图3 9 。 o s p f _ r o u t e t a b l e _ i n f o 目的节点类型：d c s l 孵 目的节点标识：d c s ti d 网络掩码：m a s k 区域标识：a r e ai d 链路权值：c o s t 源点到目的节点的转发节点列表：* p a t h 图3 8 路由表数据结构 3 3 路由协议模块实现的函数 实现路由协议模块中用到的函数简单说明如下： i n to s p f _ r c v p k ( ) 输入：o s p f 分组，分组长度，接收分组的接口i d 。 输出：一个表示调用成功与否的整数，1 为成功，2 为失败。 功能：处理接收的o s p f 分组。首先检验接收消息口头部的有效性，根据接口i d 在全局接口链表中查找该接收接口数据。解析数据包的o s p f 头部，进行数据包认证和 校验和计算，最后根据数据包类型调用具体的处理函数。 v o i do s p f _ s e n d p k ( ) 输入：发送接口，发送目的地址，发送分组，分组长度。 功能：封装数据分组i p 头部，设置s o c k e t 套接字参数值，通过s o c k e t 发送数据包。 v o i do s p f _ r c v h e l l o ( ) 输入：h e l l o 分组，接收接口，分组长度，源路由器i p 。 功能：处理h e l l o 分组，首先检查h e l l o 包的参数值与本地值是否匹配，然后根据 源i p 地址在接口的邻居链表中查找发送该h e l l o 包的邻居数据，如果为空则构造新的邻 居数据，然后调用邻居状态机事件函数进行处理。 v o i do s p f _ s e n d h e l l o ( ) 2 1 西安科技大学硕士学位论文 输入：发送接口。 功能：封装h e l l o 分组及验证数据，确定发送地址，启动重传计时器，调用o s p f _ s e n d p k 发送。 v o i do s p f _ r c v d d ( ) 输入：数据库描述分组d d ，接收接口，分组长度，源路由器i p 。 功能：处理接收的数据库描述分组d d 。根据源i p 地址查找相应的邻居数据，以邻 居当前状态为条件触发邻居状态事件函数，并对d d 分组里的l s a 首部进行判断处理。 v o i do s p f _ s e n d d d ( ) 输入：发送接口。 功能：填写d d 数据分组首部，根据邻居当前状态设置标志位，根据链路状态数据 库里的信息构造d d 的内容。调用o s p f _ s e n d p k 发送。 v o i do s p fr c v l s r ( ) 输入：l s r 分组，接收接口，分组长度，源路由器i p 。 功能：处理接收的l s r 分组。根据l s r 中请求的l s a 类型，在l s d b 中查找完整 的l s a ，调用o s p f _ s e n d l s u 函数创建一个链路状态更新分组l s u ，并将完整的l s a 填入 这个l s u 。 v o i do s p f _ s e n d l s r ( ) 输入：邻居数据。 功能：填充l s r 数据分组的o s p f 首部，然后根据邻居数据里的链路状态请求信息 构造要请求的l s a 首部，填充l s a 个数由接口m t u 值确定。调用o s p f _ s e n d p k 发送。 v o i do s p f _ r c v l s u ( ) 输入：l s u 分组，接收接口，分组长度，源路由器i p 。 功能：对接收的l s u 分组进行处理。将l s u 罩的l s a 逐个取出，与l s d b 进行对 照，如果l s d b 中存在这个l s a ，选择保留较新的l s a ，如果更新了l s d b ，则需要发 送链路状态更新分组。 v o i do s p f _ s e n d l s u ( ) 输入：邻居数据，更新的l s a 列表。 功能：填充l s u 数据分组的o s p f 首部，根据输入参数中给出的l s a 列表填充具 体的链路状态公告，填充个数由接口m t u 值确定。调用o s p f _ s e n d p k 发送。 v o i do s p f _ r c v l s a c k ( ) 输入：l s u 分组，接收接口，分组长度，源路由器i p 。 功能：对接收的l s a c k 数据分组进行处理。检查l s a c k 里的应答l s a 首部，以 l s a 首部类型、l s ai d 和广播路由器这三个值为关键字查找邻居重传链表，如找到对 应的l s a ，则将这个l s a 删除。 3 域内路由技术的研究与实现 v o i do s p fs e n d l s a e k ( ) 输入：发送接口，需要应答l s a 。 功能：填充o s p f 首部，将需要应答的l s a 填入l s a c k 应答分组中。调用o s p l s e n d p k 发送。 3 4 仿真及小结 本章在对智能光网结中o s p f 协议进行研究的同时，还采用o p n e t 通信仿真软件 对路由掷议进行了仿真1 1 6 1 。在仿真过程中采用的仿真平台为o p n e t m o d e l e r 8 0 ，操作 系统为w i n d o w s x p 。仿真的网络模型为网状网。如图3 9 。