6、Apple Talk的路由选择表维护协议–RTMP

 

      3、广播更新（Broadcast Updates）
      当路由器刚开机或者刚启动路由协议时，它如何寻找其他的路由器呢？它如何向其他路由器宣告自己的存在或者出现呢？大家可以想一下，在现实生活中，我们在一堆人中找某个人时，你会一个一个的去问还是大喊一声呢？显而易见，在路由选择协议的更新中，它使用了广播的更新方式.

 

 

 　7、水平分割（Split Horizon）详见CCNP-BSCI 002距离矢量路由协议–水平分割

　 8、计数到无穷大（在后面讲解RIP的时候会将到）

　 9、触发更新（Triggered Update）

　　触发更新又名快速更新：当路由收敛后，如果某台路由器得知自己直连的一条链路的度量变化了，（无论好或者坏）那么该路由器将立即发送更新信息，不必等到更新计时器的到期。

　 10、抑制计时器（Holddown Timer）

　　触发更新为正在进行收敛的网络增加了应变能力，为了降低接受错误路由信息的可能性，抑制计时器引入了某种程度的怀疑量

　　如果到一个目标的度量发生改变（无论是增大还是减小），那么路由器将会将该路由条目置为抑制状态——即加上一个抑制计时器。直到计时器超时，路由器才会接受有关此路由的信息。

　　它虽然降低了错误路由的可能性，但是收敛时间却会因此而变长，因为在对其进行配置的时候，一定要根据全网的情况来配置一个合适的值。

　　11、异步更新（Asynchronous Update）

　　假设有一组连接在以太网段上的路由器群，大家都记得，以太网的工作方式。如果每台路由器都共享一个广播网络的时候，很可能会出现更新同步的情况——几台路由器的更新时间同时到期，同时更新。那么就会造成报文的碰撞，然后根据CSMA/CD，它们会回退，但是，很可能这样一来影响到整个系统的时延，最终会造成整个网络的同步。所以，我们通常使用两种办法来防止同步保持异步更新：

　　·每台路由器的更新计时器都独立于路由进程，因为不会受到路由器处理负载的影响

　　·在每个更新周期中加入一个小的随机偏移量。

链路状态路由协议：

 

一、概述
 

如果把距离矢量路由选择协议比作是由路标提供的信息，那么链路状态路由选择协议就是一张交通线路图；因为它有一张完整的网络图，所以它是不容易被欺骗而作出错误的路由决策的；链路状态不同于距离矢量依照传闻进行路由选择的工作方式，每台路由器都会产生一些关于自己、本地直连链路以及这些链路的状态（以此而得名）和所有直接相连邻居的信息。这些信息从一台路由器传送到另一台路由器，每台路由器都做一份信息拷贝，但是决不改动这些信息，最终每台路由器都有一个相同的有关网络的信息，并且每台路由器可以独立地计算各自的最优路径；
链路状态协议，有时也叫最短路径优先协议或分布式数据库协议，是围绕着图论中的一个著名算法-E.W.Dijkstra的最短路径算法设计的；链路状态协议有以下几种：
 
IP开放式最短路径优先OSPF；
CLNS或IP ISO的中间系统到中间系统IS-IS；
DEC的DNA阶段5；
Novell的NetWare链路服务协议NLSP.
 

链路状态路由选择协议的基本步骤如下：
 
1、每台路由器与它的邻居之间建立联系，这种联系称为邻接关系；
2、每台路由器向每个邻居发送链路状态通告LSA。对每台路由器链路都会生成一个LSA，LSA用于标识这条链路、链路状态、路由器接口到链路的代价度量值以及链路所连接的所有邻居。每个邻居在收到通告后将依次向它的邻居转发(泛洪)这些通告；
3、每台路由器要在数据库中保存一份它所收到的LSA的备份，如果所有路由器工作正常，那么它们的链路状态数据库应该相同；
4、完整的拓扑数据库，也叫做链路状态数据库，Dijkstra算法使用它对网络图进行计算得出到每台路由器的最短路径；接着链路状态协议对链路状态数据库进行查询找到每台路由器所连接的子网，并把这些信息输入到路由表中.
 
 

二、邻居
 

邻居发现是建立链路状态环境并运转的第一步，它将使用Hello协议(Hello Protocol)。Hello协议定义了一个Hello数据包的格式和交换数据包并处理数据包信息的过程；Hello数据包至少应包含一个路由器ID CRID和发送数据包的网络地址。路由器ID可以将发送该数据包的路由器与其他路由器惟一地区分开，例如，路由器ID可以是路由器一个接口的IP地址。数据包的其他字段可以携带子网掩码、Hello间隔、线路类型描述符和帮助建立邻居关系的标记，其中Hello间隔是路由器在宣布邻居死亡之前等待的最大周期；
 
当两台路由器已经互相发现并将对方视为邻居时，它们要进行数据库同步过程，即交换和确认数据库信息，直到数据库相同为至；为了执行数据库同步，邻居之间必须建立邻接关系，即这们必须就某些特定的协议参数，如计时器和对可选择能力的支持，达成一致意见。通过使用 Hello数据包建立邻接关系，链路状态协议就可以在受控的方式下交换信息，与距离矢量相比，这种方式仅在配置了路由选择协议的接口上广播更新信息(组播)！
 
除建立邻接关系外，Hello数据包还可作为监视邻接关系的握手信号。如果在特定的时间内没有从邻接路由器收到Hello数据包，那么就认为邻居路由器不可达，随即邻接关系被解除。典型的Hello数据包交换间隔为10s，典型的死亡周期是交换间隔的4倍.
 
 
 
三、链路状态泛洪扩散(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个小时或者更长，那么这种方法是不可行的；
 
在路由器启动期间会出现一种更常见的困难。如果路由器A重启之后，它无法记得上次使用的序列号，必须重新使用1.但是如果路由器A的邻居仍然在数据库中保留了路由器A上次的序列号，那么越小的序列号也就是越旧的序列号，因而会被忽略；
 
更好的解决办法是在泛洪扩散行为中添加新的规则：如果一台重新启动的路由器向邻居发送LSA的序列号比邻居保存的序列号还要老，那么邻居会发回自己保存的LSA和序列号，这样就台路由器将知道启动前自己使用的序列号并作出相应的调整；
 
然而仍需要小心，最近使用过的序列号不能接近上限，否则，重新启动的路由器将不得不再次重新启动。必须设定规则限制路由器“跳跃”地使用序列号。例如，规则指明一次序列号增加不能超过整个序列号空间的二分之一(实际公式要复杂，因为要考虑年龄的限制)；
 

2）循环序列号空间
 
这种方法数字是循环使用的，在32位空间内紧跟在4 294 967 295后面的是0；它在重新启动路由器后也可能会遇到同线性序列号一样的问题！其结构如下：
 
循环序列号建立了一个不合逻辑的奇特位。如果X是1到4 294 967 295之间的一个数，那么0<X<0！在运行正常的网络中通过声明两条规则可以维持这种条件，其中声明的规则来确定什么时候一个序列号大于或小于另一个序列号。假设序列号空间为n，则两个序列号a和b，如果满足以下任意一种条件，则认为a更新(数量更大)：
a<b,且(a-b)<=n/2
a<b,且(b-a)>n/2
 
假设这样一种情况：在一个网络中使用6位序列号空间。现在其中的一台路由器决定离线，当它在离线之间，突然发送了3个相同且序列号为44(101100)的LSA。不幸的是，一个邻居也发生了故障，丢掉了几位数据，丢失的数据位是第2个LSA和第3个LSA序列号中的1位，随即该邻居路由器向外泛洪了这3个LSA，结果造成3个LSA序列号各不相同：
 
应用循环规则可得：44比40更新，40比8更新，8又比40更新！这个结论使3个LSA都持续扩散下去，数据库也不断地被最新的LSA更新，直到数据库缓存被塞满，CPU超载为止，最终整个网络崩溃！
 

3）棒棒糖序列号空间
 
这种方法是线性序列号空间和循环序列号空间的综合，它有一个线性组件和一个圆形组件；性线空间的缺点是不能循环使用序列号，即序列号是有限的，而圆形空间的缺点是不存在一个数小于其他所有的数；其结构如下：
 
当路由器重启时，它将从小于其他所有数的a开始，邻居将会识别出这个数，这时如果邻居数据库中还保留有上次序列号为b的LSA，那么它们会发送b给路由器A，则路由器A将跳至该序列号。在知道自己重启前使用的序列号之前，路由器A可能会发送不止一个LSA，因此，在邻居通知路由器A上次使用的序列号或上次使用的序列号从所有数据库中消失之前，必须准备充足的启动数以便路由器A不会用光所有重启序列号；
 
这些线性重启序列号开成了棒棒糖的棒；在这些数用完或邻居提供了使路由器A跳转的序列号之后，路由器A进行循环数空间，也就是棒棒糖的糖体部分。棒棒糖序列号空间使用了有符号数，即-k<0<k。从-k到-1的负数形成棒棒，从0到k的正数形成循环空间。其规则如下：
 
假设给出两个数a、b及一个序列号空间n，当且仅当：
a < 0 且 a < b, 或
a > 0, a < b, 且 (b-a) < n/2, 或
a > 0, b > 0, a > b, 且 (a-b) > n/2
认为b比a更新！

棒棒糖形序列号空间用在OSPFv1(RFC 1131)中。当前使用的OSPF版本2采用了线性和棒棒糖形序列号空间的最好的特性。OSPFv2像棒棒糖形序列号一样使用了从0×80000001开始的有符号数空间，但是当序列号数变为正数时，序列号间持续保持线性直至到达最大数0×7FFFFFFF为止。此时，在重启之前OSPF进程必须从所有链路状态数据库中删除LSA。
  
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并且在达到最大年龄之前将它的计时器复位。链路状态刷新计时器(LSRefesh Timer)就是做此用途的；一旦计时器超时，路由器将向所有邻居泛洪扩散新的LSA，收到的邻居会把有关路由器记录的年龄设置为新接收到的年龄。 OSPF定义MaxAge为1小时，LSRefresh Time为30min。
 
 

四、链路状态数据库
 

除了邻居发现和泛洪扩散LSA，链路状态路由选择协议的第3个主要任务是建立链路状态数据库。链路状态数据库，也叫拓扑数据库把LSA作为一连串记录保存下来。LSA包括两类通用信息：
 
路由器链路信息－使用路由器ID、邻居ID和代价通告路由器的邻居路由器，这里的代价是发送LSA路由器到其邻居的代价；
末梢网络信息  －使用路由器ID、网络ID和代价通告路由器直接连接的末梢网络(没有邻居的网络)；
 
注意：链路代价是按照出站接口的方向计算的！
 
 

五、SPF算法-Dijkstra算法

SPF算法的基本过程：

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

六、区域
 

一个区域是构成一个网络的路由器的一个子集。将网络划分为区域是针对链路状态协议的3个不利影响所采取的措施：
 
必要的数据库要求内存的数量比距离矢量协议更多；
复杂的算法要求CPU时间比距离矢量协议更多；
链路状态泛洪扩散数据包对可用带宽带来了不利的影响，特别是不稳定的网络.

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

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

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

距离矢量路由器仅向这的邻居发送路由信息，而链路状态路由器向整个网络中的所有路由器发送邻居信息；

距离矢量路由器通过使用不同的Bellman-Ford算法，而后者则通常使用不同的Dijkstra算法。