文档章节

路由算法总结

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 2971
阅读 10
收藏 0
点赞 0
评论 0

概述

通信子网络源节点和目的节点提供了多条传输路径的可能性。网络节点在收到一个分组后,要确定向下一节点传送的路径,这就是路由选择。

考虑的因素

在数据报方式中网络节点要为每个分组路由做出选择;而在虚电路方式中,只需在连接建立时确定路由。确定路由选择的策略称路由算法。

设计路由算法时要考虑诸多技术要素。

首先是路由算法所基于的性能指标,一种是选择最短路由,一种是选择最优路由;其次要考虑通信子网是采用虚电路还是数据报方式;其三,是采用分布式路由算法,即每节点均为到达的分组选择下一步的路由,还是采用集中式路由算法,即由中央点或始发节点来决定整个路由;其四,要考虑关于网络拓扑,流量和延迟等网络信息的来源;最后,确定是采用动态路由选择策略,还是选择静态路由选择策略。

静态路由和动态路由

静态路由

选择策略不用测量也无须利用网络信息,这种策略按某种固定规则进行路由选择。其中还可分为泛射路由选择、固定路由选择和随机路由选择三种算法。

(1)泛射路由选择法:

这是一种最简单的路由算法。一个网络节点从某条线路收到一个分组后,再向除该条线路外的所有线路重复发送收到的分组。结果,最先到达目的节点的一个或若干个分组肯定经过了最短的路线,而且所有可能的路径都被同时尝试过。这种方法可用于诸如军事网络等强壮性要求很高的场合,即使有的网络节点遭到破坏,只要源、目间有一条信道存在则泛射路由选择仍能保证数据的可靠传送。另外,这种方法也可用于将一条分组从数据源传送到所有其它节点的广播式数据交换中,它还可用来进行网络的最短传输延迟的测试。

(2)固定路由选择:

这是一种使用较多的简单算法。每个网络节点存储一张表格,表格中每一项记录对应着某个目的节点或链路。当一个分组到达某节点时,该节点只要根据分组的地址信息便可从固定的路由表中查出对应的目的节点及所应选择的下一节点。固定路由选择法的优点是简便易行,在负载稳定,拓扑结构变化不大的网络中运行效果很好。它的缺点是灵活性差,无法应付网络中发生的阻塞和故障。

(3)随机路由选择:

在这种方法中,收到分组的节点,在所有与之相邻的节点中为分组随机选择一个出路节点。方法虽然简单,也较可靠,但实际路由不是最佳路由,增加了不必要的负担,而且分组传输延迟也不可预测,故此法应用不广。

动态路由

节点路由选择要依靠网络当前的状态信息来决定的策略称动态路由选择策略,这种策略能较好地适应网络流量、拓扑结构的变化,有利于改善网络的性能。但由于算法复杂,会增加网络的负担,有时会因反应太快引起振荡或反应太慢不起作用。独立路由选择、集中路由选择和分布路由选择是三种动态路由选择策略的具体算法。

(1)独立路由选择:

在这类路由算法中,节点仅根据自己搜到的有关信息作出路由选择的决定,与其它节点不交换路由选择信息,虽然不能正确确定距离本节点较远的路由选择,但还是能较好地适应网络流量和拓扑结构的变化。一种简单的独立路由选择算法是Baran在1964年提出的热土豆(Hot Potato)算法。当一个分组到来时,节点必须尽快脱手,将其放入输出列最短的方向上排队,而不管该方向通向何方。

(2)集中路由选择:

集中路由选择也象固定路由选择一样,在每个节点上存储一张路由表。不同的是,固定路由选择算法中的节点路由表由手工制作,而在集中路由选择算法中的节点路由表由路由控制中心RCC(Routing Control Center)定时根据网络状态计算、生成并分送各相应节点。由于RCC利用了整个网络的信息,所以得到的路由选择是完美的,同时也减轻了各节点计算路由选择的负担。

(3)分布路由选择:

采用分布路由选择算法的网络,所有节点定期地与其每个相邻节点交换路由选择信息。每个节点均存储一张以网络中其它每个节点为索引的路由选择表,网络中每个节点占用表中一项,每一项又分为两个部分,即所希望使用的到目的节点的输出线路和估计到目的节点所需要的延迟或距离。度量标准可以是毫秒或链路段数、等待的分组数、剩余的线路和容量等。对于延迟,节点可以直接发送一个特殊的称作“回声”(echo)的分组,接收该分组的节点将其加上时间标记后尽快送回,这样便可测出延迟。有了以上信息,节点可由此确定路由选择。

路由算法

LS算法

采用LS算法时,每个路由器必须遵循以下步骤:

ls算法的步骤流程

1、确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后,它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息,其中包含它自身的IP地址。

2、测量相邻路由器的延时(或者其他重要的网络参数,比如平均流量)。为做到这一点,路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2,路由器便可以计算出延时。(路程往返时间是网络当前延迟的量度,通过一个分组数据包从远程主机返回的时间来测量。)该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。

3、向网络中的其他路由器广播自己的信息,同时也接收其他路由器的信息。
在这一步中,所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样,每一个路由器都能够知道网络的结构以及状态。

4、使用一个合适的算法,确定网络中两个节点之间的最佳路由。
在这一步中,路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点,如Dijkstra最短路径算法。在这个算法中,一个路由器通过收集到的其他路由器的信息,建立一个网络图。这个图描述网络中的路由器的位置以及它们之间的链接关系。每个链接都有一个数字标注,称为权值或成本。这个数字是延时和平均流量的函数,有时它仅仅表示节点间的跃点数。例如,如果一个节点与目的地之间有两条链路,路由器将选择权值最低的链路。

Dijkstra算法

具体算法见我的博客:

Dijkstra算法

Dijkstra算法执行下列步骤:

1、路由器建立一张网络图,并且确定源节点和目的节点,在这个例子里我们设为V1和V2。然后路由器建立一个矩阵,称为“邻接矩阵”。在这个矩阵中,各矩阵元素表示权值。例如,[i, j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连,它们的权值设为“无穷大”。
2、路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段:
前序字段——表示当前节点之前的节点。
长度字段——表示从源节点到当前节点的权值之和。
标号字段——表示节点的状态。每个节点都处于一个状态模式:“永久”或“暂时”。
3、路由器初始化(所有节点的)状态记录集参数,将它们的长度设为“无穷大”,标号设为“暂时”。
4、路由器设置一个T节点。例如,如果设V1是源T节点,路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后,它将不再改变。一个T节点仅仅是一个代理而已。
5、路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。
6、路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。
7、如果这个节点不是V2(目的节点),路由器则返回到步骤5。
8、如果节点是V2,路由器则向前回溯,将它的前序节点从状态记录集中提取出来,如此循环,直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

链路向量选路算法

链路状态算法(也称最短路径算法)发送路由信息到互联网上所有的结点,然而对于每个路由器,仅发送它的路由表中描述了其自身链路状态的那一部分。

距离向量算法

具体算法见我的博客:

Bellman-Ford算法

距离向量算法(也称为Bellman-Ford算法)则要求每个路由器发送其路由表全部或部分信息,但仅发送到邻近结点上。从本质上来说,链路状态算法将少量更新信息发送至网络各处,而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快,因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面,链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间,因此链路状态算法将会在实现时显得更昂贵一些。

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
《CCNA Exploration 路由协议和概念》读书笔记(一)

路由表的三大原理: 1. 每台路由器根据其自身路由表中的信息独立作出决策。 2. 一台路由器的路由表中包含某些信息并不表示其它路由器也包含相同的信息。 3. 有关两个网络之间路径的路由信息并...

方小达 ⋅ 2013/02/20 ⋅ 6

Elasticsearch的路由(Routing)特性

目录(?)[-] Elasticsearch路由机制介绍 指定个性化路由 利用路由机制的查询 路由机制的总结 Elasticsearch路由机制介绍 Elasticsearch的路由机制与其分片机制有着直接的关系。Elasticsearch...

allantaylor81 ⋅ 2015/08/11 ⋅ 0

memcache的hash一致性

MemCache是一个自由、源码开放、高性能、分布式的分布式内存对象缓存系统,用于动态Web应用以减轻数据库的负载。它通过在内存中缓存数据和对象来减少读取数据库的次数,从而提高了网站访问的...

吴之恒心 ⋅ 2017/02/24 ⋅ 0

从jredis中学习一致性hash算法

jredis是redis的java客户端,通过sharde实现负载路由,一直很好奇jredis的sharde如何实现,翻开jredis源码研究了一番,所谓sharde其实就是一致性hash算法。其实,通过其源码可以看出一致性h...

温佐镜 ⋅ 2014/01/11 ⋅ 3

sbc(六) Zuul GateWay 网关应用

image 前言 看过之前SBC系列的小伙伴应该都可以搭建一个高可用、分布式的微服务了。 目前的结构图应该如下所示: image 各个微服务之间都不存在单点,并且都注册于 ,基于此进行服务的注册于发...

crossoverJie ⋅ 2017/11/28 ⋅ 0

sbc(六) Zuul GateWay 网关应用

前言 看过之前SBC系列的小伙伴应该都可以搭建一个高可用、分布式的微服务了。 目前的结构图应该如下所示: 各个微服务之间都不存在单点,并且都注册于 ,基于此进行服务的注册于发现,再通过 ...

crossoverJie ⋅ 2017/11/28 ⋅ 0

读写分离插件--spring-boot-mybatis-rw

spring-boot-mybatis-rw 基于mybatis,springboot开箱即用的读写分离插件 Quick Start 介绍 此插件由以下2部分组成 datasource:读写数据源的代理,支持一写多读,用户只需实现 org.spring.b...

匿名 ⋅ 2017/08/22 ⋅ 1

网络层路由选择协议(RIP&OSF)

路由选择协议的核心是路由选择算法,也即路由选择与更新算法。 因特网路由选择协议可以分为两大类: 内部网关协议(IGP):把一个自治系统内部路由交换信息所用的任何信息统称为内部网关协议...

Superheros ⋅ 03/23 ⋅ 0

Asp.Net Web API 2第六课——Web API路由和动作选择

Asp.Net Web API 导航 Asp.Net Web API第一课——入门http://www.cnblogs.com/aehyok/p/3432158.html Asp.Net Web API第二课——CRUD操作http://www.cnblogs.com/aehyok/p/3434578.html Asp.......

aehyok ⋅ 2013/11/27 ⋅ 0

Tair学习小记

Tair架构 ![Tair架构][1] 本文只关注Client,ConfigerServer,DataServer三者之间的交互,不关注DataServer的存储引擎 Client,ConfigServer,DataServer三者之间的交互 情况1:Client在访问datas...

felixlv ⋅ 2014/03/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mahout基于内存的DataMode 推荐引擎Demo2

Mahout基于内存的DataMode 推荐引擎Demo2 //注释的部分是基于文件也可以理解为基于日志文件的, //DataModel 可以有很多种,实现abstractDataMode的子类,原则上都可以作为数据源,个人觉得,...

xiaomin0322 ⋅ 8分钟前 ⋅ 0

Docker部署Tomcat及Web应用

一、在线下载docker yum install -y epel-releaseyum install docker-io # 安装dockerchkconfig docker on # 加入开机启动service docker start # 启动docker服务 1 ...

Jeam_ ⋅ 8分钟前 ⋅ 0

研发运营一体化能力成熟度模型

研发运营一体化是指在 IT 软件及相关服务的研发及交付过程中,将应用的需求、开发、测试、部 署和运营统一起来,基于整个组织的协作和应用架构的优化,实现敏捷开发、持续交付和应用运营的无...

stars永恒 ⋅ 14分钟前 ⋅ 0

jQuery缩小放大触发事件

jquery的resize()方法使用 <html> <head> <script type="text/javascript" src="/jquery/jquery.js"></script> <script type="text/javascript"> var i = 0; $(document).ready(function(){ ......

RobertZou ⋅ 14分钟前 ⋅ 0

eclipse python 搭建

https://jingyan.baidu.com/article/9113f81b68ebce2b3214c7e0.html https://www.cnblogs.com/ZhangRuoXu/p/6397756.html https://blog.csdn.net/zhangphil/article/details/78962159 字符集......

之渊 ⋅ 15分钟前 ⋅ 0

weex,react native,flutter

weex: 一次编写,处处运行 RN: 学一次,到处写(针对安卓,IOS平台特性 各自写,会有很大一部分是一样的代码) 这些方案是否真正的解决了跨平台问题呢?从目前的状况来看,很显然是没有的,因...

东东笔记 ⋅ 21分钟前 ⋅ 0

Spring Cloud微服务分布式云架构-集成项目

Spring Cloud集成项目有很多,下面我们列举一下和Spring Cloud相关的优秀项目,我们的企业架构中用到了很多的优秀项目,说白了,也是站在巨人的肩膀上去整合的。在学习Spring Cloud之前大家必...

明理萝 ⋅ 26分钟前 ⋅ 1

SpringMVC图片上传问题解决

当我们上传图片时一直发现: MultipartFile file = null; if (request instanceof MultipartHttpServletRequest) 匹配不上, 解决方案: 在前端xml加入如下配置代码即可 <!-- 图片上传bean --...

泉天下 ⋅ 28分钟前 ⋅ 0

Spring表达式语言(SpEL)

1、SpEL引用 Spring EL在bean创建时执行其中的表达式。此外,所有的Spring表达式都可以通过XML或注解的方式实现。下面将使用Spring表达式语言(SpEL),注入字符串,整数,Bean到属性。 SpEL的...

霍淇滨 ⋅ 44分钟前 ⋅ 0

Gradle使用阿里云镜像

gradle 生命周期中有一个初始化( Initialization )的过程,这个过程运行在 build script 之前,我们可以在这个地方做一点系统全局的设置,如配置仓库地址。 你可以在以下几个位置实现仓库地址...

明MikeWoo ⋅ 52分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部