深论路由选择协议

在路由协议中，路由选择协议是一个重点。那么针对这个重点内容我们将要详细地为大家介绍一下。这个协议包含了很多信息和概念。希望大家从文中能够找到值得参考的内容。

一、链路状态泛洪扩散(Flooding)

在建立了邻接关系之后，路由器开始发送LSA给每个邻居，同时，每个邻居保存接收到的LSA并依次向它的每个邻居转发，除了发送该LSA的邻居之外，在这里优于距离矢量的一个特点是：LSA几乎是立即被转发的！因此，当网络拓扑发生变化时，链路状态协议的收敛速度要远远快于距离矢量协议；

路由选择协议中的泛洪扩散过程是链路状态协议中最复杂的一部分，有几种方式可以使泛洪扩散更高效和更可靠，如使用单播和多播地址、校验和以及主动确认，其中有两个过程是极其重要的：排序和老化；

1、序列号

假设这样一种情况：路由器C先从B收到了A发出的一个LSA并保存到自己的拓扑数据库中，接着又通过路由器F收到了同样的这个由A发出的LSA，路由器C发现数据库中已经存在了该LSA（知道是从B收到的），那么路由器C从路由器F接收到的这个LSA是否应该向路由器B转发？答案是不转发！因为路由器B已经收到了这个LSA，由于路由器C从路由器F接收到的LSA的序列号与早先从路由器B接受的LSA序列号相同，所以路由器C也知道这一情况，于是将该LSA丢弃；

当路由器A发送LSA时，在每个拷贝中的序列号都是相同的，此序列号和LSA的其他部分一起被保存在路由器的拓扑数据库中，当路由器收到数据库中已存在的LSA且序列号相同时，路由器将丢弃这些信息；如果信息相同但序列号更大，那么接收的信息和新序列号被保存到数据库中，并且泛洪扩散该LSA；

因为序列号被携带在LSA中的一个固定字段内，所以序列号一定有上限，那么当序列号到达上限时会发生什么呢？

1）线性序列号空间

一种办法是使用一个非常大的线性序列号以至于根本不可能到达上限，如使用32位长字段(IS-IS就是这样)；如果一个链路状态路由选择进程用完了所有序列号，那么它在重新使用最低序列号之前必须停止（重新启动），并等待它所发出的LSA在所有数据库中都不再使用。假如最大的时间是1个小时或者更长，那么这种方法是不可行的。

2）循环序列号空间

这种方法数字是循环使用的，在32位空间内紧跟在4294967295后面的是0；它在重新启动路由器后也可能会遇到同线性序列号一样的问题！

3）棒棒糖序列号空间

这种方法是线性序列号空间和循环序列号空间的综合，它有一个线性组件和一个圆形组件；性线空间的缺点是不能循环使用序列号，即序列号是有限的，而圆形空间的缺点是不存在一个数小于其他所有的数。

2、老化(Aging)

LAS包格式中有一个年龄字段，当LSA被创建时，路由器将该字段设置为0,随着数据包的扩散，每台路由器都会增加通告中的年龄。当然，另一个选项是从某个最大年龄开始，然后递减，OSPF是递增，IS-IS是递减；

老化过程为泛洪扩散增加了可靠性，该协议为网络定义了一个最大年龄差距(MaxAgeDiff)值。路由器可能接收到一个LSA的多个副本，其中序列号相同，年龄不同。如果年龄的差距小于MaxAgeDiff，那么认为是由于网络的正常时延造成了年龄的差异，因此数据库原有的LSA继续保存，新收到的LSA(年龄更大)不被扩散；如果年龄差距超过MaxAgeDiff，那么认为网络发生异常，因为新被发送的LSA的序列号值没有增加。在这种情况下，较新的LSA会被记录下来，并将数据包扩散出去。典型的MaxAgeDiff值为15min（用于OSPF）；

若LSA驻留在数据库中，则LSA的年龄会不断增加。如果链路状态记录的年龄增加到某个最大值(MaxAge)－由特定的路由选择协议－那么一个带有MaxAge值的LSA被泛洪扩散到所有邻居，邻居随即从数据库中删除相关记录；

当LSA的年龄到达MaxAge时，将被从所有的数据库中删除，这需要有一种机制来定期地确认LSA并且在达到最大年龄之前将它的计时器复位。链路状态刷新计时器(LSRefeshTimer)就是做此用途的；一旦计时器超时，路由器将向所有邻居泛洪扩散新的LSA，收到的邻居会把有关路由器记录的年龄设置为新接收到的年龄。OSPF定义MaxAge为1小时，LSRefreshTime为30min。

二、链路状态数据库

除了邻居发现和泛洪扩散LSA，链路状态路由选择协议的第3个主要任务是建立链路状态数据库。链路状态数据库，也叫拓扑数据库把LSA作为一连串记录保存下来。LSA包括两类通用信息：

路由器链路信息－使用路由器ID、邻居ID和代价通告路由器的邻居路由器，这里的代价是发送LSA路由器到其邻居的代价；

末梢网络信息－使用路由器ID、网络ID和代价通告路由器直接连接的末梢网络(没有邻居的网络)；

注意：链路代价是按照出站接口的方向计算的！

三、SPF算法-Dijkstra算法

SPF算法的基本过程：

构建最短路径树时，路由器首先将它自己作为根，然后使用拓扑数据库中的信息，创建所有与它直连的邻居列表。到一个邻居的代价最小的路径将成为树的一个分枝，该路由器的所有邻居都被加入列表。检查该列表，看是否有重复的路径：如果有，代价高的路径将从列表中删除，代价低的路由器将被加入树；路由器的邻居也被加入列表，再次检查该列表是否有重复路径。此过程不断重复，直到列表中没有路由器为止！

四、区域

一个区域是构成一个网络的路由器的一个子集。将网络划分为区域是针对链路状态协议的3个不利影响所采取的措施：

必要的数据库要求内存的数量比距离矢量协议更多；

复杂的算法要求CPU时间比距离矢量协议更多；

链路状态泛洪扩散数据包对可用带宽带来了不利的影响，特别是不稳定的网络.

当一个网络中路由器的数量很多，以至数千台的时候，那么SPF算法给内存、CPU和带宽带来的负担是不可想象的！通过划分区域可以减小这些影响。当一个网络被划分为多个区域时，在一个区域内的路由器仅需要在本区域扩散LSA，因而只需要维护本区域的链路状态数据库。数据库越小，意味着需要内存越少，运行SPF算法需要的CPU周期也越少。如果拓扑改变频繁发生，引起的扩散将被限制在不稳定的区域！

区域边界路由器是连接两个区域的路由器，它属于所连接的两个区域，而且必须为每个区域维护各自的拓扑数据库！

五、距离矢量路由选择协议与链路状态路由选择协议的区别

距离矢量路由器发送它的整个路由表，而链路状态路由器仅仅发送有关它直连链路(邻居)的信息；