伴随着网络规模的不断扩大，路由器在沟通子网连接和实现信息交换方面的重要作用逐渐被人们所认知。本文将以Cisco路由器为例简要阐述路由器之间交换路由信息的两种主要算法：距离向量法(Distance Vector Routing)和链路状态算法(Link-State Routing)。

　　一、 路由协议(Routing Protocol)

　　路由协议是路由器之间实现路由信息共享的一种机制，它允许路由器之间相互交换和维护各自的路由表。当一台路由器的路由表由于某种原因发生变化时，它需要及时地将这一变化通知与之相连接的其他路由器，以保证数据的正确传递。路由协议不承担网络上终端用户之间的数据传输任务。Cisco路由器中用于TCP/IP的路由协议包括RIP(路由信息协议，Routing Information Protocol)、IGRP(内部网关路由协议，Interior Gateway Routing Protocol)、OSPF(Open Shortest Path First)、NLSP(Netware链路服务协议，Netware Link Services Protocol)和EIGRP(增强IGRP)。

　　二、 静态路由和动态路由的概念

　　1、 静态路由

　　静态路由是指由网络管理员手工配置的路由信息。当网络的拓扑结构或链路的状态发生变化时，网络管理员需要手工去修改路由表中相关的静态路由信息。静态路由信息在缺省情况下是私有的，即它不会传递给其他的路由器。当然，你也可以通过对路由器进行设置使之成为共享的。静态路由一般适用于比较简单的网络环境，因为在这样的环境中，网络管理员易于清楚地了解网络的拓扑结构，便于设置正确的路由信息。下面是两个适合使用静态路由的实例。

　　在上图中，假设Network 1之外的其他网络需要访问Network1时必须经过路由器A和路由器B，则可以在路由器A中设置一条指向路由器B的静态路由信息，这样做的好处在于可以减少路由器A和路由器B之间WAN链路上的数据传输量，因为使用静态路由后，路由器A和B之间没有必要进行路由信息的交换。

　　在一个支持DDR(dial-on-demand routing)的网络中，拨号链路只在需要时才拨通，因此不能为动态路由信息表提供路由信息的变更情况。这种情况下，也适合使用静态路由。

　　使用静态路由的另一个好处在于其安全保密性。使用动态路由时，需要路由器之间频繁地交换各自的路由表，而通过对路由表的分析可以揭示网络的拓扑结构和网络地址等信息，因此，出于安全方面的考虑也可以采用静态路由。

　　在大型和复杂的网络环境中，往往不宜采用静态路由，一方面因为网络管理员难以全面地了解整个网络的拓扑结构;另一方面，当网络的拓扑结构和链路状态发生变化时，需要大范围地调整路由器中的静态路由信息，这一工作的难度和复杂程度是可想而知的。

　　2、 动态路由

　　动态路由使路由器能够自动地建立起自己的路由表，并且能够根据情况的变化适时地进行调整。

　　动态路由机制的运做依赖路由器的两个基本功能：

　　对路由表的维护

　　路由器之间适时的路由信息交换

　　前面提到，路由器之间的路由信息交换是基于路由协议实现的。通过左图可以直观地看到路由信息交换的过程。交换路由信息的最终目的在于通过路由表找到一条数据交换的“非常好的”路径。每一种路由算法都有其衡量“非常好的”的一套原则。大多数算法使用一个量化的参数来衡量路径的优劣，一般说来，参数值越小，路径越好。该参数可以通过路径的某一特性进行计算，也可以在综合多个特性的基础上进行计算，几个比较常用的特征是：

　　路径所包含的路由器结点数(hop count)

　　网络传输费用(cost)

　　带宽(bandwidth)

　　延迟(delay)

　　负载(load)

　　可靠性(reliability)

　　最大传输单元MTU(maximum transmission unit)

　　三、路由协议的实现算法

　　本文主要介绍两种基本的路由算法，即距离向量法(Distance Vector Routing)和链路状态算法(Link-State Routing)。路由协议和路由算法只针对动态路由。

　　(一)、距离向量法(Distance Vector Routing)

　　在距离向量法中，相邻路由器之间周期性地相互交换各自的路由表备份。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。

　　在图3中，每一个路由器从与之直接相邻的路由器那儿获得对方的路由表。例如，路由器B从路由器A和C那里获得路由信息后，根据其所得到的信息对自己的路由表进行加工，然后将加工后的路由表再传送给路由器A和C。路由器通过这种方法不断地积累路由信息，直到最终收敛为止。值得一提的是，在这种算法中，路由器不可能获知整个网络确切的拓扑结构。路由器是如何根据收到的路由信息对自身路由表进行加工，又是如何达到收敛的呢?

　　1、路由表的建立与更新

　　在图4中，有三个路由器：A、B和C。路由器A的两个网络接口E0和S0分别连接在10.1.0.0和10.2.0.0网段上;路由器B的两个网络接口S0和S1分别连接在10.2.0.0和10.3.0.0网段上;路由器C的网络接口S0和E0分别连接在10.3.0.0和10.4.0.0网段上。

　　如图4中各路由器路由表的前两行所示，通过路由器的网络接口到与之直接相连的网段的网络连接，其向量距离设置为0。这即是最初的路由表。

　　当路由器B和A以及B和C之间相互交换路由信息后，它们会更新各自的路由表。例如，路由器B通过网络端口S1收到路由器C的路由信息(10.3.0.0,S0,0)和(10.4.0.0,E0,0)后，在自己的路由表中增加(10.4.0.0,S1,1)这样一条路由信息，表示通过路由器B的网络接口S1可以访问到10.4.0.0网段，其向量距离为1，该向量距离是在路由器C的基础上加1获得的。同样的道理，路由器B还会产生一条(10.1.0.0,S0,1)的路由，这条路由是通过网络端口S0从路由器A获得的。如此反复，直到最终收敛，形成图4所示的路由表。

　　概括地说来，距离向量算法要求每一个路由器把它的整个路由表发送给与它直接连接的其他路由器。路由表中的每一条记录都包括目标逻辑地址、相应的网络接口和该条路由的向量距离。当一个路由器从它的邻居那儿收到更新信息时，它将更新信息与本身的路由表相比较，如果它能从邻居那儿找到一条它以前不曾知道的新的路由或是找到一条比当前路由更好的路由时，路由器会对路由表进行更新：将从该路由器到邻居之间的向量距离与更新信息中的向量距离相加作为新路由的向量距离。上例中将相邻路由器之间的向量距离设置为1。

　　2、收敛

　　所谓收敛，是指直接或间接交换路由信息的一组路由器在网络的拓扑结构方面或者说在网络的路由信息方面达成一致。路由协议必须通过某种算法使各路由器尽快达到收敛状态。

　　要实现收敛，必须解决路由器之间的路由环路(Routing Loops)问题。下面的例子比较直观地讲述了路由环路问题的产生。假设在图4中，网络10.4.0.0发生故障，在网络发生故障前，路由器A、B、C的路由表已经收敛为图4的状态。情况按照下面的描述一步步发生：

　　(1)网络发生故障后，路由器C检测到故障，停止通过接口E0向外发送数据包，并通过接口S0通知路由器B。在路由器A没有收到故障通知前，它仍然相信可以通过路由器B访问到10.4.0.0(路由器A路由表的最后一行)，这条路径的距离为2。

　　(2)由于路由器B的路由表中指示有一条通往10.4.0.0的路径，因此，如果路由器B在收到路由器C的故障通知前将路由表发送到C的话，C会认为通过B可以访问10.4.0.0,并在此基础上修改自己的路由表，将路由表中第二条记录修改为(10.4.0.0,S0,2),其中S0表示通过接口S0可以访问10.4.0.0,其距离为2。

　　(3)这样一来，路由器A、B、C都认为通过其他的路由器存在着一条通往10.4.0.0的网络路径，结果导致目标地址为10.4.0.0的数据包在这三个路由器之间来回地传递，从而造成一条路由环路。

　　解决路由环路问题可以采用以下几种方法：

　　(1) 水平分割(split horizon)

　　这种方法规定，路由器必须有选择地将路由表中的路由信息发送给相邻的其他路由器，而不是发送整个路由表。具体一点，即对于某条路由信息来说，不将它发送给该条路由信息的来源方向。仍以图4为例。图5是图4中路由器B的路由表，通过图5中的注释可以看到，每一条路由信息都不通过该条路由信息中所指的网络端口向外发送。

　　这样就可以避免路由环路的产生。

　　(2) 定义一个最大值

　　定义一个向量距离的最大值，可以在一定程度上防止形成路由环路，例如RIP协议定义Hop Count的最大值为16。使用这种方法，路由协议在向量距离超过协议允许的最大值前，允许路由环路的存在，一旦路由信息的向量距离超过规定的最大值，该路由信息将被标记为不可到达。 与此相关的另外一个概念是TTL(Time To Live)。TTL是一个包含在数据包中的参数，数据包每经过一次路由器的路由处理，TTL值减1，当TTL值等于0时，路由器将放弃对该数据包的处理，这样会避免数据包在某个环路中无休止的传递。

　　(3) 挂起计数器(Hold-Down Timers) 所谓挂起计数器是指路由器需要将某些可能导致路由环路的网络状态的变化保留一段时间，在这段时间内，路由器将视情况对这些网络状态的变化所产生的路由信息进行更改。下面看一下挂起计数器是如何工作的：

　　当一个路由器从它的邻居那儿收到以前某个可访问的网络现

　　在变为不可访问的信息时，路由器将指向该网络的路由设置为不可访问，同时启动计数器。

　　如果在计数器到期前，该路由器又从同一个邻居那儿收到该网络可以访问的信息，则它会重新将网络标记为可访问，并删除计数器。

　　如果该路由器从另外一个邻居那儿收到一条比原路由更好的访问该网络的路由信息，它同样将该网络标记为可访问，以新的路由替代原路由，并删除计数器。

　　如果在计数器到期前，该路由器从另外一个邻居那儿收到一条访问该网络的比原路由差的路由信息，这条信息将被忽略。这样做能够使“网络不可访问”的信息有更多的时间在整个网络上传播。

　　计数器到期后，该路由标记为不可到达，如果这时收到该网络可以访问的路由信息，路由器的处理方式同上。

　　计数器计数时间的长短应该略大于路由信息传遍整个网络所需的时间。

　　(4) 触发式更新(Triggered Updates)

　　触发式更新在这里已经不是新概念，因为我们在前面谈到路由器之间的路由信息交换和上述三种解决路由环路的方法时，已经不止一次地使用了这一概念，尽管那时没有明确这种提法。简单的说，触发式更新是指路由器之间不单纯按照预定的时间周期进行路由信息交换，而是在路由表发生变化的时候及时地进行路由信息交换。触发式更新普遍地应用在各种路由协议中。

　　一般说来，路由表在没有发生变化的情况下，将按照预定的时间周期进行交换，例如IP RIP协议规定路由器之间每隔30秒交换一次路由信息，IPX RIP协议则规定为60秒。但是当路由表由于某种原因发生变化时，路由器立刻将路由表的变化情况通知邻近的路由器，再由它们去通知其他的路由器，这样一波接一波，在不发生意外的情况下就可以将该路由的变化通知到网络中所有的路由器。意外情况包括路由更新信息在网络传输过程中的丢失或者路由更新信息没有及时地发出，这都有可能导致路由环路的产生，譬如在介绍“收敛”时所举的例子。

　　触发式更新经常与挂起计数器技术结合在一起来解决路由环路问题。(二)链路状态算法(Link-State Routing)

　　链路状态算法，有时也称为最短路径优先算法(SPF-Shortest Path First)。与向量距离算法不同的是，这种算法需要每一个路由器都保存一份最新的关于整个网络的网络拓扑结构数据库，因此路由器不仅清楚地知道从本路由器出发能否到达某一指定网络，而且在能到达的情况下，还能选择出最短的路径以及使用该路径将经过哪些路由器。使用链路状态算法的路由协议有NLSP，OSPF和IS-IS。

　　链路状态算法使用LSP(链路状态数据包，Link-State Packets)，网络拓扑数据库，SPF路径选择算法，SPF树，最终计算出从该路由器到其他目标网络的最短路径，这些路径就构成了路由表。在算法中，需要给每个路由器一个唯一的名字或标识。

　　1、 链路状态网络发现机制 该机制用于创建整个网络的一幅全景图，所有的路由器都保存该图的一个副本，从而保持一致。其具体工作步骤如下：

　　(1)每个路由器都必须知道它的邻居是谁，这一点需要相邻的路由器之间互相通知。

　　(2)每个路由器都将LSP(链路状态数据包)发送给网络上其他的路由器，LSP的内容包括该路由器通过哪些网络与哪些路由器直接连接，以及相应连接的传输代价。以图4中所示的网络为例，路由器B向外发送的LSP包括((B,A,10.2.0.0),(B,C,10.3.0.0)),表示B通过10.2.0.0与A连接，通过10.3.0.0与C连接(这里仍然假设相邻路由器之间的传输代价为1)。

　　(3)下一步，路由器将根据收到的LSP逐步地构建起网络的拓扑数据库(即SPF树，树的根接点为该路由器本身)。

　　(4)接下来，根据网络的拓扑结构数据库来判断目标网络是否可到达及其最短路径(常用算法为Dijikstra算法)。

　　(5)路由器将第4步计算出的到这些目标网络的最短路径及其所使用的该路由器的网络端口添加到路由表中。

　　(6)链路状态算法要求各路由器的网络拓扑结构数据库要一致。因此当链路状态发生变化时，最先检测到这一变化的路由器需要将变化的情况发送给其他的路由器。每当路由器收到新的LSP，它都会重新计算最短路径并更新路由表，这样才能保证各路由器在网络拓扑结构方面重新达成一致。

　　2、考虑的因素

　　在采用链路状态算法时，应当考虑以下两方面的因素：

　　路由器的存储空间和处理能力

　　由于采用链路状态算法时路由器不但要保存来自其他路由器的LSP，而且还要保存网络的拓扑结构和路由表，所以其存储空间一定要大。另外，根据SPF树计算最短路径的算法较为复杂，因此要求路由器的处理能力要强。

　　带宽

　　在建立SPF树的最初阶段，有大量的LSP需要通过网络进行传输，因此对网络带宽的要求较高。如果带宽不够，不仅影响路由器收敛的速度，而且会影响正常的数据传输。

　　3、可能出现的问题及解决办法

　　与距离向量算法类似的是，链路状态算法同样必须保证所有的路由器能够收到所有必需的LSP。图6给出了一个可能发生问题的案例。 假设路由器C首先检测到C和D之间的Network 1发生故障，那么象前面说的那样，路由器C将把该故障情况以LSP的方式发送给网络上的其他路由器B、D、和A(为了讲述方便，称该LSP为LSP1)。假设Network 1很快地就恢复了正常，而且路由器D先检测到，那么路由器D将把Network 1恢复正常的情况以LSP的形式再发送给路由器A、C和B(称之为LSP2)。如果由于某种原因(比如不同网络的传输速度不同或传输路径长度不同等)，LSP2先于

LSP1到达路由器A。这时，问题就出现了，路由器A究竟应该把哪一个LSP作为反映最终情况的LSP呢?

　　也许大家会说这里的巧合也太多了吧!其实不然，在实际的应用中，网络的拓扑结构要复杂的多，而且各方面因素的影响也很多，比如：路由器启动顺序的先后将影响到LSP发送的顺序，大型网络中不同子网的网络传输速度也可能有较大差别等等。

　　链路状态算法可以采用以下几种技术来解决这些潜在问题:

　　延长LSP的发送周期。

　　以多点发送LSP(Multicast)代替广播发送LSP(Broadcast)。

　　在由多个LAN互连组成的网络中，可以指定一个或多个路由器用于存放各路由器发送的LSP，其他的路由器通过这些指定路由器获得一致的拓扑数据。

　　在大型网络中，可以设定一个由不同区域组成的层次结构。某一级区域中的路由器不必存储和处理来自不同区域路由器的LSP。

　　使用LSP时间戳、顺序号等手段来解决LSP发送过程中的顺序问题。

　　(三)两种算法的比较

　　上述两种算法的差别基本上可以归结为下表中的四点,可以以此作为具体应用中选择路由协议的技术依据。