MODELLING RANDOM FLUCTUATIONS IN A BISTABLE TELECOMMUNICATIONS

NETWORK

by

Phil Pollett

Department of Mathematics The University of Queensland

REFERENCES

1. Pollett, P.K., “Modelling random fluctuations in a bistable telecommunications network”, Ed. W. Henderson, Proc. 7th Austral. Teletraffic Res. Seminar, (1992), 335–345.

2. Pollett, P.K., “Diffusion approximations for a circuit switching network with random alternative routing”, Austral. Telecomm. Res. 25, (1992), 45–52.

3. Pollett, P.K., “On a model for interference between searching insect parasites” J. Austral. Math. Soc., Ser. B 31, (1990), 133–150.

4. Pollett, P.K. and Vassallo, A., “Diffusion approximations for some simple chemical reaction schemes Adv. Appl. Probab. 24, (1992), 875–893.

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) r retries (initially take r = 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}},

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 OF THE NETWORK

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. The process (X^{(K)}(t), t ≥ 0) is itself a Markov chain, but one which takes values in a lattice contained in the simplex

E = {x ∈ [0, 1]^{C+1} : C ; ∑ ; i=0 x_{i} = 1} .

2-D “SUMMARY”: (X_{C}, X̄)

X_{C} is proportion of links full; this estimates link blocking probability.

And, X̄ = ∑_{i=0}^{C} iX_{i}; this estimates the mean number of circuits in use on any given link.

THE BEHAVIOUR AS THE NETWORK BECOMES LARGE

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)).

A CENTER MANIFOLD?

Ξ = \{x : x_{i} = \frac{ξ^{i}}{i!} ( C ; ∑ ; j=0 \frac{ξ^{j}}{j!} )^{−1} ; ξ ∈ (0, ∞)\}

LAW OF LARGE NUMBERS

Theorem. If, as K → ∞, X^{(K)}(0) ⇒ x_{0}, then, for all ϵ > 0 and t ≥ 0,

lim_{K→∞} Pr (sup_{s≤t} |X^{(K)}(s) − X(s, x_{0})| > ϵ) = 0,

where X(·, x_{0}) is the unique solution to the above system of differential equations with X(0, x_{0}) = x_{0}.

So, for example, {X^{(K)}(s)} converges in probability to X(s, x_{0}) and, since for each s, X^{(K)}(s) is uniformly bounded, dominated convergence implies that

lim_{K→∞} EX^{(K)}(s) = X(s, x_{0})

on all finite time intervals.

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 of [1]) shows that the random fluctuations about any given equilibrium point, x_{0}, are approximately 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}) .

MEASURING STABILITY

If C = 1 (one circuit on each link), set F (x) = 1 − (ν + 1)x − 2ν(1 − x)x^{2}, x ∈ (0, 1), G(x) = 1 + (ν − 1)x + 4ν(1 − x)x^{2} x ∈ (0, 1). Then, F has a unique zero, x_{0}, on (0, 1), for all ν > 0 (stable equilibrium point of dx/dt = F (x)). Further, X^{(K)}(s) has an approximate normal distribution with

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

where B = F′(x_{0}) = 6νx_{0}^{2} −4νx_{0} −(ν +1)(< 0), and

VarX^{(K)}(s) ≃ K^{−1} \frac{G(x_{0})}{2B} (e^{2Bs} − 1).

The magnitude of B, and hence the stability of x_{0}, increases as ν becomes large, but the stationary variance, G(x_{0})/(−2B), increases from 0 to a maximum around ν = 0.5 and then decreases to 0.

When C > 1, change coordinates:

W^{(K)}(s) = AZ^{(K)}(s),

where the rows of A are the left-eigenvectors of B = ∇F (x_{0}). Since the column sums of B are all equal to 0, B has a zero eigenvalue, and so one of the components of W^{(K)}, say W_{0}^{(K)}, is identically zero, since because ∑_{i=0}^{C} X_{i}^{(K)} = 1, we have that ∑_{i=0}^{C} Z_{i}^{(K)} = 0.

The sequence {W^{(K)}(·)}, where (for convenience) W^{(K)} = (W_{1}^{(K)}, W_{2}^{(K)}, … W_{C}^{(K)} ), converges weakly to an OU process, W (·), whose individual components are, themselves, OU processes. Its local drift matrix is D = diag (η_{1}, η_{2}, … η_{C}), where η_{1}, η_{2}, … η_{C} are the non-zero eigenvalues of B, and its local covariance matrix, S, is obtained from the matrix AGA^{T} by deleting the zeroth row and column.

In particular, W (s) has a properly C-dimensional normal distribution with

EW_{i}(s) = w_{i}e^{η_{i}s},
Var W_{i}(s) = \frac{S_{ii}}{2η_{i}}(e^{2η_{i}s} − 1)

and

Cov (W_{i}(s), W_{j}(s)) = \frac{S_{ij}}{η_{i} + η_{j}} (e^{(η_{i}+η_{j})s} − 1),

for i = 1, 2 …, C, where w = Az.

The change of coordinates allows us to use some powerful results of Andrew Barbour, which establish asymptotic results on the time of first exit of X^{(K)}(·) from a region containing x_{0}.

For example, suppose that x_{0} is a stable and let τ(K, c_{K}) be the time when W^{(K)}(·) first crosses the contour

\{w ∈ R^{C} : C ; ∑ ; i=1 ; ; ; √\frac{2T_{ii}}{w_{i}^{2}} exp (\frac{w_{i}^{2}}{2T_{ii}} ) = c_{K}^{−1} exp (c_{K}^{2})\} ,

where T, the stationary covariance matrix of W (·), has elements T_{ij} = −S_{ij}/(η_{i} + η_{j}) and {c_{K}} is a sequence which tends to ∞; to order c_{K}^{−1}, the contour delimits the rectangle

{w ∈ R^{C} : |w_{i}| ≤ c_{K}√(2T_{ii}), i = 1, 2, …, C} .

Then, if c_{K} = o(K^{\frac{1}{8}}), the random variable

−τ(K, c_{K})\frac{2}{√π}ηc_{K} exp (−c_{K}^{2}),

where η = ∑_{i=1}^{C} η_{i}, converges weakly to a unitmean exponential random variable as K → ∞. Thus, provided c_{K} = o(K^{\frac{1}{8}}), the time at which W^{(K)}(·) first crosses the contour is of order c_{K}^{−1} exp (c_{K}^{2}).

The corresponding result for the C = 1 case is more straightforward. One can show that the time that X^{(K)}(·) first leaves the interval

\{x : |x − x_{0}| ≤ K^{−\frac{1}{2}}c_{K}\}

is of order

\frac{1}{−2Bc_{K}} √\frac{πG(x_{0})}{−B} e^{−Bc_{K}^{2}/G(x_{0})},

whenever c_{K} = o(K^{\frac{1}{8}}). Hence, it is asymptotically larger than any power of K if, for example, c_{K} = O(K^{\frac{1}{8}}/ log K).