1

Selective Fair Scheduling over Fading Channels

arXiv:1801.01793v1 [cs.NI] 5 Jan 2018

∗

Apostolos Destounis∗ , Georgios S. Paschos∗ , David Gesbert†
Mathematical and Algorithmic Sciences Lab, France Research Center, Huawei Technologies Co. Ltd.
† EURECOM
∗
emails: {apostolos.destounis, georgios.paschos}@huawei.com, † gesbert@eurecom.com

Abstract—Imposing fairness in resource allocation incurs a loss
of system throughput, known as the Price of Fairness (P oF ).
In wireless scheduling, P oF increases when serving users with
very poor channel quality because the scheduler wastes resources
trying to be fair. This paper proposes a novel resource allocation
framework to rigorously address this issue. We introduce selective
fairness: being fair only to selected users, and improving P oF by
momentarily blocking the rest. We study the associated admission
control problem of finding the user selection that minimizes P oF
subject to selective fairness, and show that this combinatorial
problem can be solved efficiently if the feasibility set satisfies a
condition; in our model it suffices that the wireless channels
are stochastically dominated. Exploiting selective fairness, we
design a stochastic framework where we minimize P oF subject
to an SLA, which ensures that an ergodic subscriber is served
frequently enough. In this context, we propose an online policy
that combines the drift-plus-penalty technique with GradientBased Scheduling experts, and we prove it achieves the optimal
P oF . Simulations show that our intelligent blocking outperforms
by 40% in throughput previous approaches which satisfy the SLA
by blocking low-SNR users.

I. I NTRODUCTION
Throughput efficiency and fairness is a well-explored fundamental tradeoff in wireless communications [1]. The status quo
is to use opportunistic schedulers to exploit the fading peaks
and strike a balance between throughput and fairness [1], [2].
While fairness is important, it is also known to negatively
impact the system throughput, a phenomenon quantified by
the Price of Fairness (P oF ) [3]. In wireless downlink systems
P oF increases steeply when a base station attempts to serve
users with unreasonably poor channel quality, for instance
users trying to access spectrum from strongly shadowed areas
(e.g. building basements, tunnels), remote areas (cell-edge
users), or operating with ill-functioning or sub-standard RF
equipments. Our simulations show a 10%-40% throughput
degradation when adding 1-10 users with SNR 20dB less.
Since service quality is anyway low in these cases, the current
approach is to block users when their SNR drops below a
threshold. We propose a framework for proactively blocking
users, based on optimizing the P oF subject to fairness and a
probabilistic service guarantee. For the same quality level, our
scheme yields a 40% total throughput gain over the current
approach, unraveling significant room for optimization which
was not previously explored.
We start with a K-user scheduling problem over a wireless
fading channel. The service must be fair, but our key idea
is that it is allowed temporarily to exclude some users from
service. In this context, we introduce a novel fairness objective
called selective fairness: a subset of users S ⊆ {1, . . . , K} is
fairly treated, while the remaining users S c receive no service.

Imposing selective fairness for smin users as a constraint,
we consider the minimization of P oF (equivalent to system
throughput maximization). Solving this problem is non-trivial
because the throughput contribution of a user to a fairnessconstrained system is very complicated. Mathematically, the
problem is of combinatorial nature, potentially involving the
solution of O(2K ) large convex programs. We show, however,
that if the system satisfies the subspace monotonicity property,
then the problem can be solved efficiently. We further prove
that the subspace monotonicity property is satisfied when
the fading channels are stochastically ordered, a practical
case of interest. Then we propose an online policy, referred
to as selective GBS, which is based on O(K) number of
experts, i.e., online simulated policies that provide insight for
good scheduling decisions. The throughput vector obtained by
selective GBS is shown to converge to the optimal solution of
the P oF minimization.
The initial theoretical framework assumes we know how
many users to block, which is impractical. It is more reasonable to regulate the blocking according to a probabilistic
service guarantee over multiple scheduling problems. The
system will block users when their channel quality happens
to be very poor, but also ensure that they are served most of
the times they attempt to access the service. In the second
part of the paper we extend selective fairness to a stochastic
setting, where the blocking is controlled by a virtual queue
evolving across scheduling problems. Combining the queue
with selective GBS, we design an online policy, referred to as
Online Selective Fair (OSF) scheduler, that maximizes system
performance while satisfying the probabilistic guarantee and
being α-fair to selected users. This provides a rigorous framework to alleviate the problem of P oF in wireless scheduling.
A. Related work
The concept of opportunistic scheduling dates back to 1995
[4]. The Gradient-based Scheduler (GBS) was proposed and
analyzed early in the 2000s, cf. [5]–[7]. It has been shown to
provide a stochastic approximation of the optimal solution of
the Network Utility Maximization problem [1], [5], [6], while
it can also provide good short-term fairness performance by
using discounting factors when averaging [2], [8]. For these
reasons, and also for its great simplicity, GBS has become the
de facto scheduling policy in 3G base stations [9]. To capture
frequency-time resource blocks in LTE systems, GBS was later
extended to a multichannel version [7], [10], [11], keeping the
original properties. Prior work has shown how to extend GBS
to handle systems with many antennas, which is necessary for

the 4G and emerging 5G wireless networks [12]. As of today
GBS remains the prominent practical scheduler, therefore we
restrict our approach to be backward compatible with GBS.
It is anecdotally known that most operators tune the GBS to
achieve proportional fairness, a tradeoff between maximizing
total throughput and providing equal throughput shares to all
users [1], [13]. When some users have much lower channel
quality, maintaining proportional fairness results in a reduction of system throughput because the base station is forced
to assign a great number of resources to them with small
throughput return. Prior work has analyzed the phenomenon
of P oF in general resource allocation problems [3], [14]. In
this paper, we are interested to judiciously exclude some users
from service in order to minimize P oF . To our knowledge,
there exist no prior work studying the optimization of P oF .
We find that in systems with 5% of users with very low channel
quality, P oF optimization can improve total throughput by
40% over the existing state of art which simply blocks lowSNR users below a threshold. This gain is attributed to the
fact that the optimal set of users to block at each realization
varies from case to case, and it can not be determined by a
simple predefined SNR threshold for blocking.
Our work is related to the literature of admission control
in stochastic networks and call admission control in cellular
networks, however there are important differences. Works in
stochastic networks focus mainly on admitting fractions of
elastic traffic cf. [15], [16], while in our case we admit a
number of users. Regarding the combinatorial call admission
control for cellular networks, the most relevant work to ours is
[17], where the authors discuss admission control and blocking
rates with opportunistic scheduling and evaluate the performance of simple mechanisms. In this paper, we derive a lowcomplexity policy that explicitly maximizes the cell spectral
efficiency subject to fairness and a blocking constraint. More
broadly, a differentiating factor of our work from existing
literature is the consideration of special fairness constraints.
II. S YSTEM MODEL
A. Wireless downlink
We consider a wireless downlink with one transmitting base
station and K receiving users. Time is slotted t = 1, 2, . . . , and
at each time slot, the base station can transmit data to one of
the users with the ultimate goal to optimize the time-average
data transmissions. An extension to simultaneous service of
multiple users is possible via [7], [10], [11], but we avoid it
in the interest of presentation clarity.
If user k is scheduled at slot t, data is sent to this user at
a transmission rate Rk (t) ∈ R, where R = {r1 , r2 , . . . rL } is
a finite set of possible transmission rates. The vector R(t) ∈
RK is random, i.i.d. over time, and its randomness is attributed
to the wireless channel fading, thus it is independent of the past
choices of the base station. The realization of R(t) is provided
to the base station just before the scheduling decision is made,
as it is customary in contemporary systems.
Let Ikπ (t) ∈ {0, 1} denote the scheduling decision at time t
regarding user k under scheduling policy π, where Ikπ (t) is 1 if
user k is scheduled, and 0 otherwise. A P
policy that schedules
only one user at each slot, i.e., satisfies k Ikπ (t) ≤ 1, ∀t, is

Fig. 1: Illustration of feasible set X for a 2-user downlink.

called feasible, and we denote with Π the set of all feasible
policies. In our model, the base station always has available
data for each user,1 therefore the instantaneous rate of data
received by user k during slot t is µπk (t) = Rk (t) if Ikπ (t) = 1
and zero otherwise, the accumulated user throughput at t
Pt
µπ (τ )
π
,
xk (t) = τ =1 k
t
and the user k throughput is xk = lim inf t→∞ xπk (t). The
vector of user throughputs, denoted with x, is our key performance metric.
Definition 1 (Feasible throughputs). The set of feasible
throughputs X is the set of all throughput vectors x that can
be achieved by any policy in Π.
Let pr = P(R(t) = r) , r ∈ RK denote the probability
distribution of channel rate vectors. By considering all slots
with R(t) = r and scheduling user k with probability φkr ,
taking liminf leads
set X :

 to the convex
P
xk = r∈RK φkr pr rk 

.
(1)
X = x ≥ 0 0P≤ φkr ≤ 1

K 
φ
=
1,
∀r
∈
R
kr
k
Theorem 1 (Feasible throughputs [18]). The set of feasible
throughputs X is given by set (1).
B. Efficiency and fairness
Resource allocation with multiple users involves two important goals: (i) to operate the system at high efficiency, and
(ii) to allocate resources in a fair manner. Typically, these
two goals are conflicting. Consider the 2-user example of
figure 1, where X is the shown gray area and the marginal
user throughputs satisfy X1max > X2max . Point A corresponds
to the maximum sum throughput–it is the point in X that
maximizes x1 + x2 . An arising issue with point A however,
is that user 2 receives zero throughput, which is unfair. The
fairest point is C, which ensures that the users receive the
maximum possible equal throughputs. In this case however, the
total system throughput is significantly reduced. In practice,
engineers desire a tradeoff between the two extremes, A and
C. Point B, known as proportional fairness provides such a
tradeoff. Next we formalize the fairness notions of interest.
Definition 2 (Fairness objectives). Let X be a convex set of
feasible throughputs.
• A throughput vector x ∈ X is called max-sum-throughput
if for any vector y ∈ X it holds:
K
K
X
X
xk ≥
yk .
k=1
1 If

k=1

we replace GBS with a max-weight-type policy, it is possible to
generalize our work to stochastic arrivals using the framework in [18].

Max-sum-throughput

1 − P oF (%)

Proportional fairness

Max-min fairness
# of users with −20dB SNR
Fig. 2: System throughput sensitivity (1 − P oF ) of alpha-fairness to
users with poor channel quality.
•

•

A throughput vector x ∈ X is called max-min fair if for
any vector y ∈ X it holds:
yi > xi ⇒ ∃ j : yj < xj ≤ xi .
A throughput vector x ∈ X is called proportionally fair
if for any vector y ∈ X it holds:
X yk − xk
≤ 0.
xk
k

Since X in (1) is a closed set, a max-sum-throughput vector
always exists, but it may not be unique. Since X is convex, it
contains a unique max-min fair vector [19], and because the
proportionally fair vector is the optimal solution to maximizing
the sum of logarithms (i.e. a strictly convex function) over X ,
it exists and it is unique.
A connection between fairness and convex optimization
is rigorously established by the problem of Network Utility
Maximization (NUM) [16]:
K
X
gα (xk ),
(2)
max
x∈X

k=1

where we have usedthe α-fair function
x1−α
1−α , α ∈ [0, 1) ∪ (1, ∞)
gα (x) =
log x, α = 1.
Problem (2) is useful since by tuning the value of α we obtain
different fair vectors as solutions to the optimization problem:
1) choosing α = 0 yields max-sum-throughput,
2) choosing α = 1 yields proportional fairness [13],
3) choosing α → ∞ yields max-min fairness [20].
Consider the Gradient-Based Scheduling (GBS) policy:
schedule the user that maximizes Rk (t)gα0 (xGBS
(t)), where
k
gα0 (x) = x−α , and recall that Rk (t) is the instantaneous
transmission rate of user k and xGBS
(t) is the accumulated
k
throughput of user k; clearly GBS ∈ Π. Let x∗ (α) be a
a.s.
solution of (2), prior work [5], [6] has shown that xGBS
(t) →
k
∗
xk (α), ∀k. Hence, we can use GBS and tune the value of α to
operate the system at any desirable point. There is anecdotal
evidence that 3G and LTE base stations use GBS with α ≈ 1.
III. O PTIMIZING P RICE OF FAIRNESS
∗

Since x (α) is the solution of (2) for some α, it follows
that x∗ (0) denotes a max-sum-throughput vector. We define
the price of fairness similar
[3]: P
P to
∗
x
(0)
−
x∗ (α)
,
(3)
P oF , k kP ∗ k k
k xk (0)
which depicts how expensive it is to offer α-fairness in terms
of loss of sum throughput. Note that 1 − P oF shows the

fraction of maximum total throughput achieved by the α-fair
point.
In wireless systems it is common for some users to have
very poor signal reception. Such users can have a negative
effect in P oF , which we showcase with a simulation example.
In a downlink system with Rayleigh fading, we simulate GBS
scheduling for K = 10 users with mean channel rate 1, while
adding progressively 1..10 users with mean channel rate 20dB
less. We plot 1 − P oF for different values of α in figure 2.
Proportional fairness experiences a significant efficiency drop
of almost 10% for 1 weak user, and 40% for 10.
Our idea is to economize fairness by excluding weak users
from service. However, selecting users is challenging because
we do not know a priori their long-term contributions to the
throughput of a fairness-constrained system.
A. Selective fairness
As a first step we introduce a novel fairness metric, called
selective fairness. We partition the set of users to two sets,
S ∪ S c = {1, . . . , K}. For set S we guarantee α-fairness,
while the users in the complementary set S c are not served at
all.2 Our goal will be to select the set S carefully in order to
decrease the price of fairness.
To concretely define selective fairness we need some technical tools. Define the subspace X (S) ⊆ X , where all nonselected users S c must have zero throughputs:

X (S) , x ∈ X xk = 0, ∀k ∈ S c .
Also, we need an |S|–dimensional representation of the vectors
in X (S). Let ei be a K-dimensional column vector of zeros
with the exception of element i which is one, e.g. for K = 3
we have e2 = (0, 1, 0)T . Note that (ei )i∈K is a basis of RK .
Then define the K × |S| dimensionality reduction matrix
D S , (ek )k∈S .
For the example of 3 users, and S = {1, 3}, we have


1 0
D {1,3} =  0 0  .
0 1
If we multiply an element of X (S) or X with D S , we can
remove the dimensions that correspond to S c . Last, consider
the set with the |S|–dimensional representations of X (S):

Γ(S) , u u = xD S , x ∈ X (S) .
Definition 3 (Selective fairness). A vector x ∈ X is called
(S, α)–selective fair if
1) x ∈ X (S),
2) and xD S is α–fair in the set Γ(S).
The definition posits that the selected users in S will be
allocated α–fair throughputs in the subspace Γ(S), while the
rest users receive zero throughput.
Fix a subset S ⊆ {1, . . . , K}, and consider the conditions:
xk = 0, ∀k ∈ S c ,
(4)
X
x ∈ arg max
gα (uk ).
(5)
u∈X

k∈S

Theorem 2. The vector x is (S, α)–selective fair if and only
if it satisfies (4)-(5).
2 The concept of selective fairness can be generalized to larger user
partitions and different fairness objectives per subset.

Fig. 3: 3-user feasible throughputs and the eight possible (S, 1)selective fair points.

Fig. 4: Subspace comparison for the example of figure 3 and |S| = 2.

An implication of the theorem is that the (S, α)–selective
fair point is the limit point of GBS policy if we preclude users
in S c from scheduling.

when serving users K. If |K| ≥ smin , then:
TK ≤ TK0 , ∀K ⊆ K0 .
Hence, the optimization (6) is useful because it ensures that
the system performance does not drop even when adding users
with low average SNRs.
However P oF minimization with selective fairness (6) is in
general a combinatorial Mixed Integer Convex Program: to determine the solution we potentially need to inspect exponential
to K user subsets, and for each subset solve a difficult NUM
problem. The NUM problem is difficult due to the possibly
very large number of fading states, and explicit solutions for
Rayleigh fading are only known for the case of max-min
fairness [21]. Nevertheless, we present next a condition which
is sufficient to break the combinatorial structure, and simplifies
the solution of P oF minimization.

B. P oF minimization with selective fairness

C. Subspace monotonicity

In figure 2 we saw that when we block users with poor
channel quality, the P oF decreases. It is therefore natural to
ask the question if we were allowed to block all but smin users
in order to decrease P oF , which users would we block? Next,
we pursue a (S, α)-selective fair point that minimizes P oF
(and thus maximizes system efficiency) subject to serving at
least smin users in a fair manner.

Consider a permutation of user indices σ(.) and the arising
|S|–dimensional subspace Γσ (S), which is the same as Γ(S)
but with dimensions permuted by σ. We can now compare the
subspaces Γ(S1 ), Γ(S2 ) for two user sets with same cardinality
|S1 | = |S2 | = |S|. We say that the subspace of S1 dominates
that of S2 if there exists permutation σ2 such that
Γ(S1 ) ⊇ Γσ2 (S2 ).
Figure 4 showcases a comparison of subspaces with |S| = 2
on the example of figure 3.
If a subspace dominates another, then it also contains a
better selective fair vector; let T (S) be the total throughput of
the (S, α)–fair vector under a feasible S. Suppose there exists
permutation σ2 such that Γ(S1 ) ⊇ Γσ2 (S2 ). Then T (S1 ) ≥
T (S2 ). Next we generalize this observation.
Definition 4 (Subspace monotonicity). For feasible throughputs X with dimension K, we say that the set X satisfies
the subspace monotonicity if there exists an ordering of users
(σ(1), σ(2), . . . , σ(K)) and permutations σS , such that:
Γ({σ(1), . . . , σ(|S|)}) ⊇ ΓσS (S), ∀S ⊆ K.
Subspace monotonicity expresses the condition that if the
users are ordered according to σ(.), the subspace of first
|S| users, denoted by Γ({σ(1), . . . , σ(|S|)}), dominates the
subspace of any other subset with same cardinality.
Corollary 2. Suppose that the set X satisfies the subspace
monotonicity. Then an optimal solution of (6) is of the form
(x∗σ(1) , x∗σ(2) , . . . , x∗σ(j) , 0, . . . , 0), where smin ≤ j ≤ K.
Therefore, if the subspace monotonicity is satisfied, then
problem (6) can be solved by a polynomial number of calls
to an oracle that solves the NUM problem. Hence, we are
motivated to ask: when is subspace monotonicity satisfied?
For the interested user, subspace monotonicity is trivially

Proof. Definition-1) is equivalent to (4). We also establish the
equivalence of definition-2) to (5):
X
(4) or x∈X (S)
x ∈ arg max
gα (uk )
⇔
u∈X

k∈S

x ∈ arg max
u∈X (S)

X

gα (uk ) ⇔

k∈S

xD S ∈ arg max

u∈Γ(S)

|S|
X

gα (ui ),

i=1

where the last follows by a dimension permutation.

T (S ∗ ) =

X

max
S⊆{1,...,K}

xk

(6)

X

(7)

k

s.t. x ∈ arg max
u∈X

k∈S
c

xk = 0, k ∈ S

gα (uk )

(8)

|S| ≥ smin ,
(9)
where, (7)-(8) ensure that the solution vector is (S, α)-selective
fair, the constraint (9) ensures that at least smin users are
served, and the objective (6) aims to achieve the maximum
sum throughput denoted as T (S ∗ ) (from (3) this is equivalent
to minimizing P oF ). Problem (6)-(9) is an admission control
problem with fairness constraints.
We give a pictorial example of P oF minimization. Consider
a 3-user wireless downlink with feasible throughputs shown
in figure 3. The system operates with proportional fairness
(α = 1) and must serve at least smin = 2 users. Figure 3 shows
all possible selective fair points, where the points ({k}, 1), k =
1, 2, 3, ∅ (indicated as dots with white interior) are infeasible
due to constraint (9). Among the feasible (S, 1)-selective fair
points, the optimization selects the point with the maximum
total throughput, which in this case is ({1, 2}, 1).
Corollary 1. Suppose a system is operated with a policy that
solves (6), and denote the total achieved throughput by TK

satisfied for
P a resource allocation problem constrained on a
simplex ( k xk ≤ 1), where users can be ordered with
marginal utilities. Next, we will show that it also applies to
our problem under a specific condition for the channels. Recall
that Rk (t) is the user k instantaneous channel rate, which is
random independently distributed across users and time. In the
remaining of the paper we make the following assumption.
Assumption 1 (Stochastic dominance). The channels are
stochastically dominated: there exists a permutation σ(.) of
user indices, such that Rσ(1) (t) ≥st · · · ≥st Rσ(K) (t), where
Rσ(i) (t) ≥st Rσ(j) (t) means


P Rσ(i) (t) > x ≥ P Rσ(j) (t) > x , ∀x, t.
Assumption 1 is mild and holds for many practical cases of
interest, such as identically distributed fading channels with
different means.
Lemma 1. Consider a K-user wireless downlink where Assumption 1 holds. Then the feasible throughputs X satisfy the
subspace monotonicity.
The proofs are in the Appendix.
D. Minimizing P oF with online experts
We propose an efficient online scheme to minimize P oF
(6). Building on the subspace monotonicity property, our
scheme is shown to achieve optimal performance using a
small number of GBS experts. First we define the notion
of Gradient-Based Scheduler (GBS) expert for set S ⊆ K.
GBS(S) uses the real system observations R(t) to simulate
the (S, α)-selective fair performance.
GBS(S) expert:
Initialize: xSk (0) = 0, ∀k ∈ S.
Iterate: At t, observe R(t) and do:

Theorem 3. Assume stochastically dominated channels and
permutation σ(.) such that corollary 2 holds. Then the Selective GBS converges almost surely to T (S ∗ ):
)
(
X
sel
∗
xk (t) = T (S ) = 1.
P lim
t→∞

k

Notably from (11), the best expert is used to decide the user
set restriction S ∗ (t), but the scheduling decision of Selective
GBS is ultimately made according to xsel
k (t), which is different
from what the experts see, xSk (t).
The Selective GBS is an online policy that does not require knowledge of fading statistics and can adapt to system changes. Additionally, it requires only O(K) number of
GBS(S) experts, and hence a) selecting the best expert at each
slot, and b) storing expert data in memory, is efficient.
As input, Selective GBS requires the minimum number
of accepted users smin and the permutation σ(.) that orders
the users in decreasing average SNR. The latter can be kept
updated using frequent measurements. Determining smin is
however complicated in practice; we should avoid blocking
certain subscribers forever. The next section proposes our main
result that deals with this issue: a novel stochastic framework
which allows to determine the optimal set of blocked users on
each scheduling realization while providing blocking frequency
guarantees.
IV. S TOCHASTIC SELECTIVE FAIRNESS

1) Scheduling: Choose user k ∗ randomly from the set
Rk (t)
arg max S
k∈S (x (t))α
k
2) Throughput update:
t
1
xSk (t + 1) =
xS (t) +
Rk (t)1(k=k∗ )
t+1 k
t+1
Observe that the GBS(S) expert converges to T (S) and
hence ensures α-fairness for the user set S. To minimize P oF ,
we next present the Selective GBS policy that precludes users
from scheduling according to the best GBS(S) expert.
Selective GBS:
Input: smin , permutation of user indices σ(.).
Initialize: xsel
k (0) = 0, ∀k = 1, . . . , K. Consider the stronger
user set per cardinality:
Si = {σ(1), σ(2), . . . , σ(i)}, ∀i ∈ {1, 2, . . . , K}
(10)
Initialize all GBS(S) experts for S = Ssmin , . . . , SK .
Iterate: At t, observe R(t) and do:
1) Expert update: Throughput update xSk (t) for each of the
experts GBS(Ssmin ), GBS(Ssmin +1 ), . . . , GBS(SK ).
2) Expert selection: Choose the expert with highest total
accumulated throughput
X
S ∗ (t) ∈ arg max
xSk i (t)
{Si }i≥smin

3) Scheduling: Choose user k ∗ randomly from the set
Rk (t)
arg max
(11)
α
∗
k∈S (t) (xsel
k (t))
4) Throughput update:
t
1
xsel
xsel (t) +
Rk (t)1(k=k∗ )
k (t + 1) =
t+1 k
t+1

k∈Si

In wireless systems the actual number of users and their
average channel quality varies from base station to base station
and from time to time, hence it is impossible to operate
selective fairness with a predetermined smin . Instead, we
require a scheme that can adapt the number of selected users
in an online fashion in order to a) improve system efficiency,
and b) ensure Quality of Service.
A. Novel SLA
We follow a stochastic approach; we propose a novel
Service Level Agreement (SLA), such that an arbitrary user
is guaranteed to be selected with probability 1 − , where 
is tunable. As opposed to the snapshot scheduling of section
III, we consider a sequence of scheduling problem instances
z 1 , z 2 , . . . , where each z n is a realization of the random
variable Z describing the spatial distribution of the users, that
is the set of active users K(Z) and their average SNRs due
to slow fading, denoted by SN Rk for user k ∈ K(Z). Then
let yk (Z) = 1 indicate the event that user k is selected at a
random realization Z, we require the probabilistic constraint:
PZ (yk (Z) = 1|k ∈ Z) ≥ 1 − , ∀k.
The users are considered statistically equivalent, hence the
constraint intuitively captures the behavior of an ergodic
subscriber, i.e., one who buys a service with the associated
SLA, and then uses the service over a long time horizon

each time from possibly different locations. In this context,
the constraint implies that such a subscriber will be rarely
blocked.

tive function as a time average over scheduling realizations:
(
)
X
EZ
Tk∗ (Z, y(Z)) =
k

1
lim
E
N →∞ N
Fig. 5: Scheduling over multiple realizations.

B. Problem formulation
In this section we formalize a P oF minimization over
multiple scheduling realizations. Let T (n) = {tn , ..., tn+1 −1}
be the set of time slots spanned by the n−th realization of
the spatial distribution, Z n . Then, given the realization of
the spatial distribution in T (n), z n , we solve a selective-fair
scheduling problem where we need to decide which users to
admit in the system for these slots; let this decision be denoted
by y(z n ). We need the following assumption for time scale
separation:
Assumption 2 (Time scale separation). The changes in spatial
realizations occur in a slower time scale than the fast fading.
In particular, the duration of a realization T (n) is long enough
for the empirical throughput averages to converge to the α-fair
rates, that is
tn+1 −1
X
1
µk (t) − Tk∗ (z n , y(z n )) ≤ δ,
|T (n)| t=t
n

for some small δ > 0, where Tk∗ (z n , y(z n )) is the optimal
selective α-fair rate vector for spatial realization z n , given the
admission decision y(z n ).
The above assumption implies that user arrivals/departures
and slow fading fluctuations occur slower than the convergence
of the scheduler, which in practice takes a few seconds.
Let the admission policy y(.) be a function from spatial
realizations to deciding if a user will be admitted or not. Our
general problem then is to find the admission policy to solve
the following stochastic optimization:
(
)
X
∗
max EZ
Tk (Z, y(Z))
(12)
y

k

s.t. PZ (yk (Z) = 1|k ∈ Z) ≥ 1 − , ∀k,
(13)
where the constraint (13) ensures the satisfaction of the SLA of
each subscriber, and the maximal value of (12) represents the
best way the system can use the available admission budget
to minimize the P oF . Note that this minimization is very
complicated since it jointly considers i) the actual number of
active users at each realization, ii) the random user locations
and corresponding average SNRs, and iii) the cost of fairness.
We proceed to reformulate the problem as an optimization
of time-averages. First, it will be useful to transform the peruser SLA constraints into an equivalent constraint for the total
number of admitted users:
Lemma 2. Assume the spatial distribution of all users is the
same. Then,(13) is equivalent
 to
 X

EZ
yk (Z) ≥ (1 − )EZ {|K(Z)|}


k∈K(Z)

Then, we use the law of large numbers to express the objec-

(N −1
X X

)
Tk∗ (z n , y(z n ))

,

n=0 k∈z n

where the expectation is taken with respect to possible random
control (if the control is deterministic it can be eliminated).
Finally, constraint (13) can be rewritten as a time average of
indicator functions:
(N −1
)
X
1
n
1(k∈Z n ) yk (Z n ) ≥ (1 − )EZ {|K(Z)|} .
E
lim
N →∞ N
n=0
(14)
The problem to solve now has become:
(N −1
)
X X
1
∗
n
max
lim
E
Tk (z n , y (z n )) . (15)
{y n }n ,(14) N →∞ N
n=0
k∈z n

V. S TOCHASTIC S ELECTIVE FAIR P OLICIES
The form of (15) motivates a stochastic optimization approach [18], where we can use a virtual queue to ensure the
satisfaction of the time-average constraint.
Define a virtual queue Q(n), which evolves at the same
time scale as the spatial process as follows:
+
Q(n + 1) = [Q(n) + A(n) − D(n)] ,
(16)
where A(n) is defined as
(
|K(Z n )|, w.p. 1 − 
A(n) =
(17)
0, w.p. ,
P
and D(n) = D(Z n , y n (Z n )) = k∈K(Z n ) ykn (Z n ) is the
number of users admitted at the n−th spatial realization. Note
that A(n) is a random variable with mean (1−)EZ {|K(Z)|}.
The idea then is that, if the queue is stable, the mean of its
service D(n) will be larger than the one of its its arrivals
A(n), and the equivalent SLA constraint (14) will be met.
Therefore, our policy will strive to stabilize Q(t). We observe
that the virtual queue can be seen as a counter to track/learn
the Lagrange multiplier corresponding to the SLA constraint.
A. Known selective fair throughputs
We first deal with the case where given a realization
P ∗ z n , the
corresponding selective-fair sum throughputs
k Tk (z n , y)
are known for each y.
Drift Plus Penalty (DPP):
Initialize: Fix parameter V > 0.
Iterate over scheduling realizations: At the beginning of tn :
1) User selection: 
X
Q(n)
y n = arg max 
Tk∗ (Z n , y) +
y
V
k


X

yk  .

k∈K(Z n )

(18)
P n
2) Virtual queue update: Set D(n) =
y
,
draw
a
k k
random variable A(n) and update the queue as in (16).
Theorem 4. The DPP satisfies the SLAs, and yields sum
throughput within O(1/V ) of the maximum in (15).

B. Unknown selective fair throughputs
P ∗
In practice determining
k Tk (z n , y) for a given set of
users y knowing their channel statistics is very challenging,
with the exception of proportional and max-min fairness,
where approximations exist [21], and the case of max throughput where the solution is to always admit all users. Therefore,
we cannot always apply the DPP policy. In this section we
propose a combination of Selective
GBS (which requires smin )
P
and DPP (which requires k Tk∗ (z n , y)), to design an policy
which progressively learns the best user set
Pand thus does not
need the information of neither smin , nor k Tk∗ (z n , y). The
only information needed is the ordering of the users according
to their SNRs, which is found by measurements.
Online Selective Fair (OSF) Scheduler:
Initialize: Fix parameter V > 0, virtual queue service
S ∗ (0) = S.
Iterate tn (over scheduling realizations):
1) Update virtual queue: Generate the random variable
A(n), as per (17), set D(n) = |S ∗ (tn )|, i.e. the
cardinality of the subset chosen in the last slot of
last realization, and update the queue: Q(n + 1) =
+
[Q(n) − D(n) + A(n)] .
2) User ordering: Consider current user realization z n , and
Kn = |K(z n )|. Then permute users with σ(.) such that
SN Rσ(1) ≥ SN Rσ(2) ≥ ... ≥ SN Rσ(Kn ) .
3) Initialize next realization: Reset t = 0, construct sets Si
as per (10), set xk (0) = 0, ∀k and xSk i (0) = 0, ∀k ∈ Si
for each expert i, and run the next realization using the
following policy:
Iterate t:
1) Expert update: Execute one step of each expert
GBS(Si ), i ∈ {1, 2, ..., Kn } using R(t). Let xSi (t + 1)
be the vector of accumulated throughputs of expert i.
2) Expert selection: Choose the expert that maximizes:
"
#
X
Q(n)
Si
∗
S (t) = arg max
xk (t + 1) + |Si |
V
{Si }i
k∈Si

3) Scheduling: Choose user k ∗ (t) randomly from the set:
Rk (t)
arg max
k∈S ∗ (t) (xk (t))α
4) Throughput update:
t
1
Rk (t)1(k=k∗ (t))
xk (t + 1) =
xk (t) +
t+1
t+1
Corollary 3 (Optimality of OSF). Let assumptions of i)
time-scale separation, ii) statistically identical users, and iii)
stochastically dominated channels hold. Theorem 3 implies
that at each scheduling realization the experts converge to the
corresponding selective fair throughputs, hence OSF chooses
the action that maximizes (18), and by Theorem 4 OSF
satisfies the SLA constraints and yields sum throughput within
O(1/V ) of the maximum in (15).
A few remarks about OSF operation: searching for the best
expert and storing data for all experts is O(K), hence OSF
has low-complexity. Also, to determine D(n), we need an
estimate of the number of users admitted in last realization.

For this, we have used the cardinality of the selected users
by the best expert at the last slot. Theoretically, due to the
time-scale separation, all the experts and the scheduler have
converged and hence this is indeed the number of users served
in that realization. In our simulations, the convergence is not
completely reached but this method remains accurate.
VI. N UMERICAL R ESULTS
In this section we evaluate the performance of OSF against
policies that block users with average SNR below a threshold,
and against the case where no admission control is done and
all users are served in a fair manner. We consider a system
with 100 subscribers, each requesting a probabilistic SLA
of being served 95% of the time. The system evolves as
per figure 5. At each scheduling realization, a subscriber is
active with probability 0.1 and is placed uniformly at random
in a cell. The parameters are chosen such that a user at
the edge of the cell has an average SNR of −5dB. Each
scheduling realization lasts for 3000 time slots, and at each
slot the channel realizations are drawn from a Rayleigh fading
distribution.
The results are presented in figure 6. Figures 6b-6c show
the case α = 1; the OSF policy achieves the SLA (6b) and
outperforms the best naive threshold admission control that
also achieves the SLA by approximately 40% in terms of
total throughput (6c). In addition, it outperforms the policy
that does no admission control by a wider margin. Figure 6d
compares P oF for different values of α. In low values of α,
where fairness constraints are loose, all policies have similar
performance. As α increases, having a good user admission
strategy makes fairness cheaper; the P oF of OSF increases
slower than the other two policies. We attribute the gains of
our approach to accurately considering the actual impact of
blocking to P oF .
We also experimented with more stringent values of the
SLA. For α = 1 the gain in system throughput with respect
to the best threshold policy that satisfies the SLA is 10% and
2% for corresponding selection probabilities 99% and 99.9%.
Decreasing gain for more stringent SLA is to be expected,
since for selection probability 1 all the policies will yield the
same P oF -they are all forced to accept all users at all times.
However, we mention that the probability of good coverage
of LTE is measured in drive tests to be 90-95% [22], which
induces a fairly large amount of blocking.
VII. C ONCLUSIONS
In this paper, we introduced selective fairness, the idea
of providing fairness to some users and blocking the others,
in order to mitigate the adverse effect of users with very
poor channel quality. Extending this concept to the stochastic setting, we derived an online policy that maximizes the
system’s throughput subject to satisfying an SLA on the user
blocking probability. Our intelligent blocking outperforms by
40% naive approaches that simply block low-SNR users. It
is worth noting that our results can be easily extended to
multiple SLA classes using one queue for each class, as well
as systems with multiple cells using an operator-wide global
queue. Analyzing the transient behavior of the selective GBS



Online Selective Fair
No Admission Control

Admission Probability

Throughput [bits/s/Hz]


@
R meet SLA
@

40% improvement

Price of Fairness

6
?

Threshold −4.95dB
Threshold −3dB
Threshold −1dB

(a)

Scheduling realization index

(b)

Scheduling realization index

(c)

(d)

α

Fig. 6: Simulation results for blocking probability 5%: (a) Plot legends. (b) Empirical admission probabilities for α = 1. (c) Empirical
average system throughput for α = 1. (d) Price of Fairness for different levels of fairness (values of α).

with experts and extending our results to cases where users
have different spatial distributions are very interesting topics
for further study.
R EFERENCES
[1] H. J. Kushner and P. A. Whiting, “Convergence of proportional-fair
sharing algorithms under general conditions,” IEEE Transactions on
Wireless Communications, pp. 1250–1259, 2004.
[2] P. Viswanath, D. N. C. Tse, and R. Laroia, “Opportunistic beamforming
using dumb antennas,” IEEE Transactions on Information Theory, pp.
1277–1294, 2002.
[3] D. Bertsimas, V. F. Farias, and N. Trichakis, “The price of fairness,”
Oper. Res., pp. 17–31, 2011.
[4] R. Knopp and P. A. Humblet, “Information capacity and power control
in single-cell multiuser communications,” in IEEE ICC, 1995.
[5] R. Agrawal and V. Subramanian, “Optimality of certain channel aware
scheduling policies,” in Allerton, 2002.
[6] A. L. Stolyar, “On the asymptotic optimality of the gradient scheduling
algorithm for multiuser throughput allocation,” Oper. Res., pp. 12–25,
2005.
[7] J. Huang, V. G. Subramanian, R. Agrawal, and R. A. Berry, “Downlink
scheduling and resource allocation for OFDM systems,” IEEE Transactions on Wireless Communications, pp. 288–296, 2009.
[8] A. Eryilmaz and I. Koprulu, “Discounted-rate utility maximization
(DRUM): A framework for delay-sensitive fair resource allocation,” in
WiOpt, 2017.
[9] P. Bender, P. Black, M. Grob, R. Padovani, N. Sindhushyana, and
S. Viterbi, “CDMA/HDR: a bandwidth efficient high speed wireless data
service for nomadic users,” IEEE Communications Magazine, pp. 70–77,
2000.
[10] A. Leith, M. S. Alouini, D. I. Kim, X. Shen, and Z. Wu, “Flexible
proportional-rate scheduling for OFDMA system,” IEEE Transactions
on Mobile Computing, pp. 1907–1919, 2013.
[11] F. Capozzi, G. Piro, L. A. Grieco, G. Boggia, and P. Camarda, “Downlink Packet Scheduling in LTE Cellular Networks: Key Design Issues
and a Survey,” IEEE Communications Surveys Tutorials, pp. 678–700,
2013.
[12] D. Bethanabhotla, G. Caire, and M. J. Neely, “WiFlix: Adaptive video
streaming in massive MU-MIMO wireless networks,” IEEE Transactions
on Wireless Communications, pp. 4088–4103, 2016.
[13] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, “Rate control in communication networks: shadow prices, proportional fairness and stability,”
Journal of the Operational Research Society, pp. 237–252, 1998.
[14] D. Bertsimas, V. F. Farias, and N. Trichakis, “On the efficiency-fairness
trade-off,” Manage. Sci., pp. 2234–2250, 2012.
[15] X. Xiang, C. Lin, X. Chen, and X. Shen, “Toward optimal admission
control and resource allocation for LTE-A femtocell uplink,” IEEE
Transactions on Vehicular Technology, pp. 3247–3261, 2015.
[16] M. J. Neely, E. Modiano, and C. P. Li, “Fairness and optimal stochastic
control for heterogeneous networks,” IEEE/ACM Transactions on Networking, pp. 396–409, 2008.
[17] T. Bonald and A. Proutière, “Wireless downlink data channels: User
performance and cell dimensioning,” in ACM MobiCom, 2003.
[18] L. Georgiadis, M. J. Neely, and L. Tassiulas, “Resource allocation and
cross-layer control in wireless networks,” Found. Trends Netw., pp. 1–
144, 2006.
[19] B. Radunovic and J. Y. L. Boudec, “A unified framework for max-min
and min-max fairness with applications,” IEEE/ACM Transactions on
Networking, pp. 1073–1083, 2007.
[20] J. Mo and J. Walrand, “Fair end-to-end window-based congestion
control,” IEEE/ACM Transactions on Networking, pp. 556–567, 2000.

[21] R. Combes, Z. Altman, and E. Altman, “On the use of packet scheduling
in self-optimization processes: Application to coverage-capacity optimization,” in WiOpt, 2010.
[22] J. Furuskog, K. Werner, M. Riback, and B. Hagerman, “Field trials of
LTE with 44 MIMO,” Ericsson review, 2010.
[23] M. J. Neely, Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool Publishers,
2010.

A PPENDIX
Proof of Lemma 1: Without loss of generality we will
compare two sets of users K = {1, . . . , K − 1, K} and K0 =
{1, . . . , K − 1, K 0 } (here indices are not indicative of channel
quality), where the the channel state probability distribution of
all users is the same except of user K 0 , ql , which dominates
that of K, pl :
m
m
X
X
ql ≥
pl , m = 1, . . . , L.
l=1

l=1

and for weights β1 ≥ β2 ≥ · · · ≥ βL ≥ 0, it follows
L
L
X
X
ql βl ≥
pl βl ,
l=1

(19)

l=1

which we will use later.
Let Γ(A) be the feasible rate region of user set A. Then
we should show that Γ(K) ⊆ Γ(K0 ). If we prove this
pairwise comparison, then the subspace monotonicity follows
by extending to all sets of same cardinality using the stochastic
dominance order.
Define Γ(K, s) as the set of feasible throughput vectors
given that the channel states of users {1, . . . , K − 1} are fixed
to s ∈ RK−1 and only the channels of the last user vary. More
specifically, we will show that Γ(K, s) ⊆ Γ(K0 , s), ∀s, from
which the result
X follows since X
Γ(K) =
π(s)Γ(K, s) ⊆
π(s)Γ(K0 , s) = Γ(K0 ).
s

s

where π(s) = ΠK−1
k=1 P(Rk (t) = rk (s)) is the probability of
state s.
Fix some s ∈ RK−1 , and choose a vector u ∈ Γ(K, s), we
want to show that u ∈ Γ(K0 , s). Denote φk,l the fraction of
time user k is scheduled whenP
the channel state of the last user
is l, where φk,l ∈ [0, 1] and k φk,l ≤ 1, ∀l. The following
hold:

P
uk = Pl pl φk,l rk (s), ∀k < K
uK = l pl φK,l Rl .
Here, let us observe that since the channel states s are fixed,
the throughputs uk , k < K depend only
P on the total fraction
of time assigned to these users 1 − l pl φK,l irrespective of
state l. To this end, consider the optimization problem:
X
min
pl φK,l
(20)
[φK,l ]l=1,...,L

l

s.t. uK =

X

pl φK,l Rl

l

φK,l ∈ [0, 1],
where the solutions of this problem ensure both the achievability of throughput uK (due to first constraint) but also that
there remain enough time fractions to achieve uk , k < K (due
to the objective). Let φ∗ be a solution to (20), we have
X
X
pl φ∗K,l ≤
pl φK,l ,
l
l
P
hence the time users k < K are scheduled 1 − l pl φ∗K,l is
large enough such that there must exist coefficients (φ∗k,l )k<K
for which:
X
uk =
ql φ∗k,l rk (s), ∀k < K.
(21)
l

Additionally, due to the form of the optimization problem

(20), we must also have that φ∗K,1 ≥ φ∗K,2 ≥ · · · ≥ φ∗K,L ,
hence it is also φ∗K,1 R1 ≥ φ∗K,2 R2 ≥ · · · ≥ φ∗K,L RL , and
using (19) it follows
X
X
ql φ∗k,l Rl ≤
pl φ∗k,l Rl ,
l

l

and hence
uK =

X

ql φ∗K,l Rl ,

l

which combined with (21) proves that u ∈ Γ(K0 , s), and
concludes the proof that Γ(K, s) ⊆ Γ(K0 , s), ∀s.
Proof of Theorem 3: We assume that T (Si ) 6= T (Sj ),
define Bi (δ) = (T (Si ) − δ, T (Si ) + δ) and choose δ0 > 0
such that
Bi (δ0 ) ∩ Bj (δ0 ) = ∅, ∀i, j ∈ {smin , . . . , K}.
We also define the following events:
(
)
X
Si
δ
Ai (t) =
xk (τ ) − T (Si ) ≤ δ, ∀τ ≥ t .
k∈Si

By the almost sure convergence of GBS [5], [6], we have: for
every  > 0, there exists a finite M0 () such that
n
o
√
(22)
P Aδi 0 (t) > K 1 − , ∀t > M0 (), ∀i.
This, together with how we chose δ0 , implies that ∀t ≥ M0 ():
K
n
o
Y
P {S ∗ (τ ) = S ∗ , ∀τ ≥ t} ≥
P Aδi 0 (t) > 1 − . (23)
i=smin

Now, define the event that determines the convergence:
(
)
X
∗
C δ (t) =
xsel
k (τ ) − T (S ) ≤ δ, ∀τ ≥ t ,
k

and fix any , δ > 0. From the almost sure convergence property of GBS, we know that if for some S ∗ (t) = S ∗ , ∀t ≥ τ0
for some τ0 then there exists a constant M1 (δ) such that the
above event is true for all t0 ≥ τ0 + M1 (δ). In addition, from
(23) we have that S ∗ (t) = S ∗ , ∀t ≥ τ0 with probability at least
1− for τ0 ≥ M0 (), as defined in (22). The above discussion
implies that, there exists a t00 (, δ) = M0 () + M1 (δ) (any
value greater than this quantity will also do) such that

P C δ (t) − 1 < , ∀t ≥ t00 (, δ),

which implies limt→∞ P C δ (t) = 1, ∀δ > 0.
Proof of Lemma 2: Due to the identical spatial distribution for all users, it follows that for any y ∈ Π and any two
users k, k 0 ∈ K we must have:
PZ (yk (Z) = 1|k ∈ Z) = PZ (yk0 (Z) = 1|k 0 ∈ Z) .
Let p(y) = PZ (yk (Z) = 1|k ∈ Z), conditioning on (k ∈ Z)
we obtain:


 X

EZ
yk (Z) =


k∈K(Z)
X
=
PZ (k ∈ Z) PZ (yk (Z) = 1|k ∈ Z)
k

= p(y)

X

PZ (k ∈ Z) = p(y)EZ {|K(Z)|} .

k

Eq. (13) then implies that p(y) ≥ 1−, yielding the desired.
Proof of Theorem 4: Let y ∗ (z n ), n = 1, 2, . . . denote
the optimal solution of (12)-(13), i.e. a (possibly randomized)
function from a scheduling realization to a user admission

decision; existence of optimal stationary randomized policies
is established in [23]. To prove optimality of DPP, we will
compare to the performance of y ∗ (z n ) with respect to the
Lyapunov drift. Indeed, we first define the drift of policy y:
X
∆(y, Z, Q) =
(V Tk∗ (Z, y) + Qyk ) .
k∈K(Z)

Recall that y n denotes the decision of DPP at realization n,
and observe that it is designed to minimize the quantity ∆(.).
Then, for a given scheduling realization z n and given value
of the virtual queue Q(n), we can show that
(
)
X
 2
E Q (n + 1) − Q2 (n) − V E
Tk∗ (zn , y n (z n ))
k

≤ B + Q(n)E {A(z n )} − E {∆(y n , z n , Q(n))}
≤ B + Q(n)E {A(z n )} − E {∆(y ∗ , z n , Q(n))} ,
where B is a constant that depends only the parameters of the
system. Additionally, from optimality of y ∗ we have
(
)
X
 2
E Q (n + 1) − Q2 (n) − V E
Tk∗ (zn , y n (z n ))

≤B−VE

k

 X



k∈KZ)



Tk∗ (zn , y ∗ (z n )) ,


from which we can deduce that (i) Q(n) is (mean rate) stable
therefore the SLA constraints hold and (ii) the value of the
average throughput less than the optimal by at most B/V ,
finishing the proof.

