单播，广播，多播 路由选择
- 单播路由选择
点对点通信 - 广播路由选择
从源节点向网络中所有其它节点交付分组 - 多播路由选择
从源节点向网络中一组特定的其它节点交付分组
广播路由选择
- 从源节点向网络中所有其它节点交付分组
N次单播
- 通过对网络中所有其它节点单播来实现广播
问题
-
低效
考虑路径ABC,ABD；链路AB上会有多个冗余的广播分组 -
要求预知接收方地址
在广播的应用场景下，接收方地址很可能无法预知 -
依赖单播
循环依赖。一些单播路由选择算法（如链路状态路由选择协议）依赖广播的功能。
无控制洪泛
- 源节点向所有邻居发送广播分组；
- 某节点结束到来自邻居A的广播分组后，向它的所有其它邻居（除A外）发送广播分组；
问题
-
无限循环
若图存在圈，则广播分组会在圈上无限循环 -
广播风暴
一个节点与多个节点连接时，将产生多个副本；
每个副本在存在多个邻居的节点处又会分裂出多个副本，最终导致网络中充斥大量冗余分组；
受控洪泛——序号控制洪泛
- 源节点将其地址（或其它标识符）及广播序号放入广播分组；并向所有邻居发送广播分组
- 每个节点维护它所处理过的广播分组的(源地址，广播序号)序对的列表，对新接收的广播分组，节点检查该分组在列表中是否有对应项，若有，则丢弃之；若无，则向其所有其它邻居转发该分组
Gnutella应用层协议使用了序号控制洪泛技术
受控洪泛——反向路径转发（Reverse Path Forwarding,RPF）
- 当某节点A收到具有源地址B的广播分组时，仅当该分组到达的链路恰好在A到B的单播最短路径上时，节点A才向它的所有其它邻居转发该分组；
- 节点A不需要了解A到B的完整单播最短路径，A只需知道A到B单播最短路径上的下一跳节点即可完成判断
生成树广播
- 首先构造网络的一颗生成树；
- 当任一一个源节点要发送广播时，它向所有生成树中的邻居发送分组；
- 接收广播分组的节点也向生成树中的其它邻居转发分组；
- 节点A无需了解整颗生成树，只需知道生成树中A的邻居即可；
优点
- 每个节点仅接受广播分组的一个副本，完全避免了冗余分组；
分布式生成树算法——基于中心点的方法
- 定义一个中心节点C
- 其它节点向中心节点单播表示加入树的报文
- 加入树报文使用单播路由选择向中心节点转发，直至该报文到达一个属于树的节点
- 加入树报文所经过的路径定义了发起该报文的节点到中心节点间的生成树分支
实际中的广播算法
广播算法被用于应用层和网络层
应用层协议Gnutella使用某种形式的序号控制洪泛
路由选择算法OSPF和IS-IS使用某种序号控制洪泛来广播链路状态通过
