路由选择 路由算法的基本特性 正确性 简当性 过于复杂、或对网络状态反应很快的算法反而会得不偿失 ·路由算法不能给各个节点带来的负担过重 健壮性:能适应拓扑结构和通信量等网络状态的动态变化 稳定性:防止网络状态的变化反应过于敏感或者过于迟缓 公平性 最优性 高效性:任何路由算法,每个节点都会一些处理开销,而且 同时会带来传输的开销 前页后页退出
前页 后页 退出 路由选择 • 路由算法的基本特性 –正确性 –简当性 • 过于复杂、或对网络状态反应很快的算法反而会得不偿失 • 路由算法不能给各个节点带来的负担过重 –健壮性：能适应拓扑结构和通信量等网络状态的动态变化 –稳定性：防止网络状态的变化反应过于敏感或者过于迟缓 –公平性 –最优性 –高效性：任何路由算法，每个节点都会一些处理开销，而且 同时会带来传输的开销
扩散法 一个网络节点从某条输入线路收到一个分组之后,把 该分组从除了分组到来的线路外的所有其他输出线路 上发出 可以用于健壮性要求很高的场合,但也会产生大量的 重复分组 每个分组头部包含一计数器,每个接收到该分组的节点将该 字段减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 nS 2. 从不在M中的相邻节点中找出一个具有和节点S的最少花费路由 的节点，并且把该节点规约进M中。可以表示如下： 寻找 ，使得C(w)= 把w加入到M中 wM ( ) min C j j M