（二）路由算法

1. 静态路由和动态路由

1.1. 静态路由

• 非自适应路由选择；

• 特点：简单，开销较小，但不能及时适应网络状态的变化；

1.2. 动态路由

• 自适应路由选择；

• 特点：能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大；

• 一般是通过软件层面的算法来实现，路由算法一般是指动态路由算法；

2. 动态路由算法

2.1. 距离矢量算法

• 距离向量路由算法（Bellman-FordRouting Algorithm），也叫做最大流量算法（Ford-FulkersonAlgorithm）；

• 作为距离向量协议的一个算法，如 RIP，BGP，ISO，IDRP，NOVELL，IPX；

• 实例分析

  

  • NOTE：线路不对称，即 $d(i\to j)\ne d(j\to i)$；

  • C 的邻节点为 B，D，E，故 C 可以选择以其中任一节点为中转，到达其他任何节点；

    

  • 对于每一个目的地，取上述三个情况下距离最小值，即为 C 更新后的距离向量表

    • 对应的向量表为 $(11,6,0,3,5,8)$；

    • 对应的中转节点为：$(B,B,/,D,E,B)$；

2.2. 链路状态路由算法

• 步骤

  • 1）发现邻居节点，并知道其网络地址；

  • 2）测量到各个邻居节点的延迟或开销，即链路状态；

  • 3）组装一个分组以告之链路状态信息；

  • 4）将这个分组发送给其他路由器；

  • 5）各路由器最终得到完整的链路拓扑结构和状态信息；

  • 5）各路由器用 Dijkstra 算法等计算最短路径。

• 实例分析

  

  • L-S 路由算法：即链路状态路由算法（Link Status）；

2.3. 层次路由算法（了解）