网络中的「动态路由算法」,你了解吗?

在计算机网络中,路由器的一个很重要责任就是要在端对端的节点中找出一条最佳路径出来,通过自己与相邻节点之间的信息,来计算出从自己位置到目的节点之间的最佳线路,这种算法我们可以理解为路由算法。

路由的模式又主要分为「静态路由」和「动态路由」。静态路由协议是由网络管理员手动输入配置的,适用于小型的不太复杂的网络环境中,或者有特定需求的网络场景中。而动态路由协议是现代计算机网络中最为常用的一种方式。动态路由算法能够根据网络拓扑结构去适应流量的变化。

本文主要聊的就是「动态路由算法」,你知道动态路由算法有哪些吗?

动态路由算法大致可以分为两类:

  • 距离矢量路由算法
  • 链路状态路由算法

下面我们来看一下这两类算法的特点:

一、距离矢量路由算法

距离矢量路由算法(Distance Vector Routing),它是网络上最早使用的动态路由算法,也称为Bellman-Ford或者Ford-Fulkerson算法。基于这类算法实现的协议有:RIP、BGP等。

如图, 这类算法的基本思路是:网络中每一个路由器都要维护一张 矢量表 ,这个 矢量表 中的每一行都记录了从当前位置能到达的目标路由器的最佳出口(接口)和距离(跳数)。

每隔一段时间当前路由器会向所有的邻居节点发送自己的这个表,同时它也会接收每个邻居发来的它们的表。并会将邻居的表和自己的表做一个对比更新。 比如当前 路由器X 离 邻居Y路由器 的距离是m,此时收到 邻居Y 发来的表中写到了“ 邻居Y离路由器Z的距离是n ”,那 当前路由器X 就知道它离 路由器Z 的距离可能就是 m+n 了,如图:

就这样继续类推,要不了多久,每个路由器就可以将网络中所有路由节点和子网线路都汇聚起来了。这样的话,每个路由器只需要查找自己的表就可以很容易的知道到达目的地的最佳出口(接口)是哪个了。

当然,当网络结构发生变化的时候,各个路由器中的矢量表也会随之动态更新。

好了,讲到这里,基本上对「距离矢量路由算法」大概原理有个认识了,现在我们再来仔细分析分析这个算法的名字,可以发现,它的名字取的还是蛮有意思的,非常贴切。“距离”这个词就基本表明了这个算法是通过 距离(跳数/时间)来度量2个路由网络之间的线路的,而“矢量”这个词,可以看出线路是有方向性的,且路由表中只记录了数据包去往目的地应该走哪个出口方向,并不会记录到达目的地的整条路径。

「距离矢量路由算法」的优点很明显:非常简单清晰,且任何加入到网络中的新节点都能很快的与其它节点建立起联系获得补充信息。

缺点呢,首先就是每次发送信息的时候,要发送整个全局路由表,太大了,因为每个路由器需要在矢量表中记录下整个网络的信息,导致需要较大存储、CPU、网络开销,对资源的要求越来越高。还有一个问题就是收敛时间太慢,也就是路由器共享路由信息并使各台路由器掌握的网络情况达到一致所需的时间比较久,收敛速度慢会导致有些路由器的表更新慢,从而造成路由环路的问题。

二、链路状态路由算法

链路状态路由算法(Link State Routing ),基于Dijkstra算法,它是以图论作为理论基础,用图来表示网络拓扑结构,用图论中的最短路径算法来计算网络间的最佳路由。基于这类算法实现的协议有:OSPF 等。 如图,

这类算法的基本思路是:采用的是不停的拼接地图的方式。每一个路由器首先都会发现自己身边的邻居节点,然后将自己与邻居节点之间的链路状态包广播出去,发送到整个网络。这样,当某个路由器收到从网络中其它路由器广播来的路由信息包(链路状态包)之后,会将这个包中的信息与自己路由器上的信息进行拼装,最终形成一个全网的拓扑视图。

当路由器中形成了全网的拓扑视图后,它就可以通过最短路径算法来计算当前节点到其它路由器之间的最短路径了。当某台路由器的链路状态发生变化时,路由器采用洪泛法向所有路由器发送此信息,其它路由器使用收到的信息重新计算最佳路径,重新生成路由表(拓扑图)。

这里可以做一个类比,有一个路人甲人去问路,然后本地人A只知道A自己生活方圆5公里的地图,本地人B只知道B自己生活的方圆5公里的地图,但是路人甲要去的地方需要穿过A和B所在区域,那么就把A和B的2份地图拿来拼装在一起,然后去往目的地的完整路线就可以查出来了。

链路状态路由算法简单而言就是五个步骤:

  1. 发现邻居节点,并了解邻居网络地址
  2. 测量到邻居节点的距离或成本度量值
  3. 构建一个包含自己所拥有信息的链路状态包
  4. 将这个包广播到网络中,并接收其它路由器的链路状态包
  5. 计算出当前节点到其它节点之间的最短路径(基于Dijkstra算法)

链路状态路由算法 不会像 距离矢量路由算法 那样发送整个路由表,链路状态路由协议只会广播更新的或者改变了的网络拓扑,这样传播的信息量会少很多,同时对带宽和CPU资源也是一种节省。

「链路状态路由算法」具有很好的扩展能力,也具有更快的收敛速度,能够快速的适应网络变化,且由于一个路由器的链路状态只涉及与其相邻的路由器的联通状态,因而与整个互联网的规模并无直接关系,因此链路状态路由算法可以用于大型的或者路由信息变化剧烈的互联网环境。

将上述两种算法做一个简单的对比:

图片来源网络,经供参考。

以上,就是对计算机网络中的动态路由算法的基本讲解了,欢迎大家一起交流。

本文原创发布于微信公众号「 不止思考 」,欢迎关注,交流Java、Web、架构、大数据、职业发展、技术管理。

原文发布于微信公众号 - 不止思考(bzsikao)

原文发表时间:2018-09-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

开源 | 基于Python的人脸识别:识别准确率高达99.38%!

该库使用 dlib 顶尖的深度学习人脸识别技术构建,在户外脸部检测数据库基准(Labeled Faces in the Wild benchmark)上的准确率...

6437
来自专栏媒矿工厂

Ittiam优化VP9,turnaround时间大幅减少

libvpx是Google开发的视频编解码器VP8和VP9的开源软件实现库。libvpx中包含了VP9视频编码算法,相比H.264/AVC,在高...

3155
来自专栏FreeBuf

使用Python和Tesseract来识别图形验证码

各位在企业中做Web漏洞扫描或者渗透测试的朋友,可能会经常遇到需要对图形验证码进行程序识别的需求。很多时候验证码明明很简单(对于非互联网企业,或者企业内网中的应...

6945
来自专栏算法+

pytorch 移动端框架 thnets 附c示例代码

前年年前做一个手机移动端图像识别项目的时候, 先后尝试了mxnet,thnets,caffe,tensorflow. 当时的情况是,mxnet内存管理奇差,内存...

4867
来自专栏腾讯大数据的专栏

TDW千台Spark千亿节点对相似度计算

相似度计算在信息检索、数据挖掘等领域有着广泛的应用,是目前推荐引擎中的重要组成部分。随着互联网用户数目和内容的爆炸性增长,对大规模数据进行相似度计算的需求变得...

39810
来自专栏人工智能LeadAI

TensorFlow从0到1丨开篇:Hello TensorFlow !

我以官方文档为主线,开始对TensorFlow的学习。这期间会把我的理解进行持续的输出,作为《TensorFlow从0到1》系列。它不会止于翻译和笔记、语言和工...

4337
来自专栏ATYUN订阅号

用香蕉也能玩电脑游戏—Tensorflow对象检测接口的简单应用

Tensorflow最近发布了用于对象检测的对象检测接口(Object Detection API),能够定位和识别图像中的对象。它能够快速检测图像允许从视频帧...

3574
来自专栏人人都是极客

第三课:把tensorflow,模型和测试数据导入Android工程

关于Android项目的创建这里就不做赘述了,我们直接进入主题,看下如何把机器学习库和训练的模型导入一个安卓应用中。 导入 Inference Interfac...

38612
来自专栏CreateAMind

ROS探索总结(十一)——机器视觉

机器视觉在计算机时代已经越来越流行,摄像头价格越来越低廉,部分集成深度传感器的混合型传感器也逐渐在研究领域普及,例如微软推出的Kinect,而且...

1862
来自专栏大数据智能实战

微软开源认知服务CNTK的测试(语音训练)

前段时间,微软开源了认知服务的工具箱,直到近期才有时间进行测试。 看了文档,这个CNTK工具包还是非常厉害的,可以支持语音识别,图像分类,机器翻译等多种任务。里...

2885

扫码关注云+社区

领取腾讯云代金券