网络路由算法

本文概述

• 路由算法的分类
• 自适应路由算法
• 非自适应路由算法
• 黑白差异自适应和非自适应路由算法

• 为了将数据包从源传输到目的地, 网络层必须确定可以传输数据包的最佳路由。
• 无论网络层提供数据报服务还是虚拟电路服务, 网络层的主要工作都是提供最佳路由。路由协议可提供此工作。
• 路由协议是一种路由算法, 它提供了从源到目的地的最佳路径。最佳路径是具有从源到目的地的“最低成本路径”的路径。
• 路由是将数据包从源转发到目的地的过程, 但是发送数据包的最佳路由由路由算法确定。

路由算法的分类

路由算法分为两类：

• 自适应路由算法
• 非自适应路由算法

自适应路由算法

• 自适应路由算法也称为动态路由算法。
• 该算法根据拓扑和网络流量做出路由决策。
• 与该算法有关的主要参数是跳数, 距离和估计的渡越时间。

自适应路由算法可以分为三部分：

• 集中式算法：它也称为全局路由算法, 因为它通过使用有关网络的完整且全局的知识来计算源和目标之间的成本最低的路径。该算法将节点之间的连接性和链路成本作为输入, 并且此信息是在实际执行任何计算之前获得的。链路状态算法被称为集中式算法, 因为它知道网络中每个链路的成本。
• 隔离算法：一种通过使用本地信息而不是从其他节点收集信息来获取路由信息的算法。
• 分布式算法：也称为分散算法, 因为它以迭代和分布式方式计算源和目标之间的成本最低的路径。在分散算法中, 没有节点知道所有网络链路的成本。最初, 节点仅包含有关其自身直接连接的链接的信息, 并通过迭代计算过程计算出到达目的地的成本最低的路径。距离矢量算法是一种分散式算法, 因为它永远不知道从源到目的地的完整路径, 相反, 它知道与最小开销路径一起转发数据包的方向。

非自适应路由算法

• 非自适应路由算法也称为静态路由算法。
• 引导网络时, 路由信息将存储到路由器。
• 非自适应路由算法不会根据网络拓扑或网络流量来做出路由决策。

非自适应路由算法有两种类型：

泛洪：在泛洪的情况下, 每个到达的数据包都会发送到所有传出链接, 除了已到达的数据包。泛洪的缺点是节点可能包含特定数据包的多个副本。

随机游走：在随机游走的情况下, 节点随机发送到其邻居之一的数据包。使用随机游走的优点是, 它非常有效地使用了替代路线。

黑白差异自适应和非自适应路由算法