【摘 要】
：
单源最短路径问题作为图论的一个基本问题,广泛运用于现实世界中.在这些应用领域,最短路径树需要存储并在拓扑变化后更新.静态最短路径算法在拓扑变化后无法利用已有的SPT信
论文部分内容阅读
单源最短路径问题作为图论的一个基本问题,广泛运用于现实世界中.在这些应用领域,最短路径树需要存储并在拓扑变化后更新.静态最短路径算法在拓扑变化后无法利用已有的SPT信息,必须重新计算一颗SPT.然而,动态最短路径算法则利用已有的SPT信息,增量的更新旧的SPT而实现SPT的计算.由此,提高了SPT的计算效率.动态最短路径算法在路由协议领域称之为ISPF(Incremental Shorest Path First). ISPF只需要更新最短路径发生变化的节点.不发生变化的节点不需要在SPT上更新.从而,提高路由计算效率并降低网络路由的震荡.同时,动态最短路径算法的实现有利于单播路由协议的PRC(Partial Route Compute). PRC对提高路由协议的运行效率具有重要意义.动态最短路径算法的研究已比较成熟.但是,大部分算法都是点更新算法,处理多链路权值减小的XiaoBin算法是分支更新算法,处理多链路权值增大的动态最短路径算法的研究却很少.另一方面,已有的动态最短路径算法均没有实现负载均衡.然而,这是路由协议中PRC技术必须具备的功能.基于这些问题,本文对现有动态最短路径算法进行深入分析,主要从以下四方面进行了研究.1.提出了一多链路权值增大的分支动态最短路径算法.仿真结果显示该算法相比XiaoBin点更新算法具有更好的时间效率以及更少的冗余计算.2.为了实现PRC,本文提出了一种基于动态最短路径算法的下一跳增量计算算法.3.为了将动态最短路径算法应用到路由协议中,本文提出了一种动态最短路径算法负载均衡扩展的方法,并由此对两个半动态最短路径算法进行了扩展.4.结合扩展的动态最短路径算法以及下一跳增量计算算法,提出了一种PRC的实现方案.
其他文献
请下载后查看，本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
研究人员建立了一个求解(VI)的一个外梯度统一框架算法.证明了上述两算法算法是这种框架算法的特殊情形.并而从理论上对两种算法进行了比较.在映射F伪单调时,研究人员证明了
该文引入几类向量F-互补问题,并在一定条件下给出了向量F-互补问题,广义向量变分不等式以及可行集的最小元问题之间的相互关系.
通过星运算研究整环是当前整环研究中的一个非常活跃的方向.在具体应用中,常用的星运算是是t-运算和v-运算,这两种运算对于整环上理想的刻画作用很大,已得到广泛的探讨.而新
Nielsen在研究曲面间映射的不动点的时候,引进了自由度的概念.自由度在很大程度上反映了流形本身的性质.王诗宬证明了闭曲面自由度的上界,并且证明了某类Orbifold的复迭空间
超饱和设计是统计试验设计领域中的一个新的研究课题.在这方面,早期的研究工作集中在二水平设计上.最近两年开始有一些多水平超饱和设计的研究结果发表.该论文关于多水平超饱
该论文研究了动力系统中的连结奇点轨线的存在性.在第一章,研究人员简单地介绍了Conley不变集理论的一些基本概念和结果.在第二章,研究人员主要考虑了两个物种的生态系统.构
该文采用把经典的SiegelTheta级数看作在正定二次空间(quadraticspace)的一个整格M上求和的观点,对于一般的赋有非退化不定整二次型的整格M,定义了推广的Theta级数θM(Z;u,P)
在初中数学教育中,作业的重要性不言而喻,它不仅可以帮助学生巩固课堂上所学到的知识,还可以培养学生的实践能力以及创新能力.而目前初中数学作业的设计形式单一,并且应用意
该文结合运用Liapunov函数,Liapunov泛函,指数二分法,渐近概周期函数,不动点定理等方法,研究了概周期常微分方程和概周期泛函数微分方程概周期解的存在性、唯一性、稳定性等