链接状态路由

本文概述

• 链接状态路由分为两个阶段
• 让我们来描述一些符号
• 算法

链接状态路由是一种技术, 其中每个路由器与互联网络中的每个其他路由器共享其邻居的知识。

了解链接状态路由算法的三个关键：

• 关于邻居的知识：路由器仅发送有关其邻居的信息, 而不是发送其路由表。路由器将其标识和直接连接的链接的成本广播到其他路由器。
• 泛洪：每个路由器都将信息发送到互联网络上除邻居之外的其他所有路由器。此过程称为“泛洪”。每个接收到数据包的路由器都会将副本发送到其所有邻居。最后, 每个路由器都会收到相同信息的副本。
• 信息共享：仅当信息发生更改时, 路由器才会将信息发送给其他路由器。

链接状态路由分为两个阶段

可靠的洪水

• 初始状态：每个节点都知道其邻居的成本。
• 最终状态：每个节点都知道整个图。

路线计算

每个节点在图上使用Dijkstra算法, 以计算到达所有节点的最佳路由。

• 链接状态路由算法也称为Dijkstra算法, 该算法用于查找从一个节点到网络中其他每个节点的最短路径。
• Dijkstra算法是一种迭代算法, 它具有以下特性：在算法的第k次迭代之后, 对于k个目标节点而言, 成本最低的路径是众所周知的。

让我们来描述一些符号

• c（i, j）：从节点i到节点j的链接成本。如果i和j节点没有直接链接, 则c（i, j）=∞。
• D（v）：它定义了从源代码到目标v的路径成本, 该成本当前最低。
• P（v）：它定义前一个节点（v的邻居）以及从源到v的当前最小成本路径。
• N：这是网络中可用节点的总数。

算法

Initialization
N = {A}     // A is a root node.
for all nodes v
if v adjacent to A
then D(v) = c(A, v)
else D(v) = infinity
loop
find w not in N such that D(w) is a minimum.
Add w to N
Update D(v) for all v adjacent to w and not in N:
D(v) = min(D(v) , D(w) + c(w, v))
Until all nodes in N

在上述算法中, 循环之后是初始化步骤。循环执行的次数等于网络中可用节点的总数。

让我们通过一个例子来理解：

在上图中, 源顶点为A。

步骤1：

第一步是初始化步骤。当前已知的从A到其直接连接的邻居B, C, D的最小成本路径分别为2, 5, 1。从A到B的成本设置为2, 从A到D的成本设置为1, 从A到C的成本设置为5。从A到E和F的成本设置为无穷大, 因为它们没有直接链接到A。

第2步：

在上表中, 我们观察到顶点D在步骤1中包含最小成本路径。因此, 将其添加到N中。现在, 我们需要确定通过D顶点的最小成本路径。

a）计算从A到B的最短路径

v = B, w = D
D(B) = min( D(B) , D(D) + c(D, B) )
     = min( 2, 1+2)>
     = min( 2, 3)
The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b）计算从A到C的最短路径

v = C, w = D
D(B) = min( D(C) , D(D) + c(D, C) )
     = min( 5, 1+3)
     = min( 5, 4)
The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</p>

c）计算从A到E的最短路径

v = E, w = D
D(B) = min( D(E) , D(D) + c(D, E) )
     = min( ∞, 1+1)
     = min(∞, 2)
The minimum value is 2. Therefore, the currently shortest path from A to E is 2.

注意：顶点D没有与顶点E的直接链接。因此, D（F）的值是无穷大。

第三步：

在上表中, 我们观察到在步骤2中E和B的成本路径最少。让我们考虑E顶点。现在, 我们确定通过E的剩余顶点的最小成本路径。

a）计算从A到B的最短路径。

v = B, w = E
D(B) = min( D(B) , D(E) + c(E, B) )
     = min( 2 , 2+ ∞ )
     = min( 2, ∞)
The minimum value is 2. Therefore, the currently shortest path from A to B is 2.

b）计算从A到C的最短路径。

v = C, w = E
D(B) = min( D(C) , D(E) + c(E, C) )
     = min( 4 , 2+1 )
     = min( 4, 3)
The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

c）计算从A到F的最短路径。

v = F, w = E
D(B) = min( D(F) , D(E) + c(E, F) )
     = min( ∞ , 2+2 )
     = min(∞ , 4)
The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

步骤4：

在上表中, 我们观察到B顶点在步骤3中具有最小的成本路径。因此, 将其添加到N中。现在, 我们确定通过B的其余顶点的最小成本路径。

a）计算从A到C的最短路径。

v = C, w = B
D(B) = min( D(C) , D(B) + c(B, C) )
     = min( 3 , 2+3 )
     = min( 3, 5)
The minimum value is 3. Therefore, the currently shortest path from A to C is 3.

b）计算从A到F的最短路径。

v = F, w = B
D(B) = min( D(F) , D(B) + c(B, F) )
     = min( 4, ∞)
     = min(4, ∞)
The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

步骤5：

在上表中, 我们观察到C顶点在步骤4中具有最小的成本路径。因此, 将其添加到N中。现在, 我们确定通过C的其余顶点的最小成本路径。

a）计算从A到F的最短路径。

v = F, w = C
D(B) = min( D(F) , D(C) + c(C, F) )
     = min( 4, 3+5)
     = min(4, 8)
The minimum value is 4. Therefore, the currently shortest path from A to F is 4.

决赛桌：

坏处：

由于泛洪, 在线路状态路由中创建了大量流量。泛洪可能导致无限循环, 可以使用“离开时间”字段解决此问题