Packet scheduling algorithms for integrated services networks.

摘要

An integrated services network supports applications with diverse Quality of Service (QoS) requirements. Packet scheduling is a fundamental mechanism employed by such a network to meet the QoS requirements of the applications. In this dissertation, we design, analyze, and implement packet scheduling algorithms for integrated services networks.; We first define and analyze a class of Guaranteed Rate (GR) scheduling algorithms. We demonstrate that GR contains most of the known scheduling algorithms that can provide guaranteed QoS. The GR class enables an integrated services network to provide bounded packet delay and loss service to sources with different characteristics in heterogeneous networking environments where each switch may employ a different scheduling algorithm and packet fragmentation/reassembly may occur. The GR framework separates the end-to-end performance guarantees provided by a network from the traffic characteristics of a source and thereby leads to a simple network architecture. We demonstrate that though the GR class does not contain all the algorithms, it does not lead to loss in achievable utilization of a network. Finally, our analysis of GR class demonstrates that scheduling algorithms that are fair and/or achieve separation of rate and delay allocation are desirable.; We then examine the requirements for a suitable packet scheduling algorithm for integrated services network. Our analysis demonstrates that a suitable packet scheduling algorithm should: (1) achieve low average as well as maximum delay for low throughput applications (e.g., interactive audio, telnet, etc.); (2) provide fairness for variable bit rate video; (3) provide fairness over variable rate servers for throughput-intensive flow-controlled data applications; (4) provide QoS guarantees over variable rate servers; (5) support hierarchical link bandwidth allocation to enable a network to provide link-sharing service and facilitate coexistence of multiple services and protocols; and (6) be computationally efficient. To meet these requirements, we first design Start-time Fair Queuing (SFQ) and Fair Airport (FA) algorithms. We then employ them to design Hierarchical SFQ and FA algorithms that achieve hierarchical allocation of link bandwidth. Finally, we present an implementation of Hierarchical SFQ in an IPv6 router. Our analysis and experiments demonstrate that these algorithms meet the requirements and, thus, are suitable scheduling algorithms for integrated services networks.; The key contributions of this dissertation include: (1) a framework for tight analysis of a heterogeneous network; (2) illustration of the need for fairness over variable rate servers and design of algorithms that meet this requirement; (3) design of hierarchical scheduling algorithms that provide quantitative performance guarantees; (4) the single server and end-to-end analysis of SFQ and FA for variable rate Fluctuation Constrained and Exponentially Bounded Fluctuation servers; and (5) an analysis technique for hierarchical scheduling algorithms that yields tight performance guarantees.