计算机网络中的路由算法

计算机网络原理 链路状态路由

在1979年以前，ARPANET使用的一直是距离矢量路由选择算法，而在此之后则改为链路状态路由选择算法。两个主要问题导致了距离矢量路由选择算法的消亡。第一，因为延迟度量是队列长度，所以在选择路径的时候并没有考虑线路带宽。开始，所有的线路都是56kbps，因此线路带宽并不是待考虑的因素，但是当有些线路被升级到230kbps乃至1.544Mbps之后，带宽因素就变成了一个重要的问题。当然，也可以将延迟度量中将线路带宽因素考虑进去。但是，第二个问题仍然存在，也就是距离矢量路由选择算法需要很长时间才能收敛到稳定状态（无穷计算的问题）。由于这些原因，距离矢量路由选择算法被一个全新的算法所替代，该算法称为链路状态路由算法（Link State Routing）。现在，各种各样的链路状态路由选择算法得到了广泛的应用。

隐藏在链路状态路由算法背后的思想十分简单，可以分5个部分加以描述。每一个路由器必须完成以下的工作：

 发现它的邻节点，并知道其网络地址。

 测量到各邻节点的延迟或者开销。

 构造一个分组，分组中包含它刚知道的所有信息。

 将这个分组发送给所有其他路由器。

 计算出到每一个其他路由器的最短路径。

事实上，完整的拓扑结构和所有的延迟信息都使用实验的方法来测量，并分发给每一个路由器。然后每个路由器用Dijkstra算法就可以找出从它到每一个其他路由器的最短路径。

计算机⽹络-4-6-路由选择协议RIP

互联⽹的路由选择协议

有关路由选择协议的基本概念

理想的路由算法

路由选择协议的核⼼是路由算法。即需要⼀种算法来获取路表中的各项，⼀个⽐较好的路由选择算法应该有以下特点[BELL86]:

1. 算法必须是正确和完整的。（正确的含义是沿着各路由表所指引的路由，分组⼀定能到达最终⽬的⽹络和主机）

2. 算法在计算上应该简单。(路由选择的计算不应该使⽹络通信量增加太多的额外开销)

3. 算法能够适应通信量和⽹络拓扑的变化，也就是⾃适应性。（当⽹络中的通信量发⽣变化的时，算法能够⾃适应的改变路由以均衡各

路由的负载。当某个或者某些结点链路发⽣故障的时候，算法能够及时的改变路由，有时候称这种适应性为稳健性）4. 算法应该具有稳定性。(在⽹络通信量和⽹络拓扑结构相对稳定的情况下，路由算法应该收敛于⼀个可以接受的解，⽽不应该使得出的

路由不断地发⽣变化。)5. 算法是公平的。(路由选择算法应该对所有⽤户(除了少数优先⾼级的⽤户)都是公平的。)

6. 算法应该是最佳的。(路由选择算法应当能找出最好的路由，使得分组平均时延最⼩⽽⽹络的通信量最⼤。虽然我们希望得到“最佳”的

算法，但并不是最重要的，对于某些⽹络来说，⽹络的可靠性有时要⽐最⼩的分组平均时延或最⼤吞吐量更加的重要，因此，所谓"最

佳"只能是相对于某⼀种特定要求下得出的⽐较合理的选择⽽已。)

⼀个实际的路由选择算法，应该尽可能的接近于理想的算法，在不同的应⽤条件下，可以对上⾯提出的六个⽅⾯有不同的侧重。

倘若从路由算法能否随⽹络的通信量或拓扑⾃适应的进⾏调整变化来划分，则只有两⼤类：静态路由选择策略和动态路由选择策略。静态路

由选择策略也叫做⾮⾃适应路由选择，其特点是简单和开销较⼩，但不能即使适应⽹络状态的变化。对于很简单的⼩⽹络，完全可以采⽤静

态路由选择，⽤⼈⼯配置每⼀条路由。动态路由选择也叫做⾃适应路由选择，其特点是能够较好的适应⽹络状态的变化，但实现起来较为复

计算机网络路由研究综述　杨啸　（四川师范大学服装学院四川・成都６１０ｌ０１）　摘要本文通过结合计算机网络路由的相关知识点，包括网络路由的基本内容、路由算法的设计原则及其　分类，以及非白适应路由算去和自适应路由算法，分析和探究计算机网络路由技术的应用情况，并给予一些　参考建议。　关键词计算机网络网络路由　路由算法　中图分类号：ＴＰ３９３　文献标识码：Ａ　０引言　近年来，随着现代化技术的蓬勃发展，计算机网络路　由技术在互联网的改革和应用也越来越受到人们的普遍　关注和重视。作为计算机网络的关键性技术，网络路由主　要充当着寻找数据包从源地址到目的地址之间的最优路　径的角色。通过对计算机网络路由相关知识点的分析和　探究，对于实现计算机网络数据传输、资源共享有着重要　的意义。为此，本文主要通过网络路由的基础知识点、网　络路由算法的设计和分类等方面，以及对几种网络路由算　法的浅析，促进人们对计算机网络路由的了解和掌握，对　于实现网络化和世界化的计算机网络建设提供一些帮助。　１计算机网络路由概述　新形势下，随着计算机网络技术的快速发展，对计算　机网络路由的研究脚步也是日趋加快，尤其是在网络路由　的算法、路径选择和路由设备，以及网络路由服务等方面，　更加受到ＩＴ行业的关注和重视。在划分计算机网络路由　上，可以通过网络性质、通信方式、路由算法和对路由的要　求等几个方面划分。若按照网络性质划分，网络路由有计　算机系统路由、有线网络路由和无线网络路由等三种，按　照通信方式则可以分为单播路由、多播路由及Ａｎｙｃａｓｔ路　由，按照路由算法划分，则有源路由算法、分布式路由算法　以及分级路由算法。　２计算机网络路由的构成　２．１路由器　路由器是基于网络路由技术研发出来的硬件设备，　能够让不同网段或网络的终端设备实现通信和数据共　享。路由器不但能够完成不同网段及网络间数据的存　储、分组和转发，而且具有判断网络地址和进行路径选　择的功能，是网络技术的核心设备之一。　４８　ｌ　２０１３年３（上）・电脑连　２．２路由协议　路由协议是网络路由发送ＩＰ数据包过程中所要遵　守的规定和标准。路由协议可以根据使用范围、路由可　变性路径进行划分。按照使用范围划分，主要有内部网　关协议（ＩＧＰ）和外部网关协议（ＥＧＰ），按照路由可变性路　径划分，通常可以划分为静态路由和动态路由。其中，静　态路由具有适用于小规模的网络通信，配置较为简单的　特点。就目前来看，常用的路由器协议主要是ＲＩＰ协议、　ＯＳＰＦ协议和ＢＧＰ协议等几种。　２．３路由算法　在路由路径选择过程中，通常要用到路由算法进行计　算，求解路由最优路径。按照不同的要求分类，路由算法　的划分也不尽相同，不过最终都是为了寻求最佳路径。　至于路由算法的设计原则，通常情况下，有最优性原　则、简洁性原则、坚固性原则、快速收敛性原则和灵活性原　则等几种。最优性原则要求路由算法具有选择最佳路径　的能力；简洁性原则要求路由算法在具备路由基本功能的　基础上，设计简洁、降低成本；坚固性原则要求路由算法在　受到外界或内部特殊环境的干扰下，能够正常运行，以保　证网络通畅；快速收敛性原则，是当路由在遇到网络故障　时，能够及时将更新信息发给同个网络的路由，并重新计　算最佳路径，直到故障排除方才恢复数据传输：而灵活性　原则，则要求路由算法在设计时，具有快速适应各类网络　环境的功能。　３计算机网络路由算法　按照不同的标准划分，网络路由算法可以分为非自适　应算法和自适应算法，单播路由算法和多播路由算法等，　度量选择（即路径长度、带宽、可靠性、负载等）不同，划分　也有差别。这里只分析非自适应路由算（下转第６４页）

论计算机网络路由及其优化　

宁志华（太原理工大学，山西晋中０３０６００）　网络地带・　

摘　要：网络路由，是实现网络连接并满足不同网络之间信息传导的一种有效设备。伴随计算机网络技术的进一步发展与提升，计算机网络　的应用越来越普及化，我国计算机网络使用的用户正在逐年递增，而大规模、全面性的网络覆盖加大了计算机网络路由的工作量，使得计算　

机网络路由需要接受更大的挑战。为加强计算机网络路由的功能，提高计算机网络的安全性、稳定性、速度性，需要优化计算机网络路由以　及优化网络路由计算方法。在此，本文将重点探讨计算机网络路由及其优化。　关键词：计算机；网络路由；优化　

１网络路由及多样性种类　

网络路由，是实现网络连接并满足不同网络之间信息传导　

的一种有效设备。随着网络路由使用的普及化，网络路由也逐　

渐研究出多样性的种类，其中单播路由、多播路由、Ａｎｙｃａｓｔ　

路由是根据网络的通信方式来划分的类型，而根据网络路由计　

算方式来划分，具有分级路由计算方式、分布式路由计算方式、　

源路由计算方式三大类。分级路由计算方式，即对网络节点实　

行分级，以此来掌握每一个节点自身运行工作范围内的情况，　

并及时了解远处上级节点的大致情况，从而实现对系统全局运　

行实际情况的掌握。分布式路由计算方式，根据运行路径的实　

际需求能够掌握网络的局部情况，即掌握相邻节点之间剩余宽　

带、传播延迟、排队延迟等运行情况，以决定下一节点的运行走　

向。源路由计算方式，在网络运行路径中设置源节点，以通过每　

一个节点来掌握系统全局运行的实际情况，通过对源节点发送　

信息来决定整个系统的运行路径。　

２计算机网络路由优化及其优化算法　

２．１计算机网络路由优化　路由优化，即指对路由协议、路由策略进行整合，从而达　

到简化复杂网络的目的。计算机网络路由优化能够有效保障网　

络的稳定性、安全性、伸缩性、快速收敛，进而实现网络的高性　

能。其中，路由过滤、策略路由是较常使用的两种计算机网络路