多约束服务质量路由中的路径压缩算法

多约束服务质量路由是一种能够支持灵活的服务质量控制的有效方案.然而在多约束的环境下,从一个源节点到一个目的节点可能存在多条路径,因而必须相应地增大路由表容量.由于当前路由表的规模已相当庞大,尤其是在高速核心网中,因此,为了在QoS路由表中存储更少的路径信息,需要首先进行路径压缩.文章以解决最优路径压缩问题(OPR)为目标,力图在尽量减小路由表存储规模的同时使路由成功率最大化.为了实现这个目标,文中提出了两个基于贡献区域的算法:增量贡献算法和改进的增量贡献算法.这两个算法从一个大的多约束路径集合中依次计算出具有最大贡献区域的积的路径,最后得到一个小的结果路径集合.大量模拟实验表明,这两个算法能够以较低的运算复杂度获得令人满意的路由成功率.

Path Reduction for Multi-Constrained Quality-of-Service Routing

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.