ESTIMATING BLOCKING PROBABILITIES IN TELECOMMUNICATIONS NETWORKS

WITH LINEAR STRUCTURE

by

Mark Bebbington, Massey University Phil Pollett, The University of Queensland Ilze Ziedins, The University of Auckland

A circuit-switched network

This consists of a group of nodes (locations),

K links (circuit groups),

C_{j} circuits comprising link j, and

R – a collection of routes.

Each route r ∈ R is a set of links. Calls using route r are offered at rate ν_{r} as a Poisson stream, and use a_{jr}(≥ 0) circuits from link j. R indexes independent Poisson processes.

Calls requesting route r are blocked and lost if, on any link j, there are fewer than a_{jr} free circuits. Otherwise, the call is connected and simultaneously holds a_{jr} circuits on each link j for the duration of the call. For simplicity, we shall take a_{jr} ∈ {0, 1}.

Call durations are iid exponential random variables with unit mean, and are independent of the arrival processes.

The usual Markovian model

Let n = (n_{r}, r ∈ R), where n_{r} is the number of calls in progress using route r, let C = (C_{j}, j = 1, …, K), and let A = (a_{jr}, r ∈ R, j = 1, …, K).

The continuous-time Markov chain (n(t), t ≥ 0) takes values in

S = S(C) = {n ∈ Z_{+}^{R} : An ≤ C}

and has a unique stationary distribution given by

π(n) = G^{−1} _{r∈R}^{∏} \frac{ν_{r}^{n_{r}}}{n_{r}!} , n ∈ S,

where G = G(C) is given by

G(C) = _{n∈S(C)}^{∑} _{r∈R}^{∏} \frac{ν_{r}^{n_{r}}}{n_{r}!} .

Blocking probabilities

The stationary probability that a route-r call is blocked is given by

L_{r} = 1 − \frac{G(C − Ae_{r})}{G(C)} ,

where e_{r} is the unit vector from S(C) describing just one call in progress on route r

(recall that G(C) = _{n∈S(C)}^{∑} _{r∈R}^{∏} \frac{ν_{r}^{n_{r}}}{n_{r}!} ) .

An explicit expression for L_{r}!

However, the bad news is that G(C) can’t usually be computed in polynomial time.

For example, consider the trivial case of a fullyconnected network with all possible single-link routes (|R| = K, A = I) and C_{j} = C. Clearly, |S| = C^{K}.

Erlang Fixed Point Approximation (EFP)

Theorem (Kelly (1986)) There is a unique vector (B_{1}, …, B_{K}) ∈ [0, 1]^{K} satisfying

B_{j} = E(ρ_{j}, C_{j}), j = 1, …, K,

ρ_{j} = (1 − B_{j})^{−1} _{r}^{∑} a_{jr}ν_{r}(1 − L_{r}), j = 1, …, K,

and

L_{r} = 1 − _{i}^{∏}(1 − B_{i})^{a_{ir}}, r ∈ R,

where

E(ν, C) = \frac{ν^{C}}{C!} ( C ; ∑ ; n=0 \frac{ν^{n}}{n!})^{−1} .

E(ν, C) is Erlang’s Formula for the loss probability on a single link with C circuits and Poisson traffic offered at rate ν.

The celebrated Erlang Fixed Point Approximation is obtained by using B_{j} to estimate the probability that link j is full, and using L_{r} to estimate the route-r blocking probability.

The rationale

(Independent blocking)

If links along route r were blocked independently (they are clearly not) and if B_{j} were the link-j blocking probability, then L_{r} would be the route-r blocking probability:

L_{r} = 1 − _{i∈r}^{∏}(1 − B_{i}) = 1 − _{i}^{∏}(1 − B_{i})^{a_{ir}}.

Carrying this rationale further, the traffic offered to link j would be Poisson (at rate ρ_{j}, say) and the carried traffic (that which is accepted) on link j would be

_{r}^{∑} a_{jr}ν_{r}(1 − L_{r}) ( = (1 − B_{j})ρ_{j} ) .

The Erlang Fixed Point Approximation stipulates that the blocking probabilities (B_{1}, …, B_{K}) should be consistent with this level of carried traffic:

B_{j} = E(ρ_{j}, C_{j}), j = 1, …, K.

The Erlang Fixed Point

The (unique) fixed point of the system

B_{j} = E((_{r}^{∑} a_{jr}ν_{r} _{i∈r−{j}}^{∏}(1 − B_{i})) , C_{j} )

is called the Erlang Fixed Point.

Remarks The existence of a fixed point is easy to prove using the Brouwer fixed point theorem; these equations determine a continuous mapping from a compact convex set [0, 1]^{K} into itself. The uniqueness (Kelly) is difficult to prove.

For more complex systems, there may be more than one fixed point. This may be associated with multiple stable states for the network. For example, in networks with Random Alternative Routing the system can fluctuate between a low blocking state, where calls are accepted readily, and a high blocking state, where the likelihood of a call being accepted can be quite low.

When does the EFP perform well?

There are two limiting regimes under which the EFP is asymptotically valid:

Moderate loading (Kelly (1986)) Consider a sequence of networks indexed by N (arbitrary), and index the capacities and arrival rates accordingly:

C^{(N)} = (C_{j}^{(N)} , j = 1, …, K),
ν^{(N)} = (ν_{r}^{(N)} , r ∈ R).

Theorem Suppose that as N → ∞

\frac{1}{N} C^{(N)} → C and \frac{1}{N} ν^{(N)} → ν .

(Network topology fixed.) If L_{r}^{(N)} is the router loss probability, then, for each r ∈ R, L_{r}^{(N)} → L_{r}, where

L_{r} = 1 − _{i}^{∏}(1 − B_{i})^{a_{ir}},

and (B_{1}, …, B_{K}) is the Erlang Fixed Point determined by ν and C.

Diverse routing (General formulation - Hunt (1990)) Consider a sequence of networks indexed by K (the number of links), and index the routing matrix and arrival rates accordingly:

A^{(K)} = (a_{jr}^{(K)} , r ∈ R, j = 1, …, K),
ν^{(K)} = (ν_{r}^{(K)} , r ∈ R).

Suppose that

_{r}^{∑} a_{jr}^{(K)} a_{kr}^{(K)} ν_{r}^{(K)} → 0, j, k = 1, …, K,

and

_{r}^{∑} a_{jr}^{(K)} ν_{r}^{(K)} → ν_{j} > 0, j = 1, …, K.

(Capacities fixed.) The traffic along link j is moderate (∼ ν_{j}), but that which is common to any two links becomes small.

There are no general results. Examples include star networks (Ziedins and Kelly (1989)) and networks with alternative routing (Gibbens, Hunt and Kelly (1990)); there are many more.

The symmetric star network

This consists of a collection of K outer nodes, which communicate via a single central node. Take R to be all those routes consisting of a pair of links (there are \binom{K}{2} of them). Fix ν > 0 and take ν_{r} = ν/(K − 1) for all r ∈ R, and fix C_{j} = C for all links j = 1, …, K.

Theorem If L^{(K)} is the common route loss probability, then L^{(K)} → L, given by

L = 1 − (1 − B)^{2},

and B, the Erlang Fixed Point, is the unique solution to

B = E(ν(1 − B), C),

where E(·, ·) is Erlang’s Formula.

When can the EFP be expected to perform

badly?

The EFP can perform badly if the network exhibits any of the following features:

- highly linear structure (lines and rings)

- low capacities

- priority controls (eg, trunk reservation) In these cases, the independent blocking assumption may not be valid. Can we model the link dependencies, and thus obtain improved fixed point methods?

A symmetric ring network with two types of traffic

We shall examine a network consisting of K nodes with K links which form a loop (see Figure 3). R consist of all 1-link routes (type-1 traffic), as well as all 2-link routes (type-2 traffic) comprising pairs of adjacent links (2K routes in all). Type-t traffic is offered at rate ν_{t} on all type-t routes, for t ∈ {1, 2}, and C_{j} = C for each link j.

A two-link subnetwork

Take links 1 and 2 as “reference” links. The subnetwork consisting of just these two links has three routes: R_{12} = {{1}, {2}, {1, 2}}. Let m_{r} denote the number of calls on route r, for r ∈ R_{12} . Then, m_{1} = n_{1} + n_{K1} is the number of calls occupying capacity on link 1 but not on link 2; m_{2} = n_{2} + n_{23} is the number occupying capacity on link 2 but not on link 1; and m_{12} = n_{12} is the number of calls occupying capacity on both links (see Figure 5).

First examine the correlation between links 1 and 2, in particular,

Corr (I_{{m_{1}+m_{12} <C}} , I_{{m_{2}+m_{12} <C}} ) .

The EFP approximation

If L_{t} is the common loss probability for type-t calls, for t ∈ {1, 2}, then the EFP approximation is

L_{1} ≃ B, L_{2} ≃ 1 − (1 − B)^{2},

where the Erlang Fixed Point B is the unique solution to

B = E(ν_{1} + 2ν_{2}(1 − B), C),

where E(·, ·) is Erlang’s Formula.

Approximation I

This follows the work of Pallant (1992). The network is decomposed into independent subnetworks and the stationary distribution for each is evaluated.

The state space for the subnetwork is

S_{12} = {(m_{1}, m_{2}, m_{12} ) : m_{i} + m_{12} ≤ C, i = 1, 2} and the stationary distribution is

π(m) = G^{−1} \frac{(ν_{1} + ν_{2}(1 − B))^{m_{1}+m_{2}} ν_{2}^{m_{12}}}{m_{1}!m_{2}!m_{12} !} .

We estimate B, the probability that a link adjacent to the two-link subnetwork is fully occupied, by

B = _{m: m_{1}+m_{12} =C}^{∑} π(m_{1}, m_{2}, m_{12} )

= C ; ∑ ; m_{12} =0 C−m_{12} ; ∑ ; m_{2}=0 π(C − m_{12} , m_{2}, m_{12} ),

and use these expressions iteratively to determine the “correct” value of π, and hence B.

Approximation II

Our second approximation uses additional knowledge of the state of a given link in estimating the probability that the adjacent link is full. We use state-dependent arrival rates, ρ_{j} = ν_{1} + ν_{2}(1 − b_{j}), j ∈ {1, 2}, where b_{j} is the probability that link K is fully occupied, conditional on m_{1} = j (b_{j} is also the probability that link 3 is fully occupied, conditional on m_{2} = j), so that

π(m) = G^{−1} \frac{ν_{2}^{m_{12}} (∏_{s=0}^{m_{1}−1} ρ_{s}) (∏_{s=0}^{m_{2}−1} ρ_{s})}{m_{1}!m_{2}!m_{12} !} .

Once b_{j} is estimated and π determined, we set

L_{1}(= B) = C ; ∑ ; m_{12} =0 C−m_{12} ; ∑ ; m_{2}=0 π(C − m_{12} , m_{2}, m_{12} ).

Similarly, L_{2} can be expressed in terms of π.

An estimate of b_{j} can be found by assuming (incorrectly) that b_{j} does not depend on m_{12} . For j = 0, …, C − 1, set

b_{j} = \frac{∑_{m=0}^{j} p(j − m, m, C − m)}{∑_{m=0}^{j} ∑_{r=0}^{C−m} p(j − m, m, r)} ,

where

p(n_{1}, n_{K1}, m_{K}) = \frac{ν_{1}^{n_{1}}ν_{2}^{n_{K1}} (∏_{s=0}^{m_{K}−1} ρ_{s})}{n_{1}!n_{K1}!m_{K}!} .

Some remarks on Approximation II

The dependence of a_{j} on m_{12} (= n_{12} ) is due to the cyclic nature of the network, but is expected to be slight for large networks. The approximation is exact for the infinite line network, as Zachary (1985) shows for a network which is equivalent to the one considered here, with ν_{1} = 0 (no single-link traffic). The expression for b_{j} given above is equivalent to that obtained in his paper for the infinite line network, although written in a different form.

State-dependent arrival rates such as we have here are also discussed by various authors (for example, Pallant and Taylor (1994)). Kelly (1985) gives an exact expression in a line network (including some asymmetric cases).