U Ayesta

M Erausquin

M Jonckheere

I M Verloop

Scheduling in a random environment: stability and asymptotic optimality

We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted and users arrive and depart upon service completion. This may model for example the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: (1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based [8], Proportionally Best [1] or Potential Improvement [4] are stable under the maximum stability conditions, whereas the opportunistic scheduler Relative-Best [9] or the cµ-rule are not.

(2) We show that choosing the right tie-breaking rule is crucial for the performance (e.g. average delay) as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. We will refer to such tiebreaking rule as myopic. (3) We derive the growth rates of the number of users in the system in overload settings under various policies, which give additional insights on the performance. (4) We conclude that simple priority-index policies with the myopic tie-breaking rule, are stable and asymptotically optimal. All our findings are validated with extensive numerical experiments.

I. INTRODUCTION

Next generation wireless networks are expected to support a wide variety of data services. Due to fading and interference effects, for each user, the quality of a downlink channel, and hence its transmission rate, fluctuates over time. This has triggered a large amount of work aiming at understanding the performance of channel-aware scheduling policies. It is by now accepted that so-called "opportunistic schedulers" have many desirable properties (see for example [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF]). A policy is called opportunistic if it takes advantage of the channel fluctuations by serving a user whose channel condition is in a good state with respect to its own statistical behavior. With the objective of minimizing mean users' delay, there arises a key tradeoff in the design of scheduling mechanisms between making full use of the opportunistic gains (hence ensuring a stable system) and prioritizing users having small residual service sizes.

Broadly speaking, researchers have explored scheduling in wireless systems both at the packet level and at the flow level. In packet-level models it is typically assumed that there exists a finite number of permanent users. The focus of the scheduler is on the number of packets in the queue of each user. We refer for example to [START_REF] Tassiulas | Dynamic server allocation to parallel queues with randomly varying connectivity[END_REF], [START_REF] Andrews | Instability of the proportional fair scheduling algorithm for HDR[END_REF], [START_REF] Stolyar | Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic[END_REF], [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF], [START_REF] Andrews | Scheduling in a queueing system with asynchronously varying service rates[END_REF], [START_REF] Neely | Order optimal delay for opportunistic scheduling in multiuser wireless uplinks and downlinks[END_REF], [START_REF] Sadiq | Delay-optimal opportunistic scheduling and approximations: The log rule[END_REF] for this line of research. In a flow-level model instead, users arrive randomly to the system and leave after receiving their finitesized service demands. This allows to capture the performance as perceived by the end-users, see for example [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF], [START_REF] Hu | Traffic aided opportunistic scheduling for wireless networks: algorithms and performance bounds[END_REF], [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF], [START_REF] Park | Wireless packet scheduling based on the cumulative distribution function of user transmission rates[END_REF], [START_REF] Lassila | Combining opportunistic and size-based scheduling in wireless systems[END_REF], [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF], [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF], [START_REF] Sadiq | Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics[END_REF]. For surveys on flow-level modeling we refer to [START_REF] Liu | Optimal opportunistic scheduling in wireless networks[END_REF] and [START_REF] Borst | Flowlevel performance and capacity of wireless networks with user mobility[END_REF]. In [START_REF] Liu | Throughput-optimal scheduling in the presence of flow-level dynamics[END_REF], hybrid models are studied.

The performance evaluation and optimization of wireless networks at the flow level has proved to be extremely challenging. One of the most successful approaches has been the so-called time-scale separation argument (see [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF], [START_REF] Borst | Flow-level stability of channel-aware scheduling algorithms[END_REF], [START_REF] Borst | Stability of parallel queueing systems with coupled service rates[END_REF], [START_REF] Sadiq | Delay-optimal opportunistic scheduling and approximations: The log rule[END_REF], [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF], [START_REF] Sadiq | Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics[END_REF]) where it is assumed that at the flow scale the dynamics of the channel fluctuations can be averaged out. Under this time-scale assumption, it was shown in [START_REF] Borst | Flow-level stability of channel-aware scheduling algorithms[END_REF] that any utility-based scheduling policy is stable in a flow-level model. The authors of [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF] make the same assumption when they discuss rate-stability for priority-index policies. In the context of optimal control, in [START_REF] Sadiq | Delay-optimal opportunistic scheduling and approximations: The log rule[END_REF], [START_REF] Sadiq | Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics[END_REF] scheduling mechanisms were introduced and evaluated. In [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF] optimal control is studied without the time-scale separation assumption. The Lagrangianrelaxation method allowed the authors of [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF] to construct the Potential Improvement (PI) scheduling policy, which is optimal for a relaxed optimization problem. In addition, several other policies have been proposed and numerically investigated in the literature, among others the Proportional Fair [START_REF] Chaponniere | Transmitter directed code division multiple access system using path diversity to equitably maximize throughput[END_REF] discipline, the Score-Based (SB) algorithm [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF], the Relative Best (RB) scheduler [START_REF] Berggren | Asymptotically fair transmission scheduling over fading channels[END_REF] and Proportionally Best (PB) [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF].

To sum up, without a time-scaling separation argument, which is a rather strong assumption, the performance of opportunistic schedulers, regarding stability and performance perceived by the users, is not well understood. In order to gain better insight into the latter issue, in this paper we will study a flow-level model without the time-scale separation assumption. More precisely, we assume that users arrive randomly in time and have a finite amount of data to download. Time is slotted and the quality of the channel condition of each user varies per time slot. In every slot at most one user may be served. We are interested in stability and optimization of the system.

Given the complexity of the problem we investigate the system under the so-called fluid scaling. Fluid scaling or timespace scalings, corresponding to "zooming out" the trajectories, have been used extensively to study stochastic processes with complex dynamics [START_REF] Darling | Differential equation approximations for markov chains[END_REF]. The limiting processes are much simpler to describe while they provide us with crucial insights on the behavior of the non-scaled version of the process.

First of all, we characterize the maximum stability conditions (the weakest possible conditions on the traffic parameters such that there exists a scheduling policy that makes the system stable) and show that the set of policies that are stable under the maximum stability condition have a very simple characterization: whenever there are users present that are currently in their best channel condition, only such users are served. These policies will be referred to as Best-Rate (BR) policies. Such a characterization was previously given for rate stability [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF], but stochastic stability was still an open issue.

Second, for a large class of scheduling policies we determine the exact stability conditions and conclude that many known opportunistic scheduling policies like SB, PB, or PI are stable under the maximum stability conditions, whereas the opportunistic scheduler RB or cµ-rule are not.

Third, we demonstrate the importance of the choice of the tie-breaking rule. Until now, literature proposed to break ties at random [START_REF] Berggren | Asymptotically fair transmission scheduling over fading channels[END_REF], [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF], [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF], [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF]. We instead propose to give priority to the user with highest instantaneous departure probability when there are multiple users in their best channel conditions, which we refer to as the myopic tie-breaking rule. We prove that BR policies with this tie-breaking rule are asymptotically optimal and our numerical experiments further illustrate that the myopic tie-breaking rule significantly improves the performance. This in turn shows that simple priority-index policies that balance opportunistic gains with size-based information, will be both maximum stable and asymptotically optimal.

Fourth, our convergence result allows to compare the performance of the various policies in an overload setting. More precisely, we determine the growth rates of the number of users in the various classes and find that BR policies with a myopic tie-breaking rule minimize the total growth rate.

The paper is organized as follows. In Sections II and III we present the model and the scheduling policies. In Section IV we derive fluid limits for a large class of policies. This allows to obtain our stability results as presented in Section V. In Section VI we characterize asymptotically optimal policies, both in normal regime and in overload, and discuss the importance of the tie-breaking rule. In Section VII we perform numerical experiments to validate our theoretical findings.

II. MODEL DESCRIPTION

We consider a time-slotted system serving one user in each time slot. This models for instance a CDMA 1xEV-DO system as explained in Remark 2. There are K classes of users, and in each time slot the number of class-k users arriving to the system, A k , follows an i.i.d. sequence of random variables, with

E(A k ) = λ k and E(A 2 k ) < ∞.
For each user the departure probability varies over time as the quality of the channel is changing from slot to slot. The quality of the channel (or state of the channel) for a class-k user is modeled as an i.i.d. sequence of random variables taking values in the finite set N k := {1, 2, . . . , N k }. For each time slot we let q k,n denote the probability that a class-k user is in channel state n ∈ N k . Associated with channel state n is a departure probability µ k,n . This can be used for instance to model a system in which the service requirements are geometric (see Remark 2). W.l.o.g. we assume that the channel conditions are ordered such that 0

≤ µ k,1 ≤ µ k,2 ≤ • • • ≤ µ k,N k ≤ 1, and q k,N k µ k,N k = 0, ∀ k.
The channel condition of a class-k user is independent of the channel conditions of all the other users and of the channel quality history.

In each time slot t, a scheduler/policy f decides which user is served. Because of the Markov property of the system, we focus on policies that base decisions on the current number of users present in the various classes and on their current channel states. For a given scheduling policy f , let X f k (t) denote the number of class-k users present at time slot t and

X f (t) = (X f 1 (t), . . . , X f K (t)
). Since the channel conditions are i.i.d. and independent of the process X f (•), the process X f is Markov. Hence, it is sufficient to focus on the Markovian description in terms of the number of users in each class, X f (•), instead of the number of users in each channel state.

Let us introduce some more notation. We denote by |x| the l 1 norm of a vector x. The notation x ≤ y is used for the coordinate-wise ordering: x i ≤ y i , ∀i. Finally, we denote by u.o.c. the uniform convergence on compact sets.

Performance criteria: Our performance criteria are stability and long-run average number of users. Definition 1. A scheduling policy f is stable if the process X f is positive recurrent.

Because of the time-varying channel conditions the system is not work-conserving, and hence it depends strongly on the employed scheduling policy whether the system can be made stable. We define the maximum stability conditions as the conditions on the traffic inputs such that there exists a policy that can make the system stable. A maximum stable policy is a policy that is stable under the maximum stability conditions. From the performance point of view it is therefore of crucial importance to design a scheduler that is maximum stable.

Besides stability, another important performance measure is lim sup

T →∞ 1 T K k=1 T -1 t=0 c k E(X f k (t)), (1)
the long-run time-average holding cost, with c k > 0 the holding cost incurred per time slot for having a class-k user in the system. When c k = 1, ∀ k, this is equivalent to minimizing the mean sojourn time (cf. Little's law).

Remark 1. From a modeling perspective, the key assumption needed for the subsequent fluid-limit analysis is that the channel state evolution is independent across users. However, we believe that a similar study could be carried out under a weaker assumption on a users' channel state process: stationary ergodicity. In this case, the steady-state probabilities of the channel process would play the role of the q k,n 's in the current model description. In particular all the results on stability and asymptotic optimality that will be obtained later on would hold in this more general setting. For the sake of clarity and to avoid technicalities in the proofs we have restricted our attention to i.i.d. channel states.

Remark 2 (Modeling of a wireless data network). Our model, even though simple, captures some of the key properties of wireless communication systems. Time is slotted, as is the case in the CDMA 1xEV-DO [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users[END_REF] and the OFDM-based LTE systems [START_REF] Sadiq | Downlink scheduling of multiclass traffic in LTE[END_REF]. The available transmission rate of each user fluctuates due to fading effects, and as a consequence, it varies from one slot to another. We note that in real systems the number of feasible transmission rates is finite (see [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users[END_REF]). One may classify the users into different classes based on their applications or traffic conditions for example. Let the service requirement (in bits) of a class-k user be a geometric random variable denoted by B k , and let E(B k ) denote its expectation. Let ∆ denote the amount of bits transferred in one slot under the current channel condition. Note that in practice ∆ will vary from slot to slot depending on the channel condition, and the allocation. The probability that a user leaves the system is approximately

P(b ≤ B k ≤ b + ∆|B k > b) ≈ ∆/E(B k )
, which does not depend on the attained service b (memoryless property of the geometric distribution). This expression becomes asymptotically exact as the ratio ∆/E(B k ) goes to 0. Hence, this is the case if the mean service requirement (in bits) of a user is very large compared to the amount of bits that can be served in one slot. Let s k,n denote the transmission rate (in bits per second) of a class-k user when the channel state is n. For the CDMA 1xEV-DO system, the amount of bits transferred in one slot is ∆ = s k,n • t c . Hence, the departure probability of a class-k user under channel condition n can be approximated by

µ k,n := s k,n • t c E(B k ) , ( 2
)
where t c is the length of the slot (for example t c = 1.67ms in the CDMA 1xEV-DO system). In Section VII we perform numerical experiments with departure probabilities as obtained from a practical setting using [START_REF] Andrews | Instability of the proportional fair scheduling algorithm for HDR[END_REF].

III. POLICIES

In this section we introduce scheduling policies that will be used throughout the paper. Most of these policies are opportunistic (with the exception of the cµ-rule), meaning that they take advantage of channel fluctuations by serving a user whose channel condition is currently in a good state, in some sense, with respect to its own statistical behavior.

We first introduce priority-index policies, which are very popular due to their simplicity from an implementation point of view. A priority-index policy is characterized by an index function that assigns an index to each user based solely on its class and its current state.

Definition 2 (Priority-index policy). In every time slot, a user that has the highest index among all users present is served.

Priority-index policies might need to be augmented with a suitable tie-breaking rule. Such a rule refers to the strategy adopted when there is a tie on the highest index value. A tie means that there are several users present having the highest index value, but these users belong to different classes. In the literature, most of the papers specify to break ties at random (see for example [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF], [START_REF] Berggren | Asymptotically fair transmission scheduling over fading channels[END_REF], [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF]). We define the myopic tiebreaking rule as the rule that among the users with the highest index, it selects the one with highest value for c k µ k,N k , ∀ k (the c k 's refer to the holding cost introduced in Section II.) One of our main contributions will be that the choice for the tie-breaking rule is crucial for the performance of the system and that the myopic tie-breaking rule is close to optimal (this will be further developed in Sections VI and Section VII).

In [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF] the Score-Based (SB) policy is introduced. SB is a priority-index policy where the index value of a class-k user in state n is given by n ñ=1 q k,ñ , and ties are broken at random. In [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF] the Potential Improvement (PI) policy is introduced. PI is a priority-index policy with as index value c k µ k,n / ñ>n q k,ñ (µ k,ñµ k,n ), and the tie-breaking rule is the myopic tie-breaking rule. An important subset of the priorityindex policies are the so-called weight-based policies.

Definition 3 (Weight-based policy). A priority-index policy with index function ω k µ k,n , with ω k a class dependent weight.

Examples of weight-based policies are: the cµ-rule (ω k = c k , with c k the holding cost), Relative Best (RB) [START_REF] Berggren | Asymptotically fair transmission scheduling over fading channels[END_REF]

(ω k = 1/ N k n=1 q k,n µ k,n
), and Proportionally Best (PB) [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF] (ω k = 1/µ k,N k ). For all these policies, ties are broken at random.

It will be convenient to define the following two classes of policies, which play an important role in the results on the stability analysis and asymptotic optimality.

Definition 4 (Best Rate (BR) policies). The BR policies are such that whenever there are users present that are currently in their best channel condition (state N k ) such a user is served.

Definition 5 (Best Rate Priority (BRP) policies). The BRP policies are BR policies with a myopic tie-breaking rule.

As a consequence of our main results, we will obtain that the classes of policies BR and BRP have desirable properties: In Section V we prove that any BR policy is stable under the maximum stability conditions and in Section VI we derive that BRP policies are asymptotically optimal.

In Figure 1 we have summarized the various (classes of) policies. Note that SB, PB and PI are BR policies. This follows since the highest possible index value is 1 for SB and PB, and ∞ for PI, and these indices can only be obtained whenever a user is in its best possible channel condition. RB and the traditional cµ rule (i.e., giving in each time slot strict preemptive priority to the user having the highest c k µ k,n ) however do not belong to BR policies since, depending on the set of parameters, the index value of a class-k user in state n = N k might be larger than the index value of a class-l user in state N l . Remark also that PI is the only BRP policy.

IV. FLUID LIMITS AND CONVERGENCE

In this section we study fluid-scaling limits for a large class of policies. The fluid scaling consists in studying a sequence of systems indexed by r, i.e., for a given policy f we let X f,r k (t) denote the number of class-k users at time t when the initial state equals X r k (0) = rx k (0), k = 1, . . . , K, with r ∈ N, and

X f,r (t) = (X f,r 1 (t), • • • , X f,r K (t)). We are then interested in the fluid-scaled processes Y f,r k (t) := X f,r k (⌊rt⌋) r , t ≥ 0, k = 1, . . . , K, with Y r (0) = x(0). We can write Y f,r k (t) = x k (0) + 1 r ⌊rt⌋ s=1 A k (s) - 1 r N k n=1 S k,n (T f,r k,n (rt)), (3)
where T f,r k,n (t) is defined as the cumulative amount of time that was spent on serving class k in state n during the interval (0, t] and S k,n (t) denotes the total number of class-k users that have been completed while receiving service for a total duration of time t when being in state n.

In order to derive stability and asymptotic optimality results, we will be interested in limits of the fluid-scaled process. In Section IV-A we will characterize a generic description of weak fluid limits (usually not unique) of Equation ( 3), following the same reasoning as in [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF]. In Section IV-B we focus instead on a special class of policies for which we can prove convergence in probability towards a unique limit, which will be referred to as the strong fluid limit. (In [START_REF] Fort | The ODE method for the stability of skip-free markov chains with applications to MCMC[END_REF] similar is done but only for a subset of the state space.) We discuss the differences between weak and strong fluid limits in more detail in Remark 5, after having introduced formally both concepts.

A. Convergence towards weak fluid limits

From (3), we obtain the following result that describes the generic characterization of weak fluid limits for a given policy f . The lemma will allow to determine maximum stable policies (Theorem V.2) and to characterize asymptotically optimal policies (Section IV).

Lemma IV.1. For almost all sample paths ω and any sequence r k , there exists a subsequence r k l such that for all k = 1, 2, . . . , K, n = 1, 2, . . . , N k , and t ≥ 0, Proof: The proof follows similarly to that of [13, Proposition 4.12]. Define A k (t) as the number of class-k users that arrive in time slot t. We note that A k (1), A k (2), . . . , are independent and distributed according to A k , with E(A k ) = λ k . Since µ k,n is the probability of completing a class-k user when it receives service while being at state n, by the law of large numbers, we obtain that, almost surely,

lim l→∞ Y f,r k l k (t) = y f k (t), u.o.c., and (4)
lim l→∞ T f,r k l k,n (t) r k l = τ f k,n (t), u.o.c., with (y f k (•), τ f k,n (•)) a continuous function. In addition, y f k (t) = x k (0) + λ k t - N k n=1 µ k,n τ f k,n (t), (5)
y f k (t) ≥ 0, τ f k,n (0) = 0, k,n τ f k,n (t) ≤ t,
lim r→∞ 1 r ⌊rt⌋ s=1 A k (s) = λ k t, and lim r→∞ 1 r S k,n (rt) = µ k,n t. (6) We define T f,r k,n (t) := T f,r k,n (rt)/r. Since T f,r k,n (t) denotes the cumulative amount of time spent on serving class-k users in state n in time interval [0, t], we get T f,r k,n (rt) -T f,r k,n (rs) ≤ t -s, for every t ≥ s, i.e., T f,r k,n (t) is Lipschitz continuous.
By the Arzela-Ascoli theorem [START_REF] Renardy | An introduction to partial differential equations[END_REF] we obtain that, for almost every sample path w and any subsequence r k , there exists a subsequence r k l of r k such that lim l→∞ T f,r k l k,n (rt)/r = τ f k,n (t), u.o.c.. Now, using Equations ( 3) and ( 6), it follows that

lim l→∞ Y f,r k l k (t) = y f k (t)
, with y f (t) as given in [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users[END_REF]. ✷ We can now give our definition of weak fluid limits. Definition 6. We call the processes τ f (t) and y f (t) (as obtained in Lemma IV.1) weak fluid limits for policy f . Note that, in general, these fluid limits can be different depending on the sample path and the subsequence considered. A policy is said to have a unique fluid limit if, for all sample paths and all subsequences, the weak fluid limits coincide.

B. Convergence towards a strong fluid limit

In this subsection we will determine unique fluid limits for a special class of policies. More precisely, we will prove convergence in probability towards a unique limit. The derivation of the strong fluid limit will prove to be very useful: It allows to calculate the exact stability conditions (policy dependent) (see Theorem V.1 and the numerical Section VII). In addition, the exact characterization of the strong fluid limit provides crucial insights into the performance of the system, such as the growth rates of the number of users over time and monotonicity results with respect to the tie-breaking rule.

Obtaining exact fluid-limit characterizations will require to deal with averaging phenomena: it may happen that one class of users reaches its stationary regime, i.e., is empty in the fluid scaling, before the other classes do. In this case, the drift of the other classes needs to be averaged with the stationary distribution of this class. Hence, a description of the fluid limit will involve averaged drifts as will be defined in [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF] (we refer to this as second-vector fields, following [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF]).

We focus on the class of policies that induce partially increasing drift vector fields with uniform limits. In order to describe this class of policies we need first to introduce the drift functions and drift vector fields. For the stochastic process X f (t) associated with a policy f , we define the drift function by

δ f (x) := (δ f 1 (x), . . . , δ f K (x)), x ∈ N K , with δ f i (x) := E(X f i (1) -x i |X f (0) = x)
. (We will drop the superscript f when it is clear that we consider a unique policy.) We say that a vector field v : N K → R K has uniform limits [START_REF] Borst | Stability of parallel queueing systems with coupled service rates[END_REF] if for any U ⊂ {1, . . . K}, there exists a function v U :

N |U | → R K (constant when U = ∅) such that lim R→∞ sup x∈N K :|x U c |>R |v(x) -v U (x U )| = 0,
where x U denotes the restriction of the vector x to indices in the subclass U and U c denotes the complementary set of U . Intuitively, this means that the drift vector-field has limits when we make the number of users of some of the classes go to infinity, and that we can interchange the order of the coordinates when taking these limits. We assume in the following that the drift vector has uniform limits, so that we can define the asymptotic drifts δ U : N |U | → R K as follows:

δ U (x U ) := lim x k →∞, k∈U c δ(x). (7)
Here, U c corresponds to the "saturated" classes for which we let the number of users go to ∞. We define the stochastic process X U as the U -dimensional stochastic process corresponding to the original process seeing an infinite number of users of class k ∈ U c and let π U denote its stationary measure assuming it exists. We define the averaged drift vectors by

δU = x∈N |U | δ U (x)π U (x). (8)
Finally, following [START_REF] Borst | Stability of parallel queueing systems with coupled service rates[END_REF] we say that a vector field v is partially increasing if v i (x) is increasing in x j for all j = i. These assumptions, which are crucial to prove the convergence towards the unique strong fluid limit, are verified for many cases of interest, see the next lemma.

Lemma IV.2. A priority index policy or a BR policy with nonstate dependent tie-breaking rule (i.e., independently of the numbers of users) induces a partially increasing drift vector field with uniform limits.

Proof: We prove the lemma for BR policies, the other case being similar. When increasing the number of users of one class only, the probability that this class has at least one user in its best possible state is increased. Hence, given that the tie-breaking rule does not depend on the number of users, the probability that this class is served is increased while the probability that a user of another class is served decreases. This implies that the drift vector field is partially increasing. By the independence of the channel variations, the probability that class i ∈ U c has at least one user in its best state is 1 -(1q i,Ni ) xi , where x i is the number of class-i users. Hence, when the numbers of class-i users, i ∈ U c , grows large, the probability of having in each class in U c at least one user in its best state (and hence causing a drift δ U (x U )) converges to 1. Together with the property that the tie-breaking rule does not depend on the number of users, this implies that

δ(x) = δ U (x U ) i∈U c (1 -(1 -q i,Ni ) xi ) + o(1/|x|), (9)
as x k → ∞, k ∈ U c , which in turn implies the uniform convergence of δ(•) to δ U (•) for any U . ✷

We now state the main result of this Section, the description of the strong fluid limit. The proof can be found in Appendix A.

Theorem IV.3. For a given policy f inducing a partially increasing drift vector field with uniform limits, we have

lim r→∞ P( sup 0≤s≤t |Y f,r (s) -y f (s)| ≥ ǫ) = 0, for all ǫ > 0,
with y f (t) a piece-wise linear function that can be described recursively as follows. Let U 0 = ∅ and T 0 = 0. Then we have,

dy f k (t) dt = δf,U l k , t ∈ [T f l , T f l+1 ], ( 10
)
with T f l+1 = T f l + min k∈U c l , δU l k <0 y f k (T f l ) -δf,U l k , (11)
and

U l+1 = U l ∪ arg min k∈U c l , δU l k <0 y f k (T f l ) -δf,U l k , (12)
and if there exists no k ∈ U c l with δf,U l k < 0, then T f l+1 = ∞. We can now give our definition of the strong fluid limit. Definition 7. For a given policy f inducing a partially increasing drift vector field with uniform limits, we call the process y f (t) (as obtained in Theorem IV.3) the strong fluid limit for the policy f . Remark 3 (Calculation of the averaged drifts). Theorem IV.3 characterizes the strong fluid limit as a piece-wise linear function with slopes δU . In practice, the calculations of these slopes involve:

• deriving the asymptotic drifts (see [START_REF] Billingsley | Convergence of Probability Measures[END_REF]),

• calculating the stationary distributions of X U ,

• averaging the asymptotic drifts with these stationary distributions (see [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF]). For instance, assume K = 2, N 1 = 2, N 2 = 1, and a Bernoulli arrival process. Consider the policy that gives priority to the best class-1 user present in the system and otherwise (i.e., when there is no class 1) serves a class-2 user. Then

δ ∅ = (λ 1 -µ 1,N1 , λ 2 ), δ {1} (x 1 ) = (λ 1 -s 1 (x 1 ), λ 2 -µ 2,N2 1 (x1=0) ), with s 1 (x 1 ) = µ 1,N1 (1-(1-q 1,N1 ) x1 )+µ 1,N1-1 (1-q 1,N1 ) x1 .
The process X {1} is a 1-dimensional Markov chain with stationary distribution

π {1} (x 1 ) = C x1 j=1 λ 1 (1 -s 1 (j -1)) (1 -λ 1 )s 1 (j) ,
where C is a normalization constant. The average drift can now be computed using [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF].

In the specific case of BR policies with a priority-type tiebreaking rule, we can in fact explicitly derive the strong fluid limit by making use of rate-conservation arguments. This will be used later on to obtain asymptotic optimality statements.

Proposition IV.4. Consider a BR policy with a priority-type tie-breaking rule. Let us reorder the classes according to the priority ordering. The averaged drift vectors are

δ∅ = (λ 1 -µ 1,N1 , λ 2 , . . . , λ K ), ( 13
) if T 1 < ∞, then δ{1} = (0, λ 2 -µ 2,N2 1 - λ 1 µ 1,N1 , . . . , λ K ), (14
)

and if T k-1 < ∞, then U k-1 = {1, . . . , k -1} and δU k-1 = (0, . . . , 0, λ k -µ k,N k (1 - k-1 j=1 λ j µ j,Nj ), . . . , λ K ). ( 15
)
Proof: Using Lemma IV.2, the drift δ(•) associated to a BR policy is partially increasing with uniform limits, hence the strong fluid limit is given by Theorem IV.3. When U = ∅, there are infinitely many users of each class and hence there is always a class-1 user in its best state, which directly implies [START_REF] Bramson | Stability of queueing networks[END_REF]. Note that T 1 < ∞ if and only if λ1 µ1,N 1 < 1 (see definition of T 1 in Theorem IV.3). In this case the process X {1} is ergodic. For T 1 ≤ t ≤ T 2 , we can simplify the asymptotic drift δ{1} using the specific properties of the policy and rate conservation arguments: let A 1,x1 be the event that class 1 is served and there are x 1 class-1 users when all the other classes are saturated. With a slight abuse of notation, let us denote by π {1} (A 1,x1 ) the probability of event A 1,x1 under the stationary distribution of X {1} . Since X {1} is ergodic, by rate stability we have the following rateconservation equation,

x1 π {1} (A 1,x1 )µ 1,N1 = λ 1 , see (45) This gives that x1 π {1} (A c 1,x1 ) = 1-λ1 µ1,N 1
. Since U 1 = {1} (so in particular there is still an infinite amount of class-2 users which are exclusively served when there are no class-1 users in their best state) class 2 receives service at rate

µ 2,N2 x1 π {1} (A c 1,x1 ) = µ 2,N2 (1 -λ1 µ1,N 1
) which gives [START_REF] Chaponniere | Transmitter directed code division multiple access system using path diversity to equitably maximize throughput[END_REF]. Consider now the case where U := {1, . . . , k-1} (assuming as before that k-1 j=1 λj µj,N j < 1). Let A j,xU be the event that class j ∈ U is served and there are x i users of class i, i ∈ U. By rate-conservation arguments, see (45), we obtain xU π U (A j,xU )µ j,Nj = λ j , j ∈ U.

Noting that the sets A j,xU are disjoints, ∀ j ∈ U, this implies that xU π U (∪ j∈U A j,xU ) = j∈U λj µj,N j . Since class k is only served when no class-i users are being served, i ∈ U , there is a class-k departure with probability µ k,N k (1 -xU π U (∪ j∈U A j,xU )). Hence, we obtain Equation [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF]. ✷ Remark 4. For all BR policies where the scheduler chooses with probability α U k to serve class k when a subset U of classes has at least one user in its best channel condition, the fluid limit in the interior of the orthant has a drift given by:

δ ∅ = (λ 1 -α {1,...,K} 1 µ 1,N1 , λ 2 -α {1...,K} 2 µ 2,N2 , • • • , λ K -α {1,...,K} K µ K,NK ). ( 16
)
However, in general we cannot explicitly derive the secondvector fields. An exception is the case of two classes. Then, using the rate-conservation argument as in the previous proposition, we obtain (assuming w.l.o.g. that class 1 empties first)

δ{1} = (0, λ 2 -(1 - λ 1 µ 1,N1
)µ 2,N2 ).

Remark 5 (Weak and strong fluid limits). Though a quite subtle technical point, it is worth emphasizing the conceptual difference between the notion of weak fluid limits and the notion of strong fluid limit, introduced in Sections IV-A

and IV-B, respectively. Note that "weak" versus "strong" refers to accumulation points versus unique limit. The names do however not take into account the mode of convergence. Weak limits are a powerful tool for stability if one can characterize that they all vanish after a finite amount of time, as will be used in Theorem V.2 for the set of BR policies. However, in general weak limits might not capture the precise asymptotic behavior of the process (see [START_REF] Bramson | Stability of queueing networks[END_REF]). On the contrary, when having a unique strong fluid limit, the asymptotic behavior of the scaled process is completely described, allowing for example to obtain the policy-dependent stability conditions for a large class of policies (see Theorem V.1).

V. STABILITY ANALYSIS

The derivation of the weak and strong fluid limits in Section IV allows us to conclude for stochastic stability results. The first Theorem derives the stability conditions for any policy having a partially increasing drift with uniform limits, using the strong fluid limit as obtained in Theorem IV.3. Theorem V.1. A policy f inducing a partially increasing drift vector field with uniform limits is stable if T f l < ∞ for all l, where T f l is given by Theorem IV.3. Proof: If T f l < ∞ for all l, the strong fluid limit described in Theorem IV.3 is equal to 0 for t large enough, i.e., Y f,r (t) converges in probability to 0 for t large enough. In addition, the random variable Y f,r k (t) is uniformly integrable. This can be seen by the fact that Y f,r k (t) can be upper bounded by

x k (0) plus the users that have arrived until time ⌊rt⌋ divided by r, which is uniform integrable, see [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF]Lemma 4.5].

The convergence in probability to 0 and the uniform integrability together imply that lim r→∞ E(Y f,r k (t)) = 0, for t large enough, ∀ k, see [START_REF] Billingsley | Convergence of Probability Measures[END_REF]Theorem 3.5]. Using an extended Foster-Lyapunov criterion as expressed in [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF] or [START_REF] Ph | Stochastic Networks and Queues[END_REF]Corollary 9.8], this implies the positive recurrence of X f (•). ✷

In the following theorem we state the maximum stability condition, and prove that any BR policy achieves maximum stability. The proof is based on the weak fluid limit characterization as given in Section IV and can be found in Appendix B.

Theorem V.2. The maximum stability condition is

K k=1 λ k µ k,N k < 1. ( 17
)
In addition, any BR policy is maximum stable.

Condition [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF] was recognized as the maximal rate stability condition in [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF] and as the maximum stability condition under a time-scale separation assumption in [START_REF] Borst | User-level performance of channel-aware scheduling algorithms in wireless data networks[END_REF].

We note that SB, PI and PB are stable under the maximum stability conditions (they belong to the class of BR policies). The intuition behind Theorem V.2 is that asymptotically the system under a BR policy behaves as a classical workconserving system where class k has departure probability µ k,N k . On the contrary, other policies, including RB and the cµ-rule, spend (at the fluid scale) a non-negligible fraction of time serving users that are not in their best states, and are therefore not maximum stable. For an example, we refer to Section VII where we numerically obtain the stability conditions for RB and the cµ-rule, making use of Theorem V.1.

Remark 6 (Overload). When K k=1 λ k /µ k,N k > 1 the system is said to be in overload. That is, there does not exist any policy that can make the system stable. Theorem IV.3 is however still applicable, providing us with the rates at which the number of users in the different classes grow: given x(0) = 0, the growth rate of the number of users over time is given by X f,r (r)/r = Y f,r (1), which in the limit is equal to δ f,U . This gives us a mean to compare the performance of various policies in overload (see as well Sections VI and VII).

VI. ASYMPTOTIC OPTIMALITY

Besides stability, another important performance measure concerns the long-run average holding cost as given in [START_REF] Aalto | Flow-level stability and performance of channelaware priority-based schedulers[END_REF]. Deriving an optimal policy with respect to this criterion is difficult and the size of the state space makes the problem intractable. For this reason we introduce a related deterministic control problem, which allows us to prove that any BRP policy is asymptotically optimal for the original stochastic system. This emphasizes the important role of the tie-breaking rule in order to achieve efficient performance of the system.

We study the following deterministic fluid control model, which arises from the original stochastic model by only taking into account the mean drifts, i.e.,

min u K k=1 c k x u k (t)
, for all t ≥ 0, subject to (18)

x u k (t) = x k (0) + λ k t - N k n=1 µ k,n t 0 u k,n (v)dv, (19)
x u k (t) ≥ 0, k = 1, . . . , K, (20)
K k=1 N k n=1 u k,n (v) ≤ 1, u k,n (v) ≥ 0, ∀ k, n, v ≥ 0, (21)
and the control functions u k,n (v) being integrable. Here x u k (t) represents the amount of fluid in class k under control u(•).

We remark that though in general the fluid limit of a policy does depend on the distributions of the random environments (i.e., the q k,n 's), these do not appear in the above equations of the fluid control model. This is because the fluid trajectory x k (t) should be interpreted as a limit of the fluid-scaled process. Hence, when x k (t) > 0 this implies that there are infinitely many class-k users so that with probability 1 there are class-k users in each of the channel state conditions (this being independent of the exact values of the q k,n > 0's).

An optimal control u * (•) is derived in the following lemma.

Lemma VI.1. Assume c 1 µ 1,N1 ≥ c 2 µ 2,N2 ≥ . . . ≥ c K µ K,NK .
The fluid control u * (•) that solves the fluid control problem is as follows. Let l = arg min{k :

x k (t) > 0}. Then u * k,N k (t) = λ k µ k,N k , for k < l, u * l,N l (t) = 1 - l-1 i=1 λ i µ i,Ni
, and u * k,n (t) = 0 otherwise. Proof: Let us denote w u k (t) = x u k (t)/µ k,N k . First, we show that for any feasible control u(•), we have

j k=1 w u * k (t) ≤ j k=1
w u k (t), for all t ≥ 0, j = 1, . . . , K. (

If j k=1 w u * k (t) = 0, then [START_REF] Lassila | Combining opportunistic and size-based scheduling in wireless systems[END_REF] trivially holds. Now assume j k=1 w u * k (t) > 0. By definition of u * (•) this implies that j k=1 w u * k (s) > 0, for all s ∈ [0, t], since once all these classes empty under u * (t), they will remain empty. Since u * (t) gives full priority to classes 1 until j over classes j + 1 until K, we have that

j k=1 t 0 u * k,N k (v)dv = t. Hence, j k=1 t 0 u * k,N k (v)dv = t ≥ j k=1 N k n=1 t 0 u k,n (v)dv ≥ j k=1 N k n=1 t 0 µ k,n µ k,N k u k,n (v)dv, which implies (22), since j k=1 w u k (t) - j k=1 w u * k (t) = j k=1 t 0 u * k,N k (v)dv - j k=1 N k n=1 t 0 µ k,n µ k,N k u k,n (v)dv ≥ 0.
The minimization term K k=1 c k x u k (t) can be written as

K k=1 c k µ k,N k w u k (t) = (c 1 µ 1,N1 -c 2 µ 2,N2 )w u 1 (t) + • • • + (c K-1 µ K-1,NK-1 -c K µ K,NK ) K-1 k=1 w u k (t) + c K µ K,NK K k=1 w u k (t).
Together with ( 22) and c j µ j,Njc j+1 µ j+1,Nj+1 ≥ 0, ∀ j, we obtain that

K k=1 c k µ k,N k w u k (t) is minimized by u * (•). ✷
The optimal fluid cost serves as a lower bound for the fluidscaled cost of the stochastic network, see the lemma below.

Lemma VI.2. For any policy f and for almost all sample paths, we have

lim inf r→∞ K k=1 c k Y f,r k (t) ≥ K k=1 c k x u * k (t), for all t ≥ 0. ( 23
)
Proof: Lemma IV.1 states that for almost all sample paths we have lim inf r→∞ Y f,r k (t) = y f k (t), with y f k (t) a weak fluid limit for policy f (this follows by considering the subsequence r l corresponding to the liminf-sequence in Lemma IV.1). Note that a weak fluid limit is an admissible trajectory for the fluid control problem. Hence, lim inf r→∞

K k=1 c k Y f,r k (t) = K k=1 c k y f k (t) ≥ K k=1 c k x u * k (t). ✷
Since [START_REF] Liu | Throughput-optimal scheduling in the presence of flow-level dynamics[END_REF] holds almost surely, it follows by Fatou's lemma that the lower bound holds in probability as well, i.e.,

P( K k=1 c k Y f,r k (t) - K k=1 c k x u * k (t) ≥ 0) → 1, for all t ≥ 0.
(24) We define a policy to be asymptotically optimal when the lower bound is obtained in probability, i.e., ∀ǫ > 0,

lim r→∞ P(| K k=1 c k (Y f,r k (s) -x u * k (s))| ≥ ǫ) = 0.
The next Theorem characterizes a class of policies that is asymptotically optimal.

Theorem VI.3. Any BRP policy is asymptotically optimal.

Proof: We have

dx u * k (t) dt = λ k -u * k,N k (t)µ k,N k , with u * (•)
an optimal control as derived in Lemma VI.1. This drift coincides with the drift of the strong fluid limit y BRP (•), see Proposition IV.4, hence y BRP (t) = x u * (t). Together with Theorem IV.3, we obtain that lim r→∞

K k=1 c k Y BRP,r k (t) converges in probability to K k=1 c k x u * k (t). ✷
It can be checked that the above implies that any BRP policy minimizes lim inf r→∞ E(

∞ 0 c k Y f,r k (t)dt).
Unfortunately, this does not give any performance guarantee in terms of the long-run time-average holding cost as in Equation (1). Numerical experiments reported in Section VII indicate however that BRP policies significantly outperform all other policies in terms of the long-run time-average holding cost.

Note that the optimality results described in this section also apply in overload systems. We have the following corollary for the total growth rate.

Corollary VI.4. Any BRP policy minimizes the growth rate of the total cost, i.e., for all ǫ > 0,

lim r→∞ P K k=1 c k X r,f k (r) r - K k=1 c k X r,BRP k (r) r ≥ -ǫ = 1.
Proof: Combining (24) with the asymptotic optimality of a BRP policy, the statement is immediate. ✷

To the best of our knowledge, the only policy studied in the literature that belongs to BRP, and hence is both maximum stable and asymptotically optimal, is PI. We recall that PI was derived in [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF] as the solution of a relaxed optimization problem. SB and PB will as well become asymptotically optimal when the myopic tie-breaking rule would be applied, showing the importance of the tie-breaking rule.

Remark 7. From Theorem VI.3 we conclude that the myopic tie-breaking rule is crucial in order to obtain an asymptotically optimal scheduling policy. In view of Equation ( 2), we note that under this myopic rule, higher priority is given to users with smaller service requirements, E(B k ). Hence, BRP policies appropriately mix size-based information with achieving opportunistic gains. This is in agreement with the findings of [START_REF] Sadiq | Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics[END_REF] where the authors investigate the tradeoff between prioritizing small users and opportunistic scheduling: They show that if the opportunistic capacity is upper bounded and increases as 1a x , with a ∈ [0, 1) and x the number of users, then a significant improvement of performance can be achieved by exploiting information on the service time requirement. In our model the capacity has this behavior, see for instance Equation ( 9), and as will be observed in the numerical results, exploiting size-based information indeed allows to obtain significant improvements.

Remark 8. In the asymptotic regime, the optimal tie-breaking rule is to give priority based on µ k,N k . However, outside this regime the optimal tie-breaking rule will depend both on the µ k,N k 's and on the probabilities that users are in their best channel condition, the q N k ,k 's. The reason for this is that in the asymptotic regime there are many users in the system, which is why the q k,N k 's become irrelevant in the limit (as the number of users grows to infinite, the probability of having one best-rate user becomes equal to 1). Note however that our numerical simulations in the next section suggest that outside the asymptotic regime the asymptotically optimal tie-breaking rule performs very well as well.

VII. NUMERICAL EXPERIMENTS

We consider a CDMA 1xEV-DO system with two classes of users (K = 2). Time is slotted, with the length of one slot being t c = 1.67ms. In each time slot, one new class-k user arrives with probability λ k . We choose 10.257 kb as the expected service requirement of both a class-1 and class-2 user. Associated to the state of the channel, we have transmission rates (kb/s), see Table I (taken from [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users[END_REF]).

We simulate the queueing system as described in Section II. We assume that class-1 users have five possible transmission rates while class-2 users have three. The corresponding probabilities (q k,n ) are given in Table I. In addition, applying Equation (2) we calculate the departure probabilities (µ k,n ). We fix λ 2 = 0.05, so λ 2 /µ 2,N2 = 0.5. We set c 1 = c 2 = 1, so that we are interested in minimizing the expected total number of users in the system, see Equation (1). We will compare the performance of the policies SB, RB, PI, PB and the cµ rule, which were introduced in Section III.

Before presenting the numerical results we first summarize the main conclusions that we will make in this section:

• For different policies we validate the convergence of the system towards its fluid limit. • We prove that not all policies obtain maximum stability.

More precisely, we calculate the stability conditions under [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic users[END_REF].

RB and the cµ-rule and observe that these are much more stringent than the stability condition for BR policies.

• The drifts of the fluid limit, δ U , which are calculated numerically (and in some cases theoretically), provide very important insights on the performance. In particular, insightful monotonicity results in the tie-breaking rule are obtained with respect to the performance of the system. In addition, the drift analysis allows to show that PI outperforms all other policies in terms of the growth rates. • Our simulations illustrate that the tie-breaking rule has a big impact on the performance of the system and we find that BRP policies, i.e., policies that combine opportunistic scheduling with the myopic tie-breaking rule, minimize the long-run time-average holding cost (see ( 1)). a) Fluid limit: We first illustrate how the scaled process converges to the fluid limit. We take r = 10000, Y r (0) = X(0)/r = (1, 1) and plot the scaled processes Y r 1 (t), Y r 2 (t), and Y r 1 (t) + Y r 2 (t) for different policies, see Figure 2. In this simulation we set λ 1 = 0.14, so λ 1 /µ 1,N1 = 0.35.

We describe the fluid limit y f (t) as defined in Theorem IV.3. When both classes are saturated, i.e., U = ∅, the drift is

δ f,∅ = (λ 1 -α f µ 1,N1 , λ 2 -(1 -α f )µ 2,N2 ), (25)
see Remark 4. Here α f is a random tie-breaking rule, i.e., in case of a tie, α f is the probability that class 1 is favoured over class 2. For our set of parameters, the best class-1 user under the cµ-rule and RB is always preferred over the best class-2 user, i.e., there occur no ties, hence one can set α f = 1 in (25) for f = cµ, RB. For PI, SB and PB we do have ties, and we set α P I = 1 (since PI applies the myopic tiebreaking rule) and α SB = α P B = 1/2 (since SB and PB apply a random tie-breaking rule). In Table II we present the soobtained values for δ f,∅ . From the drifts it is clear that under all policies class 1 empties before class 2. The moment that this happens, T f 1 , can be derived from Theorem IV.3 and satisfies

T P I 1 = T cµ 1 = T RB 1 < T SB 1 = T P B
1 , see also Figure 2 a). For T f 1 < t ≤ T f 2 , the drift of class 1 is 0, whereas the drift of class 2 depends on the policy. From Proposition IV.4 we have that for all BR policies (e.g. PI, SB and PB) δ f,{1} = (0, λ 2µ 2,N2 (1λ 1 /µ 1,N1 )). For the cµ rule and RB we calculate the drift numerically using Remark 3, see Table II. In particular we observe that these drifts are positive for the latter two policies, which implies instability of the system, as can be seen in Figure 2 b). We observe that for t ≤ T f 1 the number of class-2 users increases under policies PI, cµ and RB, while for SB and PB, the drift of class-2 users is negative.

δ f,∅ δ f,{1}
We note that the slopes of the strong fluid limit indeed coincide with the slopes of the original process, Y r (t) (r = 10000), as plotted in Figure 2.

A direct consequence of the drift function is that SB, PB, and PI (in fact all BR policies) empty the system at the same time (under the maximum stability condition), i.e., T f 2 is the same (this can be seen directly from Equation (44) for example). However, the performance of a policy will depend on the order in which classes are served. In the fluid limit, this is fully determined by the choice of the tie-breaking rule. Note that, as can be seen from Figure 2 c), PI, (and hence any BR policy with the myopic tie-breaking rule) minimizes the total number of users at any moment in time.

b) Stability region: We now vary the value of λ 1 from 0.004 to 0.196, and as a consequence we have that ρ := λ 1 /µ 1,N1 + λ 2 /µ 2,N2 varies from 0.51 to 0.99. The policies PI, PB and SB belong to the BR policies, and are hence stable when ρ < 1. For the cµ-rule and RB the stability condition can be numerically calculated as follows: First, we calculate the stationary distribution of class-1 users once the stationary regime is reached. Then, we calculate the average drift δf,{1} according to Definition [START_REF] Bonald | A score-based opportunistic scheduler for fading radio channels[END_REF]. Policy f is stable if δf,{1} 2 < 0, which reduces to ρ < 0.79 for the cµ-rule and to ρ < 0.84 for RB. In Figure 3 a) we plot the mean number of users for different values of ρ and we observe that the mean number of users (and hence the mean delay) for these policies grows to infinity as the load ρ approaches the critical value.

c) Impact of Tie-Breaking rule: We study the impact of the tie-breaking rule on the performance of the system. In order to investigate this issue in more depth, we simulate PI under different random tie-breaking rules, i.e., we let the probability α vary from 0 until 1 (Recall that the parameter α is the probability, in case of a tie, that class 1 is favoured over class 2). We emphasize that PI as defined in [START_REF] Ayesta | A modeling framework for optimizing the flow-level scheduling with time-varying channels[END_REF] uses by default the myopic tie-breaking rule, i.e., α P I = 1. In Figure 3 b) we plot the relative degradation (in terms of the mean number of users) over PI as we vary α. We observe that the degradation in the mean performance is decreasing as α increases. In the fluid-scaling system a similar observation can be made: from [START_REF] Neely | Order optimal delay for opportunistic scheduling in multiuser wireless uplinks and downlinks[END_REF] and Remark 4 it follows that the drift of the total number of users of the strong fluid limit (as obtained in Theorem IV.3) is decreasing (or constant) in α, for all time t.

δ f,∅ δ f,{1}
The results show that the myopic tie-breaking rule, which was proven to be asymptotically optimal in the fluid limit (see Theorem VI.3), is in practice indeed optimal when minimizing the mean number of users. In addition, the relative degradation of the tie-breaking rule with α = 1/2 (compared to the myopic tie-breaking rule α P I = 1) can be very large. For example, for ρ = 0.8 the degradation is 29% and for ρ = 0.9 it is 45%. d) Overload: In Figure 3 c) we plot a trajectory of the total scaled number of users Y r 1 (t) + Y r 2 (t) (for r = 100) when λ 1 = 0.240 and ρ = 1.1, so all policies are unstable. In Table III we give the values for the drifts (growth rates) of the fluid limit y f (t). In this example, the worst performance is under SB/PB and the best performance is for PI. This is in contrary to the stable regime where SB/PB is maximum stable with a performance strictly better than the cµ-rule and RB, see Figure 3 a). This implies that the performance of this policy can differ very much between stable and overload regimes. In addition, the total growth rate of the system is always minimized under any BRP policy, that is a best-rate policy with the myopic tie-breaking rule, as proved in Corollary VI.4.

VIII. CONCLUSION

We have characterized the classes of policies that are maximum stable and asymptotically optimal in a system with random environment. An important conclusion, validated by numerical experiments, is that the tie-breaking rule has a tremendous impact on the performance. Our analysis also shows that simple priority-index policies like PI or SB with a cµ tie-breaking rule, are stable and asymptotically optimal. While in this model we assumed geometric service requirements, we do believe that direct extensions of all our results exist for phase-type distributed service requirements. In particular, we expect that an optimal tie-breaking rule will be of a simple priority-index type.

Lemma VIII.1. Suppose δ f (•) has uniform limits. Then for any U and any compact set C ⊂ R |U c | ++ there exists an L > 0 and ǫ r with lim r→∞ ǫ r = 0 such that

|δ f (x) -δ U ,f (x U )| ≤ ǫ r + L| x U c r -y|, ∀x ∈ R K + , x U c ∈ R |U c | ++ , y ∈ C ⊂ R |U c | ++ . (26)
Proof: Consider ǫ > 0, and y ∈ C such that

y i > ǫ, ∀i ∈ U c . Define B ry,rǫ ⊂ R |U c |
++ the ball of center ry and radius rǫ. Assume that the drift function δ(•) has uniform limits. Hence,

ǫ r = sup y∈C sup x U c ∈Bry,rǫ |δ f (x)-δ U ,f (x U )|, converges to 0, as r → ∞. Since | x U c r -y| ≥ ǫ when x U c / ∈ B ry,rǫ , we obtain that |δ f (x) -δ U ,f (x U )| ≤ sup x U c ∈Bry,rǫ |δ f (x) -δ U ,f (x U )| + + sup x U c / ∈Bry,rǫ |δ f (x) -δ U ,f (x U )| ≤ ǫ r + L| x U c r -y|, with L := 2 max k,n (λ k ,µ k,n ) ǫ ≥ sup x U c / ∈Bry,rǫ |δ f (x)-δ U ,f (xU )| ǫ . ✷
In what follows, we will use the martingale decomposition of the process (see [START_REF] Williams | Probability with martingales[END_REF]), i.e., we define M (•) such that

X(t) = X(0) + t-1 s=0 δ(X(s)) + M (t), (27)
where M is a martingale, and |M (0)| = 0. The following lemma gives a useful property for the martingale M (t).

Lemma VIII.2. It holds that E |M k (t)| 2 ≤ C ′ t, ∀k = 1 . . . , K, for some constant C ′ > 0.
Proof: Using that the drift is bounded and the arrival increments have a finite variance, it immediately follows from ( 27)

that E |M k (t)| 2 < ∞, ∀t. Hence, E |M k (t)| 2 (28)
≤ E |M k (0)| 2 + t s=1 E |(M k (s) -M k (s - 1
(t) -M k (t -1)| ≤ |X k (t) -X k (t -1)| + |δ(X i (t -1))|.
Since the drift is bounded, and the arrival process has finite mean and variance, this implies that

E |M k (t) -M k (t -1)| 2 ≤ C ′ , with C ′ > 0 a constant.
Thus, the statement follows from [START_REF] Ph | Stochastic Networks and Queues[END_REF]. ✷

We prove Theorem IV.3 for two classes of users, the general case being notationally much more cumbersome but mathematically equivalent. The trajectory of the fluid limit is defined piece-wise. We refer as the first part of the fluid limit to the case t < T 1 , and as second part of the fluid limit to the case T 1 ≤ T 2 , and we shall prove the convergence separately for the two parts. The basic techniques used to prove the convergence of the first part of the trajectory are fairly standard and we proceed using the tools of [START_REF] Fort | The ODE method for the stability of skip-free markov chains with applications to MCMC[END_REF]. Let us however emphasize that the proof relies crucially on the extended Lipschitz condition [START_REF] Park | Wireless packet scheduling based on the cumulative distribution function of user transmission rates[END_REF]. Verifying this condition might be difficult in practice. In Lemma VIII.1, combined with Lemma IV.2, we however showed that the conditions are satisfied for various scheduling policies of interest. Proving the convergence of the second part of the trajectory is much more subtle as it involves an averaging phenomena: one of the classes reaches a stationary regime while the other class keeps being macroscopically big. We must therefore rely on stochastic comparisons and on the ergodic theorem for Markov chains. Such phenomena have been observed and analyzed in [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF] for homogeneous random walks in the positive orthant.

First part of the trajectory: Assume strictly positive initial conditions for both classes, i.e., x 1 (0) > 0 and x 2 (0) > 0. At time t = 0 all classes are saturated, hence in the first part of the trajectory, t < T 1 , we need to consider U = U 0 = ∅. Consider the deterministic function y(•) as defined in the theorem, y(t) = x(0) + δ ∅ t, and we define an error function e r (t) := E sup 0≤s≤t |Y r (s)y(s)| . From [START_REF] Renardy | An introduction to partial differential equations[END_REF]

We now control the drift part in Equation [START_REF] Sadiq | Delay-optimal opportunistic scheduling and approximations: The log rule[END_REF]. Since the drift has uniform limits, we obtain from Lemma VIII.1 that |δ(X r (s))δ ∅ | ≤ ǫ r + L| X r (s) r y( s r )|, ∀ s ≤ rt. Hence, bounding the Riemann sum for piece-wise constant functions by an integral, there exists a κ > 0 such that

Together with ( 29), ( 30) and ( 32 Hence, for any ǫ > 0 there exists r 0 such that, for a C ′′ > 0, e r (t) ≤ C ′′ ǫt + t 0 e r (s)ds , for r ≥ r 0 . Using Gronwall's lemma [START_REF] Renardy | An introduction to partial differential equations[END_REF], we obtain that for any r ≥ r 0 , e r (t) ≤ C ′′ ǫt 1 + e t t 0 e -s ds ≤ C ′′ ǫt 1 + te t , for all t < T 1 . Hence, lim r→∞ e r (t) = 0 for t < T 1 . Since e r (t) = E(sup 0≤s≤t |Y r (s)y(s)|) ≥ P(sup 0≤s≤t |Y r (s)y(s)| > ǫ ′ ) • ǫ ′ , we obtain lim r→∞ P(sup 0≤s≤t |Y r (s)y(s)| > ǫ ′ ) = 0, for t < T 1 .

In case T 1 = ∞, the Theorem IV.3 is now proved ∀t > 0. In the remainder of the proof we therefore assume that T 1 < ∞.

Second part of the trajectory (one stationary class): We decomposed the trajectory of Y r into a first part (t < T 1 ) and a second part (t > T 1 ). By the Markov property, we can study the second part of the trajectory supposing that Y r (T 1 ) = (x 1 , y 2 (T 1 )r). Since T 1 < ∞, the process X {1} 1 is ergodic. Using the monotonicity of the drift, we have that X r 1 (t) ≤ st X {1} 1 (t) for t > T 1 (this can be observed by coupling the two processes and noting that in the case of an infinite number of class-2 users, the service rate for class 1 is the lowest possible since there will always be a class-2 user in its best state). This implies that the family (X r 1 (t)) r is tight and that X r 1 (t) r → 0, as r → ∞, for t > T 1 . At time T 1 class 2 is saturated, i.e., U 1 = {1}. In what follows we assume that T 1 ≤ t < T 2 . Consider the deterministic function y 2 (•) as defined in the theorem, y 2 (t) = y 2 (T 1 ) + δ{1}

Using the triangular inequality we obtain, From Lemma VIII.1 we obtain that there exists ǫ r with lim r→∞ ǫ r = 0, such that ∀s = ⌊rT 1 ⌋, . . . , ⌊rt⌋. We now derive a bound on |δ {1} 2 (X r 1 (s)) -δ{1} 2 |. In order to do that, we define a one-dimensional process X r 1 having the same dynamics as our initial process but with the number of class-2 users fixed to r(y 2 (T 1 )θ), 0 < θ < y 2 (T 1 ). Let

E r 2 (t) ≤ 1 r ⌊rt⌋-1 s=⌊rT1⌋ δ 2 (X r (s)) -δ {1} 2 (X r 1 (s)) (34)

  and τ f k,n (•) are non-decreasing and Lipschitz continuous functions.

Fig. 2 .

 2 Fig. 2. (a) Scaled number of class-1 users, (b) Scaled number of class-2 users, (c) Scaled total number of users

Fig. 3 .

 3 Fig. 3. (a) Mean number of users and stability thresholds, (b) PI under different tie-breaking rules: relative degradation (in %) over PI with α = 1, (c) Scaled total number of users in overload, ρ = 1.1.

2 ≤

 2 we obtain|Y r (t)y(t)| ≤ 1 r ⌊rt⌋-1 s=0 δ(X r (s))δ ∅ + M r (⌊rt⌋) r .(29) We first control the martingale. Using successively Cauchy-Schwartz, Doob's inequality and Lemma VIII.2, we getE sup s≤t M r (⌊rs⌋) r C ′ t r, for a C ′ > 0.

  r (s))δ ∅ ≤ ǫ r t + κ r (s))δ ∅   ≤ ǫ r t + κ t 0 e r (s)ds .

2 (t -T 1 )r ⌊rt⌋- 1 s=⌊rT1⌋δ 2 (

 2112 , T 1 ≤ t < T 2 , and define the error function E r 2 (t) := sup T1≤s≤t |Y r 2 (s)y 2 (s)|. From (27) we obtain Y r 2 (t) = y 2 (T 1 ) + 1 X r (s)) + M r 2 (⌊rt⌋) r .

|δ 2 (

 2 X r (s))

TABLE I TRANSMISSION

 I RATES AND CHANNEL CONDITION PROBABILITIES IN THE CDMA 1XEV-DO WIRELESS NETWORK, AS REPORTED IN

TABLE III DRIFT

 III OF THE FLUID LIMIT IN OVERLOAD SYSTEM.

Acknowledgements

We are grateful to S.C. Borst (TU/e and Bell-Labs) and P. Jacko (BCAM) for many fruitful discussions.

π θ,r be the stationary distribution of X r 1 . Adapting Lemma 6 in [START_REF] Borst | Stability of parallel queueing systems with coupled service rates[END_REF] to our discrete time setting, we obtain that lim r→∞ π θ,r (x) = π {1} (x), ∀x.

(36)

We define T r = inf{t : X r 2 (rt) < r(y 2 (T 1 )θ)}. Using coupling arguments, we see that T r ≥ T 1 a. s., while for T 1 < t ≤ T r , X r 1 (t) ≤ st X r 1 (t) ≤ st X {1} 1 (t). Since δ {1} 2 (•) is increasing (follows from monotonicity assumption) we obtain

Since

is uniformly upper-bounded, we have that

Hence, we obtain that for all ǫ > 0 there exists r 0 such that

, for all r ≥ r 0 , and applying the ergodic theorem for Markov chains we get

δ{1} 2 , a.s. and

Together with (37) we obtain that there exists an r 0 such that

(38) Let us now condition on the set of events Ω r 34), ( 35) and (38), and using an inequality similar to [START_REF] Sadiq | Downlink scheduling of multiclass traffic in LTE[END_REF], we obtain that for any sample path in Ω r 1 (ǫ) (with ǫ small enough) it holds that

with r large enough, and C ′′ > 0. Using Gronwall's lemma [START_REF] Renardy | An introduction to partial differential equations[END_REF], Equation (39) implies that E r 2 (t) ≤ C ′′ ǫt(1+te t ). Hence, we can conclude that for a given ǫ > 0, there is an ǫ > 0 such that for each sample path in Ω r 1 (ǫ) it holds that E r 2 (t) ≤ ǫ, for all t ≤ T r , and r large enough.

We define

, see also Figure 4. When T ∞ = ∞, it is easy to check that T r = ∞ for ǫ small enough: Consider an ǫ < θ.

, which gives a contradiction with the above. See also Figure 5.

Therefore, given t such that t < T ∞ , there exists an ǫ small enough such that t < T r for all r large enough. Hence, from (40) we obtain for t < T ∞ ,

From [START_REF] Sadiq | Balancing SRPT prioritization vs opportunistic gain in wireless systems with flow dynamics[END_REF], we obtain [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF] is not satisfied, the system is not rate stable, see Lemma VIII.3 below, which precludes stability. Hence, ( 17) is a necessary condition for stability. We are now left with proving that BR policies are stable under condition [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF]. In order to do that, we (i) prove that, under any BR policy, the set of sample paths where service is given to a user that is not in its best state is asymptotically almost surely empty. Then (ii) we prove that the fluid limit will be equal to zero almost surely for some time T large enough, if condition [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF] holds. This will allow to conclude the proof.

In the remainder of the proof we focus on BR policies and assume condition [START_REF] Eryilmaz | Stable scheduling policies for fading wireless channels[END_REF] to be satisfied. Let us define

We define the random variable T r ǫ = inf{t :

for 0 < ǫ < 1 and let T r ǫ = min {T r ǫ , T }. Consider the event A r which occurs if, during the time interval [0, ⌊rT r ǫ ⌋], there is at least one user which has been served while not being in its best possible state. Since any BR policy gives absolute priority to users which are in their best possible state, it follows that

]. Since T r ǫ ≤ T and using basic algebra, it is easy to check that there exists a constant ξ ∈ [0, 1) such that P(A r ) ≤ 1 -(1ξ r ) rT =: g(r). We will now show that

Since log(1 + x) = x + o(x) when x is close to 0, we obtain that (1ξ r ) rT = e -rT ξ r +o(rξ r ) for large values of r.

Using Taylor expansions and the fact that

1e -rT ξ r +o(rξ r ) < ∞. Hence, we obtain (43) using Borel-Cantelli's lemma [START_REF] Feller | An Introduction to Probability Theory and Its Application[END_REF].

We will now show that at time T the weak fluid limit is almost surely equal to zero. From Equation (43) we obtain that, almost surely, event A c r occurs when r is large enough. Hence, only users in their best possible state are served in the interval [0, rT r ǫ ] when r is large enough, i.e., T BR,r k,n (t) = 0, for n = N k and t ≤ rT r ǫ , for r large enough, a.s.. Hence, for almost all ω we have that in the weak fluid limit presentation of Lemma IV.1 it holds that K k=1 τ BR k,N k (t) = t and τ BR k,n (t) = 0 for all n = N k , t ≤ lim inf r→∞ T r ǫ . So we obtain that for t ≤ lim inf r→∞ T r ǫ , any weak fluid limit y BR (•) satisfies

For a given sample path ω, let r k be the subsequence corresponding to lim inf r→∞ T r ǫ . By Lemma IV.1 we know that there exists a subsequence

T ǫ , the description (44) holds for all t ≤ T ǫ . Now letting ǫ go to zero, then T ǫ → T , hence Equation (44) holds for any t ≤ T , and in particular |y f (T )| = 0.

We conclude that for almost all sample paths, any weak fluid limit converges to 0 at time T , in particular the sequence corresponding to the liminf and the limsup. Hence, one can conclude that lim r→∞ Y f,r k (T ) = y f k (T ) = 0, almost surely.

Since Y f,r k (T ) converges almost surely (and therefore, also in probability) to 0, we can use the same argument as in Theorem V.1, in order to conclude that the system will be stable under policy f , which finishes the proof of Theorem V.