路由算法比较

路由算法及分类

路由算法及分类：

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)主要问题

网络路由技术优化方法详解

网络路由是指在计算机网络中，根据特定的路由选择算法，将数据从源节点传递到目的节点的过程。随着互联网的迅速发展，网络路由技术的优化变得尤为重要。本文将详细介绍网络路由技术优化的方法。

一、优化路由算法

1. 路由选择协议优化

路由选择协议是指在网络中节点之间进行路由选择的一种通信协议，如RIP、OSPF、BGP等。优化路由选择协议可以提高网络路由的效率和稳定性。例如，在使用RIP协议时，可以通过调整路由更新间隔、设定路由更新触发条件等方式来优化路由选择过程。

2. 最短路径算法优化

最短路径算法是一种常用的路由选择算法，如Dijkstra算法、Bellman-Ford算法等。在实际网络中，网络拓扑结构复杂，节点数量庞大，使用传统的最短路径算法可能会导致计算负载过重、延迟增加等问题。因此，可以通过引入负载平衡技术、节点分级等方式来优化最短路径算法，提高网络路由的效率。

二、优化网络结构

1. 利用多层次网络架构 在大规模网络中，简单的扁平网络结构会导致路由表庞大、路由冲突等问题。因此，可以通过引入多层次网络架构来优化网络结构。例如，将大规模网络划分为多个自治系统（AS），每个自治系统内部采用内部路由协议，自治系统之间采用外部路由协议，可以降低路由表大小，减少路由冲突的发生。

2. 利用虚拟专用网络（VPN）

虚拟专用网络是一种通过公共网络创建的私有网络，可以实现安全可靠的数据传输。利用VPN技术，可以将相同地理位置的节点组建成一个虚拟网络，从而减少网络传输距离，提高传输效率。同时，VPN还可以通过隧道技术保护数据传输的安全性，提高网络的安全性。

三、优化链路负载均衡

链路负载均衡是指在多个链路之间均衡地分配网络流量，提高网络吞吐量和响应速度。常用的负载均衡技术包括：基于端口的负载均衡、基于服务器的负载均衡、基于内容的负载均衡等。通过合理配置和调整负载均衡算法，可以避免链路拥堵和数据丢失，提高网络的稳定性和可用性。

LS算法与DV算法

LS算法（Link State Algorithm）和DV算法（Distance Vector

Algorithm）是两种常见的路由算法，用于计算网络中的最佳路径。本文将详细介绍LS算法和DV算法的原理、特点和应用场景。

一、LS算法

LS算法是一种基于链路状态的路由算法。它的核心思想是每个节点都通过广播链路状态信息，将所知道的网络拓扑信息发送给所有节点，并根据收到的链路状态信息计算最佳路径。具体流程如下：

1.链路状态信息广播：每个节点定期地广播链路状态信息，包括自己与邻居节点之间的链路状态。链路状态信息包括链路的带宽、延迟、可用性等参数。

2.链路状态数据库更新：每个节点收到链路状态信息后，更新本地的链路状态数据库，保存所有节点之间的链路状态信息。

3. 最短路径计算：根据链路状态数据库，每个节点使用最短路径算法（如Dijkstra算法）计算出到达所有其他节点的最短路径。最短路径由一系列节点组成，经过这些节点可达目的节点。

4.路由表生成：每个节点根据最短路径计算结果生成路由表，将目的节点与下一跳节点对应起来。路由表中的项表示到达一些目的节点应经过的下一跳节点。

LS算法的特点如下： 1.需要大量的计算和存储开销：每个节点需要保存所有节点之间的链路状态信息，因此需要较大的存储空间。同时，最短路径计算是一个复杂的计算过程，需要耗费大量的计算资源。

2.收敛速度较快：由于每个节点都拥有全局的网络信息，LS算法的收敛速度较快。一旦网络拓扑发生变化，节点会立即更新链路状态并重新计算最短路径。

3.网络稳定性好：LS算法能够在整个网络中保持一致的路由信息，使得网络稳定性较高。即使出现链路故障或节点故障，网络也能够快速恢复。

LS算法适用于网络规模较小、带宽较大、希望快速收敛和稳定性较高的场景（如企业内部网络）。

二、DV算法

DV算法是一种基于距离向量的路由算法。它的核心思想是每个节点通过交换距离向量信息，将自己的已知距离信息传递给相邻节点，相邻节点再根据收到的距离向量信息更新自己的距离向量。具体流程如下：

路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。

路由器使用路由算法来找到到达目的地的最佳路由。

关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法： 总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。

收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。

路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有：

1、选择最短路由还是最佳路由；

2、通信子网是采用虚电路操作方式还是采用数据报的操作方式；

3、采用分布式路由算法还是采用集中式路由算法；

4、考虑关于网络拓扑、流量和延迟等网络信息的来源；

5、确定采用静态路由还是动态路由。

各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。

链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。

距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。

也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。

metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。

路由选择协议（Routing protocol）