计算机网络之链路状态路由选择算法（LS）（基于链路状态路由选择算法的路由协议有）

计算机网络之链路状态路由选择算法（LS）（基于链路状态路由选择算法的路由协议有）

一、准备知识

链路状态路路由选择算法是一种全局式路由选择算法。在此算法中，我们是假设所有网络拓扑和链路费用都是已知的（实践中通常是通过让每个结点向网络中所有其他节点广播链路状态分组来完成的）【OSPF协议】，通过节点广播使所有结点具备了该网络等同的完整视图。获得视图之后，通过LS算法可以计算出从源节点到网络任意结点的最低费用路径。.        我们下面给出的链路状态路由选择算法叫做Dijkstra算法，在了解此算法之前，我们首先明白以下几个记号：

D(v)：表示从源节点到目标结点v的最低费用路径的费用 p(x)：从源结点到目标节点v（最低费用路径）的前一个结点（v的邻居） N'：如果从源到v的最低费用路径已知，那么可以将v加入N'集合中 w：可被加入到N' 中结点，且节点的费用最小

.

二、LS算法原理

假设源节点为u，我们要找到从源节点到其他节点的最低消费路径，其算法如下：

1、初始化： N' = {u} D(u)已知，将u加入到N'集合中 for all nodes for n 对于除u以外的所有节点n if n is a neighbor of u 如果n节点使u节点的相邻节点 then D(n) = c(u，n) 那么将n节点的D(n)为c(u，n) else D(n) = ∞ 否则D(n)为无限大 2、循环阶段 find w not in N' such that D(w) is a minimum 找出不在N'中的w【最小的D(w)】 add w to N' 将w添加到N'中 update D(n) for each neighbor n of w and not in N' 更新与w节点相邻的节点n的D(n)，且n不能在N'中 D(n) = min( D(n) ， D(w)+c(w，n) ） 将D(n)置为D(n)和D(w)+c(w，n)中的最小值 until N' = N 直到N' = N是结束循环

.

三、LS震荡现象

假设：1、链路费用是该链路所承载的数据量；2、初始路由是B逆时针发送1个单位给A，D顺时针发送1个单位给A，C逆时针发送e个单位给B，B再给A         #注：红色箭头表示B、C、D路由器会有持续的1个单位，e个单位、1个单位的数据要发往路由器A.

这样的现象我们称之为拥塞敏感的路由选择震荡现象，这种现象很可能会导致如下现象：        假设B路由现处于图3-1b）状态中，并将数据转发给C，C转发给D，但是此时D的路由表更新了，那么此时链路状态将会变成3-1c）的情况。D会将先前的数据又转发给C，C又将转发给B，如果此时路由表又开始更新的话，那么将会变成图3-1d）所示。如此一来，数据报将在B、C、D之间来回转发并且到达不了A，当数据的TTL=0时，数据报将会被丢弃.

针对这种现象，链路状态算法通产会采取某种机制：让每台路由器发送链路通告的时间随机化，以确保不是所有的路由器都同时运行LS算法（即每台路由器执行LS算法的实际是不同的）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。