互联网络服务质量路由算法研究综述

被引：68

作者：

崔勇

吴建平

徐恪

徐明伟

机构：

[1] 清华大学计算机科学与技术系

来源：

软件学报 | 2002年 / 11期

关键词：

服务质量路由; NP完全问题; 启发式算法; 有效性;

D O I：

10.13328/j.cnki.jos.2002.11.002

中图分类号：

TP393.03 [];

学科分类号：

摘要：

如何提供不同的服务质量(quality of service,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-service routing,简称QoSR)则是其中的核心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1) 满足业务QoS需求;(2) 最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.

引用

收藏

页码：2065 / 2075

页数：11

相关论文

共 14 条

[1] Difficulties in simulating the Internet
Floyd, S
Paxson, V
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 2001, 9 (04) : 392 - 403
[2] Evaluating the impact of stale link state on quality-of-service routing
Shaikh, A
Rexford, J
Shin, KG
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 2001, 9 (02) : 162 - 176
[3] A distributed algorithm for delay-constrained unicast routing
Reeves, DS
Salama, HF
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 2000, 8 (02) : 239 - 250
[4] A simple approximation to minimum-delay routing
Vutukury, S
Garcia-Luna-Aceves, JJ
[J]. ACM SIGCOMM'99 CONFERENCE: APPLICATIONS, TECHNOLOGIES, ARCHITECTURES, AND PROTOCOLS FOR COMPUTER COMMUNICATIONS, 1999, 29 (04): : 227 - 238
[5] QoS routing in networks with inaccurate information[J] . Roche A. Guérin,Ariel Orda.IEEE/ACM Transactions on Networking (TON) . 1999 (3)
[6] Routing with end-to-end QoS guarantees in broadband networks
Orda, A
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 1999, 7 (03) : 365 - 374
[7] QoS routing in networks with uncertain parameters
Lorenz, DH
Orda, A
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 1998, 6 (06) : 768 - 778
[8] QoS based routing algorithm in Integrated Services Packet Networks
Pornavalai, C
Chakraborty, G
Shiratori, N
[J]. JOURNAL OF HIGH SPEED NETWORKS, 1998, 7 (02) : 99 - 112
[9] A quantitative comparison of graph-based models for Internet topology
Zegura, EW
Calvert, KL
Donahoo, MJ
[J]. IEEE-ACM TRANSACTIONS ON NETWORKING, 1997, 5 (06) : 770 - 783
[10] Strategic directions in networks and telecommunications
Clark, D
Pasquale, J
[J]. ACM COMPUTING SURVEYS, 1996, 28 (04) : 679 - 690