对于广播, 我相信在现实生活中我们时常都能接触到, 例如学校一言不合就响起了校歌, 搞的全校的人都能够听到, 想假装没听到都不行.
假如我们把学校比作一个局域网的话, 某台主机发起了一个广播, 意味着局域网内的其他所有主机都会收到这个广播, 那发起广播的主机是如何选择路径来给其他主机发送广播分组的呢? 考虑下面由几个节点组成的网络:
假如节点 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 这段链路也不会出现同一个广播分组重复经过的情况. 嗯, 这很 nice.
广播风暴
不过, 这种给所有邻居节点发送广播分组的方式够优雅吗?
看下面的一个网络组成:
按照刚才的方法, 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 加入生成树.
到此, 生成树构建完毕, 此时生成树如下:
然后在广播的时候, 就可以沿着这条路径来转发复制广播报文了.
文章讲到这里, 也大致结束. 如果文中有哪里讲错了, 欢迎你指出一下.
更多文章目录导航: https://github.com/iamshuaidi/writing
来源: https://www.cnblogs.com/kubidemanong/p/10133097.html