【作者】 杜德超；

【导师】 姚庆栋；

【作者基本信息】 浙江大学 ， 通信与信息系统， 2003， 博士

【摘要】 服务质量(QoS)是Internet发展中最重要的研究领域之一。QoS的研究内容十分广泛，包括信令协议、框架模型、路由算法、多播技术等多个方面。方案涉及QoS上的业务量分类、调度算法、链路技术、路由协议、信令方法、计费和授权方式等多种机制。 本文着重研究其中与流量传输相关QoS组件：CQS(Classifying, Queueing, and Scheduling)。包括流量控制技术，流量排队、调度和分组分类。它们是网络最终实现端到端服务质量的根本保证。本文主要研究其中的流量排队、调度和流量分类，对流量控制技术只作简单介绍。 本文主要研究工作如下： 第一章首先给出了QoS的定义，描述了当前Internet上体系结构、机制和协议等的发展情况。并介绍了三种不同的QoS框架：InterServ，DiffServ和MPLS，并比较它们各自的优缺点。最后，给出了我们所研究的内容在QoS中的作用与地位。 第二章主要是介绍几种流量控制技术，它们是CQS研究中不可缺少的组成部分。首先给出了接纳控制的基本组成。随后对几种主要的接纳控制算法进行综述，主要有：1)基于测量的接纳控制(MBAC)；2)端点接纳控制(EAC)；3)基于策略的接纳控制；4)子网带宽管理相关的接纳控制；对关键技术及要求进行了详细分析，并比较了已有的接纳控制算法的性能。最后，我们讨论了流量参数控制技术：管制与成形。 第三章详细地介绍并比较了三类缓冲结构(输入、输出及联合输入与输出)及对应的调度算法。给出了各类算法的性能要求。指出基于输出缓冲的调度算法具有最佳的QoS保证。基于输入的调度算法具有很好的可扩展性。我们重点讨论了与输入和输出都相关的流量排队与调度算法。在综合已有算法的基础上，提出了基于RPS基础上的流量调度算法——SMFQ算法。它不但具有与RSP类调度算法一样的最佳时延特性，而且算法非常简单。与目前性能较好MD-SCFQ算法相比，虽然SMFQ算法公平性稍差，但算法的计算复杂性大大简化，更适合在高速网络中应用，因此它是当前RPS类流量调度算法中综合性能最佳的算法。在给出SMFQ算法的同时，重新给出了这类算法的公平性能的分析方法，并对已有的一些不正确结果进行了修正。当将SMFQ与成形算法相结合时，可达到具有理想的worst-case公平性能。并且，所得到的成形SMFQ调度器是属于完全工作型(work-conserving)。由于它同时具有理想的公平性、worst-case公平指数、及简单的算法复杂性，所以更适合在高速网络中应用。在推导成形SMFQ算法的过程中，我们还修正了成形RPS类算法的worst-case指数，给出了有关结论的证明过程和结果。 第四章给出分组分类算法的特点与性能要求，分析了已有的比较常见的各种分组分类算法。在此基础上，提出了基于位矢量的多维分组分类算法。并与已有算法进行了性能比较。我们的分析表明，该算法是到目前为止综合性能最佳的算法。它支持多维分组分类，扩展性很强，算法简单，不但方便地可由软件实现，也能容易地由硬件实现。更多还原

【Abstract】 The quality of service (QoS) is one of the most important areas of Internet development. As the Internet originally developed for data communications is now used more and more for real-time applications, there is a need for better service than the "best effort". The research topics about QoS range from routing, multicast, implement models to QoS signaling, protocol, and so on.We only study basic components:CQS, which is rated to QoS traffic transmission: admission controlling, traffic scheduling, queueing, and flow classifying. We focus on the traffic scheduling and flow classifying in this paper. The major work of the dissertation is outlined as follow:In Chapter 1, we first present the concept quality of service, describe the current evolution of QoS architecture, mechanisms, and protocols in the Internet. A short review of the proposed standard approaches to QoS(e.g. differentiated services, integrated services, and label switching technologies) is given. Finally we introduce our dedicated research topics in this area.In Chapter 2, we look at the problem of traffic control and the research in this area. We first explain the basic components of admission control. We then talk about some well known admission control schemes: l)Measurement-based Admission Control(MBAC); 2)Endpoint Admission Control(EAC); 3)Policy-based Admission Control(PAC); 4)Subnet Bandwidth Manager(SBM). An analysis of their performances and a comparison of the results follow. Finally, we discuss traffic parameter control: policing and shaping.In Chapter 3, we discuss the queueing for input-queued, output-queued, and combined input/output-queued switch. We mainly study scheduling algorithms based on input-queued and output-queued and show that output queueing can afford the best QoS guarantee but has a poor expansibility; The input queueing, through has a high scalability, lacks of the necessary QoS features. In this chapter, we devote to the packet scheduling algorithms which are suitable to both queueing. Based on rate-proportional server(RPS), we present an efficient and simple fair queueing algorithm, called SMFQ(Start-Potential Mean Fair Queueing) which has O(l) complexity for the virtual time computation while has fairness properties batter than SPFQ. The same as SPFQ, when combined with a shaping mechanism(or select packet for transmission with SEFF policy)to achieve an ideal worst-case fairness index, SMFQ satisfies all the properties necessary to make the resulting system a work-conserving scheduler. In this chapter, we discuss that it is not true that PFQ algorithm when approximates a fluid rate-proportional server with SEFF policy can achieve the same worst-case fairness as that of WF2Q. We give a new value of worst-case fairness index for it and show that is inferior to the index of WF2Q. Some related statements and conclusions presented before are required for revision and the new results for them are given in this chapter.In Chapter 4, we introduce and analyze packet classification algorithm. Routers must perform packet classification at high speeds to support advanced functions such as firewalls and QoS routing. While several efficient solutions are known for the one-dimensional IP lookup problem, the mult-dimensional packet classification has proved to be far more difficult. Existing filter schemes with fast lookup time do not scale to large filter database. Based on tuple space search, apacket classification algorithm called bitmap vector of tuple space for multi-dimensional conflict-free filters is presented in this chapter. The result of the performance analysis in two-dimension and multi-dimension shows that the scheme provides better worst case bounds about time and space complexity than what have existed, so the algorithm is more scalable and faster. The novel approach can be easily implemented both from software and hardware which made this algorithm more practical to applications.更多还原