链路状态路由

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

理解链路状态路由算法的三个关键

• 了解邻居：路由器不发送其路由表，而是仅发送有关其邻居的信息。路由器广播其身份以及与其他路由器直接相连链路的成本。
• 泛洪：每个路由器将信息发送到互联网中的每个其他路由器，但其邻居除外。此过程称为泛洪。每个接收到数据包的路由器都会将其副本发送给所有邻居。最后，每个路由器都会收到相同信息的副本。
• 信息共享：当信息发生变化时，路由器才会将信息发送给其他所有路由器。

链路状态路由有两个阶段

可靠泛洪

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

路由计算

每个节点在图上使用 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 到 E 和 F 的成本设置为无穷大。

步骤 2

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

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

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

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

注意：顶点 D 与顶点 E 没有直接连接。因此，D(F) 的值为无穷大。

步骤 3

在上表中，我们观察到在第二步中，E 和 B 都具有最小成本路径。让我们考虑顶点 E。现在，我们确定通过 E 的剩余顶点的最小成本路径。

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

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

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

步骤 4

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

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

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

步骤 5

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

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

最终表

缺点

链路状态路由由于泛洪会产生大量流量。泛洪可能导致无限循环，这个问题可以通过使用生存时间字段来解决。