精华内容
下载资源
问答
  • 一、路由算法、 二、路由算法 分类、 三、静态路由算法、 四、动态路由算法、 五、动态路由算法 分类、 六、分层次的路由选择协议、





    一、路由算法



    路由算法 : 选择数传输的 “最佳路由” , 该 “最佳” 是相对于某特定要求得出的合理选择 ;


    路由表 : 又称为 转发表 , 有如下条目 :

    • 目的网络 IP 地址
    • 子网掩码
    • 下一跳 IP 地址
    • 接口




    二、路由算法 分类



    路由算法 分类 :

    • 静态路由算法

    • 动态路由算法





    三、静态路由算法



    静态路由算法 :

    ① 特点 :非自适应 路由算法 ;

    ② 路由配置 : 管理员 手工配置 路由信息 ;

    ③ 优点 : 简单 , 可靠 ; 负载稳定 , 拓扑变化小 的网络中 运行 ;

    ④ 缺点 : 路由更新慢 , 不适合 大型网络 ;

    ⑤ 适用场景 : 用于 安全性较高的军事网络小型商业网络 ;





    四、动态路由算法



    动态路由算法 :

    ① 特点 :自适应 路由算法 ;

    ② 路由配置 : 路由器之间 彼此交换 路由信息 ; 按照路由算法优化出路由表项 ;

    ③ 优点 : 路由信息更新快 ; 适用于大型网络 , 及时响应链路费用 和 网络拓扑变化 ;

    ④ 缺点 : 算法复杂 , 网络负担较高 ;

    ⑤ 适用场景 : 用于 大型商业网络 ;





    五、动态路由算法 分类



    动态路由算法 分类 :

    ① 全局性 动态路由算法 : 链路状态路由算法 OSPF , 所有的路由器掌握着 完整的网络拓扑 和 链路费用信息 ;

    ② 分散性 动态路由算法 : 距离向量路由算法 RIP , 路由器只掌握 物理连接的 相邻路由器 和 链路费用 ;





    六、分层次的路由选择协议



    分层次的路由选择协议 由来 :

    • 规模大 : 因特网规模很大 , 单个路由器不可能掌握所有的路由信息 ;
    • 保密性 : 很多组织对自己 网络的路由选择协议保密 , 不让外部知道具体细节 , 但还有接入因特网的需求 ;


    自治系统 ( Autonomous System ) :

    ① 自治系统 路由器 : 单一 技术管理下 的一组 路由器 ;

    ② 自治系统内部路由 : 这些 自治系统内部 路由器 使用 自治系统 内部的路由选择协议 , 和 共同的度量 , 确定分组在 自治系统 内部的路由 ;

    ③ 自治系统之间路由 : 自治系统 之间 采用相应的 自治系统之间的路由协议 ;

    ④ 管辖 : 自治系统 内部所有的网络 , 都是同一个行政单位管辖 ;

    ⑤ 连通性 : 自治系统 所有路由器必须在本自治系统 内部连通 ;



    自治系统 相关协议 :

    ① 自治系统 内部协议 : 内部网关协议 , RIP , OSPF ;

    ② 自治系统 之间协议 : 外部网关协议 , BGP-4 ;

    展开全文
  • 路由器路由算法前言定义自治系统路由协议内部网关协议RIP如何解决路由环路的问题?OSPF外部网关协议BGP后记 前言 昨天经过字节一面感觉自己对路由器了解甚少,所以决定还是认真学习一下路由器路由算法吧。 定义 ...

    前言

    昨天经过字节一面感觉自己对路由器了解甚少,所以决定还是认真学习一下路由器与路由算法吧。

    定义

    首先我们先对路由下一个定义,什么是路由?
    根据百度百科的解释,路由是指分组从源到目的地的时候,决定端到端路径的网络范围的进程。
    说白了就是选择一条合适路径来传输需要发送的数据包。

    自治系统

    自治系统(Autonomous System,AS)指的是在单一技术管理下的一组路由器,这些路由器使用同一种内部路由选择协议并且通过外部路由协议与其他的AS进行连接,一般来说一个大学、一个公司内部的所有路由器就属于一个自治系统。

    路由协议

    刚才说到一个AS有着自己的内部路由协议并且通过外部路由协议和其他AS连接。
    路由协议就可以根据内部和外部的不同分为:

    • 内部网关协议(Interior Gateway Protocol,IGP)
    • 外部网关协议(External Gateway Protocol,EGP)

    内部网关协议

    先来介绍内部网关协议,内部网关协议比较常用的有RIP和OSPF看,目前说的都是动态路由协议,如果采用静态路由协议则需要人为的设定路由信息。

    RIP

    RIP全称为路由信息协议,是一种基于距离向量的路由选择算法,其最大优点就是简单。
    基于距离向量的意思就是根据距离(代价)和方向决定目标网络或者目标主机位置的一种方式。
    RIP一般会采用洪泛法来进行更新,但是这样的问题就在于当网络构造变得复杂的时候在获得稳定的路由信息之前需要消耗大量的时间(俗称“坏消息传得慢”),而且比较容易法生路由循环等问题。

    RIP规定:

    • 网络中每个路由器都要维护从它自己到其他每一个目标网络的距离记录(也就是路由表)。
    • 距离也被称为跳数,直接相连的路由器跳数为1,然后每经过一个跳数就加1,最多不能超过15,距离为16的两个路由器被认为是不可达(防止环的问题)。
    • 两个路由器之间每隔30S发送一次路由信息。
    • 不支持子网掩码(RIP2中支持)。

    RIP是一个基于UDP的网络协议(内容跟在UDP的数据部分后面发送),选择的是路由跳数最少的路径而非最短时间的,适合用于比较小的网络。

    如何解决路由环路的问题?

    由于RIP协议中经常会出现环路的问题,所以一般有以下方法来防止一个数据包进入环路:

    • 最长距离不超过16,如果超过16则直接把数据包丢弃。
    • 规定一个路由器不再把所收到的路由信息原路返回给发送端,这也被称为水平分割。

    但是这样仍然不能解决网络中带有环这个根本问题,所以又提出了如下解决方案:

    • 毒性逆转:指的是当网络中发生链路被断开的时候不是不在发送这个消息而是将这个无法通信的消息传播出去。
    • 触发更新:当路由表发生变化的时候直接更新而不是等待30S。

    OSPF

    与RIP正好相反,OSPF常常用于管理比较大和复杂的网络。
    OSPF全称开放最短路径优先协议,采用的是分布式链路状态路由算法,每个节点会使用洪泛法的方式向其他节点告知自己与那些节点相邻,并且自己的度量(也就是从自己这里传递的代价),这样所有的节点都能直接构建出一个网络拓扑结构,最后会采用Dijkstra算法计算出一个最优的路径。
    但是这样又带来一个问题,当网络巨大的时候构建出一个完整的网络拓扑图的代价是非常巨大的,所以OSPF引入了“区域”的概念,把一个自治网络划分为若干个更小的范围,将洪泛法局限在区域之内而非整个网络,每个区域会指定若干个路由器作为默认路由来参与对外的信息交换。

    RIP的缺点还在于它利用好路由控制信息一遍确认是否连接了网络,一边传递网络信息,当网络比较巨大时候就路由控制信息就会随之变大,并且当路由表没什么变化的时候也会发送数据,浪费了网络带宽。

    相对了,OSPF面对这些问题划分出了5个不同功能的数据包:

    • 问候(Hello):确认相邻路由器或者指定路由器存在。
    • 数据库描述:链路状态数据库的摘要信息。
    • 链路状态请求:从数据库中获取链路状态信息。
    • 链路状态更新:更新链路状态数据库中的信息。
    • 链路状态确认应答:链路状态更新的确认应答。

    基于这些功能包,OSPF中每个节点会每隔一时间发送Hello数据包确认相邻节点的存活,达到一定次数没有返回则认为断开。
    当自己的链路连接情况发生变化的时候才会发送更新请求告知其他节点。

    OSPF相对RIP更加复杂,所以消耗的资源也更多,当网络巨大的时候光是计算最短路径就需要占用大量CPU。OSPF是基于IP协议的。

    外部网关协议

    BGP

    边界网关协议,BGP,是一种作用在不同AS之间的外部网关协议。采用的是路径向量路由协议,由于AS内部的协议差别巨大,所以很难找出一条最短路径,所以BGP力求一条能够达到目的网络并且比较好的路径。
    BGP要求每个AS选择至少一个对外的发言人,与RIP类似,每个节点都需要生成一个自己的路由表,并且在发生变化的时候和其他节点进行交换。
    由于路径向量在访问信息中保存了转发防线和距离还涵盖了途径所有的AS编号,所以能够检测出环路的问题,避免了无线计数的问题。

    后记

    暂时先更新到这里,算是把之前的坑给填上了,之后学习交换机工作原理以及其他网络协议的时候也会更新在这里。
    这一次字节面试让我感受到了很多不足,是时候收拾一些之前有点自满的心态,好好准备一下周五面试,感谢面试官手下留情,希望下次能出个简单点的算法。


    参考文章:
    《图解TCP/IP》学习——第七章路由协议
    到底什么是路由
    知乎问题:如何用一句话解释,链路状态协议与动态路由协议之间的区别?
    《图解TCP/IP》
    《王道考研系列计算机网络2019版》

    展开全文
  • 2、 动态路由算法:指路由器上的路由表项是通过相互连接的路由器之间彼此交换信息,然后按照一定的算法优化出来的,而这些路由信息是在一定时间间隙里不断更新,以适应不断变化的网络,以随时获得最优的寻路结果。...

    1、 静态路由算法:指由网络管理员手工配置的路由信息。当网络的拓扑结构或链路的状态发生变化时,网络管理员需要手动去修改路由表中的相关静态路由信息。大型和复杂的网络环境通常不宜采用静态路由。
    2、 动态路由算法:指路由器上的路由表项是通过相互连接的路由器之间彼此交换信息,然后按照一定的算法优化出来的,而这些路由信息是在一定时间间隙里不断更新,以适应不断变化的网络,以随时获得最优的寻路结果。,常用的动态路由可分为两类:距离—向量路由算法和链路状态路由算法。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

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

    网络:简述路由算法之动态路由算法


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

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

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

    1. 距离矢量路由算法
    2. 链路状态路由算法

    一、距离矢量路由算法

    距离矢量路由算法(Distance Vector Routing),它是网络上最早使用的动态路由算法,也称为Bellman-Ford或者Ford-Fulkerson算法。基于这类算法实现的协议有:RIP、BGP等。
    在这里插入图片描述
    如图,这类算法的基本思路是:网络中每一个路由器都要维护一张 矢量表 ,这个矢量表 中的每一行都记录了从当前位置能到达的目标路由器的最佳出口(接口)和距离(跳数)。

    每隔一段时间当前路由器会向所有的邻居节点发送自己的这个表,同时它也会接收每个邻居发来的它们的表。并会将邻居的表和自己的表做一个对比更新。

    比如当前 路由器X 离 邻居Y路由器 的距离是m,此时收到 邻居Y 发来的表中写到了“ 邻居Y离路由器Z的距离是n ”,那 当前路由器X 就知道它离 路由器Z 的距离可能就是 m+n 了,如图:
    在这里插入图片描述
    就这样继续类推,要不了多久,每个路由器就可以将网络中所有路由节点和子网线路都汇聚起来了。这样的话,每个路由器只需要查找自己的表就可以很容易的知道到达目的地的最佳出口(接口)是哪个了。

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

    「距离矢量路由算法」,“距离”这个词就基本表明了这个算法是通过 距离(跳数/时间)来度量2个路由网络之间的线路的,而“矢量”这个词,可以看出线路是有方向性的,且路由表中只记录了数据包去往目的地应该走哪个出口方向,并不会记录到达目的地的整条路径。

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

    「距离矢量路由算法」的缺点如下:

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

    二、链路状态路由算法

    链路状态路由算法(Link State Routing ),基于Dijkstra算法,它是以图论作为理论基础,用图来表示网络拓扑结构,用图论中的最短路径算法来计算网络间的最佳路由。基于这类算法实现的协议有:OSPF 等。
    在这里插入图片描述
    如图,这类算法的基本思路是:采用的是不停的拼接地图的方式。每一个路由器首先都会发现自己身边的邻居节点,然后将自己与邻居节点之间的链路状态包广播出去,发送到整个网络。这样,当某个路由器收到从网络中其它路由器广播来的路由信息包(链路状态包)之后,会将这个包中的信息与自己路由器上的信息进行拼装,最终形成一个全网的拓扑视图。

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

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

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

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

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

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

    将上述两种算法做一个简单的对比:
    在这里插入图片描述


    参考:

    1. https://mp.weixin.qq.com/s/7TTrDuykPWcYWeK5JnBT2A
    展开全文
  • 动态路由算法   可以根据里有协议算法生成动态路由表。   求最短路径算法 Bellman-Ford算法 Dijkstra算法   距离矢量路由算法——基于Bellman-Ford算法 路由器保存一张路由表,包含...
  • 高端路由器路由查找算法分析与实现.pdf
  • 实现了路由器分组转发算法,可以修改参数自定义网络。
  • 学习路由器模型及路由算法研究.pdf
  • 计算机网络篇:网络层网络互连之动态路由选择算法计算机网络篇:网络层网络互连之动态路由选择算法具体线路路由器举个栗子转载需注明出处 计算机网络篇:网络层网络互连之动态路由选择算法 首先网络层的功能之一...
  • 提出了一种MPLS流量工程中新的保证带宽的动态路由算法。传统的算法如SPF(Shortest Path First)算法、WSP算法(Widest Shortest Path)等都没有利用业务分布或入出路由器对(Ingress-Egress Pairs)的信息,可能导致...
  • 分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了...
  • IGP) RIP是一种基于距离矢量(Distance-Vector)算法的协议,它通过UDP报文进行路由信息的交换,使用的端口号为520 RIP定时器 update 为更新时间,它定时角发更新报文的发送Age为老化时间,RIP路由器如果在老化时间...
  • 路由器路由查找算法 路由器基本概念 路由器就是在网络层根据数据包目的地址进行IP数据包转发并完成其他网络功能的设备。 1)为什么要分为域间与域内路由? 满足不同域之间管理的需要,减少路由表大小。 2)为...
  • 近十年来,随着计算机网络规模的不断扩大,大型互联网络(如Internet)的迅猛发展,路由技术在网络技术中已逐渐成为关键部分,路由器也随之成为最重要的网络设备。把自己的网络同其它的网络互连起来,从网络中获取更...
  • 路由器的分组转发算法

    千次阅读 2021-02-24 19:15:18
    路由器的分组转发算法: 1.从数据报的首部提取目的主机的IP地址D,得出目的网络地址为N。 2.若N就是与此路由器直接相连的某个网络地址,则进行直接交付,不需要再经过其他的路由器,直接把数据报交付目的主机(这里...
  • 在计算机网络中,路由器的一个很重要责任就是要在端对端的节点中找出一条最佳路径出来,通过自己与相邻节点之间的信息,来计算出从自己位置到目的节点之间的最佳线路,这种算法我们可...
  • 动态路由算法大致可以分为两类: 距离矢量路由算法 链路状态路由算法 下面我们来看一下这两类算法的特点: 一、距离矢量路由算法 距离矢量路由算法(Distance Vector Routing),它是网络上最早使用的...
  • 路由算法详解

    千次阅读 2020-12-30 09:55:21
    路由算法详解1. 引言 2. 路由器基础知识 3. LS算法 4. 示例:Dijkstra算法 5. DV算法 6. 分级路由如果您已经阅读过博闻网中的路由器工作原理一文,您会了解到路由器的作用是管理网络流量和找到发送分组数据包的最佳...
  • 路由器体系结构及路由算法研究进展.pdf
  • 路由器的构造及路由算法的研究.pdf
  • 路由算法(全网最细)

    千次阅读 多人点赞 2020-05-04 18:07:17
    路由算法综述2.静态路由算法3.距离-向量路由算法(RIP)4.链路状态路由算法(OSPF)5.层次路由 1.路由算法综述 路由器转发分组是通过路由表转发的,而路由表是通过各种算法得到的。主机通常直接与一台路由器相连接,该...
  • 动态路由协议分类--按路由算法划分

    千次阅读 2019-05-16 22:27:00
    3、定期广播整个路由信息,传闻式路由算法 4、易形成路由环路配置简单,收敛慢,扩展性较差 5、链路状态路由协议(如OSPF、IS-IS 6、基于Dijikstra算法,又称为L-S算法,SPF算法(最短路径优先) 7、收集网络拓扑...
  • dv路由交换算法实现

    2019-04-27 22:15:01
    简单的一个dv路由交换算法,供学习参考
  • 文章目录前言一、路由算法引入二、静态路由三、动态路由1.链路状态(LS)路由算法2.距离向量(DV)路由算法总结 前言 提示:以下是本篇文章正文内容 一、路由算法引入 路由器的功能: 路由算法(协议)确定去往目的...
  • 实验十 路由器OSPF动态路由配置

    千次阅读 2017-03-24 10:32:03
    实验十 路由器OSPF动态路由配置 一、实验目的 掌握OSPF协议的配置方法: 掌握查看通过动态路由协议OSPF学习产生的路由; 熟悉广域网线缆的链接方式; 二、实验背景  假设校园网通过一台三层交换机连到...
  • 但是BGP在不考虑路由策略和路由控制的情况下,使用的BGP算法,用的是距离矢量算法,默认以自治系统为单位计算代价。 rip协议用的也是距离矢量算法,ospf协议用的是链路状态算法和距离矢量算法
  • 路由拨号助手是路由器拨号的辅助工具,解决路由器无法使用特殊用户名拨号的问题。同时本软件加入了星空极速V14及V18的算法,方便使用路由器共享。当前版本内置参数支持的路由
  • OSPF路由协议通过向全网扩散本设备的链路状态信息,使网络中每台设备最终同步一个具有全网链路状态的数据库,然后路由器采用 SPF 算法,以自己为根,计算到达其他网络的最短路径,最终形成全网路由...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,926
精华内容 17,970
关键字:

路由器动态路由算法