基于核心路由器的路由选择最优化算法研究与实现（毕业论文设计）.doc

基于核心路由器的路由选择最优化算法研究与实现 论文摘要*（中文） 论文摘要*（英文）目录引言随着高速网络技术和多媒体技术的飞速发展，计算机网络的应用已经渗透到生活当中的各个领域，网络在整个经济发展中的作用越来越重要，带来的价值也越来越多。人们越来越多地提出了包括多媒体通信在内的综合服务要求。在新一代网络上提供高水平服务质量保证己经成为目前计算机网络研究的主要课题。 近几年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用。当前的现状是，随着计算机应用的普及，互联网用户激增，过度到IPv6势在必行，但IPv6虽然解决了IP匮乏的问题，但随着网络用户的增加而产生的网络流量却仍然是阻碍互联网服务质量提高的绊脚石。日益暴增的网络流量对核心路由器的转发能力提出了新的挑战，而研究路由选择算法提高路由选择的速度对于提高核心路由器的性能有着重要的意义！路由器的定义路由是指通过互相连接的网络把信息从源地点移动到目标地点的活动。一般在路由过程中，信息会进过一个货多个中间节点。普通用户通常容易将路由和交换的概念混淆。其实，两者之间的主要区别就是交换发生在OSI参考模型的第二层（数据链路层），而路由发生在第三层，即网络层。这一区别决定了路由和交换在移动信息的过程中需要使用不同的控制信息，所以两者实现各自功能的方式是不同的。 路由器是互联网络的枢纽，是“交通台个警察”，是互联网的主要节点设备。路由器通过路由决定数据的转发。转发策略称为路由选择，这也是路由器名称由来。作为不同网络之间相互连接的枢纽，路由器系统构成了机遇TCP/IPD的国际互联网络的主体脉络，也可以说，路由器构成了Internet的骨架。他的处理速度是网络通信的瓶劲之一，其可靠性则直接影响着网络互连的质量。因此，在园区网、地区网乃至整个Internet研究领域中，路由技术始终处于核心地位，其发展历程和方向，成为整个Internet研究的一个缩影。路由选择算法概述由于某些关键特性的不同，各种路由选择算法也不同。首先，算法设计者的设计目标会影响路由选择协议的运行结果；其次，现有各种路由选择算法对网络和路由器资源的影响不同；最后，不同的计量标准也会影响最佳路径的计算结果。下面分别讨论这些路由选择算法的特性。1设计目标路由选择算法通常具有下列一个或多个设计要求：（1） 最优性。最优性是指路由选择算法选择最优路径的能力。最优路径取决于计量标准和计算权值，例如一个路由选择算法同时考虑途经站点的数目和延迟开销，但在计算过程中更重视延迟开销。因此，路由选择协议必须严格定义其计算方法。（2） 简易性和低开销。路由选择算法应尽可能地简单。换句话说，路由选择算法必须用最低的软/硬件开销来提供最有效的功能。实现路由选择算法的软件运行在物理资源有限的计算机上，效率显得尤为重要。（3） 强壮性和稳定性。路由选择算法必须具有强壮性，这意味着他们必须在出现异常或非预见性情况时（如硬件故障，高负荷状态和不正确的操作）也能正常运行。由于路由器位于网络节点上，发生故障时会引起更为严重的问题。因此，路由选择算法必须经受时间的考验，且在各种不同的网络环境下有很好的稳定性。（4） 快速收敛性。路由选择算法必须能够迅速收敛。收敛是指所有路由器都承认新的最有路由的过程。当一个网络由于某种时间造成路由设备停机或开通时，路由器就会发送修正路由信息，该消息在网络上传播，引发路由器重新计算最优路由，并最终促使所有路由器承认新的最优路由。路由选择算法收敛过慢，会导致路由循环或网络发生故障。例如假设数据包在时间t1到达路由器1，此时路由器1已经被更新，它知道的到达目的节点的路由是最优路由，该路由要求路由器2成为下一个节点。因此，路由器1转发数据包到路由器2。但如果路由器2还未被更新，它认为最优路由的下一个节点是路由器1.路由器2又把数据包发送回路由器1.这样，数据包持续在这两个路由器之间来回传送，直到路由器2收到路由修正命令或者达到数据包允许转发的最大的次数为止。（5） 灵活性。这意味着路由选择算法必须迅速准确地适应不同的网络环境。例如假设某一网段失灵了，路由选择算法在意识到在个问题后，应尽快为所有路由选择最佳路径，避免使用那段网络。路由选择算法在设计时应能够适应网络带宽，路由器队列大小和网络延迟等变化。2路由选择算法类型路由选择算法类型按类型划分，路由选择算法主要包括以下几种：1)静态和动态路由选择算法严格地说，静态路由选择算法不是一种算法，因为网络管理员在路由选择开始前就i建立了映射表，如果网络管理员不改变它们，映射将保持不变。静态路由选择算法设计0单，并在网络信息流相对可以预见且网络设计相对简单的环境里效果较好。 由于静态路由选择算法不能对网络的变化作出反映，所以，它不适应当今大型、易茎的网络环境的需求。20世纪90年代以来，绝大多数优秀的路由选择算法都是动态的，这些动态路由选择算法通过分析接收到的路由修正消息适应网络环境的变化。当路由器接收5网络发生变化的消息后，就会重新计算路由，并向其他路由器发出路由修正消息。其他自路由器接收到这些消息后，将重复上述过程直至所有路由器的路由表更新完毕。 静态路由选择算法可以弥补动态路由选择路算法的某些不足。例如为所有无法选择8由的数据包指定一个最终路由器，即将所有无法选择路由的数据包转发到该路由器来，U保证所有数据包都得到某种方式的处理。 2)单路径和多路径路由选择算法 一些复杂的路由选择协议支持多路径到达同一目的节点，与单路径算法不同，这些i路径算法允许信息流在多条线上进行复制。多路径算法的优势是提高了数据吞吐率和5靠性。 3）平面和分层路由选择算法 一些路由选择算法在平面空间运行，而另一些路由选择算法采用分层空间运行。在平面路由选择算法中，所有路由器是对等的，而在分层路由选择算法中，路由器被划分成主干路由器和非主干路由器。来自非主干路由器的数据包先被传送到主干路由器中，然后退过主干路由器转发到目的节点域，最后通过一个或多个非主干路由器到达目的节点。 路由系统常将逻辑节点组称为域、自主系统或区域。在分层路由选择算法中，任一域中只有一部分路由器可以与其他域中的路由器通信，而其他路由器只能与该域中的路由器通信。在超大型的网络中，可能还存在更多的层次，一般都是位于最高层的路由器形成路由器的主干。 分层路由类似公司的组织结构，其主要优点是能较好地支持信息流模式。由于大多数网络通信发生在小公司群(域)中，且域内路由器只需要了解域内的其他路由器即可。因此，可以简化它们的路由选择算法，以相应地减少路由修正消息流发布。 4)主机智能和路由器智能路由选择算法 一些路由选择算法假定源节点决定整个发送路由，这就是通常所说的源路由选择(so毗e routlng)。在源路由选择系统里，路由器只是一个存储和发送设备，负责向下一节点发送数据包。在这种系统中，主机具有路由选择的智能。 而其他的算法假定主机对路由器一无所知，路由器根据自己计算的结果来确定互联网上的路径。在这种系统中，路由器具有路由选择的智能。 虽然主机智能路由选择算法在实际发送数据包之前就能发现到达目的节点的所有可能的路由，并能根据不同系统对最优路由的不同要求做出选择，但这种选择所有路径的方法常常需要耗费大量的时间。把主机智能路由选择算法与路由器智能路由选择算法结合起来使用是一种较好的方法。5)域内和域问路由选择算法 一些路由选择算法只在域内运行，而另一些路由选择算法可在域内或域间运行。这两种算法在本质上存在不同。因此，一个最优的域内路由选择算法并不一定是最优的域问路由选择算法。 6)链接状态和距离向量路由算法 链接状态路由算法(也称作最短路径优先算法)将路由信息发送至互联网络的所有节点上，每个路由器只能传递描述其自身链接状态的那部分的路由表。而距离向量路由算法(也称作贝尔曼一福特算法)要求每个路由器将路由表的全部或部分传送到与其相邻的路由器中。实际上，链接状态路由算法的更新消息只传送路由表更新的部分，而距离向量路由算法的更新消息将传送路由表的大部分或全部传送到与其相邻的路由器中。 由于链接状态路由算法收敛速度较快，因此，它比距离向量路由选择算法更易避免路由循环。但由于链接状态路由算法需要占用更多的CPU和内存资源，因此，它比距离向量路由算法更难以支持和实现。总的来说，这两种算法在大多数情况下运行良好。路由选择计量标准前面介绍过，路由表中包含软件选择的最佳路径的信息，但路由表是如何建立的呢？路由选择表中包含的信息是什么性质的呢？路 由悬着算法又是如何决定最佳路由的呢？路由选择算法使用许多不同的计量标准确定最佳路由，一些复杂的路由选择算法将多多种计量标准融为一体。常用的伎俩标准有如下几种：（1） 路径长度。路径长度（path length）是最普通的一种计量标准。在路由选择协议允许网络管理员为每条网络链路分配任意权值的情况下，路径长度是指所经过的每条链路的权值之和。而在路由选择协议定义了站点数的目的情况下，路径长度是指数据包从源节点到目的节点过程中通过网络产品（路由器）的数目。（2） 可靠性。可靠性（reliability）是指每个网络链路的可靠性（通常比特-错误率描述），即网络链路是否容易出现网络故障，一旦发生故障，是否能迅速修复。在进行可靠性登记分配时，应将考虑所有影响可靠性的因素。通常由网络管理员给网络连累分配可靠性等级。，而这些等级一般用数值表示。（3） 路由选择延迟。（routing delay）路由选择延迟至的是通过互联网络从源节点法搜是发送数据包到目的节点所需的时间，延迟时间取决于诸多因素，其中包括网络链路的贷款及网络堵塞成都沿途每个路由器端口的队列和传输的物理距离等。由于延迟受几种重要因素的影响，因此，它是一种应用最广且最有用计量标准。（4） 带宽。带宽（bandwidth）是指链路传输信息流的能力。在所有其他条件相同的情况下，10Mb/s以太网链路显然优于64Kb/s的租用链路。尽管带宽越大表示链路传输能力越强，但通过较大带宽链路的路由并不一定比通过较慢链路的路由更好，因为如果较快的链路非常繁忙，那么，通过它想目的节点传送数据包所需的实际时间可能会更长。（5） 负载。负载（load）是指网络资源（如路由器）的繁忙成都。他可用多种方式精心计算。其中包括CPU的利用率和美妙处理数据包的次数。当然，持续不断堤监控这些负载参数本身就会占用资源。（6） 通信开销。通信开销（communication）是另外一种重要的伎俩标准，尤其是当公司关心运行费用胜过运行性能的时候。对于这些公司来说他们宁可将数据包在自己的链路上进行传输（即使这样可能增加链路延迟）也不愿意花钱（省时间）在公用链路上传输。路由选择的几个重要目标不管是为每个分组单独地选择路由，还是仅当建立新连接时选样路由，都希望路由选择算法具有某些特征：正确性（correctness）、简单性（simplicity）、健壮性（robustness）、稳定性（stability）、公平性（fairness） 和最优性（optimality）。正确性和简单性不需过多解释，但对健壮性的需要可能开头并不清楚，一旦一个重要的网络投入使用，可能希望它能无变化无错误地连续运行几年。在这期间，会有这样或那样的软硬件错误，主机、路由器和线路将增加或撤除，拓扑结构要多次改变，路由选择算法必须能妥善处理拓扑结构和通信量的变化，而不会使所有主机中的作业部终止，也不必每当某些路由器崩溃时，都要更新启动该网络。 稳定性也是路由选择算法的重要目标，有的路由选择算法不管运行了多长时间， 都不可能趋于稳定， 公平性和最优性是显而易见的肯定没有人反对，但结果证明它们常常是矛盾的。作为这种矛盾的一个简单的例子，参见图5-4。断定在A和A，B与B和C与C间的通信总是足以使图中水平链路处于饱和，为了使流量达到最大，X与X应该完全切断数据传送。 不幸的是，X与X可能都不知道这一点，于是有必要在全局效率与单个连接的公平性之间进行适当的折衷。在我们能够找到公平性与最优性间的平衡办法之前，必须确定要对什么进行优化。虽然减少分组平均延迟是一个明显的考虑因素，而提高网络的总吞吐量也很重要。此外，使用接近容量限制的队列系统暗示着会有很长的队列延迟，因此，这两个目标也是相矛盾的。作为一种折衷的办法，许多网络试图使分组必须经过的站点减至最少。因为减少站点数量，有助于改进延迟，也能减少所消耗的带宽，最终将有助于改进吞吐量。Dijkstra算法原理Dijkstra算法是解决带权图（权为非负数）的单源最短路径问题的一种贪心算法，它要一个一个地找出从某一源点出发到所有其他顶点的最短路径。Dijkstra算法的本质是能够确定路径的顺序。按照加权长度顺序首先找出最短路径，直至最后找出最长路径。对每个顶点v,Dijkstra算法将记录三条信息。（1） Kv是一个布尔值型的标记，它标明到定点V的最短路径已经知道。对所有的V，其初始值为Kv=false。（2） Dv是从Vs到V的以知道的最短路径长度。算法开始之前，最短路径是未知的，Dv也是不确定的，在算法执行期间，算法检查候选路径并修改Dv的值。最初，对所有的V，当VVs时，Dv=；当V=Vs时，Dv=0.（3） Pv是顶点的前驱，即从Vs到V的最短路径具有形式Vs,，Pv，V 。最初，对所有的V，Pv都是未知的。Dijkstra算法分阶段执行，每次都执行下列步骤：（1） 从Kv=false的顶点集合中，选出具有最小估计距离Dv的顶点V。（2） 使Kvtrue。（3） 对每个Kvtrue且邻接于顶点V的顶点w，检查dw是否大于dv+C(v，w)，C（v，w）是连接顶点v和w的边的权值。若大于，使dwdv+C(v,w),pwv。在每次执行过程中，只有一个顶点的kv设置为true。在执行n次后算法中止，所有的最短路径都已经找出。表11.1是Dijkstra算法的示例，列出了Dijkstra算法作用于图11.11中所示的图时各步的状态表，其源顶点是b。 表11.1Dijkstra算法运行过程顶点遍数初值123456a3b3b3b3b3b3bb0-0-0-0-0-0-0-c5b4a4a4a4a4ad6c6c6c6ce8c8c8c8cf11d9e9e图11.11 有向图最初，除顶点b的初值为0之外，其余各定点的最短路径长度估计值均赋初值为，因此在第一遍中可选顶点b。表中表四最短路径已经知道（）。然后，顺着顶点b发出的两条边即ba及bc，并相应地跟新它们的长度估计值。顶点a的新长度为3，顶点c的新长度为5。在这两种情况中，最短路径上a与c的下一个顶点均为b。在第二遍中，选择顶点a，并在数据项旁边标记以表明至它的最短路径长度已经知道，从a至c有一条边ac。从b开始经过a至c的长度为4，由于它小于b至c的路径长度5，所以顶点c被赋予新的值4，并把它的前驱赋予路径a。按照以上方式进行n遍，直至找出所有的最短路径。图11.12就是最终结果，它的顶点旁边标有从b至v的最短路径长度。每个顶点（除b外）都只有一条发射边，把它和它的下一个顶点连接起来，逆向构造一条b至v的最短路径。图11.12 图11.11的最短路径图Dijkstra算法实现Dijkstra算法利用了TableEntry数据结构，每个TableEntry具有known、distance、predecessor三个域，对应变量Kv，dv，pv。首先介绍Dijkstra算法的数据结构。Struct TableEntrybool known;int distance;Vertex:Number predecessor;TableEntry():known(false),distance(numeric_limits:max();Class Assoc:public Associationint priority;public: Assoc(int p,Object&object):Association(priority,object),priority(p) rescindOwnership(); 函数DijkstraAlogrihm有两个参数，第一个参数是一个指向有向图实例的const型引用，这个有向图是一个边带权图，且权是int类型。第二个参数也是const型引用，是一个指向起始点（顶点）的引用。Digraph&DijkstraAlgorithm（Digraph const& g，Vertex const& s）unsigned int const n=g.NumberofVerties();Arraytable(n);PriorityQueue& queue=*new BinaryHeap(g.NumberofEdges();tables.distance=0;Queue.Enqueue(*)new Assoc(0,const_cast(s);While(!queue.IsEmpty() Assoc& assoc=dynamic_cast(queue.DequeueMin(); Vertex& v0=dynamic_cast(assoc.Value(); if(!tablev0.known) Tablev0.known=true; Iterator& p=g.EmanatingEdges(v0); While(!p.IsDone() WeightedEdge& edge=dynamic_cast(*p); Vertex& v1=edge.V1(); int& weight=dynamic_cast(edge.Weight(); int const d=tablev0.distance+weight; if(tablev1.distanced) tablev1.distance=d; tablev1.predecessor=v0; queue.Enqueue(*new Assoc(d,v1);+p; delete &p;delete &assoc;delete &queue;Diraph& result=*new DigraphAsLists(n);for(Vertex:Number v=0;vn;+v)result.AddVertex(*new WeightedVertex(v,*new int(tablev.distance); for(Vertex:Number v=0; vn; +v)if(v!=s) result.AddEdge(*new Edege(resultv,resulttablev,predecessor);return result;Kruskal算法原理 假设G=(V,E)是一个具有n个顶点的边带权无向图，T=（U,TE）是G的最小生成树，U的初值等于V，即包含有G种的全部顶点，TE的初值为空。此算法的基本思想是：将图G中的边按权值从大道小的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留为T的一条边，若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止，此时的T即为最小生成树。图11.9是边带权无向图，图11.10是Kruskal算法作用于图11.9的处理过程。图11.9图11.10Kruskal算法要计算顶点集V的分区，最初的分区是由n个单顶点集构成的，即=，, 。当从边集数组中按次序选取一条边时，若它的两个端点分属于不同的集合，则表明此边联通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，此边应保留作为生成树的一条边，同时把端点所长的两个集合合并成一个，即成为一个连通分量；当选取的一条边的两个端点同属于一个集合时，此边应放弃，因同一个集合中的顶点是连通无回路的，若再加入一条边则必产生回路。在上述离子中，Kruskal算法计算了下列分区序列：=a,b,c,d,e,f=a,d,b,c,e,f=a,d,b,c,e,f=a,d,b,c,e,f=a,d,c,e,f,b=a,b,c,d,e,fKruskal算法实现函数KruskalAlgorithm的参数指向带权无向图的const型引用，且权时int类型。结果将以带权无向图的形式返回。Graph&KruskalsAlgorithm(Graph const& g)unsigned int const =g.NumberOfVertices();Graph& result=*new GraphAsLists(n);for(Vertex:Number v=0; vn; +v) result.AddVertex(*new Vertex(v);PriorityQueue& queue=*new BinaryHeap(g.NumberOfEdges(); Iterator& p=g.Edges();while(!p.IsDone() WeightedEdge& edge=dynamic_cast(*p); int& weight=fynamic_cast(edge.Weight(); queue.Enqueue(*new Assoc(weight,edge); +p;delete &p;Partition& partition=*new PartitionAsForest(n);while(!queue.IsEmpty()&partition.Count()1)Assoc& assoc=dynamic_cast(queue.DequeuMin();Edge& edge=dynamic_cast(assoc.Value();Vertex:Number const v0=edge.V0();Vertex:Number const v1=edge.V1();Set& s=partition.Find(Set:Element(v0);Set& t=partition.Find(Set:Element(v1);if(s!=t) partition.Join(s,t); result.AddEdge(*new Edge(resultv0，resultv1); delete &assoc;delete &partition;delete &queue;return delete;PRIM算法Prinm算法原理假设G=（V,E）是一个具有n个顶点的边带权无向图，T=（U,TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定去）将它并入U中，此时U=：然后只要U是V的真子集（即权值最小）边，假定为（）和顶点分别并入T的边集TE和顶点集U；如此进行下去，每次往生成树里并入一个顶点和一条边，直到（n-1）次后就把所有的n个顶点都并入到生成树T的顶点集中，此时U=V,TE中含有（n-1）条边，T就是最后得到的最小生成树。Prim算法的关键之处是：每次如何从生成树T中道T外的所有边中，找出一条最短边。例如，在第k次前，生成树T中已有K个顶点和(k-1)条边，此时T中道T外的所有边数为(k(n-k)，当然它包括两顶点间没有直接边相连，其权值被看做“无穷大”的边在内，从如此多的边中查找最短边，其时间复杂性为O(k（k-n）)，显然是很费时的。是否有一种好的方法能够降低查找最短边的时间复杂性呢？回答是肯定的，它能够使查找最短边的时间复杂性降低到O(k(n-k).方法是：假定在进行第K次前已经保留着从T中道T外每一顶点（共（n-k）个顶点）的各一条最短边，进行第k次时，首先从这(n-k)条最短边中，找出一条最最短的边（它就是从T中道T外的所有边中的最短边），假设为（），此步需进行（n-k）次比较；然后把边（）和顶点分别并入T中的边集TE合顶点集U中，此时T外只有（n-（k+1）个顶点，对于其中的每个顶点，若（）边上的权值小于已保留的从原T中的最短边不变，这样，就把第k次后从T中到T外每一顶点的各一条最短边都保留下来了，为进行第（k+1）次运算做好的准备，此步需进行（n-k-1）次比较。所以，利用此方法求第k次的最短边共需比较2（n-k）-1次，即时间复杂性为O（n-k）。 例如，对于图11.6它的邻接矩阵如图11.7所示。假定从出发利用Prim算法构造最小生成树T,在其过程中，每次向T中并入一个顶点和一条边后，顶点集U、边集TE（每条边后面为该边的权）以及从T中到T外每个顶点的各一条最短边所构成的集合（假定用LW表示）的状态如下：初始态 U= TE= LW=， 第一次U= TE= LW=，第二次U= TE= LW= 第三次U= TE= LW= 第四次U= ,TE= LW= 第五次U= ,，TE= ,6LW= 第六次U= ,，,TE=,6，LW= 图11.6图11.8 Prim算法实现函数PrimAlogrithm有两个参数，第一个参数是一个指向无向图实例的const型引用，这个无向图是一个边带权的图，且权是int类型。第二个参数也是const类型引用，是一个指向起始点（顶点）引用。函数返回一棵无向图描述的最小支撑树，即一个Graph实例的引用。Graph& PrimAlgorithm(Graph const& g, Verter const& s)unsigned int const n=g.NumberOfVertices();Arraytable(n);PriorityQueue& queue=*new BinaryHeap(g.NumberOfEdges();tables.distance=0;queue.Enqueue(*new Assoc(0,const_cast(s);while(!queue.IsEmpty() Assoc& assoc=dynamic_cast(queue.DequeueMin(); Vertex& v0=dynamic_cast(assoc.Value(); if(!tablev0.known) tablev0,known=true; Iterator& p=g.EmanatingEdges(v0); while(!p.IsDone() WeightedEdge& edge=dynamic_cast(*p); Vertex& v1=edge.Mate(v0); int& weight=dynamic_cast(edge.Weight(); int const d=weight; if(!tablev1.known&tablev1.distanced) tablev1.distance=d; tablev1.predecessor=v0; queue.Enqueue(*new Assoc(d,v1); +p;delete &p;delete &assoc;delete &queue;Graph& result=*new GraphAsLists(n);for(Vertex:Number v=0; vn; +v) result.AddVertex(*new Vertex(v);for(Vertex:Number v=0; vn; +v) if(v!=s) result.AddEdge(*new Edge(resultv,resulttablev.predecessor);return result;Floyd算法原理Floyd算法是解决关于密集图的每对顶点间最短路径问题的动态程序设计方法，它有效地利用了邻接矩阵。Floyd算法从图的邻接矩阵（对角线上的元素定义为0）开始，按照顶点的次序，分别以每个顶点（1kn）作为新考虑的中间点，在第k-1次运算（为图的邻接矩阵GA）的基