Course 336 - Performance Analysis

Outline answers to exam questions

1994

1

a	8 marks
Jackson's Theorem:  Bookwork.
A node's visitation rate is (proportional to) the expected number of arrivals to the node in unit time.
For node i, total incoming visitation rate is  Sj ejpji  and so in equilibrium,  ei = S ejpji. 

b i)	2 marks
Immediate from product form of Jackson's Theorem which involves factors of the form ei/mi

b ii)	3 marks
Ball in bag argument:  no. of ways of arranging M–1 identical partitions and K identical balls along a bi-infinite line - M+K–1 objects in all.

b iii)	3 marks
Server 1 idle means K customers to be allocated to a subnetwork of M–1 servers.  Hence replace M by M–1 in part ii)

b iv)	4 marks
Probability server 1 idle = sum of probabilities of states in which there is no customer at server 1.  Each state has probability  1/{result of ii}, so idle probability is {result of iii}/ {result of ii} =  M–1 / M+K–1.  Utilisation is 1 – idle probability.

2

a	10 marks
	s(t)  =  C t f(t)	for some C and normalisation gives
	1  =  C i(0,∞,t f(t) dt)  =  C m  and so   C = 1/m.
By the Law of Total Probability, residual life (R) density, r, is given by

	r(t)  =  i(t,∞,P´(R≤t | S=y) s(y) dy)
where S is the length of an observed interval.  (Less formal argument will do).

		=  i(t,∞,(1/y) (y f(y))/m dy)  =  [1 – F(t)] / m
If arrivals occur every second, m=1 and F(t) = 0 if t<1, = 1  if t≥1.  Thus 
	r(t)  =  1  if t<1,  = 0   if t≥1
i.e. uniformly distributed over [0,1).

b	10 marks
I	Derive a Markov process to represent the state transitions of each cache line in a processor, processors being assumed independent (not realistic in general for typical memory access patterns).  Find the equilibrium probability for each state - inexpensive as there will only be a small state space.  For each memory access type (which occurs with a given parameterised probabilty) in each line state (probability just calculated) determine the load generated on the bus.  Hence compute the mean delay associated with each access type.  Utilisation is then the ratio mean inter-access time :: mean inter-access time + mean delay.  (Inter-access time is time spent processing.)

3

a	10 marks
Waiting time is 1 service time (the tagged customer) + (n–1) service times (the queueing customers) + 1 residual service time (the customer in service).  But residual service time is identical to a full service time for the exponential distribution.  Thus (n+1) service times in all.

By the Random Observer Property, the queue length seen by an arrival has the same distribution as the steady state distribution, i.e. (1–r)rn.  Thus, unconditional waiting time distribution is
		isu(i=0,∞,sup2( )sdo2( ))dba6()(1–r)rn  m f((mt)n,n!) e–mt   =  (m–l)e–mt  isu(i=0,∞,sup2( )sdo2( ))dba6()f((lt)n,n!)   =  (m–l)e–(m–l)t  

b i)	4 marks
Convolution of the exponential with itself, i.e. Erlang-2 density with parameter m–l, viz
(m–l)2t e–(m–l)t.

b ii)	6 marks
Let T1 and T2 be the times to completion for the task in queue 1 and queue 2 respectively.  Then each is exponentially distributed with parameter m.  Thus the probsbility that the task in queue 1 finishes first is:
		P(T1<T2)  =  i(0,∞, P(T1<t)mes(–mt)dt)  =  i(0,∞, (1–es(–mt))mes(–mt)dt)
				=  1 – f(m,2m)  =  f(1,2)

4

a i)	5 marks
SST: Bookwork.  N.B. condition:  irreducible MP, +ve recurrence a consequence of existence of a solution to the equations.

Flow balance:  equate total probability flux into and out of each state (or set of states).

a ii)	5 marks
Draw contour round states {0,1,...,n–1}  (1≤n≤K).  
Then only 1 outgoing transition (n–1 Æ n) and 1 incoming transition (n Æ n–1).
Balance equations are threfore:

	(K–n+1)lpn–1  =  mpn	(1≤n≤K)

so that  pn = f(K!,(K–n)!) rnp0  where r=l/m.  These are the unnormalised probabilities; normalisation gives p0.

a iii)	3 marks
Always stable since the state space is finite (no arrivals in state K).  Hence the equations of the SST always have a solution, the MP always being +ve recurrent.

b i)	4 marks
No change to the possible transitions (state moves up or down by one).  Negative arrivals have the same effect as a service completion on the state (i.e. goes down) and by the superposition property of the Poisson process, the combination of negative arrivals and service completions is statistically equivalent to a single Poisson process with rate m+L.
The customer killed by a negative arrival (or served for that matter) does not come in to this argument.

b ii)	3 marks
The above argument related to the state not to a particular customer.  Clearly it matter to a customer which customer is killed, especially if it is himself!  Killing at the head of the queue means queueing customers are "safe" and the killing rate can just be added to the service rate as in b(i)  (with probability m/(m+L) of surviving).  However, this is not the case if the last (or any other) customer is chosen.  If the last is chosen, the more positive arrivals before a negative arrival the more protection is offered.  Hence need to model the evolution of the queue throughout the sojourn of a tagged customer, contrast the case without negative customers.

1995

1

a i)	3 marks
Bookwork:
P(Xt+s=x | Xu=xu, u≤t)  =  P(Xt+s=x | Xt=xt)  (MP)
P(Xt+s=x | Xt=y) = P(Xs=x | X0=y)  fo all t≥0  (TH)
For i≠j, aij = miqij where mi is the instantaneous transition rate and qij the state transition probability, and aii such that rows sum to 0

a ii)	3 marks
Bookwork:  qij(s+t) = P(Xt+s=j | X0=i) = isu(,, P(Xt+s=j | Xs=k)P(Xs=k | X0=i)) by MP and result follows by TH.

a iii)	2 marks
Bookwork:  An irreducible Markov process is positive recurrent iff the equations p.A = 0 and p.1 = 0 have a solution.  If so p is the equilibrium solution.

b	6 marks
Rate(1Æ2) = P(write by other processor–rate t–to particular location in memory)
Rate(2Æ1) = P(read or write by this processor to particular line in cache)

b	6 marks
No effect on state transition rates since protocol on states is unchanged.  Fewer writes if data modified often, but greater overhead on read miss (write-back).

2

a   MVA:  bookwork	5 marks

a i)	2 marks
Traffic rate at node i is Tvi so results follow by Little's result applied to node i and the whole network respectively.

a ii)	3 marks
JOP:  arrivals "sees" steady state with one customer removed, so Yi(K) = Li(K–1), parameterising on population K.  Mean service time is 1/mi.  This leads to the usual iteration.

b i)	6 marks
K=0:  Li(0)=0.  As KÆ∞:  (K–1)/K Æ 1 so YiÆ Li or ~ Li if it diverges.

FPE:  miWi = 1 + ((K–1)/K)TviWi
so  K = T isuin(i=1,M,viWi) = T isuin(i=1,M,vi/(mi–((K–1)/K)Tvi)), a non-linear equation for T, a FPE when written in the form T = ...

b ii)	4 marks
K = TvKM/(Km–(K–1)Tv) ﬁ TvM = Km – (K–1)Tv ﬁ Tv = Km/(M+K–1)
ﬁ W = 1/(m–(K–1)m/(M+K–1)) = (M+K–1)/Mm

3

a	8 marks
l < m.											(2)

  SSQLPD:  bookwork via birth-death process.  					(4)

FCFS not necessary, e.g. same for LCFS since state transition diagram does not change by memorylessness.									(2)

b i)	4 marks
Given queue length n>0, queueing time comprises n service times by memorylessness.
This is the same as for unconditional waiting times when queue length faced is n-1 (n>0).
Thus, using ROP, RTP  P(QL=n | n>0) = P(QL=n-1) = (1–r)rn-1 which it is since since P(n>0) = r.

b ii)	2 marks
Queueing time in the parallel server is either zero or the time required for the parallel servers to serve the whole queue that existed on arrival – of length n≥m.  But during queueing time the parallel server behaves as if a single server with rate mm.

b iii)	2 marks
P(Queueing time > t) = P(QT > t | has to queue) q =  q.P(WT in M/M/1(rate mm) > t)

b iv)	4 marks
P(Queues for more than t in M/M/2) = q exp(–(2m–l)t)  where q is the probability of having to queue = P(QL≥2) by ROP = 1–(1+r)/[1+Si>0 ri/2i-1] = r2/(2+r).  
P(Waiting time more than t in M/M/1) = exp(–(2m–l)t).

4

a i)	4 marks
Jackson's theorem:  bookwork – (a) independence of nodes;  (b) as if M/M/1 queues

a ii)	4 marks
1.  Take any subnetwork and short-circuit the rest of the network, i.e. choose same visitation rates and service rates and consider a closed network.

2.  Solve the closed network for throughput on "short-circuit", T(K), i.e. some throughputs of outputing nodes, for all required populations K.

3.  FES in original network then has service rate function m(.) = T(.)

a iii)	3 marks
When transition rates in reduced subnetwork are much higher than transition into and out of the rest of the network.

E.g. multi-access system with paging (Bookwork) has relatively few transitions from terminals into computer system (intertransition time = think time) compared with device service rates in computer system. 

Bonus of +1 if say why this model is inexact, i.e. because of blocking for memory.

b	9 marks
Nodes are:	(1)	Clients,  IS rate l
		(2)	Network 1,  M/M/1 rate m
		(3)	Network 2,  M/M/1 rate m
		(4)	FES node for server, rate R(n) when queue length is n

Throughput is l.  Mean response time is given by mean queue length + Little's result, given M/M/1 queue with arrival rate l and service rate function R.

Yes, wrt the decomposition, since rates in the server are "fast", but poor representation of networks.  IS should be a good representation because of insensitivity to distribution of service times.

1996

1

a i)	2 marks
Markov Chain:  Bookwork.
P(Xn+1=xn+1 | Xi=xi, i≤n) =  P(Xn+1=xn+1 | Xn=xn)  for all n≥0.
Qij = (Xn+1=j| Xn=i) 

a ii)	4 marks

a iii)	4 marks
SST: bookwork.
An irreducible, aperiodic MC is positive recurrent iff the equations  pi = S pjqji and S pi = 1 have a solution.  Then the pi  are the steady state probabilities of the states i.

b	10 marks
pi-1(k–i+1)ta/N + pi+1(i+1)t(1–b)/n = pi[(k–i)t/N + it(1–ab)/n]		(i>1)
p0kta/N + 2p21t(1–b)/n + (Sj≠1 pj)kt(1–a)/N = p1[(k–1)ta/N + t(1–b)/n]
p1t(1–b)/n = p0kt/N

2

a i)	3 marks
Ball in bag argument.  N balls, M–1 partitions, so N+M–1 objects to rearrange, subset of N identical and subset of M–1 identical.

a ii)	3 marks
Bookwork.  p(n) = (P xisup6(ni))/g(M,N)  where xi = ei / mi and ei is the visitation rate for server i derived by solving the traffic equations  e = e.R where R is the routing probability matrix.  mi is the service rate of server i.

a iii)	2 marks
g(m,n) = SxŒstate space (P xisup6(ni))

b	6 marks
Bookwork:  by partitioning the state space into states with nM=0 and nM>0.

c	6 marks
	P(Ni>0)	=  (1/G(N))	S P xmnm
					N≥ni>0
			=  (1/G(N)) xi	S P xmnm
					N>ni≥0
			=  (1/G(N)) xi G(N–1)

Gi is the normalising constant for the smaller network defined (uniquely) by {x1,...,xi-1, xi+1,...xM}.  Similarly for Gij.  (Explanation in terms of short-circuiting nodes can get full marks only if very carefully explained.)
	P(Ni=k, Nj=h)	=  (1/G(N))	S P xmnm
						ni=k, nj=h
			=  (1/G(N)) xik xjh	S P xini
						ni=0, nj=0
				=  (1/G(N)) xik xjh Gij(N–h–k)
(with explanation)
Similarly, P(Nj=h)  =  (1/G(N)) xjh Gi(N–h)  and dividing yields the required result.

3

a	7 marks
The process defined by the queue length just after departure instants is a Markov chain (the EMC) because:

(1)  The probability mass function for the next state depends only on the present state.

(2)  The time to the next departure depends only on the present state, since it is either a full service time or a residual interarrival time, which has the same state-independent distribution as a full interarrival time (PP) PLUS a full service time.

Hence need to derive prob. mass function for the number of Poisson arrivals in a service time of known distribution function, which is straightforward.  This gives the one-step transition probabilities for the EMC.

Bonus:  Explanation of derivation of pgf	+2 bonus

b	6 marks
L = lW for queueing system in steady state

LQ = lQ

Q = LQ.m + u.M2/2m  where M2 = v + m2,  m = 1/m,  u = l/m
by residual service time result for renewal processes and ROP

(1–l/m)Q = l(v+m2)/2

c i)	3 marks
A holds bus 1, blocked waiting for bus 2 which is held by B blocked for bus 1.  Cyclic wait condition with no release.

c i)	4 marks
bus 2:  1/m

bus 1:  Q2 + 1/m		(allow Q2 + 2/m)
where	Q2 =   f(lm–2,(1–(2l/m)))

4

a	10 marks
Bookwork:

Arrival rate at node i = Tvi.  
Little applied to node i ﬁ first equation
Little applied to whole system ﬁ third equation
Job observer property ﬁ second equation

(plus explanation re. fictitious node etc)

b i)	4 marks

k = T(k) S (vi/mi)(1+Li(k–1)) ≥ T(k) min(vi/mi) S (1+Li(k–1)) = (M+k-1) T(k) min(vi/mi)

Similarly,

k ≤ T(k) max(vi/mi) S (1+Li(k–1)) = (M+k-1) T(k) max(vi/mi)

Hence  f(k,M+k–1) sdo2(a(min,1≤i≤M)) sup4((mi/vi))  ≤  T(k)  ≤  f(k,M+k–1) sdo2(a(max,1≤i≤M)) sup4((mi/vi))

b ii)	2 marks

Li(k)  =  (viT(k)/mi)[1+Li(k–1)]

b iii)	4 marks

For all i,  T(k)vi = li < mi  for stability.  Hence as kÆ∞,   mb/vb  < T(k) <  mb/vb .

For i≠b,  Li(k)  =  (viT(k)/mi)[1+Li(k–1)]  where  viT(k)/mi  =  vimb/vbmi  <  1 by hypothesis.  Hence Li(k) converges to Li given by

Li =  (vimb/vbmi )[1+Li]  =  f(vimb/vbmi ,1–vimb/vbmi )