Dijkstra算法(续) 3.更新最少花费路径 C(}mc()C(HL(wm对所有nM 如果后一项为最小值,则从S到n的路径变为从S到w的路径再加 上从w到n的链路 4.重复步骤2和3,直到M=N。 B2,A) B(2A) H(∞,-) 前页后页退出
前页 后页 退出 Dijkstra算法 （续） 3. 更新最少花费路径： C(n)=min[C(n),C(n)+L(w,n)] 对所有 如果后一项为最小值，则从S到n的路径变为从S到w的路径再加 上从w到n的链路。 4. 重复步骤2和3，直到M=N。 nM E(,-) F(,-) D((,1) A B C E F D G H A B(2,A) C(,-) D(,-) G(6,A) H(,-) 2 7 3 2 2 3 2 2 4 6 A B(2,A) C(9,B) E(4,B) F(6,E) G(5,E) A C(9,B) E(4,B) D(,-) F(,-) G(6,A) H H(,-) B(2,A) (a) (b) (c) (d)
动态路由算法 ·静态策略不利用当前网络信息,最多由网管人 员偶尔对网络状态变化作出反应。 动态策略是指节点的路由选择要依靠网络的当 前状态信息来决定,以设法适应网络流量、拓 扑的变化。 路由选择算法非常复杂,故可能增加网络节点的处 理负担。 大多数情况下,动态策略会使用别的节点来的状态 信息来进行路由选择,因此会增加网络中的负载。 个动态策略算法有时会因反应太快而引起振荡, 或者反应太慢而起不到作用 前页后页退出
前页 后页 退出 动态路由算法 • 静态策略不利用当前网络信息，最多由网管人 员偶尔对网络状态变化作出反应。 • 动态策略是指节点的路由选择要依靠网络的当 前状态信息来决定，以设法适应网络流量、拓 扑的变化。 – 路由选择算法非常复杂，故可能增加网络节点的处 理负担。 – 大多数情况下，动态策略会使用别的节点来的状态 信息来进行路由选择，因此会增加网络中的负载。 –一个动态策略算法有时会因反应太快而引起振荡， 或者反应太慢而起不到作用
动态路由算法(续) ·孤立路由选择 不利用其他节点来的网络信息,仅仅根据它自己所 看到的情况来确定路由,比如选择所有输出链路上 具有最短队列的那条链路 集中路由选择 根据所有节点的网络信息来选择路由 和固定路由选择一样,每个节点都保存了一张当前 的路由表 ·固定路由算法中表格的建立是手工完成的 ·集中路由选择中设置了一个路由控制中心RCC,定期收集 所有节点的信息,然后根据它对整个网络全局性的了解, 利用这些信息使用最短路径算法计算出每对节点之间的最 优路径,构造出路由表分发 前页后页退出
前页 后页 退出 动态路由算法 （续） • 孤立路由选择 –不利用其他节点来的网络信息，仅仅根据它自己所 看到的情况来确定路由，比如选择所有输出链路上 具有最短队列的那条链路 • 集中路由选择 –根据所有节点的网络信息来选择路由 –和固定路由选择一样，每个节点都保存了一张当前 的路由表 • 固定路由算法中表格的建立是手工完成的 • 集中路由选择中设置了一个路由控制中心RCC，定期收集 所有节点的信息，然后根据它对整个网络全局性的了解， 利用这些信息使用最短路径算法计算出每对节点之间的最 优路径，构造出路由表分发