网海茫茫路何方

１．IP路由简介

　　路由就是选择一条数据包传输路径的过程。当TCP/IP主机发送IP数据包时，便出现了路由。路由器是从一个物理网向另一个物理网发送数据包的装置，路由器通常被称为网关。对于发送的主机和路由器而言，必须决定向哪里转发数据包。在决定路由时，IP层查询位于内存中的路由表。

（1）当一个主机试图与另一个主机通信时，IP首先决定目的主机是一个本地网还是远程网。

（2）如果目的主机是远程网，IP将查询路由表来为远程主机或远程网选择一个路由。

（3）若未找到明确的路由，IP用缺省的网关地址将一个数据传送给另一个路由器。

（4）在该路由器中，路由表再次为远程主机或网络查询路由，若还未找到路由，该数据包将

发送到该路由器的缺省网关地址。

　　每发现一条路由，数据包被转送下一级路由器，称为一次“跳步”（hop），并最终发送至目的主机。若未发现任何一个路由，源主机将收到一个出错信息。　

２．路由表和路由协议

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

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

３．路由协议的“理想”

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

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

４．两种路由算法

　　路由算法形式多样，得到广泛应用的有两种：距离向量算法和链路状态算法。目前大多数路由协议都是基于这两种路由算法之一。

（1） 距离向量算法（distance vector algorithm）

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

　　距离向量算法是基于下面的计算公式：

D（i，i） = 0

D（i，j） = min [d（i，k） + D（k，j）]　

　　其中，D（i，j）表示从节点（节点为网络或路由器）i到节点j的最短路径，d（i，k）表示从节点i到k的直接路径，也就是说节点i和k之间没有中介节点。具体运算步骤如下：

I　所有的路由器建有一个路由表，使系统中的所有目的地址都出现在表中。每一表项内容包括目的地址和下一站地址，记为元组（N，G）。

II　路由器周期性地向邻居发送更新分组，更新分组的内容为路由表中的所有信息。

III　邻居路由器接收处理更新分组。设更新分组来自G'，根据更新分组计算到目的地址N的路由开销为D'，如果D'应下一站地址为G'，也就是G' =G，采用新的路由，不管D'是大或小。

（2） 链路状态算法（link state algorithm）

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

　　链路状态算法，或者称为SPF（Shortest-Path First）算法，其思路可以分为以下4个部分来描述：

I．发现该路由器的邻居，获取它们的网络地址，建立相邻关系，并测量到每个相邻路由器的开销或延迟。建立相邻关系是通过发送Hello分组来实现的。

II．将用于交换的信息收集起来，构造包含这些信息的链路状态分组。创建链路状态分组的时机分两种，一种为定期创建，另一种就是当有事件发生时创建。

III．通过flood（洪泛扩散）算法，向所有的其它路由器发送该分组。如何可靠地发布链路状态分组在链路状态路由选择算法中占相当大的比重，链路状态算法实现的好坏在一定程度上取决于flood算法的优劣。

IV．根据收集到的链路状态信息，通过Dijkstra算法，计算本路由器到全网其它路由器或网络的最短距离。

［上一页］ ［下一页］