理论课-路由基础[下]

安妮宝贝

路由算法（Routing Algorithms）

路由算法的不同体现在几个关键特性上。首先，算法设计者的目标影响产生的路由协议
运作方式。其次，是不同的路由算法类型。各种算法对网络和路由器资源有不同的影响
。最后，路由算法使用的各种各样的Metrics直接影响计算最佳路由。下面各部分分析这
些路由算法的性质。

设计目标

路由算法通常有下列设计目标:
最优化
简单性和低维护费用
健壮性和稳定性
迅速地收敛
灵活性
最优化
最优化指路由算法选择最佳路径位置的能力。Metrics及其权值决定最佳路径。例如，路
由算法可能考虑节点数和延迟，但计算时延迟更重要。自然地，路由协议必须严格地定
义它们的Metric计算算法.
简单性
路由算法也被设计成尽可能的简单。换句话说，路由算法必须以最少的软件和使用费用
获得高效的功能。当路由算法由软件实现，并在物理资源受限制的电脑上运行时，效率
是特别重要的，
健壮性
路由算法必须是健壮的。换句话说，在异常的或者无法预料的情况面前（诸如硬件失败
，高负载条件,和不正确的安装和使用），它们也要正确运行。因为路由器定位在网络连
接点，故障时它们能导致严重的问题。最好的路由算法经得住时间的考验，并被证明在
各种的网络条件之下能保证稳定工作。
迅速的收敛
路由算法必须飞快地收敛。收敛指所有的路由器关于最佳的路由取得一致的过程。当一
个网络事件使得路由过程失败或者成功，路由器发送路由更新消息。路由更新消息弥漫
网络，导致重新计算最佳路由，并最终使所有的路由器一致同意这些路由。路由算法收
敛过慢会产生路由循环或网络损耗。
图2-3演示了路由循环。在这个例子中，一个包在时间t1到达路由器1。路由器1已经更新
，知道到目的地的最佳路径要以路由器2为下一个节点。路由器1因此把包发送到路由器
2。路由器2还没有被更新，它认为最佳的下一个节点是路由器1。路由器2因此把包向后
发送到路由器1。这个包将要继续在二个路由器之间来回传送，直到路由器2收到它的路
由更新或者包被交换的次数超过允许的最大值。
灵活性
路由算法也应具有灵活性。换句话说，路由算法应迅速和准确地适应各种各样的网络情
况。例如，假定网络的一段失灵，多数路由算法在监测到这个问题时，要很快地为使用
该段网络的路由选择次优的路径。路由算法应被设计成能够适应变化，不论网络带宽、
路由器队列大小、网络延迟，或是别的变量。

类型
路由算法可以分为几种类型。例如：
静态或者动态
单路或者多路
平坦的或者分级的
主机智能或者路由器智能
域内或者域间
链接态或者距离向量

静态或者动态
静态路由算法刚刚称得上是一种算法。静态路由表是网络管理员在路由运行之前建立的
。它们不会改变除非网络管理员改变它们。使用静态路由的算法设计简单，适于工作在
网络交通相对可预言、网络设计相对简单的环境.
因为静态路由系统不能对网络变化做出反应，它们是一般被认为不适用于现在大型的、
不断改变的网络。90年代大多数占优势的路由算法都是动态的.
动态路由算法靠分析收到的路由更新消息来实时自调整，以适应变化的网络情况。如果
消息显示网络发生了改变，路由软件就重新计算路由，向外发送新的路由更新消息。这
些信息弥漫网络，引发路由器重新运行它们的算法来调整相应的路由表。
动态路由算法可以作为静态路由的适当补充。例如，后备路由器（一个处理所有不可路
由的包的路由器）可以是特指的。这个路由器如同不可路由的包的贮藏处，确保所有的
信息至少都以某种形式被处理。
单路或者多路
一些复杂的路由协议支持到相同目的地的多条路径。这些多路算法允许可多路复用；单
路算法则不然。多路算法的优点是明显的：它们能够提供实质性的较好的生产量和可信
度.
平坦的或者分级的
一些路由算法运作于平坦的空间，而其他的使用路由分层。在平坦的路由系统中，所有
的路由器相互平等。在分级路由选择系统中，一些路由器构成路由主干（backbone）。
包从非主干（nonbackbone）路由器发送到主干路由器，再被沿主干发送，直到到达目的
地所在区域。然后从最后的主干路由器通过一个或者更多的非主干路由器到达最终目的
地.
路由系统通常指定节点的逻辑组，称为域（domain）、自治系统（autonomous system）
或者区域（area）。在分级系统中，域中的一些路由器能够与其它域的路由器通信，而
其他的仅能够与域内的路由器通信。在非常大的网络中，会存在附加的分级层。最高分
级级别的路由器构成路由主干。
分级路由选择最主要的长处是模仿了多数公司的组织形式因而很好地支持他们的通信形
式。多数网络通讯产生于小工作组（域）的内部域内路由器只需要知道域内部的其它路
由器，
因此它们的路由算法能够简化。路由更新导致的通讯量也相应的被减少。
主机智能或者路由器智能
一些路由算法假定由源端节点决定整个路径。这通常称为源端路由（source-routing）
。在源端路由系统中，路由器仅仅担任存储转发设备，简单地发送包到那下一个节点。
其它算法假定主机对路由一无所知。这些算法要求路由器自己计算并决定路径。 前一种
系统，主机拥有路由智能。后一种系统，路由器拥有路由智能。选择主机智能路由或路
由器智能路由，其实是在权衡路径最佳性和维护性通信负荷。 主机智能系统更多地选中
较好的路由，因为他们通常在真正发出包之前就搜索所有可能的路由。然后选择系统定
义的最佳路径，同时决定整个路径。然而，常常耗费网络交通和相当的时间来完成检索
。
域内或者域间
一些路由算法仅工作在域内部；其他的工作在域内部和域之间。这二种算法类型具有不
同的性质。最佳的域内路由算法并不必然是最佳的域间路由算法。
链接态或者距离向量
链接态算法（也称短路径优先算法）向网络的所有节点散发路由信息。但各路由器仅发
送描绘它自己连接状态的那部分路由表距离向量算法（也称Bellman-Ford算法）要求各
路由器发送它整个的路由表格或者其中一部分，但只发到它相邻的路由器。实质上,链接
态算法发送短小的更新到各处，距离向量算法仅向附近的路由器发送较大的更新。因为
收敛更快，链接态算法较距离向量算法不容易产生路由循环。另一方面，链接态算法比
距离向量算法需要更强的CPU更多的记忆体。因此链接态算法的实现和支持更昂贵。忽略
它们的差别，两种算法类型在大多数的情况下都工作得很好.

Metrics

路由表包含交换软件用来选择最佳路径的信息。但是路由表又是如何构造出来的呢？他
们包含的信息具有什么样的性质呢？路由算法如何决定某路径是更可取的？
路由算法使用许多不同的Metrics来决定最佳路径。成熟的路由算法能够综合多个Metri
cs进行路径选择。
以下各项是一些Metrics：
路径长度（Path Length）
可信度（Reliability）
延迟（Delay）
带宽（Bandwidth）
负载（Load）
通讯代价（Communication Cost）
路径长度（Path Length）
路径长度是最常用的路由Metric。一些路由协议允许网络管理员给各网络链接赋以任意
的耗散值。这样，路径长度就是传输路径上各链接耗散值的总和。别的路由协议定义路
径长度为节点计数，亦即包从源到达目的地途中经过的网络设备（比如路由器）的数目

可信度（Reliability）
可信度, 在路由算法中指网络连接可信度（通常以误码率表征）。一些网络连接可能比
其他的更经常出故障。而一但故障，一些网络连接可能比别的连接更容易或者更快地被
修理。任何可信度因素都能够影响可信度级别。可信度级别通常由网络管理员指定给网
络连接。一般可为任意数值。
延迟（Delay）
路由延迟指包从源到达目的地所要求的时间。延迟取决于多种因素，包括中介网络连接
的带宽、路径上各路由器端口的包队列，中介网络连接的堵塞以及传输的物理距离。因
为关系到几个重要的变量，延迟是一种常用和有效的Metric。
带宽（Bandwidth）
带宽指链接可用的交通容量。在所有其他条件相同的情况下，10-Mbps以太网链接比64-
kbps专线更可取。尽管带宽表征链接可达到的最大传输能力，通过更大带宽连接的路由
不一定比通过较慢连接的路由更好。例如，一旦更快的链接比较忙碌，那么实际传送包
所要求的时间可能比较慢的连接要长。
负载（Load）
负载指那一个网络资源（比如一个路由器）的繁忙程度。负载能够从各种各样的参数中
计算而来，包括CPU利用率和每秒被处理的包的数目。对这些参数持续不断的监视本身也
会加重资源负担。
通讯代价（Communication Cost）
通讯代价是另一个重要的Metric。一些公司可能关心运行开支更甚于关心性能。即使线
路延迟更长，他们也会通过他们自己的线路传送包，而不是通过需要计时付费的公共线
路。
　
路由及被路由协议（Routing and Routed Protocols）

路由协议与被路由协议常常引起混淆。
被路由协议是指在网络上“被路由”的协议。这样的例子有互联网络协议（IP），DECn
et，AppleTalk，NetWare，OSI，Banyan VINES，以及Xerox Network System (XNS)。
路由协议是实现路由算法的协议。简而言之，路由协议对被路由协议在网络上的传输作
路由。这种协议的例子有内部网关路由协议（Interior Gateway Routing Protocol，I
GRP），扩展内部网关路由协议（Enhanced Interior Gateway Routing Protocol，EIG
RP），开放最短路径优先（Open Shortest Path First，OSPF），外部网关协议（Exte
rior Gateway Protocol，EGP），边缘网关协议（Border Gateway Protocol，BGP），
OSI路由（OSI Routing），先进点对点网络（Advanced Peer-to-Peer Networking），
中介系统到中介系统（Intermediate System to Intermediate System，IS-IS），以
及路由信息协议（Routing Information Protocol，RIP）。
路由协议与被路由协议将在本文中详细地讨论。