第6章 路由算法总结

计算机网络中的路由算法路由算法在计算机网络中起着关键的作用，它用于确定数据包在网络中的传输路径。

根据不同的网络拓扑和需求，有多种不同的路由算法被应用。

本文将介绍几种常见的路由算法。

1. 距离矢量算法（Distance Vector Algorithm）距离矢量算法是一种分布式的路由算法，每个节点在路由表中记录到达目的节点的距离向量。

节点之间通过交换距离向量信息来更新路由表，并且通过Bellman-Ford算法来计算最短路径。

该算法简单易实现，但是在大型网络中容易产生计数到无穷大的问题，即由于链路故障等原因产生的无限循环。

2. 链路状态算法（Link State Algorithm）链路状态算法是一种集中式的路由算法，每个节点都会收集与自身相连的链路状态信息，并通过最短路径算法（如Dijkstra算法）计算出到达其他节点的最短路径。

然后，每个节点都将自己的链路状态信息广播给所有其他节点，使得每个节点都有完整的网络拓扑和链路状态信息。

该算法需要节点之间频繁的广播和计算，但是能够保证收敛，即要么找到最短路径，要么不进行路由。

3. 路径向量算法（Path Vector Algorithm）路径向量算法可以看作是距离矢量算法和链路状态算法的结合，它通过回退进行路径检测和避免计数到无穷大的问题。

每个节点在路由表中记录到达目的节点的路径和向量信息，通过交换路径向量信息来更新路由表。

在计算最短路径时，路径向量算法使用类似链路状态算法的Dijkstra算法，但是在寻找路径时，会检查前面的节点是否已经在路径中出现，以避免产生环路。

4. 队列距离矢量算法（Queue Distance Vector Algorithm）队列距离矢量算法是距离矢量算法的一种改进算法，主要解决计数到无穷大问题。

该算法引入了队列和计数器，通过计数器和链路状态信息来确定数据包是否进入队列。

每个节点在路由表中记录到达目的节点的距离向量和队列的长度。

第6章路由算法总结路由算法是网络中的核心算法之一，它决定了数据包在网络中的传输路径。

路由算法的设计和优化对于网络的性能和稳定性具有重要影响。

在本章中，我们将总结一些常见的路由算法，并介绍它们的优缺点。

1.静态路由算法：静态路由算法是最简单的路由算法，它通过人工配置将目的地和下一跳地址映射起来。

静态路由算法的优点是简单、易于实现和维护，适用于小型网络。

然而，静态路由算法的缺点是无法适应网络拓扑的变化，对于大型和复杂网络不可行。

2.距离向量路由算法：距离向量路由算法是一种基于邻居节点交换信息的分布式算法。

每个节点维护一个路由表，其中包含到达各个目的地的距离和下一跳节点信息。

节点周期性地将路由表广播给邻居节点，并根据收到的更新信息更新自身路由表。

距离向量路由算法的优点是简单、分布式，适用于小型网络。

然而，它的缺点是收敛速度慢和计算复杂度高，容易出现路由环路和计数问题。

3.链路状态路由算法：链路状态路由算法是一种基于全局网络状态信息的算法。

每个节点通过发送链路状态信息到整个网络，使得每个节点都具有完整的网络拓扑信息。

节点根据收到的链路状态信息计算最短路径，并构建路由表。

链路状态路由算法的优点是收敛速度快、计算复杂度低和稳定性好。

然而，它的缺点是需要消耗大量的带宽和存储资源，并且对于网络规模较大的情况下，算法的效率会下降。

4.链路状态路由算法的改进算法：为了优化链路状态路由算法，人们提出了一些改进算法，如OSPF （开放式最短路径优先）、IS-IS（中间系统间路由）等。

这些算法使用了一些技术，如分层、区域划分和链路优化等，以提高算法的性能和可扩展性。

5.BGP（边界网关协议）：BGP是用于互联网的一种路径向量路由协议。

它是一种自治系统之间的路由协议，用于实现互联网的路由选择。

BGP通过交换路由信息和策略来确定数据包的最佳路径。

BGP的优点是具有高度的灵活性和可配置性，可以根据策略调整路由。

然而，BGP的缺点是配置复杂和收敛速度较慢。

路由算法与路由协议
路由算法和路由协议是计算机网络中非常重要的概念。

路由算法是指在网络中选择最优路径的过程，而路由协议则是指网络中路由器之间通信的协议。

常用的路由算法包括距离矢量算法、链路状态算法和路径矩阵算法。

距离矢量算法以距离为基础来选择最优路径，链路状态算法则是通过收集邻居节点的信息来计算网络拓扑结构，从而选择最优路径。

路径矩阵算法则是通过计算矩阵来确定最优路径。

路由协议包括RIP、OSPF、BGP等。

RIP是一种基于距离矢量算
法的协议，其特点是简单易用，但是对于大型网络来说效率较低。

OSPF 是一种基于链路状态算法的协议，其特点是对于大型网络来说效率较高，但是配置相对较为复杂。

BGP是一种面向互联网的协议，其特点是可以实现自治系统之间的互联。

在实际应用中，路由算法和路由协议的选择需要根据网络的规模、性能要求等因素来确定，以实现最优的网络性能。

- 1 -。

AODV协议1. 概述Nokia研究中心开发，自组网路由协议的RFc标准，它是DSR和DSDV的综合，借用了DSR中路由发现和路由维护的基础程序，及DSDV的逐跳(Hop-by-HoP)路由、目的节点序列号和路由维护阶段的周期更新机制，以DSDV为基础，结合DSR中的按需路由思想并加以改进。

它应用于无线自组织网络中进行路由选择的路由协议, 它能够实现单播和多播路由。

该协议是自组织网络中按需生成路由方式的典型协议。

用于特定网络中的可移动节点。

它能在动态变化的点对点网络中确定一条到目的地的路由，并且具有接入速度快，计算量小，内存占用低，网络负荷轻等特点。

它采用目的序列号来确保在任何时候都不会出现回环，避免了传统的距离向量协议中会出现的很多问题。

AODV最初提出的目的是为了建立一个纯粹的按需路由的系统。

网络中的节点完全不依赖活动路径，既不维护任何路由信息，也不参与任何定期的路由表交换。

节点不需要发现和维护到其他节点的路由，除非两个节点需要通讯或者节点是作为中间转发节点提供特定的服务来维护另外两个节点的连接性。

提出：With the goals of minimizing broadcasts and transmission latency when new routes are needed, we designed a protocol to improve up on the performance characteristics of DSDV in the creation and maintenance of ad-hoc networks.2. 特点优点：（1）基本路由算法为距离向量算法，但有所改进，思路简单、易懂。

（2）按需路由协议，而且节点只存储需要的路由，减少了内存的需求和不必要的复制。

（3）采用UDP 封装，属于应用层协议。

（4）支持中间节点应答，能使源节点快速获得路由，有效减少了广播数，但存在过时路由问题。

计算机网络原理最短路径路由在路由选择方法中，我们经常采用的算法是：求给定网络中任意两个节点间的最短路径。

即求任意两个节点间的最小时延或最小费用的路径。

这里已知的是整个网络拓扑和各链路的长度。

求最短路径的方法有许多种，下面我们以图6-4所示的网络为例来讨论一种由Dijkstra 提出的求最短路径的算法，即寻找从源节点到网络中其他各节点的最短路径。

在本例中，设节点A为源节点，然后逐步寻找其最短路径，每次找一个节点到源节点的最短路径，直到把所有的点都找到为止。

图6-4 求最短路径算法的网络举例令D(V)为源节点(节点A)到节点v的距离,它就是沿着某一通路的所有链路的长度之和。

再令l(i,l)为节点i至节点j之间的距离。

整个算法有以下部分：（1）初始化。

令N表示网络节点的集合。

先令N={A}，对所有不在N中的节点v，写出：λ(A,ν)若节点ν与节点A直接相连；D(ν)= {∞若节点ν与节点A不直接相连；在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞，可以使D （v）=99。

（2）寻找一个不在N中的节点w，其D（w）值为最小。

把w加入到N中，然后对所有不在N中的节点，用D（v）与[D（w）+λ(w,ν)]中较小的值去更新原有的D（v）值，即：D（v）←min[D（v）,D（w）+λ(w,ν)]（3）重得步骤（2），直到所有的网络节点都在N中为止。

6-2所示是对图6-4的网络进行求解的详细步骤。

可以看出，上述的步骤（2）共执行了5次，表中带圆圈的数字是在每一次执行步骤（2）时所寻找的具有最小值的D（w）值。

当第5次执行步骤（2）并得出了结果后，所有网络节点都已包含在N之中，整个算法即告结束。

最后就可得出以节点A 为根的最短路径树，如图6-5（1）所示。

从这个最短路径树可以清楚地看出从源节点A 到网内任何一个节点的最短路径。

图中，每个节点旁边括号中的数字表明该节点是在执行第几步的算法时加入到集合中去的。

路由算法及分类路由算法及分类：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）主要问题洪泛要产生大量重复包.c）解决措施每个包头包含站点计数器,每经过一站计数器减1，为0时则丢弃该包；记录包经过的路径2）选择性洪泛算法（selective flooding）洪泛法的一种改进。