路由算法：分类 非自适应算法(Non-adaptive Algorithm)/静态路由 (Static Routing)：事先计算好每对节点之间的“最优” 路径，然后在每个路由器配置好对应的路由表 ■用户主机 小规模网络 自适应算法(Adaptive Algorithm)/动态路由 (Dynamic Routing):根据网络拓扑结构和状态的变 化动态调整“最优”路径，反映到每个路由器就是需要动 态更新路由表 动态性大的网络 大规模网络 “最优”路径度量：跳数、 物理距离、队列长度、排队延迟、可用带宽等
11 路由算法:分类 ◼ 非自适应算法（Non-adaptive Algorithm）/静态路由 （Static Routing） ：事先计算好每对节点之间的“最优” 路径，然后在每个路由器配置好对应的路由表 ◼ 用户主机 ◼ 小规模网络 ◼ 自适应算法（Adaptive Algorithm）/动态路由 （Dynamic Routing） ：根据网络拓扑结构和状态的变 化动态调整“最优”路径，反映到每个路由器就是需要动 态更新路由表 ◼ 动态性大的网络 ◼ 大规模网络 “最优”路径度量：跳数、物理距离、队列长度、排队延迟、可用带宽等
自适应/动态路由算法 距离矢量算法 ■链路状态算法 12
自适应/动态路由算法 ◼ 距离矢量算法 ◼ 链路状态算法 12
路由算法：图模型 图中的节点表示路由器或者网络 图中的边对应于网络中的链路 每条边上都一个相应的开销(Cost): 跳数、物理距离、队列长度、 排队延迟、可用带宽等因素的函数 A 3 C 4 D 9 3 E 路由算法就是要找出图中任意两个节点之间开销最小的路径
13 路由算法：图模型 A C B D E F 3 2 4 9 3 1 1 7 路由算法就是要找出图中任意两个节点之间开销最小的路径 ◼ 图中的节点表示路由器或者网络 ◼ 图中的边对应于网络中的链路 ◼ 每条边上都一个相应的开销(Cost)：跳数、物理距离、队列长度、 排队延迟、可用带宽等因素的函数
优化原侧 路由中最优路径=算法中最短路径 最优化原则(Optimality Principle):如果路由器]在从路由 器B到路由器M的最优路径上，那么J到M的最优路径也必定遵循 同样的路由 Sink Tree:从所有源到一个指定目标的最优路径的集合构成了 一 颗以目标节点为根的树 B B E G M 。无环 (a) (b) Figure 5-6.(a)A network.(b)A sink tree for router B. 14
优化原则 ◼ 最优化原则（Optimality Principle）：如果路由器J在从路由 器B到路由器M的最优路径上，那么J到M的最优路径也必定遵循 同样的路由 ◼ Sink Tree：从所有源到一个指定目标的最优路径的集合构成了 一颗以目标节点为根的树 14 路由中最优路径=算法中最短路径 无环
距离矢量路由：概述 距离矢量算法，也称为Bellman-Ford算法 m距离矢量(DV:Distance Vector) ·每个节点都维护一个包含了到所有其它节点的“距 离”的路由表，也称为矢量表 每个节点都将自己的路由表（矢量表）分发给它的 邻居节点 “距离”：跳数、 物理距离、队列长度、排队延迟、可用带宽等 15
15 距离矢量路由：概述 ◼ 距离矢量算法，也称为Bellman-Ford算法 ◼ 距离矢量（DV： Distance Vector） ◼ 每个节点都维护一个包含了到所有其它节点的“距 离”的路由表，也称为矢量表 ◼ 每个节点都将自己的路由表（矢量表）分发给它的 邻居节点 “距离”：跳数、物理距离、队列长度、排队延迟、可用带宽等