主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
谭晶,罗军舟,李伟.一种适合低连接度拓扑的集中式保护路由机制.软件学报,2013,24(3):575-592
一种适合低连接度拓扑的集中式保护路由机制
Centralized Intra-Domain Protection Routing Mechanism for Low-Connectivity Topology
投稿时间:2011-11-30  修订日期:2012-04-09
DOI:10.3724/SP.J.1001.2013.04250
中文关键词:  域内路由  集中式  NP-hard
英文关键词:intra-domain routing  centralized  NP-hard
基金项目:国家重点基础研究发展计划(973)(2010CB328104); 国家自然科学基金(60903161, 60903162, 61003257, 61070158,61070161, 61070210); 国家科技支撑计划(2010BAI88B03, 2011BAK21B02); 高等学校博士点学科专项科研基金(20110092130002);江苏省自然科学基金(BK2008030); 江苏省网络与信息安全重点实验室资助项目(BM2003201); 教育部计算机网络与信息集成重点实验室(东南大学)资助项目(93K-9)
作者单位E-mail
谭晶 东南大学 计算机科学与工程学院,江苏 南京 210096 tanjing@seu.edu.cn 
罗军舟 东南大学 计算机科学与工程学院,江苏 南京 210096  
李伟 东南大学 计算机科学与工程学院,江苏 南京 210096  
摘要点击次数: 2310
全文下载次数: 2458
中文摘要:
      在集中式路由中,由路由控制平台统一计算路由表进行分发,路由器不再具备决策能力,需要预先构建一种具备保护功能的路由机制,使得路由器的下游路径失效后都有立即可用的备份路径,确保报文的最小损失,已有的集中式保护路由机制在低连接度拓扑上保护效果不佳.为了解决该问题,提出了一种适合低连接度拓扑的集中式域内保护路由机制,允许失效处的相邻节点在没有可用路径时将报文返回至其上游节点,由有可用备份路径的上游节点通过备份路径发送,确保单个节点或连接失效后报文的最小损失.证明了为给定拓扑构建最优保护路由的问题是一个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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利