## Description

(1) Consider a communication network with L links that is operating in a time-slotted manner. Each link l has an associated set of interfering neighbors given by N l

. A constant

probability vector p := (pl)l

is to be assigned to the links so that in each slot link l will

attempt a packet transmission with its assigned probability pl ∈ [0, 1] independently. The

transmission of link l succeeds in a slot only if it transmits and none of its interfering

neighbor does.

(a) Express the average rate of success of link l transmissions, denoted as xl(p), as a

function of p.

(b) Suppose the utility that link l receives from a successful transmission rate of xl

is

given by ωl

log(xl) for a given constant ωl > 0. Then, express the total utility maximization

problem as a convex problem, justifying its convexity.

(c) Solve the problem of part (b) to express the optimal choice of p

∗ as a function of

the weight vector (ωl)l

. Comment on the result.

(2) Consider a network represented by a graph G = (N ,L), where N is the set of nodes,

L is the set of directed links. Let x = (x

d

s

) be the rate of flow from source node s to

destination d, and Usd(·) be the utility function associated with that flow. There are no

apriori set routes for the communication.

Each node i ∈ N has a maximum power constraint P

max

i

that is available for transmission

over its outgoing links. For each link (i, j), there is a noise level given by Nij (which

also accounts for the channel gain between nodes i and j). Then, the rate achieved by

transmitting data at rate Pij over link (i, j) ∈ L is given by

Rij (Pij ) = log(1 + Pij/Nij ).

(Note that the formulation is free from interference).

(a) Formulate the joint congestion control for utility maximization and link rate allocation for optimal routing problem under the power constrained network setting described

above. Clearly describe each new term and indicate what each constraint is due to.

(b) Write the Lagrangian function and develop the gradient-based algorithm for the

problem designed in part (a) (You can leave some components of the algorithm description

as maximizations/minimizations).

(3) In PS2, Problem 6 (referring to Boyd & Vandenberghe 4.62), you have confirmed the

convexity of the optimization problem (with known positive constants (αi)i and (βi)i):

maximize Xn

i=1

αiWi

log

1 +

βiPi

Wi

subject to

P

Pi ≥ 0, Wi ≥ 0, ∀i

n

P

i=1 Pi ≤ Ptot

n

i=1 Wi = Wtot

Now, associate a Lagrange multiplier µ only with the inequality constraint Pn

i=1 Pi ≤ Ptot

and develop the associated gradient method that clearly describes the update rule for

{µ

(t)}t as well as the power and bandwidth allocations in each step.

(4) Consider a single discrete-time queue with a service process S(t) = Bernoulli(µ) for some

µ ≤ 1, i,e, P(S(t) = 1) = 1 − P(S(t) = 0) = µ, and an arrival process A(t) that follows

the following congestion control rule:

P(A(t) = 1| Q(t) = q) = 1 − P(A(t) = 0| Q(t) = q) = 1

(1 + q)

, ∀q ∈ {0, 1, 2, · · · }

where Q(t) is the queue-length at time t that evolves as

Q(t + 1) = (Q(t) + A(t) − S(t))+.

(Note that a packet can arrive and leave the queue in the same time slot).

(a) Draw the Markov Chain diagram of Q(t) showing the transition probabilities.

(b) Using Foster-Lyapunov criterion, find the range of µ for which the Markov Chain

is positive recurrent (with proof).

(c) For any µ in the range found in (b), find the stationary distribution π

∗ = (π

∗

i

)∞

i=0.

Do not leave terms in infinite sums. (Hints: Write global balance equations for sets of

states {0}, {0, 1}, {0, 1, 2}, so on; and recall that X∞

k=0

ρ

k

k!

= e

ρ

).

(5) (Programming Exercise) In this problem, we will consider fair allocation of a shared

resource among users in the context of telecommunication networks. Consider a network

consisting of N users.

User i derives a utility of Ui(xi) by sending data at rate xi

. We assume that Ui

is an

increasing, continuously differentiable function. The service rate to user i is ri ≥ 0. In

order for stability, each user must send data at a rate less than its service rate, i.e., xi ≤ ri

.

Due to interference between links and limited capacity of each link, the service rate vector

r must satisfy the following constraint:

X

N

i=1

ri

ci

≤ 1 (1)

for given constants (ci)i

, which are defined by the network. The objective in this problem

is to maximize utility under these constraints:

max

x

X

N

i=1

Ui(xi)

subject to xi ≤ ri

, i = 1, . . . , N,

X

N

i=1

ri

ci

≤ 1

(2)

Assume that Ui(x) = log(x) for all i.

1. (Dual Algorithm) Associate each constraint (2) with Lagrange multiplier qi ≥ 0 and

write the Lagrangian of the primal problem L(x, r, q). Then, for given q, find the

optimum x and r by solving the following problems:

x

∗ = arg max

x

L(x, r, q) (3)

r

∗ = arg max

r:

P

i

ri

ci

≤1

L(x, r, q) (4)

Note that maximization over x and r are decoupled from each other, and the dual

function is D(q) = L(x

∗

, r∗

, q).We will use gradient descent to minimize D(q):

qi(t) = (qi(t − 1) − γ

d

dqi

D(q(t)))+ (5)

In summary, at stage t of the Dual Algorithm, for given q = q(t − 1), you will first

find x(t) = x

∗ and r(t) = r

∗ as the optimizers of problems (3) and (4), respectively.

Then you will update the dual variable as in (5).

(a) Solve the problems (3), (4), (5), and find the explicit rules for x(t), r(t) and q(t).

(Hint: Exploit the additive structure of Ui and thus decoupling of (xi)i and r. Also,

for finding r

∗

, observe that only one user receives a non-zero service rate at each

time slot. Which one?)

(b) Implement the Dual Algorithm for N = 2 and Ui(x) = log(x), ∀i. Let the initial

queue-lengths be q1(0) = q2(0) = 1 and (c1, c2) = (1, 2). Show the evolution of

(xi(t))i and (qi(t))i

. In a two-dimensional plot, show the trajectory of (x1(t), x2(t)).

(c) How can we interpret the dual variable qi(t)? How does its increase affect xi(t)

and ri(t)? (Hint: Identify an arrival and a service process in the explicit form of

(5).)

2. (Primal-Dual Algorithm) In Primal-Dual Algorithm, instead of finding xi(t) and at

one step as in (3), we will use gradient ascent. So, for given q(t − 1),

xi(t) = (xi(t − 1) + α

d

dxi

L(x, r, q(t − 1)))+ (6)

for all i = 1, 2, . . . , N. The rest of the algorithm is identical to Dual Algorithm.

(a) Find the update rules for (xi(t))i

.

(b) Implement the Primal-Dual Algorithm for N = 2 and Ui(x) = log(x), ∀i. Let the

initial queue-lengths be q1(0) = q2(0) = 1 and (c1, c2) = (1, 2). Show the evolution of

(xi(t))i and (qi(t))i

. In a two-dimensional plot, show the trajectory of (x1(t), x2(t)).

(c) Compare the performances of Dual and Primal-Dual Algorithm. Which one

provides faster convergence? Explain why.

3. (Heavy-Ball Method) For (c1, c2) = (1, 2), N = 2 and Ui(x) = log(x), Heavy-Ball

Method works as follows:

• Choose parameters K > 0 and β ∈ [0, 1). Set t = 0.

• Let q1(0) = q2(0) = 0. Defined the weights for each queue wi(0) = wi(−1) =

0, i = 1, 2.

• For t ≥ 1, do the following at each iteration:

∗ r(t) = arg max

r:

P

i

ri

ci

≤1

P

i wi(t)ri

. (Hint: Only one user receives a non-zero service

rate at each time slot. Which one?)

∗ xi(t) = min{U

′−1

i

(

wi(t)

K

), xmax}.

∗ qi(t + 1) = (qi(t) − ri(t) + xi(t))+.

∗ Let ∆qi(t) = qi(t + 1) − qi(t). Then, update the weights as follows:

wi(t + 1) =

wi(t) + ∆qi(t) + β(wi(t) − wi(t − 1))+

(7)

where x

max is a sufficiently large constant.

(a) Fix β = 0.5 and K = 100, and implement the Heavy-Ball Method described

above. Show the evolution of (xi(t))i and (qi(t))i

. In a two-dimensional plot, show

the trajectory of (x1(t), x2(t)).

(b) For fixed β = 0.5, increase K and observe how the total utility changes after a

sufficiently long time for increasing K.

(c) Compare the performance of Heavy-Ball Method with the algorithms implemented previously. Which one converges fastest? Explain why.