(二)链路状态算法（Link-State Routing）
　
链路状态算法，有时也称为最短路径优先算法（SPF-Shortest Path First）。与向量距离算法不同的是，这种算法需要每一个路由器都保存一份最新的关于整个网络的网络拓扑结构数据库，因此路由器不仅清楚地知道从本路由器出发能否到达某一指定网络，而且在能到达的情况下，还能选择出最短的路径以及使用该路径将经过哪些路由器。使用链路状态算法的路由协议有NLSP，OSPF和IS-IS。　
　
链路状态算法使用LSP（链路状态数据包，Link-State Packets），网络拓扑数据库，SPF路径选择算法，SPF树，最终计算出从该路由器到其他目标网络的最短路径，这些路径就构成了路由表。在算法中，需要给每个路由器一个唯一的名字或标识。
　
1、 链路状态网络发现机制 该机制用于创建整个网络的一幅全景图，所有的路由器都保存该图的一个副本，从而保持一致。其具体工作步骤如下：
　
　（1）每个路由器都必须知道它的邻居是谁，这一点需要相邻的路由器之间互相通知。
　
　（2）每个路由器都将LSP（链路状态数据包）发送给网络上其他的路由器，LSP的内容包括该路由器通过哪些网络与哪些路由器直接连接，以及相应连接的传输代价。以图4中所示的网络为例，路由器B向外发送的LSP包括(（B,A,10.2.0.0）,(B,C,10.3.0.0)),表示B通过10.2.0.0与A连接，通过10.3.0.0与C连接（这里仍然假设相邻路由器之间的传输代价为1）。
　
　（3）下一步，路由器将根据收到的LSP逐步地构建起网络的拓扑数据库（即SPF树，树的根接点为该路由器本身）。
　
　（4）接下来，根据网络的拓扑结构数据库来判断目标网络是否可到达及其最短路径（常用算法为Dijikstra算法）。
　
　（5）路由器将第4步计算出的到这些目标网络的最短路径及其所使用的该路由器的网络端口添加到路由表中。
　
　（6）链路状态算法要求各路由器的网络拓扑结构数据库要一致。因此当链路状态发生变化时，最先检测到这一变化的路由器需要将变化的情况发送给其他的路由器。每当路由器收到新的LSP，它都会重新计算最短路径并更新路由表，这样才能保证各路由器在网络拓扑结构方面重新达成一致。
　
2、考虑的因素
　
在采用链路状态算法时，应当考虑以下两方面的因素：
　
路由器的存储空间和处理能力
　
由于采用链路状态算法时路由器不但要保存来自其他路由器的LSP，而且还要保存网络的拓扑结构和路由表，所以其存储空间一定要大。另外，根据SPF树计算最短路径的算法较为复杂，因此要求路由器的处理能力要强。
　
带宽
　
在建立SPF树的最初阶段，有大量的LSP需要通过网络进行传输，因此对网络带宽的要求较高。如果带宽不够，不仅影响路由器收敛的速度，而且会影响正常的数据传输。
　
3、可能出现的问题及解决办法
　
与距离向量算法类似的是，链路状态算法同样必须保证所有的路由器能够收到所有必需的LSP。图6给出了一个可能发生问题的案例。 假设路由器C首先检测到C和D之间的Network 1发生故障，那么象前面说的那样，路由器C将把该故障情况以LSP的方式发送给网络上的其他路由器B、D、和A（为了讲述方便，称该LSP为LSP1）。假设Network 1很快地就恢复了正常，而且路由器D先检测到，那么路由器D将把Network 1恢复正常的情况以LSP的形式再发送给路由器A、C和B（称之为LSP2）。如果由于某种原因（比如不同网络的传输速度不同或传输路径长度不同等），LSP2先于LSP1到达路由器A。这时，问题就出现了，路由器A究竟应该把哪一个LSP作为反映最终情况的LSP呢？

也许大家会说这里的巧合也太多了吧！其实不然，在实际的应用中，网络的拓扑结构要复杂的多，而且各方面因素的影响也很多，比如：路由器启动顺序的先后将影响到LSP发送的顺序，大型网络中不同子网的网络传输速度也可能有较大差别等等。
　
链路状态算法可以采用以下几种技术来解决这些潜在问题:
　
　延长LSP的发送周期。
　
　以多点发送LSP（Multicast）代替广播发送LSP（Broadcast）。
　
在由多个LAN互连组成的网络中，可以指定一个或多个路由器用于存放各路由器发送的LSP，其他的路由器通过这些指定路由器获得一致的拓扑数据。
　
在大型网络中，可以设定一个由不同区域组成的层次结构。某一级区域中的路由器不必存储和处理来自不同区域路由器的LSP。
　
使用LSP时间戳、顺序号等手段来解决LSP发送过程中的顺序问题。
　
(三)两种算法的比较
　
上述两种算法的差别基本上可以归结为下表中的四点,可以以此作为具体应用中选择路由协议的技术依据。