广播路由算法:我是如何优雅着把悄悄话带给其他人的

2018 年 12 月 19 日 算法与数据结构

来自:苦逼的码农(微信号:di201805)

作者:帅地

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


本文字数:2280字

阅读本文大概需要:6 分钟

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

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

假如节点 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加入生成树。

到此,生成树构建完毕,此时生成树如下:

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

文章讲到这里,也大致结束。如果文中有哪里讲错了,欢迎你指出一下。

看完该文章有收获?不妨给博主点下方小卡片加个鸡腿激励一下?

 • end • 


●编号815,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐18个技术类公众微信

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

登录查看更多
0

相关内容

算法与数据结构 ( Algorithms and data structures )包括算法分析( Analysis of algorithms ),算法( Algorithms ),数据结构( Data structures )以及计算几何( Computational geometry ) Golden Formula: Algorithms + Data Structures = Programs
一份简明有趣的Python学习教程,42页pdf
专知会员服务
76+阅读 · 2020年6月22日
专知会员服务
145+阅读 · 2020年6月15日
Python数据分析:过去、现在和未来,52页ppt
专知会员服务
99+阅读 · 2020年3月9日
《代码整洁之道》:5大基本要点
专知会员服务
49+阅读 · 2020年3月3日
深度学习这些“坑”你们有没有踩过(入门误区)
计算机视觉战队
5+阅读 · 2019年4月27日
我是怎么走上推荐系统这条(不归)路的……
全球人工智能
11+阅读 · 2019年4月9日
研究了28本公司日历后,我们发现了一些有趣的事情
中国企业家杂志
14+阅读 · 2019年2月2日
IPSec | IKE密钥交换原理
计算机与网络安全
18+阅读 · 2018年12月23日
已删除
雪球
6+阅读 · 2018年8月19日
如何迅速提高公司估值?
计算广告
5+阅读 · 2018年5月16日
如何运用Python建一个聊天机器人?
七月在线实验室
17+阅读 · 2018年1月23日
关于孩子的未来,汪涵和李锐想告诉你这些......
三联生活周刊
6+阅读 · 2017年10月28日
代码这样写不止于优雅(Python版)
数说工作室
4+阅读 · 2017年7月17日
Arxiv
5+阅读 · 2020年3月26日
Continual Unsupervised Representation Learning
Arxiv
7+阅读 · 2019年10月31日
Conceptualize and Infer User Needs in E-commerce
Arxiv
3+阅读 · 2019年10月8日
Deep Reinforcement Learning: An Overview
Arxiv
17+阅读 · 2018年11月26日
Arxiv
6+阅读 · 2018年1月11日
VIP会员
相关资讯
深度学习这些“坑”你们有没有踩过(入门误区)
计算机视觉战队
5+阅读 · 2019年4月27日
我是怎么走上推荐系统这条(不归)路的……
全球人工智能
11+阅读 · 2019年4月9日
研究了28本公司日历后,我们发现了一些有趣的事情
中国企业家杂志
14+阅读 · 2019年2月2日
IPSec | IKE密钥交换原理
计算机与网络安全
18+阅读 · 2018年12月23日
已删除
雪球
6+阅读 · 2018年8月19日
如何迅速提高公司估值?
计算广告
5+阅读 · 2018年5月16日
如何运用Python建一个聊天机器人?
七月在线实验室
17+阅读 · 2018年1月23日
关于孩子的未来,汪涵和李锐想告诉你这些......
三联生活周刊
6+阅读 · 2017年10月28日
代码这样写不止于优雅(Python版)
数说工作室
4+阅读 · 2017年7月17日
Top
微信扫码咨询专知VIP会员