arXiv:1710.11471v2 [cs.PF] 21 Nov 2017

Distributed Server Allocation for Content Delivery
Networks
Sarath Pattathil, Vivek S. Borkar and Gaurav S. Kasbekar

∗

Abstract
We propose a dynamic formulation of file-sharing networks in terms
of an average cost Markov decision process with constraints. By analyzing a Whittle-like relaxation thereof, we propose an index policy in
the spirit of Whittle and compare it by simulations with other natural
heuristics.

1

Introduction

Recently, Content Delivery Networks (CDNs), which distribute content (e.g.,
video and audio files, webpages) using a network of server clusters situated at multiple geographically distributed locations, have been extensively
deployed in the Internet by content providers themselves (e.g., Google) as
well as by third-party CDNs that distribute content on behalf of multiple
content providers (e.g., Akamai’s CDN distributes Netflix and Hulu content) [18], [14]. The delay incurred in downloading content to an end user is
often significantly lower when a CDN is used compared to the case where all
content is downloaded from a single centralized host, since the server clusters
of a CDN are located close to end users [18], [14].
In this paper, we consider a server cluster, which contains M ≥ 2 servers
and is part of a CDN. The server cluster stores N large files (e.g., videos).
There is a high demand for each file, and hence each file is replicated at
mutiple servers within the cluster. Requests for the N files from end users
∗

Sarath Pattathil, Vivek S. Borkar and Gaurav Kasbekar are with the Department of
Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076,
India. Email: sarathpattathil@iitb.ac.in, borkar.vs@gmail.com, gskasbekar@ee.iitb.ac.in.
The work of VSB was supported in part by a J. C. Bose Fellowship and a grant for ‘Approximation of High Dimensional Optimization and Control Problems’ from the Department
of Science and Technology, Government of India.

1

or from smaller server clusters arrive at the server cluster from time to time.
Now, there are two approaches to serving the file requests [26, 28]: (i) Single
Server Allocation: Each file request is served by a single server [26, 28].
(ii) Resource Pooling: Each file request is simultaneously served by multiple
servers– in particular, different chunks of the file are served by different
servers in parallel [26, 28]. Resource pooling has been found to outperform
single server allocation in prior studies [26, 27, 28] and hence, in this paper,
we assume that resource pooling is used. Also, we allow multiple files to be
simultaneously downloaded from a given server. At any time instant, the
sum of the rates at which a server j transmits different files is constrained to
be at most µj . Requests for different files are stored in different queues, and
there is a cost for storing a request in a queue. Let ξ ij (t) be the rate at which
server j transmits file i at time t. We consider the problem of determining
the rates ξ ij (t) for each i, j and t so as to minimize the total storage cost.
We formulate this problem as a Markov Decision Process (MDP) [11]. We
show that this problem is Whittle-like indexable [33] and use this result to
propose a Whittle-like scheme [33] that can be implemented in a distributed
manner 1 . We evaluate the performance of our scheme using simulations and
show that it outperforms several natural heuristics for the problem such as
Balanced Fair Allocation, Uniform Allocation, Weighted Allocation, Random
Allocation and Max-Weight Allocation.
We now review related prior literature. In [27], performance of Content
Delivery Networks is evaluated in a static framework. This work also studies
the tradeoffs between delay for each packet vs the energy used etc. The polymatroid structure of the service capacity in this model is exploited to get an
expression for mean file transfer delay that is experienced by incoming file
requests. Performance of dynamic server allocation strategies, such as random server allocation or allocation of least loaded server, are also explored.
We use the model of [27] for CDN, but go a step further by looking at a fully
dynamic optimization problem as an MDP.
In [28], a centralized content delivery systems with collocated servers is
studied. Files are replicated in these servers and these serve as a pooled resource which cater to file requests. The article shows how dynamic server capacity allocation outperforms simple load balancing strategies such as those
which assign the least loaded server, or assign the servers at random. The
article also goes on to study file placement strategies that improve the utility
1

We use the phrase ‘Whittle-like’ instead of just Whittle because the scheme introduced
in this paper, although is in the same spirit of Whittle’s original paper, is not exactly the
same.

2

of the system.
Several works including [16, 20, 34, 17] look at large-scale content delivery networks, focusing on placement of content in the servers. Of these,
[16] also studies the greedy method of server allocation and its efficiency
under various regimes of server storage capacities, and under what content
placement strategy it would be efficient. Article [34] studies strategies for
scheduling after the content placement stage, and proposes an algorithm,
called the Fair Sharing with Bounded Degree (FSBD), for server allocation.
In [29] muliclass queuing systems are studied with different arrival rates.
The service rates are constrained to be in a symmetric polymatroid region.
Large scale systems with a growing number of service classes are studied and
several asymptotic results regarding fairness and mean delays are obtained.
Multi-server models are studied in [30] with each server connected to
multiple file types and each file type stored in multiple servers, thereby creating a bipartite graph. This article focuses on the scaling regime where the
number of servers goes to infinity. It is shown that even if the average degree dn << n := the number of servers, an asymptotically vanishing queuing
delay can be obtained. These results are based on a centralized scheduling
strategy.
In [3], multi-server queues are studied with an arbitrary compatibility
graph between jobs and servers. The paper designs a scheduling algorithm
which achieves balanced fair sharing of the servers. Several parameters are
analyzed using this policy by drawing a parallel between the state of the
system at any time to that of a Whittle network.
However, none of the above papers [28, 16, 20, 34, 17, 29, 30, 3] show
Whittle indexability of the respective resource allocation problems they address. In the present work we take an alternative approach which considers
a dynamic optimization or control problem that can be interpreted as a
problem of scheduling restless bandits. We analyze it in the framework laid
down by Whittle for deriving a heuristic index policy [33]. To the best of
our knowledge, this paper is the first to show Whittle-like indexability of
the server allocation problem, in the setting of a CDN server cluster that
uses resource pooling, with the objective of minimization of the total file
request storage cost. The fact that this problem is Whittle-like indexable
allows us to decouple the original average cost MDP, which is difficult to
solve directly, into more tractable separate control problems for individual
file types. The decoupling leads to an efficient algorithm based on computation of Whittle-like indices, which outperforms several natural heuristics for
the problem.
The Whittle index heuristic has been successfully applied to various re3

source allocation problems including: crawling for ephemeral content [5],
congestion control [6], UAV routing [23], sensor scheduling [22], routing in
clusters [21], opportunistic scheduling [8], inventory routing [2], cloud computing [9] etc. General applications to resource allocation problems can be
found in [15]. Book length treatments of restless bandits can be found in
[13] and [25].
The rest of the paper is structured as follows: In section 2, we discuss
the model which is used and formulate the problem as a Markov Decision
Process (MDP). Section 3 shows various structural properties of the value
function of the MDP formulated in section 2. In section 4, we prove that
the problem of server allocation in the resource pooling setting is in fact
indexable and provide a scheme to compute this index. Section 5 discusses
other heuristics for server allocation and presents numerical comparisons of
the proposed index policy with some other heuristics. We conclude the paper
with a brief discussion in Section 6.
We conclude this section with a brief introduction to the Whittle index
[33]. Let X i (t), t ≥ 0, 1 ≤ i ≤ N , be N Markov chains, each with two
modes of operations: active and passive, with associated transition kernels
p1 (·|·), p0 (·|·) resp. Let r1 (X i (t)), r0 (X i (t)) be instantaneous rewards for the
ith user in the respective modes with r1 (·) ≥ r0 (·). The goal is to schedule
active/passive modes so as to maximize the total expected average reward
T −1
1 XX
lim
E[rν j (t) (X j (t))]
T →∞ T
t=0

j

where ν j (t)P= 1 if jth process is active at time t and 0 if not, under the
constraint j ν j (t) ≤ M ∀t, i.e., at most M processes are active at each
time instant. This hard constraint makes the problem difficult to solve (see
[24]). So following Whittle, one relaxes the constraint to
T −1
1 XX
E[ν j (t)] ≤ M.
T →∞ T

lim

t=0

j

This makes it a problem with separable cost and constraints which, given the
Lagrange multiplier λ, decouples into N individual problems with reward for
passivity changed to λ + r0 (·). The problem is Whittle indexable if under
optimal policy, the set of passive states increases monotonically from empty
set to full state space as λ varies from −∞ to +∞. If so, the Whittle index
for a given state can be defined as the value of λ for which both modes (active
and passive) are equally desirable. The index policy is then to compute these
4

for the current state profile, sort them in decreasing order, and render active
the top M processes, the rest passive. The decoupling implies O(N ) growth
of state space as opposed to the original problem, for which it is exponential
in N . Further, the processes are coupled only through a simple index policy.
The latter is known to be asymptotically optimal as N ↑ ∞ [31]. However,
no convenient general analytic bound on optimality gap seems available.

2

Model and problem formulation

Consider a server cluster that contains multiple servers, each of which stores
one or more files. We represent this system using a bipartite graph 2 G =
(F ∪ S; E) where F is a set of N files, S is a set of M servers, E is the set of
edges, and each edge e ∈ E connecting a file i ∈ F and server j ∈ S implies
that a copy of file i is replicated at server j (see Figure 1).

Figure 1: The model

For j ∈ S, Fj denotes the set of files that are stored in server j. Similarly,
for i ∈ F , Si denotes the set of servers that store file i. Requests for file
type i ∈ F arrive to the server cluster according to an independent Poisson
process with rate Λi . We assume that the job (requested file) sizes have
an exponential distribution. Let ξ ij (t) denote the rate at which server j
transmits file type i at time t. Then the capacity constraint at each server
2
Recall that a graph G = (V, E) is said to be bipartite if its node set V can be partitioned into two sets F and S such that every edge in E is between a node in F and a
node in S [32].

5

can be expressed as:
X
ξ ij (t) ≤ µj

∀t ≥ 0, j ∈ {1, 2, · · · , M }

(1)

i∈Fj

where µj is the maximum permissible rate of transmission from server j. We
make the blanket stability assumption.
Stability Assumption: Let F denote the set of files. For any A ⊂ F , let
SA = ∪i∈A Si . Then for stability of all queues, we assume:
X
X
Λi ≤
µj
∀A ⊂ F
(2)
i∈A

j∈SA

Let f i (x) be the cost for storing x jobs in the queue i. We assume f i (·) to
be an increasing convex function for i = 1, 2, · · · , N . Our aim is to minimize
the long run average cost, given by
1
lim sup
T →∞ T

T

Z

E[
0

N
X

f i (X i (t))]dt,

(3)

i=1

where X i (t) is the length of queue i at time t. Following the classic paper of
Whittle [33], we relax the per stage constraint (1) to an averaged constraint
1
lim sup
T →∞ T

T

Z
0

X

E[ξ ij (t)] ≤ µj

∀j ∈ {1, 2, · · · , M }.

(4)

i∈Fj

This is now a constrained Markov decision process [7] that leads to the
unconstrained problem with cost


Z T
N
X
X
X
1
lim sup
E
f i (X i (t)) +
λ̂j (µj −
ξ ij (t)) dt,
(5)
T
T →∞
0
i=1

j

i∈Fj

where λ̂j is the Lagrange multiplier associated with the j th relaxed constraint
lim sup
T →∞

1
T

Z

T

X
E[
ξ ij (t)] ≤ µj .

0

i

6

Given the values of the Lagrange multipliers λ̂j , this optimization problem
decouples into separate control problems for individual file types, with the
cost function for file type i given by:
X
ci (xi , λ̂) = f i (xi ) +
λ̂j (µj − ξ ij (t)).
(6)
j∈Si

where λ̂ = [λˆ1 , λˆ2 , · · · ]. The average cost dynamic programming (DP) equation for this MDP for file type i is given by [11]:


X
V i (n)Qi (n|m, ξ ij , j ∈ Si ) = 0
(7)
min ci (m, λ̂) − β i +
ξ ij ,j∈Si

n

where β i is the optimal cost for file type i and Qi is its rate matrix given by:
for z > 0,
Qi (z + 1|z, ξ ij , j ∈ Si ) = Λi ,
X
ξ ij (t),
Qi (z − 1|z, ξ ij , j ∈ Si ) =

(8)
(9)

j∈Si

X

Qi (z|z, ξ ij , j ∈ Si ) = − Λi +


ξ ij (t) ,

(10)

j∈Si

for z = 0,
Qi (1|0, ξ ij , j ∈ Si ) = Λi ,

(11)

Qi (0|0, ξ ij , j ∈ Si ) = −Λi ,

(12)

and V i (·) is the value function. Substituting the values of Qi back in the
DP equation and dropping the isolated superscript i for ease of notation, we
have3 :

X
min c(m, λ̂) − β + V (m + 1)Λ + V (m − 1)
ξ ij (t)
ξ ij ,j∈Si

j∈Si

− V (m) Λ +

X

ξ ij (t)




= 0,

(13)

j∈Si
3

Note that when the queue of file type i is empty, no server needs to provide any service
to that particular file type.

7

equivalently,

min

ξ ij ,j∈Si

f (m) +

X

λ̂j (µj − ξ ij (t)) − β + V (m + 1)Λ

j∈Si

+ V (m − 1)

X

ij

ξ (t) − V (m) Λ +

j∈Si

X

ij

ξ (t)




= 0.

(14)

j∈Si

The expression which is to be minimized is linear in ξ ij (t), j ∈ Si and each
ξ ij (t) has the capacity constraint which restricts the values of ξ ij (t) to be
≤ µj i.e. ξ ij (t) ∈ [0, µj ]. This combined with the fact that the objective is
linear ensures that the minimum is attained at a corner where each server is
either serving at full capacity or at zero capacity, i.e., ξ ij (t) = 0 or ξ ij (t) = µj
for all j ∈ Si .
Following [33], we propose an index policy for the problem of server
allocation to file types. Let us define λk to be the marginal utility of allowing
server k to serve at 0 rate, when all other servers containing the file type are
already serving at their full capacity. Since all other servers are serving at
full rate, we have that for all servers other than server k
ξ ij (t) = µj

∀ j ∈ Si , j 6= k

(15)

Adding V (m) on both sides of equation (14) we get:

X
V (m) = min f (m) +
λ̂j (µj − ξ ij (t))
ξ ij ,j∈Si

j∈Si

− β + V (m + 1)Λi + V (m − 1)

X

ξ ij (t)

j∈Si

+ V (m) 1 − Λi +

X

ξ ij (t)




(16)

j∈Si

If we scale all transition rates by a fixed multiplicative factor, it is tantamount
to time scaling which will scale the average cost, but not affect the optimal
policy. Hence without loss of generality, we can assume that the arrival and
service rates are such that the coefficients of V (·) that appear in equation
(16) are between 0 and 1 and can be interpreted as transition probabilities
of a discrete time Markov chain as explained below. Let λk = λ̂k µk . On

8

substituting ξ ij (t) = µj ∀ j ∈ Si , j 6= k, we have:

X
V (m) = f (m) − β + min λk +
p1 (n|m)V (n),

X
p2 (n|m)V (n) .

(17)

Here p1 (·|·) is the transition probability when the server does not serve this
file type and is given by (m > 0):
p1 (m + 1|m) = Λ,
X

p1 (m|m) = 1 − Λ +


µj ,

j∈Si ,j6=k

X

p1 (m − 1|m) =

µj ,

(18)

j∈Si ,j6=k

and p2 (·|·) is the transition probability when the server serves this file type
and is given by (m > 0):
p2 (m + 1|m) = Λ,
p2 (m|m) = 1 − Λ +

X


µj ,

j∈Si

p2 (m − 1|m) =

X

µj .

(19)

j∈Si

For m = 0, the transition probabilities p1 (·|·) and p2 (·|·) are the same and
are given by (for i = 1, 2):
pi (1|0) = Λ
pi (0|0) = 1 − Λ
In the next section, we prove some structural properties of the value
function.

3

Structural Properties of the Value function

This section closely follows the proof techniques of [1], [9] and [10].
Lemma 3.1. V (·) is increasing in the number of files.

9

Proof. The proof follows along the same lines as Lemma 5 in [10]. The main
idea is to consider two processes {Xt } and {Xt0 } on a common probability
space with different initial conditions x < x0 resp., but common arrival and
control processes. Then the result follows by pathwise dominance: Xt0 ≥ Xt
a.s. ∀t, combined with monotonicity of the cost, first for infinite horizon
discounted cost problem and then, by passing through the vanishing discount
limit, for average cost.
Lemma 3.2. V (·) has the property of increasing differences, i.e., for z > 0
and x > y.
V (x + z) − V (x) ≥ V (y + z) − V (y).
Proof. The proof follows along similar lines as Lemma 6 in [10] and Theorem
4 in [1], but with several crucial differences. The argument uses induction
on the finite horizon discounted problem. Let Vn (·) denote the α discounted
n−step problem. We embed the state space into the positive real line, R+ .
Consider the case when x > 0. First, we rearrange the terms to get the
following. Here u is the optimal control for state x.
X
Vn (x) = f (x)+αVn−1 (x + 1)Λ + αVn−1 (x)(1 − Λ −
µi )
i

+ αVn−1 (x − 1)

X

µi + (1 − u)λ

i6=k

+ (1 − u)αµk Vn−1 (x) + uαµk Vn−1 (x − 1)

(20)

We have that V0 (x) = f (x) which is convex. Assume that Vn−1 is convex.
Consider two states x1 and x2 with optimal control u1 and u2 . Without loss
of generality, assume that x1 > x2 . In this part, we assume x2 > 0.
Vn (x1 ) + Vn (x2 ) = f (x1 ) + f (x2 )
X
X
+ αVn−1 (x1 )(1 − Λ −
µi ) + αVn−1 (x2 )(1 − Λ −
µi )
i

i

+ αVn−1 (x1 + 1)Λ + αVn−1 (x2 + 1)Λ
X
X
+ αVn−1 (x1 − 1)
µi + αVn−1 (x2 − 1)
µi
i6=k

i6=k

+ (1 − u1 )λ + (1 − u1 )αµk Vn−1 (x1 ) + u1 αµk Vn−1 (x1 − 1)
+ (1 − u2 )λ + (1 − u2 )αµk Vn−1 (x2 ) + u2 αµk Vn−1 (x2 − 1).

10

Consider two separate cases depending on the values of u1 , u2 .
Case 1: u1 = u2
Vn (x1 ) + Vn (x2 )


x1 + x2
∗1
≥ 2f
2


X
x1 + x2
(1 − Λ −
µi )
+ 2αVn−1
2
i



X
x1 + x2
x1 + x2
+ 2αVn−1
+ 1 Λ + 2αVn−1
−1
µi
2
2
i6=k






u1 + u2
x1 + x2
u1 + u2
+2 1−
αµk Vn−1
+ 2λ 1 −
2
2
2




u1 + u2
x1 + x2
+2
αµk Vn−1
−1
2
2





X
x1 + x2
x1 + x2
+ 2αVn−1
(1 − Λ −
µi )
2
2
i


X

x1 + x2
x1 + x2
+ 1 Λ + 2αVn−1
−1
µi
+ 2αVn−1
2
2
i6=k


x1 + x2
+ 2λ(1 − u3 ) + 2(1 − u3 )αµk Vn−1
2


x1 + x2
+ 2u3 αµk Vn−1
−1
2


x1 + x2
= 2Vn
.
2
≥∗2 2f

(21)

2
Here u3 is the optimal control when the state has x1 +x
files. Inequality ∗1
2
follows from the convexity of f (·) and Vn−1 (·). Inequality ∗2 follows from
the definition of the optimal control u3 .

Case 2: u1 6= u2 :

11

Consider the case u2 = 0, u1 = 1 (The other case is similar)
Vn (x1 ) + Vn (x2 )


x1 + x2
∗1
≥ 2f
2


X
x1 + x2
+ 2αVn−1
(1 − Λ −
µi )
2
i



X
x1 + x2
x1 + x2
+ 2αVn−1
+ 1 Λ + 2αVn−1
−1
µi
2
2
i6=k

+ λ + αµk Vn−1 (x2 ) + αµk Vn−1 (x1 − 1)



X
x1 + x2
x1 + x2
+ 2λ + 2αVn−1
(1 − Λ −
µi )
= 2f
2
2
i



X
x1 + x2
x1 + x2
+ 2αVn−1
µi
+ 1 Λ + 2αVn−1
−1
2
2
i6=k




1
1
1
+ 2αµk Vn−1 (x2 ) + Vn−1 (x1 − 1)
+ 2λ 1 −
2
2
2




X
x1 + x2
x1 + x2
∗2
≥ 2f
+ 2αVn−1
(1 − Λ −
µi )
2
2
i



X
x1 + x2
x1 + x2
+ 2αVn−1
+ 1 Λ + 2αVn−1
−1
µi
2
2
i6=k





1
x1 + x2
1
+ 2αµk Vn−1
+ 2λ 1 −
2
2
2


1
x1 + x2
+ Vn−1
−1
2
2





X
x1 + x2
x1 + x2
+ 2αVn−1
(1 − Λ −
µi )
≥ 2f
2
2
i



X
x1 + x2
x1 + x2
+ 2αVn−1
+ 1 Λ + 2αVn−1
−1
µi
2
2
i6=k


x1 + x2
+ 2λ(1 − u3 ) + 2(1 − u3 )αµk Vn−1
2


x1 + x2
+ 2u3 αµk Vn−1
−1
2
∗3



12


= 2Vn


x1 + x2
.
2

(22)

2
Here u3 is the optimal control when the state has x1 +x
files. Inequali2
ties ∗1, ∗2 follow from the convexity of f (·) and Vn−1 (·) (we use the fact that
convexity imples increasing differences, i.e., f (x+a)−f (x) ≥ f (y +a)−f (y)
for x > y, a > 0). Inequality ∗3 follows from the definition of the optimal
control u3 .

Now, consider the case where x1 > x2 = 0. We have:
Vn (0) = f (0) + (1 − u)λ + (1 − Λ)Vn−1 (0) + ΛVn−1 (1)

(23)

From this equation, we see that u = 1 if λ > 0 and u = 0 otherwise. We
rearrange equation (23) as:
X
Vn (0) = f (0) + (1 − u)λ + (1 − Λ −
µi )Vn−1 (0)
i

+

X

µi Vn−1 (0) + µk Vn−1 (0) + ΛVn−1 (1).

(24)

i6=k

We have:
Vn (x1 ) + Vn (0) = f (x1 ) + f (0)
X
X
+ αVn−1 (x1 )(1 − Λ −
µi ) + αVn−1 (0)(1 − Λ −
µi )
i

i

+ αVn−1 (x1 + 1)Λ + αVn−1 (1)Λ
X
X
+ αVn−1 (x1 − 1)
µi + αVn−1 (0)
µi
i6=k

i6=k

+ (1 − u1 )λ + (1 − u1 )αµk Vn−1 (x1 ) + u1 αµk Vn−1 (x1 − 1)
+ (1 − u2 )λ + αµk Vn−1 (0)
 
x1
,
≥∗1 2Vn
2

(25)

where ∗1 is derived using convexity and by following similar arguments as in
the case when x2 > 0
This proves convexity of the finite horizon problem. Convexity is preserved under pointwise convergence, so it follows for the infinite horizon
discounted problem by letting the time horizon go to infinity, and then for
the average cost problem by the ‘vanishing discount’ argument as in [1].
13

Convexity implies increasing differences. Therefore V (·) has increasing differences. The function restricted to the non-negative integers will retain this
property, thereby proving the lemma.
Lemma 3.3. The optimal policy is a threshold policy i.e. ∃ x∗ such that if
x > x∗ , the server serves at full capacity, otherwise the server does not serve
this file type.
Proof. In order to prove this, we show that the function:
X
X
g(x) =
p2 (y|x)V (y) −
p1 (y|x)V (y)
is decreasing. On simplifying this expression, we get:
g(x) = µk (V (x − 1) − V (x))

(26)

which is a decreasing function in x by Lemma 3.2. This implies that the
optimal policy is a threshold policy.
In order to specify the threshold uniquely for each λ, we take it to be the
smallest value of the state x for which it is equally desirable to be active or
passive.

4

Whittle Indexability

We next prove a Whittle-like indexability result in the spirit of [33]. We use
the phrase ‘Whittle-like’ because our problem formulation differs from that
of [33], though it builds upon it. By abuse of terminology, we shall still use
the terms Whittle indexability, Whittle index, etc. for our variants thereof.
Let π k denote the stationary probability distribution when the threshold
is k. That is, if the number of jobs is ≤ k, then the server does not transmit,
and if number of jobs is > k, then the server transmits at full rate. We have
the following lemma.
Pk
k
Lemma 4.1.
i=0 π (i) is non-decreasing with k.
P
Proof. Let µ̂ = j∈Si ;j6=k µj . The Markov chain formed with a threshold of
k is shown in Figure 2. This is a time reversible Markov chain with stationary
probabilities given by:
 i
Λ
k
k
π (i) = π (0)
if i ≤ k,
µ̂
 k 
i−k
Λ
Λ
k
k
π (i) = π (0)
if i > k,
(27)
µ̂
µk + µ̂
14

where π k (0) is the stationary probability of state 0.

Figure 2: Markov Chain
From this, we see that
k
X

(Λ
)k −1
µ̂

π k (i) =

i=0

(Λ
)−1
µ̂
(Λ
)k −1
µ̂
Λ
( µ̂ )−1

(28)

µ̂+µk
k
+ (Λ
µ̂ ) ( µ̂+µk −Λ )

which is a non-decreasing function of k, proving the claim.
Theorem 4.1. This problem is Whittle indexable, i.e., the set of passive
states decreases monotonically from the whole state space to the empty set φ
as λ ↑ ∞.
Proof. The proof is along the lines of Theorem 1 in [10]. It has been reproduced for the sake of completeness.
The optimal average cost of the problem is given by
X
X
β(λ) = inf {
f (k)π(k) + λ
π(k)}
k

k∈B

where π the stationary distribution and B the set of passive states. β(λ)
is the infimum of this over all admissible policies, which by Lemma 3.3 is
the same as the infimum over all threshold policies. Hence it is concave
non-decreasing with slope < 1. By Lemma 3.3, we can write this as:
β(λ) =

∞
X

x(λ)

f (k)π

x(λ)

(k) + λ

k=0

X
k=0

15

π x(λ) (k)

where x(λ) is the optimal threshold under λ. By the envelope theorem
(Theorem 1, [19]), the derivative of this function with respect to λ is given
by
x(λ)
X
π x(λ) (k).
k=0

Since β(λ) is a concave function, its derivative has to be a non-increasing
function of λ, i.e.,
x(λ)

X

π x(λ) (k) is non-increasing with λ.

k=0

P
But, from Lemma 4.1, we know that kj=0 π k (j) is a non-decreasing function
of k, where k is the threshold. Then x(λ) is a non-increasing function of λ.
The set of passive states for λ is given by [0, x(λ)]. Since x(λ) is a nonincreasing function of λ, we have that the set of passive states monotonically
decreases to φ as λ ↑ ∞. This implies Whittle indexability.

4.1

Proposed Policy

We propose the following heuristic policy inspired by [33]:
Our decision epochs are the time instances when there is some change
in the system, i.e., either an arrival or a departure occurs. For each server
j ∈ S, the index computed for each file type connected to this server is known.
The file type which has the smallest index is chosen and the server serves it
at full rate. Each time there is either an arrival into a file type or there is
a job completion, the new indices are sent to the server which then decides
which queue to serve.

4.2

Computation of the Whittle index

The Whittle index λ(x) (when the number of jobs is x) is given by the
following set of equations:
Vλn (y) = f (y) + λn (x) + Ep1 [Vλn (y)] − βλn

if y < x,

(29)

Vλn (y) = f (y) + Ep2 [Vλn (y)] − βλn

if y ≥ x,

(30)

Vλn (0) = 0

(31)

λn+1 (x) = λn + η(Ep2 [Vλn (x)] − Ep1 [Vλn (x)] − λn )
16

(32)

Here η is a small step size (taken to be 0.01). Epi [·] denotes taking expectation with respect to the probability distribution pi , i = 1, 2 (as defined in
equations (18) and (19)). Since η is small, we can view Equation 32 as an
approximate discretization to the ODE
λ̇(t) = F (λ(t)) − λ(t)

(33)

where
F (λ) := Ep2 [Vλ (x)] − Ep1 [Vλ (x)].
This is a scalar ODE and the function F is continuous decreasing with equilibrium given by that value of λ for which
λ = Ep2 [Vλ (x)] − Ep1 [Vλ (x)],

(34)

i.e., the Whittle index at state x. As a well-posed scalar ODE with bounded
trajectories, it converges to its equilibrium. The convergence of iteration
(32) to a neighborhood of this equilibrium then follows from Theorem 1 of
[12] by standard arguments. The linear system (29), (30) and (31) is solved
as a subroutine by a suitable linear system solver.

5

Simulations

In this section, we report simulations to compare the performance of the
proposed Whittle index policy with other natural heuristic policies given as
follows:
• Balanced Fair Allocation: This is a centralized scheme for allocating server capacities. See [4] for more details.
• Uniform Allocation: At each instant in time, each server splits its
rate equally to all the files that it contains.
• Weighted Allocation: The server rates are split according to prescribed weights proportional to the arrival rates into the different file
types.
• Random Allocation: The decision epochs are the same. At each
instant, for each server, a file type is chosen randomly and the server
serves this at full capacity.
• Max-Weight Allocation: Each server serves at full capacity to that
file type which has the most number of jobs at any instant.
17

We first compare the Whittle policy with the Optimal scheme and the
balanced fairness allocation scheme for the network shown in Figure 3. The
results of the simulations are shown in Figure 4. The values of parameters are
as follows: Λ1 = 0.2; f 1 (x) = 13x; Λ2 = 0.1; f 2 (x) = 10x; µ1 = 0.2; µ2 = 0.2.
The optimal value for the network in figure 3 is computed using the following
set of iterative equations:
Vn+1 (x1 + x2 ) = f 1 (x1 ) + f 2 (x2 ) − Vn (0, 0)

+ min
Ei [Vn (·)|x1 , x2 ]
i∈{1,2,3,4}

un+1 = argmin Ei [Vn (·)|x1 , x2 ]
i

Here, the control u denotes the following: u = 1 denotes server 1, 2 serve file
1. u = 2 denotes server 1 serves file 1 and server 2 serves file 2. u = 3 denotes
server 1 serves file 2 and server 2 serves file 1. u = 4 denotes server 1, 2 serve
file 2. Ei [·] denotes expectation with respect to the probability distribution
under control i. Figure 4 shows that the proposed Whittle index policy
outperforms the balanced fairness allocation policy.

Figure 3: The Network that we use for simulations

The second network that we consider is shown in Figure 5. The parameters in this simulation are as follows: Λ1 = 0.1; f 1 (x) = 10x; Λ2 =
0.2; f 2 (x) = 20x; Λ3 = 0.1; f 3 (x) = 10x; µ1 = 0.2; µ2 = 0.3.
Figure 6 shows the Whittle indices assigned by file types 1 and 2 to server
1 and Figure 7 shows the Whittle indices assigned by file type 1 to the two
servers.

18

Figure 4: Comparison of Whittle policy, True Optimal, and Balanced Fairness scheme

Figure 5: The Network that we use for simulations

19

Figure 6: Whittle index assigned by different files to the same server

Figure 7: Whittle index assigned by the same file to different servers

Figures 8 and 9 compare the performance of the Whittle index policy with
that of the Uniform Allocation, Random Allocation, Weighted Allocation
and Max-Weight Allocation policies that were described at the beginning
of this section 4 . We can see that the Whittle index based policy performs
better than the other methods of server allocation.
4

We have separated these figures to enable better comparison. This is because the
performance of the Uniform and Random allocation policies is much worse than that of
the other policies.

20

Figure 8: Comparison of Whittle policy with Uniform and Random policies

Figure 9: Comparison of Whittle policy with Weighted and Max Weight
policies

Figure 10 shows simulation results for the model with 10 file types and 10
servers such that file type i is stored in servers i, i + 1(mod10). The parameters used are as follows: Λi = 0.2, f i (x) = 15x, µi = 0.2 for i = 1, 4, 7, 10.
21

Λi = 0.3, f i (x) = 20x, µi = 0.3 for i = 2, 5, 8. Λi = 0.1, f i (x) = 10x, µi = 0.2
for i = 3, 6, 9. Figure 10 shows that the proposed Whittle index policy outperforms the Weighted Allocation and Max-Weight Allocation policies.

Figure 10: Comparison of Whittle policy with Weighted and Max Weight
policies

6

Conclusions and Future Work

We have proved Whittle-like indexability of the problem of server allocation
in resource pooling networks. The allocation of servers using the Whittlelike scheme can be implemented in a distributed manner. The next step
would be to extend this work to more general file types and possibly more
complicated network topologies.

References
[1] Agarwal, M., Borkar, V. S. and Karandikar, A., “Structural properties of
optimal transmission policies over a randomly varying channel." IEEE
Transactions on Automatic Control 53.6, pp. 1476-1491, 2008.

22

[2] Archibald, T. W.; Black, D. P. and Glazebrook, Kevin D., “Indexability
and index heuristics for a simple class of inventory routing problems."
Operations Research 57.2, pp. 314-326, 2009.
[3] Bonald, T. and Comte, C., “Balanced fair resource sharing in computer
clusters." Performance Evaluation 116 pp. 70-83, 2017.
[4] Bonald, T. and Proutiere, A. “Insensitive bandwidth sharing in data
networks." Queueing systems 44.1 pp. 69-100, 2003.
[5] Avrachenkov, K. and Borkar, V. S., “Whittle index policy for crawling
ephemeral content." IEEE Trans. on Control of Network Systems, 2016
(available online).
[6] Avrachenkov, K. ,Borkar, V. S. and Pattathil, S., “Controlling G-AIMD
using Index Policy." 56th IEEE Conference on Decision and Control,
Melbourne, Dec. 12-15, 2017.
[7] Borkar V. S., “Convex Analytic Methods in Markov Decision Processes’.
In Feinberg E. A., Shwartz A. (eds), Handbook of Markov Decision
Processes, Springer, Boston, MA, 2002
[8] Borkar, V. S., Kasbekar, G. S., Pattathil, S. and Shetty, P. Y., “Opportunistic scheduling in restless bandits." IEEE Trans. on Control of
Network Systems, 2017 (available online).
[9] Borkar, V. S. , Ravikumar, K. and Saboo, K. , “An index policy for
dynamic pricing in cloud computing under price commitments." Applicationes Mathematicae, 2017 (available online)
[10] Borkar, V. S. and Pattathil, S. , “Whittle indexability in egalitarian processor sharing systems." Annals of Operations Research, 2017 (available
online).
[11] Guo, X. and Hérnandez-Lerma, O. , Continuous-time Markov Decision
Processes: Theory and Applications, Springer Verlag, Berlin-Heidelberg,
2009.
[12] Hirsch, Morris W. “Convergent activation dynamics in continuous time
networks." Neural networks 2.5, 331-349, 1989
[13] Jacko, P. Dynamic priority allocation in restless bandit models, Lambert
Academic Publishing, 2010.

23

[14] Kurose, J.F. and Ross, K.W. Computer Networking: A Top-Down Approach, Addison Wesley, Sixth Edition, 2012.
[15] Larranaga, M. , Ayesta, U. and Verloop, I. M., “Dynamic control
of birth-and-death restless bandits: application to resource-allocation
problems." IEEE/ACM Trans. Networking, 24.6, pp. 3812-3825, 2016.
[16] Leconte, M., Lelarge, M. and Massoulie, L. , “Bipartite graph structures
for efficient balancing of heterogeneous loads", Proc. ACM Sigmetrics/
Performance, pp. 41-52, 2012.
[17] Leconte, M., Lelarge, M. and Massoulie, L., “Designing adaptive replication schemes in distributed content delivery networks", Proc. 27th
IEEE International Teletraffic Congress (ITC), pp. 28-36, 2015.
[18] Leighton, T. “Improving Performance on the Internet”, Communications
of the ACM, Vol. 52, No. 2, Feb. 2009, pp. 44-51.
[19] Milgrom, P. and Segal, I., “Envelope theorems for arbitrary choice sets."
Econometrica 70.2, pp. 583-601, 2002.
[20] Moharir, S., Ghaderi, J., Sanghavi, S. and Shakkottai, S., “Serving content with unknown demand: the high-dimensional regime", Proc. of
ACM Sigmetrics, pp. 435-447, 2014.
[21] Ninõ-Mora, J. , “Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies." Computers & Operations Research 39.12, pp. 3431-3444, 2012.
[22] Nino-Mora, J. and Villar, S. S., “Sensor scheduling for hunting elusive
hiding targets via Whittle’s restless bandit index policy." 5th International Conference on Network Games, Control and Optimization (NetGCooP), Paris, Oct. 12-14, 2011.
[23] Ny, J.L., Dahleh, M. and Feron, E. , “Multi-UAV dynamic routing
with partial observations using restless bandit allocation indices." Proc.
American Control Conference, Seattle, June 11-13, 2008, pp. 4220-4225,
2008.
[24] Papadimitriou, C. H. and Tsitsiklis, J. N. , “The complexity of optimal queuing network control", Mathematics of Operations Research
24.2 (1999), 293-305.
[25] Ruiz-Hernandez, D. , Indexable Restless Bandits, VDM Verlag, 2008.
24

[26] Shah, V. , Centralized content delivery infrastructure exploiting resource pools: Performance models and asymptotics. Ph.D.
Dissertation, Department of Electrical and Computer Engineering, University of Texas at Austin, 2015, available at
https://repositories.lib.utexas.edu/handle/2152/31419.
[27] Shah, V. and de Veciana, G. ,“Performance evaluation and asymptotics
for content delivery networks." Proc. IEEE INFOCOM, Atlanta, May
1-4, 2014, pp. 2607-2615, 2014.
[28] Shah, V. and de Veciana, G. , “High-performance centralized content
delivery infrastructure: models and asymptotics", IEEE/ ACM Transactions on Networking, 23.5, pp. 1674-1687, Oct. 2015.
[29] Shah, V. and de Veciana, D., “Impact of fairness and heterogeneity
on delays in large-scale centralized content delivery systems", Queuing
Systems, 83.3-4, pp. 361-397, 2016.
[30] Tsitsiklis, J. and Xu, K. , “Flexible queuing architectures", Operations
Research, 65.5, pp. 1398-1413, 2017.
[31] Weber, Richard R., and Weiss,G., “On an index policy for restless bandits." Journal of Applied Probability 27.3, pp. 637-648, 1990.
[32] D. West, Introduction to Graph Theory, Prentice Hall, Second Edition,
2000.
[33] Whittle, P. , “Restless bandits: activity allocation in a changing world",
Journal of Applied Probability Vol. 25: A Celebration of Applied Probability, pp. 287-298, 1988.
[34] Zhou, Y., Fu, T. and Chiu, D. “A unifying model and analysis of P2P
VoD replication and scheduling", IEEE/ ACM Transactions on Networking, 23.4, pp. 1163-1175, 2015.

25

