通信工程师交换技术考试链路状态路由算法

 　在线辅导　面授招生　考试大纲　指定教材　报名时间

1.链路状态路由算法
ARPANET-直采用距离向董路由算法，直到1979年它才被链路状态路由算法替代。两个主要问题导致了距离向童路由算法的消亡。第一，采用时延（队列长度）作为距离的度量值，在选择路由时没有将链路的带宽考虑进去；第二，节点间采用定时方式交换路由信息，所以距离向量路由算法的收敛速度比较慢，甚至出现像水平分裂算法那样的假象。因此，它被一种全新的链路状态路由（LinkStateRouting)算法所替代。
链路状态路由算法的思想十分简单，可以分五部分加以描述。每个路由器必须：
①发现它的邻居节点，并获取其网络地址；
②测量到各邻居节点的时延（或代价）；
③组装一个分组通告它刚知道的路由信息；
④将这个分组发送给所有其他网络节点；
⑤计算到所有其他节点的最短路径。
事实上，完整的拓扑结构和所有的链路时延都通过试验测量获得，并发布到网络中每一个节点。于是各个节点可以用Dijkstra算法来找出它到所有其他节点的最短路径。下面，我们将更详尽地讨论上述五个步骤。
①发现邻居节点
当一个节点被激活以后，它的第一个任务就是要知道谁是它的邻居，这是通过向每条点到点链路发送特殊的Hello分组来实现的。在另一端的节点应发回一个应答分组，以说明它是谁。所有网络节点的名字必须是全局。
当两个或多个节点通过一个局域网（LAN)连接起来时，情况就稍为复杂一些。如图24(a)所示，一个LAN将3个节点A,C和F直接连接起来。每个节点又与其他的节点相连。
可以想象用一个节点代表LAN。如图5-24(b)所示，引人了一个新的虚拟节点N，与A,C和F相连。从A经LAN到C的路径在这里表示为路径ANC。

如果是重复的，则丢弃它。如果一个分组的顺序号比目前已到达的最大的顺序号还小，则被认为是过时信息而加以废弃。在分组扩散过程中，寿命字段每单位时间递减一次，如果寿命为0,则删除该分组，以保证没有任何分组可以在网络中无限长地存活下去。
为了防止节点之间的链路出故障引起问题，规定所有的链路状态分组都需要应答。由于链路状态分组以洪泛方式扩散，这就要求毎个节点对接收到的链路状态分组能够自行确定需要向哪些邻节点转发、需要对哪些邻节点进行应答，所以每个节点需要构造一个如图5-26所示的分组处理数据结构。该围是图5-25(a)所示子网中节点B所用的数据结构，每一行对应于一个新近到达，但尚未完全处理完毕的链路状态分组。数据结构表记录了分组来自何处、它的顺序号和寿命以及描述链路状态的数据。另外，对应于B的每条输出链路（到A,C和F)各有一组发送标志位和应答标志位。发送标志位表示该链路状态分组必须发送给哪些邻节点，应答标志位表示应给哪些邻节点发送应答消息。
在图5-26中，如标志位所示，从A来的链路状态分组直接到达B,它必须被送往C和F,并且向A发应答。类似地，从F来的分组必须转发给A和C，并向F发应答。但是，当第三个来自节点E的分组到达时就有所不同。由于该分组已经到达两次，一次经过EAB,-次经过EFB。因此，它只需发往C,但要向A和F发应答，如标志位所示。如果在原始分组还在缓冲器中处理时就到达一个它的副本，标志位就得进行一下修改。例如，在表中的第四个来自C节点的分组被转发之前，又有一个C的状态信息分组的副本从F到达，那么六个标志位就应改为100011，表示不必再转发给FT,而应向F发应答。

⑤计算新路由
每个节点获得所有的链路状态分组后，便可以构造整个网络拓扑图，每一链路的两个方向都将标出时延（或代价）值。此时每个节点就可以在本地运行Dijkstra算法，从而确定到达所有目的节点的最短路径（或最小代价路径），并形成分组转发路由表。
链路状态路由算法在实际网络中得到了广泛的应用，如在Intemet中应用广泛的OSPF协议使用的就是该算法。另一个使用该算法的重要协议是IS-IS(IntermediateSystem-IntermediateSystem)协议，该协议应用于多种Intemet骨干网（包括老的NSFNET骨干网）和一些数字蜂窝系统中。

返回目录： 通信专业交换技术考试培训分组交换汇总

编辑推荐：

通信专业实务考试终端与业务教程汇总

通信专业实务考试设备与环境教程汇总

通信工程师考试培训交换理论基确汇总