路由协议的实现算法

《路由协议的实现算法》由会员分享，可在线阅读，更多相关《路由协议的实现算法（6页珍藏版）》请在金锄头文库上搜索。

1、路由协议的实现算法路由协议的实现算法 刷钻代码 http:/ 现信息交换方面的重要作用逐渐被人们所认知。本文将以 Cisco 路由器为例简要阐述路由器之间交换路由信息的两种 主要算法：距离向量法（Distance Vector Routing）和链 路状态算法（Link-State Routing）。一、 路由协议（Routing Protocol）路由协议是路由器之间实现路由信息共享的一种机制，它 允许路由器之间相互交换和维护各自的路由表。当一台路由 器的路由表由于某种原因发生变化时，它需要及时地将这一 变化通知与之相连接的其他路由器，以保证数据的正确传 递。路由协议不承担网络上终端用户之间

2、的数据传输任务。 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、 静态路由静态路由是指由网络管理员手工配置的路由信息。当网络 的拓扑结构或链路的状态发生变化时，网络管理员

3、需要手工 去修改路由表中相关的静态路由信息。静态路由信息在缺省 情况下是私有的，即它不会传递给其他的路由器。当然，你 也可以通过对路由器进行设置使之成为共享的。静态路由一 般适用于比较简单的网络环境，因为在这样的环境中，网络 管理员易于清楚地了解网络的拓扑结构，便于设置正确的路 由信息。下面是两个适合使用静态路由的实例。在左图中，假设 Network 1之外的其他网络需要访问 Network1时必须经过路由器 A 和路由器 B，则可以在路由器 A 中设置一条指向路由器 B 的静态路由信息，这样做的好处 在于可以减少路由器 A 和路由器 B 之间 WAN 链路上的数据传 输量，因为使用静态路由后

4、，路由器 A 和 B 之间没有必要进 行路由信息的交换。在一个支持 DDR（dial-on-demand routing）的网络中， 拨号链路只在需要时才拨通，因此不能为动态路由信息表提 供路由信息的变更情况。 这种情况下， 也适合使用静态路由。使用静态路由的另一个好处在于其安全保密性。使用动态 路由时，需要路由器之间频繁地交换各自的路由表，而通过 对路由表的分析可以揭示网络的拓扑结构和网络地址等信 息，因此，出于安全方面的考虑也可以采用静态路由。在大型和复杂的网络环境中，往往不宜采用静态路由，一 方面因为网络管理员难以全面地了解整个网络的拓扑结构； 另一方面，当网络的拓扑结构和链路状态发生变

5、化时，需要 大范围地调整路由器中的静态路由信息，这一工作的难度和 复杂程度是可想而知的。2、 动态路由动态路由使路由器能够自动地建立起自己的路由表，并且 能够根据情况的变化适时地进行调整。动态路由机制的运做依赖路由器的两个基本功能：对路由表的维护路由器之间适时的路由信息交换前面提到，路由器之间的路由信息交换是基于路由协议实 现的。通过左图可以直观地看到路由信息交换的过程。交换 路由信息的最终目的在于通过路由表找到一条数据交换的 “最佳”路径。每一种路由算法都有其衡量“最佳”的一套原则。大多数算法使用一个量化的参数来衡量路径的优劣， 一般说来，参数值越小，路径越好。该参数可以通过路径的 某一特性

6、进行计算，也可以在综合多个特性的基础上进行计 算，几个比较常用的特征是：路径所包含的路由器结点数（hop count）网络传输费用（cost）带宽（bandwidth）延迟（delay）负载（load）可靠性（reliability）最大传输单元 MTU（maximum transmission unit）三、路由协议的实现算法本文主要介绍两种基本的路由算法，即距离向量法 （Distance Vector Routing）和链路状态算法（Link-State Routing）。路由协议和路由算法只针对动态路由。（一）、距离向量法（Distance Vector Routing）在距离向量法中，

7、相邻路由器之间周期性地相互交换各自 的路由表备份。当网络拓扑结构发生变化时，路由器之间也 将及时地相互通知有关变更信息。在图3中，每一个路由器从与之直接相邻的路由器那儿获 得对方的路由表。例如，路由器 B 从路由器 A 和 C 那里获得 路由信息后，根据其所得到的信息对自己的路由表进行加 工，然后将加工后的路由表再传送给路由器 A 和 C。路由器 通过这种方法不断地积累路由信息，直到最终收敛为止。值 得一提的是，在这种算法中，路由器不可能获知整个网络确 切的拓扑结构。路由器是如何根据收到的路由信息对自身路由表进行加工，又是如何达到收敛的呢？1、路由表的建立与更新在图4中，有三个路由器：A、B

8、和 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,

9、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所示的路由表。概括地说来，距离向量算法要求每一个路由器把它的整个 路由表发送给与它直接连接的其他路由器。路由表中的每一 条记录都包括目标逻辑地址、相应的网络接口和该条路由的 向量距离。当一个路由

10、器从它的邻居那儿收到更新信息时， 它将更新信息与本身的路由表相比较，如果它能从邻居那儿 找到一条它以前不曾知道的新的路由或是找到一条比当前 路由更好的路由时，路由器会对路由表进行更新：将从该路 由器到邻居之间的向量距离与更新信息中的向量距离相加 作为新路由的向量距离。上例中将相邻路由器之间的向量距 离设置为1。2、收敛所谓收敛，是指直接或间接交换路由信息的一组路由器在 网络的拓扑结构方面或者说在网络的路由信息方面达成一 致。路由协议必须通过某种算法使各路由器尽快达到收敛状 态。要实现收敛，必须解决路由器之间的路由环路（Routing Loops）问题。下面的例子比较直观地讲述了路由环路问题 的

11、产生。假设在图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

12、.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）这种方法规定，路由器必须有选择地将路由表中的路由信 息发送给相邻的其他路由器，而不是发送整个路由表。具体一点，即对于某条路由信息来说，不将它发送给

13、该条路由信 息的来源方向。仍以图4为例。图5是图4中路由器 B 的路由 表，通过图5中的注释可以看到，每一条路由信息都不通过 该条路由信息中所指的网络端口向外发送。这样就可以避免路由环路的产生。2） 定义一个最大值定义一个向量距离的最大值，可以在一定程度上防止形成 路由环路，例如 RIP 协议定义 Hop Count 的最大值为16。使 用这种方法，路由协议在向量距离超过协议允许的最大值 前，允许路由环路的存在，一旦路由信息的向量距离超过规 定的最大值，该路由信息将被标记为不可到达。 与此相关 的另外一个概念是 TTL（Time To Live）。TTL 是一个包含 在数据包中的参数，数据包每经过一次路由器的路由处理， TTL 值减1，当 TTL 值等于0时，路由器将放弃对该数据包的 处理，这样会避免数据包在某个环路中无休止的传递。（3） 挂起计数器（Hold-Down Timers）所谓挂起计 数器是指路由器需要将某些可能导致路由环路的网络状态 的变化保留一段时间，在这段时间内，路由器将视情况对这 些网络状