路由选择算法与链路状态

路由选择算法可以怎样分类？

分类维度	类型	特征
信息范围	集中式	已知全局状态信息, 又称链路状态算法 (LS)
信息范围	分散式	仅知相邻节点, 靠交换与迭代算最短路径, 又称 DV
变化响应	静态	链路开销几乎不随时间变化
变化响应	动态	链路开销随网络状态变化
负载敏感	负载敏感	链路开销反映网络拥塞水平
负载敏感	负载迟钝	链路开销不明确反映网络拥塞水平

链路状态算法如何工作？

• 前提: 每台路由器掌握全网拓扑与链路开销;
• 常用算法: Dijkstra 算法与 Prim 算法;
• 结果: 算出到所有目的节点的最短路径, 据此填充转发表;

链路状态算法会带来什么问题？

• 路由震荡: 使用负载敏感的开销时, 链路开销随实时拥塞变化;
• 后果: 最短路径在两个方向之间来回切换, 转发路径持续抖动;