计算机网络网络层之链路状态路由算法

计算机网络网络层之链路状态路由算法 计算机网络网络层之链路状态路由算法

TIPS：知识出自哈尔滨工业大学李全龙老师的课程讲解。

网络抽象：图

链路状态路由算法

Djikstra算法

• 所有结点（路由器）掌握网络拓扑和链路费用
  • 通过“链路状态广播”
  • 所有结点拥有相同信息
• 计算从一个结点（“源”）达到所有其他结点的最短路径
  • 获得该结点的转发表
• 迭代：k次迭代后，得到达到k个目的结点的最短路径

符号：

• c（x，y）：结点x到结点y链路费用；如果x和y不直接相连，则=正无穷

• D（v）：从源到目的v的当前路径费用值

• p（v）：沿从源到v的当前路径，v的前序结点

• N’：已经找到最小费用路径的结点集合

Dijkstra算法

Dijkstra算法：例1

Dijkstra算法：例2

Dijkstra算法：讨论

算法复杂性：n个结点

• 每次迭代：需要检测所有不在集合N’中的结点w
• n(n_+1)/2次比较：O(n^2)
• 更高效的实现：

O ( n l o g n ) O(nlogn) O(nlogn)

存在震荡（oscillations）可能：

• e.g.，假设链路费用是该链路承载的通信量：