A QoS architecture for quantitative service differentiation

For the past decade, a lot of Internet research has been devoted to providing different levels of service to applications. Initial proposals for service differentiation provided strong service guarantees, with strict per-flow bounds on delays, loss rates, and throughput, but required high overhead in terms of computational complexity and memory, both of which raise scalability concerns. Recently, the interest has shifted to class-based service architectures with low overhead. However, these newer service architectures only provide weak service guarantees, which do not always address the needs of applications. In this article we introduce a service architecture that supports strong per-class service guarantees, can be implemented with low computational complexity, and only requires maintenance of a little state information. A key mechanism of the proposed service architecture is that service rate allocation to classes is adaptive, and combined with buffer management. Furthermore, instead of using admission control or traffic policing, the proposed architecture exploits explicit congestion notification for the purpose of regulating the traffic entering the network.     

Providing absolute differentiated services for real-time applications in static-priority scheduling networks

In this paper, we propose and analyze a methodology for providing absolute differentiated services for real-time applications. We develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and, hence, is scalable to large systems. We assume the underlying network to use static-priority schedulers. We design and analyze several priority assignment algorithms and investigate their ability to achieve higher utilization bounds. Traditionally, schedulers in differentiated services networks assign priorities on a class-by-class basis, with the same priority for each class on each router. In this paper, we show that relaxing this requirement, that is, allowing different routers to assign different priorities to classes, achieves significantly higher utilization bounds.     

Deterministic delay bounds for VBR video in packet-switchingnetworks: fundamental limits and practical trade-offs

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and trade-offs in providing deterministic performance guarantees to video and use a set of 10 to 30 min. long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, the optimal earliest-deadline-first packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for simple and efficient policing mechanisms, packet scheduling algorithms, and admission control tests     

Dynamic core provisioning for quantitative differentiated services

Efficient network provisioning mechanisms that support service differentiation are essential to the realization of the Differentiated Services (DiffServ) Internet. Building on our prior work on edge provisioning, we propose a set of efficient dynamic node and core provisioning algorithms for interior nodes and core networks, respectively. The node provisioning algorithm prevents transient violations of service level agreements (SLA) by predicting the onset of service level violations based on a multiclass virtual queue measurement technique, and by automatically adjusting the service weights of weighted fair queueing schedulers at core routers. Persistent service level violations are reported to the core provisioning algorithm, which dimensions traffic aggregates at the network ingress edge. The core provisioning algorithm is designed to address the difficult problem of provisioning DiffServ traffic aggregates (i.e., rate-control can only be exerted at the root of any traffic distribution tree) by taking into account fairness issues not only across different traffic aggregates but also within the same aggregate whose packets take different routes through a core IP network. We demonstrate through analysis and simulation that the proposed dynamic provisioning model is superior to static provisioning for DiffServ in providing quantitative delay bounds with differentiated loss across per-aggregate service classes under persistent congestion and device failure conditions when observed in core networks.     

On providing blocking probability and throughput guarantees in a multi‐service environment

As the Internet evolves from a packet network supporting a single best effort service class towards an integrated infrastructure supporting several service classes—some with QoS guarantees—there is a growing interest in the introduction of admission control and in devising bandwidth sharing strategies, which meet the diverse needs of QoS‐assured and elastic services. In this paper we show that the extension of the classical multi‐rate loss model is possible in a way that makes it useful in the performance analysis of a future admission control based Internet that supports traffic with peak rate guarantee as well as elastic traffic. After introducing the model, it is applied for the analysis of a single link, where it sheds light on the trade‐off between blocking probability and throughput. For the investigation of this trade‐off, we introduce the throughput‐threshold constraint, which bounds the probability that the throughput of a traffic flow drops below a predefined threshold. Finally, we use the model to determine the optimal parameter set of the popular partial overlap link allocation policy: we propose a computationally efficient algorithm that provides blocking probability‐ and throughput guarantees. We conclude that the model and the numerical results provide important insights in traffic engineering in the Internet. Copyright © 2002 John Wiley & Sons, Ltd.     

Supporting Excess Real-Time Traffic With Active Drop Queue

Real-time applications often stand to benefit from service guarantees, and in particular delay guarantees. However, most mechanisms that provide delay guarantees also hard-limit the amount of traffic the application can generate, i.e., to enforce to a traffic contract. This can be a significant constraint and interfere with the operation of many real-time applications. Our purpose in this paper is to propose and investigate solutions that overcome this limitation. We have four major goals: 1) guarantee a delay bound to a contracted amount of real-time traffic; 2)transmit with the same delay bound as many excess real-time packets as possible; 3) enforce a given link sharing ratio between excess real-time traffic and other service classes, e.g., best-effort; and 4) preserve the ordering of real-time packets, if required. Our approach is based on a combination of buffer management and scheduling mechanisms for both guaranteeing delay bounds, while allowing the transmission of excess traffic. We evaluate the “cost” of our scheme by measuring the processing overhead of an actual implementation, and we investigate its performance by means of simulations using video traffic traces.     

Coordinated multihop scheduling: a framework for end-to-end services

In multihop networks, packet schedulers at downstream nodes have an opportunity to make up for excessive latencies due to congestion at upstream nodes. Similarly, when packets incur low delays at upstream nodes, downstream nodes can reduce priority and schedule other packets first. The goal of this paper is to define a framework for design and analysis of coordinated multihop scheduling (CMS) which exploits such internode coordination. We first provide a general CMS definition which enables us to classify a number of schedulers from the literature, including G-EDF, FIFO+, CEDF, and work-conserving CJVC as examples of CMS schedulers. We then develop a distributed theory of traffic envelopes which enables us to derive end-to-end statistical admission control conditions for CMS schedulers. We show that CMS schedulers are able to limit traffic distortion to within a narrow range resulting in improved end-to-end performance and more efficient resource utilization. Consequently, our technique exploits statistical resource sharing among flows, classes, and nodes, and our results provide the first statistical multinode multiclass admission control algorithm for networks of work conserving servers.     

Proportional delay differentiation provision by bandwidth adaptation of class‐based queue scheduling

Supporting quality of service (QoS) over the Internet is a very important issue and many mechanisms have already been devised or are under way towards achieving this goal. One of the most important approaches is the so‐called Differentiated Services (DiffServ) architecture, which provides a scalable mechanism for QoS support in a TCP/IP network. The main concept underlying DiffServ is the aggregation of traffic flows at an ingress (or egress) point of a network and the marking of the IP packets of each traffic flow according to several classification criteria. Diffserv is classified under two taxonomies: the absolute and the relative. In absolute DiffServ architecture, an admission control scheme is utilized to provide QoS as absolute bounds of specific QoS parameters. The relative DiffServ model offers also QoS guarantees per class but in reference to the guarantees given to the other classes defined. In this paper, relative proportional delay differentiation is achieved based on class‐based queueing (CBQ) scheduler. Specifically, the service rates allocated to the classes of a CBQ scheduler are frequently adjusted in order to obtain relative delay spacing among them. The model presented can also be exploited in order to meet absolute delay constraints in conjunction with relative delay differentiation provision. Simulation experiments verify that our model can attain relative as well as absolute delay differentiation provided that the preconditions posed are satisfied. Copyright © 2004 John Wiley & Sons, Ltd.     

Towards Universal Power Efficient Scheduling in Gaussian Channels

In this paper, we propose a framework for designing power efficient schedulers for transmitting bursty traffic sources over Gaussian wireless channels that provides deterministic and statistical guarantees on absolute delays experienced by the source packets. The proposed schedulers compute the transmission rate and power using temporal water-filling techniques without any knowledge of the arrival traffic statistics. The schedulers reduce the average transmission power substantially (55% in some scenarios) for small increases in delay. The framework allows us to design schedulers that artfully tradeoff the performance with the complexity of computing the schedulers. We also introduce an iterative process to compute a lower bound on the transmit power of any scheduler that provides absolute delay guarantees. The utility of having accurate traffic predictors is demonstrated; specifically, we show that a perfect one step predictor achieves near optimal performances for small delay bounds. The proposed schedulers and iterative method of computing the lower bound are also shown to provide statistical guarantees on packet delays.     

Toward statistical QoS guarantees in a differentiated services network

In this paper, we propose and analyze a methodology for providing statistical guarantees within the diffserv model in a network, which uses static-priority schedulers. We extend the previous work on statistical delay analysis and develop a method that can be used to derive delay bounds without specific information on flow population. With this new method, we are able to successfully employ a utilization-based admission control approach for flow admission. This approach does not require explicit delay computation at admission time and hence is scalable to large systems. We systematically analyze the performance of our approaches in terms of system utilization. As expected, our experimental data show that statistical services can achieve much higher utilization than deterministic services.     

Efficient network QoS provisioning based on per node trafficshaping

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We consider a network comprised of store-and-forward packet switches, in which a packet scheduler is available at each output link. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same “minimal” envelope. The main disadvantage of this class of service discipline is that the end-to-end delay guarantees are obtained as the sum of the worst-case delays at each node, but we show that this problem can be alleviated through “proper” reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform service disciplines that are based on generalized processor sharing (GPS). Furthermore, we show that we can restrict the space of “good” shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving and as a result reduce the average end-to-end delays     

QoS provisioning in micro-cellular networks supporting multiple classes of traffic

We introduce an adaptive call admission control mechanism for wireless/mobile networks supporting multiple classes of traffic, and discuss a number of resource sharing schemes which can be used to allocate wireless bandwidth to different classes of traffic. The adaptive call admission control reacts to changing new call arrival rates, and the resource sharing mechanism reacts to rapidly changing traffic conditions in every radio cell due to mobility of mobile users. In addition, we have provided an analytical methodology which shows that the combination of the call admission control and the resource sharing schemes guarantees a predefined quality-of-service to each class of traffic. One major advantage of our approach is that it can be performed in a distributed fashion removing any bottlenecks that might arise due to frequent invocation of network call control functions.     

Absolute QoS differentiation in optical burst-switched networks

A number of schemes have been proposed for providing quality-of-service (QoS) differentiation in optical burst-switched (OBS) networks. Most existing schemes are based on a relative QoS model in which the service requirements for a given class of traffic are defined relative to the service requirements of another class of traffic. In this paper, we propose an absolute QoS model in OBS networks which ensures that the loss probability of the guaranteed traffic does not exceed a certain value. We describe two mechanisms for providing loss guarantees at OBS core nodes: an early dropping mechanism, which probabilistically drops the nonguaranteed traffic, and a wavelength grouping mechanism, which provisions necessary wavelengths for the guaranteed traffic. It is shown that integrating these two mechanisms outperforms the stand-alone schemes in providing loss guarantees, as well as reducing the loss experienced by the nonguaranteed traffic. We also discuss admission control and resource provisioning for OBS networks, and propose a path clustering technique to further improve the network-wide loss performance. We develop analytical loss models for the proposed schemes and verify the results by simulation.     

A case for relative differentiated services and the proportionaldifferentiation model

Internet applications and users have very diverse quality of service expectations, making the same-service-to-all model of the current Internet inadequate and limiting. There is a widespread consensus today that the Internet architecture has to extended with service differentiation mechanisms so that certain users and applications can get better service than others at a higher cost. One approach, referred to as absolute differentiated services, is based on sophisticated admission control and resource reservation mechanisms in order to provide guarantees or statistical assurances for absolute performance measures, such as a minimum service rate or maximum end-to-end delay. Another approach, which is simpler in terms of implementation, deployment, and network manageability, is to offer relative differentiated services between a small number of service classes. These classes are ordered based on their packet forwarding quality, in terms of per-hop metrics for the queuing delays and packet losses, giving the assurance that higher classes are better than lower classes. The applications and users, in this context, can dynamically select the class that best meets their quality and pricing constraints, without a priori guarantees for the actual performance level of each class. The relative differentiation approach can be further refined and quantified using the proportional differentiation model. This model aims to provide the network operator with the “tuning knobs” for adjusting the quality spacing between classes, independent of the class loads. When this spacing is feasible in short timescales, it can lead to predictable and controllable class differentiation, which ore two important features for any relative differentiation model. The proportional differentiation model can be approximated in practice with simple forwarding mechanisms (packet scheduling and buffer management) that we describe     

Understanding and improving TCP performance over networks withminimum rate guarantees

A large number of Internet applications are sensitive to overload conditions in the network. While these applications have been designed to adapt somewhat to the varying conditions in the Internet, they can benefit greatly from an increased level of predictability in network services. We propose minor extensions to the packet queueing and discard mechanisms used in routers, coupled with simple control mechanisms at the source that enable the network to guarantee minimal levels of throughput to different sessions while sharing the residual network capacity in a cooperative manner. The service realized by the proposed mechanisms is an interpretation of the controlled-load service being standardized by the Internet Engineering Task Force. Although controlled-load service can be used in conjunction with any transport protocol, our focus in this paper is on understanding its interaction with Transmission Control Protocol (TCP). Specifically, we study the dynamics of TCP traffic in an integrated services network that simultaneously supports both best-effort and controlled-load sessions. In light of this study, we propose and experiment with modifications to TCP's congestion control mechanisms in order to improve its performance in networks where a minimum transmission rate is guaranteed. We then investigate the effect of network transients, such as changes in traffic load and in service levels, on the performance of controlled-load as well as best-effort connections. To capture the evolution of integrated services in the Internet, we also consider situations where only a selective set of routers are capable of providing service differentiation between best-effort and controlled-load traffic. Finally, we show how the service mechanisms proposed here can be embedded within other packet and link scheduling frameworks in a fully evolved integrated services Internet     

Statistical service assurances for traffic scheduling algorithms

Network services for the most demanding advanced networked applications which require absolute, per-flow service assurances can be deterministic or statistical. By exploiting the statistical properties of traffic, statistical assurances can extract more capacity from a network than deterministic assurances. We consider statistical service assurances for traffic scheduling algorithms. We present functions, so-called effective envelopes, which are, with high certainty, upper bounds of multiplexed traffic. Effective envelopes can be used to obtain bounds on the amount of traffic on a link that can be provisioned with statistical service assurances. We show that our bounds can be applied to a variety of traffic scheduling algorithms. In fact, one can reuse existing admission control functions for scheduling algorithms with deterministic assurances. We present numerical examples which compare the number of flows with statistical assurances that can be admitted with our effective envelope approach to those achieved with existing methods     

A framework for bandwidth management in ATM networks-aggregateequivalent bandwidth estimation approach

A unified framework for traffic control and bandwidth management in ATM networks is proposed. It bridges algorithms for real-time and data services. The central concept of this framework is adaptive connection admission. It employs an estimation of the aggregate equivalent bandwidth required by connections carried in each output port of the ATM switches. The estimation process takes into account both the traffic source declarations and the connection superposition process measurements in the switch output ports. This is done in an optimization framework based on a linear Kalman filter. To provide a required quality of service guarantee, bandwidth is reserved for possible estimation error. The algorithm is robust and copes very well with unpredicted changes in source parameters, thereby resulting in high bandwidth utilization while providing the required quality of service. The proposed approach can also take into account the influence of the source policing mechanism. The tradeoff between strict and relaxed source policing is discussed     

Routing in ISL networks considering empirical IP traffic

Next-generation satellite networks are expected to provide a variety of applications with diverse performance requirements, which will call for the development of adaptive routing procedures supporting different levels of services. In this paper, we propose traffic class dependent (TCD) routing, which has the potential to differentiate between traffic classes using different optimization criteria in route calculation. The performance of TCD routing is evaluated for different traffic scenarios using an empirical traffic source model derived from the real backbone Internet traffic trace and compared with results obtained with equivalent Poisson traffic as a reference point. In addition, TCD routing is compared with a simple single service routing procedure, which does not make any distinction between traffic classes. Performance analysis, in terms of average packet delay, normalized data throughput, and normalized link load, reveals improved routing resulting from traffic class differentiation, regardless of the traffic scenario considered. The performance measures based of aggregate traffic flow show no significant difference between routing of empirical and equivalent Poisson traffic.     

Matrix extensions of the filtering theory for deterministic trafficregulation and service guarantees

We extend the filtering theory, presented in a previous paper, for deterministic traffic regulation and service guarantees to the matrix setting. Such an extension enables us to model telecommunication networks as linear systems with multiple inputs and multiple outputs under the (min,+)-algebra. Analogous to the scalar setting, there is an associated calculus in the matrix setting, including feedback, concatenation, “filter bank summation”, and performance bounds. As an application of the calculus, we derive service guarantees for networks with nested window flow control. In particular, service guarantees for networks with tandem flow control can be solved explicitly by the Gauss elimination