Architectures for providing delay-guaranteed communication over internetworks either follow a connection-oriented model or at least rely on detailed per-flow information. In the IETF Integrated Services (intserv) architecture [2], for example, each connection is controlled both by admission control at connection admission time and by packet scheduling during the lifetime of the connection. At establishment time, the necessary resources must be allocated to the new connection, and during the lifetime, the connection is policed to ensure that the abnormal behavior of a connection does not affect other connections. This necessitates that information about each connection is kept by each node along the path for admission control and packet forwarding.
It is agreed upon that Integrated Services do not scale. High-speed routers are required to maintain state and perform scheduling decisions for large numbers of connections. In addition, as the number of connections increases, the run-time overhead incurred in connection establishment and tear-down increases as well. The Integrated Services architecture therefore cannot provide scalable QoS guaranteed services, and the lack of scalability is due to overhead both at connection establishment and during the connection lifetime.
The Differentiated Services (diffserv) architecture is aimed at supporting service scalability through aggregation of flows into service classes [7]. Network nodes in diffserv display per-hop, per-class behavior, and need not maintain per-flow information. Since each router only guarantees that service agreements are locally maintained on a per-class basis, intserv-style end-to-end guarantees are difficult to provide. The end-to-end service might vary with networking conditions. A number of approaches have been proposed to provide intserv-like end-to-end performance without per-flow information in the network core. For example, assuming that no dynamic routing occurs, the Premium Service, which has been defined within the diffserv architecture, can offer the user a performance level that is similar to that of a leased-line, as long as the user's traffic is limited to a given bandwidth [18]. We call this type of service absolute differentiated services.
In order to provide service guarantees, an admission control mechanism has to be in place, which makes sure that enough resources are available to satisfy the requirements of both the new and the existing connections after the new connection has been admitted. In order to keep steps with the scalability requirements for differentiated services networks, any admission control mechanism must be extremely light-weight so that can be realized in a scalable fashion. While the benefits of flow aggregation in terms of reduced overhead for packet scheduling are clear, the question of how to take advantage of the flow aggregation in differentiated-services networks for scaling of connection admission remains to be answered. In particular, methods must be found that work in the absence of per-flow information and when policing in the network is done on a per-class basis only. A number of approaches are being studied (e.g., [4,24]) for admission control that relies on class-based information. In [24], we use appropriate system (re-)configuration steps to derive safe resource utilization bounds in each network node. Admission control is then reduced to a simple utilization-based test along the path of the flow: as long as the utilization of links along the path of a flow is not beyond a given bound, the probabilistic performance guarantee can be met. Thus, this approach (called Utilization-Based Admission Control - UBAC - in the following) eliminates explicit delay analysis at admission time, and helps the system scale up.
Utilization-based admission control (UBAC) is not new to networks. The fluid-flow model in the intserv framework, for example, allows various forms of utilization based admission control [20]. Such approaches cannot be used in a diffserv framework, however, because the fluid-flow model relies on guaranteed-rate schedulers, which need to maintain per-flow information and provide strong isolation between flows. The challenge of using the UBAC method is how to verify the correctness of a safe utilization bound at configuration time, when (i) schedulers in the nodes provide no policing and generally no isolation between flows belonging to the same class (we will be using class-based static-priority schedulers in this paper) and when (ii) no information is available yet about the flow population. For the case of deterministic performance guarantees for absolute differentiated services, we have derived methods to determine and/or assign safe utilization bounds (e.g., [24]).
While deterministic services provide a very simple model to the application, they tend to heavily overcommit resources because they account for the worst-case scenario. In real systems, this mostly results in significant portions of network resources (bandwidth etc.) being wasted [25]. Statistical services, on the other hand, significantly increase the efficiency of network usage by allowing increased statistical multiplexing of the underlying network resources. This comes at the expense of packets occasionally being dropped or excessively delayed. In this papers we will show how such probabilistic guarantees can be provided in a differentiated services framework.
We will describe below how significant progress has been made to provide statistical performance guarantees within the intserv framework. All these results depend either on flow-aware schedulers or on information about flow population during admission control, and would therefore not be suited for use in a diffserv setting.
Our approach is based on rate-variance envelopes [11,12], a simple and general traffic characterization. Such envelopes describe the variances of the flow rates as a function of the interval length. The results on delay violation probability derived in [12] depend on detailed information about the flow population. In this paper, we will develop flow-unaware versions of these results, and so develop a method that allows us to analyze delays and determine safe utilization bounds without depending on the dynamic status of the flow population. This will provide the basis for a scalable admission control for statistical performance guarantees in absolute differentiated services.
We will consider networks that use class-based static priority schedulers. Given that static priority scheduling is supported in many current routers (e.g., Packet Engines' RowerRail Routing Switch), our approach can be easily implemented in existing networks. As expected, our experimental data show that statistical services can achieve much higher utilization than deterministic services.
The rest of the paper is organized as follows. In Section 2, we describe previous work on absolute differentiated services and statistical service in general. The underlying network and traffic models for this study are introduced in Section 3. In Section 4, we develop a delay analysis methodology that is insensitive to flow information. In Section 5, we provide extensive experimental data to illustrate that the utilization achieved within a statistical model is much higher than within a deterministic model. A summary of the paper is given in Section 6.
A good survey with recent work on absolute differentiated services has been done in [21]. Nicols et. al. [18] propose the premium service model, which provides the equivalent of a dedicated link between two access routers. This model provides absolute differentiated services in priority-driven scheduling networks with two priorities, in which the high priority is reserved for premium service. Cruz [5] describes SCED+, which provides both guaranteed and statistical rate and delay bounds, and addresses scalability through traffic aggregation and statistical multiplexing. Stoica and Zhang [23] describe an architecture to provide guaranteed service without per-flow state management by using a technique called dynamic packet state (DPS). Our work is based on static-priority scheduling, which is relatively simple and widely supported.
Statistical service has been studied via envelopes of bounding moment generating functions [3], exponentially bounded envelopes [22,27], and envelopes consisting of families of bounding distributions [13,28]. Statistical envelopes have also been applied to resource allocation for inter-class resource sharing [19] and video-on-demand services [9]. Much work has been done to generalize schedulabilty conditions for a deterministic service to a probabilistic framework. Several researchers made probabilistic extensions to deterministic service models. In [12], a rate-variance envelope is introduced, which describes the variance of the arrivals of a flow as a function of a time period of length. In [10], arrivals on a flow are assumed to be characterized by the rate-variance envelope and a long-term arrival rate. Then, applying the a central limit theorem argument, a bound for the probability of a delay bound violation is derived for a static priority scheduler. In [12], the same framework is used to address bounds on the rate-variance envelope for regulated, adversarial traffic sources. In [11], the authors use a rate-variance envelope as a simple way to capture the second-moment properties of temporally correlated traffic flows, and to describe how quickly the rate-distribution becomes concentrated at the mean rate with increasing interval-length, a key factor for computing delay-bound-violation probabilities. They show empirical rate-variance envelopes for several long traces of compressed video to show how it captures the burstiness properties of realistic network traffic sources. In this paper, we will use this rate-variance envelope to do statistical delay analysis.
Admission control has been investigated widely [6,8,16]. The various approaches differ from each other in that they may require different scheduling schemes and so can be of vastly different complexity. For example, traditional admission control in networks with static priority scheduling is very complicated. Due to absence of flow separation, for any new flow request, admission control needs to explicitly compute and verify delays for the new and existing flows. This procedure is very expensive with increasing numbers of flows. The Utilization-Based Admission Control (UBAC) adopted dramatically reduces this complexity.
In its basic form, UBAC was first proposed in [15] for preemptive scheduling of periodic tasks on a simple processor. A number of utilization-based tests are known for centralized systems(e.g., 69% and 100% for periodic tasks on a single server using rate-monotonic and earliest-deadline-first scheduling, respectively [15]), or distributed systems(such as 33% for synchronous traffic over FDDI networks [1]). In this paper, we adopt utilization-based tests in providing differentiated services in static priority scheduling networks.
Our assumptions about network nodes and network traffic follow the Differentiated Services architecture: In the network, we differentiate flow-aware edge routers from core routers, which are only aware of aggregations of flows in form of flow classes. The network traffic consists of flows, which each belong to one of several flow classes. Examples of such flow classes are best-effort, voice-over-IP, video, or others. The flow class specifies both the traffic descriptor of a flow and its QoS requirements. We proceed below to describe our models in more detail.
The IETF diffserv architecture distinguishes two types of routers: Edge routers are located at the boundary of the network, and provide support for traffic policing. Core routers are within the network, and maintain no flow information. Scheduling decisions within the core are therefore made based on class information only. Routers are connected through links, which we assume - for sake of simplicity of argument - to all be of capacity C, in bits per second.
When we compute delays, we follow standard practice and model a router as a set of servers, one for each router component where packets can experience delays. Packets are typically queued at some of these servers, typically at the output buffers, where they compete for the output link. Hence, we model a router as a set of output link servers. The other servers (input buffers, non-blocking switch fabric, wires, etc.) are typically not congested, and therefore can be eliminated by appropriately subtracting their constant delays from the deadline requirements of the traffic.
We assume that the schedulers in the nodes are not flow aware. Policing and scheduling therefore happens at class level, with class-based static priority schedulers assumed in this paper. Packets belonging to classes with higher priorities will be served prior to those with lower priorities.
Using class-based static priority schedulers alone makes it difficult to determine statistical end-to-end delays. The delay analysis methods described below rely on statistical independence among flows, and without additional mechanisms, the flows are no longer independent after being multiplexed at a server. Statistical independence can be re-established with the use of class-based jitter controller [14] at each core router. Class-based jitter control works by delaying each packet in a core router by its ahead time before passing the packet to the schedulers. The ahead time is the amount of time by which the packet left the previous server ahead of the deadline for its class. In this way, the statistical properties of the traffic arriving at the network edge is re-generated at each core router. It follows that the end-to-end delays can be easily determined from local delays at each server along the path of a flow. For example, we will describe in Section 4.2 how the end-to-end delay probability is bounded by a product formula of the local delay probability of each server along the path of a flow. In the following discussion, we will therefore focus on the single-server analysis, and return to the end-to-end delay case in Section 4.2.
We call a stream of packets between a sender and receiver a flow. Packets of a flow are transmitted along a single path, which we model as a list of link servers. Following the diffserv architecture, flows are partitioned into a number, say M, classes. QoS requirements and traffic specifications of flows are defined on a class-by-class basis 1. We assume that at each link server, a certain percentage of bandwidth is reserved for each particular traffic class. Let ai denote the percentage of bandwidth reserved for Class i. It is the responsibility of the admission control module to ensure that the bandwidth usage of individual classes does not exceed the reserved portion. This is necessary to provide isolation among classes and hence to guarantee end-to-end delays to the flows in each class.
We model the traffic arrival for a flow as a stochastic arrival process A = { A(t), t ³ 0 }, where random variable A(t) denotes the incoming traffic amount of the flow for a link server during time interval [0,t]. The arrival process A is stationary and ergodic. The traffic arrivals for any two different flows are stochastically independent at the edge of the network and jitter controllers in the core routers preserve independence throughout the network core. The traffic arrival can be bounded either deterministically or stochastically by the arrival traffic envelopes as follows:
Definition 1 [Deterministic Arrival Traffic Envelope]
The function b(t) is called the deterministic arrival traffic envelope of the traffic arrival A if
A(t+ t) - A(t) £ b(t), (1)
Definition 2 [Statistical Arrival Traffic Envelope]
The distribution B(t) forms the stochastic arrival traffic envelope of the traffic arrival A if
A(t+ t) - A(t) £ st B(t), (2)
Since A(t) is stationary, A(t+ t) - A(t) possesses the same probability distributions for all t. Therefore, we can define a random variable R(t) as the stochastic arrival traffic rate as follows:
| (3) |
| (4) |
We assume that a class-i traffic flow is controlled by a leaky bucket with burst size si and average rate ri.
In the following, we will use the notation Gi,j to denote a group of flows of Class i from Input Link j of a server and use bi,j, Bi,j, and RVi,j to specify the deterministic arrival traffic envelope, the stochastic arrival traffic envelope, and the rate-variance envelope applied to the group of flows Gi,j respectively.
In the following, we will use a utilization-based test to realize admission control in a scalable fashion. During system (re-)configuration, a safe utilization bound is determined, which is then used for the tests during run time. As long as the utilization values of links along the path of a new flow do not exceed the safe utilization bound, the performance guarantees of all the flows will be met. The value for this utilization bound depends on network topology, traffic characteristics, and performance requirements of flows.
The challenge of using any utilization-based admission control method is to verify the correctness of a safe utilization bound at configuration time. Two critical issues have to be addressed:
First, we will address the issue of statistical delay analysis, and then derive the flow-population-insensitive statistical delay formula.
A probabilistic performance guarantee can be defined as a bound on the probability of exceeding a deadline as follows:
| (5) |
In statistical service, all input traffic conforms to a set of random processes. Suppose these processes are independent. If we know the mean value and the variance of each individual traffic random variable, and the number of flows is large enough, then by the Central Limit Theorem, we can approximate the random process of the combined flows. The Central Limit Theorem states that the summation of a set of independent random variables converges in distribution to a random variable that has a Normal Distribution. Actually, using rate-variance envelopes, the traffic arrival rate of each individual flow is a random variable, and the mean rate and the rate-variance of each individual flow can be determined using deterministic traffic models. The following theorem can be found in [12]:
Consider a static-priority scheduler with L input links and link capacity C such that the traffic with Class i has an associated deadline di. Suppose that the group of flows Gi,j has mean rate fi,j and rate-variance envelope RVi,j(t). With application of a Gaussian approximation over intervals, the delay violation probability for a random packet with Class i is approximately bounded by
| ||||||||||||||||||||||||||||||||||||||
| (7) |
| (8) |
| (9) |
By this theorem, the delay violation probability for any random packet can be computed approximately. In the above formula, the question left is how to get the values of mean rate and rate-variance envelope. In [12], two methods are presented for obtaining the rate-variance envelope:
Therefore, given the aggregated arrival traffic constraint function bi,j(t) of all ni,j flows, we can specify the mean rate and the rate-variance envelope as a function of ni,j etc.. By Theorem 2 in [24], the aggregated arrival traffic constraint function bi,j(t) is given as follows
| (10) | ||||||||||
| |||||||||||
Given the same condition as Theorem 1, the mean rate fi,j is
| (12) |
| (13) |
| (14) |
The proof of Theorem 2 is given in Appendix.
At this point, the only undetermined is the number of flows on each link. In the following subsections, we describe how we eliminate the dependency on the number of flows on each link. The result is a delay formula that can be applied without knowledge of the flow population.
As we described earlier, admission control at run-time makes sure that the link utilization allocated to each class of flows is not exceeded. The total number Ni of flows of Class i from all input links is therefore subject to the following constraint:
| (15) |
Consider a static priority scheduler with L input links and link capacity C such that the traffic with Class i has an associated deadline di. Suppose that the group of flows Gi,j has a stochastic envelope Bi,j(t). Then the delay violation probability for a random packet of Class i is bounded by
| (16) |
| (17) |
| (18) |
| |||||||||||||||
| |||||||||||||||||||||
This is the main result of this paper. We observe that the formula does not depend on the flow population. Hence it can be used for utilization bound verification at configuration time. In the following, we will give the proof. The basic idea is that using inequality (15), flow-population will be removed.
Substituting (12), (13) and (14) into (7) and (8), we have
| ||||||||||||||||||||||
| ||||||||||||||||||||||
| ||||||||||||||||||||||||
By (15), we have
| |||||||||||
| |||||||||||||
| (27) |
| (28) |
where xi(t) is defined in (18).
As an illustrative example, we apply the above theorem in the case of two classes, only one real-time class traffic. Suppose that a = a1, s = s1, r = r1, d = d1, D = D1, x(t) = x1(t), b = b1, for real-time class traffic. Simplifying the formula, we can get the following corollary:
In the case of a single real-time class, the delay violation probability for a random real-time class traffic packet is bounded by
| (29) |
| (30) |
| (31) |
| (32) |
Define the right hand side of (29) and (30) as e1 and e2. We can find that x(t) reaches its minimum at t = t0( = [d/( 1-a)]). By the property of function x(t), we find
| |||||||||||||||||||||||||||||||||||||||||
if b < t0, i.e., a < [d/( [(s)/( r)])], then
| |||||||||||||||||||||||||||||||||||||||||||
For the deterministic model, by Theorem 4 in [26], a bandwidth ratio formula can be derived as follows:
| ||||||||||
Having derived the flow-population-insensitive statistical delay formula, we can verify the utilization bound, and obtain the worst-case achievable utilization (WCAU). By the worst-case achievable utilization, we refer to the maximum of total utilization bound for all classes. Under the condition that the probabilistic delay guarantee can be met, we can compute the WCAU.
For a given delay violation probability ei and deadline di along route R , we can split di into {dik: k Î R}, and the delay guarantee is met when
| |||||||||||||||||||
In this section, we evaluate the performance of the approaches discussed in the previous sections. We will first define the performance metrics, and then describe the system configuration and present the performance results.
In this sub-section, we report performance results and make observations. Due to the limited space, we only present a limited number of cases here. However, we find that the conclusions we draw here generally hold for many other cases we have evaluated.
| e | WCAU | ||
| deterministic | adversarial | non-adversarial | |
| 0 | 0.250 | - | - |
| 10-6 | - | 0.250 | 0.488 |
| 10-4 | - | 0.250 | 0.563 |
| 10-2 | - | 0.307 | 0.699 |
Data on sensitivity of utilization to delay violation probability are given in Figures 1 and Table 1. Figure 1 and Table 1 show the data on the cases of the delay violation probability e. From Figures 1 and Table 1, we have the following observations:
Data on sensitivity of admission probability is given in Figure 2 (Note that the curve for deterministic model and the curve for statistical model (adversarial, e = 0.001) overlaps). From this figure, we make the following observations:
Different models have different sensitivities to l in terms of admission probability. The statistical models always achieve higher admission probabilities than the deterministic model. Non-adversarial models always achieve higher admission probabilities than adversarial models. This is because of the achievable utilization. The higher this utilization, the higher the admission probability.
In this paper, we have proposed a methodology for providing absolute differentiated services with statistical performance guarantees in networks that use static priority schedulers. Given that static priority schedulers are widely supported by current routers, we believe that our approach is practical and effective to support real-time applications in existing networks.
We have used Utilization-based Admission Control (UBAC) approach which uses a configuration-time verification to determine a safe utilization level of servers. Admission control at runtime then is reduced to simple utilization tests on the servers along the path of the new flow. Hence, the approach is scalable.
Obviously, the verification will have to be involved with delay analysis. The general delay derivation depends on flow population information, which is not available at the system configuration time. We have extended the general approach and developed a method that allows us to analyze the delays without depending on the dynamic status of flow population.
This work was partially sponsored by NSF under contract number EIA-0081761, by DARPA under contract number F30602-99-1-0531, and by Texas Higher Education Coordinating Board under its Advanced Technology Program.
The following lemmas (1, 2, and 3) [12] define the mean rate for a group of flows and show how an upper bound on the stochastic rate variane envelope can be derived from the deterministic parameters. [Mean Rate] The mean rate of the group of flows Gi,j can be defined as:
| (40) |
[Adversarial Mode] The rate-variance envelope of the group of flows Gi,j is upper bounded by:
| (41) |
[Non-adversarial Mode] The rate-variance envelope of the group of flows Gi,j is approximately:
| (42) |
We know that the aggregated arrival traffic constraint function bi,k,j(t) is given as follows
| (43) | ||||||||||
Then applying (43) to (40), (41), and (42), Theorem 2 can be proved as claimed.
1 While at network level all flows within a class have identical traffic specifications and QoS requirements, user-level connections with varying bandwidth and burstiness requirements can be established by using more than one flow.
2 X £ st Y means P{X > Z} £ P{Y > Z} [13].