论文部分内容阅读
摘要：近年来，随着计算机网络的日益普及，其现已成为各行各业中不可或缺的工具之一。由于互联网上的IP流量增长日益加剧，当前的互联网已经无法满足各种IP服务的需求，为此提高服务质量已经势在必行。正因如此，人们开始关注计算机网络路由的研究。基于此点，本文首先对计算机网络路由进行概述，进而分析了路由器技术，并在此基础上提出
关键词：计算机网络；网络路由；路由器技术；路由算法
中图分类号：TP393.02 文献标识码：A 文章编号：1007-9599 (2012) 10-0000-02
一、计算机网络路由概述
一直以来网络路由都是计算机网络领域中研究的关键问题。现如今，计算机网络的规模越来越庞大，网速也越来越快，各种媒体信息的传播都离不开网络这一载体，为此，对网络路由提出了更高的要求，路由算法更是层出不穷，无论是何种路由算法其最终目的都是为了寻找最佳路径对信息进行传递，以此来提高服务质量，并提高网络资源的整体利用率。计算机网络中的路由选择是一个比较复杂的问题，其不仅具有组合优化问题的性质，而且又属于其中的NP完全一类。由下面的例子中便可以看出这一问题的复杂性。例如，某一个网络具有21个节点，每个节点对应5条候选路由，若是采用枚举法大约需要尝试上亿次才能够得出全局最优解。换言之，就算以最快的计算机进行运算也需要近万年的时间，为此，只能采用近似算法或是随机算法。
通常在研究计算机网络设计中路由选择的优化过程中，在预先给定网络拓扑结构以及链路容量后，便可从中选出一条最佳的路由，进而达到数据信息经过网络的平均时延最小的目的，这样能够使资源的利用率最高。计算机网络路由的优化研究开始于对通信网络的分析，自此之后逐步渗透到计算机网络等领域当中。最初网络路由的效能分析方法仅仅局限于两个终端的问题上，近年来，随着大型网络系统的出现，使得这一分析变得更加复杂，许多新的计算方法和理论也随之出现。自上世纪70年代以来，网络路由的优化理论获得了长足的发展，大量与之有关的文献资料也都相继发表。有人提出使用条件概率的方法对路由的效能进行求解。上世纪70年代，印度的学者虽然对原有的算法进行了改进，但由于需要列举2 个状态，从而使得该方法在复杂的网络中无法适用。上世纪80年代，通过图论中的条件概率及边收缩原理对网络路由作出了相应的简化，但由于实现的过程较为复杂，故此该方法也未获得推广使用。在1986时有人提出了网络路由效能综合的概念，这一概念的提出是网络路由优化的研究更具实质性内容，同年我国以廖炯生为代表的多为专家学者在对路由效能进行系统研究的基础上，提出了一些数学改进算法，但是这些算法对于较为复杂的网络路由优化效果并不明显。直到1998年，巴拉巴斯与其同事在对万维网络拓扑结构的研究中发展，计算机网络并不完全是随机的，其具有一定的规律性，通过网络拓扑图能够清晰的看出，其所产生的是一条递减的曲线，而这种性质的网络被称为无标度网络。
二、路由器技术
近年来，随着互联网的快速发展以及用户数量的不断增多，形式各样的网络应用随之不断涌现，人们对于网络互联设备的安全性、稳定性以及各方面性能的要求也越来越高。路由器作为IP网络的核心设备之一，路由器技術现已成为网络领域研究的重点和热点课题，正因如此，越来越多的科研机构开始关注路由器的发展。通常情况下，路由器是在OSI/RM的网络层上工作的，其主要负责不同网络之间的数据转发、分粗以及存贮，并决定在网络间传输数据时的路由取向，可以说路由器是实现网间互联的必备设备之一。路由器最为基本的用途是能够将分开在多个逻辑上的网络进行连接，而该功能的实现需要路由器具备选择路径及网络地址判断的功能，这样才能在多个网络互连的环境中建立灵活的连接。路由器一般只接收其它路由传输过来的信息，其属于网络层中的一种互联设备。虽然路由器能够支持多种协议，但大部分路由都是在TCP/IP下运行。路由器一般可连接两个或两个以上由IP子网的逻辑端口，并且至少有一个物理端口。路由器按照接收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳的地址。而路由表的维护主要是通过与网络上其它路由器交换路由及链路信息来实现的。路由器通常由输入和输出端口、路由处理器以及交换网络等几个部分组成。输入端口既是报文接收点也是物理链路的连接点；输出端口主要负责缓冲及队列管理，同时利用复杂的调度算法能够实现QoS等功能；交换网络主要负责完成输入与输出端口间的互联；路由处理器则负责运行各种路由协议及系统软件，借此来实现维护计算转发表以及路由表等功能，这些功能既可以通过计算机硬件予以实现，也可以通过相应的软件予以实现。路由器最主要的作用就是为经过其中的每一个数据帧找到一条最佳的传输路径，并通过该路径将这些数据信息传送至目的节点。由此可见，最佳路径的选择策略即路由算法就是路由器的关键之所在。正常情况下，路由器中会保存有与各种传输路径相关的数据信息，这些数据就是我们所说的路由表，其可供路由选择路径时使用。在路由表中存储着大量的子网信息和下一个路由器的名称。
现阶段，TCP/IP网络基本都是利用路由器实现互连的，换言之，互联网就是由诸多IP子网并以路由器进行互连的国际性网络。该网络又被称之为以路由为基础的网络。路由器不但负责对IP分组进行转发，同时还负责与其它路由的联络。路由动作主要包括寻找最佳路径和转发这两项内容。寻找最佳路径通常是由路由选择算法予以实现的。由于这一过程中会涉及不同的路由选择算法及选择协议，故此该过程相对比较复杂。为了能够准确判定出最佳路径，路由选择算法应启动并维护含有路由信息的路由表。
三、路由算法的设计原则及其分类
（一）路由算法的设计原则
路由算法是指路由问题的求解方法与步骤，是计算机网络路由器的重要组成部分，采用何种算法往往能够决定最终的寻径结果。通常情况下，路由算法的设计应当遵循以下原则：
其一，最优性原则。是指路由算法选择最佳路径的能力。 其二，简洁性原则。路由算法力求设计简洁，在确保有效功能的前提下，减少软件开销成本。
其三，坚固性原则。路由算法即使处于不可预料和非正常环境下，也能够保证正常运行。由于路由器分布于网络连接点上，一旦其发生故障便会极易产生无法预知的严重后果，所以路由算法的设计必须能够经受时间的考验，并确保其在网络运行环境下具备可靠性。
其四，快速收敛性原则。收敛是指在最佳路径的判断上所有路由器达到一致的过程。当网络发生突发事件时，会引起路由处于可用或不可用状态。这时，路由器会发出更新信息，并将更新信息传播至整个网络，从而启动重新计算最佳路径的功能，直至所有路由器均处于公认的最佳路径，避免由于路由算法收敛慢而造成网络中断或路径循环。
其五，灵活性原则。路由算法应当准确、快速地适应各种网络环境，如当某个网段出现故障时，路由算法必须及时发现故障，同时为该网段中的所有路由重新选择最佳路径。
（二）路由算法的分类
路由算法能够使用多样化的度量标准来选择最佳路径，复杂的路由算法可以采用多种度量来选择路由，其常用度量包括以下几个方面，即路径长度、带宽、可靠性、负载、时延、通信成本等。路由算法包括非自适应和自适应两类。
1.非自适应算法是指不测量和不利用当前的网络拓扑结构和交通流量，而只是通过遵循某项原则选择路由。由于網络中有中心节点，它可以依据最佳路由算法来获取每对节点间的最佳路由，而后针对每个节点构建固定路由表，并在网络拓扑改变的状态下，重新计算和装入路由表，或者在各个路由相关节点上人工修改路由表。
2.自适应算法的路由主要以网络当前状态信息为依据进行选择，来设法适应不断变化的网络流量和拓扑结构。在自适应路由的选择过程中，当前能够提供的路由信息必须在网络节点间传送，所以，不可再用路由、改变的路由以及新的路由均可以在相应的路由表中得以反映。为了确保自适应路由选择的顺利实现，必须依靠路由选择协议，并采取计算最短路径的方法和定义交换路由选择信息的方式。现阶段，使用最为广泛的路由选择协议是链路状态路由选择和距离向量路由选择协议。链路状态算法，也被称为最短路径算法，是指发送路由信息到互联网上所有的节点。然而，就每个路由器而言，仅发送它的路由表中描述了其自身链路状态的一部分，而不是全部；距离向量算法是指每个路由器将路由表全部或部分信息发送到邻近节点上。两种路由选择协议的区别在于，链路状态算法可以在网络各处发送极少量的信息，距离向量算法是在邻接路由器上发送大量信息。链路状态算法具备较强的收敛性，相比较距离向量算法而言不易产生路由循环。此外，链路状态算法具有更强的CPU处理能力以及更大的内存空间，所以导致链路状态算法的运行成本较高。
参考文献：
[1]倪县乐,周卫华,曾志民,丁炜.高速路由交换技术的研究及展望[J].计算机工程与应用,2008,2
[2]刘怀亮,王东,徐国华.一种基于流量工程的网络端到端性能分析算法[J].系统工程与电子技术,2009,3
[3]于建军.宽带网络建设中基层交换技术的应用探讨[J].经济技术协作信息,2007,27
[4]王梓斌,郑袜华,向良军.基于专家决策的网络性能管理系统的设计[J].电脑知识与技术,2007,4
[5]休晓明,褚庆昕,朱明英等.一种新的自相似流量模型的网络性能分析[J].科学技术与工程,2007,14
[6]付方发,张庆利,王进祥等.支持多种流量分布的片上网络性能评估技术研究[J].哈尔滨工业大学学报,2007,5
[7]李旸.基于粒度计算智能的计算机网络路由研究[D].安徽大学,2007,4
关键词：计算机网络；网络路由；路由器技术；路由算法
中图分类号：TP393.02 文献标识码：A 文章编号：1007-9599 (2012) 10-0000-02
一、计算机网络路由概述
一直以来网络路由都是计算机网络领域中研究的关键问题。现如今，计算机网络的规模越来越庞大，网速也越来越快，各种媒体信息的传播都离不开网络这一载体，为此，对网络路由提出了更高的要求，路由算法更是层出不穷，无论是何种路由算法其最终目的都是为了寻找最佳路径对信息进行传递，以此来提高服务质量，并提高网络资源的整体利用率。计算机网络中的路由选择是一个比较复杂的问题，其不仅具有组合优化问题的性质，而且又属于其中的NP完全一类。由下面的例子中便可以看出这一问题的复杂性。例如，某一个网络具有21个节点，每个节点对应5条候选路由，若是采用枚举法大约需要尝试上亿次才能够得出全局最优解。换言之，就算以最快的计算机进行运算也需要近万年的时间，为此，只能采用近似算法或是随机算法。
通常在研究计算机网络设计中路由选择的优化过程中，在预先给定网络拓扑结构以及链路容量后，便可从中选出一条最佳的路由，进而达到数据信息经过网络的平均时延最小的目的，这样能够使资源的利用率最高。计算机网络路由的优化研究开始于对通信网络的分析，自此之后逐步渗透到计算机网络等领域当中。最初网络路由的效能分析方法仅仅局限于两个终端的问题上，近年来，随着大型网络系统的出现，使得这一分析变得更加复杂，许多新的计算方法和理论也随之出现。自上世纪70年代以来，网络路由的优化理论获得了长足的发展，大量与之有关的文献资料也都相继发表。有人提出使用条件概率的方法对路由的效能进行求解。上世纪70年代，印度的学者虽然对原有的算法进行了改进，但由于需要列举2 个状态，从而使得该方法在复杂的网络中无法适用。上世纪80年代，通过图论中的条件概率及边收缩原理对网络路由作出了相应的简化，但由于实现的过程较为复杂，故此该方法也未获得推广使用。在1986时有人提出了网络路由效能综合的概念，这一概念的提出是网络路由优化的研究更具实质性内容，同年我国以廖炯生为代表的多为专家学者在对路由效能进行系统研究的基础上，提出了一些数学改进算法，但是这些算法对于较为复杂的网络路由优化效果并不明显。直到1998年，巴拉巴斯与其同事在对万维网络拓扑结构的研究中发展，计算机网络并不完全是随机的，其具有一定的规律性，通过网络拓扑图能够清晰的看出，其所产生的是一条递减的曲线，而这种性质的网络被称为无标度网络。
二、路由器技术
近年来，随着互联网的快速发展以及用户数量的不断增多，形式各样的网络应用随之不断涌现，人们对于网络互联设备的安全性、稳定性以及各方面性能的要求也越来越高。路由器作为IP网络的核心设备之一，路由器技術现已成为网络领域研究的重点和热点课题，正因如此，越来越多的科研机构开始关注路由器的发展。通常情况下，路由器是在OSI/RM的网络层上工作的，其主要负责不同网络之间的数据转发、分粗以及存贮，并决定在网络间传输数据时的路由取向，可以说路由器是实现网间互联的必备设备之一。路由器最为基本的用途是能够将分开在多个逻辑上的网络进行连接，而该功能的实现需要路由器具备选择路径及网络地址判断的功能，这样才能在多个网络互连的环境中建立灵活的连接。路由器一般只接收其它路由传输过来的信息，其属于网络层中的一种互联设备。虽然路由器能够支持多种协议，但大部分路由都是在TCP/IP下运行。路由器一般可连接两个或两个以上由IP子网的逻辑端口，并且至少有一个物理端口。路由器按照接收到数据包中的网络层地址以及路由器内部维护的路由表决定输出端口以及下一跳的地址。而路由表的维护主要是通过与网络上其它路由器交换路由及链路信息来实现的。路由器通常由输入和输出端口、路由处理器以及交换网络等几个部分组成。输入端口既是报文接收点也是物理链路的连接点；输出端口主要负责缓冲及队列管理，同时利用复杂的调度算法能够实现QoS等功能；交换网络主要负责完成输入与输出端口间的互联；路由处理器则负责运行各种路由协议及系统软件，借此来实现维护计算转发表以及路由表等功能，这些功能既可以通过计算机硬件予以实现，也可以通过相应的软件予以实现。路由器最主要的作用就是为经过其中的每一个数据帧找到一条最佳的传输路径，并通过该路径将这些数据信息传送至目的节点。由此可见，最佳路径的选择策略即路由算法就是路由器的关键之所在。正常情况下，路由器中会保存有与各种传输路径相关的数据信息，这些数据就是我们所说的路由表，其可供路由选择路径时使用。在路由表中存储着大量的子网信息和下一个路由器的名称。
现阶段，TCP/IP网络基本都是利用路由器实现互连的，换言之，互联网就是由诸多IP子网并以路由器进行互连的国际性网络。该网络又被称之为以路由为基础的网络。路由器不但负责对IP分组进行转发，同时还负责与其它路由的联络。路由动作主要包括寻找最佳路径和转发这两项内容。寻找最佳路径通常是由路由选择算法予以实现的。由于这一过程中会涉及不同的路由选择算法及选择协议，故此该过程相对比较复杂。为了能够准确判定出最佳路径，路由选择算法应启动并维护含有路由信息的路由表。
三、路由算法的设计原则及其分类
（一）路由算法的设计原则
路由算法是指路由问题的求解方法与步骤，是计算机网络路由器的重要组成部分，采用何种算法往往能够决定最终的寻径结果。通常情况下，路由算法的设计应当遵循以下原则：
其一，最优性原则。是指路由算法选择最佳路径的能力。 其二，简洁性原则。路由算法力求设计简洁，在确保有效功能的前提下，减少软件开销成本。
其三，坚固性原则。路由算法即使处于不可预料和非正常环境下，也能够保证正常运行。由于路由器分布于网络连接点上，一旦其发生故障便会极易产生无法预知的严重后果，所以路由算法的设计必须能够经受时间的考验，并确保其在网络运行环境下具备可靠性。
其四，快速收敛性原则。收敛是指在最佳路径的判断上所有路由器达到一致的过程。当网络发生突发事件时，会引起路由处于可用或不可用状态。这时，路由器会发出更新信息，并将更新信息传播至整个网络，从而启动重新计算最佳路径的功能，直至所有路由器均处于公认的最佳路径，避免由于路由算法收敛慢而造成网络中断或路径循环。
其五，灵活性原则。路由算法应当准确、快速地适应各种网络环境，如当某个网段出现故障时，路由算法必须及时发现故障，同时为该网段中的所有路由重新选择最佳路径。
（二）路由算法的分类
路由算法能够使用多样化的度量标准来选择最佳路径，复杂的路由算法可以采用多种度量来选择路由，其常用度量包括以下几个方面，即路径长度、带宽、可靠性、负载、时延、通信成本等。路由算法包括非自适应和自适应两类。
1.非自适应算法是指不测量和不利用当前的网络拓扑结构和交通流量，而只是通过遵循某项原则选择路由。由于網络中有中心节点，它可以依据最佳路由算法来获取每对节点间的最佳路由，而后针对每个节点构建固定路由表，并在网络拓扑改变的状态下，重新计算和装入路由表，或者在各个路由相关节点上人工修改路由表。
2.自适应算法的路由主要以网络当前状态信息为依据进行选择，来设法适应不断变化的网络流量和拓扑结构。在自适应路由的选择过程中，当前能够提供的路由信息必须在网络节点间传送，所以，不可再用路由、改变的路由以及新的路由均可以在相应的路由表中得以反映。为了确保自适应路由选择的顺利实现，必须依靠路由选择协议，并采取计算最短路径的方法和定义交换路由选择信息的方式。现阶段，使用最为广泛的路由选择协议是链路状态路由选择和距离向量路由选择协议。链路状态算法，也被称为最短路径算法，是指发送路由信息到互联网上所有的节点。然而，就每个路由器而言，仅发送它的路由表中描述了其自身链路状态的一部分，而不是全部；距离向量算法是指每个路由器将路由表全部或部分信息发送到邻近节点上。两种路由选择协议的区别在于，链路状态算法可以在网络各处发送极少量的信息，距离向量算法是在邻接路由器上发送大量信息。链路状态算法具备较强的收敛性，相比较距离向量算法而言不易产生路由循环。此外，链路状态算法具有更强的CPU处理能力以及更大的内存空间，所以导致链路状态算法的运行成本较高。
参考文献：
[1]倪县乐,周卫华,曾志民,丁炜.高速路由交换技术的研究及展望[J].计算机工程与应用,2008,2
[2]刘怀亮,王东,徐国华.一种基于流量工程的网络端到端性能分析算法[J].系统工程与电子技术,2009,3
[3]于建军.宽带网络建设中基层交换技术的应用探讨[J].经济技术协作信息,2007,27
[4]王梓斌,郑袜华,向良军.基于专家决策的网络性能管理系统的设计[J].电脑知识与技术,2007,4
[5]休晓明,褚庆昕,朱明英等.一种新的自相似流量模型的网络性能分析[J].科学技术与工程,2007,14
[6]付方发,张庆利,王进祥等.支持多种流量分布的片上网络性能评估技术研究[J].哈尔滨工业大学学报,2007,5
[7]李旸.基于粒度计算智能的计算机网络路由研究[D].安徽大学,2007,4