常见的路由算法

计算机网络中的路由算法

路由算法在计算机网络中起着关键的作用，它用于确定数据包在网络中的传输路径。根据不同的网络拓扑和需求，有多种不同的路由算法被应用。本文将介绍几种常见的路由算法。

1. 距离矢量算法（Distance Vector Algorithm）

距离矢量算法是一种分布式的路由算法，每个节点在路由表中记录到达目的节点的距离向量。节点之间通过交换距离向量信息来更新路由表，并且通过Bellman-Ford算法来计算最短路径。该算法简单易实现，但是在大型网络中容易产生计数到无穷大的问题，即由于链路故障等原因产生的无限循环。

2. 链路状态算法（Link State Algorithm）

链路状态算法是一种集中式的路由算法，每个节点都会收集与自身相连的链路状态信息，并通过最短路径算法（如Dijkstra算法）计算出到达其他节点的最短路径。然后，每个节点都将自己的链路状态信息广播给所有其他节点，使得每个节点都有完整的网络拓扑和链路状态信息。该算法需要节点之间频繁的广播和计算，但是能够保证收敛，即要么找到最短路径，要么不进行路由。

3. 路径向量算法（Path Vector Algorithm）

路径向量算法可以看作是距离矢量算法和链路状态算法的结合，它通过回退进行路径检测和避免计数到无穷大的问题。每个节点在路由表中记录到达目的节点的路径和向量信息，通过交换路径向量信息来更新路由表。在计算最短路径时，路径向量算法使用类似链路状态算法的Dijkstra算法，但是在寻找路径时，会检查前面的节点是否已经在路径中出现，以避免产生环路。

4. 队列距离矢量算法（Queue Distance Vector Algorithm）

队列距离矢量算法是距离矢量算法的一种改进算法，主要解决计数到无穷大问题。该算法引入了队列和计数器，通过计数器和链路状态信息来确定数据包是否进入队列。每个节点在路由表中记录到达目的节点的距离向量和队列的长度。当链路发生故障时，节点将其距离设置为无穷大，并将计数器设置为有限值。如果计数器值到达最大值仍然没有恢复，那么节点将将其距离设置为无穷大并将数据包放入队列。这样就避免了计数到无穷大的问题。

import java.util.ArrayList;

import java.util.LinkedHashMap;

public class shutPath {

static int[][] cost;

static ArrayList visited = new ArrayList();

static ArrayList unVisited = new ArrayList();

static ArrayList vertexs = new ArrayList();

static LinkedHashMap shortPath = new

LinkedHashMap();

static ArrayList arcs = new ArrayList();

static LinkedHashMap shortPathWay = new

LinkedHashMap();

public static void main(String[] args) {

// TODO Auto-generated method stub

//init the verges set

arcs.add(new arc("A","B",2));

arcs.add(new arc("A","C",4));

arcs.add(new arc("A","D",15));

arcs.add(new arc("B","D",5));

arcs.add(new arc("B","C",1));

arcs.add(new arc("C","D",7));

arcs.add(new arc("D","E",4));

//init the nodes set

vertexs.add("A");

vertexs.add("B");

vertexs.add("C");

路由算法及分类

路由算法及分类：

1、非自适应算法，静态路由算法

不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。

特点：简单，开销少；灵活性差。

2、自适应算法，动态路由算法

可根据网络流量和拓扑结构的变化更新路由表。

特点：开销大；健壮性和灵活性好。

3、最优化原则（optimality principle）

如果路由器 J 在路由器 I 到 K 的最优路由上，那么从 J 到 K 的最优路由会落在同一路由上。

4、汇集树（sink tree）

从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树；

路由算法的目的是找出并使用汇集树。

几种典型的路由选择算法：

1、最短路径路由算法（Shortest Path Routing）

1）基本思想

构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。 2）测量路径长度的方法

结点数量

地理距离

传输延迟

距离、信道带宽等参数的加权函数

3）Dijkstra算法

每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注；

初始时，所有结点都为临时性标注，标注为无穷大；

将源结点标注为0，且为永久性标注，并令其为工作结点；

检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点；

在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点；

重复第四、五步，直到目的结点成为工作结点；

2、洪泛及选择洪泛算法

1） 洪泛算法（Flooding）

属于静态路由算法

a)基本思想

把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。 b)主要问题

距离矢量路由算法（Distance Vector Routing，DV）是ARPANET网络上最早使用的路由算法，也称Bellman-Ford路由算法和Ford-Fulkerson算法，主要在RIP（Route

Information Protocol）协议中使用。Cisco的IGRP和EIGRP路由协议也是采用DV这种路由算法的。

“距离矢量路由算法”的基本思想如下：每个路由器维护一个距离矢量（通常是以延时是作变量的）表，然后通过相邻路由器之间的距离矢量通告进行距离矢量表的更新。每个距离矢量表项包括两部分：到达目的结点的最佳输出线路，和到达目的结点所需时间或距离，通信子网中的其它每个路由器在表中占据一个表项，并作为该表项的索引。每隔一段时间，路由器会向所有邻居结点发送它到每个目的结点的距离表，同时它也接收每个邻居结点发来的距离表。这样以此类推，经过一段时间后便可将网络中各路由器所获得的距离矢量信息在各路由器上统一起来，这样各路由器只需要查看这个距离矢量表就可以为不同来源分组找到一条最佳的路由。

现假定用延时作为距离的度量，举一个简单的例子，如图7-37所示。假设某个时候路由器Y收到其邻居路由器X的距离矢量，其中m是Y估计到达路由器X的延时。若Y路由器知道它到邻居Z的延时为n，那么它可以得知Z通过Y到达X需要花费时间m+n。如果Z路由器还有其他相邻路由器，则对于从其他每个邻居那儿收到的距离矢量，该路由器执行同样的计算，最后从中选择费时最小的路由作为Z去往X的最佳路由，然后更新其路由表，并通告给其邻居路由器。

图7-37 距离矢量路由算法简单实例

现以一个如图7-38所示的示例介绍距离矢量算法中的路由的确定流程，各段链路的延时均已在图中标注。A、B、C、D、E代表五个路由器，假设路由表的传递方向为：A → B →

C → D → E（这与路由器启动的先后次序有关）。下面具体的流程。