Transcript ELE 511 – TELECOMMUNICATIONS NETWORKS

ELE 511 – TELECOMMUNICATIONS
NETWORKS
Lecturer: Dr. Thomas Afullo,
Department of Electrical Engineering,
University of Botswana,
Gaborone, Botswana.
Tel: 267-3554342; E-mail: [email protected]
Teletraffic & Queueing
Theory
Telecommunications Networks
1
ELE 511 – TELECOMMUNICATIONS
NETWORKS
• References:
• 1. R.L. Freeman: Telecommunications Transmission
Handbook, Wiley, ISBN 0-471-51816-6.
• 2. J.E. Flood: Telecommunications Switching, Traffic, and
Networks, Prentice-Hall, ISBN 0-13-033309-3.
• 3. L. Kleinrock: Queuing Systems Volume 1, Wiley.
Teletraffic & Queueing
Theory
Telecommunications Networks
2
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
•
•
INTRODUCTION
Queues and queuing systems have been the subject of considerable research
since the appearance of the first telephone systems.
The widespread use of computers in communication systems has introduced
new results on queuing networks in studies of large communication networks.
The methods of queuing networks have therefore been a basic component of
telecommunication networks. Most problems involving modeling computer
systems or data transmission networks deal with systems having multiple
resources (central processing units, channels, memories, communication
circuits, etc) to be taken into account. This complex structure leads to the study
of queuing networks rather than simple queues with a single server.
We study queues in order to be able to predict the effect of changes on the
system before we can actually implement changes on various parameters, like
a) pattern of arrivals, b) mean length of service, and c) the number of
servers.
Then we determine how these changes will affect: a) The average time
customers have to wait for service; b) The average number of waiting
customers; c) The proportion of time the facility is used.
Teletraffic & Queueing
Theory
Telecommunications Networks
3
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
•
•
•
•
•
INTRODUCTION
There are three basic elements in a queuing system:
1. The arrivals:
To describe the arrivals to a queuing system, we need to consider the statistical
patterns of the arrivals.
Possibilities include regular arrivals or irregular arrivals, with the interarrival times having some specified distribution. In such cases, we can
define the arrival rate, or the average number of arrivals per second.
2. The service mechanism:
To describe this, we need to know the number of servers and the average
duration of service time.
3. The service discipline:
Generally, the discipline is first-in-first-out (FIFO), but others are possible in
which certain customers get priority. An obvious example is accident victims
who are very seriously injured – they would jump the queue to get fast
treatment.
Teletraffic & Queueing
Theory
Telecommunications Networks
4
TELETRAFFIC & QUEUEING THEORY
•
•
INTRODUCTORY PROBABILITY THEORY
If A and B are two arbitrary events, then from the set identity:
A  B  A  A B
A  complement (A)
•
Then, probability of A or B is given by:
•
Also we get:
•
Then, from the above two equations, we have:
P  A  B   P  A  P  A B 
B   AB   A B   PB   P AB   P A B 
P A  B   P A  PB   P AB
•
If A and B are independent events, and for n mutually independent events, we
have:
P AB  P APB 
P A1 , A2 ,..., An   P A1 P A2 ...P An 
Teletraffic & Queueing
Theory
Telecommunications Networks
5
TELETRAFFIC & QUEUEING THEORY
•
•
CONDITIONAL PROBABILITY
The conditional probability that event A occurs, given that event B has
occurred, is defined as:
P A / B  
•
P AB
P B 
If A and B are independent, then:
P APB 
 P  A
P B 
P AB PB P A
P  B / A 

 P B 
P  A
P  A
P A / B  
•
Thus we obtain:
P AB  PB / AP A  P A / B PB
•
Generalizing to n events:
P A1 A2 A3 ...An   P A1 / A2 A3 ...An P A2 / A3 ..An ..P An 1 / An P An 
Teletraffic & Queueing
Theory
Telecommunications Networks
6
TELETRAFFIC & QUEUEING THEORY
•
•
CONDITIONAL PROBABILITY
If Bi, i=1,2,.. Are several events, then:
P A  P AB1   P AB2   ..  P ABN 
P A   P ABi    P A / Bi PBi 
i
•
•
i
This is called the complete probability formula, and enables us to find P(A)
assuming P(Bi) are known and P(A/Bi) can be obtained.
This leads to Baye’s formula:
PBi / A)  
•
PBi A P A / Bi PBi 

P A
P A
Using the previous formula for P(A), we obtain Baye’s formula:
PBi / A)  
P A / Bi PBi 
P A / Bi PBi 

P  A
 PA / B j P B j 
j
Teletraffic & Queueing
Theory
Telecommunications Networks
7
TELETRAFFIC & QUEUEING THEORY
•
•
•
CONDITIONAL PROBABILITY - EXAMPLES
1. A fair die is tossed twice, and events A represents even number outcome on
the first roll, and B represents an even number outcome on the second roll.
Determine P(A), P(B), and P(AB).
2. We have four urns containing a number of red or green balls, according to
the distribution shown below:
Urn
Number
1
2
3
4
•
•
•
Number of
green balls
19
3
9
9
Number of
red balls
1
2
1
1
The idea is to randomly select one of the urns and then randomly select one
ball from the chosen urn. Determine:
A) The probability that the selected ball is red.
B) The probability that the selected ball is red, given that it comes from urn 2.
Teletraffic & Queueing
Theory
Telecommunications Networks
8
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
•
•
RANDOM VARIABLES
It is often required to consider the behavior of functions defined on a sample
space and whose values are real numbers.
These functions are called random variables, where the term random refers to
the fact that the value of the function is known only after the experiment has
been performed.
The probability that a random variable, X, takes a value which does not exceed
a given number, x, is called the cumulative distribution function (CDF) of X,
denoted by F(x). Thus:
F x   PX  x,  x  
The CDF of any random variable has the following properties:
F  x   F  y , for x  y
F     0, F    1
lim F  xi   F  x , i  1
i 
Teletraffic & Queueing
Theory
Telecommunications Networks
9
TELETRAFFIC & QUEUEING THEORY
•
•
RANDOM VARIABLES
If a and b are two real numbers such that a<b, then the probability that X takes
on a value in the interval [a,b] is given by:
Pa  x  b  F b  F a 
•
If a=b, then:
•
For a continuous random variable X, F(x) is a continuous function of x; we
define the probability density function, f(x) as:
a  b  F b   F a   0
Pa  a  b   F b   F a   0
f ( x) 
•
dF ( x)
dx
According to the definition of a derivative,
F  x  x   F  x 
P x  X  x  x 
 lim
x
x
x  0
x  0
f ( x)  lim
Teletraffic & Queueing
Theory
Telecommunications Networks
10
TELETRAFFIC & QUEUEING THEORY
•
•
•
RANDOM VARIABLES
Then, when x is small, f(x)x is the probability that the random variable, X,
takes a value in the interval [x, x].
Thus, given a probability density function, f(x), the corresponding cumulative
distribution function F(x), is given by:
x
F  x    f (u )du

•
In order to ensure that F()=1, we have:

F     f (u )du  1

•
To find the probability that X falls in the interval [a,b], we have:
b
Pa  x  b   f ( x)dx
a
Teletraffic & Queueing
Theory
Telecommunications Networks
11
TELETRAFFIC & QUEUEING THEORY
•
•
DISCRETE RANDOM VARIABLES
If F(x) is constant everywhere, except at a finite set of points x1,x2,x3,.., then
the F(x) curve has the form of a staircase function, as shown below:
F(x)
f(x)
1
P1
P2
P4
P3
x
x1
•
x2
x3
x4
x
x1
x2
x3
x4
A random variable,X, that has such a CDF, F(x), is called a discrete random
variable; and assumes the values xi with probabilities Pi. Thus we have:
P X  xi   Pi
•
In the case of a discrete random variable, the PDF is called the probability
mass function (PMF), and is denoted by:
f ( x)   Pi  x  xi 
i
Teletraffic & Queueing
Theory
Telecommunications Networks
12
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
•
MOMENTS OF A RANDOM VARIABLE
Although a random variable is characterized completely by either its CDF or
PDF/PMF, such a characterization is not always possible to obtain.
Luckily, it is not always necessary to obtain a full characterization in that it is
usually sufficient to describe a random variable by a set of numbers known as
moments, that summarize the essential attributes of the random variable.
These moments are defined in terms of the CDF, but can usually be
determined directly without the knowledge of that function.
The first moment, which is called the mean or the expectation of a random
variable, X, denoted by E[X], is defined as:

Ex   xf ( x)dx

•
For a corresponding discrete random variable, X, taking values x1,x2,.. With
probabilities P1,P2,.., respectively, the mean becomes a weighted sum:
E x    xi Pi
i
Teletraffic & Queueing
Theory
Telecommunications Networks
13
TELETRAFFIC & QUEUEING THEORY
•
•
MOMENTS OF A RANDOM VARIABLE
In general, the nth moment of a continuous random variable is defined as:
E X    x

n
n
f ( x)dx

•
•
The nth moment of a discrete random variable becomes:
E X n    xin Pi
i
By far the most important moments are the first two moments. Thus, putting
n=1 gives the mean, and putting n=2 gives the second moment or the meansquare value, of X. Thus we have:
   x
EX

2
2
f ( x)dx

•
As the mean square value of a continuous random variable, and
 
E X 2   xi2 Pi
i
•
As the mean square value of a discrete random variable, X.
Teletraffic & Queueing
Theory
Telecommunications Networks
14
TELETRAFFIC & QUEUEING THEORY
•
•
CENTRAL MOMENTS OF A RANDOM VARIABLE
We also define central moments, which are simply the moments of the
difference between a random variable, X, and its mean value E[X]. Thus the
nth central moment is, for a continuous random variable X,



E  X  EX     x  EX  f ( x)dx
•
n
n

For a discrete random variable, X, the nth central moment becomes:


E  X  EX    xi  EX  Pi
n
n
i
•
The second central moment, called the variance, is extremely important in
characterizing a random variable in that it gives a measure of the spread of
the random variable around its mean. For a continuous random variable,X,
the variance is defined as:



VarX   E  X  EX     x  EX  f ( x)dx
•
2
2

In the discrete case, the variance becomes:


VarX   E  X  EX    xi  EX  Pi
2
2
i
Teletraffic & Queueing
Theory
Telecommunications Networks
15
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
CENTRAL MOMENTS OF A RANDOM VARIABLE
The square root of the variance is called the standard deviation, sxof X.
By specifying the variance, we essentially define the effective width of the
PDF or the PMF of the random variable, X, about its mean E[X].
A precise statement of this is due to Chebyshev, where the Chebyshev
inequality states that for any positive number e, we have:
s x2
P X  E  X    2
e
•
•
From this inequality, therefore, we see that the mean and variance of a random
variable give a partial description of its CDF.
Note that:

s X  VarX   E  X  EX 2
Teletraffic & Queueing
Theory
Telecommunications Networks

16
TELETRAFFIC & QUEUEING THEORY
•
•
COVARIANCE AND CORRELATION
The relationship between the second moment and the second central moment
is of interest. By definition, the variance is:

 
VarX   E  X  EX   E X 2  2 XEX   EX 
•
2
2

But we also have, for random variables a and b, and for a a constant:
Ea  b  Ea  Eb
Eab  aEb
•
Therefore:

  
VarX   E X 2  2 XEX   EX   E X 2  2 EX EX   EX 
2
 
2
VarX   E X 2  EX 
•
2
Therefore the variance of X can be obtained from the mean square value of X,
minus the square of the mean value of X.
Teletraffic & Queueing
Theory
Telecommunications Networks
17
TELETRAFFIC & QUEUEING THEORY
•
•
COVARIANCE AND CORRELATION
Let Z be a random variable which is the sum of two other random variables X
and Y. Then the variance of Z is derived as follows from the nth and central
moments of X and Y:
 
VarZ   Var X  Y   E Z 2  E Z 


2


VarZ   E  X  Y   E  X  Y   E X 2  2 XY  Y 2  E  X   E Y 
2
2
 
VarZ   E X   E  X 
 
 E Y   E Y 
2
VarZ   E X 2  2 E  XY   E Y 2  E  X   E Y   2 E  X E Y 
2
•
2
2
2
2
2
 2 E  XY   2 E  X E Y 
Then this simplifies to:
VarZ   VarX   VarY   2EXY   EX EY 
•
Clearly, the variance of a sum of random variables X and Y is only equal to the
sum of their variances if the last two terms of the last equation vanish. This
last term is called the covariance of X and Y:
CovX , Y   EXY   EX EY 
Teletraffic & Queueing
Theory
Telecommunications Networks
18
TELETRAFFIC & QUEUEING THEORY
•
•
•
COVARIANCE AND CORRELATION
The covariance is a measure of the extent to which the corresponding random
variables are correlated.
We therefore find that:
CovX , Y   0  EXY   EX EY 
•
•
That means that if the covariance between X and Y is zero, then X and Y are
uncorrelated.
If X and Y are independent random variables, then they are uncorrelated.
Teletraffic & Queueing
Theory
Telecommunications Networks
19
TELETRAFFIC & QUEUEING THEORY
•
•
•
•
•
•
GENERATING FUNCTIONS
There are many instances in practice when the quantity of interest is a sum of
independent random variables.
The mean and variance of such a sum can be obtained, as already shown, by
adding together the means and variances, respectively, of the constituent
variables.
To find the CDF or PDF of a sum of random variables is, however, a more
difficult task.
If we have a sequence of numbers {f0,f1,f2,..fk,..}, the sequence can be
converted into a single function to facilitate arithmetic manipulations.
This process of converting a sequence of numbers into a single function is
called z-transformation, and the resultant sequence is called the z-transform
of the original sequence of numbers.
The z-transform is commonly known as the generating function in
probability theory.
Teletraffic & Queueing
Theory
Telecommunications Networks
20
TELETRAFFIC & QUEUEING THEORY
•
•
GENERATING FUNCTIONS
The z-transform of a sequence{fi} is defined as:

F ( z)   f k z k
k 0
•
The z-transform possesses some interesting properties which greatly facilitate
the evaluation of parameters of a random variable. Let X and Y be two
independent random variables with respective probability mass functions fk
and gk; and let their corresponding z-transforms be F(z) and G(z). Then we
have:
af k  bg k  aF ( z )  bG ( z )
•
•
Convolution property:
If we define another random variable, H=F+G, with a probability mass
function hk, then the z-transform H(z) of hk is given by:
H ( z)  F ( z)G( z)
Teletraffic & Queueing
Theory
Telecommunications Networks
21
TELETRAFFIC & QUEUEING THEORY
•
•
GENERATING FUNCTIONS
This convolution property can be proved as follows as:

 
k 0
k  0i  0
H ( z )   hk z k    f i g k  i z k


H ( z)    fi g k i z k
l 0k 0


l 0
k i
H ( z)   fi z i  g k i z k i
H ( z )  F ( z )G ( z )
•
The following can therefore be shown, for a generating function F(z):
F ( z ) z 1  1
EX  
 
E X2
Teletraffic & Queueing
Theory
d
F ( z ) z 1
dz
d2
d
 2 F ( z ) z 1  F ( z ) z 1
dz
dz
Telecommunications Networks
22
TELETRAFFIC & QUEUEING THEORY
•
•
•
PROBABILITY DISTRIBUTION FUNCTIONS
Uniform Distribution
Consider a continuous random variable, X, that is equally likely to take any
value in a specified range. Such a variable is said to be uniformly distributed
within that range.

c, for a  x  b
f ( x)  

 0, elsewhere
•
Also, since:

b

a
 f ( x)dx   cdx  1
c 
Teletraffic & Queueing
Theory
1
ba
Telecommunications Networks
23
TELETRAFFIC & QUEUEING THEORY
•
•
•
PROBABILITY DISTRIBUTION FUNCTIONS
Uniform Distribution
The CDF is:
x
F ( x)   f (u )du


0, for x  a

 x  a 
F ( x)  
, for a  x  b
 b  a 

1, for x  b

•
The mean and variance of X are given by:

E X    x( f ( x)dx 


ab
2
 
Var X     x  E X  f ( x)dx  E X 2  E X 
2

2
b  a 
ab
Var X   c  x dx 
 
12
 2 
a
b
Teletraffic & Queueing
Theory
2
2
2
Telecommunications Networks
24
TELETRAFFIC & QUEUEING THEORY
•
•
•
PROBABILITY DISTRIBUTION FUNCTIONS
Uniform Distribution
In the discrete case, the uniform random variable X can take n discrete values,
say a,a+1, a+2, ..,b, where a is usually an integer, each with probability
1
PX  i   Pi  , i  a, a  1, a  2,..,b
n
•
The probability mass function (PMF) is given by:

1 / n a  x  b
f ( x)  

 0, elsewhere
•
The CDF is given by:
1 b
F ( x)     x  i 
n ia
Teletraffic & Queueing
Theory
Telecommunications Networks
25
TELETRAFFIC & QUEUEING THEORY
•
•
PROBABILITY DISTRIBUTION FUNCTIONS
To evaluate the mean and variance of the discrete uniformly distributed
random variable, we note that the generating function is defined by:

F ( z )   pk z k
k 0

1 n k 1
pk  1 / n  F ( z )   z  z  z 2  ..  z n
n k 1
n
dF ( z ) 1
 1  2 z  ..  nz n 1
dz
n
dF ( z )
n(n  1) (n  1)
EX  


z 1
dz
2n
2

•
The variance is:


 
Var X   E X 2  E X 
2
 
d2
d
E X  2 F ( z ) z 1  F ( z ) z 1
dz
dz
d2
1
F
(
z
)

2  (2)(3) z  ..  n(n  1) z n  2
2
n
dz
n2  1
Var X  
12
2

Teletraffic & Queueing
Theory
Telecommunications Networks

26
TELETRAFFIC & QUEUEING THEORY
•
•
EXPONENTIAL RANDOM VARIABLE
A continuous random variable X is said to be exponentially distributed with
parameter l if it has a CDF of the form:
F ( x)  1  e  lx , x  0
•
The corresponding PDF is:
f ( x) 
•
dF ( x)
 le  lx , x  0
dx
The mean value of this random variable is:

EX    xle  lx dx 
0
•
1
l
An important property of the exponential distribution is the so-called
memoryless property. That is, if a random variable is distributed
exponentially, then:
P X  t  x / X  t   P X  x ; t , x  0
Teletraffic & Queueing
Theory
Telecommunications Networks
27
TELETRAFFIC & QUEUEING THEORY
•
•
EXPONENTIAL RANDOM VARIABLE – MEMORYLESS PROPERTY
To prove the memoryless property of the exponential distribution, we use the
conditional probability formula:
P X  t  x / X  t  
Pt  X  t  x  F t  x   F (t )

P X  t 
1  F (t )
e  lt  e  l (t  x )

 1  e  lx
 lt
e
 P X  x 
•
In other words, if we interpret the random quantity as time, then knowing that
an exponentially distributed activity has been in progress for time t does not
affect the distribution of its remaining duration – it is as if the process is
starting now.
Teletraffic & Queueing
Theory
Telecommunications Networks
28
TELETRAFFIC & QUEUEING THEORY
•
•
THE GEOMETRIC DISTRIBUTION
A discrete random variable, X, is said to be geometrically distributed if it has a
probability mass function defined by:
P X  x   q x 1 p; p  1  p, x  1,2,3,..
•
•
The random variable X can be interpreted as the index x of success in an
experiment consisting of a number of independent trials, where each trial
results in a success with probability p, and failure with probability q=1-p.
The CDF is given by:
x
x
i 1
i 1
F ( x)  P( X  x)   pi  p  q i 1


F ( x)  p 1  q , x  1,2,3,..
•
x
The CDF is thus obtained from the sum of a geometric series, a characteristic
from which the distribution takes its name.
Teletraffic & Queueing
Theory
Telecommunications Networks
29
TELETRAFFIC & QUEUEING THEORY
•
THE GEOMETRIC DISTRIBUTION
•
The generating function of the random variable can be evaluated as:

p 
p 1
i
p( z )   pq z   qz   
 1
q i 1
q 1  qz 
i 1
pz
p( z ) 
1  qz

•
i 1 i
Then we can determine the mean and variance of X as:
EX  
1
p
Var X  
•
1 p
p2
Just as the exponential distribution is the only continuous distribution that has the
memoryless property, the geometric distribution is the only discrete distribution
that has this same property. Because of this, both the geometric and exponential
distributions have profound importance in queueing theory, especially in discrete
and continuous Markov chains..
Teletraffic & Queueing
Theory
Telecommunications Networks
30
TELETRAFFIC & QUEUEING THEORY
•
•
BINOMIAL DISTRIBUTION
A random variable X has a binomial distribution of order n if it takes the value
0,1,2,..,n with probability:
n
P X  k   pk    p k q n  k ; p  q  1
k 
•
The corresponding cumulative distribution function is a staircase in the
interval [0,n], given by:
n  n
F ( x)     p k q n  k ; m  x  m  1
k  0 k 
•
The generating function of this random variable is:
R( z )  1  p(1  z )
n
•
From this, we obtain the mean and variance of the binomial distribution as:
EX   np
VarX   np(1  p)
Teletraffic & Queueing
Theory
Telecommunications Networks
31
TELETRAFFIC & QUEUEING THEORY
•
•
THE POISSON DISTRIBUTION
A random variable X, taking on one of the values 0,1,2,.., is said to be a
Poisson random variable with parameter l if, for some l>0,
P  X  k   pk 
•
lk
The probability mass function is defined by the above equation since:


lk
k 0
k!
l
 pk  e 
k 0
•
•
k!
e  l , k  0,1,2,..
 e  l el  1
Then the PMF and the CDF may be written as:
f ( x)  e
l
F ( x)  e
l

lk
k 0
k!
m
lk
k 0
k!
  x  k 

, m  x  m 1
The generating function, and the mean and variance are found to be:
p( z )  el  z 1
EX   VarX   l
Teletraffic & Queueing
Theory
Telecommunications Networks
32
TELETRAFFIC & QUEUEING THEORY
•
•
THE NORMAL DISTRIBUTION
The Gaussian (or normal) distribution with mean h and variance s2 has a
probability density function given by:
f ( x) 
1
2s
2
e

 x h 
2s
2
2
,   x  
•
The probability mass function of a binomial random variable becomes more
and more normal as n becomes larger and larger.
•
A much stronger result is the Central Limit Theorem. This states that if n
random variables X1,X2,X3,..,Xn are independent, then if their sum is given by:
Y   Xi
•
i
Then the density f(y) tends to a normal curve as n. In other words, if n is
sufficiently large, then no matter what the distribution of the individual
random variables, then the distribution of their sum is Gaussian.
Teletraffic & Queueing
Theory
Telecommunications Networks
33