链路状态路由选择协议

5.2.4　链路状态路由选择协议

距离向量路由选择协议对最大度量值的规定限制了网络的规模，这是距离向量路由选择协议的一大缺点。近年来，随着网络规模的不断增长，使得有必要使用新的路由算法代替距离向量算法，链路状态路由选择协议就是其中之一。

1．链路状态路由选择协议概述

链路状态路由选择协议是为大型网络设计的，它解决了距离向量算法的一些限制，能映射整个网络的拓扑结构。链路状态路由算法的基本工作原理为：

●　路由器有责任和邻居路由器联系并了解它们的身份。

●　路由器建立链路状态信息包，这些链路状态信息包包含了网络链路列表及相关的费用等内容。

●　链路状态信息包被发送到网络中所有的路由器。

●　所有的路由器保持相同的网络链路状态表。

●　每个路由器根据自己网络链路状态表计算到所有目的地的最佳路由。

路由器通过自己的网络端口向邻居路由器发送Hello报文，建立联系。Hello报文通过点到点链路或非广播网络直接传送到邻居路由器。在局域网中，也可以发送给一个预先定义的组或组播IP地址，这样所有路由器都可以接收到Hello报文。而路由器在接收到来自邻居路由器的Hello报文后，将通过Hello报文进行应答。这样相邻路由器就可以建立联系，并在此基础上进行链路状态信息的交换。

链路状态信息是以链路状态报文的形式发送的，链路状态报文中包含了路由器所获得的链路状态表。链路状态报文通常在以下特定的条件下才进行发送：

●　当路由器发现一个新的邻居路由器时。

●　当到达邻居路由器的链路被关闭时。

●　当链路花费变化时。

●　基本更新报文每隔30分钟发送一次。

为了每个路由器都能够正确计算网络拓扑和最佳路由，应该让网络中的所有路由器均能成功接收到每个链路状态报文，这是至关重要的。通常情况下，路由器是通过泛洪（Flooding）的形式向邻居路由器发送链路状态报文的。泛洪法要求接收链路状态报文的路由器将链路状态报文发送到除源路由器以外的所有邻居路由器，并要求所有的邻居路由器在接收到链路状态报文后进行明确的应答以保证链路状态报文的正确发送。同时，在链路状态报文中加上序号和时间戳以保证不会接收和转发重复的链路状态报文。

当路由器接收到一个链路状态报文时，它先检查自己数据库中的链路状态报文的序号。如果发现与刚接收到的链路状态报文中的序号相同的链路状态报文，那么就将刚接收到的链路状态报文丢弃，否则将该链路状态报文加入到数据库中。

泛洪过程保证了网络中所有路由器均能够保存相同的链路状态信息，所有路由器根据这些链路状态信息通过一定的算法计算出到达所有目的网络的最佳路由，最为常用的算法是最短路径优先（ShortestPath First），稍后将重点介绍的OSPF路由协议就使用了最短路径优先的算法来计算最佳路由。

运行距离向量路由选择协议的路由器具有以下功能特点：

●　快速收敛。它能够在网络拓扑发生变化时，立即进行路由的重新计算，及时向其他路由器发送最新的链路状态信息，使得各路由器的链路状态表能够尽量保持一致。

●　支持可变长子网掩码（Variable Length SubnetMask，简称VLSM）。这些功能使得它可以支持在一个网络中使用多级子网IP地址。

●　提高了网络节点的可达性。因为它突破距离向量路由选择协议对15跳数的限制，支持网络中具有更多的网络节点。

●　最佳路由的选择。因为它组合了网络链路的多种性能指标来计算最佳路由。

2．OSPF路由协议

OSPF（Open ShortestPath First）路由协议，也称为开放最短路径优先路由协议，是一个最为典型的链路状态路由选择协议，目前使用得比较多的是第二版的OSPF，详细的协议描述在RFC 2328文档中。

OSPF协议是链路状态协议。每一个OSPF路由器均维护着一个数据库，它反映了整个网络拓扑。由于OSPF路由器是向直接相连的路由器发送链路状态通告来组建其数据库的，因此可以认为OSPF路由器得到的是网络链路的“第一手”信息，而RIP协议中定期广播的路由信息通常被认为是“第二手”的信息。

OSPF协议可以将网络分成若干个逻辑区域，可以形成分级路由拓扑。而在逻辑区域的边界，采用路由汇总的办法交换不同区域的路由表，既有利于减少网络中IP路由表的大小，也减少了计算远距离网络路由的时间。OSPF协议的工作是以逻辑区域为单位的，相对而言，在逻辑区域内部具有一定的独立性。

OSPF协议将所有的数据链路技术分成三种网络类型：广播或多访问（包括以太网、令牌环网和FDDI在内的所有局域网）、非广播（如X.25、帧中继等）、点对点（如T1等）。对于不同类型的网络，OSPF协议的工作机制略有区别。

（1）邻居关系与邻接

在OSPF网络中，邻居关系是非常重要的。路由器必须和与其共享链路的其他OSPF路由器保持邻居关系。而邻接则是一种特定的关系，保持邻接关系的路由器之间相互交换链路状态信息，并且保持对网络拓扑的认知同步。路由器只有在具有邻居关系的基础上才能进一步建立邻接关系。

①呼叫协议

位于一个逻辑区域内部的路由器应该像一个小镇上的亲密邻居，彼此之间经常交流信息，相互介绍新的邻居。OSPF协议中就是通过呼叫（Hello）协议在逻辑区域内部的路由器之间相互交换路由信息的。OSPF路由器在其所有链路端口都可以发送小的呼叫数据包，这种呼叫数据包非常小，图5-14给出了呼叫协议的报文格式。

图5-14　呼叫协议报文格式

呼叫协议报文中最前面是OSPF协议的公共头部，其格式如图5-15所示。

图5-15　OSPF协议公共头部格式

在OSPF协议公共头部中，版本为2，报文类型有：呼叫报文、数据库描述报文、链路状态请求报文、链路状态更新报文、链路状态确认报文。路由器ID是一个32位的二进制数，作为OSPF路由过程中每个OSPF路由器的标识符。在CISCO路由器中，路由器活动端口的最高IP地址被选为路由器ID。每个OSPF逻辑区域都有一个32位的区域标识符，即区域ID。在一条链路上的所有路由器必须与它们所在的区域保持一致。基于这条规则，区域边界不能位于链路之中，而必须在路由器之内。身份认证是一个可选项，身份认证类型为0表示没有身份认证，1表示使用简单密码进行身份认证，在这种情况下，身份认证数据中包含的是密码信息，在设置了身份认证后，要求链路上所有路由器必须遵循相同的认证类型和密码。

呼叫协议报文中的呼叫间隔是指两个呼叫之间的间隔时间，缺省情况下，呼叫间隔为10s。而停用间隔是指路由器在断定邻居已经失效之前要等待的听取时间，缺省情况下，停用间隔为呼叫间隔的4倍。

指定路由器（Designated Router，简称DR）和备份指定路由器（Backup Designated Router，简称BDR）是通过呼叫协议在OSPF网络中选举产生的，指定路由器在网络中具有两项重要功能：a.产生网络链路通告，这些通告列出了连接到多路存取网络的路由器；b.它和多路存取网络中的所有路由器形成了邻接关系，因此它成为转发链路状态通告的焦点。路由器优先级用于在多路访问链路上来协商选举指定路由器和备份指定路由器。

为了减少一个区域内路由器所处理的负载量和路由表，可以将一个区域配置成为存根区域。如果一个区域是存根区域，那么区域内的所有路由器必须通过其在呼叫报文中设置存根区域标记来默认这一点。

呼叫协议的任务是发现网络上的邻居路由器，并和它们建立关系。OSPF路由器将通过所有的端口周期性地对外发送呼叫协议报文。与其他OSPF协议报文一样，呼叫协议报文会被发送到点到点和广播网络上的标准组播IP地址，这个地址是224.0.0.5。在非广播网络中，利用每个路由器上配置的邻居网络地址信息将它们传送到一个特定的IP地址。

而OSPF路由器的某个端口中接收到邻居路由器的呼叫报文后，将在本路由器发送出去的呼叫报文中包含邻居路由器的标识，同时也包含了网络掩码、路由器优先级、指定路由器和备份指定路由器，后3项参数用于在多路存取网络中选择指定路由器和备份指定路由器。在OSPF路由器的每个端口中，均可以配置网络掩码、路由器优先级、呼叫报文的间隔时间和停用时间。

在路由器刚启动时，它没有意识到任何邻居，此时它的状态为关闭（Down）状态。在这种状态下，路由器将周期性地向外发送呼叫报文，以尝试与链路上的OSPF路由器建立联系。而一个路由器从端口中接收一个刚加入网络的路由器发送来的报文后，将新的邻居路由器添加到自己的邻居数据库中，并在下一个发送的呼叫报文中包含新的邻居路由器的ID，同时该路由器将进入初始状态。当一个路由器接收到来自另外一个路由器的呼叫报文中包含了自己的路由器ID时，说明该路由器与邻居路由器之间均意识到了对方的存在，此时就进入了双向（2-Way）状态，并在自己的邻居数据库中维护相互之间的信息。

②建立邻接关系

一旦两个路由器成为邻居后，它们便可以确定是否成为邻接。只有成为邻接之后，两个OSPF邻居路由器才可以交换链路状态数据库的描述符、请求和更新数据包，直到双方满意为止，这时候，两个路由器的链路状态数据库应具有完全相同的信息。

而当两个路由器的链路状态数据库中条目全部相同之后，这两个路由器就可以认为实现了完全邻接，邻接的两个路由器是共享网络和链路信息的。

在点对点链路上，两个路由器一旦同意成为邻居后，就会企图成为邻接关系。但并不是所有的邻居路由器都可以实现邻接。在一个多访问链路中，除了指定路由器和备份指定路由器外，其他路由器只能与指定路由器和备份指定路由器保持邻接关系，但与非指定路由器之间只能保持邻居关系。

③选择指定路由器和备份指定路由器

在一个广播多访问链路和非广播多访问链路中，可能有许多路由器，如果这些路由器之间都建立邻接关系，那么每个路由器将要浪费大量的时间和资源来维护众多的邻接关系。因此，需要选定指定路由器和备份指定路由器来负责与所有其他的路由器保持邻接，以避免所有路由器之间的直接邻接。

在如图5-16所示的由四个路由器所组成的网络中，路由器A是指定路由器，路由器B是备份指定路由器，而虚线表示这两个路由器建立了邻接关系。注意路由器C和路由器D相互之间没有建立邻接。但是它们的链路状态数据库能保证一致，因为它们都与指定路由器——路由器A保持了邻接关系。

图5-16　OSPF路由器邻接实例

当一个OSPF路由器发出呼叫报文后，如果得不到响应，它就认为链路上没有其他的OSPF路由器，于是就自觉地充当起指定路由器的角色。当这条链路上出现第二个OSPF路由器时，将作为备份指定路由器。而一个OSPF路由器加入一条已经存在指定路由器和备份指定路由器的多访问链路时，将通过呼叫协议获知该链路中的指定路由器和备份指定路由器的ID，并与其建立邻接关系。

链路上的所有路由器会将所有链路的变化直接报告到单个传送地址224.0.0.6（它是针对所有指定路由器）。而指定路由器则是将其收集到的链路变动通告发送到单点传送地址224.0.0.5（它是针对所有的OSPF路由器），该链路上的所有OSPF路由器都将接收到该链路变动通告。

在一条链路上，如果指定路由器在一个停用间隔之内没有发送任何呼叫报文，那么将重新进行指定路由器的选举。选举指定路由器的主要依据是路由器优先级，优先级最高的路由器将被选为指定路由器，优先级次之的则被选为备份指定路由器。如果存在两个或两个以上的路由器具有相同的优先级，那么将选择路由器ID较高的路由器作为指定路由器。在路由器的每个端口中，可以设置其优先级，这样就可以控制由哪些路由器来充当指定路由器和备份指定路由器。CISCO路由器缺省的优先级为1，若将一个路由器端口的优先级设置为0，那么就意味着该路由器将永远不会被选为链路的指定路由器。

需要注意的是：在点对点链路中，由于只有两个路由器，所以没有指定路由器和备份指定路由器，这两个路由器总是试图进行邻接。

（2）链路状态数据库的交换

当两个OSPF路由器之间确立了邻居关系之后，双方进入了双向状态，说明了它们之间已经建立了双向通信。接下去，它们要交换彼此的链路状态数据库中的信息，以使双方具有相同的链路状态数据库。下面介绍OSPF协议的链路状态数据库的交换过程。

链路状态数据库交换过程中的第一个状态是交换启动状态，当两个路由器进入双向状态后，彼此之间通过交换呼叫报文协商由谁启动交换过程，就表示已经进入了交换开始状态（ExStart）。两者中路由器ID较高的路由器将充当主路由器，并由它发送一个含有序号的数据库描述报文来启动交换过程。OSPF数据库描述报文的格式如图5-17所示。

主路由器首先向从路由器发送数据库描述报文以描述它的链路状态信息数据库。每个报文有一个序列号来标识，包含了主路由器链路状态数据库中链路状态头的一个列表。从路由器接收到该报文后，将发送一个包含自己的链路状态头的报文作为应答，在该报文中序列号与主路由器发送的报文的序列号一致。

数据库描述报文中，标志位I为“1”表明它是第一个这样的报文；M位为“1”表示还有更多的报文要发送；M S位为“1”表示该报文是由主路由器发出的，为“0”表示该报文是由从路由器发出的。

图5-17　OSPF数据库描述报文格式

在收到从路由器的应答后，主路由器将向从路由器发送一个对其链路状态数据库条目进行汇总的数据库描述报文。如果链路状态数据库特别大的话，这种报文的交换过程将进行好几个回合。这个过程也被称为交换状态（Exchange），而且这个交换过程是双向的。

当主从路由器之间的交换过程结束后，双方就进入了装载状态（Loading），对彼此的链路状态数据库进行最后的核实。这时相互之间以链路状态请求（LSR）报文请求特定的数据库条目，以链路状态更新（LSU）报文作为应答提供请求的信息，包含在LSU报文中的单个条目被称为链路状态通告。当所有的链路状态通告已经被接收到并进行了比较后，主从路由器将具有相同的链路状态数据库，它们将进入完全状态，称它们是完全邻接的。

（3）链路状态信息的维护

当两个OSPF路由器进入了完全邻接状态后，它们的链路状态信息将保持一致，但随着网络的变化，彼此之间还要为维护链路状态信息而进行一系列的操作，通过发布链路状态更新通告使得链路内的所有路由器得到最新的链路状态信息。

常用的链路状态通告有以下五种类型：

●　路由器状态通告。所有OSPF路由器均会产生这种通告，描述区域内的路由器端口的状态。

●　网络链路通告。该通告由多路存取链路上的指定路由器产生，列出了连接到网络上的路由器。

●　汇总链路通告。该通告有两种类型，都是由位于两个OSPF区域之间的边界路由器所产生，一种描述了到达其他区域网络的路由，另一种描述了到达AS边界路由器的路由，AS边界路由器是位于OSPF网络周边的边界路由器。

●　AS外部链路通告。该通告由AS边界路由器发出，描述了OSPF网络外部的路由信息。

网络链路的变化和路由器端口的状态变化，均能导致直接相连的路由器产生链路状态通告，将变化通知给其他的OSPF路由器。除此之外，外部路由的变化、路由器ID的变化、邻居路由器状态的变化等等也会导致链路状态通告的产生。

虽然OSPF路由器不像距离向量路由器那样频繁地、周期性地广播它们的路由信息，但也会在较长的时间间隔后刷新其链路状态通告。

（4）选择最佳路径

OSPF协议中选择最佳路径时使用了著名的最短路径优先的算法（也称之为Dijkstra算法）。在计算最短路径时，使用了前面一直提到的链路状态数据库中包含的链路状态信息，为目的网络计算出所有可能的路径，然后根据这些路径的开销进行排队，开销最低的路由将进入IP路由表，作为转发的依据。

由于OSPF采用了路径开销作为度量项，因此比RIP协议具有更好的灵活性。路径开销是以路由器的链路端口为基础来计算的，对一条OSPF路径而言，列在IP路由表中的开销等于路径上各链路端口的开销的总和。在其默认的计算方法中，CISCO路由器采用的是端口的带宽，计算公式为100除以端口的带宽。因此，10Mbps的链路的开销为10，100Mbps的链路的带宽为1。

实际上，在OSPF协议的文档中并没有对路径开销的方法作统一的规定。因此，在不同的实现中开销的计算方法会有所不同，而且通过手工设置可以覆盖路由器中以端口带宽为基础的默认开销。

（5）路由汇总

路由汇总是指在边界路由器中将一个区域内部的多条路由信息汇总成一条路由信息通告给其他的OSPF区域。这样既可以将网络中的路由表减小，还可以针对其他区域的路由器隐藏本区域的拓扑。

进行路由汇总的主要方法是将子网掩码缩短，以便用一个网络地址来表示更多的网络。例如：地址分别为202.110.124.0/24、202.110.125.0/24、202.110.126.0/24、202.110.127.0/24的四个网络可以将其子网掩码缩短2位，用202.110.124/22来表示。

因此，路由汇总就要求在设计IP网络时，对IP地址进行精心的编排，将每个区域内的IP地址都设计成连续的形式。那么边界路由器用一个或两个语句便可以对一个区域内的所有路由进行汇总。区域内的路由就以这种汇总的形式通告给其他区域，而不必对每个子网和每条路由进行单独的通告。

路由汇总实际上是在大型网络中使用OSPF协议的一个显著优点。