自然科学版 英文版
自然科学版 英文版
自然科学版 英文版

您目前所在的位置:首页 - 期刊简介 - 详细页面

中南大学学报(自然科学版)

Journal of Central South University

第32卷    第5期    总第141期    2001年10月

[PDF全文下载]    [Flash在线阅读]

    

文章编号:1005-9792(2001)05-0528-04
多可加性条件下的端点到端点QoS路由算法
肖建华,王建新,陈松乔,陈建二

(中南大学信息科学与工程学院,湖南长沙 410083)

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

 

关键字: QoS;时延;丢失率; NP完全问题

The end-to-end QoS routing algorithm under multi additional-conditions
XIAO Jian-hua,WANG Jian-xin,CHEN Song-qiao,CHEN Jian-er

College of Information Science and Engineering, Central South University, Changsha 410083, China

Abstract:One of critical functional components ofQoS deployment is the QoS-based routing. In essence, the QoS-basedis an end-to-end path finding problem with some constraints in nodes and in edges. This problem is NP-completed problem. In this paper, the authors addressed the properties of additional conditions in QoS model, built a generalization mathematical model for QoS undermulti additional-conditions, proposed a newheuristic algorithmforthismodel. The al
gorithm is called the M-WFS, which is the cutting-branch WFS by using the result of theorem 1. The new algorithm′s time-complexity is o(lgm+n×(1+d1+d2+…+dρ0))and it is better than the other algorithm for this problem.

 

Key words: QoS; delay; loss rate; NP-completed problem

中南大学学报(自然科学版)
  ISSN 1672-7207
CN 43-1426/N
ZDXZAC
中南大学学报(英文版)
  ISSN 2095-2899
CN 43-1516/TB
JCSTFT
版权所有:《中南大学学报(自然科学版、英文版)》编辑部
地 址:湖南省长沙市中南大学 邮编: 410083
电 话: 0731-88879765 传真: 0731-88877727
电子邮箱:zngdxb@csu.edu.cn 湘ICP备09001153号