Transcript Slaid_14

Series of lectures
“Telecommunication networks”
Lecture#14
Methods of the
queuing theory
Instructor: Prof. Nikolay Sokolov, e-mail: [email protected]
The Bonch-Bruevich Saint-Petersburg State
University of Telecommunications
Origin of the teletraffic theory
In the beginning of XX century telephone networks began to develop
actively. New problems of these networks planning have arisen. One of the
first problems lied in the channels bundle capacity calculation for given
loss probability. A.K. Erlang has derived formula which allowed solution
of this problem. It is considered, that development of the teletraffic theory
has begun exactly from the works of Erlang. The name "Erlang" was
given for the traffic intensity unit in 1946 by CCIF (predecessor to ITUT).
First switching systems operated according to algorithm with losses. This
means that in the absence of unoccupied serving device the call is lost.
Utilization of the program control permitted to introduce service
discipline with waiting. This has increased efficiency of the call serving.
Wide application of this algorithm has led to interchange of word
combination "teletraffic theory“ with “queuing theory”.
At the present time, queuing theory is widely applied in the researches of
telecommunications networks, transport systems, trade and retail field.
Classification of the queueing models (1)
In 1961 D.G. Kendall introduced the following notation for queueing
models " A / B / n ". Symbol A denotes arrival process, symbol B denotes
service (holding) time distribution, and n indicates a number of servers.
For a complete specification of a queueing system more information is
required. For these reason Kendall's notation was extended:
(14.1)
A/ B / n / K / S / X ,
where:
 K is total capacity of the system, alternatively only the number of
waiting positions,
 S is number of customers,
 X is queueing discipline.
In the first position of classification (14.1) symbol M is used most often.
This means, that incoming flow is a Poisson process. For more
complicated models symbols GI (general independent time interval,
renewal arrival process) and G (general, arbitrary distribution of time
interval, may include correlation) are used.
Classification of the queueing models (2)
In the second position one of the following symbols is usually
used: M (exponential distribution of service time), D (constant
service time), Ek (Erlang-k distribution of service time), H n
(Hyper-exponential of order n distribution of service time), G
(arbitrary distribution of service time). Occasionally other symbols
occur.
In a queueing system, demands can be served according to many
different principles. Usually applied disciplines are as follows:
 FCFS: first come – first served (it is also denoted as FIFO: first
in – first out),
 LCFS: last come – first served,
 SIRO: service in random order,
 SJF: shortest job first.
Classification of the queueing models (3)
In some cases, demands are divided into N priority classes.
There is difference of principle between two kinds of priorities:
non-preemptive and preemptive. For the first discipline a new
arriving demand with higher priority than a demand being
served waits until a server becomes idle (and all demands with
highest priority have been served). This discipline is also called
HOL: head-of-the-line. When using second discipline a demand
being served having lower priority than new arriving demand is
interrupted. Usually three types of serving the interrupted call
are discriminated:
1. preemptive, resume (the service is continued from where it
was interrupted),
2. preemptive, without re-sampling (the service restarts from
the beginning with the same service time),
3. preemptive, with re-sampling (the service restarts again with
a new service time).
Systems with losses
Y – traffic, V – number of channels, P – loss probability.
YV
P  VV ! k .
Y
 k!
k 0
If V =1:
Y
P
.
1 Y
The mean number of incoming calls (1)
Calls per minute
100
80
60
40
20
0
4
8
12
16
20
24
Time
of day
The mean number of incoming calls (2)
Calls per minute
14000
12000
10000
8000
6000
4000
2000
0
2
4
6
8
10
12
14
16
18
20
22
24
Time
of day
Flow of incoming calls
t
0
t1
t2
t3
t4
t5 t6
a) First mode
X(t)
X2(t)
X1(t)
t
0
t1
t2
t3
t4
b) Second mode
t5 t6
The mean holding time (1)
Mean holding time (s)
300
240
180
120
60
0
4
8
12
16
20
24
Time
of day
The mean holding time (2)
Mean holding time (s)
1200
1000
800
600
400
200
0
0
2
4
6
8
10
12
14
16
18
20
22
24
Time
of day
The carried traffic as a function of time
Number of busy channels
40
N(t)
30
Mean
value
20
10
Time
0
T1
T2
T3
T4
T5
Busy hour
Traffic
0
6
TBO
TMAX
Time
of day
18
24
The carried traffic as a function of time
Busy
Time
Idle
The most important characteristics of queueing system for the
telecommunications network planning are:
•mean value of the delay time,
•quantile of the delay distribution functions.
Exactly these two characteristics are standardized in ITU-T
recommendations and ETSI standards. For solution of other
problems not included in the network planning process, other
characteristics of queueing system are of interest.
Main formulas (1)
Mean value of the sojourn time is defined by the following
sum:
S (1)  W (1)  B (1) .
(14.2)
First summand is a mean value of the time that call spends
in a queue. Second summand is a mean value of call
serving time. It is obvious, that main complications are
related to calculation of the W (1) value that is the first
summand.
Laplace-Stiltjes transform of the call delay time
distribution function is evaluated in the following way:
(14.3)
S * ( s)  W * ( s) B* ( s).
Main formulas (2)
In this formula main complexities are related to the first
multiplier, which represents Laplace-Stiltjes transform of
the distribution function of waiting time.
For the calculation of W (1) in systems M / G /1 PollaczekKhintchine's formula was derived:
(2)

B
.
(14.3)
W (1) 
2(1   )
where:
  is the intensity of input traffic,
 B (2) is the second moment of the holding time
distribution,
  is the load of system.
Main formulas (3)
Value B (2) can be calculated by usage of the mean holding time B (1) and
corresponding coefficient of variation CB :


B(2)  B(1) 1  CB2 .
(14.4)
The load of system is equal to  B (1) . Sometimes, instead of value B (1) , service rate
 is used. It is associated with B (1) by simple ratio: B(1)   1 . Taking into
consideration these formulas, expression (14.12) can be rewritten:
W (1) 

 1  CB2
 B(1) .
2(1   )
For the system M / M /1 CB  1. Hence:

B (1)
W 
B ,S 
.
(1   )
1 
For the system M / D /1 CB  0 . Hence:
(1)
W
(1)


2(1   )
(1)
(1)
(1)
B ,S
(1)
(2   ) B (1)

.
2(1   )
(14.5)
(14.6)
(14.7)
Main formulas (4)
Quantile estimation implies derivation of the expression for calculation of
distribution function S (t ) . For the M / M /1 system required expression has
the following form:
(14.8)
S (t )  1  e(1 ) t .
For the model M / D /1 distribution function of waiting duration was derived
by C.D. Crommelin. Usually results of the function W (t ) calculation are
represented in graphical form. They are known as Crommelin curves.
Formula of calculation of W (t ) with B (1)   can be represented in following
form:
t 
 
[ (k  t )]k  (t k )
e
W (t )  (1   ) 
(14.9)
.
k!
k 0
Square brackets above index of summation indicate that the integer part of
the result of dividing t on  is used. Function S (t ) for the model M / D /1 is
defined by obvious relation:
0, for t  
S (t )  
(14.10)
.
W (t   ), for t  
Mean delay time
Mean delay time
B(1)
Load
0
1
ITU-T Recommendation Y.1541 (1)
ITU-T Recommendation Y.1541 (2)
ITU-T Recommendation Y.1541 (3)
ITU-T Recommendation Y.1541 (4)
ITU-T Recommendation Y.1542 (1)
ITU-T Recommendation Y.1542 (2)
ITU-T Recommendation Y.1542 (3)
Methods of the queuing theory
Questions?
Instructor: Prof. Nikolay Sokolov, e-mail: [email protected]