基于四叉堆优先级队列的OSPF算法.docVIP

基于四叉堆优先级队列的OSPF算法 梁志华，李东生，杜莉娜 (太原理工大学信息工程学院．山西太原030()24) 摘要：通过比较已有的D钉kstra算法和基于四又堆优先级队列的D“kstra算法的时间复杂度得出，后者的执行效率高于前者；井在此基础上提出了基于四叉堆优先级队列的()sPF算法，以提高osPF的效率。 关键词：路由选择；oSPF；四叉堆 随着Pc主频的快速发展和上网人数的大幅增加，网络速度已成为人们关注的焦点，也是影响网络继续普及的关键。因此如何有效提高网络速度已成为当今网络技术的主要课题之一。 路由选择协议是TCP／IP协议族中重要的成员之一，选路过程实现的好坏会影响整个Internet网络的效率。而路由选择算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果。因此选择路由算法需综合考虑以下几个设计目标：最优化，简洁性，坚固性，快速收敛，灵活性Internet是AS(Autonomous System，自治系统)，每个As由不同的机构运营管理，在其内部使用自己的路由选择协议。按实现范围的不同，路由选择协议aJ分为内部网关协议和外部网关协议。仅就内部网戈协议而言，现正使用的路由协议有以下儿种：R1P 1(Routing Informatlon ProtocoI，选路信息系统)；RIP 2；IGRP(Interior Gateway Routlng Protoc01，内部网关路南选择协议)；EIGRP(Extended Gateway Protoc01．扩充的内部网关路由选择协议)；Is Is(Intermediate system Intermedlate system，中间系统)；OsPF[“．其中前4种路由协议采用的是距离向量算法，Is—Is和osPF采用的是链路状态算法。对于小型网络，距离向量算法尚能胜任；而在面对大型网络时，不但其固有的无穷计数问题变得更为糟糕，所占用的带宽也迅速增长，以至于网络无法承受。对于大型网络，采用链路状态算法的Is—Is和osPF较为有效，并得到了广泛的应用。 IS一1S和OsPF在质量和性能上的差别不大，但OSPF更适用于IP，较I孓IS更具有活力。IETF始终致力于osPF的改进工作，其修改节奏比I孓Is快得多。因此OSPF正在成为最为广泛的一种路由选择协议。 oSPF属动态的路由协议，它可以迅速地检测AS内的拓扑变化，经过一个比较短的收敛期后，重新计算出无环路由。每个路由器维护一个相同的链路状态数据库，保存整个As的拓扑结构。一旦路由器有了完整的链路状态数据库，该路由器就可以以自己为根，构造最短路径树，然后再根据最短路径树构造路由表口]。构造最短路径树采用Dijkstra算法，它的时间复杂度为O(n2)H]。但本文提出的基于四叉堆优先级队列的OsPF算法的时间复杂度为协议的时间复杂度大大减少。 1 Dikstra算法 DIjkstra算法由著名数学家E．w．Dijkstra于1959年提出，是按路径长度递增的次序产生的单源最短路径算法，计算结果为一棵以起点为根的最短路径树。下面为基于邻接矩阵的DikStra算法的语言描述。 设D[i]为砜到V．的累计权值，s为最短路径节点的集合．arcs[i][力为弧v．，v，上的权值。 D[V。]为。。，s为空。 1)找到从V。出发到其余各节点的最短路径长度的初值，记为D[。](若可达，则D[z]为v。到此节点弧上的权值；若不可达，则D[z]为无穷)。 2)找出最小权值。设此最小值对应的终止节点为U，则D[j]一mtn{D[i]}V．为图中的节点}且S=S U{V，}． 3)若从y，出发到其余任一节点(设为V·)弧上的权值与DD]之和小于D[^]，即D[力+arcs[力阻]D[女]，则修改D[女]的值为；D[^]一D[力+arcs[力队]． 4)重复2)、3)共一1次，即可求得从Vo出发到其余各节点的最短路径。 此算法的第一个循环的时间复杂度为O(n)．第二个循环共进行n一1次，每次执行的时间是O(n)，所以第二个循环的时闻复杂度是o(“。)，故此算法的时问复杂度是O(舻)．我们可以看出，造成此算法效率不高的主要原因在于算法中的二重循环。当节点总数n很大时，此二重循环将耗费大量的计算时间。欲降低此算法的时间复杂度，关键在于对第二个循环进行改造。 2 基于四叉堆优先级队列的Dijkstra算法 优先级队列是一种用来维护由～组元素构成的集合的数据结构。实现优先级趴列的方法较多，但K叉堆是一种很优秀的实现方法。 K叉堆结构是一种数组对象，可以被视为一棵完全K叉树。堆结构必须满足以下|生质：对除了根节点以外的每个节点z，有A[parent(i)]≤A[i]或A[Parent(z)]≥A[z]，即某个节点的值不小于(或不大于)其父