2017-07-18 09:39:35 m0_37956168 阅读数 1455
  • Cisco CCNP路由实验专题讲解视频课程--路由重分发篇

    理解并配置路由重分发 redistribution,讨论路由重分发存在的问题:管理距离、度量值、次优链路、路由环路等,并演示对应的解决方案。 在实际组网中,由于各种各样的需求和条件决定,网络中可能存在多种路由协议,这些协议之间是相互独立和隔离的,那么如何让这些不同的路由协议能够通信呢?这就要用到路由重发技术。

    5475 人正在学习 去看看 晁海江

1. 路由算法

路由算法,又名选路算法,可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径(即具有最低费用的路径)。算法设计者的特定目标影响了该路由协议的操作;具体来说存在着多种路由算法,每种算法对网络和路由器资源的影响都不同;由于路由算法使用多种度量标准(metric),从而影响到最佳路径的计算。

在linux中使用 route 显示路由表

这里写图片描述
这他主机的网络接口接到192.254.187.0/24⽹网络,路由表的Destination是⽬目的⽹网络地址,Genmask是⼦子⽹网掩 码,Gateway是下⼀一跳地址,Iface是发送接⼜⼝口,Flags中的U标志表⽰示此条⽬目有效(可以禁⽤用某些 条⽬目),G标志表⽰示此条⽬目的下⼀一跳地址是某个路由器的地址,没有G标志的条⽬目表⽰示⽬目的⽹网络地 址是与本机接⼜⼝口直接相连的⽹网络,不必经路由器转发,因此下⼀一跳地址处记为* 号。

2. 常见的路由算法

  1. LS算法
    原理:当前节点向与自己直接相连的路由器发送数据,其他相连的路由器在接受的数据后做出相应,当前路由器通关计算来回的时间来判断出最佳路由,路由后判断是否为目标路由。
    这里写图片描述
  2. 距离向量算法
    路由器周期性地向其相邻路由器广播自己知道的路由信息,用以通知相邻路由器自己可以到达的网络以及到达该网络的距离。相邻路由器可以根据收到的路由信息修改和刷新自己的路由表。 优点是算法简单容易实现。缺点是慢收敛问题,路由器的路径变化需要像波浪一样从相邻路由器传播出去,过程缓慢。
    这里写图片描述
2016-11-29 22:37:25 baidu_34372014 阅读数 3324
  • Cisco CCNP路由实验专题讲解视频课程--路由重分发篇

    理解并配置路由重分发 redistribution,讨论路由重分发存在的问题:管理距离、度量值、次优链路、路由环路等,并演示对应的解决方案。 在实际组网中,由于各种各样的需求和条件决定,网络中可能存在多种路由协议,这些协议之间是相互独立和隔离的,那么如何让这些不同的路由协议能够通信呢?这就要用到路由重发技术。

    5475 人正在学习 去看看 晁海江

 

 

路由算法

 

 

链路状态路由算法的具体实现

 

1

)链路状态路由算法的原理

 

链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼图”的设计策略,

即每个路由器将它到其周围邻居的链路状态向全网的其他路由器进行广播。

这样,

一个路由

器收到从网络中其他路由器发送过来的路由信息后,

它对这些链路状态进行拼装,

最终生成

一个全网的拓扑视图,

近而可以通过最短路径算法来计算它到别的路由器的最短路径。

运行

链路状态路由协议的路由器

每台路由器公在其接口的状态发生变化时,

才将变化后的状态

发送给其他所有路由器,每台路由器都使用收到的信息重新计算前往每个网络的最佳路径,

然后将这些信息存储到自己的路由选择表中。

 

链路状态路由算法背后的思想非常简单,可以用

5

个基本步骤加以描述。

 

1

、发现他的邻接点,并知道其网络的地址。

 

2

、测量到各邻接点的延迟或开销。

 

3

、构造一个分组,分组中包含所有他刚刚收到的信息。

 

4

、将这个分组发送给其他的路由器。

 

5

、计算出到每一个其他路由器的最短路径。例如,每个路由器运行

Dijkstra

算法就可以找

从它到每一个其他路由器的最短路径。

链路状态路由算法的具体实现 

    链路状态路由算法的原理 

    链路状态路由协议是目前使用最广的一类域内路由协议。它采用一种“拼图”的设计策略,即每个路由器将它到其周围邻居的链路状态向全网的其他路由器进行广播。这样,一个路由器收到从网络中其他路由器发送过来的路由信息后,它对这些链路状态进行拼装,最终生成一个全网的拓扑视图,近而可以通过最短路径算法来计算它到别的路由器的最短路径。运行链路状态路由协议的路由器, 每台路由器公在其接口的状态发生变化时,才将变化后的状态发送给其他所有路由器,每台路由器都使用收到的信息重新计算前往每个网络的最佳路径,然后将这些信息存储到自己的路由选择表中。 

    链路状态路由算法背后的思想非常简单,可以用5个基本步骤加以描述。 

1、发现他的邻接点,并知道其网络的地址。

2、测量到各邻接点的延迟或开销。 

3、构造一个分组,分组中包含所有他刚刚收到的信息。 

4、将这个分组发送给其他的路由器。 

5、计算出到每一个其他路由器的最短路径。例如,每个路由器运行Dijkstra算法就可以找从它到每一个其他路由器的最短路径。
2019-05-02 19:05:40 qq_43326818 阅读数 193
  • Cisco CCNP路由实验专题讲解视频课程--路由重分发篇

    理解并配置路由重分发 redistribution,讨论路由重分发存在的问题:管理距离、度量值、次优链路、路由环路等,并演示对应的解决方案。 在实际组网中,由于各种各样的需求和条件决定,网络中可能存在多种路由协议,这些协议之间是相互独立和隔离的,那么如何让这些不同的路由协议能够通信呢?这就要用到路由重发技术。

    5475 人正在学习 去看看 晁海江

一、路由算法

二、路由协议

一、路由算法

1、泛洪算法Flooding
  • 泛洪算法的具体的做法:
    • 不需要网络信息
    • 由源节点将分组发送给其邻近结点
    • 结点接收到分组之后,在除接收链路之外的所有链路上进行转发
    • 最终,分组的多个备份将到达目的节点
    • 每个分组有唯一的序号,以消除重复的分组
    • 结点可以记住哪个分组曾被转发过,将网络负载控制在一定的范围内
    • 在分组中可以包含有关跳数的信息,一般是设定最大的跳数,每进行一跳,就将该跳数减少一,知道为0的时候就不可以再跳
  • 泛洪算法的特点:
    • 尝试所有可能的路由,很稳健
    • 可以获得最小的跳数路由,可用于建立虚电路
    • 可以获得所有结点信息,用于分组转发
    • 多次复制并转发分组,增加了网络负载
2、路由选择分类
  • 集中:路由器有全部的拓扑及链路代价的完整信息,Dijkstra算法
  • 分布:路由器知道其邻居结点,以及它到邻居结点,以及它到邻居结点的代价;通过邻居结点交换信息,通过迭代逐渐获得最小代价;Bellman-Ford算法
  • 静态:路由岁时间的变化缓慢
  • 动态:路由岁时间的变化很快,周期性更新,随链路代价的改变而变化
3、最短路径算法(Dijkstra算法)
  • 所有结点已知网络拓扑及链路代价;通过“链路状态广播"获得;所有的节点具有相同的信息
  • 计算从一个源结点到其他结点的最小代价路径;给出对应结点的转发表
  • 迭代:经过K此迭代,获得k个目的节点的最小代价路径
  • 如果到达同一个目的的距离相同,但是经过的点不同,那么就选择最新的;感觉表中的都是下一跳(废话,不是下一跳路由表难道不就没有意义了!!!!)
注意转发表和路由表之间的区别:转发表指的是输出端口的选择,所以其取值是某路由器的输出端口,而路由表是到所有的节点的下一条
4、距离矢量算法,Bellman-Ford算法
  • 核心思想是根据其他的节点来更新自己
  • 取最小的结点作为最短路径上的下一条-》转发表
  • 迭代:出发迭代的原因:链路的代价变化;收到邻居的DV更新消息
  • 异步:各节点独立计算,无需同步
  • 分布式:只有当其DV改变时,才发送消息通知邻居;邻居再发消息通知其邻居结点
  • 因为一般链路的代价是不变的,所以出发迭代是DV的改变,而DV指的就是距离矢量,也就是最短的,所以是当某结点的路由表法神改变的时候才向周围结点发送进行更新 ;而不是距离矩阵改变就想周围发送

二、路由协议

1、路由信息协议(RIP)
  • RIP是一种基于距离矢量的分布式路由协议
  • 每个路由器维护其到每个目的网络的距离记录
  • 定义:路由器到直连网络的距离为1,到非直连网络的距离为中间路由器的个数加上1,距离也成为跳数,选择具有最少跳数的路由
  • 一条路径最多只包含15个路由器,距离为16的时候表示的是不可达
  • 仅与相邻路由器交换路由表信息,路由表的信息为:目的网络 跳数 下一跳(其实与转发表也没有太大的差别)
  • 按固定的时间间隔交换路由信息,例如每隔30秒
  • 距离矢量算法
    • 收到相邻路由器地址为X的RIP报文
    • 修改此RIP报文中的所有项,将下一跳改为X,距离都增加1
    • 如果在路由表中有的项那么就不变,如果有的目的地址RIP中有但是在路由表中没有的,那么就将RIP中的项增加到路由表中,得到新的路由表
    • (选择最新原则)如果RIP的目的地址在路由表中,如果下一跳相同,那么用RIP的项代替路由表中的项(可能是因为该算法保证 了得到最新的RIP中的项为最小跳数的);如果目的地址相同下一跳不同,那么就选择跳数少的(总之就是跳数相同选最新,否则选择最少跳数的)
    • 若三分钟为收到相邻路由器的更新路由表,则将此路由器记为不可达,即将距离设置为16(因为路由表中要有到达所有网络应该怎么走,如果某个路由器不给信息, 那么说明可能有些目的的路由就得不到,所以为了防止无限等待,就将距离设置为不可达)
    • 返回
  • RIP协议的特点:
    • RIP协议采用广播或者组播进行路由更新,RIPv1使用的是广播,RIPv2使用的是组播
    • RIP协议允许主机只接收和更新路由信息而不发送信息
    • RIP协议支持默认路由
    • RIP协议的网络不超过15跳,适合中小型网络
    • RIPv1是有类的路由协议;RIPv2是无类(IP地址+掩码)路由协议,即RIPv2的报文中含有掩码信息
  • RIP协议的问题:无穷计算
    • RIP协议存在好消息传的快,坏消息传的慢的特点
    • 当某个机器启动的时候,其消息会马上发送给其他的主机
    • 但是当某个机器关机,由于其他的主机得不到这个信息,也就得不到完整的路由信息(也就是关机的主机的路径信息),那么就会无限重复计算
    • 解决的方式:将无穷大的路由器的跳数设置为最大跳数+1;禁止路由器C向路由器B发送一个从邻居B获得的最佳路径
2、开放最短路径优先(OSPF),链路状态路由(LS),也就是首先要得到整个网络的结构
  • LS的路由器的工作过程:
    • 发现邻居结点:使用hello信息
    • 测量链路代价
    • 创建链路状态分组,定时或者发生时间时创建
    • 发布链路状态分组:可靠发布
    • 计算新的路由:采用最短路径算法
  • LS的具体算法OSPF算法:
    • 使用扩散法向所有(而不只是临近)路由器发送与其相邻路由器的链路状态
    • 当链路状态发生改变时发送信息
    • 定期(至少30分钟)发送一次
    • 算法
      • 主动测试邻接结点的状态
      • 将与其相邻结点的状态信息传送给所有的节点
      • 每个节点获得完整的网络拓扑信息,完后Dijkstra最短路径算法计算到每个节点的最佳路径
    • 基本操作:物种分组类型:问候、链路状态描述、链路状态请求、链路状态更新、链路状态确认(ACK,所以是可靠的)
    • OSPF特点:
      • OSPF的数据报很短,减少路由信息量
      • 每隔一段时间,刷新一次链路状态
      • 由于一个路由器的链路状态值涉及与相邻路由器的连通状态,而与互联网的规模没有直接关系。当互联网的规模很大时,OSPF协议要比 距离向量协议RIP好很多
      • OSPF没有好消息快,坏消息慢的特点
3、LS与DV比较
  • DV仅与邻居交换信息,但提供到其他结点的DV的估计;而LS与网络所有结点交换代价信息,每个节点获得网络拓扑及链路代价的全部信息
  • 发送的报文数:LS为N*E数量级,变化一个全部交换;DV是在邻居结点之间交换,变化则再交换
  • 收敛时间:LS为n*n,DV的收敛时间收到很多的影响,一般较长
  • 稳健性:LS为分别计算,一个错误不会影响全局,稳健;DV,一个结点的计算错误,会在结点之间扩散,影响整个网络,稳健性差
2011-05-04 11:27:00 liunian59 阅读数 351
  • Cisco CCNP路由实验专题讲解视频课程--路由重分发篇

    理解并配置路由重分发 redistribution,讨论路由重分发存在的问题:管理距离、度量值、次优链路、路由环路等,并演示对应的解决方案。 在实际组网中,由于各种各样的需求和条件决定,网络中可能存在多种路由协议,这些协议之间是相互独立和隔离的,那么如何让这些不同的路由协议能够通信呢?这就要用到路由重发技术。

    5475 人正在学习 去看看 晁海江

  网络工程师考试对于路由选择协议的考查,主要包括计算机互联网络系统中信息包的传递和路由选择过程、各种常用路由选择技术的特性,以及不同路由选择协议间的区别与联系。从近几次考试的真题来看,本知识点占有比较重要的地位,基本上每次考试都有涉及,如RIPOSPFIGRP等常见路由协议,更加偏向于理论知识的考查。具体如表1-1所示:

1-1 路由选择协议的应用范围

  下面就几种常见的路由选择协议以及它们之间区别与联系进行具体介绍:

  一、路由选择协议的应用范围

  根据路由选择协议的应用范围,可以将其分为内部网关协议(IGP)、外部网关协议(EGP)和核心网关协议(GGP)三大类。其分类如图1-1所示:

  1-1 路由选择协议的应用范围

  l 自治系统(AS):是指同构型的网关连接的互连网络,通常是由一个网络管理中心控制的。

  l 内部网关协议(IGP):在一个自治系统内运行的路由选择协议,主要包括RIPOSPFIGRPEIGRP等。

  l 外部网关协议(EGP):是指在两个自治系统之间使用的路由选择协议,最新的EGP协议是BGP,其主要的功能是控制路由策略。

  l 核心网关协议:Internet中有个主干网,所有的自治系统都连接到主干网上,主干网中的网关称为核心网关,核心网关之间交换路由信息时使用的是核心网关协议GGP

  二、常用路由选择协议

  我们都常接触、使用得较多的路由选择协议是内部网关协议,根据算法的不同,主要包括RIP(路由信息协议)OSPF(开放最短路径优先协议)IGRP(内部网关路由协议)EIGRP(增强型内部网关路由协议)四种。所有的路由协议可以分为三类:

  1-2 路由协议的类别

  (1)RIP协议

  RIP(Routing Information Protocols,路由信息协议)是使用最广泛的距离向量协议,它是由施乐(Xerox)70年代开发的。TCP/IP版本的RIP是施乐协议的改进版。RIP最大的特点是,无论实现原理还是配置方法,都非常简单。RIP基于跳数计算路由,并且定期向邻居路由器发送更新消息。

  (2)IGRP协议

  IGRPCISCO专有的协议,只在CISCO路由器中实现。它也属于距离向量类协议,所以在很多地方与RIP有共同点,比如广播更新等等。它和RIP最大的区别表现在度量方法、负载均衡等几方面。IGRP支持多路径上的加权负载均衡,这样网络的带宽可以得到更加合理的利用。另外,与RIP仅使用跳数作为度量依据不同,IGRP使用了多种参数,构成复合的度量值,这其中可以包含的因素有:带宽、延迟、负载、可靠性和MTU(最大传输单元)等等。

  (3)OSPF协议

  OSPF协议是80年代后期开发的,90年代初成为工业标准,是一种典型的链路状态协议。OSPF的主要特性包括:支持VLSM(变长的子网掩码)、收敛迅速、带宽占用率低等等。OSPF协议在邻居之间交换链路状态信息,以便路由器建立链路状态数据库(LSD),之后,路由器根据数据库中的信息利用SPF(Shortest Path First,最短路径优先)算法计算路由表,选择路径的主要依据是带宽。

(4)EIGRP协议

 EIGRPIGRP的增强版,它也是CISCO专有的路由协议EIGRP采用了扩散更新(DUAL)算法,在某种程度上,它和距离向量算法相似,但具有更短的收敛时间和更好的可操作性。作为对IGRP的扩展,EIGRP支持多种可路由的协议,如IPIPXAppleTalk等等。运行在IP环境时,EIGRP还可以与IGRP进行平滑的连接,因为它们的度量方法是一致的。

路由选择协议将路由信息发送到其它节点所采用的基本算法是扩散法,为了避免信息重复发送,通常会对路由信息包进行编号,通常是每发送一个路由信息就递增编号(即加1)。表1-3中总结了五种常见路由协议的知识点:

1-3 主要路由协议

  以上四种路由协议都是域内路由协议,它们通常使用在自治系统的内部。当进行自治系统间的连接时,往往采用诸如BGP协议和EGP协议这样的域间路由协议。目前在Internet上使用的域间路由协议是BGP第四版。

  收敛是路由算法选择时所遇到的一个重要问题。收敛时间是指从网络的拓扑结构发生变化到网络上所有的相关路由器都得知这一变化,并且相应地做出改变所需要的时间。这一时间越短,网络变化对全网的扰动就越小。收敛时间过长会导致路由循环的出现。

在上述几种域内路由算法中,RIPIGRP的收敛时间相对较长,都是分钟数量级的;OSPF要短一些,数十秒内可以收敛;EIGRP最短,网络拓扑发生变化之后,几秒钟即可达到收敛状态。

相关资料:

网络工程师考前复习专题资料:http://www.csairk.com/user/xch/from.asp?id=327&wh=201212

2011年软考网络工程师全面复习资料汇总http://www.csairk.com/user/xch/from.asp?id=440&wh=201212

网络工程师考试大纲与培训指南:http://www.csairk.com/user/xch/from.asp?id=503&wh=201212

网络工程师考前网络串讲:http://www.csairk.com/user/xch/from.asp?id=365&wh=201212

网络工程师考试指南:http://www.csairk.com/user/xch/from.asp?id=240&wh=201212

网络工程师软考学院20115月软考培训全国招生:http://www.csairk.com/user/xch/from.asp?id=422&wh=201212

 

三、路由选择协议比较上述几种常见路由协议细节比较如下表所示:

2017-06-18 23:47:06 simplehap 阅读数 826
  • Cisco CCNP路由实验专题讲解视频课程--路由重分发篇

    理解并配置路由重分发 redistribution,讨论路由重分发存在的问题:管理距离、度量值、次优链路、路由环路等,并演示对应的解决方案。 在实际组网中,由于各种各样的需求和条件决定,网络中可能存在多种路由协议,这些协议之间是相互独立和隔离的,那么如何让这些不同的路由协议能够通信呢?这就要用到路由重发技术。

    5475 人正在学习 去看看 晁海江

路由算法

路由算法,又名选路算法,可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径。算法设计者的特定目标影响了该路由协议的操作;具体来说存在着多种路由算法,每种算法对网络和路由器资源的影响都不同;由于路由算法使用多种度量标准,从而影响到最佳路径的计算。

关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由,有两种主要的路由算法
总体式路由算法和分散式路由算法。采用分散式路由算法时,每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV(距离向量)算法。采用总体式路由算法时,每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS(链路状态)算法。

路由算法的核心是路由选择算法,设计路由算法时要考虑的技术要素有:

1、选择最短路由还是最佳路由;
2、通信子网是采用虚电路操作方式还是采用数据报的操作方式;
3、采用分布式路由算法还是采用集中式路由算法;
4、考虑关于网络拓扑、流量和延迟等网络信息的来源;
5、确定采用静态路由还是动态路由。

各路由算法的区别点包括:静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。


LS算法

采用LS算法时,每个路由器必须遵循以下步骤:
1、确认在物理上与之相连的路由器并获得它们的IP地址。当一个路由器开始工作后,它首先向整个网络发送一个“HELLO”分组数据包。每个接收到数据包的路由器都将返回一条消息,其中包含它自身的IP地址。
2、测量相邻路由器的延时(或者其他重要的网络参数,比如平均流量)。为做到这一点,路由器向整个网络发送响应分组数据包。每个接收到数据包的路由器返回一个应答分组数据包。将路程往返时间除以2,路由器便可以计算出延时。(路程往返时间是网络当前延迟的量度,通过一个分组数据包从远程主机返回的时间来测量。)该时间包括了传输和处理两部分的时间——也就是将分组数据包发送到目的地的时间以及接收方处理分组数据包和应答的时间。
3、向网络中的其他路由器广播自己的信息,同时也接收其他路由器的信息。
在这一步中,所有的路由器共享它们的知识并且将自身的信息广播给其他每一个路由器。这样,每一个路由器都能够知道网络的结构以及状态。
4、使用一个合适的算法,确定网络中两个节点之间的最佳路由。
在这一步中,路由器选择通往每一个节点的最佳路由。它们使用一个算法来实现这一点,如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算法)则要求每个路由器发送其路由表全部或部分信息,但仅发送到邻近结点上。从本质上来说,链路状态算法将少量更新信息发送至网络各处,而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快,因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面,链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间,因此链路状态算法将会在实现时显得更昂贵一些。

路由技术

阅读数 325

没有更多推荐了,返回首页