扩散更新算法

Ⅰ SPF 和 DUAL 两种算法有什么区别

SPF算法是OSPF路由协议的基础;DUAL（扩散更新）算法被EIGRP路由协议采用。
介绍下：
四种最常见路由协议是RIP、IGRP、OSPF和EIGRP。
1.RIP（Routing
Information
Protocol，路由信息协议）是使用最广泛的距离向量协议，它是由施乐（Xerox）在20世纪70年代开发的。最大的特点是，其实现原理和配置方法都非常简单。RIP基于跳数计算路由，并且定期向邻居路由器发送更新消息。
2.IGRP是Cisco专有的协议，只在Cisco路由器中实现。它也属于距离向量类协议，所以在很多地方与RIP有共同点，比如广播更新等。它和RIP最大的区别表现在度量方法、负载均衡等几方面。IGRP支持多路径上的加权负载均衡，这样，网络的带宽可以得到更加合理的利用。另外，与RIP仅使用跳数作为度量依据不同，IGRP使用了多种参数，构成复合的度量值，这其中可以包含的因素有：带宽、延迟、负载、可靠性和MTU（最大传输单元）等。
3.OSPF协议是20世纪80年代后期开发的，20世纪90年代初成为工业标准，是一种典型的链路状态协议。OSPF的主要特性包括：支持VLSM（变长的子网掩码）、收敛迅速、带宽占用率低等。等。OSPF协议在邻居之间交换链路状态信息，以便路由器建立链路状态数据库（LSD）之后，路由器根据数据库中的信息利用SPF（Shortest
Path
First，最短路径优先）算法计算路由表，选择路径的主要依据是带宽。
4.EIGRP是IGRP的增强版，它也是Cisco专有的路由协议。EIGRP采用了扩散更新（DUAL）算法，在某种程度上，它和距离向量算法相似，但具有更短的收敛时间和更好的可操作性。作为对IGRP的扩展，EIGRP支持多种可路由的协议，如IP、IPX和AppleTalk等。运行在IP环境时，EIGRP还可以与IGRP进行平滑的连接，因为它们的度量方法是一致的。
以上4种路由协议都是域内路由协议，它们通常使用在自治系统的内部。当进行自治系统间的连接时，往往采用诸如BGP（Border
Gateway
Protocols，边界网关协议）和EGP（External
Gateway
Protocols，外部网关协议）这样的域间路由协议。目前在Internet上使用的域间路由协议是BGP第四版。

Ⅱ 路由算法的类型有

静态路由算法

1.Dijkstra算法（最短路径算法）

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。

Dijkstra算法执行步骤如下：

步骤一：路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i,j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。

步骤二：路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：

前序字段———表示当前节点之前的节点。

长度字段———表示从源节点到当前节点的权值之和。

标号字段———表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。

步骤三：路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。

步骤四：路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。

步骤五：路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。

步骤六：路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。

步骤七：如果这个节点不是V2（目的节点），路由器则返回到步骤5。

步骤八：如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

2.扩散法

事先不需要任何网络信息；路由器把收到的每一个分组，向除了该分组到来的线路外的所有输出线路发送。将来会有多个分组的副本到达目的地端，最先到达的，可能是走了“最优”的路径常见的扩散法是选择性扩散算法。

3.LS算法

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

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

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

步骤三：向网络中的其他路由器广播自己的信息，同时也接收其他路由器的信息。

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

步骤四：使用一个合适的算法，确定网络中两个节点之间的最佳路由。

Ⅲ eigrp依靠什么机制防环

EIGRP是思科私有的路由协议，翻译过来就是增强型内部网关路由协议，也是混合型距离矢量和链路状态路由协议，用我自己话说就是“四不像”。

它的防环机制是采用扩散更新算法（DUAL），在运行EIGRP的路由器上保存着三张表：邻居表、拓扑表、路由表。当一台路由器刚刚启动EIGRP进程时，通过发送hello包来进行建立邻居关系，交换路由信息，通过执行扩散更新算法，邻居之间互相通告AD，最后将算法执行的结果写进拓扑表，拓扑表中最优的条目即写进路由表。你可以自己做个实验，敲一下sh ip eigrp topology命令，就可以看到EIGRP的拓扑表。

EIGRP计算度量值的方法为：10的7次方除以链路的带宽，加上沿途各个接口出方向的延迟delay，再乘以256.
同时在EIGRP里还有这样几个概念要清楚：
AD：邻居通过来的到达目的网络的度量值；
FD：自己到达邻居的度量值+邻居通告过来的邻居自己到达目的网络的AD；
S：FD值为最小的下一跳路由，也叫后继路由；
FS：FD值为次小的下一跳路由，也叫可行性路由。

扩散更新算法的核心就是：邻居通告过来的AD，要小于自己目前最优的FD，这样才会写进自己的路由表，具备成为S的条件。

由于FS为备用的下一跳路由，在执行完扩散更新算法后，备用的路由也选好了，所以当网络发生状况时，EIGRP的收敛速度也就是very high。

另外EIGRP有5种包：hello包、发送路由更新的updata包、对路由更新进行确认的updataack包、当路由发生变化，查找不到S时发送的查询query包、对查询进行响应的query replay包，交换这些包依靠的是RTP可靠信息传输协议机制。

注意的是：EIGRP不像OSPF建立邻居关系时是hello去hello回，而是发送hello去，对端路由返回来的直接就是路由信息。

这就是EIGRP里我自己了解的，最主要的还是看完书后，自己搭个拓扑做一下EIGRP的实验，做完后验证一下，对整个协议的运行过程也就熟悉了，这样才能真正的把所学的东西变成是自己的。

Ⅳ 路由协议的常用分析

路由分为静态路由和动态路由，其相应的路由表称为静态路由表和动态路由表。静态路由表由网络管理员在系统安装时根据网络的配置情况预先设定，网络结构 发生变化后由网络管理员手工修改路由表。动态路由随网络运行情况的变化而变化，路由器根据路由协议提供的功能自动计算数据传输的最佳路径，由此得到动态路由表。
根据路由算法，动态路由协议可分为距离向量路由协议（Distance Vector Routing Protocol）和链路状态路由协议（Link State Routing Protocol）。距离向量路由协议基于Bellman-Ford算法，主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常着名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传 递给在同一区域内的所有路由器。 根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议 （Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域 间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，已被BGP代替。
EIGRP是Cisco公司的私有协议，是一种混合协议，它既有距离向量路由协议的特点，同时又继承了链路状态路由协议的优点。各种路由协议各有特点，适合不同类型的网络。下面分别加以阐述。 静态路由表在开始选择路由之前就被网络管理员建立，并且只能由网络管理员更改，所以只适于网络传输状态比较简单的环境。静态路由具有以下特点：
· 静态路由无需进行路由交换，因此节省网络的带宽、CPU的利用率和路由器的内存。
· 静态路由具有更高的安全性。在使用静态路由的网络中，所有要连到网络上的路由器都需在邻接路由器上设置其相应的路由。因此，在某种程度上提高了网络的安全性。
· 有的情况下必须使用静态路由，如DDR、使用NAT技术的网络环境。
静态路由具有以下缺点：
· 管理者必须真正理解网络的拓扑并正确配置路由。
· 网络的扩展性能差。如果要在网络上增加一个网络，管理者必须在所有路由器上加一条路由。
· 配置烦琐，特别是当需要跨越几台路由器通信时，其路由配置更为复杂。 动态路由协议内部网关协议IGP和外部网关协议EGP。而内部网关协议IGP可以分为距离矢量路由协议和链路状态路由协议，两种协议各有特点，分述如下：
1. 距离矢量（DV）协议
距离向量指协议使用跳数或向量来确定从一个设备到另一个设备的距离。不考虑每跳链路的速率。
距离向量路由协议不使用正常的邻居关系，用两种方法获知拓扑的改变和路由的超时：
· 当路由器不能直接从连接的路由器收到路由更新时；
· 当路由器从邻居收到一个更新，通知它网络的某个地方拓扑发生了变化。
在小型网络中（少于100个路由器，或需要更少的路由更新和计算环境），距离向量路由协议运行得相当好。当小型网络扩展到大型网络时，该算法计算新路 由的收敛速度极慢，而且在它计算的过程中，网络处于一种过渡状态，极可能发生循环并造成暂时的拥塞。再者，当网络底层链路技术多种多样，带宽各不相同时， 距离向量算法对此视而不见。
距离向量路由协议的这种特性不仅造成了网络收敛的延时，而且消耗了带宽。随着路由表的增大，需要消耗更多的CPU资源，并消耗了内存。
2. 链路状态（LS）路由协议
链路状态路由协议没有跳数的限制，使用“图形理论”算法或最短路径优先算法。
链路状态路由协议有更短的收敛时间、支持VLSM（可变长子网掩码）和CIDR。
链路状态路由协议在直接相连的路由之间维护正常的邻居关系。这允许路由更快收敛。链路状态路由协议在会话期间通过交换Hello包（也叫链路状态信息）创建对等关系，这种关系加速了路由的收敛。
3.链路状态路由协议和距离向量路由协议的比较
不像距离向量路由协议那样，更新时发送整个路由表。链路状态路由协议只广播更新的或改变的网络拓扑，这使得更新信息更小，节省了带宽和CPU利用率。另外，如果网络不发生变化，更新包只在特定的时间内发出（通常为30min到2h）。
4 常用动态路由协议的分析
4.1 RIP（国际公有，最古老的路由协议，不过有很多缺陷）
RIP（路由信息协议）是路由器生产商之间使用的第一个开放标准，是最广泛的路由协议，在所有IP路由平台上都可以得到。当使用RIP时，一台 Cisco路由器可以与其他厂商的路由器连接。RIP有两个版本：RIPv1和RIPv2，它们均基于经典的距离向量路由算法，最大跳数为15跳。
RIPv1是有类路由（Classful Routing）协议，因路由上不包括掩码信息，所以网络上的所有设备必须使用相同的子网掩码，不支持VLSM。RIPv2可发送子网掩码信息，是无类路由（Classless Routing）协议，支持VLSM。
RIP使用UDP数据包更新路由信息。路由器每隔30s更新一次路由信息，如果在180s内没有收到相邻路由器的回应，则认为去往该路由器的路由不可用，该路由器不可到达。如果在240s后仍未收到该路由器的应答，则把有关该路由器的路由信息从路由表中删除。
RIP具有以下特点：
· 不同厂商的路由器可以通过RIP互联；
· 配置简单； · 适用于小型网络（小于15跳）；
· RIPv1不支持VLSM；
· 需消耗广域网带宽；
· 需消耗CPU、内存资源。
RIP的算法简单，但在路径较多时收敛速度慢，广播路由信息时占用的带宽资源较多，它适用于网络拓扑结构相对简单且数据链路故障率极低的小型网络中，在大型网络中，一般不使用RIP。
4.2 IGRP（已经退出历史的舞台）
内部网关路由协议（Interior Gateway Routing Protocol，IGRP）是Cisco公司20世纪80年代开发的，是一 种动态的、长跨度（最大可支持255跳）的路由协议，使用度量（向量）来确定到达一个网络的最佳路由，由延时、带宽、可靠性和负载等来计算最优路由，它在 同个自治系统内具有高跨度，适合复杂的网络。Cisco IOS允许路由器管理员对IGRP的网络带宽、延时、可靠性和负载进行权重设置，以影响度量的计 算。
像RIP一样，IGRP使用UDP发送路由表项。每个路由器每隔90s更新一次路由信息，如果270s内没有收到某路由器的回应，则认为该路由器不可到达；如果630s内仍未收到应答，则IGRP进程将从路由表中删除该路由。
与RIP相比，IGRP的收敛时间更长，但传输路由信息所需的带宽减少，此外，IGRP的分组格式中无空白字节，从而提高了IGRP的报文效率。但IGRP为Cisco公司专有，仅限于Cisco产品。
4.3 EIGRP（思科私有）
随着网络规模的扩大和用户需求的增长，原来的IGRP已显得力不从心，于是，Cisco公司又开发了增强的IGRP，即EIGRP。EIGRP使用与IGRP相同的路由算法，但它集成了链路状态路由协议和距离向量路由协议的长处，同时加入散播更新算法（DUAL）。
EIGRP具有如下特点：
· 快速收敛。快速收敛是因为使用了散播更新算法，通过在路由表中备份路由而实现，也就是到达目的网络的最小开销和次最小开销（也叫适宜后继， feasible successor）路由都被保存在路由表中，当最小开销的路由不可用时，快速切换到次最小开销路由上，从而达到快速收敛的目的。
· 减少了带宽的消耗。EIGRP不像RIP和IGRP那样，每隔一段时间就交换一次路由信息，它仅当某个目的网络的路由状态改变或路由的度量发生变 化时，才向邻接的EIGRP路由器发送路由更新，因此，其更新路由所需的带宽比RIP和EIGRP小得多——这种方式叫触发式（triggered）。
· 增大网络规模。对于RIP，其网络最大只能是15跳（hop），而EIGRP最大可支持255跳（hop）。
· 减少路由器CPU的利用。路由更新仅被发送到需要知道状态改变的邻接路由器，由于使用了增量更新，EIGRP比IGRP使用更少的CPU。
· 支持可变长子网掩码。
· IGRP和EIGRP可自动移植。IGRP路由可自动重新分发到EIGRP中，EIGRP也可将路由自动重新分发到IGRP中。如果愿意，也可以关掉路由的重分发。
· EIGRP为模块化设计，支持三种可路由的协议（IP、IPX、AppleTalk），更新版本支持IPv6。
· 支持非等值路径的负载均衡。
· 因EIGIP是Cisco公司开发的专用协议，因此，当Cisco设备和其他厂商的设备互联时，不能使用EIGRP
4.4 OSPF（国际公有）
开放式最短路径优先（Open Shortest Path First，OSPF）协议是一种为IP网络开发的内部网关路由选择协议，由IETF开 发并推荐使用。OSPF协议由三个子协议组成：Hello协议、交换协议和扩散协议。其中Hello协议负责检查链路是否可用，并完成指定路由器及备份指 定路由器；交换协议完成“主”、“从”路由器的指定并交换各自的路由数据库信息；扩散协议完成各路由器中路由数据库的同步维护。
OSPF协议具有以下优点：
· OSPF能够在自己的链路状态数据库内表示整个网络，这极大地减少了收敛时间，并且支持大型异构网络的互联，提供了一个异构网络间通过同一种协议交换网络信息的途径，并且不容易出现错误的路由信息。 · OSPF支持通往相同目的的多重路径。
· OSPF使用路由标签区分不同的外部路由。
· OSPF支持路由验证，只有互相通过路由验证的路由器之间才能交换路由信息；并且可以对不同的区域定义不同的验证方式，从而提高了网络的安全性。
· OSPF支持费用相同的多条链路上的负载均衡。
· OSPF是一个无类路由协议，路由信息不受跳数的限制，减少了因分级路由带来的子网分离问题。
· OSPF支持VLSM和无类路由查表，有利于网络地址的有效管理。
· OSPF使用AREA对网络进行分层，减少了协议对CPU处理时间和内存的需求。
4.5 BGP
BGP用于连接Internet。BGPv4是一种外部的路由协议。可认为是一种高级的距离向量路由协议。
在BGP网络中，可以将一个网络分成多个自治系统。自治系统间使用eBGP广播路由，自治系统内使用iBGP在自己的网络内广播路由。
Internet由多个互相连接的商业网络组成。每个企业网络或ISP必须定义一个自治系统号（ASN）。这些自治系统号由IANA （Internet Assigned Numbers Authority）分配。共有65535个可用的自治系统号，其中65512~65535为私 用保留。当共享路由信息时，这个号码也允许以层的方式进行维护。
BGP使用可靠的会话管理，TCP中的179端口用于触发Update和Keepalive信息到它的邻居，以传播和更新BGP路由表。
在BGP网络中，自治系统有： 1. Stub AS
只有一个入口和一个出口的网络。
2. 转接AS（Transit AS）
当数据从一个AS到另一个AS时，必须经过Transit AS。
如果企业网络有多个AS，则在企业网络中可设置Transit AS。
IGP和BGP最大的不同之处在于运行协议的设备之间通过的附加信息的总数不同。IGP使用的路由更新包比BGP使用的路由更新包更小（因此BGP承载更多的路由属性）。BGP可在给定的路由上附上很多属性。
当运行BGP的两个路由器开始通信以交换动态路由信息时，使用TCP端口179，他们依赖于面向连接的通信（会话）。
BGP必须依靠面向连接的TCP会话以提供连接状态。因为BGP不能使用Keepalive信息（但在普通头上存放有Keepalive信息，以允许 路由器校验会话是否Active）。标准的Keepalive是在电路上从一个路由器送往另一个路由器的信息，而不使用TCP会话。路由器使用电路上的这 些信号来校验电路没有错误或没有发现电路。 某些情况下，需要使用BGP：
· 当你需要从一个AS发送流量到另一个AS时；
· 当流出网络的数据流必须手工维护时；
· 当你连接两个或多个ISP、NAP（网络访问点）和交换点时。
以下三种情况不能使用BGP：
· 如果你的路由器不支持BGP所需的大型路由表时；
· 当Internet只有一个连接时，使用默认路由；
· 当你的网络没有足够的带宽来传送所需的数据时（包括BGP路由表）。

Ⅳ 常见的路由选择算法有哪些

链路状态算法（也称最短路径算法）发送路由信息到互联网上所有的结点，然而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法（也称为Bellman-Ford算法）则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器。 ——由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循环。但另一方面，链路状态算法要求比距离向量算法有更强的CPU能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别，两种算法在大多数环境下都能很好地运行。