|
|
|
在20世纪80年代即将结束时，距离矢量路由算法的不足变得越来越明显。首先，V-D路由算法没有考虑物理线路的带宽，因为最初ARPANET的线路带宽都是56kb/s，没有必要在路由选择时考虑线路的带宽。其次，就是前面讨论的V-D路由算法的慢收敛问题，虽然使用水平分割或其他方法可以解决慢收敛问题，但同时会引起其他一些问题。在V-D路由算法中产生慢收敛问题的本质原因是路由器不可能得到有关网络拓扑结构，因为V-D路由算法只是在邻居路由器之间交换的部分路由信息，也就是说，在V-D路由算法中，路由信息的交换是不充分的。因此必须引入一种全新的路由算法，这种算法就是链路状态（Link-State）路由算法，简称L-S路由算法。
|
|
|
|
|
|
|
|
（1）路由器之间形成邻居关系。当某个路由器启动之后，要做的第一件事是知道它的邻居是谁，这可以通过向其邻居发送问候（Hello）报文来做到。
|
|
|
|
（2）测量线路开销。链路状态路由算法要求每个路由器都知道它到邻居路由器的延迟。获得到邻居路由器延迟的最直接方式就是发送一个要求对方立即响应的特殊的Echo报文，通过计算来回延迟再除以2，就可以得到延迟估计值。如果想要得到更精确的结果，可以重复这一过程，再取平均值。
|
|
|
|
（3）构造链路状态报文。一旦路由器获得所有邻居路由器的延迟，下一步就是构造链路状态报文。链路状态报文包含构造该报文的路由器标识，以及到每个邻居路由器的延迟。下图（a）给出了某网络的拓扑结构，对应的6个链路状态报文如下图（b）所示。
|
|
|
|
|
|
|
|
构造链路状态报文并不是一件困难的事情，难在何时构造这些报文。一种方法是定期进行；另一种方法是当网络出现大的变化时（如线路断开或重新连通、邻居路由器故障或恢复等情况）就构造新的链路状态报文。
|
|
|
|
（4）广播链路状态报文。链路状态路由算法的最重要也是最具有技巧性的部分就是如何将链路状态报文可靠地广播到网络中的每一个路由器。
|
|
|
|
完成链路状态报文广播的基本思想是利用扩散。由于扩散将导致网络中存在大量的重复报文，为了控制重复报文的数量，在每个链路状态报文中加上一个序号，该序号在每次广播新的链路状态报文时加1。每个路由器记录它所接收过的链路状态报文中的信息对（源路由器，序号），当路由器接收到一个链路状态报文时，先查看一下该报文是否已收到过。将新接收到的报文序号与路由器记录的最大序号进行比较，如果前者小于或等于后者，则说明该报文是重复报文，将其丢弃；否则该报文就是新的，应将它扩散到所有的输出线路上（除了接收该报文的线路外）。
|
|
|
|
仅仅使用序号来控制重复报文会有问题，但这些问题是可以控制的。首先是序号的循环使用可能会导致序号冲突，解决的办法是使用32位的序号，这样即使是每秒钟广播一次链路状态报文（实际上链路状态报文的广播间隔不止1秒钟），得花137年才能使计数循环回来，避免了发生冲突的可能性。其次，如果某路由器由于故障而崩溃了，当此路由器重新启动后，如果它的序号再从0开始，那么后面的链路状态报文可能会被其他路由器当作重复报文而丢弃。第三，如果链路状态报文在广播过程中序号出现错误，如将序号5变为1027（一位出错），那么序号为5到1027的报文将会被当成重复报文而丢弃，因为路由器认为当前的序号是1027，所有序号小于或等于1027的报文都认为是重复报文。
|
|
|
|
为了解决重复报文这个难题，还可以在每个链路状态报文中加上生存期（Age）字段，且每隔1秒钟减1。当生存期变为0时，报文被丢弃。
|
|
|
|
还可以对链路状态报文的广播过程作一些细微修改，使算法更强壮一些。如路由器接收到链路状态报文后，并不立即将它放入输出队列进行排队等待转发，而是首先将它送到一个缓冲区等待一会儿。如果已有来自同一路由器的其他链路状态报文先行到达，则比较一下它们的序号。如果序号相等，丢弃任何一个重复报文；否则丢弃老的报文。为了防止因为路由器之间的线路故障而导致链路状态报文的丢失，所有的链路状态报文都要进行应答。一旦通信线路空闲，路由器就会循环扫描缓冲区以选择发送一个链路状态报文或者应答报文。
|
|
|
|
对于上图（a）中的网络，路由器B的报文缓冲区如下图所示。这里的每一行对应于一个新到的但未完全处理完毕的链路状态报文。这张表记录了报文来自何处、报文的序号、生存期及链路状态报文。另外，对应于B到每个邻居（到A、C和F）各有一个发送标志和应答标志。发送标志位用于标识必须将链路状态报文发送到该邻居，应答标志位用于标识必须给该邻居发送应答报文。
|
|
|
|
|
|
|
|
在上图中，A产生的链路状态报文可直接到达B，而B必须将此报文再扩散到C和F，同时B必须向A发送应答报文。类似的，F产生的链路状态报文到达B后，B必须向A和C进行转发，同时B必须向F发送应答报文。
|
|
|
|
但是，对于上图中来自E的报文就有所不同。假设B两次收到来自E的报文，一次经过EAB，另一次经过EFB。因此，B只需将E产生的链路状态报文发往C即可，但要向A和F发送应答报文。
|
|
|
|
如果重复报文在前一个报文未出缓冲区时到达，表中的标志位就得进行修改。例如，在上图中，当B还未处理完由C产生的链路状态报文，又接收到一个从F传来的C的链路状态报文时，此时应将C行的标志位由101010改为100011，表示要向F发送应答报文，而不必将C的链路状态报文再发向F。
|
|
|
|
（5）计算最短路径。由于网络上的每个路由器都可以获得所有其他路由器的链路状态报文，每个路由器都可以构造出网络的拓扑结构图。此时路由器可以根据Dijkstra算法计算出到所有目的节点的最短路径，并把计算结果填到路由器的路由表中。
|
|
|
|
|
|
链路状态路由算法使用事件（链路中断或路由器崩溃等事件）来驱动链路状态更新，而且当网络拓扑结构发生变化时能够快速收敛。另外，链路状态路由算法具有良好的扩展性，能够运用于大规模网络中。但链路状态路由算法对链路带宽及路由器的处理能力和存储空间都要求比较高。
|
|
|
