（计算机应用技术专业论文）ospf路由机制及其qos扩展研究.pdf

摘要 i n t e m e t 中的路由协议及路由算法一直是i n t e r n e t 研究的一个重点内容，传统的 i n t e m e t 部网关协议r i p 由于其安全性差、支持网络规模有限、收敛速度慢等缺 点终将被o s p f i 办议取代。但o s p f t 办议在服务质量支持方面仍然存在着欠缺，而 服务质量正成为i n t e r n e t 发展中急需解决的问题，q o s 路由算法己成为当前研究的 焦点。 论文首先对o s p f 协议的数据包格式、数据包的处理过程、采用的基本算法、 协议的基本特征、协议的工作过程、协议中的特殊机制等进行了详细分析和描述， 对当今比较流行的几种q o s 服务模型，包括i n t s e r v ，d i f f s e r v 。m p l s 和m p l s t e 进行了详细讨论，在此基础上对o s p f 协议对o o s 支持方面的欠缺进行了剖析， 给出了一个o s p f 协议实现的程序设计总体框架，包括主体程序的设计、系统各 模块的设计和几种重要数据结构，提出了基于o s p f 协议的q o s 扩展方法，定义 了相应的体系结构，提出了一个基于d i j k s t r a 算法的o n d e m a n d 计算q o s 路径的算 法，并对算法的性能迸行了分析，给出了算法的适用范围及相应的改进策略。 关键字：o s p f ，m p l s ，资源预留，o o s 路由，即时计算 a b s t r a c t l l i t e m e tr o u t i n gp r o t o c o la n dr o u t i n ga l g o r i t h m sa r ea l w a y si m p o r t a n tc o m p o n e n t o fi u t e m e tr e s e a r c h b e c a u s eo fi td r a w b a c k s ( p o o ri ns e c u r i t y , o n l yf i tt ol i m i t e ds i z e n e t w o r k , s l o wc o n v e r g e n c e ) ，r i p , t h et r a d i t i o n a li g p ( i n t e r i o rg a t e w a yp r o t o c 0 1 ) ，i s s u t ct ob er e p l a c e db yo s p eb u to s p fc a n n o tm e e to o sr e q u i r e m e n t s h o wt o p r o v i d eo o s w i t hl i m i t e dn e t w o r kr e s o u r c e sh a sb e c o m et h ef o c u s e dr e s e a r c hf i e l di n t h el u t e m e t q u a l i t yo fs e r v i c e ( q o s ) r o u t i n ga l g o r i t h m sh a v eb e c o m et h ef o c u so f r e c e u tr e s e a r c h f i r s t l y ，w eg i v ea l le x h a u s t i v ea n a l y s i so fo s p fr o u t i n gp r o t o c o l ：i n c l u d e si t s f o r m a t so fp a c k e t ，p r o t o c o lp a c k e tp r o c e s s i n g ，a l g o r i t h m ，c h a r a c t e r i s t i c sa n ds p e c i a l m e c h a n i s m s w ci n t r o d u c es e v e r a l p r e v a i l i n gq o sm o d e l s ：i n t s e r v ( i n t e g r a t e d s e r v i c e s ) ，d i f f s e r v ( d i f f e r e n t i a t e ds e r v i c e s ) ，m p l s ( m u l t i - p r o t o c o ll a b e ls w i t c h i n 曲 a n dm p l s t e ( m p l s - t r a f f i ce n g i n e e r i n g ) o nt h i sb a s i s , w ea n a l y z et h es h o r t a g eo f o s p f sq o ss u p p o r ta n dp r o p o s eaf r a m e w o r kf o ro s p fp r o t o c o li m p l e m e n t a t i o n ： i n c l u d et h ed e s i g no fe v e z 7m o d e l ，s e v e r a li m p o r t a n td a d as t r u c t u r e t h e n ，w ed i s c u s s q o s m u t i n gm e c h a n i s m sa n do s p fe x t e n s i o n s ，i n t r o d u c eao o s - b a s e dr o u t i n gm o d e l t h a t s u p p o r t s r s v p w ep r o p o s ead i j k s t r a r o u t i n ga l g o r i t h mf o rq o sp a t h c o m p u t a t i o n ，i m p l e m e n ti ti ncl a n g u a g e ，a n da n a l y s ei t sp e r f o r m a n c e w eg i v et h e a p p l i c a t i o nr a n g eo f t h ea l g o r i t h ma n dp r o p o s ec o r r e s p o n d i n gi m p r o v e m e n tp o l i c y k e y w o r d s ：o s p f , m p l s ，r s v p , q o s b a s e dr o u t i n g ，o n - d e m a n dc o m p u t a t i o n 第一章i n t e r n e t 路选机制 坤数据报转发及路由信息的维护与更新是i n t e m e t 互联层的核心功能。本章将对i n t e m e t 环境中i p 数据报的转发和选路方法，以及路由表的维护与更新方法进行简单介绍。 1 1 互联网中的选路 i p 协议的目的是提供一个可包含多个物理网络的虚拟网络，并提供无连接的数据报投 递服务。i p 协议的关键是i p 数据报的转发和选路。 在互联网中选路是十分困难的，对于那些与多个物理网络连接的计算机来说更是如此。 理想状态下，选路软件为了得到最佳路径，必须检查网络负载、数据报长度或在数据报首部 指定的服务类型。但大多数互联网选路软件远远没有这么复杂，他们往往是基于最短路径的 固定假设。 主机和路由器都参与i p 数据报的选路。当个位于主机上的应用程序需要通信时， t c p i p 协议将产生一个或多个数据报。当主机选择数据报发往何处时，必须进行最初的选 路决策。 直接投递是指在一个物理网络上把数据报从一台主机直接传输到另一台主机，这是所有 互联网通信的基础。只有当两台机器同时连到同一底层物理传输系统时( 例如，一个以太网) ， 才能进行直接投递。当目的站不在一个直接连接的网络上时，就要进行间接投递，强制要求 发送方把数据报发给一个路由器进行投递。问接投递比直接投递更困难一些，因为发送方必 须标识数据报要发送到的一个路由器。这个路由器必须把数据报转发到它的目的网络。 同一物理网络上两台主机之间的i p 数据报传输不涉及路由器。发送方通过地址解析 获取接口的物理地址，将数据报封装在数据链路层帧中，并把产生的帧直接发送到目的站。 t c p i p 互联网中的路由器形成了一个协作的互连结构。数据报从一个路由器传输到下 一个路由器，直到到达某个可直接投递数据报的路由器。 选路协议使用每台主机中的i p 选路表，该表存储有关可能目的站以及怎样到达目的站 的信息。因为主机和路由器都要路由数据报，所以他们都有选路表。主机或路由器中的i p 选路软件需要传送数据报时，它就查询选路表来决定把数据报发往何处。 选路表应存储什么信息呢? 如果每个选路表都包含所有可能目的地的地址信息，那么它 不可能使表总是符合网络的当前情况。此外，因为可能的目的站的数量是很大的，所以机器 将没有足够的空间来存储信息。 从概念上讲，我们宁愿使用信息隐藏的原理，使机器用最少的信息来进行选路决策。例 如，我们把有关特定主机的信息与它所存在的环境隔离开来，让远端的机器在不知道细节的 情况下把分组发送过来。幸运的是，m 编址方法帮助实现了这个目标。i p 地址的分配使得 所有连接到给定网络l 的机器共享一个相同的前缀( 地址的网络部分) 。这种分配使得直接 投递的测试非常高效。它意味着选路表中仅需包含网络前缀的信息而不需要整个l p 地址。 使用目的地址的网络部分而不用完整的主机地址，使选路效率很高，同时也可以保持较 小的选路表。更重要的是它帮助隐藏了信息，把特定主机的信息限制到这些主机运行的本地 环境内。典型的情况是一个选路表包含许多( n ，r ) 序偶，其中n 是目的网络的i p 地址，r 是到网络n 的路径上的“下一跳”路由器的地址。路由器r 称为下一跳，用选路表为每 个目的站存储下一跳的思想称为“下一跳选路”。因此，路由器r 中的选路表仅仅指定了从 r 到目的网络路径上的一步，而路由器并不知道目的地的完整路径。选路表中的每个表项指 向一个可通过单个网络到达的路由器，理解这一点非常重要。 用来隐藏信息、保持选路表较小的另一种技术是把多个表项统一到默认情况。这种思路 是让i p 选路软件首先在选路表中查找目的网络。如果表中没有路由，则选路例程把数据报 发给一个默认路由器。当一个网点的本地地址集很小，并且只有一个到互联网的连接时，默 认路由尤其有用。 下面是用来转发数据报的l p 算法。给定一个p 数据报和一个选路表，该算法选择数据 报要发往的下一跳。所有路由器都必须指定直接连接的网络上的下一跳： r o u t c d a t a g r a m ( d a t a g r a m ，r o u t i n g t a b l e ) 从数据报中提取目的口地址d ，并计算网络前缀n ： 讧n 与任何直接相连的 c 9 络的地址匹配 t h e n 通过该网络把数据报投递到目的地d f 其中涉及到把d 转换成一个物理地址、封装数据报 并发送该帧) e l s ei f 表中包含特定于具体主机的一个到d 的路由 t h e n 把数据报发送到表中指定的下一跳 e l s ei f 表中包含到网络n 的一个路由 t h e n 把数据报发送到表中指定的下一跳 e l s ei f 表中包含一个默认路由 t h e n 把数据报发送到表中指定的默认路由器 e k 宣布选路出错； 1 1 1 利用i p 地址选择路由 除了减少寿命和重新计算校验和外，i p 选路并不改变原始数据报，数据报的源地址和 目的地址始终不变，它们总是指定最初源站和最终目的站的i p 地址。当i p 执行选路算法时， 它总是选择一个新的i p 地址，这个地址是数据报的下一跳路由器的i p 地址。但是如果数据 报能被直接投递，那么新地址就是最终目的地的i p 地址。 之所以说i p 选路算法所选择的i p 地址是“下一跳”的地址，是因为他指明了下一步把 数据报发往何处。那么i p 把下一跳地址存储在哪里呢? 不在数据报中，这里没有为它保留 空间。事实上，p 根本不保存下一跳地址。在执行选路算法后，l p 把数据报和下一跳地址 传给一个网络接口软件，该软件对发送数据报必须经过的物理网络负责。这个接口软件把下 一跳地址绑定到一个物理地址，使用这个物理地址形成一个帧，把数据报放在该帧的数据部 分，并把结果发送出去。在用f 一跳地址找到物理地址后，网络接口软件就丢弃了f 一跳地 由e 。 2 1 1 2 处理传入的数据报 l p 软件必须对传入的数据报进行处理。当数据报到达主机时，网络接口软件就把它传 给l p 软件进行处理。如果数据报的目的地址与主机的i p 地址匹配，则主机上的i p 软件就 接受该数据报，并把它传给合适的高层协议软件迸一步处理。如果不匹配，则丢弃该数据报 ( 也就是说，禁止主机转发偶然被错误传入的数据报) 。 与主机不同，路由器要完成转发。当数据报到达路由器时，它被送给l p 软件。这又产 生两种可能：数据报可能已经到达它的最终目的地，或者它需要继续转发。与主机的情况一 样，如果数据报的目的i p 地址与路由器自己的i p 地址匹配，则i p 软件把数据报传给高层 协议软件进一步处理( 通常，目的地为路由器的数据报只是那些用于测试连接性或带路由器 管理命令的数据报，但路由器必须保留网络上广播的数据报的副本) 。如果数据报还没有到 达它的最终目的地，口就用标准算法和本地选路表中的信息为该数据报选择路由。 确定一个1 p 数据报是否到达它的最终目的地并不像看起来那么简单。要记住，即使一 台主机也可能有多个物理连接，每个连接都有自己的i p 地址。当一个i p 数据报到达时，机 器必须把目的互联网地址与它的每个网络连接的l p 地址进行比较。如果匹配，就保留该数 据报并对他进行处理。如果数据报的目的i p 地址是有限l p 广播地址或直接l p 广播地址 机器也必须接受在该物理瞬络上广播的数据报。无类型地址、子网地址和组播地址使地址识 别变得更加复杂。在任种情况下，如果数据报的目的地址与本机任何地址都不匹配，i p 就会将数据报首部中的寿命字段减1 ，如果该字段到了“0 ”，则丢弃该数据报，如果该字段 仍为正数，则计算一个新的校验和并为该数据报选择路由。 每台机器是否都应该转发它收到的】p 数据报昵? 很明显，路由器必须转发传入的数据 报，因为这是它的主要功能。一些多地址主机充当了路由器的角色，即使他们实际是一般用 途的计算机系统。虽然把主机用作路由嚣并不是个好主意，但是如果一定要这么做，主杌也 必须配置成能像路由器那样选择路由。但是其他不是用作路由器的主机该如何呢? 答案是， 不作为路由器的主机不应该路由收到的数据报，而是应该丢弃他们。 禁止不作为路由器的主机完成任何路由器的功能有4 个原因： 1 ) 当这种主机收到目的是其他主机的数据报时，本身就说明互联网的编址、选路或交 互已经出错。如果主机路由数据报，这些问题就被掩盖了： 2 ) 选路会引起不必要的网络通信量( 而且会占用主机c p u 的合法使用时间) ； 3 ) 简单的错误会导致混乱。假定每台主机都路由通信量，想象如果一台机器偶然广播 了目的为主机h 的数据报，会发生什么情况。因为它已经被广播所以网上的每台 主机都收到该数据报的副本。每台主机都会把它转发给h ，使h 淹没于众多副本中； 4 ) 路由器不仅仅路由通信量。路由器使用一种特殊的协议报告错误，然而主机却不是 这样( 同样是为了避免多个错误报告淹没源站) 。路由器还会传播选路信息，以保 证他们的选路表是一致的。如果主机路由了数据报但又不完全参与所有路由器的功 能，可能会出现难以预料的异常情况。 i p 使用选路信息转发数据报，所需的计算包括根据目的1 p 地址确定数据报发往何处。 如果目的方机器与发送方所连的是一个网络，则使用直接投递，我们把这种方式看作数据报 传输的最后一步。如果发送方无法直接到达目的地，则必须把数据报转发到一个路由器上。 一般的流程是主机直接把数据报转发到最近的路由器e 。数据报在互联网l 从一个路由器传 递到另个路由器，直到可以通过一个物理网络直接投递。 当l p 软件查找一个路由时，其算法产生下一台机器的i p 地址，这是数据报应该发往的 机器。l p 把数据报和下一跳地址传给网络接口软件。数据报从一台机器到下一台机器的传 输通常涉及了把数据报封装在一个物理帧中，把下一跳互联网地址映射到一个物理地址上， 以及使用底层硬件发送该帧。 互联网选路算法是表驱动的，并且只使用1 p 地址。尽管选路表可以包含一个特定于主 机的目的地址，但大多数都仅含有网络地址，以保持选路表较小。使用默认路由也有助于保 持选路表较小，特别是对于那些只能访问一个路由器的主机。 1 2 路由算法 路由算法是网络层软件的一部分，负责确定所收到的分组应传送的外出线路。网络层的 主要功能是将分组从源端机器经选定的路由送到目的端机器。路由算法在路由协议中起着至 关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。 通常需要综合考虑以下几个设计目标：【7 】 1 ) 正确性：算法设计应该是正确的； 2 ) 简洁性：算法设计简洁，利用最少的软件和开销，提供晟有效的功能； 3 ) 健壮性：一旦一个重要的网络投入使用，可能希望它能无变化无错误地连续运转好 几年。在这期间，会有这样那样的软硬件错误，主机、路由器和线路将增加或撤除，拓扑结 构多次改变。路由算法必须能妥善处理拓扑结构和通信量的变化，而不会使所有主机中的作 业都中止，也不必每当某些路由器崩溃时，都要重新启动该网络； 路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确 运行由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果最好的路由 器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的； 4 ) 快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程当某个网络事 件引起路由可用或不可用时，路由器就发出更新信息路由更新信息遍及整个网络，引发重 新计算最佳路径，最终达到所有路由器致公认的最佳路径收敛慢的路由算法会造成路径 循环或网络中断： 5 ) 灵活性：路由算法可以快速、准确地适应各种网络环境，例如，某个网段发生故障， 路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径； 6 ) 最优化：指路由算法选择最佳路径的能力： 7 ) 公平性：公平性和最优性是显而易见的肯定没人反对，但结果证明他们常常是 互相矛盾的： 8 ) 稳定性：稳定性也是路由算法的重要目标。有的路由算法不管运行了多长时间，都 不可能趋于稳定。 路由算法按照种类可分为以f j l 种：静态和动态、单路和多路、平等和分级、源路由和 透明路由、域内和域间、链路状态和距离矢量。前面几种的特点与字面意思基本一致，下面 着重介绍链路状态和距离矢量算法。 链路状态算法发送路由信息到互联网上所有的结点，然而对丁每个路由器，仅发送它的 路由表中描述了其自身链路状态的那一部分；距离矢量算法( 也称为b e l l m a n f o r d 算法1 则要 4 求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路 状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由 器。由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。 但另一方面，链路状态算法要求比距离向量算法有更强的c p u 能力和更多的内存空间，因 此链路状态算法将会在实现对显得更昂贵一些。除了这些区别，两种算法在大多数环境下都 能很好地运行。 路由算法使用了许多种不同的度量标准去决定最佳路径，复杂的路由算法可能采用多种 度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量，再填入路由表中， 作为寻径的标准。通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本 等。 1 3i n t e r n e t 中的动态路由协议 1 3 。l 路由和路由协议 顾名思义，动态路田协议是一些动态生成路由信息的协议。在计算机网络互联技术领域， 我们可以把路由定义如下，路由是指导i p 报文发送的一些路径信息。动态路由协议是网络 设备如路由器学习网络中路由信息的方法之一，这些协议使路由器能动态地随着网络拓扑中 产生( 如某些路径的失效或新路由的产生等) 的变化更新其保存的路由表，使网络中的路 由器在较短的时间内，无需网络管理员介入自动地维持一致的路由信息，使整个网络达到路 由收敛状态，从而保持网络的快速收敛和高可用性。 路由器学习路由信息、生成并维护路由表的方法包括直连路由、静态路由和动态路由。 直连路由是由链路层协议发现的，一般指去往路由器的接口地址所在两段的路径，该路径信 息不需要网络管理员维护，也不需要路由器通过某种算法进行计算获得，只要该接口处于活 动状态( a c t i v e ) ，路由器就会把通向该网段的路由信息填写到路由表中去，直连路由无法使 路由器获取与其不直接相连的路由信息。静态路由是由网络规划者根据网络拓扑，使用命令 在路由器上配置的路由信息，这些静态路由信息指导报文发送，静态路由方式也不需要路由 器进行计算，但是它完全依赖于网络规划者，当网络规模较大或网络拓扑经常发生改变时， 网络管理员需要傲的工作将会非常复杂并且容易产生错误。雨动态路由的方式使路由嚣能够 按照特定的算法自动计算新的路由信息，适应网络拓扑结构的变化。 1 3 2i n t e r n e t 中的动态路由协议 i n t e m e t 中使用的路由协议包括内部网关协议( i n t e r i o r g a t e w a y p r o t o c o l ，i g p ) 和外部网关 协议( e x t e r i o r g a t e w a y p r o t o c o l ，e g p ) 两种类霉! ! ，而内部网关协议目前主要包括r i p ( r o u t i n g i n f o r m a t i o np r o t o c 0 1 ) 、o s p f ( o p e n s h o r t e s t p a t hf i r s t ) 、c i s c o 公司的i g r p ( i n t e r i o r g a t e w a y r o u t i n gp r o t o c 0 1 ) 协议和o s i 的i s i s ( i n t e r m e d i a t es y s t e mt oi n t e r m e d i a t es y s t e m ，既支持 t c p i p 也支持o s i ) 9 。r i p 采用距离向量算法，o s p f 采用链路状态算法，而i g r p 为混合 型路由协议。 最初的内部网关协议是基于b e l l m a n f o r d 算法的距离向量协议r i p ，它在小系统中1 j 作 得j 良好，但当a s 变入后就不再适用了。它还受到计数到无穷问题的困扰，而且往往收敛得 很慢。因此，它在1 9 7 9 年5 月被链路状态协议取代。i e l h i n t e r a c te n g i n e e r i n gt a s kf o r c e ) 在1 9 8 8 年开发了o s p f ，这是一个内部网关路由协议用于在单一自治系统( a u t o n o m o u s s y s t e m 。a s ) 内决策路由。与r i p 相对，o s p f 是链路状态路由协议，o s p f 路由利用最短 路径优先算法( s h o r t e s tp a t hf i r s t ，s p f ) ，独立计算出到达任意目的地的路由。o s p f 通过路 由器之问通告网络接口的状态来建立链路状态数据库，生成最短路径树，每个o s p f 路由器 使用这些最短路径树构造路由表。路由是指导i p 报文发送的一些路径信息。与r i p 相比， o s p f 具有这样几个优点：1 ) 支持大型网络；2 ) 路由收敛快；3 ) 占用网络资源少。o s p f 支 持分层路由方式，这使得它的扩展能力远远超过r i p 协议。 由于o s p f 协议功能强大而又十分复杂，真正掌握它的团体和个人还是少数。因此，我 们很有必要对它进行详细的研究。 正是基于这样一个背景，本文对o s p f 路由协议进行了详细的分析，并与r i p 协议傲了 比较；对o s p f v 2 的o o s 功能进行了研究，提出了一个扩展的q o s 模型，并对现有的算法 进行了改进。 6 第二章o s p f 协议分析 2 1o s p f 协议简介 o s p f 是一个链路状态路由协议，它被设计成在单一自治系统内部运行。最初版本的协议 规范见r f c l 2 4 7 ，后来被r f c l 5 8 3 取代，后又被r f c 2 1 7 8 取代，最后发展成现在的o s p f v 2 ， j m o y 在r f c 2 3 2 8 d 0 对o s p f v 2 协议规范做了详尽的描述。每个o s p f 路由器维持一个同一的描 述自治系统拓扑结构的数据库。从这个数据库，通过构造一棵最短路径树来计算出一个路由 表。 当拓扑结构改变时，o s p f 采用最小路由协议通信量来重新计算路由。o s p f 支持等价多路 访问。它还提供区域路由能力，这使得它能提供额外一级的路由保护和减少路由协议通信量。 另外，所有o s p f 路由协议的交换需经过鉴别认证。1 4 j o s p f 是一个内部网关协议，用于在单一自治系统内决策路由。与r i p 相对，o s p f 是链路 状态路由协议，而r i p 是距离矢量路由协议。链路是路由器接口的另一种说法，因此o s p f 也称 为接口状态路由协议。o s p 随过路由器之间通告网络接口的状态来建立链路状态数据库生 成最短路径树，每个o s p f 路由器使用这些最短路径构造路由表。 o s p f 是一种内部网关协议。这意味着它是在属于同一自治系统的路由器之间发布路由信 息。o s p f i 办议基于链路状态或s p f 技术。它与基于b e l l m a n - f o r d 算法的传统t c p i p n t e r n e t 路 由协议不同。o s p f i 办议由1 下的o s p f 工作组开发。它专门为t c p i pi n t e r n e t 环境设计，包括 明显支持c i d r 和外部衍生路由信息标签。o s p f 还为路由信息更新提供认证，当发送，接受更 新信息时利用i p 多播。许多工作加起来产生了一个能对拓扑变化迅速作出反应的协议，而这些 只需要少量的路由信息通信量。 o s p f 仅仅根据在j p 分组首部发现的目的i p 地址来路由i p 分组。o s p f 是一个动态路由协议。 它能迅速侦察n a s c p 的拓扑结构变化( 例如路由器接口失效) 和在一段时期的收敛后计算出新 的无环路由。这个收敛期很短，只包括极少的路由通信量。 在一个链路状态路由协议中，每个路由器维护一个描述自治系绩a s 的拓扑结构的数据库。 这个数据库被称为链路状态数据库。每个参与的路由器都有同样的一个数据库。数据库的每 一项描述特定路由器的局部状态( 例如：路由器的可用接r 和可达邻居】。路由器在整个自治系 统中采用f l o o d i n g 来发布它的局部状态信息。 所有路由器并行运行同样的路由算法。依据链路状态数据库，每个路由器以自己为根构 造一棵最短路径树。这棵最短路径树给出到自治系统中每一目的地的路径。如果存在到目的 地的多条等价路径，通信量将被均匀分布，这就是o s p f 的负载均衡。 o s p f 具有以下优点【3j ： 1 ) 可扩展性：o s p f 特别适合大型网络，它无跳数限制，为了更易于管理，它允许域细 分： 2 ) 完全子网支持：o s p f 能完全支持子网，包括变长子网掩码和1 f 邻接子网； 3 ) h e l l o 分组：o s p f 用小型的“h e l l o ”分组来检验连接操作而不用传送大的路由表。在 稳定的删路，每3 0 分钟发生一次大型的更新； 7 4 1 服务类型路由：o s p f 能依据不同的标准( 基于服务类型t y p eo f s e r v i c e ，t o s 字段) 传送路由信息： 5 1 标签路由：路由可被标上任意值，这使与外部网关协议e g p 的互操作变得更容易， e g p 可用自治系统号来标记o s p f 路由； 当然，o s p f 也有一些缺点，主要是它很复杂，对内存和计算能力要求比较高。尽管链路 状态协议不难于理解，但是因为o s p f 有许多选项和特征，这使得它变得很复杂。 o s p f 将路由范围划分为区域h r e a s ) ，区域0 ( a r e a0 ) ，即主干，是必须的。它将内部 路由分为2 级。如果路由信息必须在2 个域之问传送，分组必须先送到主干。由于直到分组 到达主干才进行区域域间路由，这可能导致非最佳路由。小型网络可以只有一个区域，这个 区域必须为区域0 。 o s p f 将网络分为以下几类：点对点( p o i n t - t o p o i n t ) 、多路访问( m u l t i a c c e s s ) 、非广播式 多路访问( n o n b r o a d c a s tm u l t i a c c e s s ) 。将两台路由器连接到一起的串行连接为点对点连接。 而以太网和令牌环网段为多路访问。帧中继或x 2 5 为非广播式多路访问。多路访问网络( 如 以太网) 用指定路由器f d e s i g a t e dr o u t e r ，d r ) 来避免以太网内每个路由器与其他每个路由器形 成连接。如果每个路由器都和网内其他任一路由器形成连接，将导致连接数量为n 2 的爆炸式 增长。d r 管理以太网的所有链路状态，一告( 1 i n ks t a t ea d v e r t i s e m e n t s ，l s a ) ，选择d r 需要一 个选举过程，在这个过程中，也将选举出一个备份指定路由器( b a c i 【t i pd e s i g n a t e dr o u t e r ， b d r ) 。o s p f 提供优先权特征来帮助网络工程师选择d r 和b d r ，但这个实现起来比较困难。 非广播式多路访问网络，如x 2 5 ，也支持指定路由器概念，但是由于它不支持广播，所 以邻居路由器m 必须手工指定。在这样一个网络上，如果一个d r 没有邻居的完整列表，即 使网络工作正常，也将导致连接丢失。如果可能的话，建议用点对点连接集合来配置这样一 个网络，这可以避免d r 选举的复杂性。o s p f 检验网络操作的连续性的主要手段是h e l l o 协 议。每个o s p f 路由器每隔l o 秒钟向每个接口发送小h e r o 分组。o s p f 邻居通过接受h e r o 分组获知彼此的存在。h e l l o 分组不在o s p f 数据库中记录，但是如果4 0 秒没收到从某个邻居 来的h e l l o 分组，该邻居就被标记为失效。尽管一个网段的所有路由器的h e l l o 定时器必须为 常量，但是h e l l o 定时器也可以配置。链路状态广告也有使用期限。如果3 0 分钟还没有改变， 发起路由器将重新广告一个链路状态广告l s a 。 o s p f 是一种典型的链路状态路由协议。采用o s p f 的路由器彼此交换并保存整个网络的 链路信息，从而掌握全网的拓扑结构，独立计算路由。因为r i p 路由协议不能服务于大型网 络，所以，i e t f 的i g p 工作组特别开发出链路状态协议- - o s p f 。目前广泛使用的是o s p f v 2 ， 最新标准为r i 2 3 2 8 。 o s p f 作为一种内部网关协议，用于在同一个自治域中的路由器之间发布路由信息。o s p f 具有支持大型网络、路由收敛快、占用网络资源少等优点，在目前应用的路由协议中占有相 当重要的地位。 2 2o s p f 协议的基本概念 2 2 1 基本概念和术语 1 链路状态 8 o s p f 路由器收集其所在网络区域上各路由器的链路状态信息( l i n k s t a t e ) ，生成链路状态 数据库( l i n k - s t a t ed a t a b a s e ) 。路由器掌握了该区域上所有路由器的链路状态信息，也就等于了 解了整个网络的拓扑结构。o s p f 路由器利用“最短路径优先算法( s h o r t e s t p a t h f i r s t ，s p n ”， 独立地计算出到达任意目的地的路由。 2 区域 o s p f 协议引入“分层路由”的概念，将网络分割成一个“主干”连接的一组相互独立的部分， 这些相互独立的部分被称为“区域”( a r e a ) ，“主干”的部分称为“主干区域”。每个区域就如同一 个独立的网络，该区域的o s p f 路由器只保存该区域的链路状态。每个路由器的链路状态数据 库都可以保持合理的大小，路由计算的时间、报文数量都不会过大。 3 o s p f 网络类型 根据路由器所连接的物理网络不同，o s p f 将网络划分为四种类型：广播多路访问型 ( b r o a d c a s tm u l t i a c c e s s ) 、非广播多路访问型( n o n eb r o a d c a s tm u l t i a c c e s s ，n b m a ) 、点到 点型( p o i n t - t o - p o i n t ) 、点到多点型( p o i n t t o m u l t i p o i n t ) 。 广播多路访问型网络如：e t h e m e t 、t o k e nr i n g 、f d d i 。n b m a 型网络如：f r a m er e l a y 、 x 2 5 、s m d s 。p o i n t - t o p o i n t 型网络如：p p p 、h d l c 。具体结构如图2 1 ： 嗣譬 b r o a d c “t r i 一 m 一霉萄霹参 n b m a 薯誊k 囊譬翟 ；基。j* f m 霜警分7 警 图2 1 0 s p f 网络类型 4 指定路由器和备份指定路由器 在多路访问网络上可能存在多个路由器，为了避免路由器之间建立完全相邻关系而引起 的大量开销，o s p f 要求在区域中选举一个d r 。每个路由器都与之建立完全相邻关系。d r 负 责收集所有的链路状态信息，并发布给其他路由器。选举d r 的同时也选举出一个b d r 。在 d r 失效的时候，b d r 担负起d r 的职责。点对点型网络不需要d r ，因为只存在两个节点， 彼此完全相邻。 2 2 2 协议组成 o s p f 协议由h e l l o 协议、交换协议、扩散协议组成。当路由器开启一个端口的o s p f 路 由时，将会从这个端口发出一个h e l l o 报文，以后它也将以一定的间隔周期性地发送h e l l o 报 文。o s p f 路由器用h e l l o 报文来初始化新的相邻关系以及确认相邻的路由器邻居之问的通信 状态。对广播型网络和非广播型多路访问网络，路由器使用h e l l o 协议选举出一个d r 。在广 播型网络里，h e l l o 报文使用多播地址2 2 4 0 0 5 周期性地广播，) 通过这个过程自动发现路由 器邻居。在n b m a 嘲络中，d r 负责向其他路南器逐一发送h e l l o 报文。 9 2 2 3 协议操作 第一步：建立路由器的邻接关系 所谓“邻接关系”( a d j a c c n c y ) 是指o s p f 路由器以交换路由信息为目的，在所选择的相 邻路由器之间建立的一种关系。路由器首先发送拥有自身信息( l o o p b a c k 端口或最大的i p 地址) 的h e l l o 报文。与之相邻的路由器如果收到这个h e l l o 报文就将这个报文内的i d 信 息加入到自己的h e l l o 报文内。 如果路由器的某端口收到从其他路由器发送的含有自身m 信息的h e l l o 报文，则它根据 该端口所在网络类型确定是否可以建立邻接关系。 在点对点网络中，路由器将直接和对端路由器建立起邻接关系，并且该路由器将直接进 入到第三步操作：发现其他路由器。若为m u l t i a c c e s s 弼络，该路由器将进入选举步骤。 第二步：选举d r b d r 不同类型的网络选举d r 和b d r 的方式不同。 m u l t i a c c e s s 网络支持多个路由器，在这种情况卜，o s p f 需要建立起作为链路状态和l s a 更新的中心节点。选举利用h e l l o 报文内的m 和优先权( p r i o r i t y ) 字段值来确定。优先权字段 值大小从0 到2 5 5 ，优先权值最高的路由器成为d r 。如果优先权值大小一样，则1 d 值最高的 路由器选举为d r ，优先权值次高的路由器选举为b d r 。优先权值和i d 值都可以直接设置。 第三步：发现路由器 在这个步骤中，路由器与路由器之间首先利用h e l l o 报文的m 信息确认主从关系，然后 主从路由器相互交换部分链路状态信息。每个路由器对信息进行分析比较，如果收到的信息 有新的内容，路由器将要求对方发送完整的链路状态信息。这个状态完成后，路由器之间建 立完全相邻( f u l la d j a c e n c y ) 关系，同时邻接路由器拥有自己独立的、完整的链路状态数据 库。 在m u l t i a c c e s s 网络内，d r 与b d r 互换信息，并同时与本子网内其他路由器交换链路状 态信息。 在p o i n t - t o p o i n t 或p o i n t - t o - m u l t i p o i n t 网络中，相邻路由器之间互换链路状态信息。 第四步：选择适当的路由器 当一个路由器拥有完整独立的链路状态数据库后，它将采用s p f 算法计算并创建路由表。 o s p f 路由器依据链路状态数据库的内容，独立地用s p f 算法计算出到每一个目的网络的路径， 并将路径存入路由表中。 o s p f 利用量度( c o s t ) 计算目的路径，c o s t 最小者印为最短路径。在配置o s p f 路由器时 可根据实际情况，如链路带宽、时延或经济上的费用设置链路c o s t 大小。c o s t 越小，则该链 路被选为路由的可能性越大。 第五步：维护路由信息 当链路状态发生变化时，o s p f 通过f l o o d i n g 过程通告网络上其他路由器。o s p f 路由器 接收到包含有新信息的链路状态更新报文，将更新自己的链路状态数据库，然后用s p f 算法 重新计算路由表。在重新计算过程中，路由嚣继续使用旧路由表，直到s p f 完成新的路由表 计算。新的链路状态信息将发送给其他路由器。值得注意的是，即使链路状态没有发生改变， o s p f 路由信息也会自动更新，默认时间为3 0 分钟。 o s p f 路d 器之间使用链路状态通告( l s a ) 来变换箨自的链路状态信息，并把获得的信息 存储在链路状态数据库中。各o s p f 路由器独立使用s p f 算法计算到各个目的地址的路由。 1 0 o s p f 协议支持分层路由方式，这使得它的扩展能力远远超过r i p 协议。当o s p f 网络扩 展到1 0 0 、5 0 0 甚至上千个路由器时，路由器的链路状态数据库将记录成千上万条链路信息。 为了使路由器的运行更快速、更经济、占用的资源更少，网络工程师们通常按功能、结构和 需要把o s p f 网络分割成若干个区域，并将这些区域和主干区域根据功能和需要相互连接从而 达到分层的目的。 2 2 ao s p f 分层路由的思想 o s p f 把一个大型网络分割成多个小型网络的能力被称为分层路由，这些被分割出来的小 型网络就称为“区域”( a r e a ) 。由于区域内部路由器仅与同区域的路由器交换l s a 信息，这样 l s a 报文数量及链路状态信息库表项都会极大减少，s p f 计算速度因此得到提高。多区域的 o s p f 必须存在一个主干区域，主干区域负责收集非主干区域发出的汇总路由信息，并将这些 信息返回给各区域。o s p f 区域不能随意划分，应该合理地选择区域边界，使不同区域之间 的通信量最小。但在实际应用中区域的划分往往并不是根据通信模式而是根据地理或政治因 素来完成的。 2 2 5o s p f 中的路由器分类 在o s p f 多区域网络中，路由器可以按不同的需要同时成为以下四种路由器中的几种 图2 2o s p f 中路由器的类型 1 ) 内部路由器( i n t e r n a lt o u t e r s ，i r ) ：直接连接到同一个区域的所有网络的路由器，这 些路由器的所有端口在同一区域，所有这些路由器维护同一个链路状态数据库，执行基本路 由算法的一个简单拷贝。 2 ) 区域边界路f l ：l ：器( a r e ab o r d e rr o u t e r s ，a b r ) ；属于多个区域的路由器，这些路由器具 有连接多区域端口，一般作为一个区域的出e l 。a b r 运行基本路由算法的多个拷贝，每个所 连接的区域运行一个拷贝。a b r 为每一个所连接的区域建立链路状态数据库，负责将所连接 区域的拓扑结构路由摘要信息发送到主干区域，而主干区域上的a b r