Performance Analysis

Peter Harrison Imperial College, London

Course Details

• Lectures: Friday 3pm - 5pm, followed by tutorial until 6pm, in 144

• 20 lectures, 10 tutorials, 2-3 pieces of assessed coursework

• No coding

• Lecture notes at: http://www.doc.ic.ac.uk/~uh/pgh/

• This is the first year with typed notes

• Books:

– Performance modelling of communication networks and computer architectures Peter G. Harrison, Naresh M. Patel. Wokingham : Addison-Wesley, 1992. ISBN: 0201544199, 14 copies in library, out of print

– Probabilistic Modelling I. Mitrani, Paperback - 233 pages 2nd Ed (11 December, 1997) Cambridge University Press; ISBN: 0521585309, about £20 • The course aims to model real-world problems using analytical models

• Queueing theory

• Uses maths to solve problems

• Emphasis is on solving problems rather than making up hard sums

• Even if you do not choose to specialise in modelling, you will learn some “transferable” skills

• Simulation and Modelling by Tony Field, Wed. 11pm (145), Thu 9pm (343)

• Performance analysis • … Modelling

• … Planning

• … Optimisation • Real-world problem: Post Office (average length of queues, Utilisation, etc.)

• Abstraction, approximation, summary

• Assumptions

• Model

• Techniques for solution

• Answer to problem

• Abstraction helps to transfer solution to other problems (PO, computer)

1 Previews of selected examples and case studies...

1.1 Example 1: A Simple TP server

A TP system accepts and processes a stream of transactions, mediated through a (large) buffer:

• Transactions arrive “randomly” at some specified rate

• The TP server is capable of servicing transactions at a given service rate

Q: If both the arrival rate and service rate are doubled, what happens to the mean response time?

1.2 Example 2: A simple TP server

Consider the same system as above:

• The arrival rate is 15tps

• The mean service time per transaction is 58.37ms Q: What happens to the mean response time if the arrival rate increases by 10%?

1.3 Example 3: A simple multiprocessor TP system

Consider our TP system but this time with multiple transaction processors

• The arrival rate is 16.5 tps

• The mean service time per transaction is 58.37ms Q: By how much is the system response time reduced by adding one processor?

Example 4: File Allocation

What is the best way to allocate disk blocks to a heterogenous disk I/O system?

• Disk I/O requests are made at an average rate of 20 per second

• Disk blocks can be located on either disk and the mean disk access times are 30ms and 46ms respectively

Q: What is the optimal proportion of blocks to allocate to disk 1 to minimise average response time?

1.4 Example 5: A Simple Computer Model

Consider an open uniprocessor CPU system with just disks

• Each submitted job makes 121 visits to the CPU, 70 to disk 1 and 50 to disk 2 on average

• The mean service times are 5ms for the CPU, 30ms for disk 1 and 37ms for disk 2

Q: What is the effect of replacing the CPU with one twice the speed?

Example 6: A Simple Batch Processor System

How does the above system perform in batch mode?

• Each batch job makes 121 visits to the CPU, 70 to disk 1, 50 to disk 2 on average

• The mean service times are 5ms for the CPU, 30ms for disk 1 and 37ms for disk 2

Q: How does the system throughput vary with the number of batch jobs and what is the effect of replacing Disk 1 with one (a) twice and (b) three times the speed?

Example 7: A multiprogramming system with virtual memory

• Suppose now we add VM and make disk 1 a dedicated paging device

• Pages are 1Kbyte in size and the (usable) memory is equivalent to 64K pages

• Each job page faults at a rate determined by the following lifetime function: Q: What number of batch jobs keeps the system throughput at its maximum and at what point does thrashing occur?

1.5 Example 8: A multiaccess multiprogramming system with virtual memory

• During the day the system runs in interactive mode with a number of terminal users

• The average think time of each user is 30 seconds

Q: How does the system response time and throughput vary with the number of terminals and how many terminals can be supported before the system starts to thrash?

2 Stochastic Processes

2.1 Introduction

Computer systems are

1. dynamic - they can pass through a succession of states as time progresses

2. influenced by events which we consider here as random phenomena

c.f. bank, supermarket, stock exchange \underline{Definition}: A stochastic process S S S is a family of random variables {X_{t} ∈ Ω|t ∈ T }, each defined on some (the same for each) sample space Ω for a parameter space T.

• T, Ω may be either discrete or continuous • T is normally regarded as time

– real time: continuous

– every month or after job completion: discrete • Ω is the set of values each X_{t} may take

– bank balance: discrete

– number of active tasks: discrete

– time delay in communication network: continuous

2.2 Example: The Poisson process

The Poisson process is a renewal process with renewal period (interarrival time) distribution and probability density function (pdf)

F (x) = P (X ≤ x) = 1 − e^{λx}
pdf: f(x) = F′(x) = λe^{−λx}

λ is the parameter or rate of the Poisson process.

2.3 Memoryless Property of the (negative) exponential distribution

If S is an exponential random variable

P (S ≤ t + s|S > t) = P (S ≤ s) ∀t, s ≥ 0

(i.e. it doesn’t matter what happened before time t)

\underline{Proof}

P (S ≤ t + s|S > t) = \frac{P (t < S ≤ t + s)}{P (S > t)}
= \frac{P (S ≤ t + s) − P (S ≤ t)}{1 − P (S ≤ t)}
= \frac{1 − e^{−λ(t+s)} − (1 − e^{−λt})}{e^{−λt}}

(λ is the rate of the exp. distribution)

= \frac{e^{−λt} − e^{−λ(t+s)}}{e^{−λt}} = 1 − e^{−λs}
= P (S ≤ s)

2.4 More properties of the Poisson process

P (arrival in (t, t + h)) = P (R ≤ h) = P (S ≤ h) ∀t
= 1 − e^{−λh}
= λh + o(h)

Therefore

1. Probability of an arrival in (t, t + h) is λh + o(h) regardless of process history before t

2. Probability of more than one arrival in (t, t + h) is o(h) regardless of process history before t In fact we can take this result as an alternative definition of the Poisson process. From it we can derive the distribution function of the interarrival times (negative exponential) and the Poisson distribution for N_{t} (the arrival process)

P (N_{t} = n) = \frac{(λt)^{n}}{n!} e^{−λt}.

2.5 Derivation of the Poisson process

The proof of the claim is by induction on the integers. Let P_{n}(t) = (P (N_{t} = n). Base case (n = 0)

P_{0}(t + h) = P (N_{t} = 0 & no arrivals in (t, t + h))
= P_{0}(t)(1 − λh + o(h)) (by independence)
⟹ \frac{P_{0}(t + h) − P_{0}(t)}{h} = −λP_{0}(t) + o(1)
P′_{0}(t) = −λP_{0}(t) as h → 0
⟹ P_{0}(t) = Ce^{−λt}
P_{0}(0) = P (N_{0} = 0) = 1 therefore C = 1

Inductive Step (n > 0)

P_{n}(t + h) = P_{n}(t)P_{0}(h) + P_{n−1}(h)P_{1}(h) + o(h)
= (1 − λh)P_{n}(t) + λhP_{n−1}(t) + o(h)
⟹ P′_{n}(t) = −λP_{n}(t) + λP_{n−1}(t)
⟹ \frac{d}{dt}(e^{λt}P_{n}(t)) = λe^{λt}P_{n−1}(t)

Inductive hypothesis:

P_{n−1}(t) = e^{−λt} \frac{(λt)^{n−1}}{(n − 1)!}

This is OK for n = 1. Then

\frac{d}{dt}(e^{λt}P_{n}(t)) = \frac{(λ)^{n}}{(n − 1)!}t^{n−1}
⟹ e^{λt}P_{n}(t) = \frac{(λt)^{n}}{(n)!} + D

For t = 0, P_{n}(t) = 0 for n ≥ 2 and so D = 0. Thus

P_{n}(t) = e^{−λt} \frac{λt}{n!}

2.6 Derivation of the interarrival time distribution

1. Using the derived Poisson distribution

P (T ≤ t) = 1 − P (0 arrivals in (0, t))
= 1 − e^{−λt}

(distribution for negative exponential random variable)

2. Directly from assumptions (exercise). Use the memoryless property to simplify the equation

P (T ≤ t + h) = P ((T ≤ t) ∨ [(T > t) ∧ (1 arrival in (t, t + h))])

hence derive and solve a differential equation for P (T ≤ t) = F (t).

2.7 Superposition Property

If A_{1}, …, A_{n} are independent Poisson Processes with rates λ_{1}, …, λ_{n} respectively, let there be K_{i} arrivals in an interval of length t from process A_{i} (1 ≤ i ≤ n). Then K = K_{1} + ⋯ + K_{n} has Poisson distribution with parameter λt where λ = λ_{1} + ⋯ + λ_{n}. I.e. the superposition of PPs with rates λ_{i} is a PP with rate ∑_{i} λ_{i}.

\underline{Proof} The distribution of K is the convolution of the distributions of the K_{i} which are Poisson. E.g. if n = 2

P (K = k) = ∑_{i=0}^{k} \frac{(λ_{1}t)^{i}}{i!} e^{−λ_{1}t} \frac{(λ_{2}t)^{k−i}}{(k − i)!} e^{−λ_{2}t}

= \frac{e^{−(λ_{1}+λ_{2})t}}{k!} ∑_{i=0}^{k} \binom{k}{i}(λ_{1}t)^{i}(λ_{2}t)^{k−i}
= e^{−(λ_{1}+λ_{2})t} \frac{[(λ_{1} + λ_{2})t]^{k}}{k!}

as required. The proof for arbitrary n ≥ 2 is an easy induction on n.

2.8 Decomposition Property

If a Poisson Process is decomposed into processes B_{1}, …, B_{n} by assigning each arrival of A to B_{i} with independent probability q_{i} (∑ q_{i} = 1), then B_{1}, …, B_{n} are independent Poisson Processes with rates q_{1}λ, …, q_{n}λ.

\underline{Example}: Two parallel processors, B_{1} and B_{2}. Incoming jobs (Poisson arrivals A) are directed to B_{1} with probability q_{1} and to B_{2} with probability q_{2}. Then each processor “sees” a Poisson arrival process for its incoming job stream.

\underline{Proof} For n = 2, let K_{i} = number of arrivals to B_{i} in time t (i = 1, 2), K = K_{1} + K_{2}

P (K_{1} = k_{1}, K_{2} = k_{2}) = \underbrace{P (K_{1} = k_{1}, K_{2} = k_{2}|K = k_{1} + k_{2})} \underbrace{P (K = k_{1} + k_{2})}
joint probability  binomial  Poisson
= \frac{(k_{1}+k_{2})!}{k_{1}!k_{2}!}q_{1}^{k_{1}}q_{2}^{k_{2}} \frac{(λt)^{k_{1}+k_{2}}}{(k_{1}+k_{2})!} e^{−λt}
= \frac{(q_{1}λt)^{k_{1}}}{k_{1}!} e^{−q_{1}λt} \frac{(q_{2}λt)^{k_{2}}}{k_{2}!} e^{−q_{2}λt}

I.e. a product of two independent Poisson distributions (n ≥ 2: easy induction)

Figure 1: Superposition and decomposition of a Poisson process

32

2.9 Markov Chains and Markov Processes

• Special class of stochastic processes that satisfy the Markov property (MP): Given the state of the process at time t, its state at time t + s has probability distribution which is a function of s only.

• i.e. the future behaviour after t is independent of the behaviour before t

• Often intuitively reasonable, yet sufficiently “special” to facilitate effective mathematical analysis

• We consider processes with discrete state (sample) space and:

1. discrete parameter space (times {t_{0}, t_{1}, … }), a Markov chain or Discrete Time Markov Chain

2. continuous parameter space (times t ≥ 0, t ∈ R), a Markov Process or Continuous Time Markov Chain. E.g. number of arrivals in (0, t) from a Poisson arrival process defines a Markov Process because of the memoryless property.

2.10 Markov Chains

• Let X = {X_{n}|n = 0, 1, … } be an integer valued Markov chain (MC), X_{i} ≥ 0, X_{i} ∈ Z, i ≥ 0. MP states that:

P (X_{n+1} = j|X_{0} = x_{0}, …, X_{n} = x_{n}) = P (X_{n+1} = j|X_{n} = x_{n})

for j, n = 0, 1, …

• Evolution of a MC is completely described by its 1-step transition probabilities

q_{ij}(n) = P (X_{n+1} = j|X_{n} = i) for i, j, n, ≥ 0

Assumption: q_{ij}(n) = q_{ij} is independent of time n (time homogeneous)

∑_{j∈Ω} q_{ij} = 1 ∀i ∈ Ω

• MC defines a transition probability matrix

Q = [q_{00} q_{01} …; q_{10} q_{11} …; ⋮ ; q_{i0} … q_{ii} …; ⋮] in which all rows sum to 1

– dimension = # of states in Ω if finite, otherwise countably infinite

– conversely, any real matrix Q s.t. q_{ij} ≥ 0, ∑_{j} q_{ij} = 1 (called a stochastic matrix) defines a MC 2.10.1 Examples

1. \underline{Telephone line}:

Line is either idle (state 0) or busy (state 1).

Idle at time n ⟹ idle at time (n + 1) w.p. 0.9
Idle at time n ⟹ busy at time (n + 1) w.p. 0.1  Q = [\begin{matrix}0.9 & 0.1 \\ 0.3 & 0.7 \end{matrix}]
Busy at time n ⟹ idle at time (n + 1) w.p. 0.3
Busy at time n ⟹ busy at time (n + 1) w.p. 0.7

May be represented by a state diagram 2:

Figure 2: Telephone line example

37

2. \underline{Gambler}

Bets £1 at a time on the toss of fair die. Loses if number is less than 5, wins £2 if 5 or 6. Stops when broke or holds £100. If X_{0} is initial capital (0 ≤ X_{0} ≤ 100) and X_{n} is the capital held after n tosses {X_{n}|n ≤ 0, 1, 2, … } is a MC with q_{ii} = 1 if i = 0 or i ≥ 100, q_{i,i−1} = \frac{2}{3}, q_{i,i+2} = \frac{1}{3} for i = 1, 2, …, 99 q_{ij} = 0 otherwise.

3.

I/O buffer, capacity M records New record added in any unit of time w.p. α (if not full). Buffer emptied in any unit of time w.p β. If both occur in same interval, insertion done first. Let X_{n} be the number of records in buffer at (discrete) time n. Then, assuming that insertions and emptying are independent of each other and of their own past histories, {X_{n}|n = 0, 1, … } is a MC with state space {0, 1, …, M} and state diagram:

Figure 3: I/O buffer example

The transition matrix follows immediately, e.g.

q_{12} = α(1 − β) = q_{n,n+1}

(0 ≤ n ≤ M − 1)

q_{MM} = 1 − β

etc.

2.10.2 Multi-step transition probabilities Let

q_{ij}^{(2)} = P (X_{n+2} = j|X_{n} = i)
= ∑_{k∈Ω} P (X_{n+1} = k, X_{n+2} = j|X_{n} = i) from law of tot. prob.
= ∑_{k∈Ω} P (X_{n+2} = j|X_{n} = i, X_{n+1} = k)P (X_{n+1} = k|X_{n} = i)
= ∑_{k∈Ω} P (X_{n+2} = j|X_{n+1} = k)P (X_{n+1} = k|X_{n} = i) by MP
= ∑_{k∈Ω} q_{ik}q_{kj} by TH
= (Q^{2})_{ij}

Similarly, m-step transition probabilities :

q_{ij}^{(m)} = P (X_{n+m} = j|X_{n} = i) (m ≥ 1)
= (Q^{m})_{ij}

by induction on m. Therefore we can compute probabilistic behaviour of a MC over any finite period of time, in principle. E.g. average no. of records in buffer at time 50

E[X_{50}|X_{0} = 0] = ∑_{j=1}^{min(M,50)} jq_{0j}^{(50)}

Computationally intractable. Need to determine long-term behaviour: hope that asymptotically MC approaches a steady-state (probabilistically), i.e. that ∃{p_{j}|j = 0, 1, 2, … } s.t.

p_{j} = lim_{n→∞} P (X_{n} = j|X_{0} = i) = lim_{n→∞} q_{ij}^{(n)}

independent of i 2.10.3 Definitions and properties of MCs

Let v_{ij} = prob. that state j will eventually be entered, given that the MC has been in state i, i.e.

v_{ij} = P (X_{n} = j for some n|X_{0} = i)

• If v_{ij} ≠ 0, then j is reachable from i

• If v_{ij} = 0 ∀j ≠ i, v_{ii} = 1, then i is an absorbing state

\underline{Example (1) & (3)}: all states reachable from each other (e.g. look at transition diagrams) \underline{Example (2)}: all states in \{1, 2, …, 99\} reachable from each other, 0 & 100 absorbing A subset of states, C is called closed if j ∉ C, implies j cannot be reached from any i ∈ C. E.g. set of all states, Ω, is closed. If ∄ proper subset C ⊂ Ω which is closed, the MC is called irreducible. A Markov Chain is irreducible if and only if every state is reachable from every other state. E.g. examples (1) & (3) and {0}, {100} are closed in example (2).

2.10.4 Recurrent states

If v_{ii} = 1, state i is recurrent (once entered, guaranteed eventually to return). Thus we have: i recurrent implies i is either not visited by the MC or is visited an infinite number of times – no visit can be the last (with non-zero probability). If i is not recurrent it is called transient. This implies the number of visits to a transient state is finite w.p. 1 (has geometric distribution). E.g. if C is a closed set of states, i ∉ C, j ∈ C and v_{ij} ≠ 0, then i is transient since MC will eventually enter C from i, never to return. E.g. in example (2), states 1 to 99 are transient, states 0 and 100 are recurrent (as is any absorbing state)

\underline{Proposition}: If i is recurrent and j is reachable from i, then j is also recurrent. \underline{Proof}: v_{jj} ≠ 1 implies v_{ij} ≠ 1 since if the MC visits i after j it will visit i repeatedly and with probability 1 will eventually visit j since v_{ij} ≠ 0. This implies v_{ii} ≠ 0 since with non-zero probability the MC can visit j after i but not return to i (w.p. 1 − v_{ji} > 0) qed.

Thus, in an irreducible MC, either all states are transient (a transient MC) or recurrent (a recurrent MC).

2.10.5 Further properties of MCs

Let X be an irreducible, recurrent MC and let n_{1}^{j}, n_{2}^{j}, … be the times of successive visits to state j, m_{j} = E[n_{k+1}^{j} − n_{k}^{j}] (k = 1, 2, …), the mean interval between visits (independent of k by the MP).

\underline{Intuition}:

p_{j} = \frac{1}{m_{j}}

Because the proportion of time spent, on average, in state j is 1/m_{j}. This is not necessarily true, because the chain may exhibit some periodic behaviour:

The state j is periodic with period m > 1 if q_{ii}^{(k)} = 0 for k ≠ rm for any r ≥ 1 and P (X_{n+rm} = j for some r ≥ 1|X_{n} = j) = 1. Otherwise it is aperiodic, or has period 1. (Note that a periodic state is recurrent)

\underline{Proposition}: In an irreducible MC, either all states are aperiodic or periodic with the same period. The MC is then called aperiodic or periodic respectively.

\underline{Proposition}: If \{X_{n}|n = 0, 1, … \} is an irreducible, aperiodic MC, then the limiting probabilities {p_{j}|j = 0, 1, … } exist and p_{j} = 1/m_{j}.

2.10.6 Null & positive recurrence

If m_{j} = ∞ for state j then p_{j} = 0 and state j is recurrent null. Conversely, if m_{j} < ∞, then p_{j} > 0 and state j is recurrent non-null or positive recurrent.

\underline{Proposition}: In an irreducible MC, either all states are positive recurrent or none are. In the former case, the MC is called positive recurrent (or recurrent non-null).

A state which is aperiodic and positive recurrent is often called ergodic and an irreducible MC whose states are all ergodic is also called ergodic. When the limiting probabilities {p_{j}|j = 0, 1, … } do exist they form the

\begin{matrix}steady state \\ equilibrium \\ long term \end{matrix}\} probability distribution (SSPD)

of the MC. They are determined by the following theorem.

2.10.7 Steady state theorem for Markov chains

An irreducible, aperiodic Markov Chain, X, with state space S and one-step transition probability matrix Q = (q_{ij}|i, j ∈ S), is positive recurrent if and only if the system of equations

p_{j} = ∑_{i∈S} p_{i}q_{ij}

with ∑_{i∈S} p_{i} = 1 (normalisation) has a solution. If it exists, the solution is unique and is the SSPD of X.

\underline{Note}: If S is finite, X is always positive recurrent, which implies the equations have a unique solution. The solution is then found by discarding a balance equation & replacing it with the normalising equation (the balance equations are dependent since the rows of homogeneous equations \underline{p} − \underline{p}.\underline{Q} = \underline{0} all sum to zero).

2.11 Markov Processes

• Continuous time parameter space, discrete state space

X = {X_{t}|t ≥ 0} X_{t} ∈ Ω

where Ω is a countable set. • Markov property

P (X_{t+s} = j|X_{u}, u ≤ t) = P (X_{t+s} = j|X_{t})

• Markov process is time homogeneous if the r.h.s. of this equation does not depend on t

– q_{ij}(s) = P (X_{t+s} = j|X_{t} = i) = P (X_{s} = j|X_{0} = i) (i, j = 0, 1, …)

– Transition probability functions of the MP

• Markov Property and time homogeneity imply:

If at time t the process is in state j, the time remaining in state j is independent of the time already spent in state j: memoryless property \underline{Proof}:

P (S > t + s|S > t) = P (X_{t+u} = j, 0 ≤ u ≤ s|X_{u} = j, 0 ≤ u ≤ t)

where S = time spent in state j state j entered at time 0

= P (X_{t+u} = j, 0 ≤ u ≤ s|X_{t} = j) by MP
= P (X_{u} = j, 0 ≤ u ≤ s|X_{0} = j) by T.H.
= P (S > s)
⟹ P (S ≤ t + s|S > t) = P (S ≤ s)

• Time spent in state i is exponentially distributed, parameter μ_{i}.

2.11.1 Time homogeneous Markov Processes

The MP implies next state, j, after current state i depends only on i, j – state transition probability q_{ij}. This implies the Markov Process is uniquely determined by the products:

a_{ij} = μ_{i}q_{ij}

where μ_{i} is the rate out of state i and q_{ij} is the probability of selecting state j next. The a_{ij} are the generators of the Markov Process.

• intuitively reasonable 2.11.2 Instantaneous transition rates Consider now the (small) interval (t, t + h)

P (X_{t+h} = j|X_{t} = i) = μ_{i}hq_{ij} + o(h)
= a_{ij}h + o(h)

• a_{ij} is the instantaneous transition rate i → j i.e. the average number of transitions i → j per unit time spent in state i 2.11.3 Examples

1.

Poisson process rate λ

a_{ij} = \begin{cases}λ if j = i + 1 \\ 0 if j ≠ i, i + 1 \\ not defined if j = i \end{cases}

because

P (arrival in (t, t + h)) = λh + o(h)
i → i + 1  a_{i,i+1}h

2.

The buffer problem

• Records arrive as a P.P. rate λ

• Buffer capacity is M

• Buffer cleared at times spaced by intervals which are exponentially distributed, parameter μ. Clearance times i.i.d. & independent of arrivals (i.e. clearances are an independent PP, rate μ)

a_{ij} = \begin{cases}λ if j = i + 1 (0 ≤ i ≤ M − 1) \\ μ if j = 0 (i ≠ 0) \\ 0 otherwise (j ≠ i) \end{cases}

[Probability of > 1 arrivals or clearances, or ≥ 1 arrivals \underline{and} clearances in (t, t + h) is o(h)]

Figure 4: Buffer problem

3.

Telephone exchange Suppose there 4 subscribers and any two calls between different callers can be supported simultaneously. Calls are made by non-connected subscribers according to independent P.Ps, rate λ (callee chosen at random). Length of a call is (independent) exponentially distributed, parameter μ. Calls are lost if called subscriber is engaged. State is the number of calls in progress ∈ {0, 1, 2}

a_{01} = 4λ (all free)
a_{12} = \frac{2}{3}λ (caller has \frac{1}{3} probability of successful connection)
a_{10} = μ
a_{21} = 2μ (either call may end)

\underline{Exercise}: The last equation follows because the distribution of the random variable Z = min(X, Y) where X, Y are independent exponential random variables with parameters λ, μ respectively is exponential with parameter λ + μ. Prove this.

Figure 5: Telephone exchange

62

2.11.4 The Generator Matrix

∑_{j∈Ω,j≠i} q_{ij} = 1 ⟹ μ_{i} = ∑_{j∈Ω,j≠i} a_{ij}

(hence instantaneous transition rate out of i). Let a_{ii} = −μ_{i} (undefined so far)

(a_{ij}) = A = (\begin{matrix}a_{00} & a_{01} & … \\ a_{10} & a_{11} & … \\ … \\ a_{i0} & a_{i1} & … & a_{ii} & … \\ … \end{matrix})

A is the generator matrix of the Markov Process. Rows of A sum to zero (∑_{j∈S} a_{ij} = 0)

2.11.5 Transition probabilities & rates

• determined by A

q_{ij} = \frac{a_{ij}}{μ_{i}} = −\frac{a_{ij}}{a_{ii}}
μ_{i} = −a_{ii}

• hence A is all we need to determine the Markov process

• Markov processes are instances of state transition systems with the following properties

– The state holding time are exponentially distributed

– The probability of transiting from state i to state j depends only on i and j

• In order for the analysis to work we require that the process in irreducible – every state must be reachable from every other, e.g.

Figure 6: (Ir)reducible Markov chains

65

• Associated with each arc in a state transition diagram is a rate, e.g.: Figure 7: Transition rates in Markov chains

• The state holding time depends on the departure rates (1/(r_{i,a} + r_{i,b} + r_{i,c}) is the mean holding time for state i in the example).

• The probability flux from a state i to a state j is the average number of transitions from i → j per unit time at equilibrium:

Probability flux(i → j) = r_{i,j}p_{i}

• At equilibrium (if it exists) the total flux into each state must balance the total flux out of it

• For example, in the example, for state i alone:

(r_{i,a} + r_{i,b} + r_{i,c})p_{i} = r_{j,i}p_{j} + r_{k,i}p_{k} • Treating all states the same way leads to a set of linear equations:

∑_{j≠i} a_{ij}p_{i} = ∑_{j≠i} a_{ji}p_{j} = −a_{ii}p_{i} for all j ∈ S

• Called the balance equations and subject to the normalising equation

∑_{i∈S} p_{i} = 1

• The steady-state theorem tells us that if these equations have a solution then there is a steady-state and that the solution is unique

• Important generalisation: At equilibrium the fluxes also balance into and out of every closed contour drawn around any collection of states

• This often provides a short-cut to the solution – see the M/M/1 queue later.

2.12 Steady state results

\underline{Theorem}

(a) if a Markov process is transient or recurrent null, p_{j} = 0 ∀j ∈ S and we say a SSPD does not exist

(b) If a Markov Process is positive recurrent, the limits p_{j} exist, p_{j} > 0, ∑_{j∈S} p_{j} = 1 and we say {p_{j}|j ∈ S} constitute the SSPD of the Markov Process.

2.12.1 Steady State Theorem for Markov Processes An irreducible Markov Process X with state space S and generator matrix A = (a_{ij}) (i, j ∈ S) is positive recurrent if and only if

∑_{i∈S} p_{i}a_{ij} = 0 for j ∈ S [ Balance equations]
∑_{i∈S} p_{i} = 1 [Normalising equation]

have a solution. This solution is unique and is the SSPD.

2.12.2 Justification of the Balance Equation The rate going from state i to j(≠ i) is a_{ij}, the fraction of time spent in i is p_{i}

∑_{i≠j} a_{ij}p_{i} = ∑_{i≠j} a_{ji}p_{j}

Avg. no. of transitions

i → j in unit time  Avg. no. of transitions

j → i in unit time

∑_{i≠j} flux(i → j) = ∑_{i≠j} flux(j → i) ∀j

2.12.3 Buffer example (DTMC) \underline{1 ≤ i ≤ M − 1}

(Net “rate” in) = (Net “rate” out)
(α(1 − β) + β)p_{i} = α(1 − β)p_{i−1}

{= p_{i} = α(1 − β)p_{i−1} + p_{i}(1 − α)(1 − β) from S.S. Theorem} Therefore

p_{i} = kp_{i−1} = k^{i}p_{0}

where k = \frac{α(1−β)}{α+β−αβ} (1 ≤ i ≤ M − 1)

Figure 8: I/O buffer.

\underline{i = M} βp_{M} = α(1 − β)p_{M−1} therefore

p_{M} = \frac{α(1 − β)}{β}k^{M−1}p_{0}

\underline{i = 0} Redundant equation (why?) - use as check

α(1 − β)p_{0} = ∑_{i=1}^{M} βp_{i} = β ∑_{i=1}^{M−1} k^{i}p_{0} + k^{M−1}α(1 − β)p_{0}
= p_{0}(βk \frac{1 − k^{M−1}}{1 − k} + α(1 − β)k^{M−1})

rest is exercise 2.12.4 Examples (CTMC)

1. I/O buffer: By considering the flux into and out of each state 0, 1, …, M we obtain the balance equations:

λp_{0} = μ(p_{1} + ⋯ + p_{M}) (State 0)
(λ + μ)p_{i} = λp_{i−1} (1 ≤ i ≤ M − 1) State i
μp_{M} = λp_{M−1} State M

Normalising equation:

p_{0} + ⋯ + p_{M} = 1
⟹ p_{j} = (\frac{λ}{λ + μ})^{j} \frac{μ}{λ + μ} (0 ≤ j ≤ M − 1)
p_{M} = (\frac{λ}{λ + μ})^{M}

Thus (for example) mean number of records in the buffer in the steady state = Mα^{M} + ∑_{j=0}^{M−1} jα^{j} \frac{μ}{λ+μ} where α = \frac{μ}{λ+μ}

2.

Telephone network

4λp_{0} = μp_{1} (State 0)
(μ + \frac{2}{3}λ)p_{1} = 4λp_{0} + 2μp_{2} (State 1)
2μp_{2} = λ\frac{2}{3}p_{1} (State 2)

Thus p_{1} = \frac{4λ}{μ}p_{0}, p_{2} = \frac{λ}{3μ}p_{1} = \frac{4λ^{2}}{3μ^{2}} p_{0} with

p_{0} + p_{1} + p_{2} = 1 ⟹ p_{0} = (1 + \frac{4λ}{μ} + \frac{4λ^{2}}{3μ^{2}} )^{−1} Average number of

calls in progress in the steady state = 1.p_{1} + 2.p_{2} = \frac{\frac{4λ}{μ}(1+ \frac{2λ}{3μ})}{1+ \frac{4λ}{μ} + \frac{4λ^{2}}{3μ^{2}}} 2.12.5 Birth-Death processes and the single server queue

(SSQ)

A Markov process with state space S = {0, 1, … } is called a birth-death process if the only non-zero transition probabilities are q_{i,i+1} and q_{i+1,i} (i ≥ 0), representing births and deaths respectively. (In a population model, q_{00} would be 1 since 0 would be an absorbing state.) The SSQ model consists of

• a Poisson arrival process, rate λ

• a queue which arriving tasks join

• a server which processes tasks in the queue in FIFO (or other) order and has exponentially distributed service times, parameter μ (i.e. given a queue length > 0, service completions form a Poisson process, rate μ)

Figure 9: Single server queue.

• The state is the queue length (including the task being served if any), i.e. the state space is {0, 1, … }

• SSQ model is a birth-death process

• λ, μ are in general functions of the queue length (i.e. state dependent) and we write λ(n), μ(n) for state n.

2.12.6 The memoryless property in the M/M/1 queue

\underline{Notation:} The SSQ with Poisson arrivals and exponential service times is called an M/M/1 queue

• the first M describes the arrival process as a Markov process (Poisson)

• the second M describes the service time distribution as a Markov process (exponential)

• the 1 refers to a single server (m parallel server would be denoted as M/M/m)

• Later we will consider M/G/1 queues, where the service time distribution is non-Markovian (“general”)

SSQ therefore follows a Markov process and has the memoryless property that:

1. Probability of an arrival in (t, t + h) = λ(i)h + o(h) in state i

2. Probability of a service completion in (t, t + h) = μ(i)h + o(h) in state i > 0 (0 if i = 0)

3. Probability of more than 1 arrival, more than one service completion or 1 arrival and 1 service completion in (t, t + h) = o(h).

4. Form these properties we could derive a differential equation for the \underline{transient} queue length probabilities – compare Poisson process.

2.12.7 State transition diagram for the SSQ

Figure 10: Single server queue state diagram.

• Consider the balance equation for states inside the red (thick) contour. Outward flux (all from state i): p_{i}λ(i) (i ≥ 0); Inward flux (all from state i + 1): p_{i+1}μ(i + 1) (i ≥ 0).

Thus,

p_{i}λ(i) = p_{i+1}μ(i + 1)
so p_{i+1} = \frac{λ(i)}{μ(i + 1)}p_{i} = [ ∏_{j=0}^{i} ρ(j)]p_{0}

where ρ(j) = \frac{λ(j)}{μ(j+1)} • Normalising equation implies

p_{0} (1 + ∑_{i=0}^{∞} ∏_{j=0}^{i} ρ(j)) = 1
⟹ p_{0} = [ ∑_{i=0}^{∞} ∏_{j=0}^{i−1} ρ(j)]^{−1}

where ∏_{j=0}^{−1} = 1 (empty product). Therefore

p_{i} = \frac{∏_{j=0}^{i−1} ρ(j)}{∑_{k=0}^{∞} ∏_{n=0}^{k−1} ρ(n)} (i ≥ 0).

• So, is there always a steady state? • SSQ with constant arrival and service rates

λ(n) = λ, μ(n) = μ, ρ(n) = ρ = λ/μ ∀n ∈ S implies

p_{0} = [ ∑_{i=0}^{∞} ρ^{i}]^{−1} = 1 − ρ
p_{i} = (1 − ρ)ρ^{i} (i ≥ 0)

• Mean queue length, L (including any task in service)

L = ∑_{i=0}^{∞} ip_{i} = ∑_{i=0}^{∞}(1 − ρ)iρ^{i}

= ρ(1 − ρ)\frac{d}{dρ}\{ ∑_{i=0}^{∞} ρ^{i}\} = ρ(1 − ρ)\frac{d}{dρ}\{(1 − ρ)^{−1}\}
= \frac{ρ}{1 − ρ}

• Utilisation of server

U = 1 − P (server idle) = 1 − p_{0} = 1 − (1 − ρ) = ρ
= λ/μ.

However, we could have deduced this without solving for p_{0}: In the steady state (assuming it exists),

λ = arrival rate = throughput = P (server busy).service rate = Uμ

Argument applies for any system in equilibrium - didn’t need MP - see M/G/1 queue later.

2.12.8 Response times

To analyse response times, need to consider the state of the queue at the time of arrival of a task. We use the \underline{Random Observer Property} of the Poisson process: The state of a system at equilibrium seen by an arrival of a Poisson process has the same distribution as that seen by an observer at a random instant, i.e. if the state at time t is denoted by S_{t},

P (S_{t_{0}^{−}} = i | arrival at t_{0}) = P (S_{t_{0}^{−}} = i)

Mean response time, W If the queue length seen by an arriving task is j,

response time =  residual service time of task in service (if j > 0)
+ j i.i.d. service times

But for exponential service times, residual service time has the same distribution as full service time

⟹ Response time = sum of (j + 1) service times
⟹ Mean response time, W = ∑ p_{j}(j + 1)μ^{−1}
= (1 + \frac{ρ}{1 − ρ})μ^{−1} = \frac{1}{μ − λ}

Mean queueing time, W_{Q} (excluding service)

W_{Q} = W − μ^{−1} = Lμ^{−1} = \frac{ρ}{μ − λ}.

2.12.9 Distribution of the waiting time, F_{W} (x)

By the random observer property (and memoryless property)

F_{W} (x) = ∑_{j=0}^{∞} p_{j}E_{j+1}(x)

where E_{j+1}(x) is the convolution of (j + 1) exponential distributions, each with parameter μ - called the Erlang-(j + 1) distribution with parameter μ. Similarly, for density functions:

f_{W} (x) = ∑_{j=0}^{∞} p_{j}e_{j+1}(x)

where e_{j+1}(x) is the pdf corresponding to E_{j+1}(x), i.e.

\frac{d}{dx}E_{j+1}(x) = e_{j+1}(x), defined by

e_{1}(x) = μe^{−μx}
e_{j+1}(x) = μ ∫_{0}^{x} e^{−μ(x−u)}e_{j}(u)du

(convolution of Erlang-j and exponential)

⟹ e_{j}(x) = μ\frac{(μx)^{j−1}}{(j − 1)!} e^{−μx} (Exercise)
⟹ f_{W} (x) = (μ − λ)e^{(μ−λ)x} (Exercise)

\underline{Example} Given m Poisson streams, each with rate λ and independent of the others, into a SSQ, service rate μ, what is the maximum value of m for which, in steady state, at least 95% of waiting times, T ≤ w? (Relevant in “end-to-end” message delays in communication networks, for example)

P (T ≤ w) ≥ 0.95

i.e. 1 − e^{−(μ−mλ)w} ≥ 0.95
or e^{−(μ−mλ)w} ≤ 0.05
⟹ e^{(μ−mλ)w} ≥ 20

μ − mλ ≥ \frac{ln 20}{w}

⟹ m ≤ \frac{μ}{λ} − \frac{ln 20}{wλ}

m < μ/λ is equivalent to the existence of a steady state.

2.13 Multiple parallel servers - M/M/m queue

Figure 11: Multiple parallel servers.

SSQ representation:

λ(n) = λ (n ≥ 0)
μ(n) = \begin{cases}nμ (1 ≤ n ≤ m) \\ mμ (n ≥ m) \end{cases}

Front of queue served by any available server. \underline{Loading}, ρ = λ/μ (average amount of service required in unit time). By general result for M/M/1 queue:

p_{j} = p_{0} ∏_{i=0}^{j−1} \frac{λ(i)}{μ(i + 1)} = \begin{cases}p_{0} \frac{ρ^{j}}{j!} (0 ≤ j ≤ m) \\ p_{0} \frac{ρ^{j}}{m!m^{j−m}} (j ≥ m) \end{cases}

This implies

p_{0} = \frac{1}{∑_{i=0}^{m−1} \frac{ρ^{i}}{i!} + \frac{ρ^{m}}{m!} ∑_{i=m}^{∞}(\frac{ρ}{m})^{i−m}}
= \frac{1}{∑_{i=0}^{m−1} \frac{ρ^{i}}{i!} + \frac{ρ^{m}}{(m−1)!(m−ρ)}}

Average number of busy servers, S

S = ∑_{k=1}^{m−1} kp_{k} + m ∑_{k=m}^{∞} p_{k} = ⋯ = ρ

Steady state argument

arrival rate = λ
average throughput = Sμ (μ per active server)
⟹ Sμ = λ in equilibrium.

\underline{Utilisation} U = S/m = ρ/m, the average fraction of busy servers.

2.13.1 Waiting times

Waiting time is the same as service time if an arrival does not have to queue. Otherwise, the \underline{departure} process is Poisson, rate mμ, whilst the arrived task is queueing (all servers busy). This implies that the queueing time is the same as the queueing time in the M/M/1 queue with service rate mμ.

• Let

q = P (arrival has to queue)
= P (find ≥ m jobs on arrival)

• by R.O.P.

q = ∑_{j=m}^{∞} p_{j} = p_{0} \frac{ρ^{m}}{(m − 1)!(m − ρ)} Erlang delay formula

• Let Q be the queueing time random variable (excluding service)

F_{Q}(x) = P (Q ≤ x) = P (Q = 0) + P (Q ≤ x|Q > 0)P (Q > 0)
= (1 − q) + q(1 − e^{−(mμ−λ)x})
= 1 − qe^{−(mμ−λ)x}

P (Q ≤ x|Q > 0) is given by the SSQ, rate mμ, result for waiting time. (Why is this?) Note that F_{Q}(x) has a jump at the origin, F_{Q}(0) ≠ 0.

• Mean queueing time

W_{Q} = \frac{q}{mμ − λ}

• Mean waiting time

W = W_{Q} + 1/μ = \frac{(q + m)μ − λ}{μ(mμ − λ)}

• \underline{Exercise}: What is the waiting time \underline{density function}?

2.13.2 The infinite server

• In the M/M/m queue, let m → ∞ – “unlimited service capacity”

– always sufficient free servers to process an arriving task - e.g. when the number tasks in the system is finite

– no queueing ⟹ infinite servers model delays in a task’s

processing

p_{j} = \frac{ρ^{j}}{j!} p_{0} ⟹ p_{0} = e^{−ρ}

– balance equations have a solution for all λ, μ

– this is not surprising since the server can never be overloaded • This result is independent of the exponential assumption - a

property of the queueing discipline (here there is no queueing - a pathological case)

2.14 M/M/m queues with finite state space

M/M/1/k (k is the max. queue length) queue

μ(n) = μ for all queue lengths n

λ(n) = \begin{cases}λ (0 ≤ n < k) \\ 0 (n ≥ k) \end{cases}

Hence, if ρ = λ/μ.

p_{j} = \begin{cases}p_{0}ρ^{j} (j = 0, 1, …, k) \\ \frac{∏_{i=0}^{j−1} λ(i)}{∏_{i=0}^{j−1} μ(i+1)} = 0 (j > k) as λ(k) = 0 \end{cases}

Telephone network with maximum capacity of k calls

λ(n) = λ (0 ≤ n < k), λ(k) = 0
μ(n) = nμ n calls in progress
⟹ M/M/k/k queue

p_{j} = p_{0} \frac{ρ^{j}}{j!} j = 0, 1, …, k (ρ = λ/μ)

Probability that a call is lost:

p_{k} = \frac{ρ^{k}/k!}{∑_{j=0}^{k} ρ^{j}/j!} \underline{Erlang loss formula}

Throughput = λ(1 − p_{k}) [ = μ ∑_{j=1}^{k} jp_{j}]

2.14.1 Terminal system with parallel processing N users logged on to a computer system with m parallel processors

• exponentially distributed think times, mean 1/λ, before submitting next task

• each processor has exponential service times, mean 1/μ

Figure 12: Terminals with parallel processors.

• tasks may use any free processor, or queue (FIFO) if there are none.

• state space S = {n|0 ≤ n ≤ N} where n is the queue length (for all processors)

• Poisson arrivals, rate λ(n) = (N − n)λ

• Service rate μ(n) = \begin{cases}nμ (1 ≤ n ≤ m) \\ mμ (m ≤ n ≤ N) \end{cases}

Steady state probabilities {p_{i}|0 ≤ i ≤ N}

p_{i} = \frac{∏ λ(i − 1)}{∏ μ(i)} = \frac{N(N − 1) … (N − i + 1)}{i!}ρ^{i}p_{0} (0 ≤ i ≤ m)

⟹ p_{i} = \begin{cases}\binom{N}{i}ρ^{i}p_{0} (0 ≤ i ≤ m) \\ \frac{N!}{(N−i)!m!m^{i−m}} ρ^{i}p_{0} (m ≤ i ≤ N) \end{cases}

p_{0} = \{ ∑_{i=0}^{m−1} \binom{N}{i}ρ^{i} + ∑_{i=m}^{N} \frac{N!}{(N − i)!m!m^{i−m}} ρ^{i}\}^{−1}

Figure 13: State transition diagram.

The throughput is either given by

μ{ ∑_{j=1}^{m−1} jp_{j} + m ∑_{j=m}^{N} p_{j}}

(mean departure rate from processors) or

λ{N − ∑_{j=1}^{N} jp_{j}}

(mean arrival rate) Other performance measures as previously 2.14.2 The case of “always sufficient processors” - m ≥ N

• Here there is no case m < i ≤ N

⟹ p_{i} = \binom{N}{i}ρ^{i}p_{0} (0 ≤ i ≤ N)
⟹ p_{0} = \{ ∑_{i=0}^{N} \binom{N}{i}ρ^{i}\}^{−1} = (1 + ρ)^{−N}
Thus p_{i} = \binom{N}{i}(\frac{ρ}{1 + ρ})^{i}(\frac{1}{1 + ρ})^{N−i}

(Binomial distribution)

• Probabilistic explanation

– p_{i} is the probability of i “successes” in N Bernoulli (i.i.d.) trials

– probability of success = \frac{ρ}{1+ρ} = \frac{1/μ}{1/λ+1/μ} = fraction of time user is waiting for a task to complete in the steady state = probability (randomly) observe a user in wait-mode.

– probability of failure = fraction of time user is in think mode in the steady state = probability (randomly) observe a user in think-mode

– random observations are i.i.d. in steady state ⟹ trials are Bernoulli

– hence Binomial distribution

• result is independent of distribution of think times.

2.14.3 Analogy with a queueing network Regard the model as a 2-server, cyclic queueing network

⟹ Figure 14: Original and equivalent network.

• As already observed, IS server is insensitive to its service time distribution as far as queue length distribution is concerned.

• Multi-server becomes IS if M ≥ N ⟹ 2 IS servers.

2.15 Little’s result/formula/law (J.D.C. Little, 1961)

Suppose that a queueing system Q is in steady state (i.e. there are fixed, time independent probabilities of observing Q in each of its possible states at random times.) Let:

L = average number of tasks in Q in steady state
W = average time a task spends in Q in steady state
λ = arrival rate (i.e. average number of tasks entering or leaving Q

in unit time)

Then L = λW.

Intuitive Justification Suppose a charge is made on a task of £1 per unit time it spends in Q

• Total collected on average in unit time = L

• Average paid by one task = W

• If charges collected on arrival (or departure), average collected in

unit time = λ.W

⟹ L = λW

• Example: M/M/1 queue W = (L + 1)/μ by R.O.P.

L = λW ⟹ W = \frac{1}{μ − λ}

2.15.1 Application of Little’s law

Server utilisation U.

Figure 15: Little’s law.

• Consider server, rate μ (constant), inside some queueing system: i.e. average time for one service = 1/μ

• Let total throughput of server = λ = total average arrival rate (since in steady state)

• Apply Little’s result to the server only (without the queue)

mean queue length = 0.P (idle) + 1.P (busy)
= U
mean service time = μ^{−1}
⟹ U = \frac{λ}{μ}

• Not the easiest derivation! This is a simple work conservation law.

2.16 Single Server Queue with general service times - M/G/1 queue

Assuming that arrivals are Poisson with constant rate λ, service time distribution has constant mean μ^{−1} (service rate μ) and that a steady state exists

(1) Utilisation, U = P (queue length > 0)
= \frac{μ^{−1}}{λ^{−1}} = λ/μ = “load”

(average amount of work arriving in unit time, already know this, of course)

(2) Mean queue length = L
Mean number in queue = L_{Q}
Mean waiting time = W
Mean queueing time = W_{Q}
Little’s law ⟹ L = λW
L_{Q} = λW_{Q}
By definition, W = W_{Q} + 1/μ

3 equations, 4 unknowns 2.16.1 The fourth equation

• By the random observer property, queue faced on arrival has mean length L_{Q} (excluding task in service, if any)

• By “residual life” result for renewal processes, average service time remaining for task in service (if any) is \frac{μM_{2}}{2} where M_{2} is the second moment of the service time distribution (M_{2} = ∫_{0}^{∞} x^{2}f(x)dx where f(x) is the pdf of service time)

• Thus, since ρ = P (∃ a task being served at arrival instant)

W_{Q} = L_{Q}.1/μ + ρ.\frac{μM_{2}}{2}

• Now

L_{Q} = λW_{Q} ⟹ L_{Q}, W_{Q}, L, W
L = ρ + \frac{λ^{2}M_{2}}{2(1 − ρ)}

• Observe that if \frac{standard deviation}{mean} (& hence the second moment) of service time distribution is large, L is also (not trivial as M_{2} increases with μ^{−1} - but not difficult either!)

2.17 Embedded Markov Chain

• State of the M/G/1 queue at time t is X(t) ∈ S where the state space S = {n|n ≥ 0} as in M/M/1 queue.

• M/G/1 queue is not a Markov process – P (X(t + s)|X(u), u ≤ t) ≠ P (X(t + s)|X(t)) ∀t, s

– e.g. if a service period does not begin at time t

– no memoryless property

• Consider times t_{1}, t_{2}, … of successive departures and let X_{i} = X(t_{i}^{+})

• Given X_{i}, X(t) for t > t_{i} is independent of X(t′) for t′ < t_{i} since at time t_{i}^{+}

– time to next arrival is exponential with parameter λ because arrival process is Poisson – instantaneously, no task is in service, so time to next

departure is a complete service time or that plus the time to next arrival (if queue empty)

⟹ {X_{i}|i ≥ 1} is a Markov Chain with state space S ({t_{i}|i ≥ 1} are called “Markov times”)

• It can be shown that, in steady state of E.M.C., distribution of no. of jobs, j, “left behind” by a departure = distribution of no. of jobs, j, seen by an arrival = lim_{n→∞} P (X_{n} = j) by R.O.P.

• Here we solve p_{j} = ∑_{i=0}^{∞} p_{i}q_{ij} (i ≥ 0) for appropriate one-step transition probabilities q_{ij}.

2.18 Balance equations for the M/G/1 queue

• Solution for \{p_{j}\} exists iff ρ = \frac{λ}{μ} < 1, equivalent to p_{0} > 0 since p_{0} = 1 − U = 1 − ρ in the steady state.

• Valid one-step transitions are i → j for j = i − 1, i, … since may have arbitrary no. of arrivals between successive departures.

• Let

r_{k} = P (k arrivals in a service period)

then

q_{ij} = P (X_{n+1} = j|X_{n} = i) (n ≥ 0)
= r_{j−i+1} (i ≥ 1, j ≥ i − 1)
(i → i − 1 + (j − i + 1) = j)
q_{0j} = r_{j} (j ≥ 0)

[Eventually a job arrives, so 0 → 1, and then 1 → j if there are j arrivals in its service time since then 1 → 1 − 1 + j = j]

⟹ p_{0} = 1 − ρ
p_{j} = p_{0}r_{j} + ∑_{i=1}^{j+1} p_{i}r_{j−i+1} (j ≥ 0)

where r_{k} = ∫_{0}^{∞} \frac{λx)^{k}}{k!} e^{−λx}f(x)dx if service time density function is f(x) (known). This is because P (k arrivals in service time|service time = x) = \frac{λx)^{k}}{k!} e^{−λx} and P (service time ∈ (x, x + dx)) = f(x)dx

2.18.1 Solutions to the balance equations

• In principle we could solve the balance equations by “forward substitution”

– p_{0} is known

– j = 0 ⟹ p_{1} ⋮

– j = i : p_{0}, p_{1}, …, p_{i} ⟹ p_{i+1} but computationally impractical in general

• Define generating functions

p(z) = ∑_{i=0}^{∞} p_{i}z^{i}
r(z) = ∑_{i=0}^{∞} r_{i}z^{i}

Recap:

p′(z) = ∑_{i=1}^{∞} ip_{i}z^{i−1}
⟹ p′(1) = mean value of distribution {p_{j}|j ≥ 0}
p′′(z) = ∑_{i=2}^{∞}(i^{2} − i)p_{i}z^{i−2} ⟹ p′′(1) = M_{2} − M_{1}

• Multiply balance equations by z^{j} and sum:

p(z) = p_{0}r(z) + ∑_{j=0}^{∞} ∑_{i=1}^{j+1} p_{i}r_{j−i+1}z^{j}

= p_{0}r(z) + z^{−1} ∑_{i=0}^{∞} ∑_{j=0}^{∞} p_{i+1}z^{i+1}r_{j−i}z^{j−i}

where r_{k} = 0 for k < 0

= p_{0}r(z) + z^{−1} ∑_{i=0}^{∞} p_{i+1}z^{i+1} ∑_{j=0}^{∞} r_{j−i}z^{j−i}
= p_{0}r(z) + z^{−1}(p(z) − p_{0})r(z)

2.18.2 Solution for p(z) and the Pollaczek-Khinchine result

p(z) = \frac{p_{0}(1 − z)r(z)}{r(z) − z}
where r(z) = ∫_{0}^{∞} ∑_{k=0}^{∞} \frac{(λxz)^{k}}{k!} e^{−λx}f(x)dx
= ∫_{0}^{∞} e^{−λx(1−z)}f(x)dx
= f^{∗}(λ − λz)

Laplace transform of f at the point λ − λz Recap: Laplace transform f^{∗} of f defined by

f^{∗}(s) = ∫_{0}^{∞} e^{−sx}f(x)dx
so that \frac{d^{n}}{ds^{n}} f^{∗}(s) = ∫_{0}^{∞}(−x)^{n}e^{−sx}f(x)dx
⟹ \frac{d^{n}f^{∗}(s)}{ds^{n}} |_{s=0} = (−1)^{n}M_{n} n^{th} moment of f(x)

E.g. f^{∗}(0) = 1, −f^{∗′}(0) = mean service time = 1/μ. Thus,

p(z) = \frac{(1 − ρ)(1 − z)f^{∗}(λ − λz)}{f^{∗}(λ − λz) − z}

p′(1) ⟹ P-K formula … 2.18.3 Derivation of P-K formula

\frac{p′}{1 − ρ} = \frac{(f^{∗} − z)(−λ(1 − z)f^{∗′} − f^{∗}) + (1 − z)f^{∗}(1 + λf^{∗′})}{(f^{∗} − z)^{2}}

where f^{∗} = f^{∗}(λ − λz) etc.

• When z = 1, both denominator and nominator vanish ( ⟹ f^{∗}(λ − λ.1) = f^{∗}(0) = 1)

• L’Hopital rule ⟹

\frac{p′(1)}{1 − ρ} = lim_{z→1} \{\frac{λ((1 − 2z)f^{∗′} − λz(1 − z)f^{∗′}) − λf^{∗′} + 2λf^{∗}f^{∗′}}{−2(f^{∗} − z)(1 + λf^{∗′})} \}

• Again, when z = 1, both denominator and nominator vanish • L’Hopital rule now gives

\frac{p′(1)}{1 − ρ} = \frac{λ(−2f^{∗′}(0) + λf^{∗′′}(0) − 2λf^{∗′}(0)^{2})}{2(1 + λf^{∗′}(0))^{2}}
(since f^{∗}(0) = 1)
= \frac{λ^{2}M_{2} + 2(λ/μ)(1 − (λ/μ))}{2(1 − (λ/μ))^{2}} P-K formula!
(since f^{∗′}(0) = 1/μ)

• Hard work compared to previous derivation! But in principle we could obtain any moment (“well known” result for variance of queue length)

2.18.4 Waiting time distribution

• The tasks left in an M/G/1 queue on departure of a given task are

precisely those which arrived during its waiting time

⟹ p_{j} = ∫_{0}^{∞} \frac{(λx)^{j}}{j!} e^{−λx}h(x)dx

because P (j arrivals|waiting time = x) = \frac{(λx)^{j}}{j!} e^{−λx}

P (waiting time ∈ (x, x + dx)) = h(x)dx
⟹ p(z) = h^{∗}(λ − λz)

by the same reasoning as before.

• Laplace transform of waiting time distribution is therefore (let z = \frac{λ−s}{λ})

h^{∗}(s) = p(\frac{λ − s}{λ}) = \frac{(1 − ρ)sf^{∗}(s)}{λf^{∗}(s) − λ + s}

• Exercise: Verify Little’s Law for the M/G/1 queue:

p′(1) = −λh^{∗′}(0).

2.19 Example: Paging fixed head disk

Figure 16: Paging fixed head disk.

Assumptions • Tasks in the track queue require random sector

• arrivals to an empty queue always find the head at the beginning of a sector (as with the next task in the queue after a service completion)

⟹ service times may be \frac{1}{nR} (requires next sector)
\frac{2}{nR} (next but one)
⋮
\frac{1}{R} (the one just gone)

(strictly, for arrivals to an empty queue, service times have continuous sample space [1/nR, 1/nR + 1/R))

• Mean service time, μ^{−1} = ∑_{j=1}^{n} \frac{1}{n} \frac{j}{nR} = \frac{n+1}{2nR}

• Second moment, M_{2} = ∑_{j=1}^{n} \frac{1}{n}(\frac{j}{nR})^{2} = \frac{(n+1)(2n+1)}{6n^{2}R^{2}} 2.19.1 Solution and asymptotic behaviour

• Load is ρ = λ/μ = \frac{λ(n+1)}{2nR} ⟹ λ < \frac{2nR}{n+1} if drum track is not to be saturated

• Mean queue length, L = ρ + \frac{λ^{2}(n+1)(2n+1)}{12n^{2}R^{2}(1−ρ)}

• As n → ∞, i.e. many sectors on track

– assumption about arrivals to an empty queue becomes exact (large n ⟹ good approximation)

– ρ → \frac{λ}{2R}

– L → \frac{λ}{2R} + \frac{λ^{2}}{3R(2R−λ)}

3 Queueing Networks

3.1 Introduction

• Collection of servers/queues interconnected according to some topology

Figure 17: Network example • Servers may be

– processing elements in a computer, e.g. CPU I/O devices

– stations/nodes in a communication network (may be widely separated

geographically)

• Topology represents the possible routes taken by tasks through the system

• May be several different classes of tasks (multi-class network)

– different service requirements at each node

– different routing behaviours

– more complex notation, but straightforward generalisation of the single-class network in principle

– we will consider only the single class case

3.2 Types of network

• Open: at least one arc coming from the outside and at least one going out

– must be at least one of each type or else the network would be saturated or null (empty in the steady state)

– e.g. the example above

• Closed: no external (incoming or outgoing) arc – constant network population of tasks forever circulating – e.g. the example above with the external arcs removed from

nodes 1 and 4

• Mixed: multi-class model which is open with respect to some classes and closed with respect to others – e.g. in the example above a class whose tasks only ever alternated between nodes 2 and 4 would be closed, whereas a class using all nodes would be open

3.3 Types of server

• Server defined by its service time distribution (we assume exponential but can be general for non-FCFS disciplines) and its queueing discipline (for each class)

– FCFS (FIFO)

– LCFS (LIFO)

– IS (i.e. a delay node: no queueing)

– PS (Processor sharing: service shared equally amongst all

tasks in the queue)

• Similar results for queue length probabilities (in S.S.) for all

4 Open networks (single class)

• Notation:

M servers, 1, 2, …, M with FCFS discipline and exponential service times, mean \frac{1}{μ_{i}(n_{i})}, when queue length is n_{i} (1 ≤ i ≤ M)

– state dependent service rates to a limited extent

– μ_{i}(n_{j}) for i ≠ j ⟹ blocking: rate at one server depends on the state of another, e.g. rate → 0 when finite queue at next is full

• External Poisson arrivals into node i, rate γ_{i}, (1 ≤ i ≤ M) (= 0 if no arrivals)

• Routing probability matrix Q = (q_{ij}|1 ≤ i ≤ M)

– q_{ij} = probability that on leaving node i a task goes to node j independently of past history – q_{i0} = 1 − ∑_{j=1}^{M} q_{ij} = probability of external departure from

node i

– at least one q_{i0} > 0, i.e. at least one row of Q sums to less

than 1

• State space of network S = {(n_{1}, …, n_{M})}|n_{i} ≥ 0} – queue length vector random variable is (N_{1}, …, N_{M})

– p(\underline{n}) = p(n_{1}, …, n_{M}) = P (N_{1} = n_{1}, …, N_{M} = n_{M})

4.1 Traffic equations

• Determine mean arrival rates λ_{i} to each node i in the network

Figure 18: Traffic equations

• In the steady state, λ_{i} = γ_{i} + ∑_{j=1}^{M} λ_{j}q_{ji} for (1 ≤ i ≤ M) ⟹ unique solution for {λ_{i}} (because of properties of Q)

– independent of Poisson assumption since we are only considering mean numbers of arrivals in unit time

– assumes only the existence of a steady state

• Example

Figure 19: Traffic example.

λ_{1} = γ + λ_{1}q ⟹ λ_{1} = \frac{γ}{1 − q}

• Arrivals to a node are not in general Poisson, e.g. this simple example. If there is no feedback then all arrival processes are Poisson because

1. departure process of M/M/1 queue is Poisson

2. superposition of independent Poisson processes is Poisson • Similarly, let R_{i} be the average interval between a task’s arrival

at server i and its departure from the network

– R_{i} is the “average remaining sojourn time” –

R_{i} = W_{i} + ∑_{j=1}^{M} q_{ij}R_{j}

4.2 Steady state queue length probabilities

Jackson’s theorem

1. The number of tasks at any server is independent of the number of tasks at every other server in the steady state

2. Node i behaves as if it were subjected to Poisson arrivals, rate λ_{i} (1 ≤ i ≤ M)

• Thus, even though arrivals at each node are not, in general, Poisson, we can treat the system as if it were a collection of M independent M/M/1 queues

⟹ p(n_{1}, …, n_{M}) ∝ ∏_{i=1}^{M} \{\frac{λ_{i}^{n_{i}}}{∏_{j=1}^{n_{i}} μ_{i}(j)}\}

where μ_{i}(j) is the rate of server i when the queue length is j • If service rates are constant, μ_{i},

p(\underline{n}) ≈ ∏_{i=1}^{M} ρ_{i}^{n_{i}} = ∏_{i=1}^{M}(1 − ρ_{i})ρ_{i}^{n_{i}}

where ρ_{i} = \frac{λ_{i}}{μ_{i}}

• p(\underline{n}) → usual performance measures such as mean queue lengths, utilisations, throughput by standard methods – mean waiting times by Little’s result

N.B. The normalising constant for \{p(\underline{n})|\underline{n} ∈ S\} is not shown for the general case: it is the product of those for the M/M/1 queues.

4.3 Mean Value analysis

• Can exploit Jackson’s theorem directly, together with Little’s result, if only \underline{average} quantities are required

– values for mean queue lengths L_{i} are those for isolated M/M/1 queues with arrival rates λ_{i} (1 ≤ i ≤ M)

– assuming constant service rates μ_{i}

L_{i} = \frac{ρ_{i}}{1 − ρ_{i}} for 1 ≤ i ≤ M

(average number of tasks at node i)

– total average number of tasks in network

L = ∑_{i=1}^{M} L_{i} = ∑_{i=1}^{M} \frac{ρ_{i}}{1 − ρ_{i}}

• Waiting times

– Average waiting time in the network, W = L/γ by Little’s result where γ = ∑_{i=1}^{M} γ_{i} is the total arrival rate

– Average time spent at node i during each visit

W_{i} = L_{i}/λ_{i} = \frac{1}{μ_{i}(1 − ρ_{i})}

– Average time spent queueing on a visit to node i

W_{Qi} = L_{Qi}/λ_{i} = \frac{ρ_{i}}{μ_{i}(1 − ρ_{i})}

4.4 An alternative formulation

• Let v_{i} be the average number of visits made by a task to server i γv_{i} = average number of arrivals to node i in unit time = λ_{i} where γ is the average number of arrivals to the whole network in unit time and v_{i} the average number of visits a given arrival makes to node i

v_{i} = \frac{λ_{i}}{γ} (1 ≤ i ≤ M)

• Let D_{i} be the total average service demand on node i from one

task

D_{i} = \frac{v_{i}}{μ_{i}} = \frac{ρ_{i}}{γ}

ρ_{i} = γD_{i} = average work for node i arriving from outside the network in unit time

• Often specify a queueing network directly in terms of {D_{i}|1 ≤ i ≤ M} and γ; then there is no need to solve the traffic equations •

L_{i} = \frac{ρ_{i}}{1 − ρ_{i}} = \frac{γD_{i}}{1 − γD_{i}}

L and W as before

• Let B_{i} = total average time a task spends at node i

B_{i} = v_{i}W_{i} = \frac{v_{i}}{μ_{i}(1 − ρ_{i})} = \frac{D_{i}}{1 − γD_{i}}

alternatively apply Little’s result to node i with the external arrival process directly

B_{i} = \frac{L_{i}}{γ} = \frac{D_{i}}{1 − γD_{i}}

• However, D_{i} and γ cannot be used to determine μ_{i} and hence neither W_{i} nor R_{i}

• Specification for delay nodes (IS) i – L_{i} = ρ_{i} = γD_{i}

– B_{i} = D_{i} (no queueing)

– W_{i} = 1/μ_{i}

– D_{i} = v_{i}/μ_{i} (as for any work conserving discipline also)

– service time distribution arbitrary

4.5 Distribution of time delays

• Even though arrivals at each node are not, in general, Poisson, the Random Observer Property still holds: waiting time distribution at node i is exponential, parameter μ_{i} − λ_{i} again as expected from Jackson’s theorem.

• Networks with no overtaking (“tree-like” networks) are easy to solve for time delay distributions:

Figure 20: A network with no overtaking.

– sojourn time on any route is the sum of independent, exponential random variables

– this argument is independent of Jackson’s theorem and one

proof uses the idea of reversibility of the M/M/1 queue

• time delay distribution is a convolution of exponentials, e.g. f_{1} ⋆ f_{2} ⋆ f_{3} for route r where f_{i}(t) = (μ_{i} − λ_{i})e^{−(μ_{i}−λ_{i})t} for i = 1, 2, 3.

4.6 Time delays in general networks

• mean sojourn time for any route is always easy because the mean of a sum of random variables is equal to the sum of the means of those random variables, whether or not they are independent

• in networks with overtaking, the distribution of route sojourn times remains an open problem. For example, in the network

Figure 21: A network with overtaking.

– sojourn time distribution on route 1 → 3 is the convolution of 2 exponentials

– sojourn time distribution on route 1 → 2 → 3 is not the convolution of 3 exponentials because the queue length faced at node 3 upon arrival depends on the number of departures

from node 1 during the sojourn time at node 2.

– The Random Observer Property is not applicable since the arrival to node 3 is not random when conditioned on the previous arrival at node 1.

• Jackson’s theorem does not apply because it is concerned only with steady state probabilities, i.e. the asymptotic behaviour of p_{t}(\underline{n}) at the single point in time t as t → ∞.

• Subject of many research papers.

5 Closed Queueing Networks

• No external arrivals or departures (no γ_{i} terms).

• Routing probabilities satisfy

∑_{j=1}^{M} q_{ij} = 1 for 1 ≤ i ≤ M

• State space S = {(n_{1}, …, n_{M})|n_{i} ≥ 0, ∑_{j=1}^{M} n_{j} = K} for population K

– |S| = # of ways of putting K balls into M bags = \binom{K+M−1}{M−1} – finiteness of S → steady state always exists • Traffic equations are

λ_{i} = ∑_{j=1}^{M} λ_{j}q_{ji} for 1 ≤ i ≤ M

– homogeneous linear equations with an infinity of solutions which differ by a multiplicative factor (because |I − Q| = 0 since rows all sum to zero)

– let (e_{1}, …, e_{M}) be any non-zero solution (typically chosen by fixing one e_{i} to a convenient value, like 1)

therefore e_{i} ∝ arrival rate λ_{i}, i.e. e_{i} = cλ_{i} x_{i} = \frac{e_{i}}{μ_{i}} ∝ load = ρ_{i}, i.e. x_{i} = cρ_{i}

5.1 Steady state probability distribution for S

• Jackson’s theorem extends to closed networks which have a product form solution

p(n_{1}, …, n_{M}) = \frac{1}{G} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}} μ_{i}(j)} where ∑_{i=1}^{M} n_{i} = K.  (1)

where μ_{i}(j) is the service rate of the exponential server i when its queue length is j.

• G is the normalising constant of the network

G = ∑_{n n n∈S} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}} μ_{i}(j)}  (2)

not easy to compute (see later)

• Prove the result by using the network’s steady state balance equations:

Total flux out of state n n n = p(n n n) ∑_{i=1}^{M} μ_{i}(n_{i})ϵ(n_{i})
= Total flux into state n n n : ∑_{i,j}n n n_{i}^{j} → n n n
= ∑_{i=1}^{M} ∑_{j=1}^{M} p(n n n_{i}^{j})ϵ(n_{i})μ_{j}((n n n_{i}^{j})_{j})q_{ji}

where ϵ(n) = \begin{cases}0 if n = 0 \\ 1 if n > 0 \end{cases}

n n n_{i}^{j} = \begin{cases}(n_{1}, …, n_{i} − 1, …, n_{j} + 1, …, n_{M}) if i ≠ j \\ n n n_{i}^{i} = n n n otherwise \end{cases}

note that (n n n_{i}^{j})_{j} = \begin{cases}n_{j} + 1 if i ≠ j \\ n_{i} otherwise \end{cases} • Try

p(n_{1}, …, n_{M}) = \frac{1}{G} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}}μ_{i}(j)} where ∑_{i=1} n_{i} = K.  (3)

Then require

\frac{1}{G} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}}μ_{i}(j)} ∑_{i} μ_{i}(n_{i})ϵ(n_{i}) = \frac{1}{G} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}}μ_{i}(j)} ∑_{i,j:i=j} μ_{i}(n_{i})ϵ(n_{i})q_{ji}

+\frac{1}{G} ∏_{i=1}^{M} \frac{e_{i}^{n_{i}}}{∏_{j=1}^{n_{i}}μ_{i}(j)} ×

∑_{i,j:i≠j} \frac{e_{j}}{e_{i}} \frac{μ_{i}(n_{i})}{μ_{j}(n_{j} + 1)}ϵ(n_{i})μ_{j}(n_{j} + 1)q_{ji}

i.e.

∑_{i} μ_{i}(n_{i})ϵ(n_{i}) = ∑_{i} μ_{i}(n_{i})ϵ(n_{i})\{\frac{∑_{j} e_{j}q_{ji}}{e_{i}} \}

OK if eee satisfies the traffic equations.

• Note that if eee′ = ceee is another solution to the traffic equations, the corresponding probabilities p′(n n n) and G′ are

p′(n n n) = \frac{1}{G′} Gc^{∑ n_{i}}p(n n n) = \frac{Gc^{K}}{G′} p(n n n)

G′ = c^{K}G = ∑_{n n n∈S} Gc^{∑ n_{i}}p(n n n)

and therefore p′(n n n) = p(n n n). This confirms the arbitrariness of eee up to a multiplicative factor.

5.2 Computation of the normalising constant

• We consider only the case of servers with constant service rates to get an efficient algorithm.

• There are also algorithms for networks with servers having state dependent service rates, e.g. the convolution algorithm.

• Less efficient but important since the alternative MVA algorithm also requires constant rates.

• Define G = g(K, M) where

g(n, m) = ∑_{\underline{n}∈S(n,m)} ∏_{i=1}^{m} x_{i}^{n_{i}}

where S(n, m) = \{(n_{1}, …, n_{m})|n_{i} ≥ 0, ∑_{i=1}^{m} n_{i} = n\} and x_{i} = \frac{e_{i}}{μ_{i}} (1 ≤ i ≤ m).

– state space for subnetwork of nodes 1, 2, …, m and population n.

• For n, m > 0

g(n, m) = ∑_{\underline{n}∈S(n,m),n_{m}=0} ∏_{i=1}^{m} x_{i}^{n_{i}} + ∑_{\underline{n}∈S(n,m),n_{m}>0} ∏_{i=1}^{m} x_{i}^{n_{i}}

= ∑_{\underline{n}∈S(n,m−1)} ∏_{i=1}^{m−1} x_{i}^{n_{i}} + x_{m} ∑_{\begin{matrix}k_{i}=n_{i}(i≠m) \\ k_{m}=n_{m}−1 \\ \underline{n}∈S(n,m) \end{matrix}} ∏_{i=1}^{m} x_{i}^{k_{i}}

= g(n, m − 1) + x_{m}g(n − 1, m)

because \{\underline{k}|k_{i} ≥ 0; ∑_{i=1}^{m} k_{i} = n − 1\} = S(n − 1, m).

• Boundary conditions:

g(0, m) = 1 for m > 0
g(n, 0) = 0 for n ≥ 0

• Note

g(0, m) = ∑_{\underline{n}=(0,...,0)} ∏_{i=1}^{m} x_{i}^{0} = 1

and

g(n, 1) = x_{1}g(n − 1, 1) = x_{1}^{n}

5.3 Marginal queue length probabilities and performance measures

• Although p(\underline{k}) ∝ ∏ p_{i}(k_{i}) it is not the case that P (N_{i} = k_{i}) = p_{i}(k_{i}), as in the open networks. The use of M/M/1 factors is just a convenient mathematical device, there is no probabilistic interpretation.

• Probability that a server is idle (= 1 − utilisation)

P (N_{M} = 0) = \frac{1}{g(K, M)} ∑_{\underline{n}∈S(n,m),n_{m}=0} ∏_{i=1}^{M−1} x_{i}^{n_{i}} = \frac{g(K, M − 1)}{g(K, M)}.

In general

P (N_{i} = 0) = \frac{G_{i}(K)}{G(K)} for 1 ≤ i ≤ M

where G(K) = g(K, M) and G_{i}(k) is the normalising constant for the same network with the server i removed and population k

G_{i}(k) = ∑_{\underline{n}∈S(k,M−1)} ∏_{j=1}^{M−1} y_{j}^{n_{j}}

where

y_{j} = \begin{cases}x_{j} for 1 ≤ j < i \\ x_{j+1} for i ≤ j ≤ M − 1 \end{cases}

• utilisation of node i

U_{i}(K) = 1 − \frac{G_{i}(K)}{G(K)}

5.4 Alternative Formulation: Cumulative Probabilities

• For 1 ≤ k ≤ K and 1 ≤ i ≤ M

P (N_{i} ≥ k) = ∑_{\underline{n}∈S(K,M),n_{i}≥k} ∏_{j=1}^{M} \frac{x_{j}^{n_{j}}}{G(K)}
= \frac{x_{i}^{k}}{G(K)} ∑_{\begin{matrix}m_{i}=n_{i}−k \\ n_{i}≥k m_{j}=n_{j}(j≠i) \\ \underline{n}∈S(K,M) \end{matrix}} ∏_{j=1}^{M} x_{j}^{m_{j}}

= \frac{x_{i}^{k}}{G(K)} ∑_{\underline{m}∈S(K−k,M)} ∏_{j=1}^{M} x_{j}^{m_{j}}
= x_{i}^{k} \frac{G(K − k)}{G(K)}.

Therefore the utilisation is given by

U_{i} = x_{i} \frac{G(K − 1)}{G(K)}

• Equating two expressions for U_{i} yields the recurrence relation for g(k, m) previously

• Throughput of server i,

T_{i}(k) = μ_{i}U_{i}(k) = e_{i} \frac{G(K − 1)}{G(K)}

proportional to visitation rate as expected.

• Queue length distribution at server i is P (N_{i} = k) = p_{i}(k) for 0 ≤ k ≤ K and 1 ≤ i ≤ M

p_{i}(k) = P (N_{i} ≥ k) − P (N_{i} ≥ k + 1)
= x_{i}^{k} \frac{G(K − k) − x_{i}G(K − k − 1)}{G(K)}.

where G(−1) = 0 by definition.

• Notice that the previous formulation gives a more concise formulation for p_{i}(k)

p_{i}(k) = \frac{1}{G(K)} ∑_{\underline{n}∈S(K,M),n_{i}=k} ∏_{j=1}^{M} x_{j}^{n_{j}}
= \frac{x_{i}^{k}}{G(K)} ∑_{\underline{n}∈S(K−k,M),n_{i}=0} ∏_{j=1}^{M} x_{j}^{n_{j}}
= x_{i}^{k} \frac{G_{i}(K − k)}{G(K)}

for 0 ≤ k ≤ K and 1 ≤ i ≤ M. This is a generalisation of the result obtained for U_{i}(k).

• Mean queue length at server i, 1 ≤ i ≤ M, L_{i}(k)

L_{i}(K) = ∑_{k=1}^{K} kP (N_{i} = k)

= ∑_{k=1}^{K} P (N_{i} ≥ k)
= \frac{∑_{k=1}^{K} x_{i}^{k}G(K − k)}{G(K)}.

5.5 Equivalent open networks and the use of mean value analysis

• Consider an irreducible network – one in which every arc is traversed within finite time from any given time with probability 1

Figure 22: Equivalent open network.

• i.e. a network represented by an irreducible positive recurrent Markov process (finite state space)

• we introduce a node, 0, in one of the arcs and replace arc a by arc a_{1}, node 0 and arc a_{2}

– Source of a_{1} is source of a

– destination of a_{2} is destination of a

• Whenever a task arrives at node 0 (along arc a_{1}), it departs from the network and is immediately replaced by a stochastically identical task which leaves node 0 along arc a_{2}

• Define the network’s throughput, T, to be the average rate at which tasks pass along arc a in the steady state.

– i.e. T is mean number of tasks traversing a in unit time.

– One can choose any arc in an irreducible network.

5.6 Visitation rates and application of Little’s result

• Let the visitation rate be v_{i} and the average arrival rate be λ_{i} for node i, 1 ≤ i ≤ M, then λ_{i} = T v_{i} where T is the external arrival rate.

• The set {v_{i}|1 ≤ i ≤ M} satisfies the traffic equations, as we could have derived directly by a similar argument.

• Suppose arc a connects node α to node β in the closed network 1 ≤ α, β ≤ M, then v_{0} = v_{α}q_{αβ} because all traffic from α to β goes through node 0 in the open network.

• But every task enters node 0 exactly once, hence v_{α} = \frac{1}{q_{αβ}} since v_{0} = 1. This determines {v_{i}|1 ≤ i ≤ M} uniquely.

• Little’s result now yields

L_{i} = λ_{i}W_{i} = T v_{i}W_{i}

∑_{i=1}^{M} L_{i} = K = T ∑_{i=1}^{M} v_{i}W_{i}

since the sum of all queue lengths is exactly K in the closed network

⟹ T = \frac{K}{∑_{i=1}^{M} v_{i}W_{i}}

5.7 Mean waiting times

•

W_{i} = \frac{1}{μ_{i}} [1 + Y_{i}]

where the first term is the arriving task’s mean service time and Y_{i} is the mean number of tasks seen by new arrivals at server i.

• For an IS (delay) server W_{i} = \frac{1}{μ_{i}}, otherwise …

• Do not have the random observer property

– number of tasks seen on arrival does not have the same steady state distribution as the queue length since K tasks are seen with probability 0. (arrival cannot “see itself”)

– do not have Y_{i} = L − 1 as in open networks • Do have the analogous Task (or Job) Observer Property:

The state of a closed queueing network in equilibrium seen by a new arrival at any node has the same distribution as that of the state of the same network in equilibrium with the arriving task removed (i.e. with population K − 1)

– arriving task behaves as a random observer in a network with population reduced by one

– intuitively appealing since the “one” is the task itself

– but requires a lengthy proof (omitted)

5.8 Recurrence relations for throughput, mean waiting times and mean queue length

• Task observer property yields

Y_{i}(K) = L_{i}(K − 1)

for 1 ≤ i ≤ M, K > 0.

• Hence we obtain the recurrence relations

W_{i}(K) = \frac{1}{μ_{i}} [1 + L_{i}(K − 1)]
T (K) = \frac{K}{∑_{i=1}^{M} v_{i}W_{i}(K)}
L_{i}(K) = v_{i}T (K)W_{i}(K)

for 1 ≤ i ≤ M, K > 0 and the initial condition L_{i}(0) = 0 • T (K), W_{i}(K), L_{i}(K) easily computed by a simple iteration

\{L_{i}(K − 1)\} →  \underbrace{\{W_{i}(K)\} → T (K)}
→ {L_{i}(K)} → …

• 2M + 1 quantities computed each time round the loop

5.9 Alternative formulation

• Total average time spent at node i when population is K

B_{i}(K) = v_{i}W_{i}(K)

for 1 ≤ i ≤ M

• Total average service time (demand) a task requires from node i

D_{i} = \frac{v_{i}}{μ_{i}}

for 1 ≤ i ≤ M independent of population K.

• Therefore

B_{i}(K) = D_{i}[1 + L_{i}(K − 1)]
T (K) = \frac{K}{∑_{i=1}^{M} B_{i}(K)}
L_{i}(K) = T (K)B_{i}(K)

for 1 ≤ i ≤ M

• Total average time in network spent by a task

W (K) = ∑_{i=1}^{M} v_{i}W_{i}(K) = ∑_{i=1}^{M} B_{i}(K) = \frac{K}{T (K)}

as expected by Little’s law

• Utilisation of node i

U_{i}(K) = \frac{λ_{i}}{μ_{i}} = T (K)\frac{v_{i}}{μ_{i}} = T (K)D_{i} ≤ 1

which implies

T (K) ≤ min_{1≤i≤M} \frac{1}{D_{i}}

which implies the maximum throughput is dictated by a bottleneck server (or servers) - that (those) with maximum D_{i}

5.10 A faster approximate algorithm

• Algorithms given above need to evaluate 2M + 1 quantities for each population between 1 and K

• Would be faster if we could relate Y_{i}(K) to L_{i}(K) rather than L_{i}(K − 1), which implies that we do not need to worry about populations less than K

•

Y_{i}(K) = \frac{K − 1}{K}L_{i}(K)

is a good approximation, exact for K = 1 and correct asymptotic behaviour as K → ∞ (exercise)

• then

B_{i}(K) = D_{i}[1 + \frac{K − 1}{K}T (K)B_{i}(K)]

•

B_{i}(K) = \frac{D_{i}}{1 − \frac{K−1}{K}D_{i}T (K)}

• Thus we obtain the fixed point equation

T (K) = f(T (K))

where

f(x) = \frac{K}{∑{M \atop i=1} \frac{D_{i}}{1− \frac{K−1}{K} D_{i}x}}

there are many numerical methods to solve such equations

5.11 Example: Multiprogramming computer system

Figure 23: A multiprogrammed computer.

• Insert node 0 in route from CPU back to itself, throughput is the rate at which tasks are interrupted at CPU node, this is an arbitrary choice • visitation rates

v_{1} = a_{1}v_{1} + ∑_{j=2}^{M} v_{j}

v_{i} = a_{i}v_{1} for i ≥ 2 v_{1} = \frac{1}{a_{1}} with choice of position of node 0

therefore

v_{i} = \frac{a_{i}}{a_{1}} for i ≥ 2

• Sanity check: is the first equation is satisfied?

D_{i} = \frac{a_{i}}{a_{1}μ_{i}} for i ≥ 2

D_{1} = \frac{1}{a_{1}μ_{1}}

therefore T (K) follows by solving recurrence relations • total CPU throughput = \frac{T (K)}{a_{1}} (fraction a_{1} recycles)

5.12 Application: A batch system with virtual memory

• Most medium-large computer systems use virtual memory

• It is well-known that above a certain degree of multiprogramming performance deteriorates rapidly

• Important questions are

– How does the throughput and turnaround time vary with the degree of multiprogramming

– What is the threshold below which to keep the degree of multiprogramming?

5.12.1 Representation of paging

• Suppose node 2 is the paging device (e.g. fast disk)

– assume dedicated to paging

– easy to include non-paging I/O also

• We aim to determine the service demand of a task at node 2, D_{2}, from tasks’ average paging behaviour

– use results from ’70s working set theory

– consider the page fault rate for varying amounts of main store

allocated to a task

• Let the population be K

• paging behaviour will be represented by a lifetime function:

– h(x) = average CPU time between consecutive page faults when a task has x pages of memory

– h(0) ≈ 0 (the first instruction causes a fault)

– h(x) = C, the total CPU time of a task for x ≥ some constant value m, where m is the “size” of the task – h is an increasing function: the more memory a task has the

less frequent will be its page faults on average.

– Two possible types of lifetime functions:

Figure 24: Lifetime functions

– For (a) h(x) = \begin{cases}ax^{b} for x ≤ m \\ am^{b} = C for x ≥ m \end{cases} , b > 1

– For (b) h(x) = \frac{C}{1+(a/x)^{2}}

– Note that for (b) there is no m s.t. h(m) = C

• Let each task have P/K pages of memory of size P pages – average CPU time between faults = h(P/K)

– average number of faults during life of task = \frac{D_{1}}{h(P/K)}

– average time at node 2 per fault = \frac{1}{μ_{2}}

• Therefore average paging time of a task (from node 2) – D_{2} = H(K) = \frac{D_{1}}{μ_{2}h(P/K)}

– D_{2} = d_{2} + H(K) if average non-paging requirement of a task from node 2 is d_{2}

• As K → ∞, T (K) → 0 since T (K) ≤ min \frac{1}{D_{i}} and D_{2} → ∞

5.13 Solution

• We again use the alternative form of the MVA algorithm

• For population K and 1 ≤ k ≤ K

B_{i}(k) = D_{i}(K)[1 + L_{i}(k − 1)] (1 ≤ i ≤ M)
T (k) = \frac{k}{∑_{i=1}^{M} B_{i}(k)}
L_{i}(k) = T (k)B_{i}(k) (1 ≤ i ≤ M)

• Notice that only D_{2} is a function of K − D_{1} and D_{3} are constant • Computation for a range of populations requires 2 nested loops:

– outer loop for K = 1, 2, …, K_{max} – inner loop for k = 1, 2, …, K

– need new value for H(K) each time round the outer loop

5.14 Choice of lifetime function

• We assume (arbitrarily) the lifetime function

h(x) = \begin{cases}D_{1}(\frac{x}{10000})^{3.5}, x ≤ 10000 \\ D_{1} otherwise \end{cases}

for all tasks, i.e.

Figure 25: Lifetime function example.

5.15 Thrashing curves

Figure 26: Mean job processing time vs. number of jobs.

Figure 27: Throughput vs. number of Jobs.

190

5.16 Decomposition

• Separable queueing models are prone to break down in some situations: – There is usually a good model for small parts of any network

– Composing the bits can be hard unless the criteria for separability are (reasonably) met

• Ideally, we need a method to:

– Reduce complexity (breaking a large problem into smaller manageable ones)

– Provide approximate solutions where the necessary assumptions do not hold

• The most powerful general method is decomposition (sometimes called aggregation)

• The idea is to replace a subnetwork of a (complex) system with a single flow-equivalent server (FES)

Figure 28: Flow equivalent server.

• We exploit the fact that servers in separable networks may have state dependent service rates, i.e. μ_{n} for queue length n

• To find the required μ_{n}, we compute the “throughput”, τ_{n}, of the subnetwork when the population is n and set

μ_{n} = τ_{n}, n = 0, 1, …

• The throughput can be determined by any method, e.g. an explicit Markov model, standard queueing network algorithm (e.g. MVA), or even simulation

• The technique is analogous to Norton’s Theorem in electrical circuit theory.

5.17 Method

1. Identify the subnetwork to be aggregated

Figure 29: Flow equivalent server - step 1.

2. Short-circuit the rest of the network (i.e. use the same visitation rates as in the original subnetwork)

Figure 30: Flow equivalent server - step 2.

3. Compute the throughput τ_{n}, on the short-circuit arc for all populations 0, 1, …

Figure 31: Flow equivalent server - step 3.

4. Define a single FES with service rate μ_{n} = τ_{n}, n = 0, 1, …

5. Replace the subnetwork with the FES and re-solve

Figure 32: Flow equivalent server - step 5.

6. If necessary repeat the process (i.e. hierarchically)

7. Note: We can either aggregate the tricky part or aggregate the easy part leaving a smaller tricky network behind!

Figure 33: Flow equivalent server - trick.

197

5.18 Application: A multiprogramming system with virtual memory

• Let us now revisit the multiprogrammed virtual memory system, this time with terminals rather than batch processing:

Figure 34: Multiprogramming system with virtual memory • The average think time of each user is 30 seconds

• Q: How does the system throughput and response time vary with the number of terminals, K, and at what point does the system start to thrash?

• As users submit jobs, they increase the population at the computer system and consume memory

• The problem is that the performance of the computer subsystem depends on the number of jobs there

• But the number of jobs at the subsystem is governed by the number of terminals

• Specifically, the Disk 1 service rate depends on the population of the entire subnetwork: \underline{no simple (product-form) solution} Figure 35: Multiprogramming system with virtual memory - step 1 • In the batch model we computed previously the throughput,τ_{n},

when there were n batch jobs being processed

• We can thus aggregate the server subsystem into a flow-equivalent server whose service rate at population n is

μ_{n} = τ_{n}

• That is Figure 36: Multiprogramming system with virtual memory - FES • approximation because of lack of product-form solution • The resulting reduced network is a simple M/M/1 queue with

state dependent arrival and service rates:

λ_{n} = (K − n)λ
μ_{n} = τ_{n}

where 0 ≤ n ≤ K and where λ = 1/30 is the submission rate for a single terminal in the “think” state

• Let p_{n} be the equilibrium probability that there are n jobs at the subsystem (i.e. K − n users in “think” mode)

• The magic formula for the M/M/1 queue gives

p_{n} = \frac{(K − n + 1)λ}{μ_{n}} \frac{(K − n)λ}{μ_{n−1}} … \frac{Kλ}{μ_{1}}p_{0}
= λ^{n} \frac{K!}{(K − n)!} ∏_{i=1}^{n} \frac{1}{μ_{i}}

with the usual constraint that

p_{0} + p_{1} + ⋯ + p_{k} = 1

• The algorithm requires one loop to compute p_{0} and a further loop to find the p_{n}, 1 ≤ n ≤ K

• We are interested here in the throughput and mean response time for a given value of K

• The throughput is:

τ = p_{0}μ_{0} + p_{1}μ_{1} + ⋯ + p_{K}μ_{K}

• We next need to find the mean population of the subsystem:

L = 0 × p_{0} + 1 × p_{1} + ⋯ + K × p_{K}

• The mean waiting time then follows from Little’s law

W = L/τ

• With the same paging model as the batch system earlier, this is what happens to τ as we increase K

Figure 37: Throughput vs. number of terminals.

• The saturation point is clear! Beyond this the mean population of the computer subsystem is such that thrashing occurs

• Here is the behaviour of the mean waiting time as we increase W

Figure 38: Mean response time vs. number of terminals.

• And finally (for the record), here is L:

Figure 39: Central server population vs. number of terminals.

206

6 Markov Modulated Poisson Process (MMPP)

206-1

6.1 Introduction

Poisson process is a good model for many arrival streams • more short interarrival times than long

• superposition of many sparse independent renewal processes is asymptotically Poisson

• right intuitive properties given minimal information (i.e. arrival rate)

• renewal process, inter arrival times are i.i.d. But cannot model many characteristics seen in modern networks

• multiple traffic types with known switching pattern between types

• correlated traffic, i.e. non-zero correlation between interarrival times

• self-similarity

6.2 Definition of MMPP

The MMPP is a Poisson process with rate that depends on the state (called phase) of an independent continuous time finite Markov chain X(t) This is also known as doubly stochastic process.

• N is the number of phases

• λ_{k} is the rate of the Poisson process in phase k

• the arrival rates are often written as a diagonal matrix Λ_{ik} = δ_{ik}λ_{k}.

• so the probability of an arrival in a small interval of length h in phase k is λ_{k}h + o(h)

209 210

The modulating Markov chain X(t) is assumed irreducible and so has a steady state

• let the generator matrix (instantaneous transition rate matrix) be Q

• let the equilibrium probability of being in state k be

π_{k} = lim_{t→∞} P (X(t) = k)

Average arrival rate in steady state is then

\overline{λ} = ∑_{k=1}^{N} π_{k}λ_{k}

6.3 State at Arrival Instants

Important for response time distributions. MMPPs do not have the Random Observer Property. In a long period of time T at equilibrium

• expected time spent in state k is π_{k}T

• expected number of arrivals that see state k = λ_{k}π_{k}T

• total number of arrivals has mean \overline{λ}T So probability that an arrival sees state k in steady state is

π′_{k} = \frac{λ_{k}π_{k}}{\overline{λ}} .

6.4 The MMPP/M/1 queue

Suppose the queue has MMPP arrival process as defined above and server with exponential service times of constant mean μ^{−1}. This is a simple CTMC:

• easy to write down the balance equations

• apply steady state theorem

• conditions harder to derive rigorously but expect that the queue

has a steady state iff

\overline{λ} < μ

The CTMC has a 2-dimensional state space • phase of the MMPP horizontally (say)

• queue length vertically • infinite lattice strip for unbounded queue.

214

• What are the phases?

• Example: network traffic.

• Is it still a renewal process?

• Phases tend to be hidden.

• Limiting cases: all the same arrival rates, IPP • complicated BUT analytically tractable

• main aim: steady state prbabilities Let the steady state probability for phase k and queue length j be denoted by π_{jk} and let the vector

v_{j} = (π_{j1}, π_{j2}, …, π_{jN})

Balance equations are, for state (i, j + 1)

π_{j+1,i} (λ_{i} + μ + ∑_{k≠i} q_{ik}) = ∑_{k≠i} π_{j+1,k}q_{ki} + λ_{i}π_{j,i} + μπ_{j+2,i}

This may be written in matrix form as

v_{j}Λ + v_{j+1}(Q − Λ − μI) + μv_{j+2}I = 0

where I is the unit N × N matrix and Λ is the diagonal matrix with the arrival rates λ_{k} down the diagonal, i.e.

Λ = diag(λ_{1}, …, λ_{N}).

For states (i, 0) we get

v_{0}(Q − Λ) + μv_{1}I = 0

The normalising equation is

∑_{j=0}^{∞} v_{j} · (1, 1, …, 1) = 1

These equations give the unique equilibrium probabilities if \overline{λ} < μ

6.5 Exact solution methods

We have a matrix recurrence relation of the form v_{j}Q_{0} + v_{j+1}Q_{1} + v_{j+2}Q_{2} = 0 for j ≥ 0 and constant matrices Q_{0}, Q_{1}, Q_{2}. In our example above

Q_{0} = Λ

Q_{1} = Q − Λ − μI
Q_{2} = μI

Spectral Analysis (Chakka and Mitrani; see Mitrani’s book, last chapter [IM])

• Similar approach as linear differential or difference equations • Define Q(x) = Q_{0} + Q_{1}x + Q_{2}x^{2}

• find the eigenvalues ξ_{k} and eigenvectors e_{k} of Q(x)

• The eigenvalues are solutions of det[Q(x_{k})] = 0 where k = 1, … 2N.

• solution can then be shown to be, for a queue of unbounded capacity

π = ∑_{k=1}^{N} a_{k}ξ^{k}e_{k}

where the a_{k} are constants determined by the equations at queue length 0 and normalisation

• more complex result for queues of finite capacity Matrix Geometric Method

• Closely related to Spectral Analysis but a completely different approach

• Try a solution of the form v_{j} = M^{j}u for some matrix M and vector u

• Then solve

Q_{0} + MQ_{1} + M^{2}Q_{2} = 0

for M

• u from the other equations

6.6 Approximate solution methods

It often happens that phase changes are rare in comparison to arrivals and departures

• rates in Q-matrix << λ_{1}, …, λ_{N}, μ

• e.g. phase changes represent change of traffic type, such as data,

video, voice Often then a good approximation to use (an approximate) decomposition, cf. queueing networks. For each phase k, solve the M/M/1 queue assuming the arrival rate is constant, λ_{k}, giving equilibrium probability p_{j}^{(k)} for queue length j, 1 ≤ k ≤ N i.e. solve all the ‘columns’ in the 2-D state space. This can only work if every λ_{k} < μ Then solve the phase process for the equilibrium probability r_{k} of being in phase k, i.e. solve

r · Q = 0

Approximate the solution by

π_{jk} = p_{j}^{(k)}r_{k}.

6.7 Fitting MMPPs

MMPP can be fitted to observed data by matching:

• average arrival rate \overline{λ} (or mean interarrival time)

• higher moments of interarrival time (variance etc.)

• autocorrelation function (ACF)

• Hurst parameter, a measure of self-similarity Matching moments is easy but often gives a poor match on correlation, the main reason for using the MMPP in the first place! Can use ACF to model correlated traffic directly

• next slide

• computationally difficult and expensive

• possibly use spectral methods, cf. Fourier transforms Hurst parameter gives a good representation of ‘how correlated’ traffic is, but only contributes one parameter in the matching process. Better used to validate another matching process.

6.8 Autocorrelation function of the MMPP

The autocorrelation function at lag k ≥ 1 for the above MMPP is

ρ_{k} = \frac{π^{∗}R^{−2}Λ[\{I − eπ^{∗}R^{−1}Λ\}\{R^{−1}Λ\}^{k−1}]R^{−2}Λe}{2π^{∗}R^{−3}Λe − (π^{∗}R^{−2}Λe)^{2}}

where the matrix R = Λ − Q, e = (1, 1, …, 1) and π^{∗} = \frac{πΛ}{π.λ}. Autocorrelation function is easily calculated by the above formula, given the parameters of the MMPP. But the converse, to determine the parameters from the ACF, is hard!

• gives non-linear equations in several variables (the sought-after parameters)

• fixed point methods of solution tend to be unstable

• research area Real network traffic looks like this: This data was collected at Bellcore and used in Leland’s [?] paper on network traffic on an Ethernet. What does network traffic at IC look like??

This data was collected using the LINUX netstat command on OWL over several days. How does this compare to Poisson traffic?

Can MMPPs do better?

226 227

MMPP accounts for some of these limitations • models stochastically changing modes with different rates

• has non-zero autocorrelation which can be calculated

• integrates well into queueing models – the MMPP/M/1 queue

6.9 Interlude: self-similarity

• Self-similarity or long-range dependence are terms used to describe that statistical functions derived from a time series show a scaling behaviour which does not have a typical scale.

• Example: Look at previous network traffic, it looks “similar” at different resolutions. Other examples are e.g. clouds. This notion is related to fractals.

• How do you quantify “self-similarity mathematically?

• Many possibilities: Hurst parameter, log-variance plots, auto-correlation functions and power spectra.

• For a time series X(t) with zero mean the auto-correlation function at lag τ is defined as

C(τ) = lim_{T →∞} \frac{1}{2T} ∫_{−∞}^{∞} dtX(t + τ)X(t).

• For a time series of length n the auto-correlation function at lag k is defined as

c_{k} = \frac{1}{σ^{2}(n − k)} ∑(x_{i} − x̂)(x_{i+k} − x̂)

where x̂ is the mean and σ^{2} the variance.

• In fact, it is usually easier to work with the Fourier transform of the auto-correlation function. By the Wiener-Khintchine theorem, under certain assumptions, this is the same as the power spectrum (density) of the time series signal

S(f) = lim_{T →∞} \frac{1}{4πT} | ∫_{−T}^{T} dtX(t)e^{−i2πft}|^{2}.

• One is looking for power laws where the power spectrum S(f) behaves like S(f) ∝ 1/f^{α}, where f is the frequency.

• The exponent α turns out to be 0 for white noise (Poisson process) and 2 for a Brownian motion.

• From the relation of the power spectrum to the auto-correlation function

C(τ) ∝ |τ|^{α−1} for 0 < α < 1

• it also follows that an exponent α close to but smaller than 1 corresponds to long time correlations.

Examples: Bellcore

232

Owl

233

MMPP

234 235

Exercise

One of the simplest non-trivial examples of an MMPP is the interrupted Poisson process. In this case there is a 2-state modulation with rates r_{1} and and r_{2}. In the phase 1 the arrival rate is λ in phase 2 the arrivale rate is 0. The service rate is μ in both phases.

a) Draw a diagram of the state space with the transition rates labelled.

Someone hands you inter-arrival times of a point process. You know that the process is caused by 2 Poisson processes. Can you tell whether it is a simple superposition or an example of an MMPP

a) if the events are labelled

b) if the events are not labelled?

Is there any point in using MMPPs even if the phases are not identified by some intuitive sources? What is the advantage of MMPPs over G/G/1 queues?

References

[IM] Isi Mitrani, Probabilistic Modelling, CUP 1998, ISBN 0 521 58530 9