高等学校21世纪教材：《计算机网络》第5章 (5-1) 广域网1

路由选择 路由算法的基本特性 正确性 简当性 过于复杂、或对网络状态反应很快的算法反而会得不偿失 ·路由算法不能给各个节点带来的负担过重 健壮性:能适应拓扑结构和通信量等网络状态的动态变化 稳定性:防止网络状态的变化反应过于敏感或者过于迟缓 公平性 最优性 高效性:任何路由算法,每个节点都会一些处理开销,而且 同时会带来传输的开销 前页后页退出

前页 后页 退出 路由选择 • 路由算法的基本特性 –正确性 –简当性 • 过于复杂、或对网络状态反应很快的算法反而会得不偿失 • 路由算法不能给各个节点带来的负担过重 –健壮性：能适应拓扑结构和通信量等网络状态的动态变化 –稳定性：防止网络状态的变化反应过于敏感或者过于迟缓 –公平性 –最优性 –高效性：任何路由算法，每个节点都会一些处理开销，而且 同时会带来传输的开销

扩散法 一个网络节点从某条输入线路收到一个分组之后,把 该分组从除了分组到来的线路外的所有其他输出线路 上发出 可以用于健壮性要求很高的场合,但也会产生大量的 重复分组 每个分组头部包含一计数器,每个接收到该分组的节点将该 字段减1,如果计数器值为0,扔掉该分组。 另一种方法是记录下分组扩散的路径,防止它第二次再扩散 到已扩散过的路径中。 最后一种方法为选择扩散法。节点并不是简单地向所有其他 节点转发分组,而是选择那些很可能向目的节点的方向去的 节点。这里考虑的方向可以是地理上的方向,也可以是网络 拓扑中的大致方向 前页后页退出

前页 后页 退出 扩散法 • 一个网络节点从某条输入线路收到一个分组之后，把 该分组从除了分组到来的线路外的所有其他输出线路 上发出 • 可以用于健壮性要求很高的场合，但也会产生大量的 重复分组 –每个分组头部包含一计数器，每个接收到该分组的节点将该 字段减1，如果计数器值为0，扔掉该分组。 –另一种方法是记录下分组扩散的路径，防止它第二次再扩散 到已扩散过的路径中。 –最后一种方法为选择扩散法。节点并不是简单地向所有其他 节点转发分组，而是选择那些很可能向目的节点的方向去的 节点。这里考虑的方向可以是地理上的方向，也可以是网络 拓扑中的大致方向

固定路由选择 每个网络节点 存储有一张表格,每一项记录着为了到达某个目的节点而选 择的下一节点或链路。 当一个分组到达该节点时,节点只要根据分组中的地址信息 从表中找出对应的目的节点及所应选择的下一节点,将分组 转发给该下一节点 简单,适合于在一个负载稳定、拓扑变化不大的网络 中运行 个改进办法就是在最优路由的下一节点之外提供几 替换节点,并且可以使这些替换节点的使用符合 定的概率 前页后页退出

前页 后页 退出 固定路由选择 • 每个网络节点 – 存储有一张表格，每一项记录着为了到达某个目的节点而选 择的下一节点或链路。 – 当一个分组到达该节点时，节点只要根据分组中的地址信息 从表中找出对应的目的节点及所应选择的下一节点，将分组 转发给该下一节点 • 简单，适合于在一个负载稳定、拓扑变化不大的网络 中运行 • 一个改进办法就是在最优路由的下一节点之外提供几 个替换节点，并且可以使这些替换节点的使用符合一 定的概率

随机路由选择 当分组到达节点后,随意选择一条输出 线路进行转发 或者采用概率数的方法,使得每个输出 线路的选择是符合预定的概率的 由于随机性,分组可能会一直在网络中 传递,从而无法到达目的地,很少使用 前页后页退出

前页 后页 退出 随机路由选择 • 当分组到达节点后，随意选择一条输出 线路进行转发 • 或者采用概率数的方法，使得每个输出 线路的选择是符合预定的概率的 • 由于随机性，分组可能会一直在网络中 传递，从而无法到达目的地，很少使用

Dijkstra算法 定义:N=网络中所有节点的集合 S=源节点 M=已由算法归并的节点的集合 L(ij)=节点与j之间链路的权值;若两个节点间没有直接连 接则为∞。 C(n)=算法求得的当前从S到n的最少花费路由的花费 1.初始化 M={S} C(n)=L(S,n)forn≠S 2.从不在M中的相节点中找出一个具有和节点S的最少花费路由 的节点,并且把该节点规约进M中。可以表示如下: 寻找w"EM,使得C(w)m,cO 把w加入到M中 jEM 前页后页退出

前页 后页 退出 Dijkstra算法 定义：N＝网络中所有节点的集合 S＝源节点 M＝已由算法归并的节点的集合 L（i,j）＝节点i与j之间链路的权值；若两个节点间没有直接连 接则为∞。 C（n）＝算法求得的当前从S到n的最少花费路由的花费 1. 初始化： M = {S} C(n) = L(S,n) for nS 2. 从不在M中的相邻节点中找出一个具有和节点S的最少花费路由 的节点，并且把该节点规约进M中。可以表示如下： 寻找 ，使得C(w)= 把w加入到M中 wM ( ) min C j j  M

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。 nM 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，定期收集 所有节点的信息，然后根据它对整个网络全局性的了解， 利用这些信息使用最短路径算法计算出每对节点之间的最 优路径，构造出路由表分发

动态路由算法(续) ·分布路由选择 根据来自于相邻节点的信息,通过一个最短花费路 由算法计算出到每个目的地的路由 两种常用的分布路由算法: 距离向量路由 每个节点开始只知道它直接连接的链路的花费,然后通过 轮一轮地与邻居路由器交换路由信息,并进行相应的计算后, 节点逐渐了解到某个目的地或者某些目的地的最小花费路径。 链路状态路由 节点通过相互之间交换路由信息,了解到整个网络的拓扑信 息,包括网络中的链路以及链路的花费。然后每个节点基于 它所了解到的网络的全局状况计算所有可能的最小花费路径 前页后页退出

前页 后页 退出 动态路由算法（续） • 分布路由选择 –根据来自于相邻节点的信息，通过一个最短花费路 由算法计算出到每个目的地的路由 –两种常用的分布路由算法： • 距离向量路由 –每个节点开始只知道它直接连接的链路的花费，然后通过一 轮一轮地与邻居路由器交换路由信息，并进行相应的计算后， 节点逐渐了解到某个目的地或者某些目的地的最小花费路径。 • 链路状态路由 –节点通过相互之间交换路由信息，了解到整个网络的拓扑信 息，包括网络中的链路以及链路的花费。然后每个节点基于 它所了解到的网络的全局状况计算所有可能的最小花费路径

拥塞 什么是拥塞? 通信子网中某一部分的分组数高于一定的水 平,使得该部分网络来不及处理这些分组, 从而使这部分以至整个网络的性能下降 仅仅通过资源升级无法完全消除拥塞,拥塞 控制是一个动态的概念 路由器的缓冲区 通信线路的带宽 处理器速度 前页后页退出

前页 后页 退出 拥塞 • 什么是拥塞? –通信子网中某一部分的分组数高于一定的水 平，使得该部分网络来不及处理这些分组， 从而使这部分以至整个网络的性能下降 –仅仅通过资源升级无法完全消除拥塞，拥塞 控制是一个动态的概念 • 路由器的缓冲区 • 通信线路的带宽 • 处理器速度