10.22组播路由选择算法 目标—建立一个组播树使组播包传送到目标站点。 1.泛洪法(f1 ooding) ■当路由器收到一个组播包时它首先会检查是否是第一次收 到此包,若是把该包转发给所有相连节点,否则简单地丢 弃该包。利用这种方式我们可保证所有互连的路由器会至 少接到包的一个拷贝。 ■该算法已经用在OSPF协议中。 简单,但效率不高
10.2.2 组播路由选择算法 目标—建立一个组播树使组播包传送到目标站点。 1. 泛洪法(flooding) ◼ 当路由器收到一个组播包时它首先会检查是否是第一次收 到此包，若是把该包转发给所有相连节点，否则简单地丢 弃该包。利用这种方式我们可保证所有互连的路由器会至 少接到包的一个拷贝。 ◼ 该算法已经用在OSPF协议中。 ◼ 简单，但效率不高
2.支撑树(Spanning tree算法 这个算法已被IEEE820MAC采用,它有效且容易实现。 该算法利用求图的最优支撑树算法,选择一个互连链路 的集合组成一个树结构使任何两个路由器之间只有一条 路径。因为树连接了网中所有节点,所以被称为支撑树。 ■当路由器收到一个组播包时,它将此包转发到除了该包 到达的链路之外属于支撑树的所有链路,以保证多播包 达到互连网的所有路由器。 支撑树算法的缺点是:它把所有流量集中在一个小的链 路集合,且没有考虑组成员特点
2.支撑树(spanning tree)算法 ◼ 这个算法已被IEEE-820 MAC采用，它有效且容易实现。 ◼ 该算法利用求图的最优支撑树算法，选择一个互连链路 的集合组成一个树结构使任何两个路由器之间只有一条 路径。因为树连接了网中所有节点，所以被称为支撑树。 ◼ 当路由器收到一个组播包时，它将此包转发到除了该包 到达的链路之外属于支撑树的所有链路，以保证多播包 达到互连网的所有路由器。 ◼ 支撑树算法的缺点是： 它把所有流量集中在一个小的链 路集合，且没有考虑组成员特点
A B A B (a)组播网络 (b)支撑树 图102组播支撑树
图10.2 组播支撑树
3:反向路径广播( reverse path broadcasting,RPB) 已经用在 Mbone中。该方法不是建立一个全网络的支撑树, 而是为每个源节点构造一个隐含的支撑树 基于该算法,一日路由器在链路L上收到来自源节点S的组播 包时,路由器将检査L是否属于针对S的最短路径。如是这种 情况该包被转发到所有除了L的链路上,否则包被丢弃 ■RPB算法改进:如果局部路由器不处于源节点和邻节点之间 的最短路径上,组播包将会在相邻的路由器丢弃 这个算法是有效的并易于实现。且由于组播包通过从源节点 到目标节点的最短路径转发,所以它是快速的。 路由器不需要了解整个支撑树,并且组播包是通过不同支撑 树传递,流量分布在多个树上,网络得到较好地利用。 ■RPB算法主要缺点:它构造分布树不考虑组播组员的信息
3.反向路径广播（reverse path broadcasting，RPB ） ◼ 已经用在Mbone中。该方法不是建立一个全网络的支撑树， 而是为每个源节点构造一个隐含的支撑树。 ◼ 基于该算法，一旦路由器在链路L上收到来自源节点S的组播 包时，路由器将检查L是否属于针对S的最短路径。如是这种 情况该包被转发到所有除了L的链路上，否则包被丢弃。 ◼ RPB算法改进： 如果局部路由器不处于源节点和邻节点之间 的最短路径上，组播包将会在相邻的路由器丢弃。 ◼ 这个算法是有效的并易于实现。且由于组播包通过从源节点 到目标节点的最短路径转发，所以它是快速的。 ◼ 路由器不需要了解整个支撑树，并且组播包是通过不同支撑 树传递，流量分布在多个树上，网络得到较好地利用。 ◼ RPB算法主要缺点： 它构造分布树不考虑组播组员的信息
A B D E al源节点为A的RPB树 b)源节点为C的RPB树 图10.3反向路径广播树
图10.3 反向路径广播树