广播路由算法: 如何优雅地传递悄悄话？

作者 | 帅地

责编 | 仲培艺

对于广播，我相信在现实生活中我们时常都能接触到，例如学校一言不合就响起了校歌，搞的全校人都能够听到，想假装没听到都不行。

假如我们把学校比作一个局域网的话，某台主机发起了一个广播，意味着局域网内的其他所有主机都会收到这个广播，那发起广播的主机是如何选择路径来给其他主机发送广播分组的呢？考虑下面由几个节点组成的网络：

假如节点 R1 要做一个广播给 R2, R3, R4 发广播分组，显然，一种很简单的方法就是 R1 给 R2、R3、R4 三个节点分别发一次广播分组，这意味着 R1 一共要发送三次同样的广播分组。

途中不同箭头的颜色表示 R1 给不同的节点发广播分组。

大家想一个问题：这种发送方式合理吗？

是的，这种发送方式在实现上很简单，源节点（R1）每次带上目的节点的地址，然后发送给它就行了。

不过这种方式在效率上是极低的，例如，R1 发送的这三个广播分组都会经过同一段链路（R1-R2这段链路），而且 R2 要是再连接上 n 个节点的话，代表着这 R1 需要再发送 n 次广播分组，这 n 个报文也会经过同一段链路。

解决方法

为了解决这个问题，我们或许可以这样做：R1 把广播分组发给它的邻居节点 R2，然后 R1 就不管了，R2 再把报文发送给它的所有邻居节点 R3、R4 （除了从其接收该分组的那个邻居 R1）。

显然这种方式也是挺不错的，R1 只发送了一次广播分组，而且 R1-R2 这段链路也不会出现同一个广播分组重复经过的情况。

广播风暴

不过，这种给所有邻居节点发送广播分组的方式够优雅吗？

看下面的一个网络组成：

按照刚才的方法，R1 会给 R2 发送广播分组，接着 R2 会给 R3、R4 发送广播分组。刚才我们说过，收到广播分组的节点会给它的所有邻居发送报文（除了从其接受到该报文的那个邻居）。

所以这个时候 R3 会给 R4 发送广播分组文，而 R4 接收到 R3 的广播分组之后，R4 会给 R2 发送广播分组，R2 收到 R4 的广播分组之后 ，也会给 R3 再次发送广播分组…..

如果节点中形成了一个圈，那么就会像上面那样，节点之间不停发送广播分组，这时网络上充斥着大量重复的广播分组，将会严重影响资源的利用。

我们也把这种情况称之为广播风暴。

控制广播风暴

因此，我们必须想出某种策略来控制这种广播风暴。

一种很简单的方法，就是给这一份广播分组做一个标记。例如，源节点（发起广播的节点）可以将其地址以及广播序号放入这个广播分组中，然后发送给它的所有邻居节点，每个节点会维护它已经收到的、转发的源地址和广播分组的序号列表。

当节点收到一个广播分组时，会检查这个广播分组是否之前接收过（可以通过源地址、报文序号来检查），如果接收过，就把该广播分组丢弃；否则，把该广播分组接收，且向所有邻居节点转发。

例如对于下面由 7 个节点组成的网络：

如果节点 A 要做一个广播，那么 A 就会给其邻居节点 B、C 发一份广播分组，B、C 也会给其的邻居节点发送一个广播分组。意味着 B 会给 C、D 发送广播分组，而 C 也会给 B、E、F 发送一份广播分组：

当 B 收到 C 发给它的报文时，B 检测到已经有了该报文，所以 B 会丢弃 C 发送给它的广播分组，C 也一样会丢弃 B 发送给它的广播分组。图中青色的箭头代表该广播分组会被丢弃。
。

从图中不难看出，就算节点之间形成了圈，也不会出现节点之间循环转发的情况。

虽然该方法简单 ，但确实有效控制了广播风暴，当然，这只是控制广播风暴的方法之一，实际上还有其他方法，在此我就不说了。

生成树广播

虽然上面那种方法有效控制了广播风暴，但也存在着很多冗余广播分组（那些被丢弃的广播分组就是冗余的广播分组）。

如果可以，我想让每个节点仅接收一次广播分组，也不用考虑丢弃广播分组，所以理想的情况应该是这样：

有没有一种方法，可以让广播分组像上面这种情况来传送呢？请大家看下面一个图：

如果把节点当作一个图的顶点，大家观察下左边的图与右边的图有什么联系。

右边的图不就是左边图的生成树吗？(学了这么多年的生成树，终于用到了)，如果我们给每一段链路加上相应的费用，那么我们最理想的情况就是找到一颗最小生成树。

所以，我们最理想的情况就是让广播报文在最小生成树的路径中传送，于是 ，我们现在的问题就是找出这些节点组成的网络中的最小生成树。

那么，如何构造一颗生成树呢？下面提供一种基于中心某个中心的方法来建立一颗生成树。注意，是生成树，不是最小生成树。

该方法是这样的：我们先选出一个中心节点，然后其他节点向这个中心节点发送加入树报文，加入树报文经过的路径，都会被嫁接到生成树上。例如对于这个网络结构：

我们选择 E 为中心点，然后其他节点给 E 发送加入树报文：

1. F 节点给 E 发送加入树报文，此时 E-F 链路成为初始生成树，如下图（红色路径表示生成树）。

2. 接着 B 给 E 发送加入树报文，假设 B 经过的路径是 B->D->E。此时路径 B-D-E 也加入了生成树。

注：D 不用再发送加入树报文了，因此它此时已经在生成树里了。

3. 接着 C 给 E 发送加入树报文，C-E 加入生成树。

4. 接着，A 给 E 发送报文，假设 A 选择的路径是 A->C->E。不过当 A 的报文到达 C 之后，由于原本 C-E 就在生成树里面了，所以 A 的报文不用经过 C-E，A-C 就加入到生成树了。

5. 最后 G 通过 D 加入生成树。

到此，生成树构建完毕，此时生成树如下：

然后在广播的时候，就可以沿着这条路径来转发复制广播报文了。

作者：帅地，一个热爱编程的在校生，我的世界不只有coding，还有writing。目前维护订阅号「苦逼的码农」，专注于写算法与数据结构、Java、计算机网络。

声明：本文为作者个人投稿，版权归其所有。

---

 热 文 推 荐 

print_r('点个好看吧！');
var_dump('点个好看吧！');
NSLog(@"点个好看吧！");
System.out.println("点个好看吧！");
console.log("点个好看吧！");
print("点个好看吧！");
printf("点个好看吧！\n");
cout << "点个好看吧！" << endl;
Console.WriteLine("点个好看吧！");
fmt.Println("点个好看吧！");
Response.Write("点个好看吧！");
alert("点个好看吧！")
echo "点个好看吧！"

点击“阅读原文”，打开 CSDN App 阅读更贴心！

喜欢就点击“好看”吧！