文档章节

路由算法总结

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 2971
阅读 11
收藏 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
0
6
计算机网络学习笔记--网络层知识点整理

为什么要划分网络层?   不用的网络有不同的协议和标准,为了可以在不同网络之间互访,共享双方的资源,并且还要保持每个计算机网络本来的独立性,所以才划分出了网络层,并制定了专门的协议来负...

冬至饮雪
2016/04/16
0
0
从英雄联盟,看数据包何去何从?

写在前面 我们总是在说TCP/IP协议。HTTP头怎么怎么样;TCP头怎么怎么样;IP头怎么怎么样;MAC头怎么怎么样。不过话又说回来,计算机网络的问题,大多都是问这些。深入了解这部分内容,的确是...

MDove
08/27
0
0
[计算机网络] - 从英雄联盟,看数据包何去何从?

写在前面 我们总是在说TCP/IP协议。HTTP头怎么怎么样;TCP头怎么怎么样;IP头怎么怎么样;MAC头怎么怎么样。不过话又说回来,计算机网络的问题,大多都是问这些。深入了解这部分内容,的确是...

一支彩笔
08/27
0
0
(转)Elasticsearch的路由(Routing)特性

Elasticsearch路由机制介绍 Elasticsearch的路由机制与其分片机制有着直接的关系。Elasticsearch的路由机制即是通过哈希算法,将具有相同哈希值的文档放置到同一个主分片中。这个和通过哈希算...

木子SMZ
07/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

活动推荐|互联网3.0与区块链新时代论坛(北京)

1 时间地点 **时间:**9月22日 14:00 - 18:00 地点:(北京海淀)西大街70号 3w咖啡 二层 2 活动详情 Harmony创始人Stephen及团队将介绍他们的区块链分片扩容技术。Stephen曾任Apple地图服务...

HiBlock
43分钟前
1
0
如何优雅的删除Redis的大key

关于Redis大键(Key),我们从[空间复杂性]和访问它的[时间复杂度]两个方面来定义大键。前者主要表示Redis键的占用内存大小;后者表示Redis集合数据类型(set/hash/list/sorted set)键,所含有的...

IT--小哥
53分钟前
1
0
spring cloud学习笔记

工具 eclipse 4.9 gradle 4.10.2 spring cloud Finchley.SR1 spring boot 2.0.4 build.gradle buildscript {ext {springBootVersion = '2.0.4.RELEASE'}repositories {jcenter()......

bobby2006
54分钟前
1
0
Tcl命令操作实验-----(5)

Vivado% proc myproc {arg} {puts $arg}Vivado% myproc mynamemynameVivado% if {2>1} {puts 2>1} else {puts 2<1}2>1...

whoisliang
今天
1
0
比特币钱包RPC的PHP调用方法

当我们希望在Php开发的网站中加入比特币支付功能时,需要解决的第一个 问题,就是如何在Php程序代码中调用比特币钱包的RPC API开发接口来实现 我们期望的功能,例如比特币的支付与接收。 例如...

汇智网教程
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部