多可加性条件下的端点到端点QoS路由算法

摘要：

基于QoS的路由是QoS中最关键的功能组件之一.从本质上看,QoS路由就是端点到端点的带结点条件和边条件限制的最短路径问题,这种问题是NP完全的.作者研究了可加性条件限制的QoS路由模型和路由算法,分析了可加性条件的性质并得到了其对路由长度限制的定理,为多个可加性条件的QoS路由问题建立了一个一般性的数学模型;最后根据此模型,提出了一种新的启发式求解算法.在算法中,采用限制条件的可加性进行搜索剪枝,从而使新算法在实际应用中更有效;该算法的时间复杂度为o(1gm+n×(1+d1+d2+…+d00)).应用结果表明,由于采用搜索剪枝,该算法在实际应用中具有时间复杂度减小、运行速度加快等特点.

关键词：QoS、时延、丢失率、NP完全问题

所属期刊栏目：32

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金;长江学者奖励计划

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：528-531