一种适合低连接度拓扑的集中式保护路由机制  

Centralized Intra-Domain Protection Routing Mechanism for Low-Connectivity Topology

作　　者：谭晶[1] 罗军舟[1] 李伟[1] 

机构地区：[1]东南大学计算机科学与工程学院,江苏南京210096

出　　处：《软件学报》2013年第3期575-592,共18页Journal of Software

基　　金：国家重点基础研究发展计划(973)(2010CB328104);国家自然科学基金(60903161;60903162;61003257;61070158;61070161;61070210);国家科技支撑计划(2010BAI88B03;2011BAK21B02);高等学校博士点学科专项科研基金(20110092130002);江苏省自然科学基金(BK2008030);江苏省网络与信息安全重点实验室资助项目(BM2003201);教育部计算机网络与信息集成重点实验室(东南大学)资助项目(93K-9)

摘　　要：在集中式路由中,由路由控制平台统一计算路由表进行分发,路由器不再具备决策能力,需要预先构建一种具备保护功能的路由机制,使得路由器的下游路径失效后都有立即可用的备份路径,确保报文的最小损失,已有的集中式保护路由机制在低连接度拓扑上保护效果不佳.为了解决该问题,提出了一种适合低连接度拓扑的集中式域内保护路由机制,允许失效处的相邻节点在没有可用路径时将报文返回至其上游节点,由有可用备份路径的上游节点通过备份路径发送,确保单个节点或连接失效后报文的最小损失.证明了为给定拓扑构建最优保护路由的问题是一个NP-hard问题,并且提出了解决该问题的三阶段启发式算法.在各种类型的拓扑中验证了启发式算法的性能.实验结果表明,该方法优于已有保护路由方案.In centralized routing, routing tables are computed by a control platform, but routers do not make decisions anymore. It is necessary to build backup paths for each router so that packets can be forwarded after failure. Existing protecting routing schemes cannot work well in low-connectivity topology. To solve this problem, a method for building centralized protection routing is proposed in this paper. In this method~ packets can be pushed back to the upstream nodes and sent by the backup paths of upstream nodes if current node has no valid paths after failure. The problem of building optimal protection routing for a given topology is proved to be NP-hard and a heuristic algorithm is proposed. The algorithm is verified in various topologies and the experimental results show that it is better than existing schemes.

关 键 词：域内路由 集中式 NP-HARD 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]