路由算法分类比较.doc

路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。路由器使用路由算法来找到到达目的地的最佳路由。关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法： 总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 选择最短路由还是最佳路由；2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 　　3、采用分布式路由算法还是采用集中式路由算法； 　　4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 　　各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。　 　链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 　　metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。路由选择协议（Routing protocol） 当两台非直接连接的计算机需要经过几个网络通信时，通常就需要路由器。路由器提供一种方法来开辟通过一个网状联结的路径。路由选择协议的任务是，为路由器提供他们建立通过网状网络最佳路径所需要的相互共享的路由信息。当一个计算机发送一个分组时，在网络上网络协议栈的每一层都附加一些信息给它。在接收方的对等层协议可以读出这些信息。这些信息类似于通信会话的某些部分。网络层的协议附加路由选择信息，这可能是通过一个网络的完整的路径或是一些指示分组应该采用那条路径的优先值。发送方添加的网络层信息只能由路由器或接收方的网络层协议读取。中继器和桥接器不能识别网络层信息，只能传送和转发分组。Routing Algorithms 路由选择算法 一个路由器设备可能有两个或多个可以发送数据分组的端口。它必须有一张转发表（forwarding table）为每一个端口标明一个特定地址。早期路由器不和其它路由器交换网络上有关路由器的信息，因此，一个路由器通常沿着每条路径发送数据分组，分组 充满网络，并且发送的一些分组在网络上无休止地循环。 　　为了避免这些问题，路由器可以依赖人工编程把选择的路径输进设备。这被称为静态路由选择。动态路由选择是一个更好的方式，它依靠路由器收集网络信息和建立自己的路由表。路由器相互交换路由表，并且归并这些路由信息建立更新的路由表。从其它路由器上获得的信息，提供到网络上目的站点的路由中继（hop）数或与路径相关的费用。同时，每个路由选择设备上的路由表，应该包含大体上一致的路由选择信息。 路由选择协议基本上有两类：距离向量和链路状态，将在下面用两段文字介绍这两类协议。距离向量路由选择协议的分组传送路由是根据到接收站的hop数或费用决定的，这些信息由各相邻的路由器提供。技术上通常都遵循Bellman－Ford算法。 　　一个路由器有几个端口，每个端口都有指定的价值，这些价值是由网络管理员设定的。用使用一条线路实际费用的多少，作为一种衡量手段表明一条线路比另一条好或坏。此外，相邻的那些路由器告诉它们把分组送往目的站要花费的代价。路由器将端口的价值加到相邻路由器的价值上，如下面的例子： 　　端口1价值10 + 相邻路由器价值17＝27。 　　端口2价值20 + 相邻路由器价值5＝25。 　　端口3价值30 + 相邻路由器价值7＝37。 　　在这种情况下，路由器将通过端口2传送分组，因为它表明到接收站的代价最少。假如有必要，用邻接端口2的路由器再计算到下一个路由器的路径价值。 　　路由信息，如下一个hop的地址等都存在表中，并且路由器大约每隔30秒互相交换表。初始时，每一个网络只知道直接相连的路由器。当一个路由器得到一张表，它将表项与自己的表进行比较。根据这些信息，它用新增路由或删除路由来修改表。表中信息包含：网络号；端口号；价值度量；下一个h