路由选择协议的算法

joshualiunsw 2010-07-09

路由选择协议的应用,在很多大型网络中有着举足轻重的作用。为了让大家更好地掌握这部分知识,我们对路由选择协议的基础内容进行了归纳。包括它的冗余以及路由选择算法等原理内容。路由器提供一种方法来开辟通过一个网状联结的路径。这种网状网络提供了冗余路径以调整通信负载或倒行链路,通常有一条路径由于费用、速度或避开拥挤等理由优选于其它路径。路由选择协议的任务是,为路由器提供他们建立通过网状网络最佳路径所需要的相互共享的路由信息。

当一个计算机发送一个分组时,在网络上网络协议栈的每一层都附加一些信息给它。在接收方的对等层协议可以读出这些信息。这些信息类似于通信会话的某些部分。网络层的协议附加路由选择信息,这可能是通过一个网络的完整的路径或是一些指示分组应该采用那条路径的优先值。发送方添加的网络层信息只能由路由器或接收方的网络层协议读取。中继器和桥接器不能识别网络层信息,只能传送和转发分组。

Routing Algorithms 路由选择算法

一个路由器设备可能有两个或多个可以发送数据分组的端口。它必须有一张转发表(forwarding table)为每一个端口标明一个特定地址。早期路由器不和其它路由器交换网络上有关路由器的信息,因此,一个路由器通常沿着每条路径发送数据分组,分组充满网络,并且发送的一些分组在网络上无休止地循环。

为了避免这些问题,路由器可以依赖人工编程把选择的路径输进设备。这被称为静态路由选择。动态路由选择是一个更好的方式,它依靠路由器收集网络信息和建立自己的路由表。路由器相互交换路由表,并且归并这些路由信息建立更新的路由表。从其它路由器上获得的信息,提供到网络上目的站点的路由中继(hop)数或与路径相关的费用。同时,每个路由选择设备上的路由表,应该包含大体上一致的路由选择信息。在使用远程通信链路的广域网中,规整化路由选择是基本的,但是必须在远程通讯链路迅速改变(例如,线路断)时,很快地调整到新的路径拓扑。一个典型的Internet可能由2个、10个甚至50个路由器组成,这些路由器可以通过拨号异步链路或专用高速数字线路(如T1)互相连接。对于一个在网络上传送的数据分组,它们到达路由器时由路由器查看目的地址,并沿着最佳或非常合适的路由将分组发送到接收站。这样一条路由取决于所用的路由选择算法类型。路由选择协议基本上有两类:距离向量和链路状态,将在下面用两段文字介绍这两类协议。

距离向量路由选择协议

距离向量路由选择协议的分组传送路由是根据到接收站的hop数或费用决定的,这些信息由各相邻的路由器提供。技术上通常都遵循Bellman-Ford算法。一个路由器有几个端口,每个端口都有指定的价值,这些价值是由网络管理员设定的。用使用一条线路实际费用的多少,作为一种衡量手段表明一条线路比另一条好或坏。此外,相邻的那些路由器告诉它们把分组送往目的站要花费的代价。路由器将端口的价值加到相邻路由器的价值上,如下面的例子:端口1价值10 + 相邻路由器价值17=27。端口2价值20 + 相邻路由器价值5=25。端口3价值30 + 相邻路由器价值7=37。在这种情况下,路由器将通过端口2传送分组,因为它表明到接收站的代价最少。假如有必要,用邻接端口2的路由器再计算到下一个路由器的路径价值。

下一个hop的地址

价值度量是路由器向前传送分组到网中下一个路由器时选择路径所用的量值。通用距离向量路由选择协议有:路由选择信息协议(RIP)是一个首先在Xerox网络系统(XNS)中实现,而后又在Novell的NetWare中实现的距离向量路由选择协议。内部网关路由选择协议(IGRP)是由Cisco开发的距离向量路由选择协议。路由选择表维护协议(RTMP)是一个在两个AppleTalk区中选取最佳路径的Apple协议,大约每10秒广播一次。

距离向量路由选择不适合于有几百个路由器的大型网或经常要更新的网。在大型网中,表的更新过程可能过长,以至于最远的路由器的选择表不大可能与其它表同步更新。在这种情况下,链路状态路由选择更可取些。另外,链路状态协议能够为安全起见把机密信息隔离在特殊区域,或避开网上正在进行计算机辅助设计(CAD)、多媒体通讯等拥挤区域。并且,路由选择信息表在必要时进行交换而不是规律性地交换,这样可以减少网络上的信息流量。

相关推荐