多约束最短链路分离路径精确算法

作     者：熊轲 裘正定 郭宇春 张宏科 秦雅娟 XIONG Ke;QIU Zheng-Ding;GUO Yu-Chun;ZHANG Hong-Ke;QIN Ya-Juan

作者机构：北京交通大学信息科学研究所北京100044 清华大学电子工程系北京100084 北京交通大学电子信息工程学院北京100044 北京交通大学下一代互联网互联设备国家工程实验室北京100044 

基　　金：国家自然科学基金No.60772043 国家重点基础研究发展计划(973)Nos.2007CB307101 2007CB307106 国家高技术研究发展计划(863)No.2007AA01Z202 高等学校学科创新引智计划No.B08002 国家教育部科技创新工程重大项目No.706005 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2010年第21卷第7期

页      码：1744-1757页

摘      要：在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.

主 题 词：服务质量路由 网络可靠性 链路分离路径 多约束路由 最优解 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 08[工学] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3724/sp.j.1001.2010.3589

馆 藏 号：203256501...