●●● ●●●● ●●●●● ●●●● 泛洪 ●●●●● ●●●● ●●●● Flooding是一种静态算法。每一个进来的分 组将被发送到除了它进来的那条路线之外的每 条输出线路上,显然他会产生大量的重复分 组 ●抑制泛洪过程采用如下的方法:设置一个跳计 数器,每经一跳减一,当计数器到达0时分组 被丢弃(TTL) linwei@bbi.edu.cn
linwei@bbi.edu.cn 26 泛洪 ⚫ Flooding 是一种静态算法。每一个进来的分 组将被发送到除了它进来的那条路线之外的每 一条输出线路上，显然他会产生大量的重复分 组。 ⚫ 抑制泛洪过程采用如下的方法：设置一个跳计 数器，每经一跳减一，当计数器到达0时分组 被丢弃（TTL）
●●● ●●●● ●●●●● ●●●● 泛洪 ●●●●● ●●●● ●进一步抑制泛洪的方法 每个分组头上加一个序列号。 每个源路由器维持一张表,其中列出那些已经见过 的,来自于该源路由器的序列号。如果一个进来的 分组已经位于列表中,则丢弃。 为了避免列表无限膨胀,每个列表使用一个计数器k 作为参数,它表示一直到k的所有序列号都已经看过 了。当一个分组进来的时候,如果是重复分组则丢 弃,并且K以下的整个列表都不需要了。 linwei@bbi.edu.cn
linwei@bbi.edu.cn 27 泛洪 ⚫ 进一步抑制泛洪的方法： • 每个分组头上加一个序列号。 • 每个源路由器维持一张表，其中列出那些已经见过 的，来自于该源路由器的序列号。如果一个进来的 分组已经位于列表中，则丢弃。 • 为了避免列表无限膨胀，每个列表使用一个计数器k 作为参数，它表示一直到k的所有序列号都已经看过 了。当一个分组进来的时候，如果是重复分组则丢 弃，并且K以下的整个列表都不需要了
●●● ●●●● ●●●●● ●●●● 泛洪 ●●●●● ●●●● ●泛洪有很多重要的用途: 在军事领域中,泛洪有很强的健壮性。 用于分布式数据库中。 用作度量标准,用来比较其他的路由算法 用在无线网络中 linwei@bbi.edu.cn
linwei@bbi.edu.cn 28 泛洪 ⚫ 泛洪有很多重要的用途： • 在军事领域中，泛洪有很强的健壮性。 • 用于分布式数据库中。 • 用作度量标准，用来比较其他的路由算法 • 用在无线网络中
●●● ●●●● ●●●●● ●●●● 距离矢量路由 ●●●●● ●●●● ●距离矢量路由 ●每个路由器维护一张表(即一个矢量),表中列出 了当前已知的到每个目标的最佳距离(度量有可能 很多种,例如跳数、迟延、排队分组数等),以及 所使用的线路。 ●通过在邻居间相互交换信息,路由器不断更新内部 列表。 o Example: RIP, IGRP EIGRP o Bellman-Ford/ford-Fulkerson linwei@bbi.edu.cn
linwei@bbi.edu.cn 29 距离矢量路由 ⚫ 距离矢量路由 ⚫ 每个路由器维护一张表（即一个矢量），表中列出 了当前已知的到每个目标的最佳距离（度量有可能 很多种，例如跳数、迟延、排队分组数等），以及 所使用的线路。 ⚫ 通过在邻居间相互交换信息，路由器不断更新内部 列表。 ⚫ Example: RIP, IGRP, EIGRP ⚫ Bellman-Ford/Ford-Fulkerson
●●● ●●●● ●●●●● ●●●● ●●●●● Distance Vector Routing ●●●● New estimated Router delay from J D H Line A[0[242021[8A B2363128 C[25181[193628 D40[27824[20H 后E[14[7〖3022 F3209 bG831_6118H 9H[17][20[0 21_01 10 K[24D22220 ric is delay L2933[99 ·J→A:8ms delay delay delay delay J→I:10ms 10126 J→H:12ms rJ Vectors received from ·J→K:6ms Js four neighbors (b) cost Outgoing link to use (a)一个子网.(b)从A,l,H,K的输入,以及J的新路由表
linwei@bbi.edu.cn 30 Distance Vector Routing (a) 一个子网. (b) 从A，I，H，K的输入，以及J的新路由表。 • Metric is delay • J→A: 8 ms • J→I: 10ms • J→H: 12ms • J→K: 6ms Outgoing link to use cost