计算机网络原理：一般特性与分类

由上节的分析可知，无论是数据报的发送转发过程，还是虚电路的呼叫建立过程，子网都要对分组进行出站线路的选择。这种选择须按照一定的要求和条件进行，这就是所谓的路由选择（Routing），也称之为寻径。由于子网能为源主机和目的主机之间提供多条传输路径，故适当地选择路由可使网络获得较好的运行特性，如较高的吞吐率、较小的延迟以及较高的可靠性等。因此，要求路由选择功能具有正确、简单、可靠、稳定、公平和最优化等特性。路由选择算法正是依据这些特性进行设计和评价的。

正确性不言而喻，但人们往往对简单性要求不以为然。事实上，因简单的算法不仅易于实现、运算开销少，而且易于理解易于发现存在的问题并予以改进，在日益复杂化的网络中更显得重要。可靠性和稳定性是一对矛盾。当网络出现故障或局部过载时，可靠性要求路由选择方法能在不损失分组或断开虚电路的前提下，把分组可靠地投送到目的地，而稳定性则要求路由算法能平稳地处理路由选择，以使子网内部的信息流量在全局是稳定的。这二者之间难以折衷，要么对异常事件反应太慢，要么将经受从一个极端到另一个极端的反复周折。例如，为了对第一个区域的过载作出反应，网络的路由选择算法将大多数负载调往第二区域，致使第二区域过载，而此时第一区域却又利用得不足，从而又引起第二次转移。这种不断的转移可能致使分组在子网中兜圈子。同样公平性和最优化也是一对矛盾。公平性要求网中各站地位平等，而最优化则要求最大限度地发挥网络的能力，以求流量最大、延迟最小，但这往往对另外一些站是不公平的。

图5.2.1给出了公平性与最优化间矛盾的例子。假设AA'、BB'、CC'之间有足够的通信量使水平线路饱和，为使总流量尽可能地大，XX'之间的通信便应停止，但这对XX'来说则是不公平的。因此，就必须在二者之间寻求某种折衷。

图5.2.1　公平性与最优化间的矛盾

路由选择一般都基于某种判断标准。最简单的标准是选择通过网络的最短路由（即经过的结点最少的路由），由此可使每个分组“跳跃”数最少或称最少段数。最短路由的推广便是最低代价路由。代价的确定与一个或多个设计目标有关。例如，代价可以与链路的容量有关，容量越高代价越低，也可与使用该链路的排队延迟有关。在第一种情况中，最低代价路由应能提供最高的流量，而在第二种情况中，最低代价路由应使延迟最小。

在分组的传送过程中要以选定的判断标准来进行路由选择决策。路由选择决策的关键是互相独立的决策时间及决策地点。(www.xing528.com)

1、决策时间

决策时间有两种：当子网内部采用数据报机制时，子网须对每一分组进行路由选择决策；当子网内部采用虚电路机制时，子网只须对呼叫分组进行路由选择决策，而不须对信息分组进行路由选择决策。

2、决策地点

决策地点指明由谁来作出决策。在有的网络中，每一个结点都有路由选择的责任。各结点只根据本结点的局部状态信息进行决策的方法称为孤立式，各结点在相互交换网络状态信息的基础上进行决策的方法称为分布式。在另一些网络中，路由选择的责任由某一结点（如网络路由中心）来承担。它收集网络的状态信息，并将决策信息送至各结点以控制路由选择。这种方法称为集中式。另一种事先确定的路由选择方式称为确定式，这种方式没有具体的决策地点。

一般说来，路由选择决策须依据一定的网络状态信息。例如，孤立式方法依据本结点局部的信息，而分布式方法则依据各结点之间交换的信息。这些信息都要通过测量才能获得。但是，有的路由选择方法，例如洪泛式可以不要任何信息便可以作出路由选择决策。路由的信息交换得越多越及时，某结点作出的路由选择决策便越接近网络的实际情况，但消耗在传送这些信息上的网络资源也就越大。

至今已经研究开发了大量的路由选择算法，总的说来它们可以分为非适应型与适应型两类。非适应型的路由选择不随网络状态的改变而改变。网络状态包括线路流量负载状况、排队状况、拓扑状况等。拓扑的改变可能是某处结点或线路故障，或者从故障中恢复等等。非适应型路由选择算法对这些变化一概不关心，而适应型路由选择算法则恰恰相反，它们随时根据网络的一种或多种状态调整对路由的选择。两类路由选择算法的最大区别是对网络状态的自适应能力。那种须由人工定期修改的路由选择算法属于非适应型的算法。下面介绍几种最常见的路由选择算法。