Steiner树(steiner定理)

2.4 组播树

在单播模型中，数据包通过网络沿着单一路径从源主机向目标主机传递，但在组播模型中，组播源向某一组地址传递数据包，而这一地址却代表一个主机组。为了向所有接收者传递数据，一般采用组播分布树描述IP组播在网络里经过的路径。
组播分布树有四种基本类型：泛洪法、有源树、有核树和Steiner树。
2.4.1 洪泛法（Flooding）
这是最简单的向前传送组播路由算法，并不构造所谓的分布树。其基本原理如下：当组播路由器收到发往某个组播地址的数据包后，首先判断是否是首次收到该数据包，如果是首次收到，那么将其转发到所有接口上，以确保其最终能到达所有接收者；如果不是首次收到，则抛弃该数据包。
洪泛法的实现关键是“首次收到”的检测。这需要维护一个最近通过的数据包列表，但无需维护路由表。它适合于对组播需求比较高的场合，并且能做到即使传输出现错误，只要还存在一条到接收者的链路，则所有接收者都能接收到组播数据包。然而，洪泛法不适合用于Internet，因为它不考虑链路状态，并产生大量的拷贝数据包。此外，对于高速网络而言，“首次收到”列表将会很长，占用相当大的内存；尽管它能保证不对相同的数据包进行二次转发，但不能保证对相同数据包只接收一次。
2.4.2 有源树
有源树也称为基于信源的树或最短路径树（Shortest Path Tree：SPT）。它是以组播源为根构造的从根到所有接收者路径都最短的分布树。如果组中有多个组播源，则必须为每个组播源构造一棵组播树。由于不同组播源发出的数据包被分散到各自分离的组播树上，因此采用SPT有利于网络中数据流量的均衡。同时，因为从组播源到每个接收者的路径最短，所以端到端（end-to-end）的时延性能较好，有利于流量大、时延性能要求较高的实时媒体应用。SPT的缺点是：要为每个组播源构造各自的分布树，当数据流量不大时，构造SPT的开销相对较大。
2.4.3 共享树
共享树也称RP树（RPT），是指为每个组播组选定一个共用根（汇合点RP或核心），以RP为根建立的组播树。同一组播组的组播源将所要组播的数据单播到RP，再由RP向其它成员转发。目前，讨论最多同时也是最具代表性的两种共享树是Steiner树和有核树（CBT）。
Steiner树是总代价最小的分布树，它使连接特定图（graph）中的特定组成员所需的链路数最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生拥塞的风险。Steiner树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型网络缺少通用的解决方案。所以Steiner树只是一种理论模型，而非实用工具。目前，出现了许多Steiner树的次优启发式生成算法。
有核树是由根到所有组成员的最短路径合并而成的树。A. Ballardie在1997年9月的《基于核的组播路由体系结构》（Core Based Trees (CBT) Multicast Routing Architecture）(RFC2189和RFC2201)中介绍了有核树。关于它的进一步讨论见下文。
共享树在路由器所需存储的状态信息的数量和路由树的总代价两个方面具有较好的性能。当组的规模较大，而每个成员的数据发送率较低时，使用共享树比较适合。但当通信量大时，使用共享树将导致流量集中及根（RP）附近的瓶颈。