路由概述

    路由的过程可以概述为一个节点找到通往每个可能目的地的路径。路由出现在从第一层到第七层的每一层中。人们所熟悉的路由是出现在第三层(网络层)的，因此我们也只讨论第三层的IP路由。

交换路由信息的协议联接世界上的许多路由器，尽管这些路由器并不同类，通过路由表还是可以提供它们共同的网络视图。路由表为 路由器存储了到达网络上任一目的地所需要的一切必要的信息。

路由协议

    各种各样的路由协议被用来填写网络中的路由表。象BGP，OSPF，RIP和ISIS这样的协议可以传输给所有的路由器一个正确和一致的网络视图。

路由协议想要实现目标

    你能够想象如果每个路由器都存储从它的节点所能到达的每个目标点所需的信息，很可能该路由器会积累一张庞大的路由表。由于物理上(cpu，内存)的限制路由器很难有时就根本不可能处理一个庞大的路由表。因此在不影响到达每个目的地的能力的情况下，我们要使路由表最小化。例如，一个路由器通过连接到另一个路由器一个DS1链路连接到Internet，那么这个路由器可以将Internet上所有节点的信息都存储，或者它也可以将所有DS1串行链路外的非本地的信息都不存储。也就是说路由器没有在它的路由表中存储任何有关数据“包”要寻找的非本地网络目的地的信息，而是将这些“包”发送到串行链路另一端的路由器，由这个路由器来提供必要的信息。我们常把像本例中我们所说的在串行DS1链路另一端的路由器称为“Gateway of Last Resort”。这种简单的小把戏可以替路由表节省30个数量级的条目。路由信息没有必要被过于频繁地在路由器之间交换。通常路由表中的搅拌器给任何路由器所能提供的贫乏的内存和CPU施加了许多不必要的压力。信息的复制不应该影响路由器的转发操作。尽管没有必要每毫秒都刷新路由表，当然也不能每隔一个星期才刷新一次路由表。路由的一重要的目标就是为主机提供能够准确反映当前网络状态的一张路由表。

路由器最重要的操作是将接收的包发送到正确的路径。未经路由的包可能会导致数据丢失。而路由表的不一致将会导致路由环路并使某个数据包在两个相邻的界面之间被循环发送。

人们十分希望所有的路由器都能有快速的收敛性。收敛性可以被非正式地定义为计量所有路由器获得一致的网络视图的速度的单位。人们希望有极小的收敛时间，因为如此网络上的每个路由器即使在网络拓扑(即网络视图)被严重改变的情况下也能准确地反映当前的网络拓扑。当网络拓扑被改变时，每个路由器必须传输数据以帮助其它路由器来收敛出正确的网络视图。但是在刷新路由表时快速收敛也存在着它的问题。如果一个链路在迅速地振动(一会儿断开，一会儿合上)，它会产生大量的安装和撤销的请求。这个链路最终将会耗尽网络上每个路由器的资源，因为其它路由器被强迫快速安装或撤消这个路由。因此，即使快速收敛是路由协议的目标，它也不是所有网络难题的万能药。

距离矢量路由

    距离矢量路由协议向路由器的所有邻居分发一张记录形式为<目标，开销>的列表。这些记录为网络中的每个非本节点的其它节点赋上了开销这个值。值得注意的是这些信息只分发给源路由器的邻路由器。这里的邻路由器常常是物理上的，但在eBGP中也有适用于逻辑上的情况。开销的意思是从源路由器到目标节点的链路开销的总和。源路由器定期地刷新它的距离矢量记录并把记录分发给它的邻路由器。邻路由器将过去接收到的记录与现在的比较，如果过去的开销较小路由器将沿过去接收的距离矢量记录所指的路径发送输出。

许多距离矢量在实际使用时将会碰到无穷大的问题。例如，我们假设所有的链路都有一个开销单元并且每一对相邻节点之间的链路对应一个单元。如果路由器X连接到路由器Y并且路由器Y连接到路由器Z如图1，我们将会发现无穷大的问题。Y知道到Z要有1个单元的开销并且X知道到Z要2个单元的开销。假设链路YZ关闭，这条链路的开销就成为无穷大(如图2)。现在Y知道到达Z的开销是无穷大，它就将这个距离矢量路由发送给X。假设X这时发送给Y一个距离矢量路由声称它到达Z要2个单元的开销。现在Y就会认为它能通过X到达Z，它就发送给X一个刷新的距离矢量路由声称它到达Z的开销是3个单元(如 图3)。请注意X没有想到Y发给它的这个距离矢量路由是由它发送给Y的那个距离矢量路由推算来的。这就是距离矢量路由的严重缺陷，在它们未改进的结构中不包含路由障碍的信息。正如图例所示路由器将会不断改变到Z的路径信息。X和Y这两个路由器将会永远交换这个有关Z路由器的路径信息或者直到开销单元的值到达某一个事先约定的无穷大的值(例如，在RIP中是15)。

X--------------------Y--------------------Z

Y:1                  X:1                  X:2
Z:2                  Z:1                  Y:1

                   [ 图一 ]
                     
X--------------------Y--------* *---------Z

Y:1  <-------------  Z:无穷大
Z:2  ------------->  X:1

                   [ 图二 ]
                     
X--------------------Y--------* *---------Z

Z:无穷大(从 Y) -> X:1
Y:1  <-------------  Z:3

                   [ 图三 ]
                      
     使用路径矢量路由就可以解决无穷大的问题。每个距离矢量也包括他所通过的路径(如图4)。路由器如果接收到一个路径矢量中包含自己的刷新记录，路由器将不会刷新该记录(如图5)。边界网关协议(The Border Gateway Protocol)就使用了上述的方法以解决无穷大的问题。很明显如果你想使路由表包含路由器所传输的AS(Autonomous Systems on the internet)路径信息，你将必须要向路由表中添入更多的信息。因此BGP的设计者决定牺牲一点路由器能够承受的起的存储空间和处理能力。

X--------------------Y--------------------Z

Y:1 (Y)              X:1 (X)              X:2 (YX)
Z:2 (YZ)             Z:1 (Z)              Y:1 (Y)

                   [ 图四 ]
                   
X--------------------Y--------* *---------Z

Y:1 (Y)              X:1 (X)
Z:2 (Y Z)            Z:infinity

                   [ 图五 ]

    另一个无穷大问题的解决之道是分离范围。主要思想是，如果邻路由器处在通往目的地的路径上的第二个节点，路由器就不向该邻路由器广播该路径。这个解决的办法可以用刚才的例子来说明。因为到Z的路径是从X通过Y再到Z，又因为Y是X的邻路由器，所以该路径从X广播时Y不被广播。

链路状态路由

   一个路由器在使用链路状态路由时，它将会向网络上所有其它的路由器分发它到它邻路由器的距离。这就使每个路由器不用知道从某一源节点到目的节点的开销，该路由器就可以产生一张路由表。环路的问题不会出现，因为每个路由器都拥有整个网络的拓扑。主要思想是一个路由器产生有3个部分的记录包含源路由器(它自己)、邻路由器和到邻路由器的开销。因此，如果路由器A通过一条开销为3的链路连接到路由器B，并且路由器A通过一条开销为5的链路连接到路由器C，那么路由器将会向网络上所有的路由器广播链路状态包(LSPs)和。每个路由器将可以从接收到的LSPs中推算出一条通向目的节点的最短路径。

    很显然，LSP是收敛过程中的一个组成部分。如果向网络中加入了错误的LSP。将会导致错误的路由信息(会使包沿比原来更长的路径传输)甚至产生路由黑洞。如果路由器C向其它路由器广播一条到他的邻路由器的路径信息，但当该链路断开时路由器C撤回了刚才的广播。不幸的是第二个LSP先到而第一个LSP先到，这时其它路由器的路由表就不能正确地反映网络的拓扑，而只能等到另一个正确的LSP来到。

    为了解决这个问题，LSP引进了序列码。因此网络上所有的路由器都会以一些值作为起始值来初始化他们的序列码，然后在广播他们的LSP。这就解决了刚才的问题。

   当使用序列码时会碰到序列码空间是有限这一问题。LSPs可以用的序列码都被设置成有限值。因此，当序列码到达最大值后，有要从最小值重新开始。这就给路由器在比较链路状态的当前记录和刷新记录时带来困难，因为序列码大的有优先权。为了解决这个问题，可以为LSP定义一个最大老化时间。也就是说，如果路由器在X段时间内没有收到刷新记录，它就将现有的记录丢弃而去等待更新的记录。要注意必须使到目的地的路径信息无效。例如，当路由器Y连向某一局网的链路断开时，路由器Y向路由器Z广播了这条链路的信息，这时局网中的路由器们此时还在认为它们仍可以到达Z。如果它们在最大老化时间内接收不到刷新记录，它们就会假设到Y的链路已经不可达。这样所有的路由器的路由表才会一致，路由器Y和Z也可以使用有限的序列码。

    序列码的初始化也是这个问题中另一个重要的方面。假设路由器Y重起了，而此时网络又开始重新计算路径。当该路由器的链路状态协议开始工作，它必须知道重新初始化它的序列码为何值以使它和其它路由器保持一致。因此，它就广播一个带有特别的初始化集合的路径信息。这条记录会告诉其它路由器它需要那个序列码，并且其它路由器会告诉它。