直到1979年，arpanet都用的是距离矢量路由选择，之后变为由链路状态路由选择所代替。两个主要问题导致了 距离矢量路由选择算法的消亡。第一，因为延迟度量是队列长度，在选择路由时，并没有将线路的带宽考虑进去 。开始，所有的线路都是56kb/s，因此线路带宽并不是待考虑的因素。但当有些线路升级为23okb/s，乃至1． 544mb/s后，不考虑带宽因素就很成问题了。当然，也可以在延时变量中加人线路带宽因子。但第二个问题依然存 在，也就是算法往往耗去过多时间用于记录信息，即使使用了像水平分离这样的技术。因此，它被一种全新的算 法，现在叫作链路状态路由选择（link state routmg）算法所替代。现在各种各样的链路状态路由选择算法得到 了广泛的应用。

　　隐藏在链路状态路由选择之后的思想十分简单，可以分5部分加以描述。每个路由器必须完成以下的工作：

　　发现它的邻居节点，并知道其网络地址；

　　测量到它各邻居节点的延迟或开销；

　　组装一个分组以告之它刚知道的所有信息；

　　将这个分组发送给其他路由器；

　　计算到每个其他路由器的最短路径。

　　事实上，完整的拓扑结构和所有的延时都已被测量，并且被测量到各个路由器中。随后，各个路由器都可以用 dijkstra算法来找出最短路径。下面，将更详尽地讨论上述五个步骤。

　　（1）发现邻居节点

　　当一个路由器启动以后，它的第一个任务就是要知道谁是它的邻居，这是通过向每条点到点线路发送特殊的 hello分组来实现的。在另一端的路由器应发送回来一个应答来说明它是谁，这个名字必须是唯一的。

　　（2）测量线路开销

　　链路状态路由选择需要每个路由器知道它到邻居节点的延迟，至少得有个可信的估计值。取得延迟时间的最直接 方式就是发送一个要求对方立即响应的特殊的echo分组。通过测量一个来回的时间再除以2，发送方路由器就可以 得到一个可靠的延迟估计值。想要更精确些，可以重复这一过程多次，再取平均值。

　　其中一个有趣的话题是，在测量延迟时是否将载荷考虑进去。如果要考虑载荷因素，往返时间应该从echo分组 进人队列时开始计时；如果忽略载荷，计时器就得从echo分组排列队列第一位时开始计时。

　　两种方法都会有争议，在延时测量中引人流量因素意味着当一个路由器在两条相同带宽的线路间进行选择时， 如果一条线路总是有很重的负载，而另一条线路总是负载较轻，那么后者将被认为是一条更短的路径，这种选样 能导致良好的｀跬能。

　　（3）创建链路状态分组

　　一旦用于交换的信息收集起来，下一步就是构造一个包含所有数据的分组。该分组以发送者的标志符开头，紧 跟着是顺序号和年龄，和一个邻居节点列表，对于每个邻居节点，都给出了它们的延迟。

　　创建链接状态分组很容易，难的是决定何时创建分组。一种可能性是定期创建，即每隔一定时间间隔就创建一 次；另一种可能性是当出现重大事件时（像线路或邻居节点的增删，或它的特征值明显改变时）再创建。

　　（4）发布链路状态分组

　　本算法中最具技巧性的部分就是如何可靠地发行链路状态分组。当分组被发布和安装后，首先得到分组的路由 器将改变其路由选择。同时，别的路由器可能还在使用不同版本的拓扑结构，这样导致了不一致性、死循环、不 可达机器和其他问题。

　　首先描述基本发布算法，随后针对它进行一些调整。基本思想是利用扩散来发布链接状态分组。为了控制扩散 ，每个分组包含一个顺序号。该顺序号在每次发送新分组时加1。路由器记下它所见过的所有信息对（源路由器， 顺序号）。当一个新的链路状态分组到达时，它先查看一下该分组是否已收到过。如果是新的，把它再向除了进 人线路之外的所有线路发布；如果是重复的，则丢弃它。如果一个分组的顺序号比目前为止已到达的最大的顺序 号还小，贝刂被认为已过时而拒绝。

　　这个算法有一点问题，但这些问题是可以控制的。首先，如果顺序号循环使用，就会发生冲突。解决办法是使 用00jl位的顺序号；如果每秒钟发送一个链路状态分组，就得花137年才能使计数循环回来，所以避免了发生冲突 的可能性。

　　其次，如果一个路由器崩溃了，它将丢失其顺序号。如果它再从0开始，那么后面的分组可能会被当作重复分组 而被拒绝。

　　最后，如果顺序号传送后出现错误，比如发送方发送的序列号是4，但是由于产生了一位错误，接收方看到的序 列号是65540，那么序列号从5到65540都会被当成过时分组而遭拒绝，因为当前顺序号被认为是65540。

　　解决这些问题的办法是，在每个分组的顺序号之后再加上年龄字段，每秒钟将年龄递减1，当年龄变成零时，来自于那个路由器的信息就被丢弃掉。比如说，通常每lomin进入一个新分组，因 此当路由器关掉后，路由器的信息便会过时（或者6个连续的分组部