Traffic Behavior and Queuing in a QoS Environment

Session 1813
Traffic Behavior and
Queuing in a QoS Environment
Networking Tutorials

Prof. Dimitri P. Bertsekas

Department of Electrical Engineering
M.I.T.

Copyright © 2002 OPNET Technologies, Inc. 1

 Traffic Behavior and Queuing in a QoS Environment

Objectives
• Provide some basic understanding of queuing phenomena
• Explain the available solution approaches and associated
trade-offs
• Give guidelines on how to match applications and solutions

Copyright © 2002 OPNET Technologies, Inc. 2

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 3

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
– Performance measures
– Solution methodologies
– Queuing system concepts
– Stability and steady-state
– Causes of delay and bottlenecks
• Source models
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 4

 Traffic Behavior and Queuing in a QoS Environment

Performance Measures
• Delay
• Delay variation (jitter)
• Packet loss
• Efficient sharing of bandwidth
• Relative importance depends on traffic type (audio/video,
file transfer, interactive)
• Challenge: Provide adequate performance for (possibly)
heterogeneous traffic

Copyright © 2002 OPNET Technologies, Inc. 5

 Traffic Behavior and Queuing in a QoS Environment

Solution Methodologies
• Analytical results (formulas)
– Pros: Quick answers, insight
– Cons: Often inaccurate or inapplicable
• Explicit simulation
– Pros: Accurate and realistic models, broad applicability
– Cons: Can be slow
• Hybrid simulation
– Intermediate solution approach
– Combines advantages and disadvantages of analysis and simulation

Copyright © 2002 OPNET Technologies, Inc. 6

 Traffic Behavior and Queuing in a QoS Environment

Examples of Applications
Analytical Modeling Discrete-Event Simulation
Hybrid DES
M/G/./. & M/G/./. & Decomposition
Analysis Scenarios with Explicit
G/G/./. G/G/./. with Kleinrock DES only with
and
FIFO Priority Independence Explicit Traffic
Background
Analysis Analysis Assumption
Traffic
Single Link with FIFO Service

Best Effort Service for Standard Data Traffic Yes N/A N/A Yes Yes

Best Effort Service for LRD/Self-Similar

Yes N/A N/A Yes Yes
Behavior Traffic
"Chancing It" with Best Effort Service for
Yes N/A N/A Yes Yes
Voice, Video and Data
Single Link with QoS-Based Queueing
Using QoS to differentiate service levels for Yes (loss of
N/A N/A Yes Yes
the same type of traffic accuracy)
Using QoS to support different requirements
for different application types given as a Highly
N/A N/A Yes Yes
detailed study of setting Cisco Router approximate
queueing parameters
Network of Queues
Hop-by-hop Yes (some loss of Yes (Run time a Yes [Fast with
General network model extending the
N/A Analysis (loss accuracy - e.g., traffic function of network minimal loss of
previous QoS queueing model
of accuacy) shaping) complexity) accuracy]

Hop-by-hop Yes (Run time a Yes [Fast with

Reduction of the general model to a
N/A Analysis (loss N/A function of network minimal loss of
representative end-to-end path
of accuacy) complexity) accuracy]

Copyright © 2002 OPNET Technologies, Inc. 7

 Traffic Behavior and Queuing in a QoS Environment

Queuing System Concepts:

Arrival Rate, Occupancy, Time in the System
• Queuing system
– Data network where packets arrive, wait in various queues, receive
service at various points, and exit after some time
• Arrival rate
– Long-term number of arrivals per unit time
• Occupancy
– Number of packets in the system (averaged over a long time)
• Time in the system (delay)
– Time from packet entry to exit (averaged over many packets)

Copyright © 2002 OPNET Technologies, Inc. 8

 Traffic Behavior and Queuing in a QoS Environment

Stability and Steady-State

• A single queue system is stable if
packet arrival rate < system transmission capacity
• For a single queue, the ratio
packet arrival rate / system transmission capacity
is called the utilization factor
– Describes the loading of a queue
• In an unstable system packets accumulate in various queues
and/or get dropped
• For unstable systems with large buffers some packet delays
become very large
– Flow/admission control may be used to limit the packet arrival rate
– Prioritization of flows keeps delays bounded for the important traffic
• Stable systems with time-stationary arrival traffic approach a
steady-state
Copyright © 2002 OPNET Technologies, Inc. 9
 Traffic Behavior and Queuing in a QoS Environment

Little’s Law
• For a given arrival rate, the time in the system is proportional
to packet occupancy
N=T
where
N: average # of packets in the system
: packet arrival rate (packets per unit time)
T: average delay (time in the system) per packet
• Examples:
– On rainy days, streets and highways are more crowded
– Fast food restaurants need a smaller dining room than regular
restaurants with the same customer arrival rate
– Large buffering together with large arrival rate cause large delays

Copyright © 2002 OPNET Technologies, Inc. 10

 Traffic Behavior and Queuing in a QoS Environment

Explanation of Little’s Law

• Amusement park analogy: people arrive, spend time at
various sites, and leave
• They pay $1 per unit time in the park
• The rate at which the park earns is $N per unit time (N:
average # of people in the park)
• The rate at which people pay is $T per unit time (: traffic
arrival rate, T: time per person)
• Over a long horizon:
Rate of park earnings = Rate of people’s payment
or
N = T

Copyright © 2002 OPNET Technologies, Inc. 11

 Traffic Behavior and Queuing in a QoS Environment

Delay is Caused by Packet Interference

• If arrivals are regular or sufficiently spaced apart, no queuing
delay occurs
Time
Arrival Times
Departure
2
4
3
1
Times

Regular Traffic

Time
Arrival Times
Departure
2
4
3
1
Times
Irregular but
Spaced Apart Traffic

Copyright © 2002 OPNET Technologies, Inc. 12

 Traffic Behavior and Queuing in a QoS Environment

Burstiness Causes Interference

• Note that the departures are less bursty

Bursty Traffic
Queuing
1234Time
Delays

Copyright © 2002 OPNET Technologies, Inc. 13

 Traffic Behavior and Queuing in a QoS Environment

Burstiness Example
Different Burstiness Levels at Same Packet Rate

Source: Fei Xue and S. J. Ben Yoo, UCDavis, “On the Generation and Shaping Self-similar Traffic in Optical Packet-switched Networks”, OPNETWORK 2002
Copyright © 2002 OPNET Technologies, Inc. 14
 Traffic Behavior and Queuing in a QoS Environment

Packet Length Variation Causes Interference

Queuing Delays
Time

Regular arrivals, irregular packet lengths

Copyright © 2002 OPNET Technologies, Inc. 15

 Traffic Behavior and Queuing in a QoS Environment

High Utilization Exacerbates Interference

Queuing Delays
Time

As the work arrival rate:

(packet arrival rate * packet length)
increases, the opportunity for interference increases

Copyright © 2002 OPNET Technologies, Inc. 16

 Traffic Behavior and Queuing in a QoS Environment

Bottlenecks
• Types of bottlenecks
– At access points (flow control, prioritization, QoS enforcement needed)
– At points within the network core
– Isolated (can be analyzed in isolation)
– Interrelated (network or chain analysis needed)
• Bottlenecks result from overloads caused by:
– High load sessions, or
– Convergence of sufficient number of moderate load sessions at the
same queue

Copyright © 2002 OPNET Technologies, Inc. 17

 Traffic Behavior and Queuing in a QoS Environment

Bottlenecks Cause Shaping

Time

• The departure traffic from a bottleneck is more regular than the

arrival traffic
• The inter-departure time between two packets is at least as
large as the transmission time of the 2nd packet

Copyright © 2002 OPNET Technologies, Inc. 18

 Traffic Behavior and Queuing in a QoS Environment

Bottlenecks Cause Shaping

Incoming traffic Outgoing traffic

Exponential
inter-arrivals

gap

Bottleneck
90% utilization

Copyright © 2002 OPNET Technologies, Inc. 19

 Traffic Behavior and Queuing in a QoS Environment

Incoming traffic Outgoing traffic

Small

Medium

Bottleneck
90% utilization
Large

Copyright © 2002 OPNET Technologies, Inc. 20

 Traffic Behavior and Queuing in a QoS Environment

Packet Trains

Inter-departure times for small packets

Copyright © 2002 OPNET Technologies, Inc. 21

 Traffic Behavior and Queuing in a QoS Environment

Variable packet sizes

Histogram of inter-departure times for small packets

# of packets
Variable packet sizes

Peaks smeared

Constant packet sizes

sec

Copyright © 2002 OPNET Technologies, Inc. 22

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
– Poisson traffic
– Batch arrivals
– Example applications – voice, video, file transfer
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 23

 Traffic Behavior and Queuing in a QoS Environment

Poisson Process with Rate 

• Interarrival times are independent and

exponentially distributed
• Models well the accumulated traffic of many
independent sources
• The average interarrival time is 1/
(secs/packet), so  is the arrival rate
(packets/sec)
Interarrival
Time Times

Copyright © 2002 OPNET Technologies, Inc. 24

 Traffic Behavior and Queuing in a QoS Environment

Batch Arrivals
• Some sources transmit in packet bursts
• May be better modeled by a batch arrival process (e.g., bursts
of packets arriving according to a Poisson process)
• The case for a batch model is weaker at queues after the first,
because of shaping

Interarrival
Time Times

Copyright © 2002 OPNET Technologies, Inc. 25

 Traffic Behavior and Queuing in a QoS Environment

Markov Modulated Rate Process (MMRP)

State 0 State 1

OFF ON

Stay in each state an exponentially

distributed time,
Transmit according to different model
(e.g., Poisson, deterministic, etc) at each state

• Extension: Models with more than two states

Copyright © 2002 OPNET Technologies, Inc. 26

 Traffic Behavior and Queuing in a QoS Environment

Source Types
• Voice sources
• Video sources
• File transfers
• Web traffic
• Interactive traffic
• Different application types have different QoS requirements,
e.g., delay, jitter, loss, throughput, etc.

Copyright © 2002 OPNET Technologies, Inc. 27

 Traffic Behavior and Queuing in a QoS Environment

Source Type Properties

Characteristics QoS Model

Requirements
Voice * Alternating talk- Delay < ~150 ms * Two-state (on-off) Markov
spurts and silence Jitter < ~30 ms Modulated Rate Process (MMRP)
intervals. Packet loss < ~1% * Exponentially distributed time at
* Talk-spurts produce each state
constant packet-rate
traffic

Video * Highly bursty traffic Delay < ~ 400 ms K-state (on-off) Markov Modulated
(when encoded) Jitter < ~ 30 ms Rate Process (MMRP)
* Long range Packet loss < ~1%
dependencies

Interactive * Poisson type Zero or near-sero Poisson, Poisson with batch arrivals,
* Sometimes batch- packet loss Two-state MMRP
FTP
Delay may be
telnet arrivals, or bursty,
important
web or sometimes on-off

Copyright © 2002 OPNET Technologies, Inc. 28

 Traffic Behavior and Queuing in a QoS Environment

Typical Voice Source Behavior

Copyright © 2002 OPNET Technologies, Inc. 29

 Traffic Behavior and Queuing in a QoS Environment

MPEG1 Video Source Model

• The MPEG1 MMRP model can be extremely bursty, and has
“long range dependency” behavior due to the deterministic
frame sequence

Diagram Source: Mark W. Garrett and Walter Willinger, “Analysis, Modeling, and Generation of Self-Similar VBR Video Traffic, BELLCORE, 1994
Copyright © 2002 OPNET Technologies, Inc. 30
 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models
– Single vs. multiple-servers
– FIFO, priority, and shared servers
– Demo
• Single-queue systems
• Priority/shared service systems
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 31

 Traffic Behavior and Queuing in a QoS Environment

Device Queuing Mechanisms

• Common queue examples for IP routers
– FIFO: First In First Out
– PQ: Priority Queuing
– WFQ: Weighted Fair Queuing
– Combinations of the above
• Service types from a queuing theory standpoint
– Single server (one queue - one transmission line)
– Multiple server (one queue - several transmission lines)
– Priority server (several queues with hard priorities - one transmission
line)
– Shared server (several queues with soft priorities - one transmission
line)

Copyright © 2002 OPNET Technologies, Inc. 32

 Traffic Behavior and Queuing in a QoS Environment

Single Server FIFO

• Single transmission line serving packets on a FIFO (First-In-
First-Out) basis
• Each packet must wait for all packets found in the system to
complete transmission, before starting transmission
– Departure Time = Arrival Time + Workload Found in the System +
Transmission time
• Packets arriving to a full buffer are dropped

Arrivals
Transmission
Line

Copyright © 2002 OPNET Technologies, Inc. 33

 Traffic Behavior and Queuing in a QoS Environment

FIFO Queue
• Packets are placed on outbound link to egress device in FIFO order
– Device (router, switch) multiplexes different flows arriving on various ingress
ports onto an output buffer forming a FIFO queue

Copyright © 2002 OPNET Technologies, Inc. 34

 Traffic Behavior and Queuing in a QoS Environment

Multiple Servers
• Multiple packets are transmitted simultaneously on multiple
lines/servers
• Head of the line service: packets wait in a FIFO queue, and
when a server becomes free, the first packet goes into service

Arrivals
Transmission
Lines

Copyright © 2002 OPNET Technologies, Inc. 35

 Traffic Behavior and Queuing in a QoS Environment

Priority Servers
• Packets form priority classes (each may have several flows)
• There is a separate FIFO queue for each priority class
• Packets of lower priority start transmission only if no higher
priority packet is waiting
• Priority types:
– Non-preemptive (high priority packet must wait for a lower priority
packet found under transmission upon arrival)
– Preemptive (high priority packet does not have to wait …)
Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Interm.
High
Low
Line
Priority
Priority
Priority

Copyright © 2002 OPNET Technologies, Inc. 36

 Traffic Behavior and Queuing in a QoS Environment

Priority Queuing
• Packets are classified into separate queues
– E.g., based on source/destination IP address, source/destination TCP port, etc.
• All packets in a higher priority queue are served before a lower priority
queue is served
– Typically in routers, if a higher priority packet arrives while a lower priority
packet is being transmitted, it waits until the lower priority packet completes

Copyright © 2002 OPNET Technologies, Inc. 37

 Traffic Behavior and Queuing in a QoS Environment

Shared Servers
• Again we have multiple classes/queues, but they are served
with a “soft” priority scheme
• Round-robin
• Weighted fair queuing

Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Weight
Weight
Line
Weight1031

Copyright © 2002 OPNET Technologies, Inc. 38

 Traffic Behavior and Queuing in a QoS Environment

Round-Robin/Cyclic Service
• Round-robin serves each queue in sequence
– A queue that is empty is skipped
– Each queue when served may have limited service (at most k packets
transmitted with k = 1 or k > 1)
• Round-robin is fair for all queues (as long as some queues do
not have longer packets than others)
• Round-robin cannot be used to enforce bandwidth allocation
among the queues.

Copyright © 2002 OPNET Technologies, Inc. 39

 Traffic Behavior and Queuing in a QoS Environment

Fair Queuing
• This scheduling method is inspired by the “most fair” of methods:
– Transmit one bit from each queue in cyclic order (bit-by-bit round robin)
– Skip queues that are empty
• To approximate the bit-by-bit processing behavior, for each packet
– We calculate upon arrival its “finish time under bit-by-bit round robin”
assuming all other queues are continuously busy, and we transmit by FIFO
within each queue
– Transmit next the packet with the minimum finish time
• Important properties:
– Priority is given to short packets
– Equal bandwidth is allocated to all queues that are continuously busy
Finish
Arrival
i-1
iDeparture
-1 Time
timestimes
of Packet i

Copyright © 2002 OPNET Technologies, Inc. 40

 Traffic Behavior and Queuing in a QoS Environment

Weighted Fair Queuing

• Fair queuing cannot be used to implement bandwidth allocation and soft
priorities
• Weighted fair queuing is a variation that corrects this deficiency
– Let wk be the weight of the kth queue
– Think of round-robin with queue k transmitting wk bits upon its turn
– If all queues have always something to send, the kth queue receives bandwidth
equal to a fraction wk / i wi of the total bandwidth
• Fair queuing corresponds to wk = 1
• Priority queuing corresponds to the weights being very high as we move to
higher priorities
• Again, to deal with the segmentation problem, we approximate as follows:
For each packet:
– We calculate its “finish time” (under the weighted bit-by-bit round robin
scheme)
– We next transmit the packet with the minimum finish time

Copyright © 2002 OPNET Technologies, Inc. 41

 Traffic Behavior and Queuing in a QoS Environment

Weighted Fair Queuing Illustration

Weights:
Queue 1 = 3
Queue 2 = 1
Queue 3 = 1

Copyright © 2002 OPNET Technologies, Inc. 42

 Traffic Behavior and Queuing in a QoS Environment

Combination of Several Queuing Schemes

• Example – voice (PQ), guaranteed b/w (WFQ), Best Effort
(Cisco’s LLQ implementation)

Copyright © 2002 OPNET Technologies, Inc. 43

 Traffic Behavior and Queuing in a QoS Environment

Demo: FIFO

FIFO
Bottleneck
90% utilization

Copyright © 2002 OPNET Technologies, Inc. 44

 Traffic Behavior and Queuing in a QoS Environment

Demo: FIFO Queuing Delay

Applications have different

requirements
• Video
» delay, jitter
• FTP
» packet loss

Control beyond “best effort”

needed
• Priority Queuing (PQ)
• Weighted Fair Queuing (WFQ)

Copyright © 2002 OPNET Technologies, Inc. 45

 Traffic Behavior and Queuing in a QoS Environment

Demo: Priority Queuing (PQ)

PQ
Bottleneck
90% utilization

Copyright © 2002 OPNET Technologies, Inc. 46

 Traffic Behavior and Queuing in a QoS Environment

Demo: PQ Queuing Delays

PQ FTP

FIFO

PQ Video

Copyright © 2002 OPNET Technologies, Inc. 47

 Traffic Behavior and Queuing in a QoS Environment

Demo: Weighted Fair Queuing (WFQ)

WFQ
Bottleneck
90% utilization

Copyright © 2002 OPNET Technologies, Inc. 48

 Traffic Behavior and Queuing in a QoS Environment

Demo: WFQ Queuing Delays

PQ FTP

WFQ FTP

FIFO

WFQ/PQ Video

Copyright © 2002 OPNET Technologies, Inc. 49

 Traffic Behavior and Queuing in a QoS Environment

Queuing: Take Away Points

• Choice of queuing mechanism can have a profound effect on
performance
• To achieve desired service differentiation, appropriate queuing
mechanisms can be used
• Complex queuing mechanisms may require simulation
techniques to analyze behavior
• Improper configuration (e.g., queuing mechanism selection or
weights) may impact performance of low priority traffic

Copyright © 2002 OPNET Technologies, Inc. 50

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models (demo)
• Single-queue systems
– M/M/1……M/M/m/k
– M/G/1……G/G/1
– Demo: Analytics vs. simulation
• Priority/shared service systems
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 51

 Traffic Behavior and Queuing in a QoS Environment

M/M/1 System
• Nomenclature: M stands for “Memoryless” (a property of the
exponential distribution)
– M/M/1 stands for Poisson arrival process (which is memoryless)
– M/M/1 stands for exponentially distributed transmission times
• Assumptions:
– Arrival process is Poisson with rate packets/sec
– Packet transmission times are exponentially distributed with mean 1/
– One server
– Independent interarrival times and packet transmission times
• Transmission time is proportional to packet length
• Note 1/ is secs/packet so  is packets/sec (packet
transmission rate of the queue)
• Utilization factor: = /stable system if 1)
Copyright © 2002 OPNET Technologies, Inc. 52
 Traffic Behavior and Queuing in a QoS Environment

Delay Calculation
• Let
Q = Average time spent waiting in queue
T = Average packet delay (transmission plus queuing)
• Note that T = 1/ + Q
• Also by Little’s law
N = T and Nq = Q
where
Nq = Average number waiting in queue
• These quantities can be calculated with formulas derived by
Markov chain analysis (see references)

Copyright © 2002 OPNET Technologies, Inc. 53

 Traffic Behavior and Queuing in a QoS Environment

M/M/1 Results

• The analysis gives the steady-state probabilities of

number of packets in queue or transmission
• P{n packets} = n(1-) where = /
• From this we can get the averages:
N = /(1 - )
T = N/ = /(1 - ) = 1/( - )
N/μ
T
1
0
μ
1
λρ

Copyright © 2002 OPNET Technologies, Inc. 54

 Traffic Behavior and Queuing in a QoS Environment

Example: How Delay Scales with Bandwidth

• Occupancy and delay formulas

N = /(1 - ) T = 1/( - ) = /
• Assume:
– Traffic arrival rate  is doubled
– System transmission capacity  is doubled
• Then:
– Queue sizes stay at the same level ( stays the same)
– Packet delay is cut in half ( and are doubled
• A conclusion: In high speed networks
– propagation delay increases in importance relative to delay
– buffer size and packet loss may still be a problem

Copyright © 2002 OPNET Technologies, Inc. 55

 Traffic Behavior and Queuing in a QoS Environment

M/M/m, M/M/ System

• Same as M/M/1, but it has m (or ) servers

• In M/M/m, the packet at the head of the queue moves
to service when a server becomes free
• Qualitative result
– Delay increases to as= /mapproaches 1
• There are analytical formulas for the occupancy
probabilities and average delay of these systems

Copyright © 2002 OPNET Technologies, Inc. 56

 Traffic Behavior and Queuing in a QoS Environment

Finite Buffer Systems: M/M/m/k

• The M/M/m/k system

– Same as M/M/m, but there is buffer space for at most k
packets. Packets arriving at a full buffer are dropped
• Formulas for average delay, steady-state occupancy
probabilities, and loss probability
• The M/M/m/m system is used widely to size
telephone or circuit switching systems

Copyright © 2002 OPNET Technologies, Inc. 57

 Traffic Behavior and Queuing in a QoS Environment

Characteristics of M/M/. Systems

• Advantage: Simple analytical formulas

• Disadvantages:
– The Poisson assumption may be violated
– The exponential transmission time distribution is an
approximation at best
– Interarrival and packet transmission times may be
dependent (particularly in the network core)
– Head-of-the-line assumption precludes heterogeneous input
traffic with priorities (hard or soft)

Copyright © 2002 OPNET Technologies, Inc. 58

 Traffic Behavior and Queuing in a QoS Environment

M/G/1 System

• Same as M/M/1 but the packet transmission time

distribution is general, with given mean 1/ and
variance 2
• Utilization factor  =  /
• Pollaczek-Kinchine formula for
Average time in queue = (2 + 1/2)/2(1- )
Average delay = 1/ + (2 + 1/2)/2(1- )
• The formulas for the steady-state occupancy
probabilities are more complicated
• Insight: As 2 increases, delay increases

Copyright © 2002 OPNET Technologies, Inc. 59

 Traffic Behavior and Queuing in a QoS Environment

G/G/1 System

• Same as M/G/1 but now the packet interarrival time

distribution is also general, with mean  and
variance 2
• We still assume FIFO and independent interarrival
times and packet transmission times
• Heavy traffic approximation:
Average time in queue ~ (2 + 2)/2(1- )
• Becomes increasingly accurate as 

Copyright © 2002 OPNET Technologies, Inc. 60

 Traffic Behavior and Queuing in a QoS Environment

Demo: M/G/1

Packet inter-arrival times Capacity

exponential (0.02) sec 1 Mbps

Packet size
1250 bytes Packet size distribution:
(10000 bits) exponential
constant
lognormal
What is the average delay and queue size ?

Copyright © 2002 OPNET Technologies, Inc. 61

 Traffic Behavior and Queuing in a QoS Environment

Demo: M/G/1 Analytical Results

Packet Size
Delay T (sec) Queue Size (packets)
Distribution
Exponential
mean = 10000 0.02 1.0
variance = 1.0 *108
Constant
mean = 10000 0.015 0.75
variance = N/A
Lognormal
mean = 10000 0.06 3.0
variance = 9.0 *108

Copyright © 2002 OPNET Technologies, Inc. 62

 Traffic Behavior and Queuing in a QoS Environment

Demo: M/G/1 Simulation Results

Average Delay (sec) Average Queue Size (packets)

Copyright © 2002 OPNET Technologies, Inc. 63

 Traffic Behavior and Queuing in a QoS Environment

Demo: M/G/1 Limitations

Application traffic mix not memoryless

• Video
» constant packet inter-arrivals
• Http
» bursty traffic

Delay

P-K formula

Simulation

Copyright © 2002 OPNET Technologies, Inc. 64

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
– Preemptive vs. non-preemptive
– Cyclic, WFQ, PQ systems
– Demo: Simulation results
• Networks of queues
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 65

 Traffic Behavior and Queuing in a QoS Environment

Non-preemptive Priority Systems

• We distinguish between different classes of traffic (flows)
• Non-preemptive priority: packet under transmission is not
preempted by a packet of higher priority
• P-K formula for delay generalizes

Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Interm.
High
Low
Line
Priority
Priority
Priority

Copyright © 2002 OPNET Technologies, Inc. 66

 Traffic Behavior and Queuing in a QoS Environment

Cyclic Service Systems

• Multiple flows, each with its own queue
• Fair system: Each flow gets access to the transmission line in
turn
• Several possible assumptions about how many packets each
flow can transmit when it gets access
• Formulas for delay under M/G/1 type assumptions are
available

Transmission
Class 1
3
2
Arrivals
Line

Copyright © 2002 OPNET Technologies, Inc. 67

 Traffic Behavior and Queuing in a QoS Environment

Weighted Fair Queuing

• A combination of priority and cyclic service
• No exact analytical formulas are available

Copyright © 2002 OPNET Technologies, Inc. 68

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
• Networks of queues
– Violation of M/M/. assumptions
– Effects on delays and traffic shaping
– Analytical approximations
• Hybrid simulation (demo)

Copyright © 2002 OPNET Technologies, Inc. 69

 Traffic Behavior and Queuing in a QoS Environment

Two Queues in Series

• First queue shapes the traffic into second queue
• Arrival times and packet lengths are correlated
• M/M/1 and M/G/1 formulas yield significant error for second
queue
First Queue
Second
Time
Time
Queue

Copyright © 2002 OPNET Technologies, Inc. 70

 Traffic Behavior and Queuing in a QoS Environment

Two bottlenecks in series

Exponential
inter-arrivals

Bottleneck Bottleneck

No queuing delay
Delay

Copyright © 2002 OPNET Technologies, Inc. 71

 Traffic Behavior and Queuing in a QoS Environment

Approximations
• Kleinrock independence approximation
– Perform a delay calculation in each queue independently of other
queues
– Add the results (including propagation delay)
• Note: In the preceding example, the Kleinrock independence
approximation overestimates the queuing delay by 100%
• Tends to be more accurate in networks with “lots of traffic
mixing”, e.g., nodes serving many relatively small flows from
several different locations

Copyright © 2002 OPNET Technologies, Inc. 72

 Traffic Behavior and Queuing in a QoS Environment

Outline
• Basic concepts
• Source models
• Service models (demo)
• Single-queue systems
• Priority/shared service systems
• Networks of queues
• Hybrid simulation
– Explicit vs. aggregated traffic
– Conceptual Framework
– Demo: PQ and WFQ with aggregated traffic

Copyright © 2002 OPNET Technologies, Inc. 73

 Traffic Behavior and Queuing in a QoS Environment

Basic Concepts of Hybrid Simulation

• Aims to combine the best of analytical results and simulation
• Achieve significant gain in simulation speed with little loss of
accuracy
• Divides the traffic through a node into explicit and
background
– Explicit traffic is simulated accurately
– Background traffic is aggregated
• The interaction of explicit and background is modeled either
analytically or through a “fast” simulation (or a combination)
Background
Explicit

Copyright © 2002 OPNET Technologies, Inc. 74

 Traffic Behavior and Queuing in a QoS Environment

Explicit Traffic
• Modeled in detail, including the effects of various protocols
• Each packet’s arrival and departure times are recorded (together
with other data of interest, e.g., loss, etc.) along each link that it
traverses
• Departure times at a link are the arrival times at the next link (plus
propagation delay)
• Objective: At each link, given the arrival times (and the packet
lengths), determine the departure times

.. .
Arrival
Departure
Time
a
d
Delay
1
4
2
3 times
times
at aatlink
the link

Copyright © 2002 OPNET Technologies, Inc. 75

 Traffic Behavior and Queuing in a QoS Environment

Aggregated Traffic
• Simplified modeling
– We don’t keep track of individual packets, only workload counts
(number of packets or bytes)
– We “generate” workload counts
» by probabilistic/analytical modeling, or
» by simplified simulation
• Aggregated (or background) traffic is local (per link)
• Shaping effects are complex to incorporate
• Some dependences between explicit and background traffic
along a chain of links are complicated and are ignored

Copyright © 2002 OPNET Technologies, Inc. 76

 Traffic Behavior and Queuing in a QoS Environment

Hybrid Simulation (FIFO Links): Conceptual

Framework
• Given the arrival time ak of the kth explicit packet
• Generate the workload wk found in queue by the kth packet
• From ak and wk generate the departure time of the kth packet as
Departure Time dk = ak + wk + sk
where sk is the transmission time of the kth packet
ARRIVAL TIMES
Explicit Explicit

aK wK a K+1 w K+1
Time

Background Background
Explicit Explicit
d K = aK + wK + sK

Copyright © 2002 OPNET Technologies, Inc.

DEPARTURE TIMES 77
 Traffic Behavior and Queuing in a QoS Environment

Simulating the Background Traffic Effects

• Use a traffic descriptor for the background traffic (e.g., carried
by special packets)
• Traffic descriptor includes:
– Traffic volume information (e.g., packets/sec, bits/sec)
– Probability distribution of interarrival times
– Probability distribution of packet lengths
– Time interval of validity of the descriptor
• Generate wk using one of several ideas and combinations
thereof
– Successive sampling (for FIFO case)
– Steady-state queue length distribution (if we can get it)
– Simplified simulation (microsim - applies to complex queuing
disciplines)

Copyright © 2002 OPNET Technologies, Inc. 78

 Traffic Behavior and Queuing in a QoS Environment

Hybrid Simulation (FIFO Case)

• Critical Question: Given arrival times a k and ak+1, workload wk, and background
traffic descriptor, how do we find wk+1?
Arrival times/Workload found

a1 w1 a2 w2 a3 w
. . .
3

.. . Time

d1 = a1 + w1 + s1 d2 = a2 + w2 + s2 d3 = a3 + w3 + s3

Departure times

• Note: wk+1 consists of wk and two more terms:

– Background arrivals in interval ak+1 - ak
– (Minus) transmitted workload in interval a k+1 - ak
• Must calculate/simulate the two terms
• The first term is simulated based on the traffic descriptor of the background traffic
• The second term is easily calculated if the queue is continuously busy in a k+1 - ak
Copyright © 2002 OPNET Technologies, Inc. 79
 Traffic Behavior and Queuing in a QoS Environment

Short Interval Case (Easy Case)

• Short interval ak+1 - ak (i.e., ak+1 < dk)
• Queue is busy continuously in ak+1 - ak
• So wk+1 is quickly simulated
– Sample the background traffic arrival distribution to simulate the new
workload arrivals in ak+1 - ak
– Do the accounting (add to wk and subtract the transmitted workload in
ak+1 - ak )
Short Interval w k+1 = wk + (New bkg arrivals) - (Old bkg transmissions)

ak w k a k+1 wk+1

.. . Time

dk d k+1
Copyright © 2002 OPNET Technologies, Inc. 80
 Traffic Behavior and Queuing in a QoS Environment

Long Interval Case

• Long interval ak+1 - ak (i.e., ak+1 > dk)

• Queue may be idle during portions of the interval ak+1 - ak
• Need to generate/simulate
– The new arrivals in ak+1 - ak
– The lengths of the busy periods and the idle periods
• Can be done by sampling the background arrival distribution in each busy
period
•k+1
.. .
k Other
Time
Long
a
w
Idle
Busy
d kk+1 alternatives are possible
Periods
Periods
Interval

Copyright © 2002 OPNET Technologies, Inc. 81

 Traffic Behavior and Queuing in a QoS Environment

Steady-State Queue Length Distribution

• If the interval between two successive explicit packets is very
long, we can assume that the queue found by the second
packet is in steady state
• So, we can obtain wk+1 by sampling the steady-state
distribution
• Applies to cases where the steady-state distribution can be
found or can be reasonably approximated
– M/M/1 and other M/M/. Queues
– Some M/G/. systems

Copyright © 2002 OPNET Technologies, Inc. 82

 Traffic Behavior and Queuing in a QoS Environment

Micro Simulation: Conceptual Framework

• Handles complex queuing systems

– Micro-packets are generated to represent traffic load within the context
of the queue only (i.e., they are not transmitted to any external links)
– For long intervals, where convergence to a steady-state is likely
» Try to detect convergence during the microsim
» Estimate steady-state queue length distribution
» Sample the steady state distribution to estimate w k+1
• Microsim speeds up the simulation without sacrificing
accuracy
• Microsim provides a general framework
– Applies to non-stationary background traffic
– Applies to non-FIFO service models (with proper modification)

Copyright © 2002 OPNET Technologies, Inc. 83

 Traffic Behavior and Queuing in a QoS Environment

Examples of Applications
Analytical Modeling Discrete-Event Simulation
Hybrid DES
M/G/./. & M/G/./. & Decomposition
Analysis Scenarios with Explicit
G/G/./. G/G/./. with Kleinrock DES only with
and
FIFO Priority Independence Explicit Traffic
Background
Analysis Analysis Assumption
Traffic
Single Link with FIFO Service

Best Effort Service for Standard Data Traffic Yes N/A N/A Yes Yes

Best Effort Service for LRD/Self-Similar

Yes N/A N/A Yes Yes
Behavior Traffic
"Chancing It" with Best Effort Service for
Yes N/A N/A Yes Yes
Voice, Video and Data
Single Link with QoS-Based Queueing
Using QoS to differentiate service levels for Yes (loss of
N/A N/A Yes Yes
the same type of traffic accuracy)
Using QoS to support different requirements
for different application types given as a Highly
N/A N/A Yes Yes
detailed study of setting Cisco Router approximate
queueing parameters
Network of Queues
Hop-by-hop Yes (some loss of Yes (Run time a Yes [Fast with
General network model extending the
N/A Analysis (loss accuracy - e.g., traffic function of network minimal loss of
previous QoS queueing model
of accuacy) shaping) complexity) accuracy]

Hop-by-hop Yes (Run time a Yes [Fast with

Reduction of the general model to a
N/A Analysis (loss N/A function of network minimal loss of
representative end-to-end path
of accuacy) complexity) accuracy]

Copyright © 2002 OPNET Technologies, Inc. 84

 Traffic Behavior and Queuing in a QoS Environment

Demo End-to-end Delay: Baseline Network

Traffic modeled as
1) Explicit traffic
2) Background traffic

Copyright © 2002 OPNET Technologies, Inc. 85

 Traffic Behavior and Queuing in a QoS Environment

Target Flow: ETE delay as a function of ToS

Target flow: Seattle  Houston - modeled using explicit traffic

– Varying its Type of Service (ToS)
» Best Effort (0)
» Streaming Multimedia (4)
Copyright © 2002 OPNET Technologies, Inc. 86
 Traffic Behavior and Queuing in a QoS Environment

Explicit Simulation Results for Target Flow

– Total traffic volume

» 500 Mbps
– Time modeled
» 35 minutes
– Simulation duration
» 31 hours

Copyright © 2002 OPNET Technologies, Inc. 87

 Traffic Behavior and Queuing in a QoS Environment

Hybrid Simulation Results for Target Flow

– Total traffic volume

» 500 Mbps
– Time modeled
» 35 minutes
– Simulation duration
» 14 minutes

Copyright © 2002 OPNET Technologies, Inc. 88

 Traffic Behavior and Queuing in a QoS Environment

Comparison: Hybrid vs Explicit Simulation

Copyright © 2002 OPNET Technologies, Inc. 89

 Traffic Behavior and Queuing in a QoS Environment

References
• Networking
– Bertsekas and Gallager, Data Networks, Prentice-Hall, 1992
• Device Queuing Implementations
– Vegesna, IP Quality of Service, [Link], 2001
– [Link]
• Probability and Queuing Models
– Bertsekas and Tsitsiklis, Introduction to Probability, Athena Scientific, 2002,
[Link]
– Cohen, The Single Server Queue, North-Holland, 1992
– Takagi, Queuing Analysis: A Foundation of Performance Evaluation. (3
Volumes), North-Holland, 1991
– Gross and Harris, Fundamentals of Queuing Theory, Wiley, 1985
– Cooper, Introduction to Queuing Theory, CEEPress, 1981
• OPNET Hybrid Simulation and Micro Simulation
– See Case Studies papers in
[Link]

Copyright © 2002 OPNET Technologies, Inc. 90