首页 | 本学科首页   官方微博 | 高级检索  
     检索      

多约束服务质量路由中的路径压缩算法
引用本文:赵有健,张铁蕾,崔勇.多约束服务质量路由中的路径压缩算法[J].计算机学报,2007,30(12):2090-2100.
作者姓名:赵有健  张铁蕾  崔勇
作者单位:清华大学计算机科学与技术系,北京,100084
基金项目:国家自然科学基金 , 国家重点基础研究发展计划(973计划)
摘    要:多约束服务质量路由是一种能够支持灵活的服务质量控制的有效方案.然而在多约束的环境下,从一个源节点到一个目的节点可能存在多条路径,因而必须相应地增大路由表容量.由于当前路由表的规模已相当庞大,尤其是在高速核心网中,因此,为了在QoS路由表中存储更少的路径信息,需要首先进行路径压缩.文章以解决最优路径压缩问题(OPR)为目标,力图在尽量减小路由表存储规模的同时使路由成功率最大化.为了实现这个目标,文中提出了两个基于贡献区域的算法:增量贡献算法和改进的增量贡献算法.这两个算法从一个大的多约束路径集合中依次计算出具有最大贡献区域的积的路径,最后得到一个小的结果路径集合.大量模拟实验表明,这两个算法能够以较低的运算复杂度获得令人满意的路由成功率.

关 键 词:服务质量路由  覆盖网络  多约束  路径选择  预计算  多约束  服务  质量路由  路径集合  压缩算法  Routing  Reduction  运算复杂度  模拟实验  结果  计算  改进  增量  区域  大化  成功率  目标  问题  最优  路径压缩
修稿时间:2006年1月10日

Path Reduction for Multi-Constrained Quality-of-Service Routing
ZHAO You-Jian,ZHANG Tie-Lei,CUI Yong.Path Reduction for Multi-Constrained Quality-of-Service Routing[J].Chinese Journal of Computers,2007,30(12):2090-2100.
Authors:ZHAO You-Jian  ZHANG Tie-Lei  CUI Yong
Abstract:Multi-constrained quality-of-service routing (QoSR) is regarded as a promising solution to support flexible QoS-oriented services. However, there may exist multiple paths from a source node to a destination node in the context of multi-constrained routing and thus the routing table has to be enlarged accordingly. Since the current routing table size is quite large, especially in the high-speed core networks, path reduction needs to be performed in order to store less paths into the QoS routing table. In this paper the authors try to solve the Optimal Path Reduction Problem (OPR) which aims to reduce the storage space of the QoS routing table as much as possible and at the same time to maximize routing success ratio. To achieve this goal, the authors propose two contribution region based algorithms: the incremental contribution algorithm and its improved version. These two algorithms figure out the path with maximum capacity of contribution region one by one from a large set of multi-constrained paths and finally obtain a small set of selected paths. Extensive simulations show that these two algorithms achieve satisfying performance in terms of the routing success ratio with low time complexity.
Keywords:QoS routing  overlay  multiple constraints  path selection  precomputation
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号