kl800.com省心范文网

776

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

Coordinated Multihop Scheduling: A Framework for End-to-End Services

Chengzhi Li, Member, IEEE, and Edward W. Knightly, Member, IEEE

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

I. INTRODUCTION URING periods of congestion, a flow or class end-to-end performance properties are strongly influenced by the choice of the packet scheduling algorithm employed at the network’s routers. Consequently, recent advances in scheduler design can ensure properties such as fairness, performance differentiation, and performance isolation [3], [13], [15], [26]. Moreover, such performance properties are now achievable in high-speed implementations [24], [30], [32] and scalable architectures in which core nodes do not maintain a per-flow state [6], [25], [33]. Exploiting these scheduling mechanisms, admission control can limit congestion levels so that (for example) targeted latencies and throughputs are ensured, thereby providing services with predictable and controlled performance levels [22]. For example, statistical class-based admission control tests have been derived for earliest deadline first (EDF) [4], [27], [31], weighted fair queueing (WFQ) [12], [27], [38], strict priority [27], and virtual clock [20]. Moreover, techniques for providing

D

Manuscript received August 28, 2000; revised May 24, 2002; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor P. Steenkiste. An earlier version of this paper was published in the Proceedings of ICNP 2000. This work was supported by the National Science Foundation under Grant ANI-0085842 and Grant ANI-9733610, by a gift from Texas Instruments, and by a Sloan Fellowship. C. Li is with the Department of Computer Science, University of Virginia, Charlottesville, VA 22094 USA (e-mail: chengzhi@cs.virginia.edu). E. W. Knightly is with Rice University, Houston, TX 77005 USA. Digital Object Identifier 10.1109/TNET.2002.805024

multinode or end-to-end statistical services have been developed for several classes of nonwork-conserving schedulers [5], [28], [31], [37] and for WFQ networks with isolation among flows [38].1 However, in both the data plane (scheduling) and control plane (admission control), none of the aforementioned techniques exploit a key property of multihop networks, namely, that a downstream node can compensate for excessive latency or unfairness incurred at an upstream node. Nor will downstream nodes reduce the priority of a packet which arrives ahead of schedule due to a lack of congestion upstream. In contrast, a number of service disciplines in the literature have been proposed which do exploit this property, which we refer to as coordination. Examples include the oldest customer-first service discipline [8], global earliest deadline first (G-EDF) [8], modified first-in-first-out (FIFO+) [10], and coordinated earliest-deadline-first (CEDF) [1], [2]. The contributions of this paper are twofold. First, we devise a general framework for design and specification of a class of service disciplines which we refer to as coordinated multihop schedulers (CMSs). The key CMS property is that a packet’s priority index at a downstream node is recursively expressed through the priority index of the same packet at the previous node and therefore is a function of the packet’s (perhaps virtual) entrance time into the network. We show that a broad class of schedulers from the literature, including CEDF, FIFO+, and others, can be characterized by this recursion and belong to the CMS class. We make several observations regarding coordinated multihop schedulers. 1) The well-known traffic distortion problem, in which provisioning of end-to-end services is hampered by complex traffic distortions due to multiplexing, e.g., [11], [23], can be addressed. 2) CMS inter-server cooperation can improve a flow’s end-to-end performance, and consequently, improve the efficiency and utilization of the network at large. 3) They can be core-stateless, in some cases quite trivially, and therefore can share the same scalability properties of architectures in which core nodes do not maintain per-flow state [33]. Our second contribution is to devise a general theory for statistical analysis and admission control of coordinated servers. Our key technique is to devise a framework for end-to-end service provisioning that exploits the structural properties of coordinated multihop schedulers, thereby overcoming the traffic distortion problem and realizing the efficiency gains

1That

is, a statistical multiplexing among flows is not considered.

1063-6692/02$17.00 ? 2002 IEEE

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

777

of coordination. To analyze CMS networks, we introduce the concept of essential traffic, which is the traffic that must be served before a time instant such that no local service violations will occur at that time. Using this concept and building on the interclass theory of [27], we derive expressions for the essential traffic and service envelopes, which provide a general statistical characterization of a CMS node’s workload and service capacity. Within this framework, we establish an important property of the CMS discipline, namely, that traffic distortion in CMS networks is limited to within a narrow range. Therefore, the essential traffic and service envelopes at a CMS node can be evaluated as simple and minimally distorted functions of the flows’ original (undistorted) traffic envelopes that characterized traffic before entrance into the network. We then derive CMS admission control conditions by transforming the problem of evaluating the service-violation probability into the problem of computing the essential traffic envelope and the essential service envelope. Previous techniques for multinode admission control include studies of nonwork-conserving schedulers which shape and reshape traffic [5], [17], [18], [28], [31], [36], [37]. While such schemes can have good performance properties, they require per-flow traffic processing in core nodes and do not exploit the coordination property. For work-conserving service disciplines, a key issue is traffic distortion. Previous approaches include bounding this distortion [7], [11], [23], [35] and exploiting isolation properties of GPS servers [14], [19], [26], [38]. While such techniques are important for their generality, we will show that they can be conservative in practice. In contrast, our work develops a general framework for end-to-end services in CMS networks. Our solution applies to the broad class of (work-conserving) CMS servers, exploits the efficiency gains of coordination, and provides an end-to-end admission control algorithm that is quite general and achieves high utilization for multiclass multinode services. The remainder of this paper is organized as follows. In Section II, we define the CMS discipline and show how scheduling algorithms from the literature can be classified within the CMS framework. Next, in Section III, we develop a general theory for analysis and admission control for statistical end-to-end services. Finally, in Section IV, we provide admission control results obtained by simulations and numerical analysis, and in Section V we conclude.

TABLE I

Finally, let denote the increment of the priority index of the th packet of flow at its th hop.2 Definition 1 (Coordinated Multihop Scheduling): Consider a multiplexer which services packets in increasing order of their priority indexes. A scheduler possesses the CMS property if the priority index of packet of flow at its th hop can be expressed as (1) where and for is a nonnegative function of , , , , and , , the priority increments satisfy , , , for some constants and . In other words, at the first node, the priority index is added to the packet’s arrival time, and the index may be a constant, or a function of the packet’s arrival time, the packet size, the priority index of the flow’s previous packet, or constants associated with

2Notation

II. FRAMEWORK FOR COORDINATED SCHEDULING In this section, we provide a formal definition of the CMS coordination property. We then use this definition to show how a number of schedulers from the literature possess this property so that our admission control tests derived in Section III apply to a broad class of schedulers. A. CMS Definition as the priority index assigned to the th packet Denote denote of flow with size at its th hop. Moreover, let the time when the th packet of flow arrives at its first hop.

is summarized in Table I.

778

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

(a)

(b)

(c) Fig. 1. Illustration of coordination. (a) CMS and EDF at first hop. (b) EDF at second hop. (c) CMS at second hop.

the flow and/or node. In contrast, at downstream nodes, the priority index is computed recursively as a function of the upstream index rather than by using the local arrival time. Moreover, while this downstream index can also be dynamic, it must be bounded , . within a range such that is a function of , , , Observe that the requirement that , and can be interpreted as meaning that the priority index of flow ’s th packet at its th hop can be determined when the packet first enters the network. Consequently, FIFO, EDF, WFQ, and virtual clock are not coordinated schedulers. For example, the priority index assigned by FIFO can be written , where is the arrival time of the th packet of as , cannot be determined when flow at its th hop. For the packet arrives at its first hop. Similarly, for virtual clock, the , . priority index can be written as , depends on the arrival time of the th However, for packet of flow at its th hop and cannot be determined when the packet arrives at its first hop. Based on the selected method for assigning the increments of the priority index, we subclassify CMS service disciplines into delay- and rate-CMS. A service discipline belongs to the represents a delay parameter of the th delay-CMS class if packet of flow at its th hop. For example, this delay parameter can be simply a local delay bound or, for other service disciplines (described below), can be a function of packet ’s delay relative to the scheduler’s mean delay. In contrast, a service discipline belongs to rate-CMS class if is a function of and , where is the size of the th is the reserved bandwidth for flow at packet of flow and its th hop. The main characteristic of this class is that reserved bandwidths rather than delay bounds determine the service pri-

ority. Below we also describe examples of schedulers belonging to the rate-CMS class. B. Discussion The key property of the CMS discipline is that the priority index of each packet at a downstream server depends on its priority index at upstream servers, so that all servers in the network cooperate to provide the end-to-end service. For example, if a packet violates a local deadline at an upstream server, downstream nodes will increase the packet’s priority, thereby increasing the likelihood that the packet will meet its end-to-end delay bound. Similarly, if a packet arrives “early” due to a lack of congestion upstream, downstream nodes will reduce the priority of the packet. To illustrate this property, consider the simple example of Fig. 1 in which three packets of flow arrive to the network , respectively, and traverse two hops with at . In the example, all packets have identical size, the link speed is one packet per time unit, and cross traffic exists at both hops. At the first hop, these three packets are assigned priority indexes (deadlines) of 5, 6, and 7, respectively, by both CMS and EDF. Suppose further that these three packets depart from the first hop at times 3, 4, and 10, respectively, so that the third packet misses its local deadline by three time units due to cross traffic with higher priority. According to the arrival times at the second hop, these three packets are assigned priority indexes of 8, 9, and 15 by EDF, whereas the indexes are 10, 11, and 12 for CMS. In the example, with further cross traffic at the second hop, the third packet has higher priority in the CMS network than the EDF network and therefore is able to meet both its local delay bound and global delay bound. In contrast, in the

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

779

EDF network, the third packet meets its local delay bound at the second hop, but is not able to “catch up,” and meet its end-to-end delay bound. C. Example CMS Disciplines The above definition of CMS is quite general. Here, we show how several service disciplines from the literature, including G-EDF [8], FIFO+ [10], core-jitter virtual clock (CJVC) [34], and CEDF [1], [2] can be classified as instances of the CMS discipline. 1) Global EDF: The G-EDF service discipline was introduced in [8] to address the problem that reconstruction of continuous speech from voice packets is complicated by variable delays of packets due to multiplexing. In G-EDF, the priority index for a packet with age (time in network) arriving at a , where server at time is defined as is the maximum allowable entry-to-exit delay and is the estimated delay along the packet’s remaining route in the network. If we rewrite the priority index assigned by G-EDF as

to the th packet of flow before it enters the network. Fur, thermore, it can be verified that for , where and . Thus, considering , it is clear that work-conserving CJVC is a rate-CMS service discipline. 4) Coordinated EDF: In [1] and [2], the CEDF service discipline is developed with the goal of minimizing end-to-end delays. The approach is to use EDF together with randomization of packet injection time and coordination of servers. There exist two ways to assign local deadline in CEDF service discipline. In [2], the priority indexes are assigned as (5) is the token arrival time chosen uniformly at random where , , is the maxfrom interval is the rate of flow , is the imum size of flow- packets, is a constant (expected local delay utilization factor, and bound) determined for the th hop of flow . In [1], the priority indexes are assigned as

(2)

is the path length of flow , and is the expected where delay suffered by flow- packets at its th hop, then it is clear that G-EDF is a delay-CMS discipline. 2) FIFO+: The modified first-in-first-out (FIFO+) service discipline [10] assigns a packet’s priority index according to the difference between the average queueing delay seen by a packet and the particular queueing delay suffered by the packet at upstream servers. From the definition in [10], we can rewrite the recursive FIFO+ priority index as (3) is the average queueing delay of flow seen by where , , the packet at the upstream server. Provided that is determined before the packet departs from its first hop and that the range of is bounded, comparing (3) with Definition 1 shows that FIFO+ is also a delay-CMS discipline. 3) Work Conserving CJVC: CJVC was proposed in [34] as a mechanism for achieving guaranteed service without per-flow state in the network core. CJVC uses “dynamic packet state” to store information in each packet header containing the eligible time of the packet at the ingress router and a slack variable that allows core routers to determine the local priority index of the packet. For a work-conserving variant of CJVC, the priority index of packet of flow at node is given by

(6)

where

is the end-to-end delay bound for flow , , is the arrival time of token for the th packet of flow (similar to above), the is the capacity of the server in the th hop of flow , and is the path length of flow . Thus, both variants of CEDF can be classified as delay-CMS disciplines in which the first priority index is randomized. III. CMS ANALYSIS AND ADMISSION CONTROL

(4)

where flow th packet size and reserved bandwidth are given is the slack variable assigned by and respectively, and

In this section, we develop a statistical multinode analysis and admission control algorithm for CMS. We proceed in several steps. First, we introduce two key concepts needed for analysis: essential traffic and essential service. These concepts enable us to statistically bound the traffic that must be serviced in order to meet a flow’s local QoS constraints. We next show how the essential traffic at a downstream node can be computed based on a simple and minimally distorted transformation of the traffic at the entrance of the network. This result (Theorem 1) is a key to efficient end-to-end analysis. We then derive an expression for the statistical service envelope (Theorem 2): with this statistical description of service, we can characterize and control statistical sharing across traffic classes. Finally, we derive an end-to-end admission control test for coordinated schedulers (Theorem 3). as the total Throughout, we denote arriving from traffic flow at its th hop, a node traffic in . Without loss of generality, we igwhich is indexed by nore propagation delays so that the departure traffic of flow from server is the arrival traffic of flow to server

780

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

. Similar to [27], we call a sequence of nonnegaa statistical traffic envelope tive random variables 3 of flow if (7) and are independent and and assume that and are independent if . Furthermore, we consider a discrete time model with an infinite buffer in which traffic is treated as fluid. We next review several facts about stochastic ordering that is used later in this section. be independent and Lemma 1: Let be independent. If for , then ; 1) for any real number ; 2) 3) there exist independent random variables such that has the same distribution as and for . Proof: See [29]. A. Essential Traffic Here, we define essential traffic as a building block for analysis of coordinated schedulers that enables us to accurately evaluate a flow’s delay-bound-violation probability. In particular, for a given local deadline , all arriving traffic of server arriving in can be virtually decomposed according to whether or not its local deadline is later than . As only the portion of traffic with local deadline no later than time affects the probability of violating the local deadline , we refer to this traffic as essential traffic, which we formally define as follows. Definition 2 (Essential Traffic): The essential arrival traffic of flow at server is defined as the total flowtraffic with local deadline no later than time arriving at server no later than , i.e., (8) Fig. 2 illustrates the relationship among arrival traffic, essential traffic, and departure traffic. If, for example, the priority index increment for flow at each hop is , then flow ’s esis simply at node 1. Supsential traffic pose further that some flow- packets miss their local deadline will at the first hop. Then, according to Definition 2, as depicted in the figure. Next, ignoring propacross gation delay, the departure traffic of node 1 is the arrival traffic at node 2. Since at node 2, flow ’s arrival traffic has not missed its . node-2 local deadline upon arriving, The key point for Fig. 2(b) is that the relationship between the and the essential traffic characarrival traffic terizes the advantage of CMS’s coordination mechanism. In parand ticular, the horizontal distance between corresponds with the queueing delay incurred at node 1: the larger the queueing delay, the shorter the horizontal distance, and the higher the resulting priority index. Consequently, excessively delayed packets at upstream nodes can “catch up” at downstream nodes and still satisfy their end-to-end deadline requirement.

3X

(a)

(b) Fig. 2. Example of arrival, essential, and departure traffic (priority index increment ). (a) First hop. (b) Second hop.

=

B. Essential Traffic Envelope In each server of CMS networks, packets are served in increasing order of their priority indexes (local deadlines). For a must be charactergiven , flow ’s essential traffic ized to compute the local deadline violation probability. Furaffects the probability of thermore, violating the local deadline by no more than for a packet with during . Thus, local deadline arriving at server we define the essential traffic envelope as follows. Definition 3 (Essential Traffic Envelope): A sequence of is an essential nonnegative random variables and traffic envelope of flow at its th hop if such that , (9) A key challenge for provisioning multinode services is characterizing the traffic at downstream servers. The difficulty is due to the fact that a flow’s traffic is unavoidably distorted after multiplexing with other flows. Furthermore, the traffic distortion may be accumulated along the path of a flow in networks without coordinated scheduling disciplines. However, due to the coordination property, the accumulated distortion phenomenon of the essential traffic is mitigated. In networks with coordinated scheduling, the distortion of a flow’s essential traffic after passing through a server depends only on the local deadline violation. If the flow’s traffic does not violate its local deadlines, the distortion of the essential traffic is eliminated, even if the flow’s traffic incurs a queueing delay. The following theorem precisely characterizes this advantage of the coordination property. denote the maximum tolerable local deadline viLet . That is, a flow- packet olation of flow- traffic at server will be discarded if it misses its local deadline at server by more than . Let denote the amount of no later than flow- traffic with local deadline at server that is discarded during before arriving at server .

Y (stochastic inequality) denotes P X > z

[

] P [Y

> z for all z .

]

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

781

Theorem 1: An essential traffic envelope its th hop is given by

of flow at (10)

Since , we have according to (12) and (14), we have

. Thus,

. where Proof: To relate a flow’s downstream essential traffic to its original arrival envelope, we statistically upper bound and lower bound . . For all and such that , Let . Without loss of generality, asconsider the interval sume that there is at least one flow- packet with local deadline during . Otherno later than arriving at server , a trivial case. Since for wise, a given flow , packets are always serviced in increasing order of their local deadlines, all flow- packets arriving at server before time have local deadlines no later than . According to , we have Definition 2 and the definition of (11) Notice that the interval has duration Since , we have and , ,

According to (7),

(12) Next, we lower bound as follows: (13)

Thus, we have

since at time all flow- traffic with local deadlines at server no later than either has departed and arrived at server or has been disserver carded due to the maximum tolerable local deadline violation at server for flow- traffic. Thus, similar to (12), we have

That is, by Definition 3,

(14)

This theorem describes an important property of the CMS discipline, namely, that distortion of essential traffic downstream is limited to within a narrow range. To illustrate, consider the for all so that special case in which for . In this case, for any flow , its essential traffic envelope at downstream servers, namely, , is affected by the maximum toler. Furthermore, if is able local deadline violation chosen appropriately such that flow- packets do not miss their local deadlines or flow- packets that miss local deadlines are

782

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

discarded, i.e., , flow- ’s essential traffic envelope at downstream servers is identical to that at the ingress server, . Finally, for two different flows namely, and , according to (10), and are indepenand are independent. Thus, the property of dent if independence between essential traffic envelopes at the network edge is preserved downstream. C. Essential Service Envelope The above result enables us to derive end-to-end admission control tests for CMS networks in the single class case. However, with multiple traffic classes with statistical sharing across classes, classes affect each others’ performance. Consequently, characterizing the extent to which resources are shared across classes is the key to achieving high utilization in multiclass networks without worst-case allocation for each class [27]. Thus, we use statistical service envelopes as a tool for characterizing and controlling interclass resource sharing. Definition 4 (Essential Service Envelope): A sequence of is called a (stanonnegative random variables to tistical) essential service envelope provided by server and such that , the traffic of flow , if , the minimum available service, denoted as to flow- traffic with local deadline at server from server no later than and arriving at server during is lower bound by (15) , server only services the provided that, during . traffic arriving during is a measure of the service provided in Roughly, an interval with length to flow- traffic with local deadline seconds before the end of the interval. Notice that the minimum during an interval available service for flow from server will depend on the other flows’ arriving traffic. Furthermore, the to flow essential service envelope provided by server depends on the other flows’ essential traffic. Using this definition, we can now derive an expression for the essential service envelope. , and , Theorem 2: For a given

, according to Theorem 1, the total flow- traffic with local deadlines no later than arriving at server during is bound by

Since , Lemma 1, we have

, , are independent and , , are independent, according to

and so

where and are defined by , is the set of flows served by server , and is the capacity of server . Proof: Since the amount of total traffic (except flow ) with local deadlines no later than and arriving at server during is and the total service capacity of server during the same time , we have interval is That is, by Definition 4, (16)

(17)

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

783

According to this theorem and Lemma 1, for a given , and , there exists a random variable with the such that same distribution as (18) Furthermore, according to (17), (7), and (10), we have that

(19) has the same distriwhere the random variable and bution as . Finally, according to (10) and , , , , are independent. are independent, , , are independent, and from Furthermore, , , are indepenLemma 1 we have that has dent. Since , the same distribution as

Observe that is the amount of flow- traffic deduring . If parting from server , all flow- traffic with local deadline no later than at and arriving at server before time has departed server . For one flow- packet with local server before time at time , the event of this deadline arriving at server is contained in the event packet being served after time , and we henceforth consider this latter event. The following theorem shows how to evaluate this delay distribution. Theorem 3: The virtual delay distribution of flow at its th hop is bounded by

(23) , where and for are random variables with the same distribution as , respectively. Proof: From (22), we have

and

(20) Since , so that5 D. Admission Control We now derive an end-to-end admission control condition for CMS networks. The technique used to analyze the deadline-violation probability is to analyze per-server local delay-bound-violation probabilities and then compose them into end-to-end ones. When computing the local-deadline-violation probability at a given server, any arrival packet at the server is not considered as discarded even if it incurs a long queueing delay, i.e., packet discarding only occurs at the upstream servers. For a multiplexer (server) in a CMS network and given time and local deadline , an important instant previous to is the time when the multiplexer does not service traffic with local deadlines later than . As we see below, this is important for analysis because the traffic arriving at the multiplexer before this moment does not affect the probability of local deadline violation. and We refer to this instant as the void time denoted as precisely define it as and (21) , . Thus,

If , there always exist packets with deadlines during . Since no later than at server there is not traffic with a deadline no later than at at amount of flow- traffic has server , at least , server been served. Furthermore, during only serves the traffic with local deadline no later than and . Similar to (16), we have arriving at server after

Thus,

is the total amount of traffic with local deadline where no later than backlogged at server at time .4 Notice that is not necessarily idle at time as it may be server busy serving traffic with local deadlines later than . We use a concept of (virtual) delay due to the essential traffic at a particular node to derive the local deadline-violation probability as an intermediary step toward bounding the end-to-end deadline violation probability. Thus, we define (virtual) essential delay of flow- traffic with local deadline no later than time at server at time as (22)

4Without

and so

loss of generality, we assume that network is idle at time 0.

5When computing the probability of local deadline violation for a flow-i packet with local deadline s arriving at time t, f (s + D ; s) = f (t; s), because the local deadline of any flow-i packet arriving after time t is larger than s, so that f (t; s) f (s + D ) > 0 f (s + D ; s) (s + D ) > 0 . f

f

0 g

g f

0

784

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

Since the random variable

, we have

where

and Notice that for a real number , from Theorem 1 and Theorem and 2, . According to Lemma 1, we can find random variables and with the same distribution as and respectively such and that . Thus, we have

and are defined by Proof: From Theorem 3, we have

.

According to Theorem 1

and according to (20)

(25) Therefore Therefore, we have

That is Thus, according to Theorem 3, the problem of computing the flow- delay distribution is transformed into the problem of finding flow ’s essential traffic envelope and essential service envelope. Based on Theorems 1 and 2, we have the following results. Corollary 1: For (24)

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

785

Fig. 3.

Tandem network topology.

Thus, applying this result, each flow can be guaranteed an end-to-end delay bound along with its violation probability by using Corollary 1 to compose per-node QoS parameters into end-to-end ones. IV. SIMULATION AND ADMISSION CONTROL EXPERIMENTS In this section, we study the performance of the CMS discipline by performing a set of ns-2 simulation and admission control experiments. Our goal is twofold. First, we establish the effectiveness of our admission control algorithm in properly controlling the number of admitted flows in CMS networks. To achieve this, we first perform a large set of simulation experiments, in which a fixed number of flows are established over various network paths (as described below). For each scenario, we perform numerous simulations and record average performance measures such as a end-to-end delay bound violation probability. We then run a set of admission control experiments in which we use an implementation of our admission control to determine the maximum number of admissible flows under a certain performance criteria. The results of these experiments yield experimental and predicted admissible regions, i.e., the true admissible region obtained by simulations and those obtained by our admission control algorithm. Our second set of experiments explore the end-to-end performance of CMS networks as compared with non-CMS networks. In particular, we consider networks of FIFO, EDF, and WFQ schedulers and investigate the fraction of packets violating end-to-end delay targets under the different schedulers. These experiments illustrate the potential QoS improvements of coordinated network scheduling, that is, its ability to improve end-to-end performance under a particular network load, or conversely to improve the admissible region under a particular QoS requirement. A. Scenario We consider a simple tandem network topology as depicted in Fig. 3. All link rates are 10 Mb/s, packet lengths are 100 bytes, flows entering and propagation delays are 0 ms. There are the network from the first server and exiting from the last server. These flows have the longest path and are chosen to be the target class for analysis. In addition, each router also serves two classes flows which traverse a single of cross traffic consisting of flows that traverse router and then exit the network, and two routers and then exit the network. The cross traffic has the same characteristics as the target traffic (described below) and comprises approximately 80% of the total traffic.

We simulate exponential ON–OFF flows with ON-rate of 64 kb/s, mean ON time of 312 ms, and mean OFF time of 325 ms. For the CMS discipline, we choose for cross traffic flows with a 1 hop path;

for cross traffic flows with a 2 hop path;

for target traffic flows with a 6 hop path where is the expected end-to-end queueing delay bound. In , is equivalent this case, , . Using [21], and the to flows’ mean rate, peak rate, and mean burst length given by the , we approximate the statistical traffic envelope tuple as and var , where

. Furthmore, when predicting the admissible region for CMS networks, we assume that a packet will be discarded if it suffers a queueing delay at a server more than two times its queueing . Finally, for the delay budget at that server, i.e., EDF discipline, we choose the priority index for flow- ’s th , and for the WFQ discipline packet at its th hop as we assign the same weight for each flow. B. WFQ Admission Control To compare CMS with WFQ, we also implement WFQ admission control as follows. Consider flow with guaranteed guaranteed at router such that bandwidth

where is the long-term average rate of flow and is the set of flows that are served by server . By simple extension of the results in [38], the probability of the end-to-end deadline violation of the traffic of flow can be bounded by (26)

786

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

where and is the set of flows with the same source and destination as flow . C. Computing Performance Bounds To compute

we use the maximum variance approach developed in [9]. Let

Fig. 4. Measured and predicted admissible regions.

var A proof of this bound can be found in [9] and a detailed comparative performance study in [22]. Roughly, the approach uses the dominant time scale, the value of minimizing the expression above, to derive the exponential asymptotic upper bound of (27). Our goal here is to use the technique as an efficient and accurate means to evaluate the admission control conditions. Regardless, refinements based on large deviations theory can also be applied within the context of statistical envelopes [4]. D. Admissible Regions Here, we compare measured and predicted admissible regions for CMS and WFQ networks for the scenario described above and present measured admissible regions for EDF and FIFO networks. The results of the experiments are depicted in Fig. 4. The figure shows network utilization versus the end-to-end queueing delay of the target traffic, i.e., aggregate average traffic rate divided by link capacity versus the delay target. The combinations of the target traffic and cross traffic and the corresponding expected end-to-end queueing delays are given in Table II. The simulation curves depict the maximum number of flows (scaled to utilization) that can be multiplexed such that the delay target (depicted on the horizontal axis) is satisfied with delaybound-violation probability of no more than 0.001. For these curves, ten independent simulation runs of 400 simulated seconds are performed and mean results are reported. Similarly, the “predicted” curve depicts the maximum number of flows admitted by our admission control algorithm, under the targeted delay depicted on the horizontal axis, and a delay-bound-violation probability of 0.001. We make the following observations regarding this figure. First, notice that the admissible region for the CMS network is larger than that of the WFQ, EDF, and FIFO networks. For example, for the same violation probability ( 0.001) and the same traffic load (60 target traffic flows and 240 cross traffic flows at each node, i.e., approximately 94.1% utilization), CMS can support an end-to-end delay of 48 ms whereas WFQ’s delay is 52 ms, EDF’s delay is 56 ms, and FIFO’s delay is 80 ms. Thus, while WFQ achieves local fairness of bandwidth sharing at each node [26] and EDF minimizes the queueing delay at a single server system [16], CMS uses the coordination property

var

Approximating

as Gaussian, the following upper bound can been obtained:

(27)

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

787

TABLE II TRAFFIC COMBINATION AND EXPECTED END-TO-END QUEUEING DELAY

to minimize end-to-end delay and achieve global performance properties. Second, we observe that our CMS admission control algorithm is able to exploit a large fraction of the available statistical multiplexing gain. For example, by an end-to-end delay bound of 60 ms, the CMS admission control algorithm admits a set of flows which contains 56 target traffic flows and 224 cross traffic flows at every server, within 6.1% of the actual utilization achievable in simulations (60 target traffic flows and 240 cross traffic flows). In contrast, for the WFQ network, 54 target traffic flows and 208 cross traffic flows are admitted at each router, which is more than 10% less than the utilization achievable in simulations (58 target traffic flows and 234 cross traffic flows). The reason for the more conservative nature of WFQ admission control is that traffic is treated as traversing the network on a guaranteed-rate “pipe” between an ingress and egress router, without taking into account inter-class resource sharing among pipes. Thus, with more traffic classes and more complex topologies, such an approach will suffer further utilization penalties. E. End-to-End Delay Performance Here, we compare the end-to-end queueing delays incurred by the target traffic for networks with CMS, WFQ, FIFO, and EDF schedulers. FIFO services provide baseline results for a scheduler with neither coordination nor QoS differentiation. In contrast, EDF provides differentiation and optimality at a single node, but does not employ coordination, so that gains of CMS versus EDF are strictly due to coordination. We measure end-to-end delay distributions for two scenarios: 1) Fifty-six target traffic flows and 224 cross traffic flows at each server (the expected end-to-end queueing delay bound for each flow is 6 ms, and so the increments of the priority index at each server are 1 ms for target traffic, 3 ms for cross traffic with a two-hop path, and 6 ms for cross traffic with a one-hop path); 2) Sixty target traffic flows and 240 cross traffic flows at each server (the expected end-to-end queueing delay bound for each flow is 45 ms, and so the increments of the priority index at each server are 7.5 ms for target traffic, 22.5 ms for cross traffic with a two-hop path, and 45 ms for cross traffic with a one-hop path). For this fixed number of flows and utilization, Fig. 5 depicts the end-to-end queueing delay and its corresponding violation probability. We make two observations regarding the figure. First, the QoS-violation probabilities for CMS, WFQ, and EDF are al-

(a)

(b)

ON–OFF

D=

Fig. 5. Comparison of FIFO, EDF, WFQ, and CMS disciplines (exponential traffic). (a) Utilization 87.7%, 6 ms. (b) Utilization 94.1%. 45 ms.

=

D=

=

ways smaller than those for FIFO. For example, in Fig. 5(b), the violation probability for a 50-ms end-to-end queueing delay bound is 0.0007 for CMS, 0.0016 for EDF, 0.001 for WFQ, and 0.0094 for FIFO. Second, notice that for smaller delays (less than 6 ms with 87.7% utilization or less than 40 ms with 94.1% utilization), the CMS violation probability larger than EDF’s whereas for larger end-to-end queueing delays (greater than 6 ms with 87.7% utilization or greater than 40 ms with 94.1% utilization scenario) is smaller than EDFs. The reason for this is that, in a CMS network, packets which suffer excessive queueing delays at upstream nodes have an opportunity to “catch up” at a downstream node, by having a higher (relative)

788

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 10, NO. 6, DECEMBER 2002

priority index. In contrast, in EDF networks, each router treats packets locally according to their arrival time and local deadline, without regard to whether this arrival time is late or early. Thus, the experiments indicate that coordinated scheduling also has performance advantages, in addition to its other properties (e.g., tractability) established above. V. CONCLUSION In this paper, we developed a framework for CMS. With a definition of the fundamental coordination property, we showed how a number of schedulers from the literature can be characterized as CMS disciplines. We then developed a general theory based on traffic and service envelopes to analyze CMS networks and devised admission control tests for statistical end-to-end services. We showed that CMS disciplines limit traffic distortion to within a narrow range, thereby providing a foundation for efficient and scalable multinode services. We performed a set of simulation and admission control experiments to illustrate the accuracy of the approach to control multinode admissions and demonstrated potential performance advantages of CMS as compared to WFQ, EDF, and FIFO. Our results present a new framework for understanding end-to-end statistical services in differentiating and work-conserving schedulers. ACKNOWLEDGMENT The authors would like to thank the anonymous referees and the Editor, Prof. P. Steenkiste, for their constructive comments. REFERENCES

[1] M. Andrews, “Probabilistic end-to-end delay bounds for earliest deadline first scheduling,” in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 603–612. [2] M. Andrews and L. Zhang, “Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule,” in Proc. IEEE INFOCOM ’99, New York, Mar. 1999, pp. 380–388. [3] J. Bennett and H. Zhang, “WF Q: Worst-case fair weighted fair queueing,” in Proc. IEEE INFOCOM ’96, San Francisco, CA, Mar. 1996, pp. 120–128. [4] R. Boorstyn, A. Burchard, J. Liebeherr, and C. Oottamakorn, “Effective envelopes: Statistical bounds on multiplexed traffic in packet networks,” in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 1223–1232. [5] , “Tradeoffs in networks with end-to-end statistical QoS guarantees,” in Proc. IWQoS 2000, June 2000, pp. 221–230. [6] Z. Cao, Z. Wang, and E. Zegura, “Rainbow fair queueing: Fair bandwidth sharing without per-flow state,” in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 922–931. [7] C. Chang, “Stability, queue length, and delay of deterministic and stochastic queueing networks,” IEEE Trans Automat. Contr., vol. 39, pp. 913–931, May 1994. [8] T. Chen, J. Walrand, and D. Messerschmitt, “Dynamic priority protocols for packet voice,” IEEE J. Select. Areas Commun., vol. 7, pp. 632–643, June 1989. [9] J. Choe and N. Shroff, “A central limit theorem based approach to analyze queue behavior in ATM networks,” IEEE/ACM Trans. Networking, vol. 6, pp. 659–671, Oct. 1998. [10] D. Clark, S. Shenker, and L. Zhang, “Supporting real-time applications in an integrated services packet network: Architecture and mechanism,” in Proc. ACM SIGCOMM ’92, Baltimore, MD, Aug. 1992, pp. 14–26. [11] R. Cruz, “A calculus for network delay, Parts I and II,” IEEE Trans. Inform. Theory, vol. 37, pp. 114–141, Jan. 1991. [12] G. de Veciana and G. Kesidis, “Bandwidth allocation for multiple qualities of service using generalized processor sharing,” IEEE Trans. Inform. Theory, vol. 42, pp. 268–272, Jan. 1995. [13] C. Dovrolis and P. Ramanathan, “A case for relative differentiated services and the proportional differentiation model,” IEEE Network, vol. 13, pp. 26–35, Sept. 1999.

[14] A. Elwalid, D. Mitra, and R. Wentworth, “Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes,” in Proc. IEEE INFOCOM ’99, Mar. 1999, pp. 1220–1230. [15] S. Floyd and V. Jacobson, “Link-sharing and resource management models for packet network,” IEEE/ACM Trans. Networking, vol. 3, pp. 365–386, Aug. 1995. [16] L. Georgiadis, R. Guérin, and A. Parekh, “Optimal multiplexing on a single link: Delay and buffer requirements,” IEEE Trans. Inform. Theory, vol. 43, pp. 1518–1535, 1997. [17] L. Georgiadis, R. Guérin, and V. Peris, “Effect of network QoS provisioning based on per node traffic shaping,” IEEE/ACM Trans. Networking, vol. 4, pp. 482–501, Aug. 1996. [18] S. Golestani, “A stop-and-go queueing framework for congestion management,” in Proc. ACM SIGCOMM ’90, Philadelphia, PA, Sept. 1990, pp. 8–18. [19] P. Goyal, S. Lam, and H. Vin, “Determining end-to-end delay bounds for heterogeneous networks,” in Proc. IEEE Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’95), Durham, NH, Apr. 1995, pp. 287–298. [20] P. Goyal and H. Vin, “Statistical delay guarantee of virtual clock,” in Proc. IEEE Real-Time Systems Symp., Dec. 1998, pp. 450–459. [21] E. Knightly, “Enforceable quality of service guarantees for bursty traffic streams,” in Proc. IEEE INFOCOM ’98, San Francisco, CA, Mar. 1998, pp. 635–642. [22] E. Knightly and N. Shroff, “Admission control for statistical QoS: Theory and practice,” IEEE Network, vol. 13, pp. 20–29, Mar. 1999. [23] J. Kurose, “On computing per-session performance bounds in high-speed multi-hop computer networks,” in Proc. ACM SIGMETRICS ’92, Newport, RI, June 1992, pp. 128–139. [24] A. Mekkittikul and N. McKeown, “A practical scheduling algorithm to achieve 100% throughput in input-queued switches,” in Proc. IEEE INFOCOM ’98, San Francisco, CA, Mar. 1998, pp. 792–799. [25] T. Nandagopal, N. Venkitaraman, R. Sivakumar, and V. Bharghavan, “Delay differentation and adaptation in core-stateless networks,” in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 421–430. [26] A. Parekh and R. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: The multiple node case,” IEEE/ACM Trans. Networking, vol. 2, pp. 137–150, Apr. 1994. [27] J. Qiu and E. Knightly, “Inter-class resource sharing using statistical service envelopes,” in Proc. IEEE INFOCOM ’99, New York, Mar. 1999, pp. 1404–1411. [28] M. Reisslein, K. Ross, and S. Rajagopal, “A framework for guaranteeing statistical QoS,” IEEE/ACM Trans. Networking, vol. 10, pp. 27–42, Feb. 2002. [29] S. M. Ross, Stochastic Processes: Wiley, 1983. [30] M. Shreedhar and G. Varghese, “Efficient fair queueing using deficit round-robin,” IEEE/ACM Trans. Networking, vol. 4, pp. 375–385, June 1996. [31] V. Sivaraman and F. Chiussi, “Providing end-to-end statistical delay guarantees with earliest deadline first scheduling and per-hop traffic shaping,” in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 631–640. [32] D. Stephens and H. Zhang, “Implementing distributed packet fair queueing in a scalable switch architecture,” in Proc. IEEE INFOCOM ’98, San Francisco, CA, Mar. 1998, pp. 282–290. [33] I. Stoica, S. Shenker, and H. Zhang, “Core-stateless fair queueing: A scalable architecture to approximate fair bandwidth allocations in high speed networks,” in Proc. ACM SIGCOMM ’98, Vancouver, BC, Canada, Sept. 1998, pp. 118–130. [34] I. Stoica and H. Zhang, “Providing guaranteed services without per flow management,” in Proc. ACM SIGCOMM ’99, Cambridge, MA, Aug. 1999, pp. 81–94. [35] O. Yaron and M. Sidi, “Performance and stability of communication networks via robust exponential bounds,” IEEE/ACM Trans. Networking, vol. 1, pp. 372–385, June 1993. [36] H. Zhang, “Providing end-to-end performance guarantees using nonworking-conserving disciplines,” Comput. Commun., vol. 18, no. 10, pp. 769–781, Oct. 1995. [37] H. Zhang and E. Knightly, “Providing end-to-end statistical performance guarantees with bounding interval dependent stochastic models,” in Proc. ACM SIGMETRICS ’94, Nashville, TN, May 1994, pp. 211–220. [38] Z. Zhang, D. Towsley, and J. Kurose, “Statistical analysis of generalized processor sharing scheduling discipline,” IEEE J. Select. Areas Commun., vol. 13, pp. 368–379, Aug. 1995.

LI AND KNIGHTLY: COORDINATED MULTIHOP SCHEDULING: A FRAMEWORK FOR END-TO-END SERVICES

789

Chengzhi Li (S’97–M’99) received the B.S. degree in applied mathematics from Fuzhou University, China, and the M.S. degree in operations research from Xiamen University, China, and the Ph.D. degree in computer engineering from Texas A&M University, College Station, in 1999. He is currently a Research Scientist with the University of Virginia, Charlottesville. He From 1999 to 2001, he was a Post-Doctoral Fellow with Rice University, Houston, TX. His research areas encompass wired and wireless networking.

Edward W. Knightly (S’92–M’96) received the B.S. degree from Auburn University in 1991, the M.S. degree from the University of California at Berkeley in 1992, and the Ph.D. degree from the University of California at Berkeley in 1996. He is an Associate Professor in the ECE/CS Departments at Rice University, Houston, TX. His research interests are in the areas of quality-of-service, scheduling, admission control, and media access protocols in wireless and wireline networks. He is an Editor of the Computer Networks Journal. Prof. Knightly is an Editor for IEEE/ACM TRANSACTIONS ON NETWORKING, IEEE TRANSACTIONS ON MULTIMEDIA, and previously, IEEE Network Magazine. He served as Co-Guest Editor of IEEE Network Magazine’s Special Issue on integrated and differentiated services for the Internet in 1999. He served as co-chair of IWQoS 1998 and on the steering committee for IWQoS from 1999–2001. He is the finance chair for ACM MOBICOM 2002, was the tutorial co-chair for IEEE ICNP 2001, and served on the program committee for numerous networking conferences including ICNP, INFOCOM, IWQoS, MOBICOM, and SIGMETRICS. He received the National Science Foundation CAREER Award in 1997 and the Sloan Fellowship in 2001.

Knightly, "*Coordinated* *Multihop* *Scheduling*: *A* *Framework* *for* *End-to-End* *Services*," IEEE/ACM Transactions on Networking, 10(6), December 2002. 5. V. ...

Energy level Performance of *Multi hop* CDMA ...using proper routing and node *scheduling* algorithm....*A*. Scheme I Average *end-to-end* packet error ...

This paper considers the *multihop* network structure...*endto-end* throughput with the help of TDs from...The review of this paper was *coordinated* by Dr....

be in active if not *coordinated* through the MD....source node to the sink node in *a* *multi*-*hop* ...*A*. Average *end-to-end* delay The average end-...

ed *end-to-end*, i.e., by the ?nal *hop*. ...*coordinated* *scheduling* with *a* set of numerical ...*scheduling*: *A* *framework* *for* *end-to-end* *services*....

rate control mechanism and *a* *coordinated* admission control/*scheduling* mechanism.... resource adaptability, and *end-to-end* QoS) associated with the *framework*....

Energy-Efficient *Multi*-*hop* Medical Sensor Networking...*COordinated* Sleep *Scheduling* (TICOSS), *a* mechanism...*end-to-end* packet delay, MAC protocols *for* ...

Based on *Scheduling* by Multiple Edge Reversal (...*coordinated* rhythmic patterns observed among pairs ...*Hop*?eld nets) will oscillate with *a* higher ...

and *Coordinated* Science Laboratory, University of ...We proceed to larger *multi*-*hop* networks, and ...Internet is to enable *end-to-end* information ...

ne the problem and discuss the *coordinated* ... *end-to-end* max-min fairness to *multi*-*hop* ?... in contention resolution or packet *scheduling*, ...

OFDMA *scheduling* determines the parameters *to* use *for* each resource unit [3...*For* this, *a* *multihop* transmission is *coordinated* by centralized control ...

1. Introduction *End-to-end* applications almost ... distributed *scheduling* involves un*coordinated* ...In this case, *a* source that gets multiple ...

- Coordinated network scheduling A framework for end-to-end services
- Framework Design for End-to-End Optimization
- QOS CONTROL IN NEXT-GENERATION MULTIMEDIA NETWORKS A Framework for End-to-End Service Diffe
- A packet scheduling algorithm for max–min fairness in multihop wireless LANs
- Link scheduling with power control for throughput enhancement in multihop wireless networks
- End-to-end QoS routing framework for differentiated services networks
- A Framework for Secure End-to-End Delivery of Messages in PublishSubscribe Systems
- A Framework for End-to-End Verification and Evaluation of Register Allocators
- AN END-TO-END QoS FRAMEWORK FOR MULTIMEDIA STREAMING SERVICES IN 3G NETWORKS
- Chameleon an Architecture for Advanced End-to-end Services