在确定最佳路径的过程中，路由选择算法需要初始化和维护路由选择表（ routing table ）。路由选择表中包含的路由选择信息根据路由选择算法的不同而不同。一般在路由表中包括这样一些信息：目的网络地址，相关网络节点，对某条路径满意程度，预期路径信息等。

为了成功地转发一个数据包，IP路由算法根据路由表选择 下一跳的目的地址。

IP路由算法如下：

假设一个 待转发的IP报文的目的地址是D, 网络前缀是N:

If (N属于某直连网络)

把IP报文直接转发

else if（路由表包含目的为D的路由）

根据路由表中的下一跳转发IP报文（如果存在多条匹配的路由，则选择子网掩码长度最长的路由转发）

Else if（路由表中存在缺省路由）

根据缺省路由转发IP报文

Else

向源主机 发送ICMP 出错消息，通知IP报文不能被转发。

路由器之间传输多种信息来维护路由选择表，修正路由消息就是最常见的一种。修正路由消息通常是由全部或部分路由选择表组成，路由器通过分析来自所有其他路由器的最新消息构造一个完整的网络拓扑结构详图。链路状态广播便是一种路由修正信息。

所谓交换指当一台主机向另一台主机发送数据包时，源主机通过某种方式获取路由器地址后，通过目的主机的协议地址（网络层）将数据包发送到指定的路由器物理地址（介质访问控制层）的过程。

通过使用交换算法检查数据包的目的协议地址，路由器可确定其是否知道如何转发数据包。如果路由器不知道如何将数据包转发到下一个节点，将丢弃该数据包；如果路由器知道如何转发，就把物理目的地址变换成下一个节点的地址，然后转发该数据包。在传输过程中，其物理地址发生变化，但协议地址总是保持不变。

路由选择是指选择通过互连网络从源节点向目的节点传输信息的通道，而且信息至少通过一个中间节点。路由选择工作在 OSI 参考模型的网络层。

路由选择包括两个基本操作，即最佳路径的判定和网间信息包的传送（交换）。两者之间，路径的判定相对复杂。

各种路由算法不尽相同，主要是由于：首先，算法设计者的设计目标会影响路由选择协议的运行结果；其次，现有的各种路由选择算法对网络和路由器资源的影响不同；最后，不同的计量标准也会影响最佳路径的计算结果。

路由选择基础知识

路由是将对象从一个地方转达发到另一个地方的一个中继过程

学习和维持网络拓扑结构知识的机制被认为是路由功能。渡越数据流经路由器进入接口

穿过路由器被移送到外出接口的过程，是另一项单独的功能，被认为是交换/转发功能。路由设备必须同时具有路由和交换的功能才可以作为一台有效的中继设备。

为了进行路由，路由器必须知道下面三项内容：

l、路由器必须确定它是否激活了对该协议组的支持；

2、路由器必须知道目的地网络；

3、路由器必须知道哪个外出接口是到达目的地的最佳路。

路由选择协议通过度量值来决定到达目的地的最佳路径。小度量值代表优选的路径；如果两条或更多路径都有一个相同的小度量值，那么所有这些路径将被平等地分享。通过多条路径分流数据流量被称为到目的地的负载均衡。

执行路由操作所需要的信息被包含在路由器的路由表中，它们由一个或多个路由选择协议进程生成。路由表由多个路由条目组成，每个条目指明了以下内容：

*学习该路由所用的机制（动态或手动）

*逻辑目的地

*管理距离

*度量值（它是度量一条路径的总"总开销"的一个尺度）

*去往目的地下一HOP的中继设备（路由器）的地址；

*路由信息的新旧程度

*与要去往目的地网络相关联的接口

使用命令SHOW IP ROUTE可看到以上内容

缺省管理距离的预先分配原则是：人工设置的路由条目优先级高于动态学到路由条目，度量值算法复杂的路由选择协议优先级高于度量值算法简单的路由选择协议。

路由器一般选择具有最小度量值的路径；CISCO路由器的IP环境中如果同时出现了多条度量值最低且相同的路径，那么在这多条路径上将启用负载均衡，C ISCO默认支持4条相同度量值的路径，通过使用"maximum-paths"命令可以认CISCO路由器支持最多达6条相同度量值路径。

RIP是一种用在小到中型TCP/IP网络中采用的路由选择协议，它采用跳数作为度量值，它的负载均衡功能是缺省启用的，RIP决定最佳路径时是不考虑带宽的！！！

IGRP是一种用在中到大型TCP/IP网络中采用的路由选择协议，它采用复合的度量值，它考虑了带宽、延迟、可靠性、负载和最大传输单元（M TU），但缺省地使用了带宽和延时值。IGRP也能进行负载均衡。

在路由器启动之后，它立刻试图与其相邻路由设备建立路由关系。该初始通信的目的是为了识别相邻设备，并且开始进行通信并学习网络相结构。建立相邻关系的方法和对拓扑结构的初始学习随路由选择协议的不同而不同。

路由选择协议会交换定期的HELLO消息或定期的路由更新数据包，以维持相邻设备间进行着通信。

在了解了网络拓扑结构，且路由表中已包含了到已知地网络的最佳路径后，向这些目的地的数据转发就可以开始了。

路由选择选择协议

有类别路由选择（classful routing）概述

不随各网络地址发送子网掩码信息的路由选择协议被称为有类别的选择协议（RIPv1、IGRP）

当采用有类别路由选择协议时，属于同一主类网络（A类、B类和C类）有所有子网络都必须使用同一子网掩码。运行有类别路由选择协议的路由选择协议的路由器将执行下面工作的一项以确定该路由型网络部分：

*如果路由更新信息是关于在接收接口上所配的同一主类网络的，路由器将采用配置在接口上的子网掩码；

*如果路由更新是关于在接收接口上所配的不同主类的网络的，路由器将根据其所属地址类别采用缺省的子网掩码。

有类别归纳路由的生成是由有类别路由选择协议自动处理的

无类别路由选择(classless routing)概述

无类别路由选择协议包括开放最短路径优先（OSPF）、EIGRP、RIPV2、中间系统到中间系统（IS-IS）和边界网关协议版本4（BGP4）。

在同一主类网络中使用不同的掩码长度被称为可变长度的子网掩码（VLSM）。无类别路由选择路由选择协议支持VLSM，因此可以更为有效的设置子网掩码，以满足不同子网对不同主机数目的需求，可以更充分的利用主机地址。

多数距离矢量型路由选择协议产生的定期的、例行的路由更新只传输到直接相连的路由设备。

在纯距离矢量型路由环境中，路由更新包括一个完整的路由表，通过接收相邻设备的全路由表，路由能够核查所有已知路由，然后根据所接收到的更新信息修改本地路由表。解决路由问题的距离矢量法有时被称为" 传闻路由（routing by rumor）"

CISCO IOS支持几种距离矢量型路由选择协议，凶手RIPv1、RIPv2和IGRP。CISCO也直持EIGRP，它是一种高级的距离矢量型路由选择协议。

路由选择协议通常与协议组的网络层关联

大多数距离矢量型路由选择协议采用贝乐曼-福特(Bellman-Ford)算法来计算路由。EIGRP是一种高级的距离矢量路由协议，它采用弥散修正算法（D UAL）

Cisco的IP距离矢量型路由选择协议的比较

特征RIPv1RIPv2IGRPEIGRP

计数到无限XXX

横向距离XXXX

抑制计时器XXX

触发式更新，路由反向 XXXX

负载均衡-等成本路径XXXX

负载均衡-非等成本路径XX

VLSM支持XX

度量值跳数跳数复合复合

跳数限制

易扩展性小小中大

注：IGRP和EIGRP的跳数限制缺省为100，但是可以配置到最大为255。

链路状态型路由选择协议只当网络拓扑结构发生变化时才生成路由更新数据包。当链路状态发生变化时，检测到这一变化的设备就生成一个关于该链路（路由）的链路状态通告（L SA）。随后LSA通过一个特殊的多目组播地址被传播给所有相邻设备。每台路由设备都会保留LSA拷贝，并向其相邻设备转发该LSA（这个过程变称为扩散f looding）然后更新其拓扑结构数据库（这是一个包含网络所有链路状态信息表）。LSA扩散被用于确保所有路由设备都能了解到这个变化，这样它们就能够更新它们的数据，并生成一个更新过的、反映新的网络拓扑结构的路由表。

Cisco的链路状态型路由选择协议的比较

特征OSPFIS-ISEIGRP

要求体系化拓扑结构XX

保留对所有可能路由的了解XXX

路由归纳-人工XXX

路由归纳-自动X

事件触发式通告XXX

负载均衡-等成本路径XXX

负载均衡-非等成本路径X

VLSM支持XXX

路由算法DijkstraIS-ISDUAL

度量值链路成本（带宽）链路成本（带宽）复合

跳数限制无1024100

易扩展性大很大大

各路由器中的路由进程都必须留有到各可能目的地逻辑网络的无环路单路径，当所有路由表都达到同步，且每个路由表都包含有到各目的地网络的一条可用路由时，网络就达到了收敛状态。收敛是在网络拓扑结构发生变化后，比如增加了新的路由或现有路由的状态发生了变化后，与路由表同步相关联的活动。

收敛时间是网络中所有路由对当前拓扑结构的认知达到一致所需的时间，网络的大小、所使用的路由选择协议以及众多可配置的计时器都能够影响收敛时间。

有两种检测的方法：

*当物理层或数据链路层没能接收到一定数量（通常是3）的连续keepalive消息时，就认为该链路失效。

*当路由选择协议没能接收到一定数量（通常是3）的连续Hello消息或路由更新或相类似消息时，就认为该链路失效了。

大多数路由选择协议都具有防止在链路状态转换过程中产生拓扑结构环路用的计时器。

路由选择就是构建网络节点路由表的过程，无论哪种分组网络，路由选择都是由网络提供的基本功能，但咋X.25建议中对路由选择并未作出明确规定，对不同的分组网允许有不同的路由选择算法，如何确立路由选择算法的好坏呢？分组的路由选择的基本原则如下：算法简单，易于实现，以减少额外开销；算法对所有用户都是公平的；应选择性能最佳的传输路径，使得端到端时延尽量小，个网络节点工作量均衡，最大限度提高网络资源利用率；网络出现故障时，在网络拓扑改变的情况下，算法仍能正常工作，自动选择迂回路由。

不同的分组交换网有可能采取不同的路由选择。路由选择可分为动态法和静态法两类。

路由选择器静态法

(1)扩散式路由法，分组从原始节点发往与之相邻的节点，接受该分组的节点检查它是否收到过该分组，如果已经收到过，则将它抛弃；如果未收到，只要该分组的目的节点不是该节点，就将此分组对相邻节点进行广播，最终该分组必将到达目的节点。其中，最早到达目的节点的分组所经历的过程必定是一条最佳路径。采用扩散式路由法，路由选择与网络拓扑无关，即使网络严重故障。只要有一条通路存在，分组也能到达终点，因此分组的传输的可靠性很高。但缺点是分组的无效传输量很大，网络的额外开销也大，网络中业务量的增加会导致排队时延的加大。

(2)固定路由表法，在每个节点交换机中设置一个包含路由目的节点地址和对应输出逻辑信道号的路由表，他指明从该节点到网络中的任何终点应当选择的路径。呼叫请求分组根据分组的目的地址查找该路由表，这样可以获得各转接节点的输出逻辑信号，从而形成一条端到端的虚电路。为防止网络故障或通路阻塞，路由表中可以规定主用路由和备用路由。

路由选择器动态法

(1)自适应路由选择网，自适应路由选择法是指路由选择根据网络情况的变化而变化。路由是由若干段链路串接而成的，自适应路由选择法是用迭代法逐段选取虚链路，从而形成一条端到端的虚电路。但在这种算法中，要求各节点存有全网络拓扑数据，而且每条链路的变化信息必须广播给网络所有的节点。自适应路由选择算法对减少网络时延、平滑网络负载、防止网络阻塞是有利的，但是路由表的频繁更换可能引起网络的不稳定，产生分组循环或者使分组在一对节点之间来回穿梭，自适应路由选择算法是X.25分组网中应用最为普遍的一种选路方式。

(2)集中式路由交换，网管中心负责全网状态信息的采集、路由计算以及路由表的下载。在分组交换网中，交换机之间一般有多条路由可选择。如何获得一条较好的路由，除了要有一个通过网络的平均时延较短和平衡网内业务量能力较强的路由算法外，同时还要考虑网内资源的利用和网络结构的适应能力。 2100433B

路由协议分为内部网关协议 (IGP)和外部网关协议(EGP)两种，各用于自治系统内部和自治系统之间，其中IGP又分为距离向量和链路向量。距离向量是定期向相邻的路由器交流整个路由表的信息，如路由信息协议(RIPvl)、IGRP。而链路向量只在链路状态发生改变时向所有的路由器交流链路状态信息，如开放最短路优先 (OSPF)。而像EIGRP则同时具有两种协议的特点。

路由选择器内部网关协议

(1)路由信息协议RIP，最早的路由协议之一，而且现在仍然在广泛使用。它是距离向量路由式协议，该协议在计算两个地方的距离时只计算经过的路由器的数目，如果到相同目标有两种不等速或带宽不同的路由器，但是经过的路由器的个数一样，RIP认为两者距离一样;而实 际传送数据时，很明显一个快一个慢，这就是RIP协议的不足之处。 RIP广播一个用户数据报协议 (UDP)数据包更换路由信息，每个路由器间隔30秒更换一次路由信息，在180秒内未收到某路由器的回应，它则认为目前该路由器不可到达；若在270秒后仍未有应答， 则把有关它的路由信息从路由表中删掉。RIP运行简单，适用于小型网络，因特网上还在部分使用着 RIP。

（2）开放最短路径优先协议OSPF，修正了RIP中的一些缺陷。每个采用OSPF的路由器监视每个相邻节点链路状态，然后将链路状态信息以洪泛方式发送到网络内的其他路由器。采用这种方式可以使网络内的每个路由器构造一个相同的链路状态数据库，以描述完整的网络拓扑。

路由选择器外部网关协议

边界网关协议BGP，是基于外部网关协议，用于不同自治系统网络之间交换路由信息的协议，广泛用于因特网。 BGP经常用于网关主机之间，主 机中的路由表包括了已知路由的列表、可达的地址和路由加权，这样就可以在路由中选择最好的通路了。当主机发现更改时，它就使用TCP进行BGP通信，发送更新了的路由信息，此时只发送列表的更新部分。BGP在局域网中通信时使用内部BGP(IBGP)。BGP—4 是最新的版本，它使管理员能够在 已知的路由策略上配置路由加权。 BGP—4可以更方便地使用无级域间路由(CIDR)，它是一种在网络中可以容纳更多地址的机制，它比外部网关协议(EGP)更新。

路由选择方法的精确描述，属于网路软件的一部分。对它的要求是正确、简单、可靠、稳定、公平和优化。

路由选择算法可分为自适应型和非自适应型两大类。自适应型的特点在于它的路由选择能在一定程度上随网路运行状态（如流量和拓扑）而改变，可避开出现异态的节点或链路。非自适应型采用静态路由选择算法。常见的非自适应型有扩散式、随机式、固定式等；而自适应型有集中式、孤立式、分布式等。

固定式是一种应用范围比较广的非自适应型路由选择算法。它是根据网路拓扑和信息流量的统计模型事先确定各节点的路由表，每个节点的路由表指明从该节点出发到某个目的节点所应该选择的输出链路以及下一节点。路由表由算法确定，而在固定式中是事先预定的。

最短路径算法为最常用的算法，它寻求在源节点和目的节点之间能沿着长度最短的路径来传送分组。这里所指的“长度”赋于特别含义，既可以是实际距离，也可以是平均时延或者链路费用。长度参数是路由表的依据，如果参数值来自网路运行的当前状态，路由表变为动态生成，这样的路由选择算法就属于自适应型。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。

算法描述如下：

1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex(G,v),i] vi∈V

2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。