精华内容
下载资源
问答
  • 链路状态
    千次阅读
    2020-09-29 14:32:28

    路由算法

      网络层的主要功能是将数据包从源机器路由到目标机器。在大多数网络中,数据包需要经过多跳才能到达目的地。路由算法和这些算法所用的数据结构是网络层设计的最主要内容。

      可以这样想,路由器内部有两个进程。其中一个进程在每个数据包到达的时候,对它进行处理,它在路由表中查找该数据包所对应的出境路线,这个进程即为转发进程;另一个进程负责生成和更新路由表,这正是路由算法发挥作用的地方

      路由算法可以分为两大类:
      非自适应算法不会根据当前测量或者估计的流量和拓扑结构,来调整他们的路由决策。相反,从I到J的所使用的了路由选择是预先下载到路由器中的,也称为静态路由。因为它无法响应故障,所以对与路由选择已经很清楚的场合非常有用。
      自适应算法会改变它们的路由决策以便反映出拓扑结构的变化,通常也会反映出流量的变化情况。这些动态路由算法在多方面有些差别:获取信息的来源不同(本地、邻居路由器、所有路由器)、改变路径的时间不同(每当拓扑发生变化时、每隔T秒随负载变化)、路由优化的度量不同(距离、跳数、估计的传输时间)

    从Dijkstra最短路径算法开始

      给定一个完整的网络视图,dijkstra最短路径算法可以计算出单点到其他所有点的最优路径。这些路径是我们希望分布式路由算法发现的,即使不是全部路由器都知道网络的所有细节。

    可以参看博客 Dijkstra最短路径算法 的描述

    泛洪算法

      在实现路由算法时,每个路由器必须根据本地只是而不是网络的全貌做决策,一个简单的本地技术是泛洪(flooding)。这种技术将每一个入境数据包发送到除了该数据包到大的那条线路以外的每条出境路线。
      很明显,泛洪法会产生大量的重复的数据包,这就需要采取一些措施:

    • 在每个数据包的头中设置一个跳计数器,每经过一跳该计数器减一,当计数器到达0时就丢弃该数据包
    • 跟踪已经泛洪过的数据包,从而避免第二次发送它们。一种方式是,让每个源路由器在接收来自主机的数据包时填上一个序号,然后每个路由器为每个源路由器准备一张表,记录已经观察到的来自源路由器的序号,如果入境包在这张表中,就不再泛洪该数据包。
    • 为了防止该表膨胀,每个表应该使用一个计数器K作为参数,表示直到K的所有序号都已经观察到了,不需要记录K以下的整个列表。

      对于发送大多数数据包来说,泛洪算法是不切实际的,但它确实有一些重要的用途。首先,它确保数据包能被送到网络中的每个节点。对于广播信息来说,这是一种有效的广播手段。其次,泛洪算法的鲁棒性非常好,即使大量的路由器被炸碎,它依然可以找到一条路径(如果存在),把数据包送到目的地。泛洪需要的安装很少,路由器仅仅需要知道自己的邻居即可。
      这意味着,泛洪可以作为其他路由算法的基本构件,那些算法更有效但需要更多的处理。泛洪算法总能选出最短的路径,没有其他的算法能够产生一个更短的延迟(当然,这要忽略泛洪过程本身产生的开销)

    距离矢量算法(distance vector routing)

      每个路由器维护一张表(即一个矢量),表中列出了当前已知的到每个目标的最佳距离,以及所用的链路。这些表通过邻居之间交换信息而不断被更新,最终每个路由器都了解到达每个目的地的最佳链路。也叫分布式Bellman-Ford路由算法

      可以参考:距离矢量算法简介距离矢量算法示例

      这个算法存在一个严重的缺陷:虽然它总是能够收敛到正确的答案,但速度可能非常慢。尤其是,它对于好消息的反应非常迅速,而对于坏消息的反应异常迟钝。这个算法存在无穷计数的问题。可扩展性很差,越大的网络收敛的越慢。而且,会占用比较大的网络带宽。

    链路状态路由(link state routing)

      导致距离矢量算法退位的主要原因在于,当网络拓扑结构发生变化后距离矢量路由算法需要太长的时间才能收敛到稳定的状态(由于无穷计数的问题)。因此,出现了一个全新的算法,链路状态路由算法。今天,链路状态路由算法的变种算法——IS-IS或者OSPF已经称为大型网络或Internet应用最为广泛的路由算法。

      该算法的设计思路非常简单,对于每个路由器来说,需要完成以下步骤:

    • 发现它的邻居节点,并了解其网络地址
    • 设置到每个邻居节点的距离或者成本度量值
    • 构造一个包含所有刚刚获知的链路信息包
    • 将这个包发送给所有其他的路由器,并接收来自所有其他路由器的信息包
    • 计算出到每个其他路由器的最短路径

      实际上,该算法将完整的拓扑结构分发给了每一个路由器。然后每个路由器运行Dijkstra算法就可以找到从本地到每一个其他路由器的最短路径。

    发现邻居

      当一个路由器启动时,它的第一个任务就是找出哪些路由器是它的邻居。为了实现这个目标,它只需要在每一条点到点线路上发送一个特殊的 HELLO数据包。线路另一端的路由器应该返回一个应答说明自己是谁。

    设置链路成本

      为了寻求最短路径,链路状态路由算法需要每条链路以距离或成本度量。到邻居节点的成本可自动设置或由网络运营商配置的度量。一种常见的选择是使成本和带宽成反比。如果网络地理上分散,链路的延迟可以作为成本的组成部分。确定这种延迟的最直接的方法是通过线路给另一边发送一个特殊的 ECHO数据包,要求对方立即返回,通过测量往返时间再除以2,发送路由器可以得到一个合理的延迟估计值。

    构造链路状态包

      该数据包的内容首先是发送方的标识符,接着是一个 序号(seq)年龄(age),以及一个 邻居列表,对于每个邻居同时要给出 到这个邻居的成本链路状态包
      构造链路状态包很容易。难得是确定什么时候构造数据包,一种做法是周期性的构造数据包。另一种做法是每当发生某些重要的事情时才创建数据包,比如当一条线路断掉或者一个邻居节点停机时,或者当它们重新恢复运行时,或当它们得特性发生了一定变化时。

    分发链路状态包

      链路状态路由算法最技巧的部分在于分发路由状态数据包。首先,基本的思路是使用泛洪法将链路状态包分发给所有的路由器。

      为了控制泛洪规模,每个数据包都包含一个 序号(seq),序号随着每一个新数据包发出而注意递增。路由器记录下它所看到的所有(源路由器、序号)对。当一个新的链路状态数据包到达时,路由器检查这个新来的数据包是否已经出现在上述观察到的列表中。如果是一个新的数据包,则把它转发到除了入境路线之外的所有其他线路上。如果这是一个重复的数据包,则将它丢弃。如果数据包得序号小于当前所看到过得来自该源路由器得最大序列号,则将它作为过时数据包而拒绝接收,因为路由器已经有了更新得数据。
      问题一:序号绕回,可能会产生混淆。解决方案是使用一个32位得序列号,即使1S一个链路状态数据包,也要137年才能绕回,所以这种可能性可以忽略!
      问题二:序号被破坏了。比如发送方发送得序号是4,由于产生1bit错误,所以接收方接受的65540,那么,序号5-65540得数据包都将被作为过时数据包而拒绝接受。

      所有这些问题的解决方案都一样:在每个数据包得序号后面包含一个 年龄(age) 字段,并且每秒钟将年龄减1,当年龄字段的值被减到0时,来自路由器的该信息将被丢弃。通常情况下,每隔一段时间,比如10s,一个新的数据包就会到来;所以只有当一个路由器停机时(或者6个连续的数据包被丢失,这种情况发生的可能性不大),路由器信息才会超时。在初始泛洪过程中,每个路由器也要递减age字段,这样可以确保没有数据包丢失,也不会无限制生存下去。

      为了使得算法更为健壮。当一个链路状态数据包被泛洪到一个路由器时,它并没有立即被排入队列等待传输。相反,它首先被放到一个 保留区 中等待一段时间。如果在这个数据包被发出去之前,另一个来自同一个源路由器的链路状态数据包也到来了,那么就比较它们得序号,保留最新的包。为了防止线路产生错误导致丢包和错包,所有的链路状态数据包都要被确认。
    在这里插入图片描述
      在图中,来自A得链路状态数据包可以直接到达,所以B必须将它发送给C和F,并按照标志位得指示向A发送确认。
      然而,第三个数据包,即来自E得数据包有所不同。它到达两次,依次经过EAB,另一次经过EFB。因此它只需要被发送给C,但仍然需要向A和F确认。

    计算新路由

      一旦路由器积累了全部的链路状态数据包之后,它就可以构造出完整的网络图,然后就可以在路由器本地运行Dijkstra算法,从而构造出从本地出发到所有可能目标的最短路径。这个算法的运行结果告诉路由器到达每个目的地能够走那条路径。这个信息被安装在路由表中。

    实际应用

      相比于距离矢量算法,链路状态路由算法需要更多的内存和计算,在大型网络中运行这个算法依然是个问题。不过,在许多现实场合,链路状态路由算法工作得非常好,因为它没有慢收敛得问题。

      链路状态路由算法被广泛应用于实际网络中。IS-IS,Intermediate System-Intermediate System,被很多的ISP使用。后来它被ISO采纳用于OSI协议;然后它被修改多次以便能够处理多种协议,比如IP协议。OSPF,Open Shortest Path First,是另一个主流的链路状态协议。

    参考

    Dijkstra最短路径算法

    距离矢量算法简介

    距离矢量算法示例

    CSDN-链路状态路由选择

    博客园-链路状态路由选择

    更多相关内容
  • 直到1979年,ARPANET都用的是距离矢量路由选择,之后变为由链路状态路由选择所代替。两个主要问题导致了 距离矢量路由选择算法的消亡。第一,因为延迟度量是队列长度,在选择路由时,并没有将线路的带宽考虑进去 。...
  • 实验四 链路状态路由算法原理实验报告 【实验目的】 1、要求实验者利用路由选择算法模拟软件提供的通信功能,模拟链路状态路由选择算法的初始化、路由信息扩散过程和路由计算方法; 2、掌握链路状态算法的路由...
  • 华为ospf链路状态数据库,LSA TYPE 1、LSA TYPE 2、LSA TYPE、3 LSA TYPE、4 LSA TYPE 5;的一些总结。
  • 计算机网络课程设计文档,题目是链路状态路由选择算法的实现,用c语言来实现全部功能,包括代码(用visual studio 来实现),完成答辩,成绩较高。大家可以下载参考下。
  • 链路状态路由协议的实现(CS 542 学期项目,2013 年秋季) 截止日期:中午,11/25/2013。 概述链路状态路由协议是路由协议的主要类别。 它由网络中的每个路由器(交换节点)执行。 链路状态路由的基本概念是每个...
  • 内部路由器:当一个OSPF路由器上所有直联的链路都处于同一个区域时,我们称这种路由器...随着OSPF路由器种类概念的引入,OSPF路由协议又对其链路状态广播数据包(LSA)作出了分类。OSPF将链路状态广播数据包共分成5类。
  • 智能家居WSN链路状态感知算法.pdf
  • SDN中基于链路状态感知的路由优化模型
  • HC110110017 链路状态路由协议-OSPF
  • 基于网络节点贡献度的链路预测算法研究 中文摘要 随着网络信息技术的迅猛发展生活中涌现出大量的复杂系统网络科学研 究得到了快速的发展链路预测作为复杂网络研究的重要分支之一是用来预测 网络中没有连边的节点间...
  • OSPF简介,介绍了关于经常在企业里面用到的链路状态路由协议。
  • OSPF之链路状态数据库LSDB

    千次阅读 2022-02-04 14:29:49
    OSPF链路状态数据库 原理概述: OSPF是一种基于链路状态的动态路由协议,每台 OSPF 路由器都会生成相关的LSA,并将这些LSA通告出去。路由器收到LSA后,会将它们存放在链路状态数据库LSDB中。 LSA有多种不同的...

    OSPF链路状态数据库

    原理概述:

    OSPF是一种基于链路状态的动态路由协议,每台 OSPF 路由器都会生成相关的LSA,并将这些LSA通告出去。路由器收到LSA后,会将它们存放在链路状态数据库LSDB中。

    LSA有多种不同的类型,不同类型的LSA的功能和作用是不同的,下面介绍几种常见的LSA:

    Type-1 LSA(Router LSA):每台路由器都会产生,用来描述路由器的直连链路状态和开销值。Type-1 LSA只能在所属区域内部泛洪,不能泛洪到其他区域。

    Type-2 LSA(Network LSA):它是DR产生的,主要用来描述该DR所在网段的网络掩码以及该网段内有那些路由器。Type-2 LSA只能在所属区域内部泛洪,不能泛洪到其他区域。

    Type-3 LSA(Network Summary LSA);它是由ABR(Area Boundary Router)产生的,ABR路由器将所连区域的Type-1和Type-2 LSA 转换为 Type-3 LSA,用来描述区域间的路由信息。Type-3 LSA可以泛洪到整个AS(Autonomous System,自治域)内部,但不能泛洪到Totally Stub区域和Totally NSSA(Not-So-Stubby Area)区域。

    Type-4 LSA(ASBR Summary LSA);它是由ASBR(Autonomous System Boundary Router)所在区域的ABR产生的,用来描述到ASBR的路由。Type-4LSA 可以泛洪到整个AS内部,但不能泛洪到Stub区域、Totally Stub区域、NSSA区域和Totally NSSA区域中。

    Type-5 LSA(AS External LSA):它是由ASBR产生的,用来描述到AS外部网络的路由。Type-5 LSA可以泛洪到整个AS内部,但不能泛洪到Stub区域、Totally Stub区域、NSSA区域和Totally NSSA区域中。

    Type-6 LSA(Group Membership LSA):在MOSPF中用于标识组播组成员使用的用户组播路由。

    Type-7 LSA(NSSA LSA):它是由NSSA区域或Totally NSSA区域的NSSA ASBR产生的,用来描述到AS外部的路由。Type-7 LSA只能出现在所属NSSA区域或Totally NSSA区域内部。

    实验目的:

    理解OSPF中不同类型的LSA的作用

    熟悉OSPF中不同类型的LSA的泛洪范围

    熟悉LSA中重要字段的含义

    实验拓扑:

     

    1:首先基础配置

    R1:
    
    #
    
    interface GigabitEthernet0/0/0
    
     ip address 10.0.12.1 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/1
    
    #
    
    interface GigabitEthernet0/0/2
    
    #
    
    interface NULL0
    
    #
    
    interface LoopBack0
    
     ip address 10.0.1.1 255.255.255.255
    
    #
    
    interface LoopBack1
    
     ip address 192.168.1.1 255.255.255.0
    
    R2:
    
    #
    
    interface GigabitEthernet0/0/0
    
     ip address 10.0.12.2 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/1
    
     ip address 10.0.235.2 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/2
    
    #
    
    interface NULL0
    
    #
    
    interface LoopBack0
    
     ip address 10.0.2.2 255.255.255.255
    
    R3:
    
    #
    
    interface GigabitEthernet0/0/0
    
     ip address 10.0.34.3 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/1
    
     ip address 10.0.235.3 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/2
    
    #
    
    interface NULL0
    
    #
    
    interface LoopBack0
    
     ip address 10.0.3.3 255.255.255.255  
    
    R4:
    
    #
    
    interface GigabitEthernet0/0/0
    
     ip address 10.0.34.4 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/1
    
    #
    
    interface GigabitEthernet0/0/2
    
    #
    
    interface NULL0
    
    #
    
    interface LoopBack0
    
     ip address 10.0.4.4 255.255.255.255
    
    #
    
    interface LoopBack1
    
     ip address 172.16.1.1 255.255.255.0
    
    R5:
    
    #
    
    interface GigabitEthernet0/0/0
    
     ip address 10.0.235.5 255.255.255.0
    
    #
    
    interface GigabitEthernet0/0/1
    
    #
    
    interface GigabitEthernet0/0/2
    
    #
    
    interface NULL0
    
    #
    
    interface LoopBack0
    
     ip address 10.0.5.5 255.255.255.255
    
    
    
    2:配置OSPF路由协议
    
    R1:
    
    #
    
    ospf 1
    
     area 0.0.0.1
    
      network 10.0.1.1 0.0.0.0
    
      network 10.0.12.0 0.0.0.255
    
      network 192.168.1.0 0.0.0.255
    
    R2:
    
    #
    
    ospf 1
    
     area 0.0.0.0
    
      network 10.0.235.0 0.0.0.255
    
     area 0.0.0.1
    
      network 10.0.2.2 0.0.0.0
    
      network 10.0.12.0 0.0.0.255
    
    R3:
    
    #
    
    ospf 1
    
     area 0.0.0.0
    
      network 10.0.235.0 0.0.0.255
    
     area 0.0.0.2
    
      network 10.0.3.3 0.0.0.0
    
      network 10.0.34.0 0.0.0.255
    
    R4:
    
    #
    
    ospf 1
    
     area 0.0.0.2
    
      network 10.0.4.4 0.0.0.0
    
      network 10.0.34.0 0.0.0.255
    
      network 172.16.1.0 0.0.0.255
    
    R5:
    
    #
    
    ospf 1
    
     area 0.0.0.0
    
      network 10.0.5.5 0.0.0.0
    
      network 10.0.235.0 0.0.0.255

    在R3上查看OSPF的DR与BDR的选举情况!

    可以看到,在R2、R3、R5组成的广播网络中,目前R5是DR,R2是BDR。接下来查看每台路由器的路由表;

    R1:

    R2:

    R3:

    R4:

    R5:

     

    可以看到,每台路由器都已获得了非直连网络的路由条目。接下来使用ping命令检测连通性;

      

    可以看到,各个网段之间的通信是正常的

    区域1是普通区域,区域2是NSSA区域,区域1的R1和区域2的R4都需要引入Loopback 1接口所连接的外部网络路由。在R1和R4上使用Route-Policy精确匹配Loopback 1接口的直连路由引入并引入OSPF进程。

    R1:
    
    #
    
    ospf 1
    
     import-route direct route-policy 10
    
     area 0.0.0.1
    
      network 10.0.1.1 0.0.0.0
    
      network 10.0.12.0 0.0.0.255
    
      network 192.168.1.0 0.0.0.255
    
    #
    
    route-policy 10 permit node 1
    
     if-match acl 2000
    
    R4:
    
    #
    
    ospf 1
    
     description mcu
    
     import-route direct route-policy 10
    
     area 0.0.0.2
    
      network 10.0.4.4 0.0.0.0
    
      network 10.0.34.0 0.0.0.255
    
      network 172.16.1.0 0.0.0.255
    
    #
    
    route-policy 10 permit node 1
    
     if-match acl 2000

    配置完成后,在R5上查看由R1和R4引入的两条路由

     

    可以看到,在R5的路由表中,这两条路由都显示为O_ASE,且优先级与开销也都相同,不同之处是这两条路由的下一跳,因为它们是由不同的路由器发送给R5的。

    3:查看Type-1 LSA,Type-2 LSA,Type-3 LSA

    在区域0的R5上查看LSDB。

     

    可以看到,R5的LSDB中共有5种LSA,它们分别是Router LSA(或称Type-1 LSA)。

    Network LSA(或称Type-2 LSA)、Sum-Net LSA(或称Type-3 LSA,Network Summary LSA)、Sum-Asbr LSA(或称Type-4 LSA、ASBR Summary LSA)和External LSA(或称Type-5 LSA,AS External LSA)。

    在R5上查看Router-ID为10.0.2.2产生的Router LSA的详细信息

     

    下面解释一下显示信息中的部分参数的含义:

    Type:显示信息中,Type表示了LSA的类型,这里表示的是Router LSA。不同类型的LSA的作用和泛洪区域范围是不相同的。Router LSA描述了路由器的直连链路或接口,泛洪范围为所在区域的内部,以使本区域的其他路由器了解其直连链路或接口的状态信息;

    Ls id:对于Router LSA,Ls id就是产生该Router LSA的路由器的Router-ID。

    Adv rtr:Adv rtr描述了LSA是由哪台路由器产生的。对于Router LSA来讲,Adv rtr就是产生该Router LSA的路由器的Router-ID。

    Seq#:这一条LSA都会维护一个Seq#(序列号),产生这条LSA的路由器默认会过30s的周期泛洪这条LSA,每次泛洪时,序列号就加1,LSA的序列号越大,表明这条LSA越新。

    Chksum:chksum(校验和)用来校验LSA的完整性。所有的LSA都会保存在路由器的LSDB中,每5min会计算一次。如果路由器收到了同一条LSA,且序列号相同,则会比较它们的校验和,校验和越大就被认为相应的LSA越新。

    Ls age:Ls age是指LSA的老化时间,用来表示LSA已经存活了多长时间,最大值为3600s。当一台路由器产生一条LSA的时候,路由器会将LSA的老化时间设置为0。LSA在产生之后,无论是停留在路由器的LSDB内,还是在传递过程之中,老化时间都会不断增加,为了防止因LSA的过期而造成路由回馈,路由器会每隔30min泛洪自己产生的LSA。若序列号与校验和的比较都不能确定出最新的LSA时,则会比较老化时间。

    在LSDB中,如果老化时间相差大于15min以上,则Ls age的值越小,说明LSA越新,如果相差15min内,则认为两条LSA是一样的。

    在上面的显示信息中,Link count以上的参数信息通常被称为LSA头部信息,Link count及以下部分为具体的链路描述信息,Link count标识了这条LSA描述的链路信息的数量。对于P-2-P链路类型,Link ID是指链路上邻居接口的IP地址;对于TranNet链路类型,Link ID是指DR接口的IP地址。Data是指自身接口的IP地址,Link Type是指接口的链路类型,Metric是指路由器自己到达这条链路的Cost值,需要说明的是,OSPF协议会把Broadcast和NBMA这两种具有多路访问能力的网络都认为是TransNet网络。

    从上得知,R2的Router LSA描述了自己连接到了某个TransNet网络,网络的DR接口的IP地址为10.0.235.5(R5),自己使用10.0.235.2连接到该网络中,且到达这个网络的Cost值为1。

    Network LSA是由DR产生的,它的主要作用是描述TransNet网络的掩码信息和连接到TransNet网络的路由的路由器的信息。在多路访问网络中,每台路由器都产生Network LSA是没有必要的,因为这会导致Network LSA的重复。

    R5是TransNet网络的DR,在R5上查看它产生和发送的Network LSA的详细信息。

     

     

     

    可以看到,这条Network LSA说明了TransNet网络的掩码为255.255.255.0,连接到这个TransNet网络的路由器有10.0.5.5(R5)、10.0.3.3(R3)。Network LSA中没有携带路径的开销,原因是Router LSA已经描述了自己到TransNet网络的Cost值。

    在R2、R3、R5上查看区域0的LSDB。

     

    可以发现,R2、R3、R5的LSDB中区域0的Router LSA和Network LSA是完全一样的。

    Router LSA和Network LSA可以完全描述本区域的网络拓扑,但这些LSA不能泛洪到其他区域,当OSPF网络包含多个区域时,通过Router LSA和Network LSA就无法进行区域间路由的计算,区域间路由到达计算需要利用Sum-Net LSA来实现,ABR路由器会将自己相连的区域的Router  LSA和Network LSA转换为Sum-Net LSA,然后泛洪到其他区域。

    R2同时连接了区域0和区域1,所以是一台ABR路由器。查看R2的LSDB。

    可以看到,R2的区域0中有一条LinkState ID为10.0.12.0 的Sum-Net LSA,它的AdvRouter为10.0.2.2。网段10.0.12.0/24本是属于区域1的网络,现在被ABR路由器R2转换为Sum-Net LSA并泛洪到了区域0中。10.0.235.0/24本是属于区域0的网络,现在被ABR路由器R2转换为Sum-Net LSA并泛洪到了区域1中,实际上,Sum-Net LSA是ABR利用自己相连的区域的Router-LSA和Network-LSA来计算得到的路由信息的。

    在R2上查看LinkState ID为10.0.12.1的这条Sum-Net LSA的详细信息。

    可以看到,这条LSA的Type为Sum-Net,Ls id表明了目的网络地址为10.0.12.0,Net mask表明了目的网络的掩码为255.255.255.0,metric表明了ABR路由器R2去往目的网络的Cost值为1。

    在R5上查看LSDB,并查看路由表中关于10.0.12.0/24的路由信息

      

    可以看到,R5的LSDB中存在10.0.12.0这条Sum-Net LSA,R5的路由表中关于10.0.12.0/24这条路由信息表明R5在去往10.0.12.0/24的Cost为2,R5通过这条Sum-Net LSA得知网络中存在10.0.12.0/24网段,这个网段的AdvRouter为10.0.2.2(R2),R2有已到达10.0.12.0/24的Cost为1,R5和R2同属于区域0,所以R5可以通过Router LSA和Network LSA计算出自己到R2的Cost为1,因此,R5可以计算出自己到10.0.12.0/24的Cost值为1+1=2。

    区域间的路由是根据Sum-Net LSA并结合Router LSA及Network-LSA计算出来的,对于某个区域的一台OSPF路由器来说,它无需了解其他区域的链路状态信息,但可以通过Sum-Net LSA并结合Router-LSA及Network-LSA及计算出区域间路由,计算区域间路由时,采用的不再是链路状态算法,而是距离矢量算法。

    在R2上查看LinkState ID为10.0.34.0/24这条LSA的信息。

     

    可以看到,10.0.34.0/24是属于区域2的网络,ABR路由器R3将关于10.0.34.0/24的路由信息以Sum-Net LSA的方式通告进了区域0,Cost为1,然后,ABR路由器R2又继续将此信息以Sum-Net LSA的方式通告进了区域0。

    对于ABR来说,如果在自己相连的某个区域的LSDB中存在某条Sum-Net LSA,并且这Sum-Net LSA的AdvRouter不是自己的Router-ID时,就会将这条Sum-Net LSA的AdvRouter修改为自己的Router-ID,并重新计算自己到达这条Sum-Net LSA的Cost值,然后将泛洪到与自己相连的其他区域中。

    4:查看Type-4 LSA和Type-5 LSA

    路由器可以通过Router LSA和Network LSA计算区域内的路由,可以通过Sum-Net LSA并结合Router LSA和Network LSA计算区域间的路由,可以通过Sum-Asbr LSA和External LSA计算AS外部的路由。

    R1的Loopback 1是外部路由,被ASBR路由器R1引入到了OSPF网络中,查看R1的LSDB

    可以看到,R1的LSDB中存在一条Type为External,LinkState ID为192.168.1.0,AdvRouter为10.0.1.1的LSA,在R1上查看这条LSA的其他信息。

    可以看到,这条LSA的Type是External,AdvRouter为10.0.1.1(R1),这条LSA实际上是一条目的网络为192.168.1.0/24的AS外部路由,显示信息中的E Type(External Type)的值为2。

    External LSA可以在整个AS内部泛洪(但不能泛洪到Stub区域,Totally Stub区域,NSSA区域和Totally NSSA区域中),在泛洪过程中其各个参数不会改变,查看R2,R3,R4,R5的LSDB中是否也存在这条LSA。

    在R5上使用display ospf abr-asbr命令查看到达ABR和ASBR的Cost值

     

    可以看到,从R5到达ABR路由的R2的Cost值为1,从R5到达ASBR路由器R1的Cost值为2,由此可见,R5其实是通过Router LSA和Network LSA先计算出到达ABR路由器R2的Cost值,然后加上Sum-Asbr LSA所表示的从ABR的路由器R2到达ASBR路由器R1的Cost值

    [R1]ospf
    
    [R1-ospf-1]un im
    
    [R1-ospf-1]un import-route dir
    
    [R1-ospf-1]un import-route direct

    在R5上查看LSDB

    5:查看Type-7 LSA

    NSSA区域是不允许External LSA存在的,但NSSA区域允许通过import-route命令引入外部路由,那么如何来描述在NSSA区域中的AS外部路由呢?NSSA区域引入的外部路由不能以External LSA的形式出现,取而代之的是使用NSSA LSA来描述NSSA区域中的AS外部路由,且NSSA LSA只能出现在NSSA区域中。NSSA LSA由NSSA区域的NSSA ASBR产生。

    R4为NSSA区域的ASBR,查看R4的LSDB

    可以看到,R4为外部路由172.16.1.0产生了相应的NSSA LSA。在R4上查看这条LSA的详细信息;

    可以注意到,NSSA LSA的参数信息基本上和External LSA相同。

    NSSA LSA是特殊类型的LSA,只会出现在NSSA区域中,不能泛洪到其他任何区域,那么其他区域的路由器又是如何计算去往NSSA LSA所表示的外部网络的路由呢?

    原来,NSSA区域的ABR会将NSSA LSA转换为External LSA,并泛洪到其他区域。

    R3为NSSA区域的ABR路由器,在R3上查看LSDB信息。

    可以看到,由10.0.4.4产生的NSSA LSA被R3转换成了 External LSA,并泛洪到其他区域。

    备注:如有错误,请谅解!

    此文章为本人学习笔记,仅供参考!如有重复!!!请联系本人!

    展开全文
  • 链路状态路由算法

    千次阅读 2021-08-02 15:18:21
    一、路由的基本概念 ...路由算法的关键:在给定的一组路由器以及连接路由器的链路中,找到一条从源路由器到目的路由器的”好“路径。 怎样才算好路径呢?就是具有”最低费用“的路径。可以是最小的链路延时,经过的

    一、路由的基本概念

    (1)默认路由器:与主机直接相连的路由器,又叫第一路由器。每当主机发送一个分组时,都先传送给它的默认路由器。
    源主机的默认路由器被成为源路由器;目的主机的默认路由器被称为目的路由器;从源主机到目的主机的选路归结为从源路由器到目的路由器的选择。
    (2)路由算法:是确定一个分组从源路由器到目的路由器所经路径的算法。
    路由算法的关键:在给定的一组路由器以及连接路由器的链路中,找到一条从源路由器到目的路由器的”好“路径。
    怎样才算好路径呢?就是具有”最低费用“的路径。可以是最小的链路延时,经过的最小路由器数目等。

    二、网络的抽象图模型

    对于一个由链路及路由器组成的网络,可以用节点图来表示网络的结构。
    在这里插入图片描述
    上图G=(N,E)表示N个节点和E条边的集合,每条边是来自N的一对节点。
    节点:表示路由器即做出分组转发判决的点。
    如上图的u、v、w、x、y、z。
    边:连接节点的线段,表示路由器之间的物理链路。如图中的(u,v)、(u,x)等。
    费用(cost)可以表示对应链路的物理长度、或链路速度、或与链路相关的费用。
    c(x,y)表示节点x和节点y之间边的费用,即从节点x到节点y的链路费用。
    (1)若节点x与节点y直接相连,也就是x和y是邻居。 则c(x,y)=链路费用
    如c(u,v)=2,节点u与节点v互为邻居。
    (2)若节点x与节点y不直接相连,则
    c(x,y)=无穷
    如c(u,y)=无穷,c(u,z)=无穷。

    三、路由算法的分类

    1、根据节点是否需要全局的拓扑信息分

    (1)全局路由算法:所有路由器拥有完整的网络拓扑信息和链路费用信息。
    链路状态路由算法属于全局路由算法,它必须知道网络中每条链路的费用。
    (2)分布式路由算法:以迭代的、分布式的方式计算最低费用路径。
    节点只有与其直接相连链路的费用信息:不需拥有所有网络链路费用的完整信息。
    通过迭代计算,并于相邻节点交换信息。
    逐步计算出到达某目的节点或一组目的节点的最低费用路径。
    距离向量路由算法属于分布式路由算法:每个节点维护到网络中所有其它节点的费用的估计向量。

    2、根据路径是否变化分类

    (1)静态路由算法:路由确定后基本不再变化。只有人工干预调整时,可能有一些变化。
    (2)动态路由算法:当网络的流量负载或拓扑发生变化时,路径可能发生改变;可以周期性地或直接地响应拓扑或链路费用地变化;易受选路循环、路由振荡之类问题的影响。

    四、链路状态选路算法

    本篇文章主要讲链路状态选路算法。
    链路状态选路算法主要是通过Dijkstra最低费用路径算法。学过数据结构的朋友们对Dijkstra应该都不陌生。
    在此算法中每个节点都需要知道网络拓扑以及每条链路的费用信息;然后计算任意一个节点到所有其它节点的最低费用路径;通过K次迭代后可以知道到达K个目的节点的最低费用路径。
    基本思想:以源节点为起点,每次找出一个到源节点的费用最低的节点,直到把所有的目的节点都找到为止。

    1、术语定义

    (1)c(x,y):表示从节点x到节点y的链路费用,若c(x,y)=无穷则表示不是直接邻居。
    (2)D(v):表示从源节点到目的节点v的当前路径的费用。
    (3)p(v):表示从源节点到目的节点v的路径上的前驱节点。
    (4)N’:表示已经找到最低费用路径的节点集合。

    2、算法描述

    Dijkstra伪代码如下:
    在这里插入图片描述
    (1)初始化(第一行到第6行):
    N’={源节点u};
    对所有不在N’中的节点v,标出其D(v)值;
    若节点v与源节点u直接相连,则D(v)=c(u,v);
    若节点v不与源节点u直接相连,则D(v)=无穷。
    (2)找出一个到源节点的费用最低的节点w,并以此更新其它点D(v)值:
    从不在N‘中的节点中找出一个D(w)值最小的节点w,并将w加入到N’中。(对应第9到第10行代码);
    对不在N’中,但与节点w是邻居的节点v,用新的值更新D(v)=min[D(v),D(w)+c(w,v)],公式的含义为将节点v原值与节点v现经节点w到源节点的值比较,取小值。
    (3)重复步骤(2),直到所有的网络节点都在N’中为止。
    在这里插入图片描述
    例如计算上图从u到所有可能目的节点的最低费用路径。
    计算过程如表,其中的每一行表示一个迭代结束时的算法变量值。
    在这里插入图片描述
    最后根据计算结果构建出从源节点到所有目的节点的路径:
    (1)对于每个节点,都得到从源节点沿着它的最低费用路径的前驱节点;
    (2)每个前驱节点,又可得到它的前驱节点;以此继续,可以得到所有目的节点的完整路径。
    如节点z的前驱节点依次为:z->y->x->u
    (3)得出从源节点u到节点z的最低费用路径为:uxyz,费用为4。
    在这里插入图片描述

    3、构建最低费用路径树

    (1)根据目的节点找出顺序和其费用以及前驱节点,可以画出源节点u到所有目的节点的最低费用路径树。
    (2)根据得到的所有目的节点的完整路径,或最低费用路径树,可以生成源节点的转发表。
    转发表:存放从源节点到每个目的节点的最低费用路径上的下一跳节点。即指出对于发往某个目的节点的分组,从该节点发出后的下一节点。
    最低费用路径树以及转发表如下图所示:
    在这里插入图片描述
    我们看到上述转发表有一部分的下一跳是相同的,因此可以进行合并,如下图
    在这里插入图片描述
    默认路由*:表示所有具有相同下一跳的表项。即将下一跳相同的项合并为一项,目的节点用*表示。优先级最低,转发分组时,当找不到对应表项时,才使用默认路由。
    Dijkstra算法复杂度为O(n 2 ^2 2)。

    展开全文
  • 链路状态路由协议

    千次阅读 2022-03-23 09:34:30
    与距离矢量路由协议不同,链路状态路由协议通告的的是链路状态而不是路由表。运行链路状态路由协议的路由器之间首先会建立一个协议的邻居关系,然后彼此之间开始交互LSA(Link State Advertisement,链路状态通告) ...

    一、LSA泛洪

    与距离矢量路由协议不同,链路状态路由协议通告的的是链路状态而不是路由表。运行链路状态路由协议的路由器之间首先会建立一个协议的邻居关系,然后彼此之间开始交互LSALink State Advertisement,链路状态通告)

    每个路由器都会在启动路由协议之后,生成自己的链路状态信息,此时不再通告路由信息,而是LSA。LSA描述了路由器接口的状态信息,例如接口的开销、连接的对象、带宽、对端ip、网络类型等。路由器之间都会交互·这种链路状态信息,所有路由器最后出现一个区域内完全相同的链路状态数据库,区域内部的每个路由器都有其他路由器的LSA,此时大家都有全部的LSA,LSA存放在数据库(LSDB),想当于每个路由器都知道别的链路情况

    二、LSDB

    每台路由器都会产生LSAs,路由器将接收到的LSAs放入自己的LSDBLink State DataBase,链路状态数据库)。路由器通过LSDB,掌握了全网的拓扑。

    三、SPF算法

    每台路由器基于LSDB,使用SPFShortest Path First,最短路径优先)算法进行计算。每台路由器都计算出一棵以自己为根的、无环的、拥有最短路径的“树”。有了这棵“树”,路由器就已经知道了到达网络各个角落的优选路径。COST值的计算方法:参考带宽(100)/实际带宽

    四、路由表的生成

    五、邻接关系建立流程

    hello包每隔十秒发送一次。

    六、OSPF协议报文类型

    ospf通过hello报文来发现和维持邻居关系,通过DD、LSR、LSU、LSACK报文来同步LSDB。

    七、OSPF的基础配置命令

    解释一下反掩码的作用: 

    net 192.168.1.254 0.0.0.0               精确到具体的192.168.1.254的接口开启ospf

    net 10.0.0.0 0.255.255.255             10.0.0.0地址范围内的所有接口开启ospf

    net 10.1.23.0 0.0.0.255                    10.1.23.0地址范围内的所有接口都开启ospf

    解释一下network的作用

    1.被选中的接口开启ospf功能

    2.对外开启hello报文

    3.生成该接口的路由信息

    OSPF配置命令(二)

    解释:

    cost值:单向接口的cost值加起来之和

    带宽参考值:默认是100,但是可以自行修改,建议更改的话就全部的ospf路由器都更改

    选举dr:优先值越大的就会选举成dr,而且不会抢占,BR和BDR之间会建立full状态,DRother之间会建立2Way状态

    展开全文
  • 基于链路状态快速感知的环路避免技术,阳碧云,,随着计算机网络通信技术的发展,人们对于通信质量的要求越来越高。但是网络的生存能力面临着各种威胁因素,增强网络在自然灾害、
  • 计算机网络网络层之链路状态路由算法 网络抽象:图 链路状态路由算法 Djikstra算法 所有结点(路由器)掌握网络拓扑和链路费用 通过“链路状态广播” 所有结点拥有相同信息 计算从一个结点(“源”)达到所有...
  • 1、DV(distance-vector)距离矢量协议 相邻路由器通知路由信息(成品) (链路状态通知的是链路状态+拓扑信息——相当于原材料) 逐跳传递路由信息,路由收敛慢 没有充足信息描述拓扑 距离矢量协议的优点: 开销小 ...
  • 三十五、OSPF协议的链路状态算法

    千次阅读 2021-12-28 10:53:16
    文章目录1、OSPF协议2、链路状态路由算法3、OSPF的区域4、OSPF的分组5、OSPF的其他特点THE END 1、OSPF协议 \qquad开放最短路径优先OSPF协议:“开放”标明OSPF协议不是受某一家厂商控制,而是公开发表的;“最短...
  • 千兆冗余以太网链路状态检测技术
  • 链路状态协议——OSPF(一)

    千次阅读 2019-10-14 19:11:54
    链路状态协议——OSPF(一) 链路状态协议和距离矢量协议有着很大的区别,ok,我们来看看二者的特点 链路状态协议(又最短路径优先协议): 1,每台路由器了解其自身的链路(即与其直连的网络) 2,每台路由器负责"问候...
  • 计算机网络:链路状态路由算法

    千次阅读 2021-05-21 10:17:24
    链路状态路由算法(LS算法) DV算法是路径矢量算法(distance Vector),现在我们着重了解一下链路状态算法的相关描述。 链路状态路由算法 link state routing algorithm 俗称LS算法。 工作原理: -每个路由器将...
  • OSPF协议及链路状态算法(详解)

    千次阅读 2020-06-05 12:56:04
    OSPF最主要的特征就是使用分布式的链路状态协议。 OSPF的特点: 和谁交换? 使用洪泛法向自治系统内所有路由器发送信息,即路由器通过输出端口向所有相邻的路由器发送信息,而每一个相邻路由器又再次将此信息发往...
  • OSPF是指开放最短路径优先协议,基于链路状态算法。 D-V 算法中,每个节点只需要维护自身的距离向量,且只需要与自己相连的链路的状态,需要的存储空间小;而L- S 算法中每个节点都需要知道所有链路的状态,需要的...
  • OSPF的三张表(链路状态公告)

    千次阅读 2020-11-16 17:23:55
    OSPF(Open Shortest Path First,开放最短路径优先)是IETF(Internet Engineering Task Force,互联网工程任务组)组织开发的一个基于链路状态的自治系统内部网关协议。目前针对IPv4协议使用的是OSPF Version 2。...
  • 一、路由选择协议分类、 二、OSPF 协议 简介、 三、链路状态路由算法、 四、OSPF 区域、 五、OSPF 特点、
  • CCNA链路状态配置

    2014-06-17 10:48:23
    针对于学习CCNA和CCNP的同学,初级的网络配置的链路状态配置
  • 链路状态算法 最短路径示例 1 2 3 4 5 6 1 2 5 4 1 4 1 2 3 最短路径示例 1 2 3 4 5 6 1 2 5 4 1 4 1 2 3 路由器的工作 监测所有相邻路由器的状态 周期性地广播链路状态的信息 获得链路状态 路由器周期性地发送短...
  • 优化链路状态路由协议 (OLSR) 通过带宽的多路径分配进行扩展,这被称为多路径优化链路状态路由协议 (MP-OLSR)。 OLSR具有主动性,更稳定,更容易适应,广泛应用于密集复杂网络流量的通信。 MP-OLSR 采用多路径 ...
  • 然后将这两个概念整合到优化的链路状态路由(OLSR)协议中;最后在OLSR协议中使用一种稳定性函数作为主路径选择标准来选取稳定且可持续的多点继电器节点和拓扑。提出的机制显著减少了MPR的重计算和路由表重计算过程...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 155,579
精华内容 62,231
关键字:

链路状态