资源描述：
《互联网络服务质量路由算法研究综》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1000-9825/2002/13(11)2065-11©2002JournalofSoftware软件学报Vol.13,No.11互联网络服务质量路由算法研究综述Ã崔勇,吴建平,徐恪,徐明伟(清华大学计算机科学与技术系,北京100084)E-mail:cy@csnet1.cs.tsinghua.edu.cnhttp://netlab.cs.tsinghua.edu.cn/~cuiy摘要:如何提供不同的服务质量(qualityofservice,简称QoS)是互联网络面临的一个重要问题,而服务质量路由(quality-of-servicerouting,简称QoSR)则是其中的核
2、心技术和热点问题.QoSR的主要作用是为QoS业务请求寻找可行路径,这体现了QoSR的两个目标:(1)满足业务QoS需求;(2)最大限度地提高网络利用率.由于QoSR是NP完全问题,研究者们设计了很多启发式算法进行了广泛深入的研究.在有权图和QoS度量的基础上介绍了QoSR的基本概念,详细分析了面向单播应用的QoSR算法中的热点问题,并按照所求解的问题类型和求解方法,将这些算法分成以下几类:多项式非启发类、伪多项式非启发类、探测类、限定QoS度量类、路径子空间搜索类、QoS度量相关类、花费函数类和概率求解类.在分析每类中典型算法的基础上,总结和对比了各类的特点,进而详细剖析了算法
3、的有效性,并基于此总结了基于概率模型求解QoSR问题的方法.最后指出了该领域中需要进一步研究的热点问题.关键词:服务质量路由;NP完全问题;启发式算法;有效性中图法分类号:TP393文献标识码:A当前Internet只提供尽力发送(best-effort)服务,网络层不区分用户业务的种类,而将网络资源公平地提供给各类业务,在分组丢失、延迟等方面公平地对待各类业务.这种尽力发送的机制使网络层无法保证传输的参数,然而丢失率、带宽、端到端延迟、延迟抖动等对于应用业务往往是至关重要的.例如,文件传输业务要求分组的丢失率尽可能低,而传输延迟不是关键因素;实时多媒体业务则更看重延迟和抖动.这
4、就要求网络能够区别对待各种业务,并对它们提供不同的服务质量.由于IP是无连接的协议,不要求像ATM网络那样在数据传输前从源到目标节点建立连接.这种尽力发送的体系结构是无连接、与状态无关的,它既不能支持资源预留,也不能预测传输参数,甚至还可能产生多媒体实时业务不希望的乱序等.由此,面向服务质量的网络体系结构应运而生.1服务质量路由概述定义1(服务质量).服务质量(qualityofservice,简称QoS)是网络在传输业务流时,业务流对网络服务的需[1]求的集合,其中业务流是指与特定QoS相关的从源到目的地的分组流.也就是说,QoS是应用业务对网络传输服务提出的一组可度量的要求,
5、主要包括带宽、端到端延迟、分组丢失率、抖动、花费等.网络在传输相应的数据业务时,必须满足这组要求.QoS需求可以通过一个约束集来描[2]述,包括链路约束、路径约束和树约束.链路约束定义了从源到目的地的每一条链路的约束,如带宽约束;路径Ã收稿日期:2001-12-31;修改日期:2002-04-10基金项目:国家自然科学基金资助项目(90104002;69725003);国家高技术研究发展计划资助项目(2002AA103067;2001AA121013)作者简介:崔勇(1976－),男,新疆乌鲁木齐人,博士生,主要研究领域为计算机网络体系结构,协议的仿真和测试,多目标优化的路由算法
6、及其评价;吴建平(1953－),男,山西太原人,博士,教授,博士生导师,主要研究领域为计算机网络体系结构,计算机网络协议测试,形式化技术;徐恪(1974－),男,江苏洪泽人,博士,讲师,主要研究领域为计算机网络体系结构,计算机系统性能评价;徐明伟(1971－),男,辽宁朝阳人,博士,副教授,主要研究领域为计算机网络体系结构,计算机网络性能评价,协议测试.2066JournalofSoftware软件学报2002,13(11)约束定义了从源到目的地的一条路径上端到端QoS需求,如延迟;树约束定义了对组播中整个组播树的约束,例如对组播树延迟的约束是对树中从源到所有目的地的路径中最大延
7、迟的约束.定义2(可行路径(可行树)).可行路径(可行树)是网络中从源到(所有)目标节点的一条路径(组播树),并且该路径(树)具有足够的尚未分配的资源,能够满足特定的QoS需求.定义3(服务质量路由(QoSR)).服务质量路由(QoSrouting)是一种基于数据流QoS请求和网络可用资源进[1]行路由的机制.或者,QoSR是一种动态路由协议,并且在其路径选择标准里可能包含可用带宽、链路和端到端[3]路径利用率、资源消费量、延迟、跳数以及抖动等QoS参数.当前Internet的主
