## Abstract

Channel conditions in wireless networks exhibit huge variations across space and time, giving rise to vast fluctuations in the transmission rates. Channel-aware scheduling strategies provide an effective mechanism for improving throughput performance by exploiting such rate variations, and these have been extensively examined at the packet level for a static user configuration. In this paper, we discuss the performance implications at the flow level for a dynamic user population, taking into account variations on a slower time scale and wide-range user mobility as well. First of all, we present simple necessary conditions for flow-level stability and prove that these are in fact (near) sufficient for a wide family of utility-based scheduling strategies. It is further shown how the flow-level performance of the proportional fair scheduling strategy may be evaluated by means of a processor-sharing model with a state-dependent service rate. In addition, we examine the impact of variations on a slower time scale, and establish that the so-called fluid and quasi-stationary regimes yield explicit, insensitive performance bounds. Finally, we turn our attention to a network of several base stations (BSs) with handoffs of active sessions governed by wide-range user mobility. It is demonstrated that mobility increases the capacity, not only in the case of globally optimal scheduling but also when each of the BSs adheres to a local fair-sharing discipline.

## 1. Introduction

The design and efficient operation of wireless networks involve similar issues to those encountered in wireline situations, such as congestion control, fairness and service differentiation. In wireless environments, these issues are greatly exacerbated by interference problems, intrinsically limited bandwidths and highly uncertain and random characteristics of wireless channels. Specifically, the channel quality may differ widely among spatially distributed users due to distance-related attenuation. In addition, the channel conditions for a given user may vary dramatically over time owing to fading effects.

Fading is an extremely complex physical phenomenon caused by the interaction between the propagation environment and user mobility. It emerges in diverse forms and typically spans a wide range of time scales. Multi-path fading arises at the level of a wavelength and occurs on a time scale that depends on the propagation characteristics, the carrier frequency and the speed of mobility. Path loss and shadow fading manifest themselves at a more macroscopic level as a result of distance-related attenuation and scattering due to obstacles and terrain conditions, and tend to vary over a longer time scale.

Wireless voice systems rely on power control mechanisms for adjusting the transmit power to combat fading and maintain a constant transmission rate. Various data applications, on the other hand, such as file transfers and Web browsing sessions, are less sensitive to packet-level delays and do not have an intrinsic rate requirement. Such elastic applications are well suited for rate control algorithms that continuously adapt the transmission rate over time so as to match the fluctuations in channel quality. Channel-aware or opportunistic scheduling strategies offer an effective mechanism for improving throughput performance by exploiting such rate variations (Knopp & Humblet 1995), and these have been intensively examined at the packet level for a static user configuration (e.g. Borst & Whiting 2001, 2003; Agrawal & Subramanian 2002; Neely *et al*. 2002, 2003, 2005; Viswanath *et al*. 2002; Liu *et al*. 2003; Tsibonis *et al*. 2003; Andrews *et al*. 2004, 2005; Bonald 2004; Kushner & Whiting 2004; Stolyar 2004, 2005*a*,*b*; Eryilmaz & Srikant 2005; Lin & Shroff 2005). We refer to the excellent survey by Georgiadis *et al*. (2006) for a comprehensive overview and additional references.

In this paper, we explore the implications of rate variations for performance at the flow level in wireless data networks, particularly borrowing from results originally reported in Borst (2003, 2005), Bonald *et al*. (2004*a*,*b*), Borst & Jonckheere (2006) and Borst *et al*. (2006). Besides the throughput gains produced by channel-aware scheduling, we also explicitly account for the impact of rate variations on a slower time scale and handoffs of active sessions as governed by wide-range user mobility. Owing to page limitations, we present a high-level discussion and refer to a longer version of the paper for technical details (Borst 2008).

We first present simple necessary conditions for flow-level stability and establish that these are in fact (near) sufficient for a wide family of utility-based scheduling strategies (Kelly *et al*. 1998; Mo & Walrand 2000). Imposing certain symmetry assumptions on the rate variations, we then proceed to show how the flow-level performance of the proportional fair scheduling strategy may be evaluated by means of a processor-sharing model with a state-dependent service rate. The latter model provides explicit formulae for the distribution of the number of active users, mean transfer delays, blocking probabilities and user throughputs. In particular, the performance is *insensitive*, in the sense that these measures depend only on the statistical characteristics of the system through a readily computed load factor.

Next, we focus on the impact of user mobility that occurs on a slower time scale and manifests itself in the form of rate variations at the flow level, but remains confined to a single cell. Owing to these slower rate variations, the insensitivity property is lost and the performance depends in some complicated fashion on the detailed rate statistics and traffic characteristics. In order to obtain tractable performance estimates, we examine two limit regimes, termed *fluid* and *quasi-stationary* regimes, and use stochastic comparison techniques to show that these yield optimistic and conservative performance estimates, respectively.

Finally, we turn our attention to a network of several base stations (BSs) with handoffs of active sessions governed by wide-range user mobility. The dynamic interaction among neighbouring BSs due to interference and mobility is quite complex and has received little attention in the literature. As one of the few exceptions, Bonald *et al*. (2004*a*,*b*) considered a network in which the transmission rates at the various BSs depend on the activity states of surrounding BSs as a result of interference. We characterize the capacity of networks with several BSs and show that mobility increases the capacity region, not only in the case of globally optimal scheduling but also when each of the BSs adheres to a local fair-sharing discipline such as round robin.

The rest of this paper is organized as follows. In §2, we first establish simple necessary conditions for flow-level stability, and then prove that these are (near) sufficient for a wide family of utility-based scheduling strategies. In §3, we describe how the flow-level performance of the proportional fair scheduling strategy may be evaluated by means of a multi-class processor-sharing model with a state-dependent service rate. In §4, we examine the impact of rate variations on a slower time scale and establish that two limit regimes, termed fluid and quasi-stationary regimes, yield explicit, insensitive performance bounds. Finally, in §5, we turn our attention to a network of several BSs with handoffs of active sessions governed by wide-range user mobility, and show that mobility increases the capacity region. We make some concluding remarks in §6.

## 2. Flow-level stability

We consider a system with *K* traffic classes, each representing a category of statistically identical users in terms of service requirements and rate characteristics. Class-*k* users arrive as a Poisson process of rate *λ*_{k} (per time unit) and have generally distributed service requirements *F*_{k} (in bits) with mean *ξ*_{k}. Let denote the offered traffic of class *k* (in bits per time unit) and we define .

For a given user population (*n*_{1}, … ,*n*_{K}), let be the set of feasible service rate vectors. The dependence on the user population accounts for the fact that the scheduling gains from fast rate variations increase with the degree of multi-user diversity (see, for instance, ch. 6 of Tse & Viswanath 2005). Observe that the sets are convex and monotone increasing in the user population, i.e. if , then , since additional users may simply be excluded from service without affecting the feasible service rates of the remaining users. We define as the closure of , which inherits the convexity of the sets *A*(*n*_{1},…,*n*_{K}). While the set *A*^{*} may have a complicated structure in general, it has a rather simple form in the special case where only a single user is served in each time slot: , with denoting the maximum possible rate value of class-*k* users.

Proposition 2.1 provides a simple necessary stability condition.

*No scheduling strategy achieves flow-level stability for* .

Proposition 2.1 follows from the simple observation that the long-term mean service rate vector must be contained in conv(*A*^{*})=*A*^{*}.

Henceforth, we focus on the family of one-parameter utility functions introduced by Mo & Walrand (2000), i.e. for some *α*≥0, with the convention that *U*(*x*)=log (*x*), for *α*=1. The latter family of utility functions covers the most common fairness notions, such as max-throughput (*α*=0), proportional fairness (*α*=1) and max–min fairness (*α*=∞). Note that *α*-fair strategies may be implemented at the slot level via (adaptive) weight-based (gradient-based) scheduling strategies (Viswanath *et al*. 2002; Stolyar 2004, 2005*a*,*b*).

Proposition 2.2 shows that the condition identified in proposition 2.1 is in fact (near) sufficient for stability of weighted *α*-fair scheduling strategies, assuming exponential service requirement distributions.

*A weighted α-fair scheduling strategy with α*>0 *achieves flow-level stability for* .

Proposition 2.2 may be established in a similar fashion as the flow-level stability of weighted *α*-fair rate allocation policies in wireline networks (Bonald & Massoulié 2001).

In the special case where only a single user is served in each time slot so that , the stability condition of proposition 2.2 reduces to . Thus, a weighted *α*-fair strategy achieves stability as long as the system is stable if every class could be served at the maximum possible rate whenever selected for service. This may be explained by the observation that, under a weighted *α*-fair strategy, every class will either be served at the maximum possible rate or not at all whenever any of the classes is unstable.

It is interesting to observe that propositions 2.1 and 2.2 contrast with the fact that utility-based scheduling strategies generally fail to provide maximum stability guarantees at the packet level (e.g. Andrews 2004; Neely *et al*. 2005). Various simple queue-length-based strategies, on the other hand, do achieve stability at the packet level whenever possible (Tassiulas & Ephremides 1992, 1993; Andrews *et al*. 2004). In order to reconcile these paradoxical facts, it is worth observing that while such utility-based strategies operate agnostically of the queue lengths at the packet level, they *do* respond to congestion that occurs at the flow level. Thus, from a stability perspective, the behaviour of a utility-based strategy at the flow level shows resemblance to that of a queue-length-based strategy at the packet level.

## 3. Proportional fair scheduling

In §2, we derived simple necessary conditions for flow-level stability and established that these are in fact (near) sufficient for a wide family of *α*-fair scheduling strategies. We now specifically consider the proportional fair strategy (Kelly *et al*. 1998; Chaponniere *et al*. 2002), which corresponds to *α*=1 in a scenario where the distribution of the set of feasible rate vectors is symmetric in the sense that the relative variations around the time-average rates are statistically identical for all users. In that case, each user receives service at a fraction *G*(*n*)/*n* of its time-average rate when there are *n* users in the system, where *G*(*n*) represents a scheduling gain factor (Borst 2008). As shown below, we can not only establish stability criteria but also explicitly evaluate the flow-level performance in terms of the number of active users, mean delays, blocking probabilities and user throughputs, and even allow for generally distributed service requirements.

As before, we consider *K* traffic classes and let denote the rate coefficient of a class-*k* user. Let be the normalized service requirement of a class-*k* user with mean . We define as the normalized traffic intensity of class *k* and as the total normalized traffic intensity. Let be a random variable representing the residual lifetime of *B*_{k}, and the corresponding distribution function, i.e. . In addition, we include admission control and assume that, at most, *M* users are admitted in the system simultaneously. Users which initiate service requests when there are already *M* transfers in progress are denied access and abandoned.

Let (*N*_{1}, … ,*N*_{K}) be a random vector representing the number of users of the various classes at an arbitrary epoch in statistical equilibrium (assuming it exists). Let denote the total number of users in the system. Given that there are *n*_{k} class-*k* users in the system, let be the remaining normalized service requirement of the *i*th class-*k* user, *i*=1,…,*n*_{k}, *k*=1,…,*K*.

As mentioned above, each class-*k* user receives service at rate when there are *n* active users in the system. Thus, the normalized remaining service requirement of each user is reduced at rate *G*(*n*)/*n*, which means that the normalized remaining service requirements evolve in a similar probabilistic fashion as the remaining service requirements in a multi-class processor-sharing system with arrival rates *λ*_{k}, generic service requirements *B*_{k} and service rate *G*(*n*) when there are, in total, *n* users present. Proposition 3.1 follows from well-known results for such a system (Cohen 1979; Kelly 1979).

*The proportional fair strategy achieves stability for ρ*<*G*^{*} *or M*<∞, *in which case**with* , *and normalization constant* .

Using Little's law, we find that the mean delay experienced by a class-*k* user is given by , with . The above formula reflects the insensitivity property of the processor-sharing discipline, which shows that the mean delay of a class-*k* user depends only on the service requirement distribution of class *k* through its mean *β*_{k}. In fact, it may be shown that the conditional expected delay of any user with actual service requirement *b* is given by . Thus, the expected delay incurred by a user is proportional to its normalized service requirement, with proportionality factor .

## 4. Slow rate variations

So far, we have assumed that the rate variations occur on a fast time scale and average out over the time scale of interest for the flow-level performance, only manifesting themselves in the throughput gains obtained from channel-aware scheduling. We now turn our attention to a scenario where the fluctuations may have a slowly varying component. We continue to assume that the rate variations are symmetric in the sense described in §3, but now additionally allow the rate coefficients of the various users to slowly vary over time. In order to model the slower fluctuations, it is convenient to adopt a ‘state structure’, with the users moving among several possible states indexed by a finite set . The states implicitly correspond to subregions of the cell area. When in state , the rate coefficient of a user is *C*_{i}.

As before, we consider a system with *K* traffic classes and now let *F*_{km} denote the service requirement of the *m*th arriving class-*k* user, and *S*_{km}(*t*) denote its state at time *t*. We assume that *F*_{km} and *S*_{km}(*t*), *m*=1, 2,…, are independent and identically distributed copies of a random variable *F*_{k} with mean *ξ*_{k} and a stationary and ergodic process *S*_{k}(*t*) with state space , respectively. Let denote the generic rate process for class *k* and we define as the expected rate coefficient of a class-*k* user. Assuming proportional fair scheduling, the service rate at the flow level of the *m*th arriving class-*k* user, if present at time *t*, is , where *n* denotes the total number of users present at time *t* and *G*(*n*) represents the scheduling gain factor mentioned earlier.

In order to obtain tractable performance estimates, we introduce two limit regimes, termed *fluid* and *quasi-stationary* regimes, where the rate processes evolve on an infinitely fast and slow time scale, respectively. Formally, let us consider a family of systems, parametrized by , where the generic rate process for class *k* is . Thus, the parameter *s* represents the ‘speed’ of the rate process, or, equivalently, the value 1/*s* models the time scale of the rate process. If *S*_{k}(*t*) is a Markov process, the process may be obtained by scaling the transition rates with *s*.

When the parameter *s* grows large, the rate process approximately averages out over the time scale of the flow dynamics. In the limit for *s*→∞, the variations completely vanish and the rate process reduces to a constant, giving rise to the ‘fluid’ regime with . It is worth observing that the fluid regime is reminiscent of but different from the usual law-of-large-numbers fluid limit. On the other hand, as the value of *s* becomes small, the fading process remains roughly constant over the time scale of the flow dynamics. In the limit for *s*→0, the changes completely disappear and the rate process freezes in some initial state, yielding the ‘quasi-stationary’ regime with , where *R*_{k}(0) has the stationary marginal distribution of the process *R*_{k}(*t*).

Now observe that in the fluid and quasi-stationary regimes, the system behaves as a multi-class processor-sharing system with a state-dependent service rate *G*(*n*) and class-*k* service requirements given by and *F*_{k}/*R*_{k}(0), respectively. Accordingly, define the traffic intensities associated with class *k* in the fluid and quasi-stationary regimes as and , respectively, with owing to Jensen's inequality. We denote the total traffic intensities in the fluid and quasi-stationary regimes by and , respectively.

With the above translation to a multi-class processor-sharing system, the performance in the fluid and quasi-stationary regimes may be explicitly evaluated using well-known results for such a system (Cohen 1979; Kelly 1979). In particular, a necessary and sufficient condition for stability of the fluid (respectively, quasi-stationary) regime is *ρ*^{fl}<*G*^{*} (respectively, *ρ*^{qs}<*G*^{*}). When the system is stable, the stationary distributions *π*^{fl} and *π*^{qs} of the numbers of active flows of the various classes in the fluid and quasi-stationary regimes depend on the class characteristics through the traffic intensities and only,where ‘#’ represents ‘fl’ or ‘qs’; ; ; and is determined by the normalizing condition.

It follows from the stochastic bounds to be derived below that the condition is necessary for stability, while the condition is sufficient. Note that when the number of active flows tends to infinity, each flow stays in the system for a long time, so that the rate process tends to average out over the flow duration, i.e. the system behaves as in the fluid regime. Thus, one would expect the condition to be not only necessary but also sufficient for stability, as confirmed by proposition 4.1.

*If* , *then the system is stable*.

We now compare the performance of the system with that in the fluid and quasi-stationary regimes. Assume that the system is empty at time 0 and let *N*_{k}(*t*) denote the number of active class-*k* flows at time *t*. With minor abuse of notation, for *m*=1, …, *N*_{k}(*t*), let be the remaining service requirement of the *m*th active class-*k* flow at time *t*. We define the total workload at time *t* as . We assume that the cumulative distribution function associated with the service requirement *F* is concave.

Proposition 4.2 states that the performance improves (respectively, deteriorates) in terms of the number of active flows, the workload and the response times *D*, when the rate processes of some flows are replaced by the corresponding fluid (respectively, quasi-stationary) versions as described earlier. Similar comparison results hold for the equilibrium distributions.

*For all k*=1,…,*K*, *t*≥0,*where* ≤_{icx} *and* ≤_{st} *indicate the increasing-convex and stochastic orderings, respectively* (Müller & Stoyan 2002), *while the superscript* ‘fl’ (*respectively,* ‘qs’) *refers to a system where the rate processes of some flows are replaced by the corresponding fluid* (*respectively, quasi-stationary*) *versions*.

## 5. Large-scale user mobility

We now further extend the model to a network with several BSs, indexed by the set , and possible handoffs among cells as governed by large-scale user mobility in addition to slow rate variations driven by mobility within cell areas. The scheduling gains from fast rate variations are no longer included. In order to model the slow rate variations and possible handoffs, we continue to use the state structure introduced before, with users moving among several possible states. However, we now additionally allow the users to be served by different BSs in different states. Define as the set of states where a user is served by BS *n*.

We consider a system with *K* traffic classes as described in §4. As before, the state of a class-*k* user is governed by a stationary ergodic process *S*_{k}(*t*), with . Let denote the set of states in which a class-*k* user may reside. We define as the stationary probability that a class-*k* user is in cell *n* and let denote the set of cells that class-*k* users may visit.

### (a) Optimal scheduling strategies

We now determine the capacity region for optimal scheduling strategies. In other words, we characterize the set of all traffic vectors for which there exists a scheduling strategy that achieves stability. We define

The component *τ*_{i,k}, , may be interpreted as the fraction of resources of BS *n* allocated to class-*k* users in state *i*. With that interpretation, the quantity represents the total service rate received by class-*k* users. Thus, may be interpreted as the achievable rate region, i.e. the set of all achievable service rates for the various traffic classes. Note that is a convex set and depends on the spatial user distributions through the sets only.

*There exists a scheduling strategy that achieves stability if* . *Conversely, if* , *then there exists no scheduling strategy that achieves stability*.

#### (i) No mobility

We now consider a scenario without any mobility, i.e. the state of a user is assumed to be fixed for the duration of the flow, and the probability that a class-*k* user is in state *i* is *ψ*_{i,k}. The rate region simplifies to , such that , and may equivalently be represented as .

It is easily verified that , assuming . This demonstrates that mobility increases the achievable capacity as long as the scheduling discipline is left flexible, which agrees with findings in the context of ad hoc mobile networks (Grossglauser & Tse 2002). However, this does not imply that mobility increases the capacity achieved by a given scheduling discipline, e.g. fair resource sharing. In this regard, it is worth recalling that the results in §4 show that *intra*-cell mobility, which manifests itself in the form of slow rate variations, improves the performance under fair resource sharing. In §5*b*, we investigate whether *inter*-cell mobility increases the capacity under fair resource sharing as well.

### (b) Fair resource sharing

We now turn our attention to a scenario where each of the BSs operates according to an *α*-fair scheduling strategy. Thus, when there are *n*_{ik} class-*k* users in state *i*, , each of them receives service at rateWe define

Note that the vector , withbelongs to the set , so that . The components of the vector may be interpreted as the numbers of flows of the various classes. With that interpretation, the quantityrepresents the total service rate received by class-*k* flows under an *α*-fair sharing strategy.

Proposition 5.2 provides a characterization of the capacity region in the case of *α*-fair resource sharing, assuming exponential service requirement distributions. It states that the system is stable if and only if there exists a relative distribution of the numbers of flows across the various classes so that the total service rate received by each of the traffic classes is larger than the traffic intensity of that class.

*If* , *then the system is stable. If* , *then the system is unstable*.

#### (i) No mobility

We now consider a scenario without any mobility, i.e. the state of a user is assumed to be fixed for the duration of the flow, and the probability that a class-*k* user is in state *i* is *ψ*_{i,k}. As mentioned earlier, the rate region simplifies to .

The latter region may or may not be larger than the stability region in the presence of mobility, depending on the probabilities *π*_{i,k} and *ψ*_{i,k} and the rates *C*_{i}. When the spatial user distribution is identical in the two scenarios, however, i.e. *π*_{i,k}=*ψ*_{i,k} for all , *k*=1,…, *K*, then it may be shown that .

## 6. Conclusion

In summary, we observe that rate variations and mobility tend to improve the performance and increase the capacity region. In some respects, this simply ties in with the generic principle of opportunistic scheduling, and confirms the natural expectation that the throughput improvements obtained at the packet level translate into performance and capacity gains at the flow level. This applies not only to fast rate variations but also to mobility that occurs on a slower time scale and creates additional opportunities to serve users in the most favourable locations, which may be interpreted as a form of network-wide opportunistic scheduling. In this regard, the above observation resonates with the fact that mobility increases the capacity of ad hoc mobile networks (Grossglauser & Tse 2002). What is perhaps less obvious is that the performance and capacity improvements also arise in the case of fair sharing, e.g. channel-oblivious round-robin scheduling, where BSs allocate equal resource shares to users in less advantageous conditions. In that case, the improvements reflect a certain convexity property of flow-level performance measures and capacity with respect to the rate processes, as inspection of the proofs reveals. The above results have important implications for traffic engineering and dimensioning. In particular, ‘neglecting’ mobility and pretending that users remain stationary for the duration of their service yields a simple, conservative capacity estimate.

## Acknowledgments

The author gratefully acknowledges the tremendous benefits enjoyed from fruitful interactions with Thomas Bonald (France Telecom R&D), Nidhi Hegde (France Telecom R&D), Matthieu Jonckheere (CWI), Sindo Núñez-Queija (CWI), Alexandre Proutière (Microsoft Research) and Phil Whiting (Alcatel–Lucent).

## Footnotes

One contribution of 16 to a Discussion Meeting Issue ‘Networks: modelling and control’.

- © 2008 The Royal Society