（通信与信息系统专业论文）ospfv3路由协议实现与测试.pdf

北京交通大学硕 i s 学位论 义 o s p f v 3 路山 协议实现与 测试 摘要 论文所涉及的内容是+家 “ 8 6 3 ” 重大科研项目“ 高性能i p v 6 路由器协 议栈软件” 。本论文是该项目的重要组成部分。目前该项日已经通过 “ 8 6 3 项日 组中期验收，并等待最终验收。 目 前t c p / i p 协议栈主要基于i p v 4 。随着互联网的飞速发展，用户的期 望也越来越高. i p v 4 网络己经不能从根本上满足人们对网络地址空间、 o o s , 移动性以及安全性等方面的更高要求，这使得 i p v 6技术的发展成为必然 那么研制下 一 代网络的核心设备i p v 6路由器将是一项十分重要而紧迫 的任务， 经过几年的研究与实践，2 0 0 2 年9 月，北京交通大学i p网络实验室正 式启动国家 “ 8 6 3 重大科研项目“ 高性能 i p v 6路由器协议栈软件” 。本项 日的主要目 标是面向下一代互联网的发展趋势与需求，研究高性能路由器 i p v 6 协议实现技术，自 主开发完成i p v 6 协议栈软件。 本论文作为该项目的重要组成部分，所完成的工作如下: l . i p v 6 发展趋势基础上剖析i p v 6 路由协议的优缺点。 2 .给出在 l i n u x 操作系统_ l 实现路由协议软件高性能、高稳定性、可移植 j性的关键技术。 3 .研究 o s p f v 3 协议演变过程，剖析其工作原理;给出了o s p f v 3 路由协 议软件的设计方案，重点讲述了基于 l i n u x操作系统o s p f v 3的编码实 现。 4 .深入研究软件测试理论;自 行编写i p v 6 路由协议测试方案， 给出软件实 际的测试结果。 5 .总结本论文所做工作，给出了今后o s p f v 3 协议研究的方向。 关键词:i p v 6 o s p f v 3实现测试 北 京交通人 学硕 学位论文o s p f v 3路山协议实现与测试 ab s t r a c t t h i s p a p e r i s c o n s t r u c t e d o n th e r e s e a r c h o f n a t i o n a l 8 6 3 p r o j e c t o n t h e i p v 6 p r o to c o l s t a c k f o r t h e n e x t g e n e r a t i o n o f i n t e r n e t . t h e p r o j e c t h a s b e e n s u c c e s s f u l l y a c c o m p l i s h e d a n d p a s s e d t h e m e t a p h a s e c h e c k g i v e n b y 8 6 3 e x p e r t g r o u p . a t t h e p r e s e n t t i m e , t h e t c p / i p s u i te i s m a i n l y b a s e d o n i p v 4 . v a r i o u s n e w a p p l ic a t i o n s s w a r m i n g i n t o i n t e r n e t r e s u l t i n h e a v y d e m a n d s o f t h e c o n s u m e r . t h e t r a d i t i o n a l i p v 4 i n t e rn e t c a n n o t s a t i s f y p e o p l e s r e q u i r e m e n t s f o r b i g g e r a d d r e s s s p a c e , b e t t e r q u a l i t y o f s e r v i c e , b e t t e r m o b i l i t y ,b e t t e r s e c u r i t y ,a n d s o o n . t h e n e w p r o t o c o l i p v 6 i s i n e v i t a b l e .t h e r e f o m d e v e l o p i n g t h e i p v 6 r o u t e r s w h i c h i s t h e c o r e o f t h e n e x t g e n e r a t i o n o f i n t e r n e t b e c o m e s a n u r g e n t a n d im p o rt a n t t a s k a f t e r s e v e r a l y e a r s o f r e s e a r c h a n d p r a c t i c e , i p n e tw o r k l a b o f b e i j i n g j i a o t o n g u n i v e r s i t y s t a r t u p n a t i o n a l 8 6 3 p r o j e c t 一 “ t h e p r o t o c o l s u i t e s o f t w a r e o f h i g h p e r f o r m a n c e o f i p v 6 r o u t e r , s e p t e m b e r 2 0 0 2 .wh a t w e s h o u l d d o i s t o s t u d y t h e d e v e l o p m e n t o f i p v 6 r o u t e r s a n d r e a l i z e t h e i m p r o t o c o l s t a c k f o r t h e n e x t g e n e r a t i o n o f i n t e r n e t i n d e p e n d e n t l y . b e in g a n i m p o rt a n t c o n s t i t u t e s o f t h e p r o j e c t , w h a t t h e p a p e r d i s c u s s e s is a s f o l l o ws : 1 . b a s e d o n t h e i n e v i t a b i l i t y o f i p v 6 w e a n a l y s e t h e a d v a n t a g e s a n d l i m i t a t i o n s o f i p v 6 r o u t i n g p r o t o c o l 2 . e x p l a in e t h e p r e d o m i n a n c e o f l i n u x o p e r a t i n g s y s t e m s i n d e v e l o p i n g i p v 6 r o u t e r s , f o l l o w e d b y t h e k e y t e c h n i q u e w h ic h m a k e t h e r o u t i n g p r o t o c o l h a v i n g h i g h p e r f o r m a n c e ,s t a b i l i z a t i o n a n d t r a n s f e r a b i l i t y 3 . i n v e s t i g a t e t h e e v o l u t i o n i s m a n d w o r k fl o w s o f o s p f v 3 ;p r e s e n t e t h e b l u e p r i n t o f o s p f v 3 , a n d t h e n f u l l y d i s c u s s e t h e r e a l i z a t i o n o f i t w h i c h i s b a s e d o n l i n u x , a l o n g w i t h p a r t s o f fl o w c h a r t s a n d p s e u d o c o d e 4 . g o d e e p i n t o t h e t h e o r y o f s o f t w a r e t e s t i n g ; i n n o v a t e t h e t e s t i n g d e s i g n p a p e r o f i p v 6 r o u t i n g p r o t o c o l ， a f t e r w a r d l a y o u t t h e t e s t r e s u l t 5 . f i n a l l y w e r e t r o s p e c ts o u r w o r k a n d p u t s f o r w a r d s o m e s u g g e s t i o n s o n t h e i m p r o v e m e n t o f o s p f v 3 k e y w o r d s : i p v 6 o s p f v 3 r e a l i z e t e s t 北京交通大学硕 卜 学位论文 独 创 性 说 明 本人声明所呈交的论文是我个人在导师指导下进行的研究丁作及取得 的研究成果。 尽我所知， 除了文中特别加以标注和致谢的地方外， 论文中不 包含其他人已经发表或撰写过的研究成果， 也不包含为获得北京交通大学或 其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名:t j j日期 :而 本3u 关于论文使用授权的说明 本人完全了解北京交通大学有关保留、 使用学位论文的规定，即: 学校 有权保留送交论文的复印件， 允许论文被查阅和借阅; 学校可以公布论文的 全部或部分内容， 可以采用影印、 缩印或其他复制手段保存论文。论文中所 有创新和成果归北京交通大学 i p 网络实验室所有。未经许可，任何单位和 个人不得拷贝。版权所有，违者必究。 签 名 : 玺企_ 导 师 赞 爆 一丛 如 日期: c 4 -4. 3 . s 二 - .经 柞活 、 导 re f + 勿全文公 布 l 京交通 又 学硕 f : 学位论文 os p f v 3路由协议实现与测试 第一章绪论 1 . 1 . 研究背景及意义 按照日 前网络的发展趋势，到2 0 0 5 和2 0 1 5 年之间i p v 4的地址就会 耗尽，在对i p地址资源日 益凸现的需求中，在对语音、数据、视频融合 应用1 j 渐迫切的渴望中，i m以其无限大的地址空f h j 、内置的安全特性 以及能对侮个终端进行i p全球化管理的优势，成为人们探讨下一代网络 发展时首先关注的焦点， 成为互联网产业化的必然要求。 信息产业部电信 研究院院长杨泽民做出 如下的判断: “ 对于下一代网络， 1 0 0 0 个人有1 0 0 0 种说法，1 0 0 0 个人有 1 0 0 0 个目 的。 对于光传输来讲，下一 代网络是全光 交换网;对于移动通信来说，是3 g 甚至4 g ;对业务传输来说是软交换， 而下一代网络的核心协议一定是 i m .” 2 0 0 3 年6 月， 美国国防部正式提出在美国军方正规划实施的“ 全球信 息网格” 中全面部署i m 的重要政策。在i m 部署与推进方面一向持谨 慎保守态度的美国， 一改以往的被动姿态， 积极主动全面部署并且重金投 入。与美国不同的是，中国对i m的需求首先来自 于地址资源的匾乏与 危机。 其次， 随着中国通信及互联网市场的高速增长， 随着中国与其他互 联网发达国家技术和产品上的差距逐渐缩小， 中国对下一代网络的需求也 越来越强烈， 同时也具备了在下一代互联网产业争取主动权与发言权的基 本实力。那么，尽早启动以i p v 6为基础核心协议的下一代网络建设，从 国家战略的高度上整体规划和全面部署，则势在必然也迫在眉睫。 为此，国家启动 “ 高性能 i p v 6路由器”8 6 3计划，信息产业部科技 发展计划中也己经将i m列为重点攻关课题。 本论文是国家 “ 8 6 3 ” 重大 北京交通大学硕 卜 学位论文o s p f v 3 路由协议实现与 测试 科研项目 “ 高性能 i p v 6路由器协议栈软件”中的一部分内容，旨在完成 可以在单处理器和分布式多处理器硬件平台上运行的、 基于自由操作系统 l i n u x 的o s p f v 3 路由协议，同时保证该协议栈软件的可移植性、 稳定性。 1 .2 . 国内 外研究现状 从全球各国发展i m的战略来看:日 本立足于通过i m的发展普及 信息化并带动其具有优势的电子设备、 汽车及信息家电等工业的发展; 韩 国是世界上电信业最为发达的国家之一，移动和宽带互联网是其发展 i p v 6的胜 要方向;欧洲在移动通信上有优势，策略是先移动后固定，在 第 3代移动网中率先引入 i p v 6 ，以实现在互联网领域与美国并驾齐驱的 目 标; 美国的重心在于网络安全， 同时也保持其在互联网领域的核心技术 和市场优势。 对于我国民族产业来说: 2 0 0 2 年 1 月，北京交通大学与北京佳讯飞 鸿电气有限责任公司合作的佳讯飞鸿网络技术有限公司， 在国内首家推出 1 j 时支持i m 和 t p v 4 协议的双协议栈路由器f h 6 5 0 1 . f h 6 5 0 1 通过了北 京市 科技成果鉴定， 鉴定委员会一致认为该成果填补了国内空白， 达到了 国际先进水平。同年， 天地互连公司推出其b i t 1 1 2 2 i p v 6 过渡服务器， 该产品为第一 款拥有自 有知识产权的国产支持工 p v 4 到工 p v 6 多种过渡策略 的接入级服务器， 目 前己 经在6 n e t 、 北京邮电大学i p v 6 实验网、 湖南i p v 6 实验网广泛应用。此外，中兴公司计划2 0 0 3 年底推出丁 p a八p v 6 双栈高 端路由器。港湾公司计划2 0 0 4 年在其t比特路由器p 6 4 0l 实现工 p v 6 协 议栈的支持。 华为公司计划在2 0 0 3 年内， 推出支持工 p v 6 的数通产品、 3 g 产 : 品和n g n 产品， 并在2 0 0 4 年完成商用化阶段。 在 i p v 6 软件开发上， 华 为在2 0 0 2 年9 月完成 工 p v 6 基本包开发;计划2 0 0 4 年4月完成全功能包 北京交通大学f 0 1 : 学位论文o s p f v 3 路由协议实现 i 测试 井发。在i m 的产品开发上 ，国内) 一 商虽然起步晚于国际1商，产品也 有待进 一 步发展和成熟，但是毫无疑问，在下一阶段我国的大规模 i m 网络建设中，中国的民族产业厂商将获得巨大的发展空间。 1 .3 . 选题意义及主要工作 我们可以看到互联网如火如茶的发展己经到了必然要由i p v 4向i m 过渡的关键时期，目 前国内网络设备供应商采用的i p协议栈软件包大都 是购买国外软件公司开发的协议栈代码，且仅限于i p v 4 协议栈。我们研 制具有自 主知识产权的基于i m 的协议栈软件包必将促进国内i p v 6 路由 器的自主开发及产业化使我国在新一轮的网络设备竞争中占据有利地 位。而其中路山技术作为网络互连中的核心技术，是研制路由器的关键。 其选路过程实现的好坏直接会影响整个互联网的效率。那么研究开发 i p v 6路由技术在技术革新、经济发展、带动其它学科、增强民族竞争力 以及维护国家社会安全等方面具有重大的经济和社会意义。 本沦文所选题目是国家 “ 8 6 3 ” 重大科研项目“ 高性能i p v 6 路由器协 议 栈软件” 项日 中的一部分。 整个协议栈的目 标是完成可以 在单处理器和 分布式多处理器硬件平台上运行的、基于l i n u x和 v x wo r k s 两种操作系 统的、 能够与i p v 4 协议栈实现互连互通的“ 高性能i p v 6 路由器协议栈软 件” 。本论文的主要工作是完成 o s p f v 3 动态路由协议在 l i n u x 操作系统 l 的实现以及测试。 本论文的主要工作如下: ( 1 系统分析了i m 创新点以 及i m 势在必行的 发 展趋势; 重点 分析了 i m 路由 技术的发展与选择。 2 论述l i n u x 操 作系 统 在开 发i m 高 端路由 器方面独 特的 优势; 给出 北京交通大学硕 学位论文 o s p f v 3 路山协 议实现与 测试 了实现该路由协议软件高稳定性、可移植性技术的关键点。 3 在消 化吸 收i e t f 制定的 系 列 相关 标 准的 基 础 上， 对内 部网 关 路由 协 议o s p f的工作原理进行了深入探讨; 用功能区域分割的思想自行设 计 一 实现了基于l i n u x 操作系统的o s p f v 3 0 # 深入研究软件 测试理 论; 自 行设计o s p f v 3 测试用 例; 编写 单元测 试 函数对其进行模块细划测试; 编写基于o s p f v 3 路由协议系统功能测 试设计书并按照测试方案实施测试。 5 分析了o s p f v 3 的发展趋势， 给出了 今后开展工作的重点。 本论文的结构为: 第 一 章 绪论 第二章 o s p f v 3 路山 协议研究 第三章 o s p f v 3 路由协议实现 第四章 测试与结果 第五章 总结与展望 北京交通人 学顽 卜 学位论文o s p f v 3路由协议实现f 1 测试 第二章o s p f v 3 路由协议研究 2 . 1 . i p v 6 路由协议 2 . 1 . 1 .路由 协议综述 当网络启用了路由协议， 网络便具有了能够自 动更新路由表的强大功 能。 内部网关协议首先适合于在那些只有单个管理员负责网络操作和运行 的地方; 否则， 将会出现配置错误导致网络性能降低或是导致网络运行不 稳定的情况。 如果网络中只有一个路由器， 不需要使用路由协议; 只有当网络中具 有多个路由器时， 才有必要让它们去共享信息。 但如果仅有小型网络， 完 全可以通过静态路由手动地更新路由表。 卜 路由信息协议 r i p 协议4 1 基于一个被称为“ r o u t e d ” 的 程序， 该程序运行在b s d i 版本 的u n ix 系统之上，并在1 9 8 8 年被标准化在r f c 1 0 5 8中。而在r f c 1 3 8 8 中所述的版本 2中，增加了对 v l s m 的支持，但没有弥补该协议的主要 缺陷。 例如， 在有多重路径到相同目 标的网络中， r i p 确定使用一条可选 择的路径将花费许多时间 ，在没有多重路径的网络中，r i p协议己经被 一 泛使用 ri pr14 议被列为趾离矢量协议，这意味着它使用跟离来决定最佳路 径，如通过路由跳数来衡量。路由器每3 0 秒互相发送广播信息。收到广 播信息的每个路由器增加一个跳数。如果广播信息经过多个路由器收到， 七 京交通大学硕士学位论文 o s p f v 3路山协议实现t 测试 到这个路由器具有最低跳数的路径是被选中的路径。 如果首选的路径不能 正常工作，那么具有较高跳数的路径被作为备份。 对于r i p协议 ( 和其他路由 协议) ，网络上的路山器在 一 条路径不能 用时必须经历决定替代路径的 过程，这个过程称为收敛 ( c o n v e r g e n c e ) . r i p 协议花费大量的时间用于收敛是个主要的问题。 在r i p 协议认识到路 径不能达到前，它被设为等待，直到它己错过6 次更新总共1 8 0 秒时间。 然后， 在使用新路径更新路由表前， 它等待另一个可行路径的下一个信息 的到来。 这意味着在备份路径被使用前至少经过了3 分钟， 这对于多数应 用程序超时是相当长的时间。 r i p协议的另一个基本问题是，当选择路径时它忽略了连接速度问 题。 例如， 如果 一 条由 所有快速以太网 连接组成的 路径比 包含一个l o m b p s 以 太网连接的路径远一个跳数， 具有较慢i o m b p s 以 太网连接的路径将被 选定作为最佳路径。 r i p 协议的原始版本不能应用 v i . s m， 因此不能分割地址空间以最大 效率地应用有限的i p 地址。 r i p 2 协议通过引入子网屏蔽与每一路由i 一 播 信息起使用实现了这个功能。 路由协议还应该能防止数据包进入循环， 或落入路由选择循环， 这是 由于多余连接影响网络的问题o r i p 协议假定如果从网络的一个终端到另 一个终端的路由跳超过巧个，那么一定牵涉到了循环。因此当一个路径 达到 1 6 跳，将被认为是达不到的。显然，这限制了r i p 协议只能在网络 上的使用。 r i p的最大问题涉及到具有多余路径的较大网络。 如果网络没有多余 的路径， r i p 协议将很好地工作， 它是被几乎每个支持路径选择的厂商实 施的i n t e r n e t 标准。r i p协议适用于多数服务器操作系统，它的配置和障 碍修复非常容易而对于规模较大的网络， 或具有多余路径的网络， 应该考 北京交通人学硕 上 学位论文o s p f v 3路由协议实现与测试 虑使用其它路由协议。 链路状态路由 协议 o s p f 协议f3 1 是类似r i p 协议的i n t e r n e t 标准，可以 弥补r i p 协议的 缺点。 1 9 9 1 年在r f c 1 2 4 7 中它被第一次标准化; 最新的版木是在r f c 2 3 2 8 中。 但是与r i p协议不同， o s p f是一套链路状态路由协议， 这意味着路 由选择的变化基于网络中路由器物理连接的状态与速度， 并且变化被立即 广播到网络中的每一个路由器。 当一 个o s p f路由器第一次被激活，它使用o s p f的“ h e l l o 协议” 来 发现与它连接的邻节点，然后用 l s a ( 链路状态广播信息)等和这些路 由器交换链路状态信息。 每个路山器都创建了由每个接口、 对应邻节点和 接口 速度组成的数据库。每个路由器从邻接路由器收到的l s a被继续向 各自的邻接路由器传递， 直到网络中的每个路由器收到了 所有其它路由器 的 l s a. 链路状态数据库不同于路由表， 根据数据库中的信息， 每个路由器计 算到网络的每一目 标的一条路径， 创建以它为根的路由拓扑结构树， 其中 包含了形成路由 表基础的 最短路径优先树 ( s p f树) 。l s a每3 0分钟被 交换一次， 除非网络拓扑结构有变化。 例如， 如果接口变化， 信息立刻通 过网络广播;如果有多余路径，收敛将重新计算s p f 树。 计算s p f 树所 需的时间取决于网络规模的大小。 因为这些计算， 路由 器运行o s p f 需要 占用更多c p u资源。 一种弥补o s p f协议占用c p u和内存资源的方法是将网络分成独立 的层次域， 称为区域。 每个路由器仅与它们自己区域内的其它路由器交换 l s a 。区域0 被作为主干区域，所有区域必须与域0 相邻接。在a b r上 定义了两个区域之间的边界。 a b r与区域 0和另 一 个非主干区域至少分 别有一个接口。最优设计的 o s p f网络包含通过 v l s m 与每个区域邻接 北京交通人学硕 l 学位论文o s p f v 3 路由协 议实现与测试 的主干网络。这使得在路由表的 个条目中描述多个网络成为可能。 虽然o s p f 协议是r t p 协议强大的替代品，但是它执行时需要更多f : 路由器资源。 如果网络中正在运转的是u p 协议， 并民 没有发生任何问题， 仍然可以继续使用。但是如果想在网络中利用基于标准协议的多余链路， o s p f 协议是更好的选择。 2 . 1 . 2 . i p v 6 路由协议的选择 同i p v 4一样，i p v 6的内部网关协议有多种路由协议可选，主要的有 r i p n g , o s p f v 3 o r i p第一版和第二版是用来承载i p v 4的路由信息，不同用在 i p v 6的 网 络中。 在i p v 6 网 络中 使用的r i p 协议叫r i p n g ( r i p n e x t g e n e r a t i o n ) . r i p n g 主要基于r i p v 2 ， 使用u d p 端口 号5 2 1 ， 并进行扩展来支持i p v 6 地址。 r i p v 2 同r i p n g 并不兼容。 通过o s p f 来传递i p v 6 路由信息的路由协议叫o s p f v 3 , o s p f v 3 是一 个完全崭新的协议，对原有o s p f v 2 进行了 较大的改进。 o s p f v 3 运行在 i p v 6 网络中，它同o s p f v 2 并不兼容，同o s p f v 2 相比，o s p f v 3己经支 持路由器在网络上转发 i p v 6数据。o s p f v 3提高了通用性，使网络可以 适应不断变化的要求。 这使复杂的网络得以简化， 并且它采取了一些增强 措施以保证升级方便地进行， o s p f v 3 还进行了优化，并且安全性也得到 了提高。对于网络的拓扑结构变化可以迅速地做出反应，进行相应调整， 提供短的收敛期，使路由表尽快稳定化，并且与其它路由协议相比， o s p f v 3在对网络拓扑变化的处理过程中仅需要最少的通信流量并且提 供点到多点接口，支持c i d r 无类型域间路由)地址。 目 前国内外绝大多数i p v 6 网 络运行的i g p 均为o s p f v 3 。极进的i p v 6 北京 交通大 学硕下 学位论文o s p f v 3 路由协议实现与测试 产品是首批支持o s p f v 3 路由协议的产品，率先推动了i m 应用的成熟 化。o s p f v 3 进程运算不会影响o s p f v 2 ，也就是说，i p v 6 的网络运行和 i p v 4 完全是独立的， 这对在 i p v 4 网络上大规模部署 i p v b 带来 一 定的安全 -r t o 2 . 2 . o s p f 工作原理 o s p f己成为日 前i n t e rn e t 广域网和i n t r a n e t 企业网采用最多、 应用最 广泛的路由协议之一。 o s p f路由协议是由i e t f i g p工作小组提出的，是一种基于 s p f算 法的路由协议。 它是由多个研究结果发展而来的， 是 一 种基于区域实现的、 建 立 在链 路 状态算法 和d ij k s t r a 算 法基础之上的内 部网 关动态路由 协议。 每个运行 o s p f算法的路由 器都维护一个用于跟踪网络链路状态的链路 状态数据库l s d b 。 数据库中存储的是反映路由器及其链路状态的各种链 路状态通告 l s a ，这些状态包括路由器可用接口、已知可达路由和各链 路的状态信息。 链路状态数据库实际上就是一张有关该区域的完整的网络 映射图，是路由器建立路由表的依据， 一个自 治系统内的路由 器要形成 对网络拓扑结构的一致视图，就必须同步它们的链路状态数据库。o s p f 依靠 “ 邻接协议” ， “ 交换协议” ， “ 扩散协议” 3 来完成o s p f 包的交互过程， 并 最终实现同一 个路由域中所有路由器的l s d b同步。 当o s p f网络扩展到 1 0 0 , 6 0 0甚至上千台路由器时，路由器的链路 状态数据库中将存放上千上万条链路信息。为了使路由器的运行更快速， 更经济，占用的资源更少，需要把o s p f网络分割成若干区域。 北京交通大学硕 卡学位论文 o s p f v 3 路由协议实现与测试 2 . 2 . 1 . 区域划分 自 治系统a s 图2 - 1 o s p f 区域划分 如图2 - 1 所示， o s p f 网络被分割成若干个区域11 1根据不同的域对外 部路由的需求不同，可将域分为如下四种类型: 主干域: 能够处理所有l s a类型 传输域:可以生成和注入外部路由 s t u b 域:既不生成也不注入外部路由 n s s a域:可以为其它域生成外部路由，但该域内不需要注入其它外 部路由 区域的划分产生了两种不同类型的o s p f路由， 区别在于源和目的是 在相同的还是不同的区域， 分别为区域内路由和区域间路由。 区域。 被称 为o s p f的主干区域， 它负责在区域之间分发路由信息， 即任何两个区域 北京交通大学硕+学位论文o s p f v 3 路由协议实现与测试 之间的信息交互都要通过区域0 ， 它们不能进行直接的路山信息交互。 对 于每个区域中有 5 0个路山器应该是个比较安全的目 标当最开始推出 o s p f的时候，推荐的每个区域中的最大数目为2 0 0 。实际上，随着更多 的路由器 ( 以及它们相关的前缀) 加入到区域中， 每个区域的链接状态数 据库会变大， 这个限制也就不可能达到了。 根据区域拓扑结构的不同， 每 个区域可以有超过5 0 个路由器，甚至可以超过2 0 0 个。 在 o s p f l 作层次的划分中，层次中最大的实体是 a s ，即遵循共同 的路由策略统一管理下的网络群。 虽然o s p f 是一种在a s内部 ( 内部网 关) 实现的路由协议， 但运行o s p f 路由算法的路由器可以与其它a s中 的路由器交换路由信息。这种能与 其他 a s交互路由信息的路由器，在 o s p f中称为自治系统边界路由器a s b r ， 如图2 - 1 中r 2 即为一个a s b r . 拥有多个接口的路由器可以加入多个区域， 加入两个或两个以上区域 的路由器称为区域边缘路由器a b r , a b r为每个区域分别保存一个反映 其拓扑状态的l s d b ，如图中r 8即为域2 和域 3 之间的a b r .随着区域 概念的引入，意味着不再是在同一个a s 内的所有路由器都有一个相同的 链路状态数据库，而是路由器具有与其相连的每一个区域的链路状态信 息， 即该区域的结构数据库， 在同一个区域中所有路由器有着对该区域相 同的结构数据库。 那么不同域之间的路由信息的获取需要遵从一定的域 定义的规则，域之间的路由更新通过路由汇总来实现。区域边界路由器 a b r 负责将一个区域内的路由汇总后扩散到其它区域， 使其它区域的路由 器能建立目的在该区域的域间路由。 这样通过路由汇总可以减少区域之间 路由更新的传递。 如: 区域 1 的a b r 既要承担域内路由器的角色， 与域内 路由器交换域内链路状态信息， 同时也要将域1 内的路由汇总后发送给其 它区域; 而a s b r 如r 2 则将自治系统外部的路由信息汇总后通知给自 治系 统内各路由器。 北京交通人学硕 上 学位论文 o s p f v 3路由协议实现与测试 在o s p i 路由协议中，侮一个区域中的路由器都按照该区域中定义的 链路状态算法来计算网络拓扑结构， 由于区域内部路由器仅仅与同区域的 路由 器交换 l s a 信息， 使得链路状态数据库中的内容大大的减少， 极大的 提高了路由器的运算效率。 每一个区域就象一个独立的网络， 有着该区域 独有的网络拓扑数据库及网络拓扑图。 对于每一个区域， 其网络拓扑结构 在区域外是不可见的， 同样， 在每一个区域中的路由器对其域外的其余网 络结构也不了解。这意味着 o s p f 路由域中的网络链路状态数据广播被区 域的边界挡住了， 这样做有利于减少网络中链路状态数据包在全网范围内 的广播，也是o s p f 将其路由 域或一个a s 划分成很多个区域的重要原因。 所以路由协议运行的开销只与区域的规模成正比，而不是网络的规 模。 如: 对于区域 1 要生成该域的路由表是通过该域内的路由器r 1 , r 2 , r 3 按照 一 定的o s p f 工作流程 ( 包括邻接协议， 交换协议， 扩散协议) 交 互五种包，从而使该区域内的三台路由器拥有统一的拓扑网络结构图 l s d b ，就是利用该l s d b 运用s p f 算法最后生成该域的路由表。 区域的划分是逻辑意义上的分区， 其目的是为了避免由于链路局部问 题而引起的在整个a s 内的泛洪， 从而导致的整个a s 内路由表的重新计算。 分层后， 某一链路状态的变化只会涉及本区域内路由表的重新计算， 相邻 区域只需修改相应条目，从而达到链路状态的快速收敛。 2 .2 .2 .邻接协议，交换协议，扩散协议 一句话概括: o s p f 是一个分布式数据库， 是一个扩散过程， 是一个相 邻性定义和外部路由的特殊记录 o s p f的整个工作过程其实就由三大协议组成: 邻接协议: 检测链路是否可用， 在广播型与非广播型网络上选举 d r , 北京交通大 学硕 _ 学位论文 o s p f v 3 路由协议实规与 测试 b d r ;通过这种方式使建立邻居关系;交互的是o s p f五种包中的h e l l o 包。 因为邻居关系与近邻关系是不同的， 在点到点， 点到多点网络和虚拟链路 连接的路由器之间总是建立近邻关系。在广播和n b ma上 所有的路山器 都与d r , b d r建立近邻关系，是否建立近邻应遵循 卜 面规则: 漪双向通信的邻居处于以 卜 之 一 的状态时，应建立近邻关系: 卜 底层网络是点到点 底层网络是点到多点 底层网络是虚拟链路 路由器自己是 d r 路由器自己是b d r y 邻居路山器是d r或b d r 而相应的o s p f 动作有如下片段: - d o w n :这是o s p f建立交互关系的初始化状态，表示在一定时间之 内没有接收到从某一相邻路由器发送来的信息。在非广播性的网络环境 内，o s p f 路由器还可能对处于d o w n 状态的路由器发送h e l l o 数据包。 a t t e m p t : 该 状态仅在n b m a环境， 例如 帧中 继、 x .2 5 或a t m环境 中有效，表示在一定时间内没有接收到某一相邻路由器的信息，但是 o s p f路由器仍必须通过以一个较低的频率向该相邻路由器发送 h e l l o数 据包来保持联系。 -i n i t : 在该 状态时， o s p f 路由器已经接收到相邻路由器发送来的h e l l o 数据包，但自身的i p地址并没有出现在该h e l l o数据包内，也就是说， 双方的双向通信还没有建立起来。 - 2 -wa y : 这个 状态 可以 说 是建 立交互方式 真正的开 始步 骤。 在这个 状 态， 路由器看到自身已 经处于相邻路由器的h e l l 。 数据包内， 双向通信已 北京交通大学硕 上 学位论文o s p f v 3 路由协议实现与测试 经建立。 指定路由器及备份指定路由器的选择正是在这个状态完成的。 在 这个状态， o s p f路由器还可以根据其中的一个路由器是否指定路由器或 是根据链路是否点对点或虚拟链路来决定是否建立交互关系。 交换协议:在两个路由器已经通过邻接协议建立双向连接后，它们 就必须使它们的数据库进行同步， 则同步过程通过交换协议完成; 交互的 是o s p f五种包中的数据库描述包 ( d d包，只含有l s a头信息) 。 一一e x s t a r t : 这个状态是建立交互状态的第一个步骤。 在这个状态，路山 器要决定用于数据交换的初始的数据库描述数据包的序列号， 以保证路由 器得到的水远是最新的链路状态信息。 同时， 在这个状态路由器还必须决 定路由器之间的主备关系， 处于主控地位的路由器会向处于备份地位的路 由器请求链路状态信息。 在交换协议时， 在协商主， 从路由器时， 只有主路由器可以把序列号 加 1 ，而从路由器返回给主路由器时，不可以自己加序列号，而要把主路 由器设置的序列号原封不动的返回去。 这也是区别主， 从路由器的标志之 扩散协议: 交换协议发送的只是一些数据库描述包， 是为了减少不必 要的流量:而真正链路状态通告包是通过扩散协议发送的:交互的是 o s p f 五种包其中的三种: r 链路状态更新包:包含完整l s a信息的l s u包 r 链路状态请求包:请求整个 l s a信息的l s r包 r 链路状态确认包: 为保证正确发送和接收l s a而发送的l s a c k 包 o s p f路由器周期性地产生与 其相联的所有链路的状态信息，有 时这些信息也被称为链路状态广播l s a .当路由器初始化或当网 络结构发生变化 ( 例如增减路由器，链路状态发生变化等)时， 北京交通大学硕 卜 学位论文 o s p f v 3 路由协议实现与 测试 路由器会产生链路状态厂播数据包l s a ， 该数据包里包含路由器 上所有相连链路，也即为所有端口的状态信息。 所有这it h 广播数据是通过泛洪f l o o d方式在某一个 o s p f区 域内进行的。 泛洪是指路由器将其 l s a数据包传送给所有与其相 邻的o s p f路由器，相邻路由器根据其接收到的链路状态信息更 新自己的数据库， 并将该链路状态信息转送给与其相邻的路山器， 直至稳定的 一 个过程。 其体工作原理如图 2 - 2所示: 路由器a 路 由器b 发送h e l l o( 周期发送) 发送h e l l o( 周期发送)，并把a 放在邻居列表中 接收到h e l l o ，发现自己在b 的邻居列表中，给b 发d d 包 i仪 到人 的d d 包，查看数据库，将自己没有的发在l s r 包中 收到b 的l s r 包，在白己数据库中查找l s a 形成l s u 包发送给b 收 到 a 的 l s u 包， 更新数 据库， 并且 给a 发 送l s a c k 包 r o u t e r a 和b 的数据库同步，a 和b 互为f u l l 状态的邻居 图 2 - 2 o s p f 7 一 作流程图 在o s p f中， 各个网络节点不必交换整个路由表， 而只需维护一张网 比 1 t 交通大学硕士学位论文o s p f v 3 路由协议实现与测试 络 “ 图” ., o s p f有自己的网络拓扑结构，自己 提炼信息从而知道到达各 个目的的最短路径树， 生成路由表 ( 所有都是由自己完成的而小依靠邻居 了) ，也不会出现如 r i p协议的中间环路，累加到无穷的问题。 2 .2 .3 . o s p f 快速收敛技术 o s p f 路由收敛快的优点使其在目 前应用的路由协议中占有相当重要 的 地 位; 它 使用d ij k s t r a 算法 2 1 1来从 分布的 链接 状 态数 据库中 创建 转 发 表，使用区域的概念来支持层次路由使本身的网络汇聚速度非常快。 区域内路由 在同一个网络中的所有路由器运行同一 个路由选择算法， 并且彼此间 直接发送路由 选择表的更新。 s p f 算法是o s p f 路由 协议的基础。 s p f 算 法将每一个路由 器作为根来计算其到每一个目的地路由器的距离， 每 一 个 路由器根据上面我们辛苦建立起来的统一的数据库会计算出路由域的拓 扑结构图， 该结构图类似于一棵树，在s p f 算法中， 被称为最短路径树。 在o s p f 路由协议中， 最短路径树的树干长度， 即o s p f路由器至每一个 目的地路由器的距离，称为o s p f的c o s t ,其算法为:c o s t =1 0 0 x 1 0 6 / 链路带宽。 其计算过程x2 1 如下: 1 ) 当 路由 器 初 始 化 或当 网 络结 构 发生 变 化( 例 如 增减 路由 器， 链路 状 态 发生变化等)时，路由器会产生链路状态广播数据包 l s a，该数据 包里包含路由器上所有相连链路，也即为所有端日的状态信息。 2 ) 所有路由 器会通过一种被称为 刷新的 方法来 交换 链路状态数据泛洪 是指路由器将其l s a数据包传送给所有与其相邻的o s p f路山 器， 相邻路由器根据其接收到的链路状态信息更新白己的数据库， 并将该 北京交通人学硕 t : 学位论文o s p f v 3路由协议实现与测试 链路状态信息转送给与其相邻的路由器，直至稳定的一个过程。 3 ) 当网 络重新稳定下来， 也可以 说o s p f 路由 协议收敛卜 来时， 所有的 路由器会根据其各自的链路状态信息数据库计算出各自 的路由表。 该 路由表中包含路由器到侮 一 个可到达目的地的 c o s t 以及到达该目的 地所要转发的下一个路由器。 在 冲 网络中计算最短路径优先树时，要将网络和路由器视为相同的 11 点。如图2 - 3 所示。图2 - 3 简单表示了一个区域内网络的拓扑: 虱 n i 3 rl t n4 / 了 入_ z_ 2入 l q、一 匕二nn一 产厂 、 、 一 /、 、 _上 ， j一八 乙卜 丁 戈 . j 图2 - 3域内网络拓扑简图 o s p f通过邻接协议，交换协议，扩散协议完成了域内所有路由器的 同步， 即域内各个路由 器拥有统一的链路状态数据库l s d b ， 根据该l s d b 中含有的路由 器 l s a和网络l s a来生成最短路径树，