摘要
如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1) 满足业务QoS需求;(2) 最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.
It is a challenging problem to provide QoS (quality-of-service) guarantee for the next-generation networks, among which QoSR (QoS routing) is one of the key issues. QoSR seeks to find a feasible path for QoS traffic with two objectives: (1) providing the QoS guarantee for QoS traffic, (2) maximizing the utilization of the whole network. However, some multi-constrained QoSR problems, which are NP-complete, can't be resolved accurately in polynomial time. Based on the weighted graph network model and QoS metrics, the basic concept of QoSR is introduced and the hot issues of the unicast QoSR heuristics are analyzed. QoSR algorithms can be classified into the several classes. After typical algorithms are analyzed, the summary and comparison are given for each of the above classes. The validity of algorithms is dissected in detail. Based on the validity analysis, a summary is given for the QoSR algorithms based on probability models. At last, key issues are pointed out to be further studied in the QoSR field.
出处
《软件学报》
EI
CSCD
北大核心
2002年第11期2065-2075,共11页
Journal of Software
基金
国家自然科学基金资助项目(90104002
69725003)
国家高技术研究发展计划资助项目(2002AA103067
2001AA121013)~~
关键词
互联网络
服务质量
路由算法
NP安全问题
启发式算法
有效性
Algorithms
Classification (of information)
Computational complexity
Heuristic methods
Interconnection networks
Mathematical models
Optimization
