OPTIMAL ALLOCATION OF EFFORT IN GENERAL QUEUEING NETWORKS

by

Phil Pollett

Department of Mathematics The University of Queensland

PACKET SWITCHING NETWORKS

A packet switching network with 4 nodes (labelled A,B,C and D) and 5 links (labelled 1, 2 …, 5)

PACKET SWITCHING NETWORKS N switching nodes (labelled n = 1, 2, …, N) J links (labelled j = 1, 2, …, J) Poisson traffic on route m → n at rate ν_{mn}

(type-mn traffic) Common expected message length: 1/μ (bits)

(Message lengths have an arbitrary distribution which does not depend on type)

Transmission rate on link j is ϕ_{j} (bits/sec.) (There is a first-come first-served (FCFS) discipline at each link)

ROUTING MECHANISMS

Fixed routing Define R(m, n) to be the collection of (distinct) links used by type-mn traffic:

R(m, n) = {r_{mn}(1), …, r_{mn}(s_{mn})} ,

where s_{mn} is the number of links on route m → n and r_{mn}(s) is the link used at stage s.

Random alternative routing This can be accommodated within the framework of fixed routing by allowing a finer classification of type (mni):

ν_{mni} = ν_{mn}q_{mni} ,

where q_{mni} is the probability that alternative route i is chosen; there is fixed set of alternative routes for each OD pair (m, n).

PACKET SWITCHING NETWORK AND CORRESPONDING QUEUEING NETWORK

A NETWORK OF QUEUES

Links ↔ queues Messages ↔ customers T - set of customer types ν_{t} - arrival rate of type-t customers

(Independent Poisson streams) Route for type-t customers:

R(t) = {r_{t}(1), …, r_{t}(s_{t})} .

A NETWORK OF QUEUES

If message lengths have an exponential distribution the links behave independently (indeed, as if they were isolated), each with independent streams of Poisson offered traffic (independent among types). For example, if

α_{j}(t, s) = \begin{cases}ν_{t}, & if r_{t}(s) = j, \\ 0, & otherwise , \end{cases}

so that the arrival rate at link j is given by

α_{j} = _{t∈T}^{∑} s_{t} ; ∑ ; s=1 α_{j}(t, s)

and the demand by a_{j} = α_{j}/μ (bits/sec), then, if the system is stable (a_{j} < ϕ_{j} for each j), the expected number of messages at link j is

E(n_{j}) = \frac{a_{j}}{ϕ_{j} − a_{j}}

and the expected delay is

E(W_{j}) = \frac{1}{α_{j}} (\frac{a_{j}}{ϕ_{j} − a_{j}} ) = \frac{1}{μϕ_{j} − α_{j}} .

THE INDEPENDENCE ASSUMPTION

Kleinrock (1964) proposed the following assumption: that successive messages requesting transmission along any given link have lengths which are independent and identically distributed, and that message lengths at different links are independent.

Thus, we shall assume that at link j message lengths have a distribution function F_{j}(x) which has mean μ_{j}^{−1} and variance σ_{j}^{2}.

Even under this assumption, the model (now a network of ·/G/1 queues with a FCFS discipline) is not analytically tractable. To make progress, we shall use the Residual-life Approximation (Pollett (1984)).

THE RESIDUAL LIFE APPROXIMATION

Let Q_{j}(x) be the distribution function of the queueing time at link j: the time a message spends in the buffer before transmission. The Residual-Life Approximation (RLA) provides an accurate approximation for Q_{j}(x):

Q_{j}(x) ≃ ∞ ; ∑ ; n=0 Pr(n_{j} = n)G_{j}^{(n)} (x) ,  (2)

where

G_{j}(x) = μ_{j} ∫_{0}^{ϕ_{j}x}(1 − F_{j}(y)) dy

and G_{j}^{(n)} (x) denotes the n-fold convolution of G_{j}(x). The distribution of n_{j}, the number of messages at link j, used in (2) is that of the corresponding quasireversible network of symmetric queues obtained by imposing a symmetry condition at each link j. In the present context, this amounts to replacing FCFS by a last-come first-served (LCFS) discipline.

One immediate consequence of (2) is that the expected queueing time Q̄_{j} is approximately

\frac{1 + μ_{j}^{2}ϕ_{j}^{2}}{2μ_{j}ϕ_{j}} E(n_{j}) ,

where E(n_{j}) is the expected number of messages at link j in the quasireversible network. Hence, the expected delay at link j is approximated as follows:

E(W_{j}) ≃ \frac{1}{μ_{j}ϕ_{j}} + \frac{1 + μ_{j}^{2}ϕ_{j}^{2}}{2μ_{j}ϕ_{j}} E(n_{j}) .  (4)

In the RLA, it is only E(n_{j}) which changes when the service discipline is altered. For the present FCFS discipline E(n_{j}) is given by

E(n_{j}) = \frac{α_{j}}{μ_{j}ϕ_{j} − α_{j}}

OPTIMAL ALLOCATION OF EFFORT

We shall minimize the average network delay, or equivalently the average number of messages in the network:

m̄ = J ; ∑ ; j=1 α_{j}E(W_{j})

(using the RLA for E(W_{j})).

$F - overall network budget

f_{j}ϕ_{j} ($-seconds/bit) - cost of operating link j (The cost of operating link j is proportional to the capacity ϕ_{j})

Thus, we should choose the capacities subject to the cost constraint

J ; ∑ ; j=1 f_{j}ϕ_{j} = F .

THE PROBLEM

Let c_{j} = μ_{j}^{2}σ_{j}^{2} be the squared coefficient of variation of F_{j}(x) and let a_{j} = α_{j}/μ_{j}.

Minimize

m̄ = J ; ∑ ; j=1 a_{j} \{\frac{1}{ϕ_{j}} + \frac{a_{j}(1 + c_{j})}{2ϕ_{j}(ϕ_{j} − a_{j})} \}

over ϕ_{1}, …, ϕ_{J} subject to

J ; ∑ ; j=1 f_{j}ϕ_{j} = F .

Introduce a lagrange multiplier λ^{−2}; our problem then becomes one of minimizing

L(ϕ_{1}, …, ϕ_{J}; λ^{−2}) = m̄ + \frac{1}{λ^{2}} ( J ; ∑ ; j=1 f_{j}ϕ_{j} − F ) .

Setting ∂L/∂ϕ_{j} = 0 yields a quartic polynomial equation in ϕ_{j}:

2f_{j}ϕ_{j}^{4} − 4a_{j}f_{j}ϕ_{j}^{3} + 2a_{j}(a_{j}f_{j} − λ^{2})ϕ_{j}^{2} − 2ϵ_{j}a_{j}^{2}λ^{2}ϕ_{j} + ϵ_{j}a_{j}^{3}λ^{2} = 0, (6)

where ϵ_{j} = c_{j} − 1.

Find solutions such that ϕ_{j} > a_{j} (recall that this latter condition is a requirement for stability).

Using the transformation

ϕ_{j}f_{j}/F → ϕ_{j}, a_{j}f_{j}/F → a_{j}, λ^{2}/F → λ^{2}, (8)

the problem reduces to one with unit costs f_{j} = F = 1; equation (6) becomes

2ϕ_{j}^{4} − 4a_{j}ϕ_{j}^{3} + 2a_{j}(a_{j} − λ^{2})ϕ_{j}^{2} − 2ϵ_{j}a_{j}^{2}λ^{2}ϕ_{j} + ϵ_{j}a_{j}^{3}λ^{2} = 0, (10)

and the constraint becomes

J ; ∑ ; j=1 ϕ_{j} = 1 .  (12)

EXPONENTIAL SERVICE TIMES

If transmission times are exponentially distributed (ϵ_{j} = 0 for each j) it is easy to verify that (10) has a unique solution on (a_{j}, ∞) given by

ϕ_{j} = a_{j} + |λ|√a_{j} .

Upon application of the constraint (12) we arrive at the optimal capacity assignment

ϕ_{j} = a_{j} + (1 − J ; ∑ ; k=1 a_{k}) \begin{matrix}√ & a_{j} \\ ∑ & {J \atop k=1} & √ & a_{k} \end{matrix} ,

for unit costs. In the case of general costs this becomes

ϕ_{j} = a_{j} + \frac{1}{f_{j}} (F − J ; ∑ ; k=1 f_{k}a_{k}) \begin{matrix}√ & f_{j}a_{j} \\ ∑ & {J \atop k=1} & √ & f_{k}a_{k} \end{matrix} ,

after applying the transformation (8). This is a result obtained by Kleinrock (1964).

THE GENERAL CASE

We shall adopt a perturbation approach, assuming that the lagrange multiplier and the optimal allocation take the following forms:

\begin{aligned}λ & = λ_{0} + J ; ∑ ; k=1 λ_{1k}ϵ_{k} + O(ϵ^{2}) , \\ ϕ_{j} & = ϕ_{0j} + J ; ∑ ; k=1 ϕ_{1jk}ϵ_{k} + O(ϵ^{2}) , \\ & j = 1, …, J, \end{aligned} (14)

where by O(ϵ^{2}) we mean terms of order ϵ_{i}ϵ_{k}. The zero^{th} order terms come from Kleinrock’s solution:

ϕ_{0j} = a_{j} + λ_{0}√a_{j}, j = 1, …, J,

where

λ_{0} = \frac{1 − ∑_{k=1}^{J} a_{k}}{∑_{k=1}^{J} √a_{k}} .

FIRST-ORDER SOLUTION

On substituting (14) into (10) we obtain an expression for ϕ_{1jk} in terms of λ_{1k}, which in turn is calculated using the constraint (12) and by setting ϵ_{k} = δ_{kj} (the Kronecker delta).

To first order, the optimal allocation is

ϕ_{j} = a_{j} + λ_{0}√a_{j} − \begin{matrix}√ & a_{j} \\ ∑ & {J \atop k=1} & √ & a_{k} \end{matrix} _{k≠j}^{∑} b_{k}ϵ_{k}

+ (1 − \begin{matrix}√ & a_{j} \\ ∑ & {J \atop k=1} & √ & a_{k} \end{matrix}) b_{j}ϵ_{j} ,

where

b_{k} = \frac{1}{4}λ_{0}a_{k}^{3/2} \frac{a_{k} + 2λ_{0}√a_{k}}{(a_{k} + λ_{0}√a_{k})^{2}} .

SENSITIVITY

Let ϕ_{j}, j = 1, 2, …, J, be the new optimal allocation obtained after incrementing ϵ_{j} by a small quantity δ > 0. We find that, to first order in δ,

ϕ′_{j} − ϕ_{j} = (1 − \begin{matrix}√ & a_{j} \\ ∑ & {J \atop k=1} & √ & a_{k} \end{matrix}) b_{j}δ > 0

and, for i ≠ j,

ϕ′_{i} − ϕ_{i} = −\begin{matrix}√ & a_{i} \\ ∑ & {J \atop k=1} & √ & a_{k} \end{matrix}(ϕ′_{j} − ϕ_{j}) < 0 .