Transcript Introduction

CSE 550
Computer Network Design
Dr. Mohammed H. Sqalli
COE, KFUPM
Spring 2012 (Term 112)
Outline
 Queuing Models
 Application to Networks
 Traffic Flow Analysis
CSE-550-T112
Lecture Notes - 3
2
Basic Components of a Queue
1. Arrival
process
5. Customer
population
CSE-550-T112
6. Service
discipline
4. Waiting
positions
Lecture Notes - 3
2. Service time
distribution
3. Number of
servers
3
Kendall Notation A/S/m/B/K/SD
 A: Arrival process
 S: Service time distribution
 m: Number of servers
 B: Number of buffers (system capacity)
 K: Population size
 SD: Service discipline
CSE-550-T112
Lecture Notes - 3
4
Queuing Models - Notation
 The notation X/Y/N is used for queuing models
 X = distribution of the inter-arrival times
 Y = distribution of service times
 N = number of servers
 The most common distributions are:
 G = general independent arrivals or service times
 M = negative exponential distribution
 D = deterministic arrivals or fixed length service
 Example: M/M/1
CSE-550-T112
Lecture Notes - 3
5
Queuing Models - Single-server queues  M/G/1 model:
The arrival rate is Poisson and the service time is
general
M/M/1 model:
 The standard deviation is equal to the mean, the service
time distribution is exponential, i.e., service times are
essentially random
M/D/1 model:
 The standard deviation of service time is equal to zero, i.e., a
constant service time
The poorest performance is exhibited by the exponential service
time (M/M/1), and the best by a constant service time (M/D/1)
Usually, the exponential service time can be considered to be
the worst case:
 An analysis based on this assumption will give conservative
results





CSE-550-T112
Lecture Notes - 3
6
Queuing Models - Single-server queues  Coefficient of variation =

Zero: Constant service time (M/D/1)


Example: a data entry application for a particular form
Ratio close to 1: This is a common occurrence and
corresponds to exponential service time (M/M/1)


Example: all transmitted messages have the same length
Ratio less than 1: Using M/M/1 model would give answers
on the safe side: it will give queue sizes and times that are
slightly larger than they should be


σTs/Ts
Example: message sizes varying over the full range, shared
LAN, and packet-switching networks
Ratio greater than 1: Need to use the M/G/1 model and not
rely on the M/M/1 model

CSE-550-T112
Example: a system that experiences many short messages,
many long messages, and few in between
Lecture Notes - 3
7
Key Variables
1
2
l
m
m
ns
nq
n
Previous
Arrival
Time
Begin
Service
Arrival
t
w
End
Service
s
r
CSE-550-T112
Lecture Notes - 3
8
Key Variables (cont)
 t = Inter-arrival time = time between two successive arrivals.
 l = Mean arrival rate = 1/E[t]





May be a function of the state of the system,
e.g., number of jobs already in the system.
s = Service time per job.
m = Mean service rate per server = 1/E[s]
Total service rate for m servers is mm
n = Number of jobs in the system.
This is also called queue length.
Note: Queue length includes jobs currently receiving service
as well as those waiting in the queue.
CSE-550-T112
Lecture Notes - 3
9
Rules for All Queues
Rules: The following apply to G/G/m queues:
1. Stability Condition:
l < mm
Finite-population and the finite-buffer systems are
always stable.
2. Number in System versus Number in Queue:
n = nq+ ns
Notice that n, nq, and ns are random variables.
E[n]=E[nq]+E[ns]
CSE-550-T112
Lecture Notes - 3
10
Rules for All Queues (cont)
3. Number versus Time:
If jobs are not lost due to insufficient buffers,
Mean number of jobs in the system
= Arrival rate  Mean response time
4. Similarly,
Mean number of jobs in the queue
= Arrival rate  Mean waiting time
The above two Equations are known as Little's law.
5. Time in System versus Time in Queue
r=w+s
r, w, and s are random variables.
E[r] = E[w] + E[s]
CSE-550-T112
Lecture Notes - 3
11
Key Variables (cont)
 nq = Number of jobs waiting
 ns = Number of jobs receiving service
 r = Response time or the time in the system
= time waiting + time receiving service
 w = Waiting time
= Time between arrival and beginning of
service
CSE-550-T112
Lecture Notes - 3
12
Little's Law
 Mean number in the system
= Arrival rate  Mean response time
 This relationship applies to all systems or parts of
systems in which the number of jobs entering the
system is equal to those completing service.
 Named after Little (1961)
 Based on a black-box view of the system:
Arrivals
Black
Box
Departures
 In systems in which some jobs are lost due to finite
buffers, the law can be applied to the part of the
system consisting of the waiting and serving positions.
CSE-550-T112
Lecture Notes - 3
13
Proof of Little's Law
4
Job
3
number
2
1
Arrival
4
Departure
Number
3
in
System 2
1
12345678
Time
12345678
Time
 If T is large, arrivals = departures = N
 Arrival rate = Total arrivals/Total time= N/T
 Hashed areas = total time spent inside the
system by all jobs = J
 Mean time in the system= J/N
 Mean Number in the system
= J/T =
= Arrival rate X Mean time in the system
CSE-550-T112
Lecture Notes - 3
4
Time
3
in
System 2
1
1 2 3
Job number14
Application of Little's Law
Arrivals
Departures
 Applying to just the waiting facility of a service center:

Mean number in the queue = Arrival rate  Mean waiting time
 Similarly, for those currently receiving the service, we
have:

Mean number in service = Arrival rate  Mean service time
CSE-550-T112
Lecture Notes - 3
15
M/M/1 Queue
 M/M/1 queue is the most commonly used type of queues
 Used to model single processor systems or to model individual




devices in a computer system
Assumes that the interarrival times and the service times are
exponentially distributed and there is only one server.
No buffer or population size limitations and the service discipline is
FCFS
Need to know only the mean arrival rate l and the mean service
rate m.
State = number of jobs in the system
l
0
l
1
m
CSE-550-T112
l
…
2
m
l
m
j-1
j
m
Lecture Notes - 3
l
l
j+1
m
…
m
16
Results for M/M/1 Queue
 Birth-death processes with
 Probability of n jobs in the system:
CSE-550-T112
Lecture Notes - 3
17
Results for M/M/1 Queue (Cont)
 The quantity l/m is called traffic intensity and is usually
denoted by the symbol r. Thus:
 n is geometrically distributed.
 Utilization of the server
= Probability of having one or more jobs in the system:
CSE-550-T112
Lecture Notes - 3
18
Results for M/M/1 Queue (Cont)
 Mean number of jobs in the system:
 Variance of the number of jobs in the system:
CSE-550-T112
Lecture Notes - 3
19
Results for M/M/1 Queue (Cont)
 Probability of n or more jobs in the system:
 Mean response time (using the Little's law):
Mean number in the system = Arrival rate × Mean response
time
That is:
CSE-550-T112
Lecture Notes - 3
20
Results for M/M/1 Queue (Cont)
 Mean number of jobs in the queue:
 Idle  there are no jobs in the system
 Busy period = The time interval between two
successive idle intervals
CSE-550-T112
Lecture Notes - 3
21
Example
 On a network gateway, measurements show that the packets
arrive at a mean rate of 125 packets per second (pps) and the
gateway takes about two milliseconds to forward them. Using
an M/M/1 model, analyze the gateway. What is the probability
of buffer overflow if the gateway had only 13 buffers? How
many buffers do we need to keep packet loss below one packet
per million?




Arrival rate l = 125 pps
Service rate m = 1/.002 = 500 pps
Gateway Utilization r = l/m = 0.25
Probability of n packets in the gateway
= (1-r)rn = 0.75(0.25)n
CSE-550-T112
Lecture Notes - 3
22
Example (Cont)
 Mean Number of packets in the gateway
= r/(1-r) = 0.25/0.75 = 0.33
 Mean time spent in the gateway
= (1/m)/(1-r)= (1/500)/(1-0.25) = 2.66 milliseconds
 Probability of buffer overflow
P(more than 14 packets in the gateway)
= r14= 0.2514 =3.73 *10 -9
≈ 4 packets per billion packets
 To limit the probability of loss to less than 10-6:
We need about ten buffers.
CSE-550-T112
Lecture Notes - 3
23
Example (Cont)
 The last two results about buffer overflow are
approximate. Strictly speaking, the gateway
should actually be modeled as a finite buffer
M/M/1/B queue.
 However, since the utilization is low and the
number of buffers is far above the mean
queue length, the results obtained are a close
approximation.
CSE-550-T112
Lecture Notes - 3
24
Queuing Models - Single-Server Queue  λ: average number of packets arriving per second [pps]
 Utilization, fraction of time the facility is busy: ρ
= λTs
 Theoretical maximum input rate that can be handled by
the system is: λmax = 1/Ts
 Queues become very large near system saturation,
growing without bound when ρ = 1
 Practical considerations limit the input rate for a single
server to 70-90% of the theoretical maximum
 Little's formula (general relationship) : E[n] = λTr and
E[nq] = λTw
CSE-550-T112
Lecture Notes - 3
25
Queuing Models - Multiserver Queue -
 Utilization: ρ
= λTs/N
 Theoretical maximum input rate that can be handled by the
system is: λmax = N/Ts
 Traffic intensity: u = Nρ
CSE-550-T112
Lecture Notes - 3
26
Queuing Models - Multiple Single-server queues -
 Example of a Network of Queues



Traffic Partitioning
Traffic Merging
Queues in Tandem
CSE-550-T112
Lecture Notes - 3
27
Queuing Models
- Network of Queues  Jackson's theorem states that:
 In such a network of queues, each node is an
independent queuing system, with a Poisson input
determined by the principles of partitioning, merging,
and tandem queuing
 Each node may be analyzed separately from the
others using the M/M/1 or M/M/N model
 Results may be combined by ordinary statistical
methods, e.g., mean delays at each node may be
added to derive system delays
CSE-550-T112
Lecture Notes - 3
28
Application to a Packet-Switching Network
 Consider a packet-switching network:
 Consists of nodes interconnected by transmission
links
 Each node acts as the interface for zero or more
attached systems, each of which functions as a
source and destination of traffic
 Each link is seen as a service station servicing
packets
CSE-550-T112
Lecture Notes - 3
29
Inside a Router
CSE-550-T112
Lecture Notes - 3
30
Component Models
 Simplifications



Packets (requests) arrive according to a
Poisson process (exponential interarrival
times)
Infinite buffer size
Independent queues (just add delays induced
in the different queues encountered on the
path)
CSE-550-T112
Lecture Notes - 3
31
Traffic Flow Analysis - Objective
 Estimate:
 Delay
 Utilization of resources (links)
 Traffic flow across a network depends on:
 Topology
 Routing
 Traffic workload (from all traffic sources)
 Desirable topology and routing are
associated with:


CSE-550-T112
Low delays
Reasonable link utilization (no bottlenecks)
Lecture Notes - 3
32
Traffic Flow Analysis - Assumptions







Topology is fixed and stable
Links and routers are 100% reliable
Processing time at the routers is negligible
Capacity of all links is given (in bps)
Traffic workload is given Г = [γjk] (in pps)
Routing is given
Average packet size is given
CSE-550-T112
Lecture Notes - 3
33
Analyzing Throughput
 The capacity of the network can also limit the
number of connections/users it can handle for
a particular type of service
 This is determined by finding out the
narrowest available bandwidth in the path

This is the network bottleneck
 The narrowest bandwidth can be a router,
switch, or link
CSE-550-T112
Lecture Notes - 3
34
External Workload
 The external workload offered to the network is:

Where:
 γ
= total workload in packets per second
 γjk = workload between source j and destination k
 N = total number of sources and destinations
CSE-550-T112
Lecture Notes - 3
35
Internal Workload
 The internal workload on link i is:
λi = Σ

Where:


i Є jk
γjk
γjk = workload between source j and destination k
jk = path followed by packets to go from source j and
destination k
 The total internal workload is:

Where:



CSE-550-T112
λ = total load on all of the links in the network
λi = load on link i
L = total number of links
Lecture Notes - 3
36
Link Utilization
 Utilization of link i is: ρi
= λi * Tsi
 Service time for link i is: Ts = M / Bi
i
 Where:
M = Average packet length (in bits)
 Bi = Data rate on the link (in bps)
 Average service rate: μi = 1/Ts = Bi / M

i
= λi / μi = λi * M / Bi
ρb = max (ρi) – Link b is the primary bottleneck
 ρi

 Stability condition of a network is: ρb < 1
CSE-550-T112
Lecture Notes - 3
37
Path Length and Packets Waiting
 Average length for all paths:
 Average number of packets waiting and being served
for link i is:
E[ni] = λi Tri
 Number of packets waiting and being served in the
network can be expressed as (using Little's formula):
γT =
CSE-550-T112
Lecture Notes - 3
38
Link Delay
 Because we are assuming that each queue can be
treated as an independent M/M/1 model, we have:
 The service time for link i is: Ts = M / Bi ,Then:
i
CSE-550-T112
Lecture Notes - 3
39
Network Delay
 Average delay experienced by a packet through the
network:
 Putting all of the elements together, we get:
CSE-550-T112
Lecture Notes - 3
40
Applying M/M/1 Results to a Single Network Link
•Poisson packet arrivals with rate: λ = 2000 pps
•Fixed link capacity: C = 1.544 Mbps (T1 Carrier rate)
•We approximate the packet length distribution by an exponential with
mean: L = 515 bits/packet
•Thus, the service time is exponential with mean:
Ts = L/C = 0.33 ms/packet
i.e., packets are served at a rate of: μ = 1/Ts = M / C = 3000 pps
•Using our formulas for an M/M/1 queue:
ρ = λ/μ = λ*Ts = 0.67
So,
E[n] = ρ/(1- ρ) = 2 packets
and:
Tr = E[n]/ λ = 1 ms
CSE-550-T112
Lecture Notes - 3
41
Exercise 1






The problem consists of 3 Routers A, B, C, and 6 Switches, a, b, c, d, e, and f
Assume that the three Routers are connected according to a unidirectional ring
topology (A-B-C-A) and that all links have the same capacity of 2 Mbps
Assume that the Switches are connected as follows: (a, C), (b, C), (c, A), (d, A),
(e, B), (f, B)
The average packet size has been estimated equal to 2000 bits
It has also been observed that the traffic generated by the various switches is
Poissonian with rates as indicated in the following table showing the Interswitches traffic in pps:
a
b
c
d
e
f
a
-
20
50
10
30
20
b
20
-
10
20
40
60
c
50
10
-
80
20
10
d
10
20
80
-
50
50
e
30
40
20
50
-
100
f
20
60
10
50
100
-
Question: Find T, the average delay per packet
CSE-550-T112
Lecture Notes - 3
42
CSE-550-T112
Lecture Notes - 3
43
Animation of a Transmission Link
 Play with animation of a transmission link at
http://poisson.ecse.rpi.edu/~vastola/pslinks/p
erf/hing/mm1animate.html
CSE-550-T112
Lecture Notes - 3
44
References
 The Art of Computer Systems Performance
Analysis by Raj Jain, John Wiley, 1991.
http://www.cse.wustl.edu/~jain/books/perfbo
ok.htm
 William Stalling, “Queuing Analysis”, 2000
 Dr. Khalid Salah (ICS, KFUPM), CSE 550
Lecture Slides, Term 032
CSE-550-T112
Lecture Notes - 3
45