tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

- Utilization-based admission control for real-time applications
- Real-time behavior-based robot control
- 1 Fuzzy Based Rate Control for Real-Time MPEG Video
- Interval-based Real-Time Transmission Control
- Partition-Based Admission Control in Heterogeneous Networks for Hard Real-Time Connections
- A Sound Localization Based Interface For Real-Time Control Of Audio Processing
- Scalability based admission control of real-time channels
- Real-Time Model-Based Control System Design and Automation for Gelcast Drying Process
- A Unified Approach for Predictability Analysis of Real-Time Systems using UML-based Control
- Admission control for hard real-time connections in

Real-Time Systems, 24, 171±202, 2003 # 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.

Utilization-Based Admission Control for Scalable Real-Time Communication

BYUNG-KYU CHOI bkchoi@mtu.edu Department of Computer Science, Michigan Technological University, Houghton, MI 49931-1295, USA DONG XUAN xuan@cis.ohio-state.edu Department of Computer and Information Science, The Ohio State University, Columbus, OH 43210-1277, USA RICCARDO BETTATI bettati@cs.tamu.edu Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, USA WEI ZHAO zhao@cs.tamu.edu Department of Computer Science, Texas A&M University, College Station, TX 77843-3112, USA CHENGZHI LI c14v@cs.virginia.edu Department of Computer Science, University of Virginia, Charlottesville, VA 22904-4740, USA Abstract. We propose a utilization-based schedulability and admission control mechanism for distributed systems with workload aggregation to achieve scalability. We use the differentiated services (diffserv) architecture to describe and illustrate our approach. Scalability of admission control is achieved by determining off-line safe levels of server utilization. Scalability during the connection lifetimes is provided by the aggregation mechanisms (for example, class-based scheduling) provided by the diffserv architecture. Our evaluations show that our system's admission probabilities are very close to those of signi?cantly more expensive approaches, which do not allow for workload aggregation. At the same time, admission control overhead during ?ow establishment is very low. Keywords: admission control, end-to-end deadlines, schedulable utilization, QoS guarantees, and differentiated services

1.

Introduction

This paper presents a methodology to apply utilization-based admission control to provide hard real-time communication in a scalable fashion. By hard real-time we mean that packets are delivered from their sources to the destinations within their end-to-end deadlines. Packets delivered beyond their end-to-end deadlines are considered useless. By scalable we mean that we want to support a large number (say, many thousands) of connections over a network with many nodes (in our context nodes are switches or routers), while at the same time allowing for high resource utilization. The integrated services (IS) architecture of the IETF (Braden et al., 1994) is a good example to illustrate the types of problems encountered in admission control for large systems. In IS, each connection is strictly controlled both by admission control at connection establishment time and by packet scheduling during the lifetime of the connection. At establishment time, the necessary resources for the new connection are

172

CHOI ET AL.

allocated, and during the lifetime, the connection is policed to ensure that abnormal behavior of a connection does not affect other connections. This necessitates that information about every connection is kept by each node along the path for admission control and packet forwarding purposes. Integrated services are dif?cult to deploy in large-scale high-speed internetworks, as they do not scale well, for two reasons: ?rst, high-speed routers are required to maintain and schedule packets for large numbers of connections. Second, as the number of connections increases, the run-time overhead incurred for connection establishment and tear-down increases as well. The IS architecture therefore does not provide scalable quality of service (QoS) guaranteed services, and the lack of scalability is due to overhead both at connection establishment and during the connection lifetime. To make real-time communication scalable, the overhead of both admission control during connection establishment and packet scheduling during the connection lifetime must be largely independent of the number of connections in the system. One way to achieve this is to aggregate connections: Each of the many user-level ?ows1 is assigned to only a small number of prede?ned classes. Packets in each class are served accordingly to a class-based scheduling policy. The result is that nodes are aware only of aggregations of ?ows. While the bene?ts of ?ow aggregation in terms of reduced overhead for packet scheduling are clear, and are being made use of, for example, in the differentiated services (DS) architecture (Bernet et al., 1999; Blake et al., 1998; Nicols et al., 1997), the question of how to take advantage of ?ow aggregation for scaling of connection admission remains to be answered. Utilization-based methods have implicitly, but naturally relied on workload aggregation to provide scalable and robust schedulability testing and admission control mechanisms. All these techniques de?ne a utilization level below which all the workload using the resource is guaranteed to meet its deadline. This utilization level is sometimes called the worst-case schedulable utilization (WCSU) for that resource. The WCSU can then be compared against the resource utilization during schedulability analysis at design time or during admission control at run time to determine whether the workload can be guaranteed to meet its deadlines. A variety of WCSU's for different settings have been found, for example, 69% and 100% for preemptive scheduling of periodic tasks on a single server using rate-monotonic and earliest-deadline-?rst scheduling, respectively (Liu and Layland, 1973; Park et al., 1996), or 33% bandwidth utilization for scheduling synchronous traf?c over FDDI networks. Unfortunately, utilization-based methods to provide end-to-end delay guarantees in distributed systems are limited. WCSU's have been derived for single servers, or for some shared servers (like token rings), and can therefore be used only indirectly for systems with multiple servers. This is typically done by deriving the local delay of a ?ow on each single server from that server's utilization, and then summing up the local delays on all the servers used by the ?ow. Utilization-based methods assume either ?ows with periodic arrival at the server, or the presence of workload regulation. Workload regulation in networks can be done explicitly, with the use of traf?c shapers, or is inherently part of servers with guaranteed-rate schedulers, such as weighted-fair-queueing (WFQ) (Parekh and Gallager, 1993; 1994), virtual clock (VC) (Zhang, 1991), or others. Unfortunately, workload regulation in the

UTILIZATION-BASED ADMISSION CONTROL

173

network relies on identifying individual ?ows to regulate, thus eliminating ?ow aggregation for packet forwarding. Relying on workloads being periodic at the ?rst server does not hold in systems where ?ows traverse multiple servers, and therefore become more and more jittered as they do so. In this paper, we derive a highly scalable utilization-based mechanism to perform admission control in a system with workload aggregation. One of the main results in this paper will be a complement of the results on schedulable utilization bounds for single server systems. We will describe a simple algorithm to test whether a given utilization level can guarantee that a set of workloads with end-to-end delay requirements can be guaranteed to meet its deadlines over a network of servers. While our results can be used for a large class of networks or distributed systems, we will illustrate our approach using the DS architecture (Nicols et al., 1997; Blake et al., 1998; Bernet et al., 1999). From the user's point of view, the DS model partitions each user-level ?ow into one of a set of prede?ned classes. Packets of each class are served inside the network according to a class based scheduling policy. The result is that routers are aware only of aggregations of ?ows.2 Each edge router is supposed to aggregate the individual ?ows into a small number of such aggregate ?ows. In this fashion, the DS model makes the network scalable regardless of the number of ?ows. A number of details about how to realize and deploy DS are still being discussed. We make admission control scalable by using an off-line test to determine a safe utilization level of servers. Admission control then is reduced to simple utilization tests on the servers along the path of a connection. In data forwarding, we assume class-based static priority packet scheduling, which typically requires a small number of classes, and therefore allows for a large degree of ?ow aggregation. We show in Section 5 that our system provides admission probabilities and resource utilizations that are very similar to those of other existing approaches. This is particularly interesting, since the run-time overhead of our approach is very low, compared to the other previous approaches, regardless of whether they allow for ?ow aggregation or not. The rest of the paper is organized as follows. In Section 2, we describe previous work and our motivation. Our models of network, ?ow, and the DS model are presented in Section 3. In Section 4, we provide our system including off-line end-to-end delay calculation, admission control, and class-based static priority scheduling scheme. We also present the end-to-end delay formula in Section 4.2, with detailed proof in the appendices Section 5 presents evaluation by simulation of our system and previous works. While Section 6 introduces issues involved in implementation, a summary and motivation of future work are given in Section 7 in our conclusions.

2.

Previous Works

Obviously, most currently deployed packet forwarding schemes for internetworks do not guarantee anything on end-to-end delay since the delay purely depends on the dynamic load of network links. A number of schemes proposed are the ways to deploy network services that provide QoS guarantees. As described earlier, the IS architecture is a great

174

CHOI ET AL.

step towards the goal of QoS guarantees. One step further, the DS architecture (Nicols et al., 1997; Blake et al., 1998; Bernet et al., 1999) takes scalability issues into account. Among the QoS guarantee components, our main interests are admission control and packet scheduling, in terms of end-to-end delay guarantees for real-time services. As far as these two technical aspects are concerned, much research has been proposed in the last decade. First, with some traf?c models, a number of end-to-end delay calculation methods have been proposed (Figueira and Pasquale, 1995; Banerjea and Keshav, 1993; Golestani, 1995; Goyal et al., 1995). Also, many packet scheduling mechanisms have been provided (Bennett and Zhang, 1996; Figueira and Pasquale, 1997; Hyman et al., 1991; Parekh and Gallager, 1993; 1994; Zhang, 1991; Zhang et al., 1996). Finally admission control has been investigated as well (Dailianas and Bovopoulis, 1994; Firoiu et al., 1997; Liebeherr et al., 1996). Much of this work addresses admission control and packet scheduling. Some deal with meeting end-to-end delay requirements. Some of the proposals have been implemented and deployed, for example, NetEx, RSVP, and Tenet. NetEx (Devella et al., 1997; Sahoo et al., to appear) is a good working example of implemented system based on extensions of Cruz's methodology for delay analysis (Cruz, 1991a; 1991b). Essentially, NetEx provides connection-oriented real-time communication service by relying on a strict admission control (Raha et al., 1995). RSVP (Zhang et al., 1993) has been proposed as the signaling and resource reservation in the IS architecture. Tenet Scheme II (Bettati et al., 1995) uses a two-pass resource allocation scheme, with extensive functionality needed for multi-party communication. However, one common point of all these systems is their limited scalability. As the number of connections increases, the admission control needs proportionally more time to make admission decision. Because they rely on each connection's information. Therefore, they provide a real-time service, but are not scalable to a large scale internetwork due to their run-time overhead in admission control and packet scheduling. Recently, a number of efforts have focused on reducing the negative effect on scalability caused by connection awareness in signaling protocols. The work in Stoica and Zhang (1999) is a good example of such efforts. The basic idea in Stoica and Zhang (1999) is to move per-?ow information to edge routers from core routers by relying on estimation. The key points of the estimation technique are: (1) each core router relies on dynamic packet status information for admission control and packet scheduling, (2) dynamic packet status information is carried over by each packet. With this information, the core router estimates each ?ow's dynamic information such as end-to-end delay. So it achieves that the core router does not need to maintain per ?ow information anymore but infers it based on information carried with the packet. As such, Stoica and Zhang (1999) does not do ?ow aggregation. Only the storage of per-?ow information has moved to the edge router from the core router. This means that, since each packet bears the ?ow's information, the run-time overhead of the estimation technique becomes a non-negligible factor. We believe that to be scalable, the core router should serve packets with classbased information only, thus rely on ?ow aggregation. For the DS architecture, much research needs to be done to provide end-to-end delay guarantees. In this paper, we propose a system of admission control and packet forwarding schemes that guarantee end-to-end delay for each ?ow in a DS architecture (Blake et al., 1998). By having off-line end-to-end delay computation, our admission

UTILIZATION-BASED ADMISSION CONTROL

175

control complexity is de?nitely lower than those of (Devella et al., 1997; Sahoo et al., to appear; Cruz, 1991a; 1991b; Raha et al., 1995; Stoica and Zhang, 1999; Bettati et al., 1995), while guaranteeing end-to-end delay deadlines for all ?ows. Also, we argue that our system's runtime overhead should be lower than that of Stoica and Zhang (1999), because we use class-based static priority scheduling. To the best of our knowledge, this is the ?rst proposal addressing end-to-end delay guarantee and scalable run time overhead within a DS model.

3.

Our Models

In this section, we describe the model and de?ne the terminology (network, link server, path, ?ow, and service classes) that will be used in the following sections. Network A network consists of a number of nodes (e.g., routers and hosts). Nodes are connected by physical links on which packets are forwarded. Following the DS model, we assume that the network is partitioned into multiple domains. Each domain can have many routers. Figure 1 illustrates an example of one domain. The network resources are controlled by the domain manager(s) in centralized or distributed fashion. In this paper, we focus on a network with a single domain. We expect that a number of approaches, for example, deadline partitioning, can then be used to extend to networks with multiple domains. The particular approach choses would also depend on the details of the interdomain service level agreements.

Figure 1. A simple illustration of our domain.

176

CHOI ET AL.

Routers and Links There are two kinds of routers in a domain: edge and core router as shown in Figure 1. As the name implies, the edge router is at the edge of the domain, and the core router is in the interior of the domain. A router has multiple input and output links. We assume that there are N input links at a router. For the incoming packet, the router determines the output link by looking up its routing table, and transports the packet to the proper output link, which, in turn, connects to the next hop. It is possible that a packet may have to be queued at the output link because of the limitation of output link capacity. We denote C as the output link capacity, in bits per second. Packets may exceed the capacity at the output link, and thus the packet may suffer some queueing delay at the output link. This delay depends on the load of the output link and the scheduling policy adopted at the output link. For delay computation purpose, the router can be regarded as a set of link servers, one for each output link, at which the packet can experience the queuing delay. C denotes the link capacity in bits per second. In the following discussion, we treat output links as link servers, or servers, with a given capacity and scheduling policy. The network is then modeled as a network of link servers. We denote link server i as Si . There are total M servers. Paths A packet is transmitted along a path. The path is a list of nodes. Equivalently, a path can also be denoted as a list of link servers. For example, if a path traverses link servers: S1 , S2 , S6 and S7 , then the path can be denoted as h1; 2; 6; 7i, where the integers are the ids of link servers which the path traverses. In the rest of this paper, the path means a list of link servers rather than nodes unless otherwise mentioned. In the following discussion of the admission control, we assume that the path of a new ?ow has been determined by a separate routing sub-system and is assumed to be given. Flows and Classes of Service A series of continuous packets from a source to a destination router forms a ?ow. We assume that the ?ow is constrained by a leaky bucket at the edge router when it enters the domain. This edge router is called the ingress router to this ?ow. Following the DS model, ?ows are partitioned into classes. QoS requirement and speci?cations of the traf?c carried by the ?ows are de?ned on a class-by-class basis. The traf?c carried by ?ows in the same class has the same mathematical representation at the ingress routers, which is given as follows: De?nition 1 The source traf?c of a ?ow in Class i is controlled by a leaky bucket with parameters ?Ti ; ri ?. The total amount of traf?c, generated by this source during any time interval ?t; t ? I?, is bounded by minfC ? I; Ti ? r? Ig. i Here, the notations are:

*

Ti is the burst size of source traf?c of the ?ow in Class i. ri is the average rate of source traf?c of the ?ow in Class i. C is the link capacity.

*

*

UTILIZATION-BASED ADMISSION CONTROL

177

While the leaky bucket appropriately characterizes the source traf?c at the ingress router, this traf?c characterization is not valid within the networks, as the traf?c is perturbed by queueing delays at servers as it traverses the network. We use traf?c functions and their time independent counterpart traf?c constraint functions to characterize traf?c of any server in the network. De?nition 2 The traf?c function fi;k;j ?t? is de?ned as the amount of the traf?c of Class i arriving at Server k by the input link j during time interval ?0; t?. Traf?c functions are cumbersome to handle and not of much help in admission control, as they are time dependent. A time-independent traf?c characterization is given by the traf?c constraint function, which is de?ned as follows: De?nition 3 The function Fi;k;j ?I? is called the traf?c constraint function of fi;k;j ?t? if for any t 4 0 and I 4 0, fi;k; j ?t ? I? ? fi;k; j ?t? Fi;k; j ?I? ?1? The QoS requirement of ?ows is speci?ed on a class-by-class basis as well. To our purpose, we de?ne the deadline requirement of traf?c in Class i to be Di . As no distinction is made between ?ows belonging to the same class, all ?ows in the same class receive the same level of delay guarantees. In the following, we will use dk;i to denote the queueing delay suffered by Class i traf?c at Server k. Following the DS model, at each link server, certain percentage of bandwidth is reserved for individual traf?c classes. ai denotes the percentage of bandwidth reserved for Class i. It is the responsibility of the admission control to ensure that the bandwidth usage of individual classes does not go beyond the reserved portion. This is necessary to provide isolation among classes and hence to guarantee end-to-end delays to the ?ows in each class.

4. 4.1.

Scalable QoS Guaranteed System Overview

While our declared objective is to provide scalability for QoS guaranteed system, other aspects must be considered as well. In this section, we propose a methodology to provide QoS guaranteed real-time communication over a DS network with the following main objectives in mind: 1. Scalability: In our system, admission control and packet-forwarding scheme are scalable regardless of the number of ?ows in the system. This means that the overhead of admission control and packet forwarding is independent of the number of ?ows in the system.

178 2.

CHOI ET AL.

Effectiveness: Our admission control maximizes the bandwidth utilization to the extent possible. This means that it is highly accurate even though it does not rely on per-?ow information. The result is a system with high probability of admitting a new ?ow if resources are available. Compatibility: For practical purposes, our system is compatible with current industrial practice. We avoid modi?cations to communication infrastructure, such as the modi?cations to the architecture of routers, signaling protocols, or to the packet format, etc.

3.

While all these objectives are important and critical, they may con?ict with each other. For example, in order to improve scalability and reduce overhead, the admission probability may be compromised. On the other hand, using the existing link scheduling algorithms may limit our capability to improve the scalability. In our system, we adopt the class-based static priority algorithm to ensure the scalability in packet forwarding. We utilize off-line delay computation technology to reduce the overhead at admission control while keeping resources utilization and admission probability high. Our system consists of three major modules: 1. Off-line delay computation and veri?cation: Here, we use an ingenious delay calculation method to estimate the delay bound for every class at each router. This module veri?es whether the end-to-end delay bound in each feasible path of the network satis?es the deadline requirement as long as the bandwidth usage on the path is within a pre-de?ned limit. The module works during initial network con?guration, or during modi?cation of service level agreement among the communication service providers and their customers. Ef?cient admission control: As the delay has been veri?ed off-line, this module checks only if the bandwidth is available along the path of the new ?ow. Packet forwarding control: In a router, packets are transmitted according to their class priorities. Within a class, packets are served in FIFO order.

2. 3.

Before we describe the above modules in detail, we would like to introduce a delay computation formula. This formula will be used in the module for off-line delay computation and veri?cation. 4.2. Delay Computation

The worst-case delays on link servers in such systems depend on the number and traf?c characteristics of ?ows competing for the server. Inside the network, the traf?c characteristics of a ?ow at the input of a link server depends on the amount of contention experienced upstream by that ?ow. Intuitively, all the ?ows currently established in the

UTILIZATION-BASED ADMISSION CONTROL

179

network must be known in order to compute delays when no ?ow separation is provided. Delay formulas for this type of systems have been derived for a variety of scheduling algorithms (Li et al., 1997). While such formulas could be used (at quite some expense) for ?ow establishment at system run-time, they are not applicable for delay computation during con?guration time, as they rely on run-time information about ?ows. Hence, the worst case delays must be determined under the assumption of the worst-case combination of ?ows has been established. An obviously impractical way to do that is to exhaustively list all possible combinations of ?ows in the system and compute the delays on the link servers for the every possible combinations to get the worst case delays. Fortunately, we can derive an upper bound on the worst-case delay without having to exhaust all the ?ow combinations. In this section, we will describe such a method for the case of class-based static priority scheduling at the link servers. We will start with a formula for delay computation that depends on ?ow information, which we call general delay formula. We will focus on how to remove its dependency on ?ow information. General delay formula Consider Server k, which at some time moment has ni;k;j Class i traf?c ?ows through its Input Link j. Let Fi;k;j ?I? be the constraint function for the aggregated traf?c belonging to Class i on Input Link j of Server k. This constraint function can be formulated as the sum of the constraint functions of the individual ?ows using Input Link j, that is, Fi;k;j ?I? ?

ni;k;j ? m?1

Hi;k;j;m ?I?

?2?

where Hi;k;j;m ?I? is the constraint function for the m-th ?ow in Class i on Input Link j of Server k. The worst case delay, di;k , can then easily be formulated in terms of the aggregated traf?c constraint functions and the service rate C of the server as follows (Li et al., 1997): 2 3 i?1 N N ?? ? 1 di;k ? max F ?I ? di;k ? ? Fi;k;j ?I? ? C ? I ?3? C I>0 l ? 1 j ? 1 l;k;j j?1 Substituting (2) into (3), we observe that the above delay formula depends on the dynamic system status, that is, ni;k;j , the numbers of ?ows at each input link and Hi;k;j;m , the traf?c constraint function of the individual ?ows. This kind of dependency on the dynamic system status must be removed in order to perform delay computations at con?guration time. We will describe below how we ?rst eliminate the dependency of the delay formula on the traf?c constraint function Hi;k;j;m ?I?. Then we eliminate the dependency on the numbers of ?ows on each link, that is, ni;k;j . Removing the dependency on Hi;k;j;m , the constraint function of the individual ?ows In the following theorem, we show that the aggregated traf?c function Fi;k;j ?I? can

180

CHOI ET AL.

be bounded by replacing the individual traf?c constraint functions Hi;k;j;m ?I? by a common upper bound Hi;k ?I?, where Hi;k ?I? is de?ned to be the traf?c constraint function of the ?ow in Class i experiencing the longest delay upstream from Server k. THEOREM 1 The following inequality holds: Fi;k;j ?I? ni;k;j ? Hi;k ?I? ?4?

for j ? 1, . . . , N, where Hi;k ?I? can be formulated as follows: Hi;k ?I? ? minfC ? I; Ti ? ri ? Yi;k ? ri ? Ig where Yi;k ? max

Path [ Si;k

?5?

?

j [ Path

di;j

?6?

and where Si;k is the set of all paths upstream from Server k for ?ows that traverse Server k. A proof of Theorem 1 is given in Appendix A. According to Theorem 1, the general delay formula in (3) can be re-formulated as: di;k 2 3 i?1 N N ?? ? 1 ? max n ? Hl;k ?I ? di;k ? ? ni;k;j ? Hi;k ?I? ? C ? I C I>0 l ? 1 j ? 1 l;k;j j?1

? di;k

?7?

Computing delays by using (7) still depends on the number of ?ows on each input links. Next, we describe how to remove this dependency. Removing the dependency on ni; k; j , the numbers of ?ows per input link As we described earlier, admission control at run-time makes sure that the link utilization allocated to each class of ?ows is not exceeded. The number of ?ows on each input link is therefore subject to the following constraint:

N ? j?1

ni;k;j

ai C ri

?8?

Under this assumption, the delay bound in (7) can be maximized for all the possible distribution of ni;k;j , as the following theorem shows: THEOREM 2 The delay in (7) is maximized when $ % ai C maxfni;k;1 ; ni;k;2 ; . . . ; ni;k;N g ? ri N

?9?

A proof of Theorem 2 is given in Appendix B. This theorem states that when the maximum value of ni;k;j is dai C=ri N e, the bound of ?? the delay di;k is maximized. In fact, the theorem is consistent with the intuition that when

UTILIZATION-BASED ADMISSION CONTROL

181

the ?ows distribute evenly among the input links, the delay of the server will be maximized. Using the above results, we have the following theorem: THEOREM 3 The delay di;k is bounded as follows: ? ?i a ?Ti ?ri Y ? i a ?Tl ? rl ? Yl;k ? rl ? al ? 1 ir ?N?a i;k l?1 l?1 i? l i di;k ? ?i ? 1 1 ? l ? 1 al

?10?

A proof of Theorem 3 is given in Appendix C. The right-hand side of (10) does not depend on any parameters related to dynamic system status. Hence, this formula can be used for delay computation at con?guration time. Con?guration-time Delay Computation Procedure In order to simplify notations, we ~ use vector d to denote the upper bounds of the queueing delays suffered by the traf?c of class i at all servers:

b ~ di ? ?di;1 ; di;2 ; . . . ; di;jSj ?

?11?

We note that, in (10), di;k depends on Yi;k . Then, according to (6), the value of Yi;k , in turn, depends on the delays experienced at servers other than Server k. In general, we ~ ~ have a circular dependency, as di depends on Yi;k , and Yi;k depends on d i . Hence, the values of di;k , k ? 1, . . . , jSj depend on each other and must be computed simultaneously. Let us de?ne: ? ?i ai ?Ti ?ri Yi;k ? i al l ? 1 ?Tl ? rl ? Yl;k ? rl ? l ? 1 al ? 1 ri ?N?ai ? ~ zi;k ?d i ? ? ?12? ?i ? 1 1 ? l ? 1 al and ~ ~ ~ ~~ Z?d i ? ? ?zi;1 ?d i ?; zi;2 ?di ?; . . . ; zi;jSj ?d i ??b ?13? ~ The queuing delay bound vector d can then be determined by the following vector equation: ~ ~~ di ? Z?di ? ?14? ~ Since the unknown vector di appears on both sides of (14), an iterative procedure is ~ needed to compute d i .

4.3.

Off-line End-to-end Delay Computation and Veri?cation

Equation (14) provides a means to compute the worst-case delay experienced by any ?ow in a given network, as long as the portion of bandwidth allocated to the individual classes are not exceeded. We can directly make use of this to verify off-line whether the network with the given bandwidth allocation of service classes satis?es all the delay requirement of the classes. If this is the case, admission control during ?ow establishment is limited to

182

CHOI ET AL.

simply check whether enough bandwidth is available on the links along the path of the ?ow. An actual delay analysis during ?ow establishment is then not necessary anymore. A work-?ow representation of the algorithm for the off-line delay computation and veri?cation is given in Figure 2. The inputs of the algorithm are de?ned as follows: ai : The portion of link bandwidth assigned to the traf?c of Class i. Ti : The burstiness of the traf?c of a ?ow of Class i at the ingress routers. ri : The average rate of traf?c of a ?ow of Class i. Di : The delay requirement of ?ows in Class i.

Figure 2. Algorithm for off-line delay computation and veri?cation.

UTILIZATION-BASED ADMISSION CONTROL

183

P_Set: The set of all possible paths that can be taken by ?ows. This is determined by the network topology and the routing policy. L: Number of classes. The algorithm consists of two nested loops. The outer loop traverses all the classes in the order of decreasing priority. For each Class i, the algorithm computes the delays on all servers, using the fact that lower-priority classes do not affect the transmission for ?ows in Class i, and that delays of higher priority classes have already been computed. The inner loop computes the delays for traf?c in Class i by iterating in Step 4 ?h is the ~ iteration counter? until either the values of the delays in di converge or it can be safely concluded that the delay requirement for Class i cannot be met. In Step 3, the recursive formula of Equation (7) for delay computation is called to ~ ~ calculate di?h ? 1? based on d i?h? , until the maximum end-to-end delay as computed by Function G( ? ) is larger than the delay requirement Di of ?ows in Class i (Step 4), or until the computation of delays has converged (Step 5).3 Function G( ? ) computes the worst-case end-to-end delay that can be experienced by ~ any ?ow of Class i in the system, given d i?h?1? and the route information. This can be ~ done, for example, by summing up and comparing the local delays in di?h?1? for the link servers along any possible paths used by ?ows in Class i. If Function G( ? ) returns a delay larger than Di , there is at least one route along which the delay requirement for Class i traf?c can not be guaranteed. In that case, the algorithm returns FAIL to report that the veri?cation of the end-to-end delay did not succeed. In this case the network needs to be recon?gured, for example, by changing the routing policy, or by re-allocating portion of link bandwidths to classes. If the delay computation converges, the delay computation for Class i is ?nished, and the algorithm proceeds to compute the delays for the class with the next lower priority. If the delay of all the classes traf?c is calculated, the outer loop terminates, and the algorithm returns SUCCESS, which indicates that the algorithm was successful in verifying that the delay requirements for all classes can be met. The correctness of the algorithm is given by the following two theorems. THEOREM 4 The algorithm for the off-line end-to-end delay computation and veri?cation will terminate. This theorem guarantees the work ?ow will not loop in?nitely. Since the number of classes ?L? is limited, the outer loop will execute a ?nite numbers of times. Thus we need to only prove that inner loop for computing delays for classes i will stop after some ?nite number of iterations. The proof of this theorem is in Appendix D. THEOREM 5 If the algorithm returns SUCCESS, the end-to-end delay will be guaranteed for any new request as long as enough bandwidth is available along the path of the ?ow. Proof of Theorem 5 This theorem follows directly from the algorithm. If the theorem is untrue then there will be one path, along which the end-to-end delay for one class (say Class i) is larger than its deadline Di under the condition that the bandwidth is available

184

CHOI ET AL.

for for Class i. However, according to the condition in Step 4 of the algorithm, the algorithm must return FAILURE. j Once the algorithm has determined that end-to-end deadlines are met for all classes, the delay requirement need not to be checked anymore during the establishment of new ?ows. Note that the algorithm runs at network (re-)con?guration, not during network operation. The run time overhead of the admission control is therefore reduced considerably, as opposed to systems at establishment time delay calculation, and hence the scalability of admission control is signi?cantly improved. 4.4. Admission Control

During ?ow establishment, an admission control procedure must make sure that the QoS requirements for the new ?ow (in our case these are delay requirements) can be satis?ed under the current network load, and that the network resources are not over-committed. If the network con?guration has been previously veri?ed off-line to meet the delay requirements of all classes for the given bandwidth allocation to classes, the admission control procedure is signi?cantly simpli?ed: We showed in Theorem 5 that no ?ow will miss its delay requirements as long as no bandwidth allocation of a class is exceeded. In other words: as long as the bandwidth allocated to a Class i does not exceed ai on any link, every ?ow meets its deadline requirements. The admission control procedure during ?ow establishment of a ?ow in Class i only needs to check whether admitting the new ?ow would keep the bandwidth used for Class-i traf?c at or below ai on every link on the path of the new ?ow. 4.5. Packet-Forwarding Scheme

The delay formula assumes the usage of a class-based static priority scheduling policy at the link servers, in which each class has its own FIFO queue. We do not rely on any form of traf?c shaping in the link server. Note that while this signi?cantly complicates delay calculation, it keeps the packet forwarding mechanism extremely simple. Class-based static priority scheduling integrates well with the DS architecture, as the priority of a packet can be de?ned in the speci?c ?eld type of service (TOS) of the IP packet heads by the ingress router when the packet enters a domain (Blake et al., 1998). This ?eld is used for packet forwarding by the core router. 5. Experimental Evaluation

In order to evaluate the performance (in terms of admission probability and of admission control overhead) of our class-based approach, we ran a suite of simulation experiments to compare it with two forms of connection oriented admission control systems: (1) NetEx (Devalla et al., 1997; Sahoo et al., to appear) has been selected as a generic

UTILIZATION-BASED ADMISSION CONTROL

185

connection oriented admission control with static priority system packet forwarding. This allows to study the effect of a connection admission control mechanism that relies on detailed delay computations of individual connections versus the new utilization-based admission control with the same packet-forwarding scheme. (2) Virtual Clock (Zhang, 1991; Figueira and Pasquale, 1995) has been selected in order to study whether there is any difference in using a guaranteed-rate scheduling policy such as VC as opposed to a simple class-based policy, such as class-based static priority scheduling. For VC, we use an utilization-based admission control mechanism. In these experiments, we compare admission probability and run-time overhead of the three systems. Figure 3 shows the topology of the MCI ISP backbone network, which we use throughout the experiments. In the experiments, all routers can act as edge routers. Following common practice, we rely on a separate routing subsystem to determine the paths of ?ows. As routing should not affect the result, we use a shortest-path routing policy throughout the experiments. We simulate the admission control behavior in the system by simulating ?ow requests and establishments at varying rates with a constant average ?ow lifetime. Requests for ?ow establishment form a Poisson process with rate l, while ?ow lifetimes are exponentially distributed with an average lifetime of 180 seconds for each ?ow. Source and destination edge routers are chosen randomly and the ?ow is set up along the shortest path. We consider a system with two classes. One is real-time class. Another is non-real-time class. We assume that all ?ows in the real-time class have a ?xed packet length of 640 bits (RTP, UDP, IP headers and two voice frames) (Kostas et al., 1998), and a ?ow rate of 32 Kbps. The end-to-end delay requirement of all ?ows is ?xed at 100 ms.4 Thus, the input traf?c of each ?ow is constrained by a leaky bucket with parameters T ? 640 bits and r ? 32 Kbps. This kind of QoS requirements is similar to ``Voice-over-IP'' (Borgonovo et al., submitted). All links in the simulated network have the same capacity of 10 and 100 Mbps. Our experiments have shown that the results for 100 Mbps scale linearly with higher link capacity (e.g., 155, 622 Mbps and 1 Gbps). We show the results

Figure 3. Simulation network topology.

186

CHOI ET AL.

for the NetEx approach for 10 Mbps only, as its overhead on a loaded 100 Mbps system would be too high. The admission control for the VC system is relatively simple. With a VC system, the delay bound at a server is tightly coupled with the bandwidth reserved. We assume that the admission control in the VC system allocates suf?cient but not excessive bandwidth to a ?ow so that both delay and bandwidth requirements of the ?ow are met. Figures 4 and 5 show the admission probabilities for the real-time class in the three cases as a function of ?ow arrival rates. The graphs show the results of two experiment

Figure 4. Admission probability comparison over 10 Mbps links (a) a ? 0.1; (b) a ? 0.35.

UTILIZATION-BASED ADMISSION CONTROL

187

Figure 5. Admission probability comparison over 100 Mbps links (a) a ? 0.1; (b) a ? 0.35.

runs with different amounts of bandwidth allocated to the real-time class traf?c. In the ?gure, ``VC_10'' means the VC admission probabilities with a ? 0.10, so does ``VC_35'' with a ? 0.35. By the same rule, ``DS_10'' stands for DS with a ? 0.10, and so on. So, the curves in Figures 4(a) and 5(a) are for the case of 10% bandwidth allocation for the real-time class traf?c, and the ones in Figures 4(b) and 5(b) for the case of 35%. As it should be, with larger bandwidth allocated to the class, we get higher admission probabilities. The practical meaning of l ? 20 is that an average of 20 ?ows

188

CHOI ET AL.

arrive at the system per second. Since the average lifetime of the ?ow is 180 seconds, we have 3,600 ?ows on average in the simulation system with l ? 20. As can be seen, the admission probabilities of all three systems are almost identical. The reason for the similarity of the results for the class-based system and the NetEx system lies in the fact that we limit the amount of bandwidth allocated to the real-time class, while NetEx can use connection information to compute tighter delay bounds, mostly this does not come into play, as the ?ow is rejected earlier due to lack of available (allocated) bandwidth. The reason for the similarity of the results for the VC system and the class-based system is again because the admission decision reduces to checking the availability of allocated bandwidth for the class. For ?ows with longer paths, the admission probability in the VC system is actually worse. This is due to the delay-bandwidth coupling of VC scheduling: in order to meet tighter deadlines VC requires more bandwidth. Because the establishment of some ?ows using the VC system requires more bandwidth than the class-based system, as the arrival rate increases, the class-based system scheduling outperforms the VC. For a link with eight hops for example, the VC system needs roughly 1.6 times more bandwidth than the class-based system. In this way allocated bandwidth gets used up quite quickly, and admission probability suffers. These experimental results show that our utilization-based approach provides admission probabilities that are very similar to those of approaches with signi?cantly more expensive packet-scheduling and admission control mechanisms. The comparison with NetEx as a system with a similar packet scheduling policy shows that a connectionoriented admission control scheme brings little to no bene?t over a class-based scheme. In addition, the comparison with the VC system illustrates how the use of a connection oriented scheme and a sophisticated guaranteed-rate scheduling policy brings no bene?t over a simple class-based scheme. We measured the run time overhead in admission control for comparison. Figure 6 shows average run time overhead values in msec with three different l values for the three systems. As can be seen, the class-based system is the smallest overhead. VC's and our overhead are close, as they both are utilization-based approaches. Our admission control of the class-based system checks only if there is enough available bandwidth for the new request, while VC's admission control computes the required bandwidth to meet the prede?ned end-to-end delay. So the difference is just for new bandwidth calculation in VC. However, since both systems do not check the state of each ?ow, their overhead is much smaller than that of NetEx. This is because NetEx calculates the end-to-end delay bounds of all existing ?ows whenever a new request arrives. While the admission overhead for the class-based and the VC system remain constant with increasing system load, overhead of the NetEx system grows linearly with the number of connections in the system. (Note that the overhead of NetEx' admission control is due to the fact that NetEx does not rely on guaranteed-rate schedulers, and hence, can not rely on ?ow isolation. This makes the admission control signi?cantly more expensive. The great bene?t of our new utilization-based admission control is that it signi?cantly streamlines admission control without having to rely on ?ow isolation.) This data illustrates that the class-based system outperforms both the VC and NetEx systems in terms of run time overhead of admission control.

UTILIZATION-BASED ADMISSION CONTROL

189

Figure 6. Run time overhead for three cases with two link capacities (a) 10 Mbps; (b) 100 Mbps.

6. 6.1.

Implementation Motivation

The experimental results demonstrate that the proposed class based scheme is competitive with connection-oriented schemes when it comes to network utilization. In addition, they indicate that admission overhead during ?ow establishment is very low. Given this encouraging results, we proceed to design and implement the proposed system

190

CHOI ET AL.

as part of a DS architecture. Recall that our system consists of three modules: off-line delay computation and veri?cation, admission control, and packet forwarding. These modules have two basic requirements: ?rst, the incoming traf?c is constrained by a leaky bucket at the edge router; second, both the edge routers and the core routers provide a class-based static priority scheduling police at output links.

6.2.

PowerRail Routing Switch

We use PowerRail routing switches produced by Packet Engines in our implementation. The PowerRail Switch is a gigabit switch and provides many capabilities including multiple QoS queues, TOS-based routing, etc. The switch has 8 different classes of service queues per output port, and three different ways of servicing and scheduling packets from these eight queues: FIFO, STARVE (static priority) and WFQ. The PowerRail switch provides a series of offset mask ?lters (OMF) on each port which the switch uses to ?lter, count, prioritize, or redirect frames. The OMF operates based on the policies set by the administrator. These policies can apply offset mask ?ltering to a speci?c application. Of interest to us is that the PowerRail switch provides class-based (up to eight classes) static priority scheduling. Also, it provides a series of ?lters, which can be used to constrain incoming traf?c. Hence, the switches are well suited to act as the edge and core routers.

6.3.

Architecture

Figure 7 illustrates the architecture of proposed system based on the PowerRail switches. For each domain, we designate a domain resource manager (DRM), which is performed after the bandwidth broker in Nicols et al. (1997). The DRM has access to the whole domain topology and link capacity information. It performs the off-line delay computation and veri?cation as well as admission control. The off-line delay computation and veri?cation is performed during initialization of the network, or during the modi?cation of SLAs between the service provider and its customers. In our implementation, both the edge and core routers are PowerRail routing switches. In addition to forwarding packets, the edge routers participate in the ?ow establishment. They are responsible for communicating with the DRM. For communication between edge routers and the DRM, we use the policy client-server protocol, such as COPS (Boyle et al., 1999). Messages for ?ow establishment and teardown can be handled on a besteffort basis. Alternatively, network resources can be set aside to such messages by de?ning a separate class of service. Upon receiving a ?ow admission request, the ingress router forwards it requests to the DRM. The DRM invokes its admission control function, and sends a policy (e.g. the admission decision and traf?c shaping policing parameters) to the edge router. The edge router will set the policies on the appropriate port via the policy-set interface.

UTILIZATION-BASED ADMISSION CONTROL

191

Figure 7. The architecture of proposed system.

Once the ?ow is admitted, the edge routers will appropriately ?lter the incoming traf?c according to the policies just set. For each packet passing through the ?lter, the priority is marked in the TOS ?eld in the packet header and the packet is forwarded to the appropriate output links. Core routers then honor the priority in their packet forwarding scheduling. The information maintained in the DRM is limited to one counter for each class per link server in the domain, requiring very little memory storage. Also, the admission control procedure in the DRM only needs to check the bandwidth usage along the path of the ?ow in its local database, making the run time overhead very low. Based on this consideration, we believe that the DRM will not be a bottleneck for the performance of network. In cases where the number of ?ow establishment and teardown requests is very high, a hierarchical approach can be used. In such an approach, the admission decision could be delegated to ingress routers by appropriately pre-assigning resources. By delegating the admission control to ingress routers, the number of signaling messages would be signi?cantly reduced and the computation load of the admission control procedure would be shared across ingress routers.

7.

Conclusions

We have described a methodology for applying utilization-based tests to determine schedulability or admission in a network of servers. As the driving model in this paper, we have chosen the Differentiated Services (diffserv) architecture. The result is a scalable methodology for providing QoS-guaranteed services within a DS architecture. To the best of our knowledge, this is the ?rst approach to guarantee real-time services with ?ow aggregation and no connection awareness in core routers thus achieving much lower complexities in admission control and packet forwarding.

192

CHOI ET AL.

We achieve this by determining safe utilization levels off-line, which allows to reduce the overhead at admission control while keeping admission probability and resource utilization high. Indeed, our evaluation data shows our system's admission probabilities are very close to those of signi?cantly more expensive approaches. At the same time, admission control overhead during ?ow establishment is very low. Our results therefore support the claim from the DS architecture literature that scalability can be achieved through ?ow aggregation without sacri?cing resource utilization and with signi?cant reduction in run time overhead. We paid particular attention to the compatibility with the existing DS architecture. We are currently proceeding to design, implement, and deploy the proposed methodology with a DS capable IP network to further illustrate its easy deployability. The algorithm described in Section 4.3 veri?es whether a given bandwidth allocation guarantees deadline requirements for ?ows of all classes. If this veri?cation fails (that is, deadline requirements for some classes of ?ows on some paths may be violated), a ``better'' bandwidth allocation has be found and the veri?cation step repeated. A simple but effective method would be to use binary search in order to ?nd a bandwidth allocation that satis?es the requirements of all traf?c classes. More sophisticated methods for bandwidth allocation can be used if appropriate support in the routers and switches is available. For example, if routers can be con?gured off-line so that the paths taken by traf?c is known during at con?guration time, the delay formulas in Section 4.2 can be signi?cantly improved (Dong et al., 2000). Similarly, if switches and routers are able to handle class descriptors independently from priority descriptors, and the class-based schedulers can make scheduling decisions based on class and priority descriptors, the delay formulas can again be improved, thus allowing for higher resource utilizations. For many applications, deterministic guarantees are not necessary (Zhang et al., 1995). The quality of IP telephony, for example, would not suffer from the underlying system providing high-quality statistical instead of deterministic guarantees. We are therefore investigating how to extend our off-line computation of safe utilizations to allow for statistical guarantees.

Appendix A.

Proof of Theorem 1

Recall that Hi;k;j;m ?I? is the traf?c constraint function of ?ow m of class i at Input Link j of Server k. As we assume that at their sources, ?ows in the same class have the same constraint functions Hi ?I?, that is, Hi ?I? ? minfC ? I; Ti ; ? ri ? Ig ?15? Let Yi;k;j;m be the total worst case queuing delay experienced by the packets from this ?ow before arriving at Server k. Recall that Yi;k is the maximum of the worst case queuing delay suffered by any ?ow in class i before arriving at Server k. That is, Yi;k;j;m Yi;k ?16?

UTILIZATION-BASED ADMISSION CONTROL

193

According to Theorem 2.1 in Cruz (1991a), and using (5), (15) and (16), we have Hi;k;j;m ?I? Hi ?I ? Yi;k;j;m ? Hi ?I ? Yi;k ? ? Hi;k ?I? ?17?

That is, the traf?c constraint functions of individual ?ows are bounded by Hi;k ?I? that is the traf?c constraint function of the ?ow which experience the largest delay before arriving at Server k. By substituting (17) into (2), we have Fi;k;j ?I?

ni;k;j ? m?1

Hi;k ?I? ? ni;k;j ? Hi;k ?I?

?18? j

Thus, (4) holds.

Appendix B.

Proof of Theorem 2

Before we formally prove Theorem 2, we need some lemmas. Lemma 1 The aggregated traf?c of Class i on Input Link j of Server k Fi;k;j ?I? ? ni;k;j ? Hi;k ?I? can be expressed as follows: & C ? I; Fi;k;j ?I? ? ni;k;j ? Ti ? ni;k;j ? ri ? Yi;k ? ni;k;j ? ri ? I; where ti;k;j ? ni;k;j ? Ti ? ni;k;j ? ri ? Yi;k C ? ni;k;j ? ri ?21? ?19?

I ti;k;j I > ti;k;j

?20?

Sketch of Proof of Lemma 1 This Lemma can be proved by substituting (5) into (19), and then Fk;j ?I? can be rewritten in the segmented form. The following Lemma gives the new format of di;k originally in (7): Lemma 2 ?i di;k ?

l?1 a ?Tl ? rl ? Yl;k ? rl ?

l

?

1?

?i ? 1

l?1

i l?1

al ? 1 maxN? 1 fti;k;j g j

al

?22?

194

CHOI ET AL.

Sketch of Proof of Lemma 2 With some algebraic manipulations (Li et al., 1997) on (7), we can have ? ? ?i ?N i ?Tl ? rl ? Yl;k ? N? 1 nl;k; j ? rl nl;k;j ? C maxN? 1 fti;k; j g j l?1 j l?1 j?1 di;k ? ?i ? 1 1 ? l ? 1 al C ?23? As we know

N ? j?1

ni;k;j

ai C ri

?24?

Substituting (24) into (23), we have: ?i di;k

l?1

? i N l ?Tl ? rl ? Yl;k ? arC ? l ? 1 al ? 1 C maxj ? 1 fti;k; j g l ? 1 ? il ? 1 al C ?1 ? ?i i a ?Tl ? rl ? Yl;k ? rl ? al ? 1 maxN? 1 fti;k; j g j l?1 l?1 l ? ?i ? 1 1 ? l ? 1 al

?25? j

Now, we are ready to prove Theorem 2. Proof of Theorem 2 Observing (22), we notice that the delay only depend on ti;k; j (as ? we know, ti;k; j is a function of ni;k; j ). Since ? il ? 1 al ? 1? is negative, to maximize the worst case delay, we need to get the minimum value of maxN? 1 ?ti;k; j ?. For this purpose, j we denote T?ni;k;1 ; ni;k;2 ; . . . ; ni;k;N ? ? max fti;k; j ?ni;k; j ?g

j ? 1;...;N

?26?

where ti;k;j is de?ned in (21). Recall that ai is the portion of bandwidth of each server reserved for traf?c of Class i. Let M be the total number of the ?ows of Class i supported by Server k. That is, M?

N ? j?1

ni;k; j

ai C ri

?27?

Substituting (21) into (26), we have T?ni;k;1 ; . . . ; ni;k;N ? ? max fti;k; j ?ni;k; j ?g j ? 1;...;N @ A ni;k; j ?Ti ? ri Yi;k ? ? max j ? 1;...;N C ? ni;k; j ? ri

?28?

UTILIZATION-BASED ADMISSION CONTROL

195

Because f ?x? ?

x?Ti ?ri ?Yi;k ? C ? xri

is a monotonically increasing function of variable x, we have n? ?Ti ? ri ? Yi;k ? i;k C ? n? ri i;k ?29?

T?ni;k;1 ; . . . ; ni;k;N ? ?

where n? ? maxfni;k;1 ; . . . ; ni;k;N g. Without loss of generality, in the rest of this proof, we i;k assume that ni;k;1 ? ? ? ni;k;N ? n? . i;k Now, we would like to show that if a sequence of integers ni;k;1 ; ni;k;2 ; . . . ; ni;k;N , satis?es

N ? j?1

ni;k; j ? M

?30?

and minimizes T?ni;k;1 ; ni;k;2 ; . . . ; ni;k;N ?, then $ % M n? ? i;k N

?31?

Let us assume that this is not true. That is, (3) does not hold. We have three cases to deal with.

*

Case 1: n? 5dMe. That is n? ?M?. We have i;k i;k N N " # N ? M ni;k; j Nn? N 5M i;k N j?1 This is impossible either in accordance with (30).

?32?

Case 2: n? > dMe. Now let us consider another sequence of integers i;k N ^ ^ ^ ni;k;1 ; ni;k;2 ; . . . ; ni;k;N , where @? ? M 1 j K; N ; ^ ni;k; j ? ?M? ?33? K5j N; N ; ? ^ where K ? NdMe ? M. It is easy to verify that N? 1 ni;k; j ? M and j N

*

^ ni;k;N ?Ti ? ri ? Yi;k ? n? ?Ti ? ri ? Yi;k ? i;k 5 C ? n? r i C ? ni;k;N ri i;k

?34?

This is a contradiction because the sequence ni;k;1 ; . . . ; ni;k;N is supposed to minimize T?ni;k;1 ; . . . ; ni;k;N ?. Hence, (31) holds. Recall that to maximize the worst-case delay (22), we need to maximized n? . n? is maximized when M is maximized, which gives i;k i;k M? ai C ri ?35? j

The theorem then follows.5

196 Appendix C. Proof of Theorem 3 ?N

j?1

CHOI ET AL.

Following Theorem 2, we have, if

nk; j ? M,

?M ? ?Ti ? ri ? Yi;k ? ? ? T?ni;k;1 ; ni;k;2 ; . . . ; ni;k;N ? ! N C ? M ri l m N 1 ai C N ri ?Ti ? ri ? Yi;k ? l m ? 1 i C ? N arC ri

i

! ?

1 ai C N ri ?Ti

? ri ? Yi;k ?

ai C ri ri

1 C?N

ai ?Ti ? ri ? Yi;k ? N ? ai ri

?36?

Substituting (36) and (26) to (22), we have: ?i di;k ?

al l ? 1 ?Tl ? rl ? Yl;k ? r ?

l

?

? 1 ? il ? 1 al ?1 a T ?r Y ? a ?i ?i ? ? ? ? l Tl ? rl Yl;k r ? al ? 1 i r ?i N ?ia i;k l?1 l?1 i? l i ? 1 ? il ? 1 al ?1

i l?1

al ? 1 maxN? 1 fti;k;j g j

?37? j

Appendix D.

Proof of Theorem 4

We need to establish a lemma before proving the theorem. Lemma 3 In an execution of the off-line delay computation and veri?cation algorithm shown in Figure 2, ~?h ? 1? ! d ?h? ~ di i where h ! 0 and i ? 1, . . . , L. Proof of Lemma 3 We prove this lemma by induction. ?38?

UTILIZATION-BASED ADMISSION CONTROL

197

According to the algorithm P Q 0 T0U T.U ~?0? T . U di ? T . U T.U R.S . 0 and U T ~?0? U P Q T z d ? U T i;1 i U T ?i 0 U U T l ? 1 Tl rl? T ~ U T0U T zi;2 d ?0? U T ? i U T.U U T T 1? U T . U ~?0? U T T ~ ~?0? . ? Zi d i ? T U ! T . U ? di U?T . . U T.U U T T . . . U R.S U T T . . U T . U T . . . S T R 0 ??.i ? aT U ?0? U T ?i ~ a i i zi;M d i S R l ? 1 Tl rll? a ?1 l?1 l ri? N ? ai? ?i ? 1

1?

l?1

?39?

P

Q

P ?i

l?1

Tl rl?

l

a

? ?i

? 1? ?? al

~?1? di

ai T i a ?1 l?1 l ri? N ? ai? i?1 a l?1 l i ai T i al ?1 l?1 ri? N ? ai? i?1 a l?1 l

?

Q

?40?

al

~ where zi;k and Z i are de?ned in (5) and (6), respectively. ~?0? d ?1? ? ? ? d ?h? , we need to show d ?h? d ?h ? 1?. Note that, by ~ ~ ~ ~ Assuming that d i i i i i ~ ~ ~ its de?nition, Y i;k is an increasing function of di . That is, if d i?h? ! d i?h ? 1? , ~ ~ Yi;k ?d i?h? ? ! Yi;k ?d i?h ? 1? ?. Furthermore, we observe ?i ai qzi;k ai ? ? l?1 al ? 1? N ? ai ? !0 ? qYi;k 1 ? il ? 1 al ?1 ?41?

Thus, zi;k is an increasing function of Yi;k . Synthesizing the monotonic properties of zi;k and Yi;k , which are observed above, we ~ ~ ~?h? ~?h ? 1? , conclude that zi;k ?di ? is an increasing function of di . Thus, if d i ! d i ~?h? ~?h ? 1? zi;k d i ! zi;k d i ?42? Now, following the algorithm, we have

Q P Q ~?h? ~?h ? 1? zi;1 d i zi;1 d i T U T U T U T U ~ ~ T zi;2 d ?h? U T zi;2 d i?h ? 1? U i U T U T T U T U ~ ~?h ? 1? ~?h? ~ ~?h? . . ? di ? Zi d i ? T U!T U ? Zi d i . . T U T U . . T U T U . . T U T U . . . S R . S R ~?h? ~?h ? 1? zi;M d i zi;M d i P

~?h ? 1? di

?43?

j

198 Appendix E. Proof of Theorem 4

CHOI ET AL.

We prove this theorem by a contradiction. Assume that the inner loop of the algorithm iterates in?nitely. If this is the case, from Lemma 3, we know ~?0? di ~?1? di ~ kd i

?h ? 1?

~?2? di ~ ?di k

?h?

??? ~ kd i

~?h? di

?h ? 1?

??? ~ ?di k

?h?

?44?

Since the algorithm iterates in?nitely, we know, for h 4 1, e5 That is, ~ kd i

?h ? 1?

~ kd i

?h ? 1?

k

?1?

~ kd i k

?1?

?45?

~ ~ ? d i k ! ekd i k > 0

?h? ?h? ?h ? 1?

?46?

?1?

Therefore, we can ?nd kh ; h ? 2; 3; . . . ; such that di;kh

?h ? 1?

~ ? d i;kh ? kd i

~ ~ ? d i k ! ekd i k

?h?

?47?

where 1 kh M. Then we can ?nd a server k and a sequence of integers h1 5h2 5 ? ? ? 5hn 5 ? ? ? such that ~ ekd i k

?1?

?48?

di;kn ? 1 ? di;kn

?h

?

?h ?

?49?

Hence, we have

?h ? lim d n n?? i;k

??

?50?

Equation (50) implies, for a given Di , there is an X 4 0 so that when n 4 X di;kn > Di However, by the algorithm, ?h ? ~?h ? di;kn G d i n ; P Set

?h ? ?h ?

?51?

Di

?52? j

~ where G?d i n ; P Set? is de?ned in Section 4.3. This is a contradiction.

Notes

1 In the following, we will use the term ?ow to indicate a stream of data between a source and a destination, and the term connection to indicate the virtual circuit that needs to be established to carry the ?ow. 2 In this paper we use aggregated ?ow and class interchangeably. 3 k?d1 ; . . . ; dn ?b k ? maxn? 1 jdi j. i

UTILIZATION-BASED ADMISSION CONTROL

199

4 In a real situation this value is not correct, as we only consider queueing delay for end-to-end delay deadline. There are many other factors like propagation delay, Codec (Coder and Decoder) delay or others we do not know now. More accurate values can be found in (Kostas et al., 1998). We use this value just for reference. With other values, we would see similar results. i 5 In general, arC is not necessarily an integer. However, in a modern practical system ai ? C is very large in i comparison with ri . For example, if we consider a gigabit router, C ? 109 bits=sec. For voice traf?c 4 i r ? 3:2610 bits=sec, if ai ? 15%, arC ? 4687:5. Therefore, in order to simplify notation, we assume that i ai C ai C ? r ?& r .

i i

References

Banerjea, A., and Keshav, S. 1993. Queueing delays in rate controlled ATM networks. Proceedings of Inforcom'93. Bennett, J., and Zhang, H. 1996. WF2 Q: worst-case fair weighted fair queueing. Proceeding of IEEE INFOCOM'96. Bernet, Y. et al. 1999. A framework for differentiated services. Internet-Draft, IETF, Feb. Bettati, R., Ferrari, D., Gupta, A., Heffner, W., Howe, W., Moran, M., Nguyen, Q., and Yavatkar, R. 1995. Connection establishment for multiparty real-time communication. In Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, Durham, New Hampshire. Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z., and Weiss, W. 1998. An architecture for differentiated service, RFC 2474, Dec. Borgonovo, F., Capone, A., Fratta, L., and Petrioli, C. (submitted) End-to-end call admission control for telephony services over IP networks. IEEE Network and IEEE Internet Computing Joint Issue. Boyle, J., Cohen, R., Durham, D., Herzog, S., Rajan, R., and Sastry, A. 1999. The COPS (Common Open Policy Service) Protocol. Internet-Draft Feb. Braden, R., Clark, D., and Shenker, S. 1994. Integrated services in the internet architecture. RFC 1633, June. Cruz, R. L. 1991a. A calculus for network delay, Part I: Network elements in isolation. IEEE Transactions on Information Theory, 37: Jan. Cruz, R. L. 1991b. A calculus for network delay, Part II: Network analysis. IEEE Transactions on Information Theory 37: Jan. Dailianas, A., and Bovopoulis, A. 1994. Real-time admission control algorithms with delay and loss guarantees in ATM networks. Proceedings of INFOCOM'94, pp. 1065±1072. Devalla, B., Li, C., Sahoo, A., and Zhao, W. 1997. Connection-oriented real-time communication for mission critical applications?an introduction to NetEx: a portable and ef?cient tool kit. In Aerospace and Electronics Conference, NAECON 1997, vol. 2, pp. 698±707. Dong, X., Li, C., Bettati, R. Chen, J., and Zhao, W. 2000. Utilization-based admission control for real-time applications. In Proceedings of the International Conference on Parallel Processing (ICPP'2000). Figueira, N. R., and Pasquale, J. 1995. An upper bound on delay for the VirtualClock service discipline. IEEE/ ACM Transactions on Networking 3: Aug. Figueira, N. R., and Pasquale, J. 1997. Rate-function scheduling. Proceedings of Infocom'97. Firoiu, V., Kurose, J., and Towsley, D. 1997. Ef?cient admission control for EDF schedulers. Proceedings of Infocom'97. Golestani, S. J. 1995. Network delay analysis of a class of fair queuing algorithms. IEEE Journal on Selected Areas in Communications 13(6). Goyal, P. Lam, S. S., and Vin, H. 1995. Determining end-to-end delay bounds in heterogeneous networks. In 5th International Workshop on Network and Op. Sys. Support for Digital Audio and Video (NOSSDAV). Hyman, J. M., Lazar, A. A., and Paci?ci, G. 1991. Real-time scheduling with quality of service constraints. IEEE Journal on Selected Areas in Communications 9(7). Kostas, T. J., Borella, M. S., Sidhu, I., Schuster, G. M., Grabiec, J., and Mahler, J. 1998. Real-time voice over packet-switched networks. IEEE Network Mag, Jan./Feb.

200

CHOI ET AL.

Li, C., Bettati, R., and Zhao, W. 1997. Static priority scheduling for ATM networks. Proceedings of the 18th IEEE Real-Time Systems Symposium. Liebeherr, J., Wrege, D. E., and Ferrari, D. 1996. Exact admission control in networks with bounded delay services. IEEE/ACM Transactions on Networking. Liu, C. L., and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 20(1): 46±61. Nicols, K., Jacobson, V., and Zhang, L. 1997. A two-bit differentiated services architecture for the internet. Internet-Draft, Nov. Parekh, A. K. J., and Gallager, R. G. 1993. A generalized processor sharing approach to ?ow control in integrated services networks: the single-node case. IEEE/ACM Transaction Networking 1(3). Parekh, A. K. J., and Gallager, R. G. 1994. A generalized processor sharing approach to ?ow control in integrated services networks: the multiple-node case. IEEE/ACM Transactions on Networking 2(2). Park, D.-W. Natarajan, S., and Kanevsky, A. 1996. Generalized utilization-bound test for ?xed-priority real-time scheduling. Journal of Systems and Software. Raha, A., Kamat, S., and Zhao, W. 1995. Guaranteeing end-to-end deadlines in ATM networks. In The 15th International Conference on Distributed Computing Systems. Sahoo, A. Devalla, B., Guan, Y., Bettati, R., and Zhao, W. (to appear) Adaptive connection management for mission critical applications over ATM Networks. International Journal of Parallel and Distributed Systems and Networks. Special Issue On Network Architectures for End-to-end Quality-of-Service Support, to appear. Stoica, I., and Zhang, H., 1999. Providing guaranteed services without per ?ow management. Proceedings of SIGCOMM. Zhang, L. 1991. Virtual clock: A new traf?c control algorithm for packet switching networks. ACM Transactions on Computer Systems 9: May. Zhang, L., Deering, S., Estrin, D., Shenker, S., and Zappala, D. 1993. RSVP: a new resource reservation protocol. IEEE Networks Magazine 31(9): 8±18. Zhang, Z.-L., Towsley, D., and Kurose, J. 1995. Statistical analysis of the generalized processor sharing scheduling discipline. IEEE Journal of Selected Areas in Communications 13(6): 1071±1080. Zhang, J.-L., Liu, Z., and Towsley, D. 1996. Closed-form deterministic end-to-end performance bounds for the generalized processor sharing scheduling discipline. Journal of Combinatorial Optimization.

Byung Kyu Choi received the B.S. degree from the department of Electronic Engineering, M.S. degree from the department of Computer Science both in Yonsei University, Korea, in 1985 and 1994 respectively. He has ?nished his Ph.D. work in the department of Computer Science at Texas A&M University in summer 2002. He is an assistant professor in the department of Computer Science at Michigan Technological University since August 2002. His research interests are in networking and distributed real-time systems and applications. Before joining Texas A&M, he was a team leader in LG R&D Center, Korea, where he led/participated many projects including: special purposes switching systems, ATM switch, and Video-On-Demand systems.

UTILIZATION-BASED ADMISSION CONTROL

201

Dong Xuan received his B.S. and M.S. degrees in Electronic Engineering from the Shanghai Jiao Tong University (SJTU), China, in 1990 and 1993, and Ph.D. degree in Computer Engineering from Texas A&M University in 2001. Currently, he is an assistant professor in the Department of Computer and Information Science, the Ohio State University. He was on the faculty of Electronic Engineering at SJTU from 1993 to 1997. In 1997, he worked as a research assistant in the Department of Computer Science, City University of Hong Kong. From 1998 to 2001, he was a research assistant and then associate in RealTime Systems Group of the Department of Computer Science, Texas A&M University. His research interests includes real-time computing and communication, network security and distributed systems.

Chengzhi Li is currently a research scientist in the University of Virginia. He received his B.S. degree in Applied Mathematics and M.S. degree in Operations Research from Fuzhou University and Xiamen University, China respectively. He received his Ph.D. in Computer Engineering from Texas A&M University in 1999. From 1999 to 2001, he was a postdoctoral fellow in Rice University. His research areas encompass wired and wireless networking.

Riccardo Bettati received his Diploma in Informatics from the Swiss Federal Institute of Technology (ETH), Zuerich, Switzerland, in 1988 and his Ph.D. from the University of Illinois at Urbana-Champaign in 1994. From 1993 to 1995, he held a postdoctoral position at the Inter-national Computer Science Institute in Berkeley and at the University of California at Berkeley. Since 1995 he is Associate Professor in the Department of Computer Science at Texas A&M University. His research interests are in real-time distributed systems, realtime communication, and network support for distributed applications.

202

CHOI ET AL.

Wei Zhao received his B.Sc. of physics from Shaanxi Normal University, Xian, China, M.Sc. degree and Ph.D. in Computer and Information Science from the University of Massachusetts, Amherst, MA, in 1983 and 1986, respectively. In 1990 he joined the Department of Computer Science at Texas A&M University where he is currently a full professor and department head. He is an IEEE Fellow. Dr. Zhao leads the Real-Time Systems Research Group. His current research interests includes secured real-time computing and communication, distributed operating systems, database systems and fault tolerant systems. Dr. Zhao was the Editor of the IEEE Transactions on Computers and is currently an associate editor for the IEEE Transactions on Parallel and Distributed Computing Systems. He was the Program and General Chairs of The IEEE Real-Time Technology and Applications Symposia in 1995 and 1996, respectively. He served as the Program and General Chairs of the IEEE Real-Time Systems Symposia in 1999 and 2000, respectively. He will be the Co-Program Chair for the IEEE International Conference on Distributed Computing Systems in 2001. Dr. Zhao with his students received the Outstanding Paper Award in the IEEE International Conference on Distributed Computing Systems and the Best Paper Award in the IEEE National Aerospace and Electronics Conference. He has published over 150 papers in journals, conferences and book chapters.