分组交换路由选择

路由选择方法的精确描述，属于网路软件的一部分。对它的要求是正确、简单、可靠、稳定、公平和优化。

路由选择算法可分为自适应型和非自适应型两大类。自适应型的特点在于它的路由选择能在一定程度上随网路运行状态（如流量和拓扑）而改变，可避开出现异态的节点或链路。非自适应型采用静态路由选择算法。常见的非自适应型有扩散式、随机式、固定式等；而自适应型有集中式、孤立式、分布式等。

固定式是一种应用范围比较广的非自适应型路由选择算法。它是根据网路拓扑和信息流量的统计模型事先确定各节点的路由表，每个节点的路由表指明从该节点出发到某个目的节点所应该选择的输出链路以及下一节点。路由表由算法确定，而在固定式中是事先预定的。

最短路径算法为最常用的算法，它寻求在源节点和目的节点之间能沿着长度最短的路径来传送分组。这里所指的“长度”赋于特别含义，既可以是实际距离，也可以是平均时延或者链路费用。长度参数是路由表的依据，如果参数值来自网路运行的当前状态，路由表变为动态生成，这样的路由选择算法就属于自适应型。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。

算法描述如下：

1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex(G,v),i] vi∈V

2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。

各国公用分组交换网大多采用自适应型算法。法国的TRANSPAC网包含数十个节点，路由选择采取集中式自适应型为主兼有孤立式特点，基于最短路径算法，以链路长度定义为链路通信容量与缓冲存储器队列长度的函数。每个节点通过测量和估算，求得各条输出链路的长度；网内设一集中式网路管理中心，负责收集来自各节点的网路状态信息，并计算出任何两节点之间的最短路径及其长度。美国ARPA网采用基于最短路径算法的分布与集中相结合的自适应实现方式，每一节点每隔10秒钟更新一次与它相连接的各条链路的时延值，同时每一节点收到其他节点送来的链路时延更新值后，就重新计算其路由表。

分组交换路由选择，是分组交换网内任一节点（源节点或中继节点）在接收到一个分组后，确定一条后继路径传送该分组到目的接点的一个决策过程。路由选择是影响网路性能的重要因素之一，因为它直接决定分组通过网路所经历的平均时延。

路由选择的操作过程与分组交换网所提供的业务类型有关。如提供数据报业务，对每收到的一个分组都作一次路由选择，同一个源节点连续发出的多个分组可能经过不同的路由而到达同一目的节点；当提供虚电路业务时，通常只在建立虚电路时才进行路由选择，一旦虚电路建立后，在用户会话期间对所有报文分组均沿着同一路由进行传送。比较起来，虚电路业务的路由选择频度较低。

所谓交换指当一台主机向另一台主机发送数据包时，源主机通过某种方式获取路由器地址后，通过目的主机的协议地址（网络层）将数据包发送到指定的路由器物理地址（介质访问控制层）的过程。

通过使用交换算法检查数据包的目的协议地址，路由器可确定其是否知道如何转发数据包。如果路由器不知道如何将数据包转发到下一个节点，将丢弃该数据包；如果路由器知道如何转发，就把物理目的地址变换成下一个节点的地址，然后转发该数据包。在传输过程中，其物理地址发生变化，但协议地址总是保持不变。

路由选择就是构建网络节点路由表的过程，无论哪种分组网络，路由选择都是由网络提供的基本功能，但咋X.25建议中对路由选择并未作出明确规定，对不同的分组网允许有不同的路由选择算法，如何确立路由选择算法的好坏呢？分组的路由选择的基本原则如下：算法简单，易于实现，以减少额外开销；算法对所有用户都是公平的；应选择性能最佳的传输路径，使得端到端时延尽量小，个网络节点工作量均衡，最大限度提高网络资源利用率；网络出现故障时，在网络拓扑改变的情况下，算法仍能正常工作，自动选择迂回路由。

不同的分组交换网有可能采取不同的路由选择。路由选择可分为动态法和静态法两类。

路由选择器静态法

(1)扩散式路由法，分组从原始节点发往与之相邻的节点，接受该分组的节点检查它是否收到过该分组，如果已经收到过，则将它抛弃；如果未收到，只要该分组的目的节点不是该节点，就将此分组对相邻节点进行广播，最终该分组必将到达目的节点。其中，最早到达目的节点的分组所经历的过程必定是一条最佳路径。采用扩散式路由法，路由选择与网络拓扑无关，即使网络严重故障。只要有一条通路存在，分组也能到达终点，因此分组的传输的可靠性很高。但缺点是分组的无效传输量很大，网络的额外开销也大，网络中业务量的增加会导致排队时延的加大。

(2)固定路由表法，在每个节点交换机中设置一个包含路由目的节点地址和对应输出逻辑信道号的路由表，他指明从该节点到网络中的任何终点应当选择的路径。呼叫请求分组根据分组的目的地址查找该路由表，这样可以获得各转接节点的输出逻辑信号，从而形成一条端到端的虚电路。为防止网络故障或通路阻塞，路由表中可以规定主用路由和备用路由。

路由选择器动态法

(1)自适应路由选择网，自适应路由选择法是指路由选择根据网络情况的变化而变化。路由是由若干段链路串接而成的，自适应路由选择法是用迭代法逐段选取虚链路，从而形成一条端到端的虚电路。但在这种算法中，要求各节点存有全网络拓扑数据，而且每条链路的变化信息必须广播给网络所有的节点。自适应路由选择算法对减少网络时延、平滑网络负载、防止网络阻塞是有利的，但是路由表的频繁更换可能引起网络的不稳定，产生分组循环或者使分组在一对节点之间来回穿梭，自适应路由选择算法是X.25分组网中应用最为普遍的一种选路方式。

(2)集中式路由交换，网管中心负责全网状态信息的采集、路由计算以及路由表的下载。在分组交换网中，交换机之间一般有多条路由可选择。如何获得一条较好的路由，除了要有一个通过网络的平均时延较短和平衡网内业务量能力较强的路由算法外，同时还要考虑网内资源的利用和网络结构的适应能力。 2100433B

路由选择包括两个基本操作，即最佳路径的判定和网间信息包的传送（交换）。两者之间，路径的判定相对复杂。