Transcript m-1

Lecture 6
Performance analysis for
high speed switches
The M/M/1 Queueing
System
The M/M/1 Queueing System
• The M/M/1 Queueing System consisits of a
single queueing station with a single server. The
name M/M/1 reflects standard queueing theory
nomenclature whereby:
– The first letter indicates the nature of the arrival
process.
• e.g., M stands for memoryless, which here means a Poisson
process, G stands for a general distribution of interarrival
time, D stands for deterministic interarrival times.
– The second letter indicates the nature of the
probability distribution of the service times.
– The last number indicates the number of servers.
The M/M/1 Queueing System
• We have already established, via Little’s Theorem, the
relations
N  T , NQ  W
Between the basic quantities,
N = Average number of customers in the system
T = Average customer time in the system
NQ = Average number of customers waiting in queue
W = Average customer waiting time in queue
• Given these statistics, we will be able to derive the
steady-state probabilities
– pn = Probability of n customers in the system, n = 0,1, …
• From these probabilities, we can get N 
and using Little’s Theorem, T  N


npn

n0
Arrival statistics—the Poisson
process
• A stochastic process A(t) t  0 taking nonnegative integer
values is said to be a Poisson process with rate λif














– A(t) is a counting process that represents the total number of
arrivals that have occurred from 0 to t, and for s < t, A(t)-A(s)
equals the numbers of arrivals in the interval (s, t].
– The numbers of arrivals that occur in disjoint time intervals are
independent.
– The number of arrivals in any interval of length τ is Poisson
distributed with parameter  . That is, for all t, τ> 0,
n
(

)


P A(t  )  A(t)  n  e
, n  0,1,...






n!
Arrival statistics—the Poisson
process (Cont)
• We list some of the properties of the Poisson process that
will be of interest:
– Interarrival times are independent and exponentially distributed
with parameter λ; that is, if tn denotes the time of the nth arrival,
the intervals  n  tn1  tn have the probability distribution
P  n  s 1 e s , s  0


and are mutually independent.
– For every t  0 and   0 ,
P  A(t   )  A(t )  0  1    o( )
P  A(t   )  A(t )  1    o( )
P  A(t   )  A(t )  2  o( )
where we generically denote by o(δ) a function of δsuch that
lim
 0
o ( )

0
Arrival statistics—the Poisson
process (Cont)
• We list some of the properties of the Poisson process
that will be of interest:
– If two or more independent Poisson processes A1 ,..., Ak are
merged into a single process A  A1  A2  ...  Ak , the latter
process is Poisson with a rate equal to the sum of the rates
of its components.
– If a Poisson process is split into two other processes by
independently assigning each arrival to the first (second) of
these processes with probability p ( 1-p, respectively), the
two arrival processes thus obtained are Poisson.
Service Statistics
• Our assumption regarding the service process is that the
customer service times have an exponential distribution
with parameter μ, that is, if sn is the service time of the
nth customer,
P sn  s  1  e  s , s  0
• An important fact regarding the exponential distribution is
its memoryless character, which can be expressed as
P  n  r  t |  n  t  P  n  r , for r , t  0
P sn  r  t | sn  t  P sn  r , for r , t  0
for the interarrival and service times  n and sn ,respectively
• Verification of the memoryless property follows the
calculation
P  n  r  t |  n  t 

P  n  r  t
P  n  t
e ( r t )
et
 e r  P  n  r
Markov Chain Formulation
• Let us focus attention at the times 0,  , 2 ,..., k ,...
where δis a small positive number. We denote
Nk = Number of customers in the system at time k 
• Let Pij denote the corresponding transition probabilities
Pij  P N K 1  j | N k  i
• We can show that
P00  1    o( )
Pii  1      o( ), i  1
Pi ,i 1    o( ), i  0
Pi ,i 1    o( ), i  1
Pij  o( ), i and j  i, i  1, i  1
P 0 customers arrive and 0 depart in I k   1      o( )
P 0 customers arrive and 1 depart in I k     o( )
P 1 customers arrive and 0 depart in I k     o( )
Derivation of the Stationary
Distribution
• Consider now the steady-state probabilities
pn  lim P  N k  n  lim P N (t )  n
k 
t 
• The probability that the system is in state n and makes a transition
to n+1 in the next transition is the same as the probability that the
system is in state n+1 and makes a transition to n, that is,
pn   o( )  pn1  o( )
Derivation of the Stationary
Distribution (Cont.)
• By taking the limit in the equation as   0, we obtain
pn   pn1
These equations can also be written as pn 1   pn , n  0,1,...



where

n1
p


p0 , n  0,1,...
• It follows that n1
• If   1, the probabilities pn are all positive and add up to
unity, so


p
1
pn 
 n p0  0
1 
n 1
n 1


• Combing the last two equations, we finally obtain
pn   n (1   ), n  0,1,...
Derivation of the Stationary
Distribution (Cont.)
• We can now calculate the average number of customers in the
system in steady-state:
N  lim E  N (t ) 
t 
  (1   )

 np
n
n 0

 n
n 1
n 0


 n
n
(1   )
n 0


  (1   )
(
n)
 n  0

  (1   )

1
1
(
)   (1   )
 1  
(1   ) 2
and finally, using  
 , we have N    
1    

• The average delay per customer is given by Little’s Theorem,
N

T

  (1   )
Using  

, this becomes
T
1
Average Number in the system N
Derivation of the Stationary
Distribution (Cont.)
N

1 
Utilization Factor



• The average waiting time in queue, W, is the average
delay T less the average service time 1/μ, so
1
1

W
 
    
• By Little’s Theorem, the average number of
customers in queue is
2
NQ  W 
1 
Occupancy Distribution upon Arrival
• The steady-state occupancy probabilities upon arrival,
an  lim P  N (t )  n | an arrival occured just after time t
t 
need not be equal to the corresponding unconditional
steady-state probabilities,
pn  lim P  N (t )  n
t 
• It turn out, however, that for the M/M/1 system, we
have
pn  an , n  0,1,...
Occupancy Distribution upon Arrival
(Cont.)
• A formal proof under the preceding assumption:
– Let
pn (t )  P N (t )  n
an (t )  P N (t )  n | an arrival occured just after time t
– We have, using Bayes’ rule,
an (t )  lim P  N (t )  n | A(t , t   )
 
 lim
 
 lim
 
P  N (t )  n, A(t , t   )
P  A(t , t   )
P  A(t , t   ) | N (t )  n
P  A(t , t   )
– By assumption, the event A(t, t+δ) is independent of the
number in the system at time t, therefore,
P  A(t , t   ) | N (t )  n  P  A(t , t   )
and we obtain
an (t )  P N (t )  n  pn (t )
Occupancy Distribution upon Departure
• Let us consider the distribution of the number of
customers in the system just after a departure has
occurred, that is, the probabilities
dn (t )  P N (t )  n | a departure occured just after time t
• The corresponding steady-state values are denoted
dn  lim dn (t ), n  0,1,...
t 
• It turns out that
dn  an , n  0,1,...
The M/G/1 Queueing
System
The M/G/1 System
• Let
X  E X  
1

 Average service time
 
X 2  E X 2  Second moment of service time
• The Pollaczek-Khinchin(P-K) formula:
X2
W 
2(1   )
where W is the expected customer waiting time in
queue and

   X

• The total waiting time, in queue and in service, is
X2
TX
2(1   )
M/G/1: System (Cont.)
• Appling Little’s formula to W and T, we get the
expected number of customers in the queue NQ and the
expected number in the system N:
NQ
2 X 2

2(1   )
2 X 2
N   
2(1   )
• Under exponential service time, i.e.,
W

 (1   )
X2 
W
2 (1   )
2
,
( M / M /1)
• When service time is deterministic, i.e.,

2
( M / D /1)
X2 
1
2
M/G/1: System (Cont.)
• Denote
–
–
Wi = Waiting time in queue of the ith customer
Ri = Residual service time seen by the ith customer. By this
we mean that the customer j is already being serve
when i arrives, Ri is the remaining time until customer
j’s service time is complete. If no customer is in
service(i.e., the system is empty when i arrives), then Ri
is zero
– X = Service time of the ith customer
i
– N = Number of customers found waiting in queue by the ith
i
customer upon arrival
• We have
i 1
Wi  Ri 

j i  Ni
Xj
M/G/1: System (Cont.)
• By taking expectations and using the independence of
the random variable N i and X i 1 ,..., X i  N , we have
i 1


E Wi   E Ri   E 
E X j | Ni

 j i  N i
 



  E Ri   X E Ni 


• Taking the limit as i   , we obtain
W  R
1

NQ
where
R = Mean residual time, define as R  lim E Ri  .
i 
M/G/1: System (Cont.)
Residual Service time γ
τ
（
）
X1
0
X1
X M (t )
X2
• By Little’s Theorem, we have
time 
NQ  W
and by substitution in the waiting time formula, we
obtain W  R  W

where  
is the utilization factor; so finally,

R
W
1 
M/G/1: System (Cont.)
• The time average of  ( ) in the interval [0,t] is
1
t

t
1
 ( )d 
0
t
M (t )

1 2
Xi
2
i 1
where M(t) is the number of service completions within[0,t], and Xi
is the service time of the ith customer.
• We can also write this equation as
1
t

t
1 M (t )
 ( )d 
0
2 t

M (t )
i 1
X i2
M (t )
and assuming the limits below exist, we obtain
1
t  t
lim

t
0
 ( )d 
1
M (t )
lim
lim
2 t  t t 

M (t )
i 1
X i2
M (t )
• Assuming that time averages can be replaced by
ensemble averages, we obtain R  1  X 2
2
X2
• The P-K formula, W 
2(1   )
Crossbar Switches
• Crossbar switches are an important general architecture
for fast switches.
• 2 x 2 Crossbar Switches
• A general N x N crossbar switch
Input Queueing versus Output
Queueing
• Input Queueing -"If we come in
together then we
wait together"
• Output Queueing -"We wait at the
destination (output)
together"
The queueing will be at the input
or at the output?
• The switch fabric speed is equal to the input line
speed
– To avoid collision on the single speed switch fabric, only one input line can
can place a packet on the switch fabric at a time. This requires the other
inputs to stop the packet from entering the switch fabric. This is
implemented using an queue at the input.
• The switch fabric speed is N times faster than
the input line speed
– The internal switch has slot times which are N times as fast as
those of the input lines. The packets enter the crossbar switch
together and are shifted to the outputs together. This requires
queueing at the outputs to avoid collisions.
General Assumptions for Analysis
• In any given time slot, the probability that a
packet will arrive on a particular input is p.
Thus p represents the average utilization of
each input.
• Each packet has equal probability 1/N of
being addressed to any given output, and
successive packets are independent.
Analysis of Output Queueing
• Switch with Speedup factor of N.
• Arriving packets reach the targeted output
”immediately”.
• Am = # arriving packets at the tagged queue
during a given time slot m
p= load
1
1
1
1
ai  Pr[ Am  i]  (iN )( Np )i (1 Np ) N i
N!
i!( N i)!
i p
p
 e
i!
e p
as N  
Poisson
Distribution.
Analysis of the Output Queue Size
Qm : the number of packets in the tagged queue at the
end of the time slot m
Qm  max(0,Qm1 Am 1)
Using a standard approach in queueing analysis















(1 p)(1 z)
if N 
p
p
N
(1  z )  z
N N
Q( z)  (1 p)(1 z) 
A( z)  z
(1 p)(1 z)
The mean
e p(1 z)  z
stead-state
queue size
Q  d [Q( z)]
d ( z)
As
z1
if N 
2
 ( N 1)  p  ( N 1) QM / D /1
N
N
2(1 p)
N , Q QM / D/1
The mean queue
size for an M/D/1
queue
The State transition diagram for the
output queue size
a4
a3
a3
a0  a1
a1
a2
a2
0
a1
1
a0
a2
2
a0
a0
…
The Steady-State Queue Size
Probabilities
q  Pr(Q  0)  (1 p)e p
0
a0 Pr(Q  1)  (a2  a3  ...) Pr(Q  0)
q1  Pr(Q 1) 
(1 a0  a1)
q0
a0
a0 Pr(Q  2)  a2 Pr(Q  0)  (a0  a2  a3  ...) Pr(Q  1)
…
(1 a )
a
q2  Pr(Q  2)  a 1 q1 a2 q0
0
0
n
a0 Pr(Q  n)   ai Pr(Q  n  i)  (a0  a2  a3  ...) Pr(Q  n 1)
i 2
n a
(1 a )
qn  Pr(Q  n)  a 1 qn1  ai qni
0
0
i2
Analysis of the Packet Waiting Time
W
The time slots that
packet must wait
while packets that
arrived in earlier
time slots are
transmitted

W1

W2
The time slots that
packet must wait
additionally until it is
randomly selected out
of the packet arrivals in
the time slot m
Analysis of the Packet Waiting Time
W1( z)  Q( z)  (1 p)(1 z)
A( z)  z
W1  Qm1
• b: the size of the batch the packet arrives in
Pr[b  i] 
iai
A

iai
p

Pr[W2  k ] 
 Pr[W
2
i 0
k

 k | b  i ] Pr[b  i ]


1
 0 Pr[b  i ] 
Pr[b  i ]
i
i 0
i  k 1




1
1

Pr[b  i ] 
ai
i
p i  k 1
i  k 1
W2 ( z)  1 A( z)
p(1 z)
Analysis of the Packet Waiting Time
A z）
W (z) W1(z) W2(z)  Q(z) 1 （
（1 z)
•
the mean steady-state waiting time
2
1
W  Q  [ A  A]  ( N 1) p  ( N 1)W M / D /1
N 2(1 p) N
2p
The mean
waiting time
for an M/D/1
queue
Analysis of the Packet Waiting Time
• The steady-state waiting time probabilities:
k
Pr[W  k ] 
 Pr[W
1
 n and W2  k  n ]
n 0
k
1

p
q
1

p
q
n
n 0
k
n
n 0


ai
i  k 1 n
k n
[1 
a ]
i
i 0
Analysis of Input Queueing
• More complex system to analyze than output
queueing case.
• In order to analyze it, we make a simplifying
assumption of "heavy load", i.e. all queues are
always full.
• This is a worst-case assumption.
head-of-line (HOL) blocking
Input Queues
Winning packet
Losing packet
31
cannot access
output 2 because
it is blocked by
the first packet
21
4
3
Outputs
1
Internally
Nonblocking
Switch
2
3
4
Internally Nonblocking Switch:
Dropping packets
0 = Pr[ carry a packet ]
1
2
3
2
Pr[ carry a packet ] = p
1 0  (1
p N
)
N
0  1 (1 p ) N 1 e p
N
For p=1, 0 = 0.632
for large N
the fictitious output queues used for analysis
Fictitious
Output Queues
formed by HOL
packets
Output 1
(3,2) (1,2) Output 2
(2,3) Output 3
(4,4) Output 4
(input, output)
(1,1)
(2,1)
(3,2)
(4,1)
Outputs
(1,2)
(2,3)
(3,2)
(4,4)
Internally
Nonblocking
Switch
1
2
3
4
– How about small N?
N
*
2
3
4
5
0.75 0.68 0.66 0.64
* : the maximum throughput with input queueing
– Simulation Results with
Large N
Throughout of Input-Buffered Switch
– Consider a fictitious queue i
Cmi = # packets at start of time slot m.
Ami = # packets arriving at start of time slot m.
i
i
i
C

max(0,
C

1)

A
– m
m
m
Bmi 1
i
i
– Am is Poisson and independent of Bm1
as N  
i
Pr[ Am
–

A( z ) 

i 0
pk  p
 k] 
e
k!
Pr[ A  i]Z i  e( z 1) p
e.g. Fictitious Queue i
i
Am
2
i
Cm
1  3
1
i
i
1
i
i
1
2
2
2
3
i
time slot time slot
m
m-1

–
B( z ) 

z k Pr[ B  k ]
k 0
 Pr[ B  0]  z Pr[ B  1]  ...
 Pr[C  0]  Pr[C  1]  z Pr[C  2]...
 (1  z 1 ) Pr[C  0]  z 1C( z)
1 p
–
under
saturation
1
C( z)  [(1  z )(1  p)  z C( z)]A( z)
C ( z)( z  A( z))  ( z  1) A( z )(1  p)
2C '(1)(1  A '(1))  A"(1)  2 A '(1)(1  p)
1
–
1
p
p2
p
p2  4 p  2  0  p  2  2  0.586
Meaning of Saturation Throughput
p0 =


Input Queue
For finite buffer size,
if p0 > p* = 0.586 at
least (p0 - p*)/ p0
fraction of packets are
dropped.
Must keep p0 < p*
p = throughput
Queuing scenario for the delay analysis
of the input-buffered switch
Fictitious Queues
Input Queue
N
1/N
1/N
2
Output 1
Output 2
HOL
1/N
Time spent in HOL
are independent
for successive
packets when N is
large
Output N
Service times at
different
fictitious queues
are independent
The busy periods and interpretations
for delay analysis of an input queue
U(t)

X0 
X1
 X2X3
Idle
period Busy period
Y
Busy period
Arrivals here
are considered
as arrivals in
intervals i-2
X0
Arrivals here are considered
as arrivals in intervals i-1
Xi-1
Xi
t
Illustration of the meanings of random
variables used in the delay analysis of an
input queue
Arrival of the packet of focus. One
simultaneous arrival to be served before
the packet; L=1.
mi =2
prior
arrivals
(1) (1)
Departure of
packet of focus.
(2)
Xi
Xi+1
Ri
W
-- Packet arrival in interval i.
-- packet departure in interval i+1.
(n) -- number of arrivals
Three Selection Policies
• Random Selection Policy
– If k packets are addressed to a particular output, one of the
k packets is chosen at random, each selected with equal
probability 1/k.
• Longest Queue Selection Policy
– The controller sends the packet from the longest queue
• Fixed Priority Selection Policy
– The N inputs have fixed priority levels and of the k packets,
the controller send the one with highest priority
Different contention-resolution policies have
different waiting time versus load
relationships, but a common maximum load at
which waiting time goes to infinity.
_
W
p0
Conclusion
• Mean queue length are always greater for
queueing on inputs than on outputs
• Output queues saturate only as the utilization
approaches unity
• Input queues saturate at a utilization that
depends on N, but is approximately 0.586
when N is large