广播路由算法:如何优雅地传递悄悄话?
- CSDN
- 2019-01-01 14:02
对于广播,我相信在现实生活中我们时常都能接触到,例如学校一言不合就响起了校歌,搞的全校人都能够听到,想假装没听到都不行。
假如我们把学校比作一个局域网的话,某台主机发起了一个广播,意味着局域网内的其他所有主机都会收到这个广播,那发起广播的主机是如何选择路径来给其他主机发送广播分组的呢?考虑下面由几个节点组成的网络:
假如节点 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 加入生成树。
到此,生成树构建完毕,此时生成树如下:
然后在广播的时候,就可以沿着这条路径来转发复制广播报文了。
相关文章
资讯
- 5天前
东南亚传统保险领投TakaChain Insurance,开启创世挖矿
- 1周前
眼控科技赋能车辆通行证办理便民、智能、高效
- 1个月前
EIZO推出基于NVIDIA Turing的图形和GPGPU卡
- 1个月前
Inertial Labs发布了IMU/数字倾斜传感器
- 1个月前
LWIR摄像机的USB集成板发布
- 2020-12-28
国产大飞机研制取得重大进展 民营航空企业迎来发展新机遇
- 2020-12-07
双十二好物推荐,一款超能打的智能教育笔记本
- 2020-11-26
用技术驱动企业采购模式升级,京东企业购助力中小企业数字化转型
- 2020-11-03
守卫平安保障,提防保险“代理全额退保”诸多风险危害
- 2020-10-30
工厂里的“新面孔”,进博“大家伙”这样助力中国制造提质升级
- 2020-10-28
2021第五届中国上海国际车轮及轮胎展览会暨嘉年华活动
- 2020-10-28
2021中国上海国际汽车底盘及制动系统展览会
- 2020-10-19
京东企业业务发布技术服务品牌“电解智” 用“+服务”的综合性解决方案保障技术产品落地
- 2020-10-13
财富健康双保障 平安人寿“金瑞人生21”重磅上市
- 2020-09-29
《小马宝莉之彩虹音爆》全球首站,在成都正式开演!
原创
荐读
-
智能手机竞争中失败,日本在联网汽车领域举步维艰
据外媒报道,在制造带有数字联网服务的汽车的竞争中,丰田汽车和日产汽车面临着被本土市场拖累的风险。与美国和欧洲的汽车消费者不同的是,日本消费者不愿意为这些联网功能和服务买单。结果就是:日本只有10%的汽车...
-
2020年河南省将推广应用3万台工业机器人
到2020年,推广应用3万台工业机器人,建设1000条智能生产线、300个智能车间、150个智能工厂……4月16日,在2018两岸智能装备制造郑州论坛上,河南省工信委发布了《2017年河南省智能制造白皮书》,河南智能制造的2020...
-
全国首个获批建设国家技术标准(贵州大数据)创新基地
近日,国家标准委复函批准 , 同意贵州省建设国家技术标准 ( 贵州大数据 ) 创新基地,标志着贵州成为全国首个获批建设大数据国家技术标准创新基地的省份。按照国家标准委批复要求,国家技术标准 ( 贵州大数据 ) 创新...