下载文档原格式
计算机网络中的路由算法路由算法在计算机网络中起着关键的作用，它用于确定数据包在网络中的传输路径。
根据不同的网络拓扑和需求，有多种不同的路由算法被应用。
本文将介绍几种常见的路由算法。
1. 距离矢量算法（Distance Vector Algorithm）距离矢量算法是一种分布式的路由算法，每个节点在路由表中记录到达目的节点的距离向量。
节点之间通过交换距离向量信息来更新路由表，并且通过Bellman-Ford算法来计算最短路径。
该算法简单易实现，但是在大型网络中容易产生计数到无穷大的问题，即由于链路故障等原因产生的无限循环。
2. 链路状态算法（Link State Algorithm）链路状态算法是一种集中式的路由算法，每个节点都会收集与自身相连的链路状态信息，并通过最短路径算法（如Dijkstra算法）计算出到达其他节点的最短路径。
然后，每个节点都将自己的链路状态信息广播给所有其他节点，使得每个节点都有完整的网络拓扑和链路状态信息。
该算法需要节点之间频繁的广播和计算，但是能够保证收敛，即要么找到最短路径，要么不进行路由。
3. 路径向量算法（Path Vector Algorithm）路径向量算法可以看作是距离矢量算法和链路状态算法的结合，它通过回退进行路径检测和避免计数到无穷大的问题。
每个节点在路由表中记录到达目的节点的路径和向量信息，通过交换路径向量信息来更新路由表。
在计算最短路径时，路径向量算法使用类似链路状态算法的Dijkstra算法，但是在寻找路径时，会检查前面的节点是否已经在路径中出现，以避免产生环路。
4. 队列距离矢量算法（Queue Distance Vector Algorithm）队列距离矢量算法是距离矢量算法的一种改进算法，主要解决计数到无穷大问题。
该算法引入了队列和计数器，通过计数器和链路状态信息来确定数据包是否进入队列。
每个节点在路由表中记录到达目的节点的距离向量和队列的长度。
4.5路由选择算法到目前为止，我们在本章中主要研究了网络层的转发功能。
我们知道当分组到达一台路由器时，该路由器索引其转发表并决定该分组被指向的链路接口。
我们也知道路由选择算法在网络路由器中运行、交换和计算信息，用这些信息配置这些转发表。
路由选择算法和转发表之间的相互影响如图4-2所示。
在已经较为深入地研究了转发后，我们将注意力转向本章的其他重要主题，即网络层的至关重要的路由选择功能。
不管网络层提供的是数据报服务（在此情况下，在给定源和目的地址之间的不同分组可能采用不同的路由），还是虚电路服务（在此情况下，在给定源和目的地址之间的所有分组将采用相同路径），网络层都必须为从发送方到接收方的分组确定所采用的路径。
我们将看到路由选择的工作是：确定从发送方到接收方通过路由器网络的好路径（等价为路由）。
主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器（defaultrmiter)，又称为该主机的第一跳路由器（first-hop router)。
每当主机发送一个分组时，该分组被传送给它的默认路由器。
我们将源主机的默认路由器称作源路由器（sourcemuter)，把目的主机的默认路由器称作目的路由器（destinationmuter)。
一个分组从源主机到目的主机的路由选择问题显然可归结为从源路由器到目的路由器的路由选择问题。
这是本节的重点。
因此，路由选择算法的目的是简单的：给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的“好”路径。
通常，一条好路径指具有最低费用的路径。
然而我们将看到，实践中现实世界还关心诸如策略之类的问题（例如，诸如“属于组织Y的路由器X不应转发任何来源于组织Z网络的分组”之类的规则），这也使得概念简单、性能优秀的算法变得复杂。
然而这些概念简单、性能优秀的算法的理论奠定了当今网络路由选择实践的基础。
可以用图来形式化描述路由选择问题。
我们知道图( graph)G=(N,E)是一个N个结点和E条边的集合,其中每条边是取自N的一对结点。
常见的路由算法常见的路由算法路由算法是指为了用于在互联网之类的分组通讯网络中的数据包进行寻址所使用的一种算法。
其目的是为了能够掌握网络拓扑结构，更有效的使用网络资源，提供更好的服务质量，在众多的路由算法中，下面列出了一些常见的。
1. 链路状态路由协议（Link State Routing Protocol）链路状态路由协议是一种以网络中所有的节点为基础的路由协议，它的特点是在所有节点之间建立并保持一个网络状态数据库，每个节点首先会发出一个链路状态数据包来描述自己知道的其他节点的相关信息，并通过该信息计算出一张最短路径树。
LSRP一般都有洪泛问题，产生洪泛的原因在于每个节点的发出的链路状态数据包要发到整个网络中，所以数据包会不断传播，产生大量网络流量。
常见的LSRP有OSPF等。
2. 距离向量路由协议（Distance Vector Routing Protocol）距离向量路由协议是一种以自身节点所连接的邻居节点的路由信息为基础的协议，每个节点只知道自己所连接的邻居节点的路由信息，而不知道整张网络的拓扑结构。
DVRP算法通过递归与相邻节点交换距离向量信息来分配最短路径，因此它能够在网络中改变路由波动时使整个路由表保持一致。
常见的DVRP有RIP等。
3. 混合路由协议（Hybrid Routing Protocol）混合路由协议是链路状态和距离向量路由协议的混合体，它采用链路状态路由协议的优点，建立了一张网络拓扑地图；同时又采用距离向量路由协议的算法对网络进行遍历，它使用距离向量路由协议的性质表明每个路由器只需要与它的成邻接的路由器通信，这样可以大大减小链路状态路由协议产生的洪泛问题。
4. 路由发现协议（Route Discovery Protocol）路由发现协议通常是物理网络发挥作用的协议。
当网路中有一个新的路由器被连接时，路由器会通过路由发现协议来发现新路由器，这样数据就可以经过新路由器并到达目的地。
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）支持中间节点应答，能使源节点快速获得路由，有效减少了广播数，但存在过时路由问题。
路由算法及分类路由算法及分类：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）洪泛法的一种改进。
计算机网络的路由算法在计算机网络中，路由算法是用来确定数据包从源节点到目标节点的路径的一种算法。
它是实现网络通信的重要组成部分，承担着决定数据传输路线的关键任务。
本文将介绍几种常见的路由算法。
一、最短路径算法最短路径算法是一种常见且重要的路由算法。
它的目标是找到节点之间的最短路径，以最快速度将数据包从源节点发送到目标节点。
其中，迪杰斯特拉算法和贝尔曼-福特算法是两种常见的最短路径算法。
迪杰斯特拉算法（Dijkstra Algorithm）是一种广泛应用于计算机网络中的最短路径算法。
它通过计算从源节点到其他节点的最短路径，并记录路径上的节点和距离，最终找到从源节点到目标节点的最短路径。
该算法具有高效性和准确性，很好地满足了网络数据传输的需求。
贝尔曼-福特算法（Bellman-Ford Algorithm）是另一种常用的最短路径算法。
与迪杰斯特拉算法不同的是，贝尔曼-福特算法可以处理包含负权边的图。
它通过迭代地更新节点之间的距离，直到收敛为止，找到最短路径。
虽然贝尔曼-福特算法的效率较低，但其对于具有复杂网络结构的情况仍然具有重要的应用价值。
二、最优路径算法除了最短路径算法，最优路径算法也是计算机网络中常用的路由算法之一。
最优路径算法旨在找到包括最少跳数、最小延迟或最大带宽等特定需求的路径，以满足网络通信的性能要求。
例如，最小跳数算法（Minimum Hop Routing）是一种常见的最优路径算法，它通过选择路径上的最少跳数来实现数据传输。
这在实时性要求较高的应用场景中非常有用，如语音通话和视频会议等。
另外，最小延迟算法（Minimum Delay Routing）和最大带宽算法（Maximum Bandwidth Routing）也是常用的最优路径算法。
前者通过选择具有最小传输延迟的路径来实现数据传输，适用于对实时性要求较高的应用。
而后者则通过选择具有最大传输带宽的路径来实现数据传输，适用于对吞吐量要求较高的应用。
第四章路由器硬件结构及工作原理4.1路由器的硬件构成路由器主要由以下几个部分组成：输入/输出接口部分、包转发或交换结构部分（switching fabric）、路由计算或处理部分。
如图4-1所示。
图4-1 路由器的基本组成输入端口是物理链路和输入包的进口处。
端口通常由线卡提供，一块线卡一般支持4、8或16个端口，一个输入端口具有许多功能。
第一个功能是进行数据链路层的封装和解封装。
第二个功能是在转发表中查找输入包目的地址从而决定目的端口（称为路由查找），路由查找可以使用一般的硬件来实现，或者通过在每块线卡上嵌入一个微处理器来完成。
第三，为了提供QoS（服务质量），端口要对收到的数据包进行业务分类，分成几个预定义的服务级别。
第四，端口可能需要运行诸如SLIP（串行线网际协议）和PPP（点对点协议）这样的数据链路级协议或者诸如PPTP（点对点隧道协议）这样的网络级协议。
一旦路由查找完成，必须用交换开关将包送到其输出端口。
如果路由器是输入端加队列的，则有几个输入端共享同一个交换开关。
这样输入端口的最后一项功能是参加对公共资源（如交换开关）的仲裁协议。
普通路由器中该部分的功能完全由路由器的中央处理器来执行，制约了数据包的转发速率（每秒几千到几万个数据包）。
高端路由器中普遍实现了分布式硬件处理，接口部分有强大的CPU处理器和大容量的高速缓存，使接口数据速率达到10Gbps，满足了高速骨干网络的传输要求。
路由器的转发机制对路由器的性能影响很大，常见的转发方式有：进程转发、快速转发、优化转发、分布式快速转发。
进程转发将数据包从接口缓存拷贝到处理器的缓存中进行处理，先查看路由表再查看ARP 表，重新封装数据包后将数据包拷贝到接口缓存中准备传送出去，两次查表和拷贝数据极大的占用CPU的处理时间，所以这是最慢的交换方式，只在低档路由器中使用。
快速交换将两次查表的结果作了缓存，无需拷贝数据，所以CPU处理数据包的时间缩短了。
分布式算法设计基础第四章路由算法（Routing Algorithms）一般地，一个进程并不直接用一个其他每一个结点联结，一个结点能够直接发送信息邮包的结点集合称之为该结点的邻居。
所谓路由是一个刻画决策过程的术语，根据这个决策过程，一个结点选择其邻居结点中的一个（或一个以上），使这条路上的邮包最终到达目的地。
设计路由算法的目的是对每个结点产生一个决策过程，以便执行该功能并确保每个邮包的投递。
显然，每个结点都要保留网络拓扑结构的一些信息作为（局部）决策的工作基础，我们把这些信息与路由表联系在一起，根据这些表的引导，路由问题可以很自然地分成两部分：（1）表计算在网络初始化的时候计算路由表，且当网络拓扑结构发生改变时，该表必须重新计算更新；（2）邮包转递通常，我们从以下几个方面来判断和评价一个“好”的路由方法：（3）正确性算法必须把递交给网络的每一个邮包投递到它的最终目的地；（4）复杂性路由表的计算算法应该尽可能地使用极少的信息、时间和存储；（5）有效性算法必须经过“好”的路径发送邮包，例如，路径只承受小的时间延迟，并且保证整个网络高度流畅（通畅）。
若一个路由算法使用“最佳”路径，则该算法称为最优的，令人满意的；（6）健壮性在拓扑结构被改变的情况下（如增加或删除一个结点和通道），算法能自动更新路由表，以便在修改后的网络中执行路由选择功能；（7）适应性算法应能调整路由表以便平衡通道和结点负载，以免这些要经过的结点和通道过于忙碌；（8）公平性算法应该以相同的优先级公平地为每个用户提供服务。
这些标准并不一定都能达到，其中一些有时候是相互冲突的，大多数算法只能针对其中的一部分是比较好的。
一般地，网络的拓扑结构抽象地用一个图来表示，于是，算法的最优性依赖于图中什么是“最佳”路径。
有几种“最佳”的概念，每一种都与其自己的路由算法联系在一起，就象编译和文法的分析方法一样。
（1）最小跳跃应用一般路径的成本度量为该路径跳跃的数目，即经过的结点数目减一， hop（跳跃）表示经过通道或从一个结点到一个结点的步数。
一个最小跳跃路由算法使用一条具有最小可能跳跃数目的路径。
（2）最短路径每个通道静态地被赋予一个非负数，也称权。
一段路径的成本度量为该路径上通道的权和。
一个最短路径算法使用一条具有最低可能成本的路径。
（3）最小延迟每个通道动态赋予一个权，该权取决于通道上的交通忙闲情况。
一个最小延迟算法以下列方式重复修正一个表，使得这条路径的选择具有最小总延迟数，即总的延迟时间最小。
当通道上遇到的延迟依赖于实际交通时，经过网络发送的各个邮包会相互影响，并由此导致群延迟，这是十分复杂的。
1．基于目的地的路由当投递一个邮包通常只涉及邮包的目的地（和路由表的内容）时要做路由决策，而且，这种决策与邮包最初的发送者是无关的。
这样，路由可以忽略源头同时仍使用最优路径策略。
本章所得到的结果并不依赖于路径上具体的最优性标准的选择，即无论是最短路径、最小跳跃或其他标准都可以，但下列假设必须成立（回忆：一个路径是简单的，如果他包含每个结点至多一次；称一个路径是一个环，如果第一个结点等于最后一个结点）：（1）经一条路径P发送一个邮包的成本与该路径的实际利用无关，特别，当其他信息也可以使用P的边时，这一假设允许我们把使用路径P的成本看成是路径函数，故将P的成本用C（P） R表示。
（2）两条路径连接的成本等于被连接的路径的成本之和，即对所有的i=0，1，2，k，C（<u0，u1，⋯，u k>）= C（<u0，u1，⋯，u i>）+ C（<u i，u i+1，⋯，u k>）特别，空路径<u0> 的成本满足C（<u0>）= 0 。
（3）图中不包含一个负成本的环。
最小跳跃和最短路径成本标准满足这些标准。
从u到v的一条路径称为是最优的，如果不存在从u到v的具有更小成本的路径。
注意，一条最优路径并不总是唯一的，有可能存在不同的路径，它们都具有相同的最小成本。
引理4.1设G =（V，E），u，v V，如果G中存在一条从u到v的路径，则存在一条最优的简单路径。
证明：直接在黑板上证明。
定理4.2对每一个d V，存在一棵树T d = ( V，E d ) 使得，E d ⊆ E，且使得对每一个结点v V，T d中从v到d的路径是G中从v到d的最优路径。
证明：这棵树实际上是一棵生成树。
定理4.2中每一棵树 T d 实际上是原来图中一棵以d为根结点的最优汇集树，他是一棵生成树，但不一定是一棵最小生成树。
术语：若一棵树具有定理4.2中所给定的性质，则称该树为最优汇集树。
最优汇集树的存在性表明：如果仅考虑路由算法，那么，算法4-2中的转发机制不会是对最优性的折中，即不会损害算法的最佳路由。
在算法中，table-lookup u是仅有一个变量的局部过程，它根据路由表作出判断，返回u的近邻作为值。
当所有目的地为d的邮包，经过朝向根为d的生成树最优路由时，如果对于所有的u≠d，table-lookup u（d）返回的是生成树T d中u的父结点，则转发是最优的。
当转发机制具有这种形式且拓扑结构不再变化，使用下面的结果就能验证路由表的正确性。
称（针对目的地结点d）路由表包含回路，若存在结点u1，u2，⋯，u k，满足对任意i，u i≠d，对任意i<k，table_lookup u i(d) = u i+1，且 table_lookup u k(d) = u1若对任何目的地d，路由表不包含回路，则称它是无回路的。
算法4.2 基于目的地的向前推进算法。
（转发算法）引理4.3 向前推进机制把每个邮包投递到它的目的地，当且仅当路由表无回路。
∙ 最小延迟分支路由算法作一个简单的说明。
2．所有点对最短路径问题本节针对一个网络中同时计算所有结点的路由表问题讨论由Toueg提出的算法，该算法对每一对结点（u,v），计算从u到v的最短路径。
， C×C ≥0， ， ⇝0 ⋜i< k（Z, I, ⊢i, ⊢s, ⊢r），⊢s⊢r Z×M×Zc ⊢d ⇔ (c,d) ∈⊢i ∨ m ∈ M（（c，m，d）∈ ⊢s ∪ ⊢r）P={p1，p2，⋯⋯，p N}，（Z p i, I p i, ⊢pi i, ⊢pi s, ⊢pi r））⑴ C ={（c p1，c p2 ，⋯⋯，c pN，M）：（p∈P：c p ∈ Z p）且M∈M（M）}⑵ =（∪p∈Pp），p，pi（c p1，c p2 ，⋯，c pi ，⋯，c pN，M1），（c p1，c p2 ，⋯，c’pi，⋯，c pN，M2）① （c pi，c’pi ）∈ ⊢pi i 且 M1 = M2 ；② 对某个m∈M,（c pi，m，c’pi ）∈ ⊢pi s 且 M2 = M1∪{m} ；③ 对某个m∈M,（c pi，m，c’pi ）∈ ⊢pi r 且 M1 = M2∪{m} ；⑶ I ={（c p1，c p2 ，⋯⋯，c pN，M）：（p∈P：c p ∈ I p）且M=φ }（c，d）∈⊢p i=（c p1，c p2 ，⋯，c p ，⋯，c pN，M），（c p1，c p2 ，⋯，d，⋯，c pN，M）=（c p1，c p2 ，⋯，c p ，⋯，c pN，M），（c p1，c p2 ，⋯，d，⋯，c pN，M∪{m}）（Z p i, I p i,⊢pi i, ⊢pi s, ⊢pi r））C ={（p1，p2 ，⋯⋯，p N）： p∈P：c p ∈ Z p }=（∪p∈Pp）∪（∪p, q∈P: p≠qpq），（c p1，c p2 ，⋯，c pi ，⋯，c pN），（c p1，c p2 ，⋯，c’pi，⋯，c pN），（⋯，c pi ，⋯，c pj ，⋯），（⋯，c pi ，⋯，c’pj，⋯），（c pi，m，c’pi ）∈ ⊢pi s 且 （c pj，m，c’pj ）∈ ⊢pj rI ={（c p1，c p2 ，⋯⋯，c pN） ：（p∈P：c p ∈ I p}true 如果P在 成立P()=False 否则{ P }{ Q }⑴ ∈I，P()，且⑵ { P }{ P }⑴ ∈I，Q() ⇒ P()，且⑵ { Q ∧ P }{ Q ⇒ P } （ 是变迁）⑴ ∈I，Q()∧ P()，且⑵ { Q ∧ P }{ Q ∧ P } （ 是变迁）∈I，Q()w1 ≻ w2 ≻ w3 ≻w4 ≻ ⋯⋯ w i∈W。
>，或P()term ⇒ P， ，e（）=（c p1，c p2 ，⋯，d，⋯，c pN，（M- x）∪ y ）e p=（b p，x p ，y p，d p）e q=（b q，x q ，y q，d q）=（⋯，c p ，⋯，c q ，⋯，M）c p = b p，c q = b q，x p ⊆ M，x q⊆ M =（⋯，d p，⋯，c q，⋯，（M- x p）∪ y p），当x q⊆ M 且x q∩ x p = φ=（⋯，d p，⋯，d q，⋯，（（（M- x q）∪ y q）- x p）∪ y p），（（M- x p∪ y p）- x q∪y q）=（（M- x q∪ y q）- x p∪ y p），⋯，，e p（），e q（e p（）），⋯a = e0，e1，e2，⋯，e k = b≼ ， = =（c p1，c p2 ，⋯，c pN，M），=（c’，x’，y’，d’），c p = d’，，（X，<）a≺b （a）<（b）。
（e1，⋯，e k） e1≺ e2≺⋯≺ e k = aa≺b （a）<（b）（a1，⋯，a n）≤（b1，⋯，b n）i（1≤i ≤n）: a i≤ b i≺≮∽∢≤≤≥≮≯⋯a ≼ b。
