基于四叉堆优先级队列的ospf算法

基于四叉堆优先级队列的ospf算法

ID:14122815

大小:628.00 KB

页数:4页

时间:2018-07-26

基于四叉堆优先级队列的ospf算法_第1页
基于四叉堆优先级队列的ospf算法_第2页
基于四叉堆优先级队列的ospf算法_第3页
基于四叉堆优先级队列的ospf算法_第4页
资源描述:

《基于四叉堆优先级队列的ospf算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、基于四叉堆优先级队列的OSPF算法梁志华,李东生,杜莉娜(太原理工大学信息工程学院.山西太原030()24)摘要:通过比较已有的D钉kstra算法和基于四又堆优先级队列的D“kstra算法的时间复杂度得出,后者的执行效率高于前者;井在此基础上提出了基于四叉堆优先级队列的()sPF算法,以提高osPF的效率。关键词:路由选择;oSPF;四叉堆随着Pc主频的快速发展和上网人数的大幅增加,网络速度已成为人们关注的焦点,也是影响网络继续普及的关键。因此如何有效提高网络速度已成为当今网络技术的主要课题之一。路由选择协议是TCP/IP协议族中重要的成员

2、之一,选路过程实现的好坏会影响整个Internet网络的效率。而路由选择算法在路由协议中起着至关重要的作用,采用何种算法往往决定了最终的寻径结果。因此选择路由算法需综合考虑以下几个设计目标:最优化,简洁性,坚固性,快速收敛,灵活性Internet是AS(AutonomousSystem,自治系统),每个As由不同的机构运营管理,在其内部使用自己的路由选择协议。按实现范围的不同,路由选择协议aJ分为内部网关协议和外部网关协议。仅就内部网戈协议而言,现正使用的路由协议有以下儿种:R1P1(RoutingInformatlonProtocoI,选

3、路信息系统);RIP2;IGRP(InteriorGatewayRoutlngProtoc01,内部网关路南选择协议);EIGRP(ExtendedGatewayProtoc01.扩充的内部网关路由选择协议);IsIs(IntermediatesystemIntermedlatesystem,中间系统);OsPF[“.其中前4种路由协议采用的是距离向量算法,Is—Is和osPF采用的是链路状态算法。对于小型网络,距离向量算法尚能胜任;而在面对大型网络时,不但其固有的无穷计数问题变得更为糟糕,所占用的带宽也迅速增长,以至于网络无法承受。对于大

4、型网络,采用链路状态算法的Is—Is和osPF较为有效,并得到了广泛的应用。IS一1S和OsPF在质量和性能上的差别不大,但OSPF更适用于IP,较I孓IS更具有活力。IETF始终致力于osPF的改进工作,其修改节奏比I孓Is快得多。因此OSPF正在成为最为广泛的一种路由选择协议。oSPF属动态的路由协议,它可以迅速地检测AS内的拓扑变化,经过一个比较短的收敛期后,重新计算出无环路由。每个路由器维护一个相同的链路状态数据库,保存整个As的拓扑结构。一旦路由器有了完整的链路状态数据库,该路由器就可以以自己为根,构造最短路径树,然后再根据最短路

5、径树构造路由表口]。构造最短路径树采用Dijkstra算法,它的时间复杂度为O(n2)H]。但本文提出的基于四叉堆优先级队列的OsPF算法的时间复杂度为协议的时间复杂度大大减少。1Dikstra算法DIjkstra算法由著名数学家E.w.Dijkstra于1959年提出,是按路径长度递增的次序产生的单源最短路径算法,计算结果为一棵以起点为根的最短路径树。下面为基于邻接矩阵的DikStra算法的语言描述。设D[i]为砜到V.的累计权值,s为最短路径节点的集合.arcs[i][力为弧上的权值。D[V。]为。。,s为空。1)找到从V

6、。出发到其余各节点的最短路径长度的初值,记为D[。](若可达,则D[z]为v。到此节点弧上的权值;若不可达,则D[z]为无穷)。2)找出最小权值。设此最小值对应的终止节点为U,则D[j]一mtn{D[i]}V.为图中的节点}且S=SU{V,}.3)若从y,出发到其余任一节点(设为V·)弧上的权值与DD]之和小于D[^],即D[力+arcs[力阻]

7、行n一1次,每次执行的时间是O(n),所以第二个循环的时闻复杂度是o(“。),故此算法的时问复杂度是O(舻).我们可以看出,造成此算法效率不高的主要原因在于算法中的二重循环。当节点总数n很大时,此二重循环将耗费大量的计算时间。欲降低此算法的时间复杂度,关键在于对第二个循环进行改造。2基于四叉堆优先级队列的Dijkstra算法优先级队列是一种用来维护由~组元素构成的集合的数据结构。实现优先级趴列的方法较多,但K叉堆是一种很优秀的实现方法。K叉堆结构是一种数组对象,可以被视为一棵完全K叉树。堆结构必须满足以下

8、生质:对除了根节点以外的每个节点z

9、,有A[parent(i)]≤A[i]或A[Parent(z)]≥A[z],即某个节点的值不小于(或不大于)其父节点的值。这样.堆中的最小(或最大)元素就存在根节点中.}=L每一

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。