下载文档原格式
计算机网络中的路由算法路由算法在计算机网络中起着关键的作用，它用于确定数据包在网络中的传输路径。
根据不同的网络拓扑和需求，有多种不同的路由算法被应用。
本文将介绍几种常见的路由算法。
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的缺点是配置复杂和收敛速度较慢。
常见的路由算法常见的路由算法路由算法是指为了用于在互联网之类的分组通讯网络中的数据包进行寻址所使用的一种算法。
其目的是为了能够掌握网络拓扑结构，更有效的使用网络资源，提供更好的服务质量，在众多的路由算法中，下面列出了一些常见的。
1. 链路状态路由协议（Link State Routing Protocol）链路状态路由协议是一种以网络中所有的节点为基础的路由协议，它的特点是在所有节点之间建立并保持一个网络状态数据库，每个节点首先会发出一个链路状态数据包来描述自己知道的其他节点的相关信息，并通过该信息计算出一张最短路径树。
LSRP一般都有洪泛问题，产生洪泛的原因在于每个节点的发出的链路状态数据包要发到整个网络中，所以数据包会不断传播，产生大量网络流量。
常见的LSRP有OSPF等。
2. 距离向量路由协议（Distance Vector Routing Protocol）距离向量路由协议是一种以自身节点所连接的邻居节点的路由信息为基础的协议，每个节点只知道自己所连接的邻居节点的路由信息，而不知道整张网络的拓扑结构。
DVRP算法通过递归与相邻节点交换距离向量信息来分配最短路径，因此它能够在网络中改变路由波动时使整个路由表保持一致。
常见的DVRP有RIP等。
3. 混合路由协议（Hybrid Routing Protocol）混合路由协议是链路状态和距离向量路由协议的混合体，它采用链路状态路由协议的优点，建立了一张网络拓扑地图；同时又采用距离向量路由协议的算法对网络进行遍历，它使用距离向量路由协议的性质表明每个路由器只需要与它的成邻接的路由器通信，这样可以大大减小链路状态路由协议产生的洪泛问题。
4. 路由发现协议（Route Discovery Protocol）路由发现协议通常是物理网络发挥作用的协议。
当网路中有一个新的路由器被连接时，路由器会通过路由发现协议来发现新路由器，这样数据就可以经过新路由器并到达目的地。
无论是电路开通还是业务恢复，均需使用链路权重Link Cost和共享风险链路组SRLG。
所以在ASON网络一开始就要由操作者配置Link Cost和SRLG。
1，电路开通电路开通有三种方式：松散路由约束，半松散路由约束，和严格路由约束。
下面逐一说明。
松散路由约束：操作者只需指定电路的源和宿，路由选择完全由控制平面完成。
选路算法如下：a)在所有可选路径中选择路由经过的链路Link Cost之和最小的路径；b)如果有多条路径满足Link Cost之和最小，从中选择跳数（经过的节点数）最小的路径；c)如果仍有多条路径符合要求，从中选择网络碎片最少的路径。
（所谓碎片，即链路中不连续被使用的时隙（time slot）。
在其他因素相同的情况下，系统内部会根据链路的时隙使用情况来进行相应的碎片整理以避免网络碎片更多，即新建电路和恢复电路会选择碎片最大的路由，留下较大的管道给其他大颗粒电路使用。
例如对两条10G链路，一个10G中占用了一个时隙，另外一条10G链路中占用了2个时隙，如果后者的10G链路的时隙是连续的如时隙1和2，这时恢复时系统是不会区分这两条10G链路那个负载更多一些，而如果后者的10G链路的时隙是分离的如1和5，这时恢复时就会优先选用该条链路，因为它碎片程度更严重。
）半松散路由约束：操作者除了指定电路的源和宿，还指定希望经过的节点或链路，或不希望经过的节点和链路。
在路由选择中，在多条可选路径里，首先排除使用了不希望经过的节点和链路的路径，或保留使用了希望经过的节点和链路的路径。
然后按照松散路由的选路算法（如上a）到c))选择最优路径。
严格路由约束：操作者严格指定电路的源和宿，中间经过的节点、链路和时隙。
需要注意的是，如果建立PRC、SNCP和GR电路，则会涉及到主备两条路径。
以上选路算法适用于主用路径（工作路径），备用路径（保护路径）则选择尽量和主用路径SRLG（链路和节点）分离的路由。
运营商操作者需要在ASON网络启用初期，在网管上完成如下设置：将端口及相对应的链路资源加到ASON域；将多个属性相同的物理链路绑定为一个TE Link，如相邻节点间同方向的多个速率相同的物理链路可以设置绑定关系，本步骤不是必须的；为每个TE Link设置链路权重Link Cost；设置TE Link之间的风险共享关系SRLG。
第5.6章路由算法教学导入：TCP/IP网络中路由器的基本工作原理,介绍了IP路由器的几大功能,给出了静态路由协议和动态路由协议,以及内部网关协议和外部网关协议的概念,同时简要介绍了目前最常见的RIP、OSPF、BGP和BGP-4这几种路由协议。
教学内容：1距离向量算法2 链路状态算法3平衡混合路由算法一距离向量法(Distance Vector Routing)在距离向量法中，相邻路由器之间周期性地相互交换各自的路由表备份。
当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。
在图1中，每一个路由器从与之直接相邻的路由器处获得对方的路由表。
例如，路由器B从路由器A和C获得路由信息后，对自己的路由表进行加工，加工后的路由表再传送给路由器A和C。
路由器通过这种方法不断地积累路由信息，直到最终收敛为止。
图1 路由表传递示意1. 路由表的建立与更新在图2中，有三个路由器：A、B和C。
路由器A的两个网络接口E0和S0分别连接在10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1分别连接在10.2.0.0和10.3.0.0网段上；路由器C的网络接口S0和E0分别连接在10.3.0.0和10.4.0.0网段上。
图2 路由表内容列表如图2中各路由器路由表的前两行所示，通过路由器的网络接口到与之直接相连的网段的网络连接，其向量距离设置为0。
这即是最初的路由表。
当路由器B和A以及B和C之间相互交换路由信息后，它们会更新各自的路由表。
例如，路由器B通过网络端口S1收到路由器C的路由信息（10.3.0.0,S0,0）和（10.4.0.0,E0,0）后，在自己的路由表中增加一条（10.4.0.0,S1,1）路由信息。
该信息表示: 通过路由器B的网络接口S1可以访问到10.4.0.0网段，其向量距离为1，该向量距离是在路由器C的基础上加1获得的。
同样的道理，路由器B还会产生一条（10.1.0.0,S0,1）路由，这条路由是通过网络端口S0从路由器A获得的。
