路由协议具体算法_按照路由算法,可以将动态路由协议分为 - CSDN
  • 路由算法入门

    2017-01-13 00:02:11
    路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。 路由器使用路由算法来找到到达目的地的最佳链路。 网络可以抽象成图来理解 路由算法分类: 静态路由是指由用户或网络管理员手工配置的路由...

    路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。
    路由器使用路由算法来找到到达目的地的最佳链路。
    这里写图片描述
    网络可以抽象成来理解
    这里写图片描述
    这里写图片描述
    路由算法分类:
    静态路由是指由用户或网络管理员手工配置的路由信息。
    动态路由是指路由器能够自动地建立自己的路由表,并且能够根据实际情况的变化适时地进行调整。
    动态路由通常使用以下两种形式的路由协定来达成:距离向量算法(RIP)与链路状态算法(OSPF)。所有路由算法几乎都可以分类到这两种算法中。
    这里写图片描述
    链路状态算法:
    在连线状态算法中,每个节点拥有网络的图谱(一个图)。每个节点将自己可以连接到的其他节点资讯传送到网络上所有的节点,而其他节点接着各自将这个资讯加入到图谱中。每个路由器即可根据这个图谱来决定从自己到其它节点的最佳路径。
    完成这个动作的算法——Dijkstra算法——建立另一种数据结构——树。节点产生的树将自己视为根节点,且最后这棵树将会包含了网络中所有其他的节点。一开始,此树只有根节点(节点自己)。接着在树中已有的节点的邻居节点且不存在树中的节点集合中,选取一个成本最低的节点加入此树,直到所有节点都存入树中为止。
    这棵树即用来建立路由表、提供最佳的“下一个节点”等,让节点能跟网络中其它节点通讯。
    这里写图片描述

    这里写图片描述
    举个例子,理下思路:(感觉图例比文字阐述更容易理解)
    这里写图片描述
    再举个栗子,加深记忆
    这里写图片描述
    这里写图片描述
    这里写图片描述
    假设在该网络中链路费用等同于链路上的负载,初始状态为:
    节点B和D都发送到目的地A的一个单位的流量,且都选择它们与A直接相连的链路。
    C有目的地为A的流量e,并走通过B到达A的链路。
    此时非0费用的链路有:

    • B,D之间的链路费用为1+e
    • C,B之间的链路费用为e
    • D,C之间的链路费用为1

    当LS运行时,则
    节点B发现,它与A直接相连的链路的费用是1+e,而C->D->A这条路径的总费用是1,因而它选择走该链路
    节点C发现,它走B->A的费用是1+e,而走D->A的费用是1,因而选择D->A的路径。
    节点D的选路不变
    此时非0费用的链路有:

    • B,C之间的链路费用为e
    • C,D之间的链路费用为1+e
    • D,A之间的链路费用为2+e

    当LS运行时,则
    节点B发现,它与A直接相连的链路的费用是0,而C->D->A这条路径的总费用是2+e,因而它选择走与A直接相连的路径
    节点C发现,它走B->A的费用是0,而走D->A的费用是2+e,因而选择走B->A
    节点D发现,它走C->B->A的费用为0,而走直接连接A的链路的费用是2+e,因而它选择C->B->A的路径
    此时非0费用的链路有:

    • D,C之间的链路费用为e
    • C,B之间的链路费用为1+e
    • B,A之间的链路费用为2+e

    LS算法继续运行,就会不断震荡,解决方案是确保并非所有的路由器都在同一时刻运行LS算法。做法是对于每台路由器,引入随机的延时链路状态更新。
    距离向量算法:
    距离向量算法使用Bellman-Ford算法。对于每一条网络上节点间的路径,算法指定一个“成本”给它们。节点会选择一条总成本(经过路径的所有成本总和)最低的路径,用来把资料从节点甲送到节点乙。
    这里写图片描述

    这里写图片描述

    这里写图片描述
    这里写图片描述
    这里写图片描述
    距离向量DV:链路费用变化
    这里写图片描述
    距离向量DV:无穷计数问题
    这里写图片描述
    还是X、Y、Z三个节点。的距离向量为:d(X) = 5, d(Y) = 1, d(Z) = 0。于是Y在更新向量时发现,咦,Z到X的距离只有5诶,那可以先到Z再到X,于是Y的距离向量更新为:d(x) = 5 + 1 = 6, d(Y) = 0, d(z) = 1。我们可以发现,这个逻辑显然是错误的,因为Z到X的距离为5的前提是要经过Y,但Y更新后的路径又要经过Z,这就形成了一个选路环路 (routing-loop)问题。因为Y的距离向量更新了(虽然是错误的),但它还是向Z发送了更新报文。Z收到更新报文后,比较了下邻居们到X的距 离,发现经过Y的路径距离为1 + 6 = 7,小于直接到X的距离,于是Z也更新的自己的距离向量,然后又将更新后的距离向量发给Y。Y收到后又更新向量为8,然后再发给Z。。。这样循环往复,更 新报文在Y和Z之间传来传去,直到第44次迭代后,Z算出它经由Y的路径费用大于50为止。此时,Z最终确定到X的最短路径费用是直接到达X的费用50, 而Y也得到了最短路径是经Z到X的费用51。
    可以看出,虽然最后还是得到了正确的信息(最后的50和51是正确的!),但坏消息的传播与好消息相比实在是慢太多了!而且,如果X和Y之间的费用为10000,Z和X的费用是9999时,就会出现计数到无穷(count-to-infinity)的问题!
    毒性逆转方法(The Reverse-Poison(Split-horizon) Hack)
    这里写图片描述
    当涉及3个或更多节点(而不仅仅是两个直接相连的邻居节点)的环路将不能被毒性逆转技术检测到。
    这里写图片描述


    层次路由
    这里写图片描述
    这里写图片描述
    这里写图片描述
    自治系统间(lnter-AS)路由任务
    这里写图片描述
    这里写图片描述
    在多AS间选择:
    这里写图片描述
    这里写图片描述

    展开全文
  • 路由器原理和路由协议算法详解 1、网络互连 把自己的网络同其它的网络互连起来,从网络中获取更多的信息和向网络发布自己的消息,是网络互连的最主要的动力。网络的互连有多种方式,其中使用最多的是网桥互连和...
     
    
    路由器原理和路由协议、算法详解
     
    1、网络互连
     
    把自己的网络同其它的网络互连起来,从网络中获取更多的信息和向网络发布自己的消息,是网络互连的最主要的动力。网络的互连有多种方式,其中使用最多的是网桥互连和路由器互连。
     
    1.1 网桥互连的网络
     
    网桥工作在OSI模型中的第二层,即链路层。完成数据帧(frame)的转发,主要目的是在连接的网络间提供透明的通信。网桥的转发是依据数据帧中的源地址和目的地址来判断一个帧是否应转发和转发到哪个端口。帧中的地址称为“MAC”地址或“硬件”地址,一般就是网卡所带的地址。
     
    网桥的作用是把两个或多个网络互连起来,提供透明的通信。网络上的设备看不到网桥的存在,设备之间的通信就如同在一个网上一样方便。由于网桥是在数据帧上进行转发的,因此只能连接相同或相似的网络(相同或相似结构的数据帧),如以太网之间、以太网与令牌环(token ring)之间的互连,对于不同类型的网络(数据帧结构不同),如以太网与X.25之间,网桥就无能为力了。
     
    网桥扩大了网络的规模,提高了网络的性能,给网络应用带来了方便,在以前的网络中,网桥的应用较为广泛。但网桥互连也带来了不少问题:一个是广播风暴,网桥不阻挡网络中广播消息,当网络的规模较大时(几个网桥,多个以太网段),有可能引起广播风暴(broadcasting storm),导致整个网络全被广播信息充满,直至完全瘫痪。第二个问题是,当与外部网络互连时,网桥会把内部和外部网络合二为一,成为一个网,双方都自动向对方完全开放自己的网络资源。这种互连方式在与外部网络互连时显然是难以接受的。问题的主要根源是网桥只是最大限度地把网络沟通,而不管传送的信息是什么。
     
    1.2 路由器互连网络
     
    路由器互连与网络的协议有关,我们讨论限于TCP/IP网络的情况。
     
    路由器工作在OSI模型中的第三层,即网络层。路由器利用网络层定义的“逻辑”上的网络地址(即IP地址)来区别不同的网络,实现网络的互连和隔离,保持各个网络的独立性。路由器不转发广播消息,而把广播消息限制在各自的网络内部。发送到其他网络的数据茵先被送到路由器,再由路由器转发出去。
     
    IP路由器只转发IP分组,把其余的部分挡在网内(包括广播),从而保持各个网络具有相对的独立性,这样可以组成具有许多网络(子网)互连的大型的网络。由于是在网络层的互连,路由器可方便地连接不同类型的网络,只要网络层运行的是IP协议,通过路由器就可互连起来。
     
    网络中的设备用它们的网络地址(TCP/IP网络中为IP地址)互相通信。IP地址是与硬件地址无关的“逻辑”地址。路由器只根据IP地址来转发数据。IP地址的结构有两部分,一部分定义网络号,另一部分定义网络内的主机号。目前,在Internet网络中采用子网掩码来确定IP地址中网络地址和主机地址。子网掩码与IP地址一样也是32bit,并且两者是一一对应的,并规定,子网掩码中数字为“1”所对应的IP地址中的部分为网络号,为“0”所对应的则为主机号。网络号和主机号合起来,才构成一个完整的IP地址。同一个网络中的主机IP地址,其网络号必须是相同的,这个网络称为IP子网。
     
    通信只能在具有相同网络号的IP地址之间进行,要与其它IP子网的主机进行通信,则必须经过同一网络上的某个路由器或网关(gateway)出去。不同网络号的IP地址不能直接通信,即使它们接在一起,也不能通信。
     
    路由器有多个端口,用于连接多个IP子网。每个端口的IP地址的网络号要求与所连接的IP子网的网络号相同。不同的端口为不同的网络号,对应不同的IP子网,这样才能使各子网中的主机通过自己子网的IP地址把要求出去的IP分组送到路由器上。
     
    2 、路由原理
     
    当IP子网中的一台主机发送IP分组给同一IP子网的另一台主机时,它将直接把IP分组送到网络上,对方就能收到。而要送给不同IP于网上的主机时,它要选择一个能到达目的子网上的路由器,把IP分组送给该路由器,由路由器负责把IP分组送到目的地。如果没有找到这样的路由器,主机就把IP分组送给一个称为“缺省网关(default gateway)”的路由器上。“缺省网关”是每台主机上的一个配置参数,它是接在同一个网络上的某个路由器端口的IP地址。
     
    路由器转发IP分组时,只根据IP分组目的IP地址的网络号部分,选择合适的端口,把IP分组送出去。同主机一样,路由器也要判定端口所接的是否是目的子网,如果是,就直接把分组通过端口送到网络上,否则,也要选择下一个路由器来传送分组。路由器也有它的缺省网关,用来传送不知道往哪儿送的IP分组。这样,通过路由器把知道如何传送的IP分组正确转发出去,不知道的IP分组送给“缺省网关”路由器,这样一级级地传送,IP分组最终将送到目的地,送不到目的地的IP分组则被网络丢弃了。
     
    目前TCP/IP网络,全部是通过路由器互连起来的,Internet就是成千上万个IP子网通过路由器互连起来的国际性网络。这种网络称为以路由器为基础的网络(router based network),形成了以路由器为节点的“网间网”。在“网间网”中,路由器不仅负责对IP分组的转发,还要负责与别的路由器进行联络,共同确定“网间网”的路由选择和维护路由表。
     
    路由动作包括两项基本内容:寻径和转发。寻径即判定到达目的地的最佳路径,由路由选择算法来实现。由于涉及到不同的路由选择协议和路由选择算法,要相对复杂一些。为了判定最佳路径,路由选择算法必须启动并维护包含路由信息的路由表,其中路由信息依赖于所用的路由选择算法而不尽相同。路由选择算法将收集到的不同信息填入路由表中,根据路由表可将目的网络与下一站(nexthop)的关系告诉路由器。路由器间互通信息进行路由更新,更新维护路由表使之正确反映网络的拓扑变化,并由路由器根据量度来决定最佳路径。这就是路由选择协议(routing protocol),例如路由信息协议(RIP)、开放式最短路径优先协议(OSPF)和边界网关协议(BGP)等。
     
    转发即沿寻径好的最佳路径传送信息分组。路由器首先在路由表中查找,判明是否知道如何将分组发送到下一个站点(路由器或主机),如果路由器不知道如何发送分组,通常将该分组丢弃;否则就根据路由表的相应表项将分组发送到下一个站点,如果目的网络直接与路由器相连,路由器就把分组直接送到相应的端口上。这就是路由转发协议(routed protocol)。
     
    路由转发协议和路由选择协议是相互配合又相互独立的概念,前者使用后者维护的路由表,同时后者要利用前者提供的功能来发布路由协议数据分组。下文中提到的路由协议,除非特别说明,都是指路由选择协议,这也是普遍的习惯。
     
    3、 路由协议
     
    典型的路由选择方式有两种:静态路由和动态路由。
     
    静态路由是在路由器中设置的固定的路由表。除非网络管理员干预,否则静态路由不会发生变化。静态路由不能对网络的改变作出反映.
    动态路由是网络中的路由器之间相互通信,传递路由信息,利用收到的路由信息更新路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明发生了网络变化,路由选择软件就会重新计算路由,并发出新的路由更新信息。这些信息通过各个网络,引起各路由器重新启动其路由算法,并更新各自的路由表以动态地反映网络拓扑变化。动态路由适用于网络规模大、网络拓扑复杂的网络。当然,各种动态路由协议会不同程度地占用网络带宽和CPU资源。
     
    静态路由和动态路由有各自的特点和适用范围,因此在网络中动态路由通常作为静态路由的补充。当一个分组在路由器中进行寻径时,路由器首先查找静态路由,如果查到则根据相应的静态路由转发分组;否则再查找动态路由。
     
    根据是否在一个自治域内部使用,动态路由协议分为内部网关协议(IGP)和外部网关协议(EGP)。这里的自治域指一个具有统一管理机构、统一路由策略的网络。自治域内部采用的路由选择协议称为内部网关协议,常用的有RIP、OSPF;外部网关协议主要用于多个自治域之间的路由选择,常用的是BGP和BGP-4。下面分别进行简要介绍。
     
    3.1 RIP路由协议
     
    RIP协议最初是为Xerox网络系统的Xerox parc通用协议而设计的,是Internet中常用的路由协议。RIP采用距离向量算法,即路由器根据距离选择路由,所以也称为距离向量协议。路由器收集所有可到达目的地的不同路径,并且保存有关到达每个目的地的最少站点数的路径信息,除到达目的地的最佳路径外,任何其它信息均予以丢弃。同时路由器也把所收集的路由信息用RIP协议通知相邻的其它路由器。这样,正确的路由信息逐渐扩散到了全网。
     
    RIP使用非常广泛,它简单、可靠,便于配置。但是RIP只适用于小型的同构网络,因为它允许的最大站点数为15,任何超过15个站点的目的地均被标记为不可达。而且RIP每隔30s一次的路由信息广播也是造成网络的广播风暴的重要原因之一。
     
    3.2 OSPF路由协议
     
    80年代中期,RIP已不能适应大规模异构网络的互连,0SPF随之产生。它是网间工程任务组织(1ETF)的内部网关协议工作组为IP网络而开发的一种路由协议。
     
    0SPF是一种基于链路状态的路由协议,需要每个路由器向其同一管理域的所有其它路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其它一些变量。利用0SPF的路由器首先必须收集有关的链路状态信息,并根据一定的算法计算出到每个节点的最短路径。而基于距离向量的路由协议仅向其邻接路由器发送有关路由更新信息。
     
    与RIP不同,OSPF将一个自治域再划分为区,相应地即有两种类型的路由选择方式:当源和目的地在同一区时,采用区内路由选择;当源和目的地在不同区时,则采用区间路由选择。这就大大减少了网络开销,并增加了网络的稳定性。当一个区内的路由器出了故障时并不影响自治域内其它区路由器的正常工作,这也给网络的管理、维护带来方便。
     
    3.3 BGP和BGP-4路由协议
     
    BGP是为TCP/IP互联网设计的外部网关协议,用于多个自治域之间。它既不是基于纯粹的链路状态算法,也不是基于纯粹的距离向量算法。它的主要功能是与其它自治域的BGP交换网络可达信息。各个自治域可以运行不同的内部网关协议。BGP更新信息包括网络号/自治域路径的成对信息。自治域路径包括到达某个特定网络须经过的自治域串,这些更新信息通过TCP传送出去,以保证传输的可靠性。
     
    为了满足Internet日益扩大的需要,BGP还在不断地发展。在最新的BGp4中,还可以将相似路由合并为一条路由。
     
    3.4 路由表项的优先问题
     
    在一个路由器中,可同时配置静态路由和一种或多种动态路由。它们各自维护的路由表都提供给转发程序,但这些路由表的表项间可能会发生冲突。这种冲突可通过配置各路由表的优先级来解决。通常静态路由具有默认的最高优先级,当其它路由表表项与它矛盾时,均按静态路由转发。
     
    4、 路由算法
     
    路由算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终的寻径结果,因此选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标:
     
    ——(1)最优化:指路由算法选择最佳路径的能力。
     
    ——(2)简洁性:算法设计简洁,利用最少的软件和开销,提供最有效的功能。
     
    ——(3)坚固性:路由算法处于非正常或不可预料的环境时,如硬件故障、负载过高或操作失误时,都能正确运行。由于路由器分布在网络联接点上,所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验,并在各种网络环境下被证实是可靠的。
     
    ——(4)快速收敛:收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时,路由器就发出更新信息。路由更新信息遍及整个网络,引发重新计算最佳路径,最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。
     
    ——(5)灵活性:路由算法可以快速、准确地适应各种网络环境。例如,某个网段发生故障,路由算法要能很快发现故障,并为使用该网段的所有路由选择另一条最佳路径。
     
    路由算法按照种类可分为以下几种:静态和动态、单路和多路、平等和分级、源路由和透明路由、域内和域间、链路状态和距离向量。前面几种的特点与字面意思基本一致,下面着重介绍链路状态和距离向量算法。
     
    链路状态算法(也称最短路径算法)发送路由信息到互联网上所有的结点,然而对于每个路由器,仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法(也称为Bellman-Ford算法)则要求每个路由器发送其路由表全部或部分信息,但仅发送到邻近结点上。从本质上来说,链路状态算法将少量更新信息发送至网络各处,而距离向量算法发送大量更新信息至邻接路由器。
     
    由于链路状态算法收敛更快,因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面,链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间,因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别,两种算法在大多数环境下都能很好地运行。
     
    最后需要指出的是,路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由,通过一定的加权运算,将它们合并为单个的复合度量、再填入路由表中,作为寻径的标准。通常所使用的度量有:路径长度、可靠性、时延、带宽、负载、通信成本等。
     
    5、 新一代路由器
     
    由于多媒体等应用在网络中的发展,以及ATM、快速以太网等新技术的不断采用,网络的带宽与速率飞速提高,传统的路由器已不能满足人们对路由器的性能要求。因为传统路由器的分组转发的设计与实现均基于软件,在转发过程中对分组的处理要经过许多环节,转发过程复杂,使得分组转发的速率较慢。另外,由于路由器是网络互连的关键设备,是网络与其它网络进行通信的一个“关口”,对其安全性有很高的要求,因此路由器中各种附加的安全措施增加了CPU的负担,这样就使得路由器成为整个互联网上的“瓶颈”。
     
    传统的路由器在转发每一个分组时,都要进行一系列的复杂操作,包括路由查找、访问控制表匹配、地址解析、优先级管理以及其它的附加操作。这一系列的操作大大影响了路由器的性能与效率,降低了分组转发速率和转发的吞吐量,增加了CPU的负担。而经过路由器的前后分组间的相关性很大,具有相同目的地址和源地址的分组往往连续到达,这为分组的快速转发提供了实现的可能与依据。新一代路由器,如IP Switch、Tag Switch等,就是采用这一设计思想用硬件来实现快速转发,大大提高了路由器的性能与效率。
     
    新一代路由器使用转发缓存来简化分组的转发操作。在快速转发过程中,只需对一组具有相同目的地址和源地址的分组的前几个分组进行传统的路由转发处理,并把成功转发的分组的目的地址、源地址和下一网关地址(下一路由器地址)放人转发缓存中。当其后的分组要进行转发时,茵先查看转发缓存,如果该分组的目的地址和源地址与转发缓存中的匹配,则直接根据转发缓存中的下一网关地址进行转发,而无须经过传统的复杂操作,大大减轻了路由器的负担,达到了提高路由器吞吐量的目标。
     
     
    展开全文
  • 本文旨在区分清楚路由选择、路由协议和路由算法的关系。然后讲解常用路由协议和路由算法。什么是路由选择百科的说法: 路由选择是指选择通过互连网络从源节点向目的节点传输信息的通道,而且信息至少通过一个中间...

    本文旨在区分清楚路由选择、路由协议和路由算法的关系。然后讲解常用路由协议和路由算法。

    什么是路由选择

    百科的说法:

    路由选择是指选择通过互连网络从源节点向目的节点传输信息的通道,而且信息至少通过一个中间节点。

    我的理解:路由选择的目的就是为 IP 数据包选择出一条合适的路。

    什么是路由协议

    百科的说法:

    路由协议是在路由指导IP数据包发送过程中事先约定好的规定和标准。

    我的理解:路由协议规定了 IP数据报在网络中存储和转发的方式。

    什么是路由算法

    百科的说法:

    路由算法是提高路由协议功能,尽量减少路由时所带来开销的算法。

    我的理解:路由算法就是根据度量标准,从众多路径中高效地选择出最佳路由路径。

    上面三个到底有什么不可描述的联系

    下面观点纯属个人理解,如有不对还望指出。

    三者之间的关系:

    总的来说:路由选择依赖于各种路由协议,而各种路由协议又依赖于路由算法。
    各种路由协议之间采取不同的路由算法进行路由选择。

    现在说点人话:我们可以把路由选择看做要干一件什么一样的事情,而路由协议规定了我们按照什么样的方式去完成这件事情,而路由算法则具体的如何去做这件事情。拿生活中的一个例子来说:

    小明要做一件事情,这件事情就是去上学,此时选一种合适的方式去上学就是路由选择。而从家里出发到学校的过程,有不同路径和不同的交通方式,此时路由协议可以看做我们要进行去上学这件事情的大方向,比如说直走,右转,左转等。而路由算法则具体的描述了如何完成这件事情,我首先应该步行五分钟,然后坐公交车从哪个方向,做那一路公交车和走哪一条街,具体高效快速的到达学校相当于路由算法。

    常见路由协议

    按应用应用范围的不同,路由协议可分为两类:

    在一个AS(Autonomous System,自制系统)内的路由协议称为内部网关协议(Interior gateway protocol),AS之间的路由协议称为外部网关协议(Exterior gateway protocol)。

    正在使用的内部网关协议:

    • RIP(Routing Information Protocol):基于距离矢量(DV)的路由协议,以路由跳数作为计数单位的路由协议,适用于比较小的网络环境。
    • IGRP(Interior Gateway Routing Protocol):一种基于距离向量型的内部网关协议。
    • EIGRP(Enhanced Interior Gateway Routing Protocol):增强内部网关路由协议,结合了链路状态(LS)和距离矢量(DV)型路由选择协议的Cisco专用协议
    • IS-IS(Intermediate System-to-Intermediate System):中间系统到中间系统路由协议,最初是ISO为CLNP(Connection Less Network Protocol,无连接网络协议)设计的一种动态路由协议。
    • OSPF(Open Shortest Path First):开放式最短路径优先。是对链路状态路由(LS)协议的一种实现,隶属内部网关协议(IGP),故运作于自治系统内部。著名的迪克斯加算法(Dijkstra)被用来计算最短路径树。

    外部网关协议:

    • EGP (Exterior Gateway Protocol):是AS之间使用的路由协议,由于EGP存在很多的局限性,IETF边界网关协议工作组制定了标准的边界网关协议(BGP),当前被广泛使用。
    • BGP 边界网关协议

    路由算法

    路由协议根据路由算法生成路由表并选择最佳路径进行转发数据包。

    算法的设计目标:

    • 最优化
    • 简洁性
    • 坚固性
    • 快速收敛
    • 灵活性

    路由算法主要分以下两类:

    • 总体式路由算法:每个路由器都拥有网络中其他路由器的全部信息,以及网络的流量状态。也叫LS (链路状态)算法。
    • 分散式路由算法:每个路由器只有与它直接相连的路由器的信息,没有网络中每个路由器的信息。也叫DV (距离向量)算法。

    LS算法

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

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

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

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

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

    4、使用一个合适的算法,确定网络中两个节点之间的最佳路由。

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

    DV算法

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

    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的最佳路由。

    展开全文
  • 文章目录路由算法(一)路由算法的分类静态路由和动态路由:实现方式—集中式或者分布式两大路由选择协议内部网关协议IGP(1)RIP协议RIP特点链路失效、恢复路由表的处理RIP报文距离向量算法:RIP协议优缺点(2)OSPF...

    路由算法(一)

    路由算法的分类

    静态路由和动态路由:

    静态路由选择策略:即非自适应路由选择

    • 手工配置

    • 路由更新慢,优先级高

    • 其特点是简单和开销较小,但不能及时适应网络状态的变化。

    动态路由选择策略:即自适应路由选择

    • 路由更新快-定期更新,能够及时响应链路费用及网络拓扑的变化

    • 其特点是能较好地适应网络状态的变化,但实现起来较为复杂,开销也比较大。

    实现方式—集中式或者分布式

    (1)集中式:

    路由器知道整个网络的拓扑结构和链路状态,由于互联网规模大,其代价太大

    (2)分布式:

    路由器只掌握物理相邻的路由器及其链路费用。

    两大路由选择协议

    内部网关协议IGP

    -在一个自治系统内(AS)使用统一的路由选择算法.AS内使用的路由协议称为IGP(内部网关协议),如RIP、OSPF.

    (1)RIP协议

    RIP特点
    • 分布式的、基于距离向量的路由选择协议。 --此处的距离定义为一条路由的路由器数目

    • 仅仅和相邻路由器交换信息,

    • 交换的信息是自己的路由表(全部信息)

    • 按照固定时间间隔30s交换路由信息,

    • 使用RIP协议的路由不能超过15个,16个路由时,则路径不可达

    • RIP协议中的距离是以路由器的个数定义的,因此可能会忽略高速低延迟但路由器较多的链路

    • RIP 协议的收敛过程较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。

    链路失效、恢复
    • 如果路由器A在180s内为未收到相邻路由器B发来的交换信息,那么经过B路由器的链路则不可用。
    • 重新计算路由
    • 向相邻路由器发送新的通告,重新建立路由表
    路由表的处理
    • RIP路由表通过一个route-d的应用层进程实现的
    • 通告报文周期性的通过UDP传播
    RIP报文

    使用UDP传播

    以RIP2报文为例

    在这里插入图片描述

    RIP报文中:由首部和路由信息两部分组成。

    地址族标识符:用来标志所使用的的地址协议。

    路由标记:填入自治系统的号码,虽然是内部网关协议,但也有可能收到自治系统外的路由选择信息。

    网络地址、下一跳、距离:表明到达目的网络的下一跳地址、距离等信息。

    距离向量算法:

    –基于Bellman-Ford的距离向量算法-用于在一个图中,找出最短路径,此时的距离不再是这里定义的结点(路由器)的个数

    路由器收到相邻路由器(其地址为 X)的一个 RIP 报文

    (1) 先修改此 RIP 报文中的所有项目:把“下一跳”字段中的地址都改为 X,并把所有的“距离”字段的值加 1。

    (2) 对修改后的 RIP 报文中的每一个项目,重复以下步骤:

    若项目中的目的网络不在路由表中,则把该项目加到路由表中。

    ​ 否则

    ​ 若下一跳字段给出的路由器地址是同样的,则把收到的项目替换原路由表中的项目。

    ​ 否则

    ​ 若收到项目中的距离小于路由表中的距离,则进行更新,

    ​ 否则,什么也不做。

    (3) 若 3 分钟还没有收到相邻路由器的更新路由表,则把此相邻路由器记为不可达路由器,即将距离置为 16(表示不可达)。

    (4) 返回
    实例:
    在这里插入图片描述

    RIP协议优缺点

    优点:简单、代价下,收敛过程快

    缺点:规模小(路由限制在16个路由器以下),可能会造成无穷计数问题。

    (2)OSPF协议

    OSPF特点:
    • 开放的
    • 采用分布式的链路状态协议
    • 向本自治系统内所有路由器发送信息,使用洪泛法
    • 发送的信息是与本路由器相邻的所有路由器的链路状态(只是部分信息),链路状态包括本路由器与哪些路由器相连,以及这些路由器之间的度量。–相当于图中某一个结点的所有邻接点的编号和其边的权重。
    • 只有在链路状态改变时,才徐昂自治系统内所有路由器发送信息。
    链路状态数据库
    • 由于各路由器之间频繁的交换链路状态信息,因此,所有路由器最终都能建立一个链路状态数据库–即全网的拓扑结构图。
    • OSPF协议中的链路状态数据库可以较快更新,使每个路由器都能及时更新路由表,OSPF更新过程收敛较快。

    在这里插入图片描述

    OSPF的区域
    • 将一个很大的自治系统再划分为若干个更小的范围,叫做区域
    • 每个区域都有一个32位区域标志符,使用点分十进制
    • 这样的好处是在使用洪泛法交换链路状态信息时,只需要在每一个区域内交换即可,减少了网络的通信量
    • 上层的主干区域(0.0.0.0)用来连接下层的区域

    在这里插入图片描述

    OSPF报文
    • 直接使用IP数据报(数据量少),不使用UDP

    在这里插入图片描述

    • 路由器标志符、区域标识符:表明此路由器的信息。
    OSPF的分组类型
    • 问候分组
    • 数据库描述分组
    • 链路状态请求分组
    • 链路状态更新分组
    • 链路状态确认

    实例:路由器R向整个网络发送其信息。
    在这里插入图片描述

    最短路径算法

    –使用了Dijkstra提出的最短路径算法,见链接-图的最短路径算法

    每台路由器从链路状态数据库里得到带权有向图,分别利用最短路径算法,得到自己到其他目的网络(路由器)的最短路径

    在这里插入图片描述

    OSPF优缺点

    优点:互连网规模较大时,OSPF比RIP较好,响应网络变化的时间短,不存在RIP协议中无穷计数的情况

    缺点:代价大,具体实现起来复杂

    展开全文
  • 路由算法的总结

    2016-10-10 22:29:37
    路由算法首先可以分为两大类: 静态路由算法 动态路由算法 静态的路由算法主要工作由网管完成,所以这里不多说,需要总结的是动态路由算法。动态路由算法主要是两类: 距离–向量路由算法(RIP) 链路状态路由算法...
  • LEACH算法是一种无线传感器网络路由协议,来源于Wendi Rabiner Heinzelman, Anantha Chandrakasan, 和Hari Balakrishnan三人在2000年Proceedings of the 33rd Hawaii International Conference on System Sciences...
  • 路由算法

    2017-06-18 23:47:06
    算法设计者的特定目标影响了该路由协议的操作;具体来说存在着多种路由算法,每种算法对网络和路由器资源的影响都不同;由于路由算法使用多种度量标准,从而影响到最佳路径的计算。关于路由器如何收集网络的结构信息...
  • 路由常见算法

    2017-07-18 10:27:07
    算法设计者的特定目标影响了该路由协议的操作;具体来说存在着多种路由算法,每种算法对网络和路由器资源的影响都不同;由于路由算法使用多种度量标准(metric),从而影响到最佳路径的计算。在linux中使用 route ...
  • 路由路由算法

    2017-05-15 21:29:01
    路由路由算法
  • 路由算法综述2.静态路由算法3.距离-向量路由算法(RIP)4.链路状态路由算法(OSPF)5.层次路由 1.路由算法综述 路由器转发分组是通过路由表转发的,而路由表是通过各种算法得到的。主机通常直接与一台路由器相连接,该...
  • 其中16位网络地址仅仅在网络内部使用,用于路由机制和数据传输。这个地址是在节点加入网络时由其父节点动态分配的。当网络中的节点允许一个新节点通过它加入网络时,它们之间就形成了父子关系。所有加入ZigBee网络的...
  • 因为笔者主要研究WMN,所以首先从WMN的路由协议说起,但是WMN路由协议很多都是借鉴有线网络的路由协议,所以目的在于让读者对于网络层的路由协议有个全局的认识。本篇虽然有一些专业术语,但基本都在上下文可以找到...
  • 互联网常用路由选择协议理想路由算法自治系统AS内部网关协议IGPRIP(UDP端口520)距离向量算法流程RIP报文格式RIP缺点OSPF外部网关协议EGPBGP 理想路由算法 理想路由算法的特点: 算法必须是正确的完整的; ...
  • 实验报告一:RIP动态路由协议实验 实验拓扑: Requirment: 某网络整体结构如果所示,在Router1上有3个回环口,IP地址如图,Router3连接两台主机,现要求通过使用路由协议实现全网互联。 在各路由器上配置静态路由...
  • Flooding and gossiping 这种算法也是传统网络中最基本的路由方式,不需要知道网络拓扑结构和使用任何路由算法。每个传感器节点把自己接收到的packet 发送给所有它的邻居节点,这个过程一直重复直到该分组到达sink ...
  • 距离矢量路由算法

    2018-03-11 21:32:21
    转载自: http://blog.csdn.net/u013007900/article/details/45565389 现代计算机网络通常使用动态路由算法,因为这类算法能够适应网络的拓扑和流量变化,其中最流行的两种动态路由算法是“距离矢量路由算法”和...
  • BGP路由协议(1)

    2019-10-21 22:49:22
    BGP是外部路由协议,是一种增强的距离矢量路由协议。 BGP作用 用来在AS之间传递路由信息。 什么是系统(AS) AS是由同一个技术管理机构管理、使用统一选路策略的一些路由器的集合。 BGP特征 可靠的路由更新机制 ...
  • 路由算法有很多,本篇采用迪杰斯特拉最短路径法实现简单的路由算法。可能很多人一看到这个就会想到数据结构了,想到数据结构中必须要建立图的结构就很头疼,今天这种写法可以先不采用数据结构书上的写法,也可以实现...
  • 链路状态路由协议(也可以说OSPF)工作原理: 每台路由器通过使用Hello报文与它的邻居之间建立邻接关系 每台路由器向每个邻居发送链路状态通告(LSA),有时叫链路状态报文(LSP). 每个邻居在收到LSP之后要依次向它的...
  • AODV路由协议详解

    2020-07-08 16:56:44
    移动Ad Hoc网络(Mobile Adhoc Network,MANET)是一种无线自组织的...AODV(Ad Hoc On-Demand Distance Vector)路由协议是专门为移动Ad Hoc网络设计的路由协议,它是一个按需路由协议,只要当需要建立到目的节点的路
1 2 3 4 5 ... 20
收藏数 37,422
精华内容 14,968
关键字:

路由协议具体算法