●●● ●●●● ●●●●● ●●●● 路由算法 ●●●●● ●●●● B C A 公平性和最优性之间的冲突 linwei@bbi.edu.cn
linwei@bbi.edu.cn 16 路由算法 公平性和最优性之间的冲突
●●● ●●●● ●●●●● ●●●● 路由算法 ●●●●● ●●●● ●路由算法可分成两类: Adaptive algorithms:-根据当前的业务流量, 拓扑的变化改变路由决策,以反映这些变化。 Non- adaptive algorithms-也叫静态路由。 linwei@bbi.edu.cn
linwei@bbi.edu.cn 17 路由算法 ⚫ 路由算法可分成两类： ⚫ Adaptive algorithms： - 根据当前的业务流量， 拓扑的变化改变路由决策，以反映这些变化。 ⚫ Non-adaptive algorithms – 也叫静态路由
●●● ●●●● ●●●●● ●●●● 优化原则 ●●●●● ●●●● ●优化原则 如果路由器J是在从路由器工到K的最优路径上,那 ,从J到K的最优路径也必定沿着同样的路由路 径 最优化原则的一个直接结果是:从所有的源到一个 指定目标的最优路径的集合构成一棵以目标节点为 根的树,称为汇集树 linwei@bbi.edu.cn
linwei@bbi.edu.cn 18 优化原则 ⚫ 优化原则 如果路由器J是在从路由器I到K的最优路径上，那 么，从J到K的最优路径也必定沿着同样的路由路 径。 最优化原则的一个直接结果是：从所有的源到一个 指定目标的最优路径的集合构成一棵以目标节点为 根的树，称为汇集树
●●● ●●●● ●●●●● ●●●● 优化原则 ●●●●● ●●●● B A (b) (a)一个子网(b)路由器B的汇集树
linwei@bbi.edu.cn 19 优化原则 (a) 一个子网 (b) 路由器B的汇集树
●●● ●●●● ●●●●● ●●●● 最短路径路由 ●●●●● ●●●● ●使用广泛(简单且易于理解) 最短路径测度( Path Length) 跳数 °物理距离 平均的排队和传输迟延 带宽 ●平均流量 ●通信开销 linwei@bbi.edu.cn
linwei@bbi.edu.cn 20 最短路径路由 ⚫ 使用广泛（简单且易于理解） ⚫ 最短路径测度 (Path Length) ⚫ 跳数 ⚫ 物理距离 ⚫ 平均的排队和传输迟延 ⚫ 带宽 ⚫ 平均流量 ⚫ 通信开销