9. Sharing systems

lect09.ppt

S-38.1145 – Introduction to Teletraffic Theory – Spring 2006

1


9. Sharing systems

Contents
•

Refresher: Simple teletraffic model

•
•

M/M/1-PS (∞ customers, 1 server, ∞ customer places)
M/M/n-PS (∞ customers, n servers, ∞ customer places)

•

Application to flow level modelling of elastic data traffic

•

M/M/1/k/k-PS (k customers, 1 server, k customer places)

2

9. Sharing systems

Simple teletraffic model
•

Customers arrive at rate λ (customers per time unit)
– 1/λ = average inter-arrival time

•

Customers are served by n parallel servers

•

When busy, a server serves at rate µ (customers per time unit)
– 1/µ = average service time of a customer

•

There are n + m customer places in the system
– at least n service places and at most m waiting places
It is assumed that blocked customers (arriving in a full system) are lost

•

λ

n+m


µ1
µ
µ
µ
n

3


9. Sharing systems

Pure sharing system
•

Finite number of servers (n < ∞), infinite number of service places
(n + m = ∞), no waiting places
– If there are at most n customers in the system (x ≤ n), each customer has
its own server. Otherwise (x > n), the total service rate (nµ) is shared fairly
among all customers.
– Thus, the rate at which a customer is served equals min{µ,nµ/x}
– No customers are lost, and no one needs to wait before the service.
– But the delay is the greater, the more there are customers in the system.
Thus, delay is an interesing measure from the customer’s point of view.

λ

∞

µ1

µ
µ
µ
n

4


9. Sharing systems

Contents
•

Refresher: Simple teletraffic model

•
•

M/M/1-PS (∞ customers, 1 server, ∞ customer places)
M/M/n-PS (∞ customers, n servers, ∞ customer places)

•

Application to flow level modelling of elastic data traffic

•

M/M/1/k/k-PS (k customers, 1 server, k customer places)

5



9. Sharing systems

M/M/1-PS queue
•

Consider the following simple teletraffic model:
– Infinite number of independent customers (k = ∞)
– Interarrival times are IID and exponentially distributed with mean 1/λ
• so, customers arrive according to a Poisson process with intensity λ
– One server (n = 1)
– Service requirements are IID and exponentially distributed with mean 1/µ
– Infinite number of customer places (p = ∞)
– Queueing discipline: PS. All customers are served simultaneously in a fair
way with equal shares of the service capacity µ.

•
•

Using Kendall’s notation, this is an M/M/1-PS queue
Notation:
– ρ = λ/µ = traffic load
6


9. Sharing systems

State transition diagram
•


Let X(t) denote the number of customers in the system at time t
– Assume that X(t) = i at some time t, and
consider what happens during a short time interval (t, t+h]:
• with prob. λh + o(h),
a new customer arrives (state transition i → i+1)
• if i > 0, then, with prob. i(µ/i)h + o(h) = µh + o(h),
a customer leaves the system (state transition i → i−1)

•

Process X(t) is clearly a Markov process with state transition diagram
0

•

λ
µ

1

λ
µ

2

λ
µ

Note that this is the same irreducible birth-death process with an infinite

state space S = {0,1,2,...} as for the M/M/1-FIFO queue.
7


9. Sharing systems

Equilibrium distribution (1)
•

Local balance equations (LBE):

π i λ = π i +1µ

(LBE)

⇒ π i +1 = λ π i = ρπ i
µ
⇒ π i = ρ iπ 0 , i = 0,1,2, K
•

Normalizing condition (N):

∞

∞

i =0

i =0


∑π i = π 0 ∑ ρ i = 1
∞



i
⇒ π 0 =  ∑ ρ 
 i =0 

(N)

−1

=

( )

1 −1
1− ρ

= 1 − ρ , if ρ < 1

8


9. Sharing systems

Equilibrium distribution (2)
•


Thus, for a stable system (ρ < 1), the equilibrium distribution exists
and is a geometric distribution:

ρ < 1 ⇒ X ∼ Geom( ρ )
P{ X = i} = π i = (1 − ρ ) ρ i , i = 0,1,2, K
ρ
E[ X ] = 1− ρ ,
•

2

D [X ] =

ρ

(1− ρ ) 2

Remark: Insensitivity with respect to service time distribution
– The result for the PS discipline is insensitive to the service time
distribution, that is: it is valid for any service time distribution with mean 1/µ
– So, instead of the M/M/1-PS model, we can consider, as well, the more
general M/G/1-PS model
9


9. Sharing systems

Mean delay
•


Let D denote the total time (delay) in the system of a (typical) customer

•

Since the mean number of customers in the system, E[X], is the same
for all work-conserving queueing disciplines, also the mean delay is the
same, by Little’s result.
Thus, we may apply the result derived for the FIFO discipline in Lect. 8:

•

E[D ] = µ1 ⋅ 1−1ρ

10


9. Sharing systems

Mean delay E[D] vs. traffic load ρ
– Note that the time unit is the average service requirement E[S]
6
5
4

E[D]

3
2
1
0.2


0.4

0.6

0.8

1

traffic load ρ

11


9. Sharing systems

Relative throughput
•

A quality of service measure is the relative throughput E[S]/E[D]:

E[ S ] 1
= ⋅ µ (1 − ρ ) = 1 − ρ
E[ D ] µ

12


9. Sharing systems


Relative throughput E[S]/E[D] vs. traffic load ρ

1
0.8

E[S]/E[D]

0.6
0.4
0.2
0.2

0.4

0.6

0.8

1

traffic load ρ

13


9. Sharing systems

Contents
•


Refresher: Simple teletraffic model

•
•

M/M/1-PS (∞ customers, 1 server, ∞ customer places)
M/M/n-PS (∞ customers, n servers, ∞ customer places)

•

Application to flow level modelling of elastic data traffic

•

M/M/1/k/k-PS (k customers, 1 server, k customer places)

14


9. Sharing systems

M/M/n-PS queue
•

Consider the following simple teletraffic model:
– Infinite number of independent customers (k = ∞)
– Interarrival times are IID and exponentially distributed with mean 1/λ
• so, customers arrive according to a Poisson process with intensity λ
– Finite number of servers (n < ∞)
– Service requirements are IID and exponentially distributed with mean 1/µ

– Infinite number of customer places (p = ∞)
– Queueing discipline: PS. If there are at most n customers in the system
(i ≤ n), each customer has its own server. Otherwise (i > n), the total
service rate (nµ) is shared fairly among all customers.

•
•

Using Kendall’s notation, this is an M/M/n-PS queue
Notation:
– ρ = λ/(nµ) = traffic load
15


9. Sharing systems

State transition diagram
•

Let X(t) denote the number of customers in the system at time t
– Assume that X(t) = i at some time t, and
consider what happens during a short time interval (t, t+h]:
• with prob. λh + o(h),
a new customer arrives (state transition i → i+1)
• if i > 0, then, with prob. i⋅min{µ,nµ/i}⋅h + o(h) = min{i,n}⋅µh + o(h),
a customer leaves the system (state transition i → i−1)

•

Process X(t) is clearly a Markov process with state transition diagram

0

•

λ
µ

1

λ

λ

2µ

nµ

n

λ
nµ

n+1

λ
nµ

Note that this is the same irreducible birth-death process with an infinite
state space S = {0,1,2,...} as for the M/M/n-FIFO queue.
16



9. Sharing systems

Equilibrium distribution (1)
•

Local balance equations (LBE) for i < n:

π i λ = π i +1 (i + 1) µ

(LBE)
nρ

⇒ π i +1 = ( +λ1) µ π i = i +1π i
i

•

( nρ )i
⇒ π i = i! π 0 , i = 0,1,K , n
Local balance equations (LBE) for i ≥ n:

π i λ = π i +1nµ

(LBE)

⇒ π i +1 = nλµ π i = ρπ i
⇒ πi = ρ


i−n

πn =

n
i − n ( nρ )
ρ
π0
n!

=

nn ρ i
π 0,
n!

i = n, n + 1, K 17


9. Sharing systems

Equilibrium distribution (2)
•

Normalizing condition (N):

∞

 n −1 ( nρ )i ∞ n n ρ i 
∑ π i = π 0  ∑ i! + ∑ n!  = 1

 i =0

i =0
i =n
 n −1 (nρ ) i ( nρ ) n ∞ i − n 

⇒ π 0 =  ∑ i! + n! ∑ ρ
 i =0

i =n
 n −1 ( nρ )i


=  ∑ i! + n!(1− ρ ) 
 i =0

( nρ ) n

n −1 ( nρ ) i

Notation : α = ∑

i =0

i!

−1

, β=


(N)
−1

1
=
, if ρ < 1
α +β

( nρ ) n
n!(1− ρ )

18


9. Sharing systems

Equilibrium distribution (3)
•

Thus, for a stable system (ρ < 1, that is: λ < nµ), the equilibrium
distribution exists and is as follows:

ρ <1 ⇒
 ( nρ )i 1
 i! ⋅ α + β , i = 0,1, K , n
P{ X = i} = π i =  n i
 n ρ ⋅ 1 , i = n, n + 1, K
 n! α + β
•


Remark: Insensitivity with respect to service time distribution
– The result for the PS discipline is insensitive to the service time
distribution, that is: it is valid for any service time distribution with mean 1/µ
– So, instead of the M/M/n-PS model, we can consider, as well, the more
general M/G/n-PS model

19


9. Sharing systems

Mean delay
•

Let D denote the total time (delay) in the system of a (typical) customer

•

Since the mean number of customers in the system, E[X], is the same
for all work-conserving queueing disciplines, also the mean delay is the
same, by Little’s result.
Thus, we may apply the result derived for the FIFO discipline in Lect. 8:

•

(

p

)


E[ D ] = µ1 ⋅ n(1W
+1
−ρ )
– where pw refers to the probability

pW =

∞

∞

nn ρ i
P{ X * ≥ n} = ∑ π i = ∑ π 0 ⋅ n!
i =n
i =n

( nρ ) n
= π 0 ⋅ n!(1− ρ )

β

= α +β
20


9. Sharing systems

Mean delay E[D] vs. traffic load ρ
– Note that the time unit is the average service requirement E[S]

6
5
4

E[D]

n=1

3

2

2

3
10
100

1
0.2

0.4

0.6

0.8

1

traffic load ρ


21


9. Sharing systems

Relative throughput
•

A quality of service measure is the relative throughput E[S]/E[D]:

n (1− ρ )
n (1− ρ )
E[ S ] 1
=
⋅
µ
⋅
=
E[ D ] µ
pW ( n ) + n(1− ρ ) pW ( n ) + n (1− ρ )

E[ S ]

1− ρ

n = 1 : E[ D ] = p (1) +1− ρ = 1 − ρ
W
n = 2:


2(1− ρ )
E[ S ]
=
E[ D ] pW ( 2) + 2(1− ρ )

= 1− ρ 2

22


9. Sharing systems

Relative throughput E[S]/E[D] vs. traffic load ρ

1
0.8

E[S]/E[D]

0.6

n=1

2

3

10

100


0.4
0.2
0.2

0.4

0.6

0.8

1

traffic load ρ

23


9. Sharing systems

Contents
•

Refresher: Simple teletraffic model

•
•

M/M/1-PS (∞ customers, 1 server, ∞ customer places)
M/M/n-PS (∞ customers, n servers, ∞ customer places)


•

Application to flow level modelling of elastic data traffic

•

M/M/1/k/k-PS (k customers, 1 server, k customer places)

24


9. Sharing systems

Application to flow level modelling of elastic data traffic
•

M/G/n-PS model is applicable to flow level modelling of elastic data
traffic
– customer = TCP flow

λ = flow arrival rate (flows per time unit)
– r = access link speed for a flow (data units per time unit)
– C = nr = speed of the shared link (data units per time unit)
– E[L] = average flow size (data units)
– E[S] = 1/µ = E[L]/r = average flow transfer time with access link rate
– ρ = λ/(nµ) = traffic load
A quality of service measure is the throughput
–


•

E[ L ]

r ⋅E[ S ]

r ⋅n(1− ρ )

(1− ρ )

θ = E[ D ] = E[ D ] = p ( n) + n(1− ρ ) = C ⋅ p ( n) + n(1− ρ )
W
W
25