TRAFFIC PROCESSES

Traffic process (N(t), t ≥ 0): N(t) is the (cumulative) number of arrivals in [0, t]. Assume that N(0) = 0 and that no two calls can arrive at exactly the same time.

If N were a Poisson process (with rate γ), then

E_{s} (N(t) − N(s)) = γ(t − s), 0 ≤ s ≤ t.

or, more generally,

E_{s} (N(t) − N(s)) = ∫_{s}^{t} γ(u) du, 0 ≤ s ≤ t.

Here E_{s} represents expectation conditional on the past at time s (formally, E_{s}(·) = E( · |F_{s}), where {F_{s}} is an increasing, rightcontinuous family of σ-algebras, with N(s) being F_{s} measurable and F_{0} being complete).

We say that N has a deterministic pastconditional arrival rate.

WATANABE’S THEOREM

Now let N be an arbitrary traffic process.

Theorem If N has a deterministic pastconditional arrival rate, then N is a Poisson process.

Outline Proof For simplicity, suppose that

E_{s} (N(t) − N(s)) = t − s, 0 ≤ s ≤ t. (1)

Now extend (1) to stopping times τ and σ with τ ≥ σ as follows:

E (N(τ) − N(σ)) = E(τ − σ) (2)

(recall that τ is a stopping time if {τ ≤ s} ∈ F_{s}). Let 0 < T_{1} < T_{2} < … be the sequence of arrival times, and, for fixed i, define

σ = min (t, T_{i−1}) and τ = min (t, T_{i}).

Consider the three possible cases

T_{i−1} ≤ T_{i} ≤ t, T_{i−1} ≤ t < T_{i}, t < T_{i−1} ≤ T_{i}, and observe that

N(τ) − N(σ) = I(T_{i} ≤ t).

Thus,

P (T_{i} ≤ t) = E (N(τ) − N(σ))
= E(τ − σ)
= E (∫_{0}^{t} I(N(s) = i − 1) ds)
= ∫_{0}^{t} P (N(s) = i − 1) ds.

Setting p_{i}(t) = P (N(t) = i) we find that

p_{i}(t) = P (T_{i} ≤ t < T_{i+1} )

= P (T_{i} ≤ t) − P (T_{i+1} ≤ t) = ∫_{0}^{t} p_{i−1}(s) ds − ∫_{0}^{t} p_{i}(s) ds,

and hence that p′_{i} = p_{i−1} − p_{i}.

For i = 0 we get

p_{0}(t) = 1 − ∫_{0}^{t} p_{0}(s) ds,

which gives p′_{0} = −p_{0}. Since p_{i}(0) = δ_{i0} we deduce that N(t) has a Poisson distribution with parameter t.

We also require N(t) − N(s) (0 ≤ s ≤ t) to be independent of the past at s. Fix s and A ∈ F_{s}, and let M(t) = N(s+t)−N(s). Then, (2) gives

E′_{t}(M(u) − M(t)) = u − t, 0 ≤ t ≤ u,

where E′_{t} refers to expectation conditional on the past at time t, including the fixed event A. But the previous analysis then gives a Poisson(t) distribution for M(t), that is, a Poisson distribution with parameter t for N(s+ t) − N(s), conditional on A. This establishes the required independence.

CONDITIONAL INTENSITY

Let (N(t), t ≥ 0) be an arbitrary traffic process.

Under mild regularity conditions, the limit

γ(s) = lim_{t↓0} \frac{1}{t} (E_{s}(N(t + s) − N(s)))

exists and defines the conditional intensity (process), (γ(s), s ≥ 0), and, if we set

Γ(t) = ∫_{0}^{t} γ(u) du,

then, for all 0 ≤ s ≤ t,

E_{s}(N(t) − N(s)) = E_{s}(Γ(t) − Γ(s)).

For stopping times τ and σ such that τ ≥ σ,

E_{σ}(N(τ) − N(σ)) = E_{σ}(Γ(τ) − Γ(σ)),

where E_{σ} means expectation conditional on the past at time σ: formally, the σ-algebra of events, A, such that A ∩ [σ ≤ t] ∈ F_{t} for each t.

POISSON APPROXIMATIONS

Let N be a traffic process with conditional intensity γ. Fix t ≥ 0 and let A be an event determined by N on [0, t]. It is proposed to approximate P (A) by Π(A), where Π(A) is the probability that A would have if N were Poisson with given rate α.

The idea is to construct a Poisson process M using N. Define Γ̂ (t) = inf {s : Γ(s) ≥ t}, the (pseudo) inverse of the increasing (random) function s ↦ Γ(s). In general Γ(Γ̂ (t)) = t, but Γ̂ (Γ(t)) ≥ t, with inequality occurring at only those t for which Γ is constant around an interval containing t. Certainly Γ̂ (t) ≥ Γ̂ (s) for t ≥ s, and so we may apply the above (stopping time) result, namely

E_{σ}(N(τ) − N(σ)) = E_{σ}(Γ(τ) − Γ(σ)),

with σ = Γ̂ (s) and τ = Γ̂ (t).

This gives

E_{Γ̂ (s)}{N(Γ̂ (t)) − N(Γ̂ (s))}

= E_{Γ̂ (s)}{Γ(Γ̂ (t)) − Γ(Γ̂ (s))} = t − s.

Thus, by the previous argument, {N(Γ̂ (t))} is a unit-rate Poisson process and so M, where M(t) = N(Γ̂ (αt)), is a Poisson process with rate α. A familiar coupling argument then leads to the following result:

Proposition For arbitrary A,

|P (A) − Π(A)| ≤ ∫_{0}^{t} E|α − γ(s)| ds

≤ ∫_{0}^{t} (E(α − γ(s))^{2}) ^{1/2} ds,

where Π(A) is the probability that A would have if the traffic process were Poisson with parameter α. If the traffic process is stationary with α = Eγ(s), then

|P (A) − Π(A)| ≤ t (Var γ(s))^{1/2} .

A STAR NETWORK

8

A STAR NETWORK

There are K outer nodes which communicate via a single central node. Thus, there are K links (circuit groups), and each route consists of a pair of links (i, j).

Assume that

• the links have C circuits,

• calls arrive as independent Poisson processes,

• these have the same rate, ρ = ν/(K − 1),

• call lengths are exponential with mean 1,

• these are mutually independent.

Keep the total offered traffic, ν, (to the network) fixed and let the number of switching nodes, K, become large; what happens?

A POISSON APPROXIMATION FOR THE STAR NETWORK

Let N_{k}(t) be the number of calls offered to link k in the time-interval [0, t] and let m_{j}(s) be the number of circuits in use on link j at time s. Clearly γ_{k}, the conditional intensity of N_{k}, is given by

γ_{k}(s) = _{j≠k}^{∑} ρI[m_{j}(s) < C].

Thus Eγ_{k}(s) = νP (m_{1} < C) and

Var γ_{k}(s) =

ν (ρP (m_{1} < C) + (\frac{K−1}{K−2}) νP (m_{1} < C, m_{2} < C)

−ν(P (m_{1} < C))^{2}) .

Recall that if A is any event determined by N_{k} on [0, t], then

|P (A) − Π(A)| ≤ t (Var γ_{k}(s))^{1/2} .

ASYMPTOTICALLY INDEPENDENT BLOCKING

Proposition (Ziedins and Kelly (1989)): By keeping the total offered traffic, ν, fixed and letting the number of switching nodes, K, become large, the links are blocked independently. Specifically, as K → ∞,

P (m_{1} < C, m_{2} < C) − (P (m_{1} < C))^{2} → 0.

We deduce that the traffic offered to any given link is approximately Poisson, since

Var γ_{k}(s) =

ν (ρP (m_{1} < C) + (\frac{K−1}{K−2}) νP (m_{1} < C, m_{2} < C)

−ν(P (m_{1} < C))^{2})

∼ \frac{ν^{2}}{K−1}P (m_{1} < C) (1 + (\frac{K−1}{K−2}) P (m_{1} < C)) .

A MARKOVIAN QUEUEING NETWORK

Label the links 1, 2, …, J and make the usual simplifying assumptions:

• the links are perfectly reliable and are not subject to noise, so that message transmission times are determined by their length.

• the time taken by the nodes to switch, and, if necessary, buffer, reassemble and acknowledge messages, is negligible in comparison with their transmission times.

• traffic entering the network from external sources is Poisson and message lengths are mutually independent and exponentially distributed with mean 1.

A total effort (or capacity) of ϕ_{j}(n) is provided by link j when there are n messages whose transmission is incomplete.

A POISSON APPROXIMATION

Let N_{k}(t) be the net traffic offered to a given link, k, on the interval [0, t]. Since all messages have unit mean length, the rate at which messages are transmitted by link j is ϕ_{j}(n) when there are n messages present. Thus, if n_{j}(s) is the number of messages present at link j at time s, then γ_{k}, the conditional intensity of N_{k}, is given by

γ_{k}(s) = ν_{k} + J ; ∑ ; j=1 ϕ_{j}(n_{j}(s))λ_{jk},

where ν_{k} is the rate of externally offered traffic and λ_{jk} is the proportion of messages emanating from link j which next use link k.

Let α_{k} = Eγ_{k}(s). Then (in equilibrium)

α_{k} = ν_{k} + J ; ∑ ; j=1 α_{j}λ_{jk}, k = 1, 2, …, J.

An equilibrium exists if and only if, for each j,

b_{j}^{−1} = ∞ ; ∑ ; n=0 \frac{α_{j}^{n}}{∏_{l=1}^{n} ϕ_{j}(l)} < ∞,

in which case, the states of the individual links are independent and the probability that there are n messages at link j is given by

π_{j}(n) = \frac{b_{j}α_{j}^{n}}{∏_{l=1}^{n} ϕ_{j}(l)} .

We can then show that

Var γ_{k}(s)

= J ; ∑ ; j=1 α_{j} ( ∞ ; ∑ ; n=0 ϕ_{j}(n + 1)π_{j}(n) − α_{j}) λ_{jk}^{2}.

This leads to a bound on the degree of deviation of N_{k} from a Poisson process with rate α_{k}.

STATE-INDEPENDENT CAPACITY

Suppose

ϕ_{j}(n) = ϕ_{j}I[n > 0].

Then

|P (A) − Π(A)| ≤ t ( J ; ∑ ; j=1 ϕ_{j}^{2}λ_{jk}^{2}ρ_{j}(1 − ρ_{j})) ^{1/2} ,

where ρ_{j} = α_{j}/ϕ_{j} (we must have that ϕ_{j} > α_{j}). Thus, if for each j, ϕ_{j}λ_{jk} is O(1) and either

(1) ϕ_{j}λ_{jk} is o(J^{−1/2} ),

(2) ρ_{j} is o(J^{−1}), or

(3) 1 − ρ_{j} is o(J^{−1}), then the Poisson approximation is sure to be good.

SIMULTANEOUS APPROXIMATIONS BY INDEPENDENT POISSON PROCESSES

Let N_{1}, N_{2}, …, N_{l} be l traffic processes and let γ_{1}, γ_{2}, …, γ_{l} be their conditional intensities.

If A is an event which is determined by these processes on the interval [0, t] and Π(A) is the probability that A would have if these processes were independent Poisson processes with rates α_{1}, α_{2}, …, α_{l}, then

|P (A) − Π(A)| ≤ l ; ∑ ; k=1 ∫_{0}^{t}(E(α_{k} − γ_{k}(s))^{2})^{1/2} ds.

If the system is in equilibrium and α_{1}, α_{2}, …, α_{l} are chosen such that α_{k} = Eγ_{k}(s), then a simpler bound is given by

|P (A) − Π(A)| ≤ t l ; ∑ ; k=1 (Var γ_{k}(t))^{1/2} .