MODELLING BISTABILITY IN TELECOMMUNICATIONS NETWORKS

by

Phil Pollett

Department of Mathematics The University of Queensland A SYMMETRIC FULLY-CONNECTED

NETWORK N - nodes K = \binom{N}{2} = \frac{1}{2}N(N − 1) - links C - circuits on each link Poisson traffic offered at rate ν

Exponentially distributed holding times (mean 1)

THE GHK MODEL

Let n_{j}^{(K)} (t) be the number of links with j circuits in use at time t (for a network with K links).

Let n^{(K)} = (n_{0}^{(K)}, n_{1}^{(K)}, …, n_{C}^{(K)} ). Then, (n^{(K)}(t), t ≥ 0) is a continuous-time Markov chain which takes values in

S^{(K)} = {n ∈ {0, 1, … }^{C+1} : C ; ∑ ; i=0 n_{i} = K} .

The transition rates, Q^{(K)} = (q^{(K)}(n, n′), n, n′ ∈ S^{(K)}), of the process are given by q^{(K)}(n, n + e_{j+1} − e_{j}) = νn_{j}, 0 ≤ j ≤ C − 1,

q^{(K)}(n, n + e_{j−1} − e_{j}) = jn_{j}, 1 ≤ j ≤ C,

q^{(K)}(n, n + e_{i+1} − e_{i} + e_{j+1} − e_{j}) = νn_{C} \frac{n_{i}n_{j}}{\binom{K}{2}},

i > j, 0 ≤ i, j ≤ C − 1,

q^{(K)}(n, n + 2(e_{j+1} − e_{j})) = νn_{C} \begin{matrix}( & {nj \atop 2} & ) \\ ( & {K \atop 2} & ) \end{matrix},

0 ≤ j ≤ C − 1,

where e_{i} is the unit vector with 1 as its i^{th} entry.

THE BEHAVIOUR AS THE NETWORK BECOMES LARGE (Theorem 4.1)

Let X^{(K)} = (X_{0}^{(K)}, X_{1}^{(K)}, …, X_{C}^{(K)} ), where X_{j}^{(K)} (t) = n_{j}^{(K)} (t)/K is the proportion of links with j circuits in use at time t.

If, as K → ∞, X^{(K)}(0) ⇒ x_{0}, then X^{(K)}(·) ⇒ X(·, x_{0}), where (X(t, x_{0}), t ≥ 0) is a deterministic process with initial point X(0, x_{0}) = x_{0} and which satisfies

\frac{d}{dt}X_{0}(t) = X_{1}(t) − (ν + λ(t))X_{0}(t),

\frac{d}{dt}X_{j}(t) = (ν +λ(t))X_{j−1}(t)−(ν +λ(t)+j)X_{j}(t)

+(j + 1)X_{j+1} (t), 1 ≤ j ≤ C − 1,
\frac{d}{dt}X_{C}(t) = (ν + λ(t))X_{C−1}(t) − CX_{C}(t),

where λ(t) = 2νX_{C}(t)(1 − X_{C}(t)).

THE EQUILIBRIUM POINTS

If x_{0} = (p_{0}, p_{1}, … p_{C}) is an equilibrium point it must be of the form given by

p_{j} = \frac{ξ^{j}}{j!} ( C ; ∑ ; i=0 \frac{ξ^{i}}{i!})^{−1} , 0 ≤ j ≤ C,

where ξ solves

ξ = ν + 2νE(ξ, C) (1 − E(ξ, C)) .

The quantity E(ξ, C), given by

E(ξ, C) = \frac{ξ^{C}}{C!} ( C ; ∑ ; i=0 \frac{ξ^{i}}{i!})^{−1} ,

is Erlang’s formula for the loss probability of a single link with C circuits and with Poisson traffic offered at rate ξ. It is usually more convenient to calculate the equilibrium points by setting b = E(ξ, C) and solving the equation

b = E (ν + 2νb(1 − b), C) .

MODELLING RANDOM FLUCTUATIONS

The central limit law (Theorem 4.2) shows that the random fluctuations about any given equilibrium point, x_{0}, are Gaussian. Moreover, it shows that these fluctuations can be approximated by an Ornstein-Uhlenbeck (OU) process.

Let x_{0} be an equilibrium point. Then, if

lim_{K→∞} √K (X^{(K)}(0) − x_{0}) = z,

the family of processes {Z^{(K)}(·)}, defined by

Z^{(K)}(s) = √K (X^{(K)}(s) − x_{0}) , 0 ≤ s ≤ t,

converges weakly to an Ornstein-Uhlenbeck process with initial value Z(0) = z and with a local drift matrix, B, and a local covariance matrix, G, which can be determined from the parameters of the model.

In particular, Z(s) is normally distributed with mean

μ_{s} = e^{Bs}z

and covariance matrix

Σ_{s} = ∫_{0}^{s} e^{Bu}Ge^{B^{T} u}du = Σ − e^{Bs}Σe^{B^{T} s},

where Σ, the stationary covariance matrix, satisfies

BΣ + ΣB^{T} + G = 0.

We can conclude that, for K large, X^{(K)}(s) has an approximate normal distribution for each s, and an approximation for the mean and the covariance matrix of X^{(K)}(s) is given by

EX^{(K)}(s) ≃ x_{0} + e^{Bs}(X^{(K)}(0) − x_{0})

and

Cov X^{(K)}(s) ≃ K^{−1} (Σ − e^{Bs}Σe^{B^{T} s}) .