BOTTLENECKS IN MARKOVIAN QUEUEING NETWORKS

by

Phil Pollett

The University of Queensland

OUR SETTING

A closed network of queues:

• Fixed number of nodes (queues) J

• N customers circulating

• Usual Markovian assumptions in force Examples:

• A job shop, where manufactured items are fashioned by various machines in turn.

• Provision of spare parts for a collection of machines.

• A mining operation, where coal faces are worked in turn by a number of specialized machines.

Can we identify regions of congestion (bottlenecks) from the parameters of the model?

BOTTLENECKS

Common sense:

The nodes with the smallest service effort will be the most congested.

A formal definition: If n_{j} is the number of customers at node j, then this node is a bottleneck if, for all m ≥ 0, Pr(n_{j} ≥ m) → 1 as N → ∞.

SIMPLE EXAMPLES

All nodes have infinitely many servers:

Pr(n_{j} = n) = \binom{N}{n}α_{j}^{n}(1 − α_{j})^{N−n}, n = 0, …, N, where α_{j} (< 1) is proportional to the arrival rate at node j divided by service rate. Clearly Pr(n_{j} = n) → 0 for each n as N → ∞, and so all nodes are bottlenecks.

All nodes have a single server:

The distribution of n_{j} cannot be written down explicitly, but we can show that if there is a node j whose traffic intensity is strictly greater than the others, it is the unique bottleneck.

Moreover, for each node k in the remainder of the network, the distribution of n_{k} approaches a geometric distribution with parameter α_{k}/α_{i} in the limit as N → ∞, and n_{k}, for k ≠ j, are asymptotically independent.

MARKOVIAN NETWORKS

Our only assumption:

The steady-state (joint) distribution π of the numbers of customers n = (n_{1}, n_{2}, …, n_{J}) at the various nodes has the product form

π(n) = B_{N} J ; ∏ ; j=1 \frac{α_{j}^{n_{j}}}{∏_{r=1}^{n_{j}} ϕ_{j}(r)} , n ∈ S,

where S is the finite subset of Z_{+}^{J} with ∑_{j} n_{j} = N and B_{N} is a normalizing constant chosen so that π sums to unity over S.

Here α_{j} is proportional to the amount of service requirement (in items per minute) coming into node j (this will actually be equal to α_{j}B_{N}/B_{N−1}). Suppose (wlog) that ∑_{j} α_{j} = 1.

ϕ_{j}(n) is the service effort at node j (in items per minute) when there are n customers present. We shall assume that ϕ_{j}(0) = 0 and ϕ_{j}(n) > 0 whenever n ≥ 1.

GENERATING FUNCTIONS

Our primary tool:

Define generating functions Φ_{1}, Φ_{2}, …, Φ_{J} by

Φ_{j}(z) = 1 + ∞ ; ∑ ; n=1 \frac{α_{j}^{n}}{∏_{r=1}^{n} ϕ_{j}(r)} z^{n}.

It is easily shown that B_{N}^{−1} = < ∏_{j=1}^{J} Φ_{j}>_{N}, where <·>_{n} takes the n^{th} coefficient of a power series. The marginal distribution of n_{j} can be evaluated as

π_{j}^{(N)} (n) = B_{N}<Φ_{j}>_{n} <_{∏k≠j} Φ_{k}>_{N−n} ,

for n = 0, 1, …, N.

SINGLE-SERVER NODES

Suppose that each node j has a single server (ϕ_{j}(n) = 1 for n ≥ 1). Then, <Φ_{j}>_{n} = α_{j}^{n} and so <Φ_{j}>_{n+m} = α_{j}^{m}<Φ_{j}>_{n}. Summing

π_{j}^{(N)} (n) = B_{N}<Φ_{j}>_{n} <_{∏k≠j} Φ_{k}>_{N−n}

over n, and recalling that B_{N}^{−1} = < ∏_{j=1}^{J} Φ_{j}>_{N}, gives P r(n_{j} ≥ m) = α_{j}^{m}B_{N}/B_{N−m}.

Suppose that α_{1} ≤ α_{2} ≤ ⋯ ≤ α_{J−1} < α_{J}, so that node J has maximal traffic intensity.

If we can prove that B_{N−1}/B_{N} → α_{J} as N → ∞, then P r(n_{J} ≥ m) → 1 (node J is a bottleneck) and P r(n_{j} ≥ m) → (α_{j}/α_{J})^{m} < 1 for j < J (the others are not).

WHY DOES B_{N−1}/B_{N} → α_{J}?

Define Θ_{i} = Φ_{1} ⋯ Φ_{i}, where now Φ_{j}(z) = 1/(1 − α_{j}z). Clearly Φ_{j} has radius of convergence (RC) ρ_{j} = 1/α_{j}; in particular, Θ_{1} (= Φ_{1}) has RC 1/α_{1}.

Claim: Θ_{i} has RC 1/α_{i} for all i, so that

\frac{B_{N}}{B_{N−1}} = \frac{<Θ_{J}>_{N−1}}{<Θ_{J}>_{N}} → \frac{1}{α_{J}} , as N → ∞.

Proof : Suppose Θ_{k} has RC 1/α_{k} and consider

<Θ_{k+1} >_{m} = m ; ∑ ; n=0 α_{k+1}^{m−n}<Θ_{k}>_{n}

= α_{k+1}^{m} m ; ∑ ; n=0 ρ_{k+1}^{n} <Θ_{k}>_{n} .

Clearly ∑_{n=0}^{∞} ρ_{k+1}^{n} <Θ_{k}>_{n} = Θ_{k}(ρ_{k+1} ) < ∞, since ρ_{k+1} < ρ_{k}, and so

\frac{<Θ_{k+1} >_{m}}{<Θ_{k+1} >_{m+1}} → \frac{1}{α_{k+1}} as m → ∞,

implying that Θ_{k+1} has RC 1/α_{k+1} .

THE GENERAL CASE

Message: Bottleneck behaviour depends on the relative sizes of the radii of convergence of the power series Φ_{1}, Φ_{2}, …, Φ_{J}.

Proposition 1: Suppose Φ_{j} has radius of convergence ρ_{j} and that ρ_{J} < ρ_{J−1} ≤ ρ_{J−2} ≤ ⋯ ≤ ρ_{1}. Suppose also that

\frac{<Φ_{1} ⋯ Φ_{J−1}>_{n−1}}{<Φ_{1} ⋯ Φ_{J−1}>_{n}}  (1)

has a limit as n → ∞. Then, node J is a bottleneck.

Example: Suppose node j has s_{j} servers, so that the traffic intensity at node j is proportional to α_{j}/s_{j}. Since ϕ_{j}(n) = min {n, s_{j}}, we have ϕ_{j}(n) → s_{j}, and so <Φ_{j}>_{n−1}/<Φ_{j}>_{n} → s_{j}/α_{j}. Therefore ρ_{j} is proportional to the reciprocal of the traffic intensity at node j. It can be shown that (1) holds.

COMPOUND BOTTLENECKS

What happens when the generating functions corresponding to two or more nodes share the same minimal RC?

Proposition 2: In the setup of Proposition 1, suppose that ρ_{L} = ρ_{L+1} = ⋯ = ρ_{J}(= ρ) and that ρ < ρ_{j} for j = 1, 2, …, L − 1. Then, nodes L, L + 1, …, J behave jointly as a bottleneck in that Pr(∑_{i=L}^{J} n_{i} ≥ m) → 1 as N → ∞.

It might be conjectured that when the generating functions corresponding to two nodes share the same minimal RC, they are always bottlenecks individually. However, while this is true when all nodes have a single server (because P r(n_{j} ≥ m) → (ρ/ρ_{j})^{m}), it is not true in general.

SOME EXAMPLES

Consider a network with J = 2 nodes and suppose that α_{1} = α_{2} = 1/2. In the following examples Φ_{1} and Φ_{2} have the same RC ρ = 2.

Only one node is a bottleneck: Suppose that ϕ_{1}(n) = (n + 1)^{2}/n^{2} and ϕ_{2}(n) = 1 for n ≥ 1. Then, it can be shown that Pr(n_{1} = n) → 6/(π^{2}(n + 1)^{2}) and Pr(n_{2} = n) → 0 as N → ∞.

Neither node is a bottleneck: Suppose that ϕ_{1}(n) = ϕ_{2}(n) = (n + 1)^{2}/n^{2} for n ≥ 1. Then, Pr(n_{1} = n) → 3/(π^{2}(n + 1)^{2}) as N → ∞.

AND FINALLY ...

Proposition 3: Suppose that Φ_{1}, Φ_{2}, …, Φ_{K} have the same strictly minimal RC ρ, and that ϕ_{j}(n) converges monotonically for some j ∈ {2, …, K}. Then, node 1 is a bottleneck if and only if

Pr(n_{1} ≥ m | ∑_{i=1}^{K} n_{i} = N) → 1 as N → ∞.

A sufficient condition for node 1 to be a bottleneck is that Φ_{1} diverges at its RC and

\frac{<Φ_{2} ⋯ Φ_{K}>_{n−1}}{<Φ_{2} ⋯ Φ_{K}>_{n}} converges as n → ∞.

This latter condition is not necessary: In the setup of the previous examples, suppose that ϕ_{1}(n) = (n + 1)^{2}/n^{2} and ϕ_{2}(n) = (n + 1)^{3}/n^{3} for n ≥ 1. Then, Φ_{1} and Φ_{2} have common RC ρ = 2 and both converge at their RC. But, it can be shown that Pr(n_{1} = n) is bounded above by a quantity which is O(N^{−1}) as N → ∞, implying that node 1 is a bottleneck.