Transcript Introduction to Queue theory

Computer Networks
(Graduate level)
Lecture 3: Performance
Evaluation
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Computer Network
1
Outline



Strategy
Performance factors
Queuing Theory
Univ. of Tehran
Computer Network
2
Strategies

Circuit switching: carry bit streams




Packet switching: store-and-forward messages




Connection oriented.
original telephone network
Dedicated resource.
Connectionless (IP) or connection oriented (ATM)
Internet
Shared resource.
Packet switching is the focus of computer
Networks.
Univ. of Tehran
Computer Network
3
Packet Switching
A
Source
B
R2
R1
R3
Destination
R4





It’s the method used by the Internet.
Each packet is individually routed packet-by-packet,
using the router’s local routing table.
The routers maintain no per-flow state.
Different packets may take different paths.
Several packets may arrive for the same output link at
the same time, therefore a packet switch has buffers.
Univ. of Tehran
Computer Network
4
Packet Switching
Simple router model
“4” Link 1, ingress
Choose
Egress
Link 1, egress
Link 2, ingress
Choose
Egress
Link 2, egress
Link 3, ingress
Choose
Egress
Link 3, egress
Link 4, ingress
Choose
Egress
Link 4, egress
Link 2
Link 1
R1“4”
Link 3
Link 4
Univ. of Tehran
Computer Network
5
Multiplexing (resource sharing)


Time-Division Multiplexing (TDM)
Frequency-Division Multiplexing (FDM)
L1
R1
L2
R2
L3
Univ. of Tehran
Switch 1
Switch 2
Computer Network
R3
6
Statistical Multiplexing



On-demand time-division
Schedule link on a per-packet basis
Packets from different sources interleaved on link




scheduling
fairness, quality of service
Buffer packets that are contending for the link
Buffer (queue) overflow is called congestion
…
Univ. of Tehran
Computer Network
7
Statistical Multiplexing
Basic idea
rate
One flow
rate
Two flows
Average
rate
time
rate
time
 Network traffic is bursty.
i.e. the rate changes frequently.
 Peaks from independent flows
generally occur at different times.
 Conclusion: The more flows we have,
the smoother the traffic.
Univ. of Tehran
Computer Network
Many flows
Average rates of:
1, 2, 10, 100,
1000 flows.
time
8
Packet Switches

A node in a packet switching network
incoming links
Node
outgoing links
Memory
Univ. of Tehran
Computer Network
9
Packet Switching
Statistical Multiplexing
Packets for
one output
1
Data
Hdr
2
Data
Hdr
R
R
Queue Length
X(t)
X(t)
Link rate, R
Dropped packets
B
R
N
Data


Hdr
Packet
buffer
Time
Because the buffer absorbs temporary bursts, the egress link
need not operate at rate (NxR).
But the buffer has finite size, B, so losses will occur.
Univ. of Tehran
Computer Network
10
Statistical Multiplexing
Rate
A
C
A
C
B
C
time
Rate
B
C
time
Univ. of Tehran
Computer Network
11
Statistical Multiplexing Gain
Rate
A+B
2C
R < 2C
A
R
B
time
Statistical multiplexing gain = 2C/R
Other definitions of SMG: The ratio of rates that give rise to
a particular queue occupancy, or particular loss probability.
Univ. of Tehran
Computer Network
12
Why does the Internet use
packet switching?
Efficient use of expensive links:
1.



The links are assumed to be expensive and scarce.
Packet switching allows many, bursty flows to share the
same link efficiently.
“Circuit switching is rarely used for data networks, ...
because of very inefficient use of the links” - Gallager
Resilience to failure of links & routers:
2.

”For high reliability, ... [the Internet] was to be a datagram
subnet, so if some lines and [routers] were destroyed,
messages could be ... rerouted” - Tanenbaum
Univ. of Tehran
Computer Network
13
Some Definitions






Packet length, P, is the length of a packet in bits.
Link length, L, is the length of a link in meters.
Data rate, R, is the rate at which bits can be sent, in
bits/second, or b/s.1
Propagation delay, PROP, is the time for one bit to travel
along a link of length, L.
PROP = L/c.
Transmission time, TRANSP, is the time to transmit a
packet of length P.
TRANSP = P/R.
Latency is the time from when the first bit begins
transmission, until the last bit has been received. On a
link: 1. Note that a kilobit/second, kb/s, is 1000 bits/second, not 1024 bits/second.
Latency = PROP + TRANSP.
Univ. of Tehran
Computer Network
14
Packet Switching
A
B
R2
Source
R1
R3
Destination
R4
Host A
TRANSP1
“Store-and-Forward” at each Router
TRANSP2
R1
PROP1
TRANSP3
R2
PROP2
TRANSP4
R3
Host B
PROP3
PROP4
Minimum end to end latency   (TRANSPi  PROPi )
i
Univ. of Tehran
Computer Network
15
Packet Switching vs. Message
switching
M/R
M/R
Host A
Host A
R1
R1
R2
R2
R3
R3
Host B
Latency   ( PROPi  M / Ri )
Host B
Latency  M / Rmin   PROPi
i
i
Breaking message into packets allows parallel transmission
across all links, reducing end to end latency. It also prevents
a link from being “hogged” for a long time by one message.
Univ. of Tehran
Computer Network
16
Performance Metrics

Bandwidth (throughput)



data transmitted per time unit
link versus end-to-end
notation



KB = 210 bytes
Mbps = 106 bits per second
Latency (delay)



time to send message from point A to point B
one-way versus round-trip time (RTT)
components
Latency = Propagation + Transmit + Queuing
Queuing time can be a dominant factor
Univ. of Tehran
Computer Network
17
Latency (Queuing Delay)
The egress link might not be free, packets may be queued in a buffer. If
the network is busy, packets might have to wait a long time.
Host A
TRANSP1
Q2
R1
TRANSP2
PROP1
TRANSP3
R2
PROP2
R3
Host B
TRANSP4
How can we
determine the
queuing delay?
PROP3
PROP4
Actual end to end latency   (TRANSPi  PROPi  Qi )
i
Univ. of Tehran
Computer Network
18
Queues and Queuing Delay



To understand the performance of a packet switched network,
we can think of it as a series of queues interconnected by links.
For given link rates and lengths, the only variable is the
queuing delay.
If we can understand the queuing delay, we can understand
how the network performs.
Univ. of Tehran
Computer Network
19
Queues and Queuing Delay
Cross traffic causes
congestion and variable
queuing delay.
Univ. of Tehran
Computer Network
20
A router queue
Model of router queue
A(t), l
Buffer
Server
m
D(t)
Q(t)
A(t ) : The arrival process. The number of arrivals in interval [0, t ].
l : The average rate of new arrivals in packets/second.
D(t ) : The departure process. The number of departures in interval [0, t ].
1 : The average time to service each packet.
m
Q(t ): The number of packets in the queue at time t.
Univ. of Tehran
Computer Network
21
A router queue (cont)
Model of router queue
A(t), l
Buffer
Server
m
D(t)
Q(t)
Usually buffer size is finite
State of the system depends on :
1. Packet arrival process, (Poisson, deterministic, etc)
2. Packet length distribution
3. The service discipline (FCFS, LCFS, priority, etc)
4. # of Server, service process
Univ. of Tehran
Computer Network
22
A simple deterministic model
Model of FIFO router queue
A(t), l
m
D(t)
Q(t)
•Service discipline is FIFO
•Buffer can be finite of
infinite
Properties of A(t), D(t):
 A(t), D(t) are non-decreasing
 A(t) >= D(t)
Univ. of Tehran
Computer Network
23
A simple deterministic model
bytes or “fluid”
Cumulative number of bits
that arrived up until time t.
A(t)
A(t)
Cumulative
number of bits
D(t)
Q(t)
Service
process
m
D(t)
Cumulative number of
departed bits up until time t.
Univ. of Tehran
m
time
Properties of A(t), D(t):
 A(t), D(t) are non-decreasing
 A(t) >= D(t)
Computer Network
24
Simple deterministic model
Cumulative
number of bits
d(t)
A(t)
Q(t)
D(t)
time
•Queue occupancy: Q(t) = A(t) - D(t).
•Queuing delay, d(t), is the time spent in the queue by
a bit that arrived at time t, and if the queue is served
first-come-first-served (FCFS or FIFO)
Univ. of Tehran
Computer Network
25
Example
Cumulative
number of bits
Q(t)
d(t)
100
A(t)
D(t)
0.1s
0.2s
1.0s
Example: Every second, a train of
100 bits arrive
at rate 1000b/s. The maximum
departure rate is 500b/s.
What is the average queue
occupancy?
time
Solution: During each cycle, the queue fills at rate 500b/s for 0.1s,
then drains at rate 500b/s for 0.1s.The average queue occupancy when
the queue is non-empty is therefore: (Q (t ) Q(t )  0)  0.5  (0.1 500)  25 bits.
The queue is empty for 0.8s each cycle, and so: Q (t )  (0.2  25)  (0.8  0)  5 bits.
(You'll probably have to think about this for a while...).
Univ. of Tehran
Computer Network
26
Queues with Random Arrival
Processes
1.
2.
3.
Usually, arrival processes are
complicated, so we often model them as
random processes.
The study of queues with random arrival
processes is called Queueing Theory.
Queues with random arrival processes
have some interesting properties. We’ll
consider some here.
Univ. of Tehran
Computer Network
27
Properties of queues

Time evolution of queues.

Examples




Burstiness increases delay
Determinism minimizes delay
Little’s Result.
The M/M/1 queue.
Univ. of Tehran
Computer Network
28
Time evolution of a queue
Packets
Model of FIFO router queue
A(t), l
m
D(t)
Q(t)
Packet
Arrivals:
Departures:
time
1m
Q(t)
Univ. of Tehran
Computer Network
29
Burstiness increases delay

Example 1: Periodic arrivals




Example 2:





1 packet arrives every 1 second
1 packet can depart every 1 second
Depending on when we sample the queue, it will contain
0 or 1 packets.
N packets arrive together every N seconds (same rate)
1 packet departs every second
Queue might contain 0,1, …, N packets.
Both the average queue occupancy and the variance
have increased.
In general, burstiness increases queue occupancy
(which increases queuing delay).
Univ. of Tehran
Computer Network
30
Determinism minimizes delay

Example 3: Random arrivals




Packets arrive randomly; on average, 1 packet
arrives per second.
Exactly 1 packet can depart every 1 second.
Depending on when we sample the queue, it will
contain 0, 1, 2, … packets depending on the
distribution of the arrivals.
In general, determinism minimizes delay.
i.e. random arrival processes lead to larger
delay than simple periodic arrival processes.
Univ. of Tehran
Computer Network
31
Little’s Result
L  ld
Where:
L is the average number of customers in the system
(the number in the queue + the number in service),
l is the arrival rate, in customers per second, and
d is the average time that a customer waits in the
system (time in queue + time in service).
Result holds so long as no customers are lost/dropped.
Univ. of Tehran
Computer Network
32
The Poisson process
Arrival process is Poisson
Queuing system is M/M/1, Poisson arrival, Exponential service,
with 1 server.
• Arrival process is momeryless or arrival of packets are
independent of each others
•Prob. of one arrival in Δt is λ Δt + o(Δt)
Poisson process is a simple arrival process in which:
1. Probability of k arrivals in an interval of t seconds is:
(l t ) k  l t
Pk (t ) 
e
k!
2. The expected number of arrivals in interval t is: l t.
3. Successive interarrival times are independent of each other
(i.e. arrivals are not bursty).
Univ. of Tehran
Computer Network
33
The Poisson process (cont)

Poisson process is a probability distribution
function.
Σp(k) = 1 for all k=0, 1, …

How many arrivals in t second? It is the expected
value:
Σkp(k) = λt

What is interarrival time, r, between two arrival
f(r) = λe-λr

This is the same the service time.
f(r) = μe- μr
Univ. of Tehran
Computer Network
34
The Poisson process

Why use the Poisson process?


It is the continuous time equivalent of a series of coin
tosses.
It is known to model well systems in which a large number
of independent events are aggregated together. e.g.





Arrival of new phone calls to a telephone switch
Decay of nuclear particles
“Shot noise” in an electrical circuit
It makes the math easy.
Be warned



Network traffic is very bursty!
Packet arrivals are not Poisson.
Univ.it
of models
Tehran
Networkof new flows.
But
quite well Computer
the arrival
35
An M/M/1 queue
Model of FIFO router queue
A(t), l
m
D(t)
A(t) is a Poisson process with rate l, and the time to serve each
packet is exponentially distributed with rate m, then:
 We assume the system is in steady state, or stationary, with
none time varying values.
 Pn is the probability that there are n customer in the queue
including the one in the service.
 ρ= l/m , ration of load on capacity, is utilization or traffic
intensity.
Univ. of Tehran
Computer Network
36
An M/M/1 queue (cont)
1
0
m

l
l
l
2
….
l
n-1
m
m m
l
l
n
n+1
m
m
m
Prob. that the system move
from state n-1 to n is l ,
with no departure, and probability that it moves from
state n to n-1 is m. In order the system to be in
stationary state the probability of departure and
moving state should be equal.
(l  m)Pn  lPn-1  mPn+1
Univ. of Tehran
Computer Network
37
An M/M/1 queue (cont)
1
0
m

l
l
l
2
….
l
l
n-1
m
m m
n
n+1
m
Considering the ratem of interring and leaving
the surface gives us .
Pn  mPn+1 => Pn+1= rPn => Pn = rnP0
What is the value of P0?
ΣnPn 1 => P0Σnrn =1 => P0 =1 –r
Pn =(1 –r) rn
Univ. of Tehran
Computer Network
38
An M/M/1 queue
Model of FIFO router queue
A(t), l

m
D(t)
If A(t) is a Poisson process with rate l, and the time to
serve each packet is exponentially distributed with rate
m, then:
Average delay, d 
Univ. of Tehran
1
l
; and so from Little's Result: L  l d 
m l
m l
Computer Network
39
Next Lecture: LANs



How to share the wire
How to extend to multiple segments
Assigned reading



[MB76] ETHERNET: Distributed Packet
Switching for Local Area Networks
[B+88] Measured Capacity of an Ethernet:
Myths and Reality
Chap. 2 of book (Recommended!)
Univ. of Tehran
Computer Network
40