Transcript QoS Principles

IP QoS Principles
Theory and Practice
Dimitrios Kalogeras
Agenda
 Introduction – History – Background
 QoS Metrics
 QoS Architecture
 QoS Architecture Components
 Applications in Cisco Routers
2
A Bit of History
 The Internet, originally designed for U. S. government
use, offered only one service level: Best Effort.
– No guarantees of transit time or delivery
– Rudimentary prioritization was available, but it was rarely used.
 Commercialization began in early 1990’s
–
–
–
–
Private (intranet) networks using Internet technology appeared.
Commercial users began paying directly for Internet use.
Commerce sites tried to attract customers by using graphics.
Industry used the Internet and intranets for internal, shared
communications that combined previously-separate, specialized
networks -- each with its own specific technical requirements.
– New technologies (voice over the Internet, etc.) appeared,
designed to capitalize on inexpensive Internet technologies.
The Demands on Modern Networks
 Network flexibility is becoming central to enterprise
strategy
– Rapidly-changing business functions no longer carried out in
stable ways, in unchanging locations, or for long time-periods
– Network-enabled applications often crucial for meeting new
market opportunities, but there’s no time to custom-build a
network
 Traffic is bursty
 Interactive voice, video applications have stringent
bandwidth and latency demands
 Multiple application networks are being combined into
consolidated corporate utility networks
– Bandwidth contention as critical transaction traffic is squeezed by
web browsing, file transfers, or other low-priority or bulk traffic
– Latency problems as interactive voice and video are squeezed by
transaction, web browsing, file transfer, and bulk traffic
QoS Background
QoS development inspired by new types of applications
in IP environment:




5
Video Streaming Services
Video Conferencing
VoIP
Legacy SNA / DLSw
Definitions
 Quality of Service (QoS) classifies network traffic and
then ensures that some of it receives special handling.
– May track each individual dataflow (sender:receiver) separately.
– May include attempts to provide better error rates, lower
network transit time (latency), and decreased latency variation
(jitter).
 Differentiated Class of Service (CoS) is a simpler
alternative to QoS.
– Doesn't try to distinguish among individual dataflows; instead,
uses simpler methods to classify packets into one of a few
categories.
– All packets within a particular category are then handled in the
same way, with the same quality parameters.
 Policy-Based Networking provides end-to-end control.
– The rules for access and for management of network resources
are stored as policies and are managed by a policy server.
Statistical Behavior: Random
Arrival
 In random arrival, the time that each packet arrives is
completely independent of the time that any other packet
arrives.
– If the true situation is that arrivals tend to be evenly spaced, then
random arrival calculations will overestimate the queuing delay.
– If the true situation is that arrivals are bunched in groups (typical
of data flows, such as packets and acknowledgements), then
random arrival calculations will underestimate the queuing delay.
 Our intuition is usually misleading when we think of
random processes.
– We tend to assume that queue size increases linearly as the
number of customers increases.
– But, with random arrival, there is a drastic increase in queue size
as the customer arrival rate approaches 80% of the theoretical
server capacity. There’s no way to store the capacity that is
unused by late customers, but early customers increase the
queue.
Random Arrival and Intuition
Queue Length
 The surprising increase in queue length is best
shown by a graph:
Actual
Intuitive
20%
40%
60%
System Capacity
80%
Random Arrival vs. Self-Similar
 Although random arrival is very convenient
mathematically (it’s relatively simple to do random arrival
calculations), it has been shown that much data traffic is
self-similar.
– Ethernet and Internet traffic flows, in particular, are self-similar.
– The rate of initial connections is still random, however.
 Self-similar traffic shows the same pattern regardless of
changes in scale.
– Fractal geometry (e.g., a coastline) is an example.
 Self-similar traffic has a heavy tail.
– The probabilities of extremely large values (e.g., file lengths of a
gigabyte or more) don’t decrease as rapidly, as they would with
random distributions of file lengths.
– This matches real data traffic behaviours.
 Long file downloads mixed with short acknowledgements
 Compressed video with action scenes mixed with static scenes
Implications of Self-Similar Behaviour
 “If high levels of utilization are required, drastically larger
buffers are needed for self-similar traffic than would be
predicted based on classical queuing analysis [i.e.,
assuming random behaviour].” [Stallings]
Queue Length
– Combining self-similar traffic streams doesn’t quickly result in
smoother traffic patterns; it’s only at the highest levels of
aggregation that random-arrival statistics can be used.
Self-similar
Random arrival
20%
10
40%
60%
System Capacity
80%
QoS Metrics: What are we trying to control?
Four metrics are used to describe a packet’s
transmission through a network – Bandwidth,
Delay, Jitter, and Loss
Using a pipe analogy, then for each packet:
Bandwidth




11
Bandwidth is the perceived width of the pipe
Delay is the perceived length of the pipe
Jitter is the perceived variation in the length of the pipe
Loss is the perceived leakiness if the pipe
A
The path as perceived by a packet!
Delay
B
QoS Metrics – Bandwidth
The amount of bandwidth available to a packet is
affected by:
 The slowest link found in the transmission path
 The amount of congestion experienced at each hop – TCP
slow-start and windowing
 The forwarding speed of the devices in the path
 The queuing priority given to the packet flow
100 Mb/s
2Mb/s
2 Mb/s Maximum Bandwidth
12
10 Mb/s
QoS Metrics – Delay
The amount of delay experienced by a packet is the
sum of the:
 Fixed Propagation Delays
Bounded by the speed of light and the path distance
 Fixed Serialization Delays
The time required to physically place a packet onto a transmission
medium
 Variable Switching Delays
The time required by each forwarding engine to resolve the next-hop
address and egress interface for a packet
 Variable Queuing Delays
The time required by each switching engine to queue a packet for
transmission
13
QoS Metrics – Jitter
The amount of Jitter experienced by a packet is
affected by:
~214ms Serialization
Delay for a 1500-byte
packet at 56Kb/s
 Serialization delays on low-speed interfaces
 Variations in queue-depth due to congestion
 Variations in queue cycle-times induced by the service architectures –
First-Come, First-Served, for example
60B every 20ms
Voice
1500 Bytes of Data Voice
60B every 214ms
Voice
1500 Bytes of Data Voice
10 Mbps Ethernet
Voice
1500 Bytes of Data Voice
10 Mbps Ethernet
56 Kbps WAN
14
60B every 214ms
QoS Metrics – Loss
The amount of loss experienced by a packet flow is
affected by:
 Buffer exhaustion due to congestion caused by
oversubscription or rate-decoupling
 Intentional packet drops due to congestion control
mechanism such as Random Early Discard
DS-3
GE
GE
Oversubscribed
15
GE
Buffer Exhaustion
QoS Architecture Models
 Best Effort Service
 Integrated Service
 Differentiated Service
16
QoS Implementation Models
No State
Aggregated State
Per-Flow State
1. Best Effort
2. IntServ/RSVP
3. DiffServ
4. RSVP+DiffServ+MPLS
17
Best Effort Service
What exactly IP does:
 All packets treated equally
 Unpredictable bandwidth
 Unpredictable delay and jitter
18
IntServ (RFC1633)
19
Integrated Services (IntServ)
 The Integrated Services (IntServ) model builds upon Resource
Reservation Protocol (RSVP)
 Reservations are made per simplex flow
 Applications request reservations for network resources which
are granted or denied based on resource availability
 Senders specify the resource requirements via a PATH
message that is routed to the receiver
 Receivers reserve the resources with a RESV message that
follows the reverse path
RESV
Sender
Receiver
PATH
20
IntServ – Components
The Integrated Services Model can be divided into two
parts – the Control and Data Planes
Control Plane
Routing Selection
Admission Control
Reservation Setup
Reservation Table
Data Plane
Flow Identification
21
Packet Scheduler
IntServ – Components
Control Plane
 Route Selection – Identifies the route to follow for the reservation
(typically provided by the IGP processes)
 Reservation Setup – Installs the reservation state along the selected
path
 Admission Control – Ensures that resources are available before
allowing a reservation
Data Plane
 Flow Identification – Identifies the packets that belong to a given
reservation (using the packet’s 5-Tuple)
 Packet Scheduling – Enforces the reservations by queuing and
scheduling packets for transmission
22
IntServ – Service Models
Applications using IntServ can request two basic servicetypes:
 Guaranteed Service
Provides guaranteed bandwidth and queuing delays end-to-end, similar to a
virtual-circuit
Applications can expect hard-bounded bandwidth and delay
 Controlled-Load Service
Provides a Better-than-Best-Effort service, similar to a lightly-loaded network of
the required bandwidth
Applications can expect little to zero packet loss, and little to zero queuing delay
These services are mapped into policies that are applied via CB-WFQ,
LLQ, or MDRR
23
IntServ – Scaling Issues
 IntServ routers need to examine every packet to
identify and classify the microflows using the 5tuple
 IntServ routers must maintain a token-bucket per
microflow
 Guaranteed Service requires the creation of a
queue for each microflow
 Data structures must be created and maintained
for each reservation
24
DiffServ (RFC2474/2475)
25
Differentiated Services (DiffServ)
 The DiffServ Model specifies an approach that offers a
service better than Best-Effort and more scalable than
IntServ
 Traffic is classified into one of five forwarding classes at the
edge of a DiffServ network
 Forwarding classes are encoded in the Differentiated
Services Codepoint (DSCP) field of each packet’s IP header
 DiffServ routers apply pre-provisioned Per-Hop Behaviors
(PHBs) to packets according to the encoded forwarding
class
5
26
4
3
2
1
5
4
3
2
1
DiffServ – Compared to IntServ
 DiffServ allocates resources to aggregated rather than to
individual flows
 DiffServ moves the classification, policing, and marking
functions to the boundary nodes – the core simply forwards
based on aggregate class
 DiffServ defines Per-Hop forwarding behaviors, not end-toend services
 DiffServ guarantees are based on provisioning, not
reservations
 The DiffServ focus is on individual domains, rather than endto-end deployments
27
DiffSrv – The DS Field (RFC 2474)
DS field
DSCP
CU
 The DS field is composed of the 6 high-order bits of the
IP ToS field
 The DS field is functionally similar to the IPv4 TOS and
IPv6 Traffic Class fields
 The DS field is divided into three pools:
 nnnnn0 – Standards Use
 nnnn11 – Experimental / Local Use
 nnnn01 – Experimental / Local Use, possible Standards Use
 Class Selector Codepoints occupy the high-order bits
(nnn000) and map to the IPv4 Precedence bits
28
DiffSrv – Forwarding Classes
DSCP
Codepoint
000000
CS0 (DE)
001000
CS1
 Eight Class Selector Codepoints compatible
with legacy systems (CS0-7)
001010
AF11
001100
AF12
001110
AF13
 An Expedited Forwarding (EF) Class
 Four Assured Forwarding Classes, each with
three Drop Precedence (AFxy, where x=1-4, and
y=1-3)
 Packets in a higher AF Classes have a higher
transmit priority
 Packets with a higher Drop Precedence are
more likely to be dropped
010000
CS2
010010
AF21
010100
AF22
010110
AF23
011000
CS3
011010
AF31
011100
AF32
011110
AF33
100000
CS4
100010
AF41
100100
AF42
100110
AF43
101000
CS5
101110
EF
110000
CS6
111000
CS7
The DS Field can encode:
29
DiffServ – Per-Hop Behaviours
 A Per-Hop Behaviour (PHB) is an observable forwarding
behaviour of a DS node applied to all packets with the same
DSCP
 PHBs do NOT mandate any specific implementation
mechanisms
 The EF PHB should provide a low-loss, low-delay, low-jitter,
assured bandwidth service
 The AF PHBs should provide increasing levels or service
(higher bandwidth) for increasing AF levels
 The Default PHB (CS0) should be equivalent to Best-Effort
Service
 Packets within a given PHB should not be re-ordered
30
DiffServ – Boundary Nodes
DiffServ Boundary Nodes are responsible for classifying and
conditioning packets as they enter a given DiffServ Domain
Conditioning
Remarker
Classification
Classifier
Marker
Meter
Shaper
Dropper
 Classifier
 Marker
 Meter
 Remarker
 Shaper
 Dropper
31
Examine each packet and assign a Forwarding Class
Set the DS Field to match the Forwarding Class
Measure the traffic flow and compare it to the traffic profile
Remark (lower) the DS Field for out-of-profile traffic
Shape the traffic to match the traffic profile
Drop out of profile traffic
DiffServ – Summary
DiffServ Domain
Classification / Conditioning
PHB
LLQ/WRED
Premium Gold
32
Silver Bronze
The Trouble with DiffServ
 As currently formulated, DiffServ is strong on
simplicity and weak on guarantees
 Virtual wire using EF is OK, but how much can be
deployed?
 DiffServ has no topology-aware admission control
mechanism
33
RSVP-DiffServ Integration
The best of both worlds – Aggregated RSVP integrated with
DiffServ
No State
Aggregated
State
Per-Flow State
RSVP + DiffServ
Best Effort
DiffServ
Aggregated State
Firm Guarantees
Admission Control
IntServ
But – given the presence of a DiffServ
domain in a network, how do we support
RSVP End-to-End?
34
RSVP-DiffServ Integration – How?
 Routers at edge of a DS cloud perform microflow
classification, policing, and marking
• Guaranteed Load set to the EF, Controlled load set to AFx, and Best
Effort set to CS0
• Service Model to Forwarding Class mapping is arbitrary
 RSVP signaling is used in both the IntServ and DiffServ
regions for admission control
 The DiffServ core makes and manages aggregate
reservations for the DS Forwarding Classes based on the
RSVP microflow reservations
 The core then schedules and forwards packets based only
on the DS Field
35
RSVP-DiffServ Integration
Border Routers implement per-flow
classification, policing, and marking
DiffServ Region
RSVP Signaling is propagated
End-to End
The IntServ regions contain
Guaranteed or Controlled
Load Microflows
36
The DiffServ region
aggregates the flows into
DS Forwarding Classes
RSVP-DiffServ Integration – Summary
 The forwarding plane is still DiffServ
 We now make a small number of aggregated
reservations from ingress to egress
 Microflow RSVP messages are carried across the
DiffServ cloud
 Aggregate reservations are dynamically adjusted to
cover all microflows
 RSVP flow-classifiers and per-flow queues are
eliminated in the core
 Scalability is improved – only the RSVP flow states are
necessary – Tested to 10K flows
37
QoS Architecture Components
 Classification
 Coloring
 Admission Control
 Traffic Shaping/Policing
 Congestion Management
 Congestion Avoidance
 Signaling
38
Traffic Classification
 Most fundamental QoS building block
 The component of a QoS feature that recognizes
and distinguishes between different traffic
streams
 Without classification, all packets are treated the
same
39
Traffic Classification/
Admission Control Issues
 Always performed at the network perimeter
 Makes traffic conform to the internal network
policy
 Marks packets with special flags (colors)
 Colors used afterwards inside the network for
QoS management
40
Classification/
Admission Control Scheme
Meter
Admitted
Classifier
Marker
Shaper/
Policer
Packet
Dropped
41
Classification Criteria
 IP header fields
 TCP/UDP header fields
 Routing information
 Packet Content (NBAR)
i.e. HTTP, HTTPS, FTP, Napster etc.
42
Traffic Coloring Options
 IP Precedence
 DSCP
 QoS Group
 802.1p CoS
 ATM CLP
 Frame Relay DE
43
Type-of-Service (RFC791)
Precedence
Version
Length
0
44
D
T
ToS Field
R
Unused
…
Total Length
8
15
31
0
1
D
Normal Delay
Low Delay
T
Normal Throughput
High Throughput
R
Normal Reliability
High Reliability
IP Precedence Values
45
111
Network Control
110
Internetwork Control
101
Critical
100
Flash Override
011
Flash
010
Immediate
001
Priority
000
Routine
DSCP
Diffserv Code Point
DSCP (6 bits)
Class 1
Class 2
Class 3
Class 4
001010
010010
011010
100010
Medium Drop
Precedence
001100
010100
011100
100100
High Drop
Precedence
001110
010110
011110
100110
Low Drop
Precedence
46
Unused
Classification mechanisms
 MQC ( Modular Qos Command Line Interface)
 CAR ( Commited Access Rate)
47
Modular QoS CLI
Modular QoS CLI (MQC)
Command syntax introduced in 12.0(5)T
Reduces configuration steps and time
Uniform CLI across all main Cisco IOS-based
platforms
Uniform CLI structure for all QoS features
48
Basic MQC Commands
router(config)#
class-map [match-any | match-all] class-name
• 1. Create Class Map - a traffic class ( match access list, input
interface, IP Prec, DSCP, protocol (NBAR) src/dst MAC address, mpls
exp).
router(config)#
policy-map policy-map-name
• 2. Create Policy Map (Service Policy) - Associate a
class map with one or more QoS policies (bandwidth, police, queuelimit, random detect, shape, set prec, set DSCP, set mpls exp).
router(config-if)#
service-policy {input | output} policy-map-name
• 3. Attach Service Policy - Associate the policy map with an
input or output interface.
49
Basic MQC Commands
 1. Create Class Map – defines traffic selection criteria
Router(config)# class-map class1
Router(config-cmap)# match ip precedence 5
Router(config-cmap)# exit
 2. Create Policy Map- associates classes with actions
Router(config)# policy-map policy1
Router(config-pmap)# class class1
Router(config-pmap-c)# set mpls experimental 5
Router(config-pmap-c)# bandwidth 3000
Router(config-pmap-c)# queue-limit 30
Router(config-pmap)# exit
 3. Attach Service Policy – enforces policy to interfaces
Router(config)# interface e1/1
Router(config-if)# service-policy output policy1
Router(config-if)# exit
50
Classification Configuring Sample
MQC based
IOS 12.1(5)T
class-map match-all premium
match access-group name premium
!
Traffic class definitions
class-map match-any trash
match protocol napster
match protocol fasttrack
!
policy-map classify
class premium
set ip precedence priority
QoS policy definition
class trash
police 64000 conform-action set-prec-transmit 1
excess-action drop
!
ip access-list extended premium
ACL definition
permit tcp host 10.0.0.1 any eq telnet
!
interface serial 2/1
QoS Policy attached
ip unnumbered loopback 0
to interface
service-policy input classify
51
Classification Configuring Sample
CAR based
ip cef
!
interface serial 2/1
ip unnumbered loopback 0
rate-limit input access-group 100 64000 8000 8000
conform-action set-prec-transmit 1 exceed-action
set-prec-transmit 0
!
access-list 100 permit tcp host 10.0.0.1 any eq http
CAR definition
ACL definition
52
Classification Configuring Sample
Route-map based
route-map classify permit 10
match ip address 100
set ip precedence flash
!
Route-map definitions
route-map classify permit 20
match ip next-hop 1
set ip precedence priority
!
interface serial 2/1
ip unnumbered loopback 0
Route-map attached
ip policy route-map classify
to interface
!
access-list 1 permit 192.168.0.1
access-list 100 permit tcp host 10.0.0.1 any eq http
ACL definitions
53
Shaping/Policing
 Used to assign more predictive behavior to traffic
 Uses Token Bucket model
54
Token Bucket Model
Token Bucket characterizes traffic source
Tokens
v
Token Bucket main parameters:
 Token Arrival Rate - v
 Bucket Depth - Bc
 Time Interval – tc
Overflow Tokens
 Link Capacity - C
Bc
C
tc = Bc/v
Incoming
packets
Conform
Exceed
55
Token Bucket Model
 Bucket is being filled with tokens at a rate v token/sec.
 When bucket is full all the excess tokens are discarded.
 When packet of size L arrives, bucket is checked for
availability of corresponding amount of tokens.
 If several packets arrive back-to-back and there are
sufficient tokens to serve them all, they are accepted at
peak rate (usually physical link speed).
 If enough tokens available, packet is optionally colored
and accepted to the network and corresponding amount of
tokens is subtracted from the bucket.
 If not enough tokens, special action on packet is
performed.
56
Token Bucket Model
Actions performed on nonconforming packets:
 Dropped (Policing)
 Delayed in queue either FIFO or WFQ (Shaping)
 Colored/Recolored
57
Token Bucket Model
Bucket depth variation effect:
Bc = 0 Constant Bit Rate (CBR)
Bc No Regulation
Bucket depth is characteristic of traffic burstiness
Maximum number of bytes transmitted over period of time t:
A(t)max = Bc+v·t
58
Excess Burst (Be)
Cisco Implementation
GTS ( Generic Traffic Shaping)
If during previous tcn-1 interval bucket Bc was not depleted (there is
no congestion), in the next interval tcn Bc+Be bytes are available for
burst.
In frame relay implementations packets admitted via Be tokens are
marked with DE bit.
59
Excess Burst (Be)
Cisco Implementation
CBTS (Class Based Traffic Shaping)
allows higher throughput in uncongested environment up to peak
rate calculated as
vPeak = vCIR(1+Be/Bc)
Peak rate can be set up manually.
60
Excess Burst (Be)
Cisco Implementation
CAR
allows RED like behavior:
 traffic fitting into Bc always conforms
 traffic fitting into Be conforms with probability proportional to
amount of tokens left in the bucket
 traffic not fitting into Be always exceeds
CAR uses the following parameters:




61
t – time period since the last packet arrival
Current Debt (Dcur) – Amount of debt during current time interval
Compound Debt (Dcomp) – Sum of all Dcur since the last drop
Actual Debt (Dact) – Amount of tokens currently borrowed
Excess Burst (Be)
Cisco Implementation
Packet of length
L arrived
Bccur – L > 0
Y
CAR Algorithm
Conform
Action
Bccur = Bccur – L
N
Dcur = L - Bccur
Bccur = 0
Dcomp = Dcomp + Dcur
Dact = Dact + Dcur
+v·t
Y
Dact > Be
N
Y
Dcomp > Be
N
62
Exceed
Action
Dcomp = 0
Shaping Configuration Sample
GTS Based
interface serial 2/1
ip unnumbered loopback 0
traffic-shape rate 64000 8000 1000 256
!
Shaper Definitions
interface serial 2/2
ip unnumbered loopback 0
traffic-shape group 100 64000 8000 8000 512
!
access-list 100 permit tcp host 10.0.0.1 any eq http
ACL definition
Shaper can be only used to control egress traffic flow!
63
Policing Configuration Sample
CAR Based
IOS 12.0(5)T
ip cef
interface serial 2/1
ip unnumbered loopback 0
rate-limit output access-group 100 64000 8000 16000
conform-action transmit excess-action drop
CAR Definitions
!
interface serial 2/2
ip unnumbered loopback 0
rate-limit input 128000 16000 32000 conform-action
transmit excess-action drop
!
access-list 100 permit tcp host 10.0.0.1 any eq http
ACL definition
Policer can be used to control ingress traffic flow!
64
Shaping/Policing Configuration
Sample
MQI Based
IOS 12.1(5)T
class-map match-all policed
match protocol http
Class definitions
class-map match-all shaped
match access-group name ftp-downloads
!
policy-map bad-boy
class policed
police 64000 8000 8000 conform-action transmit
exceed-action drop
class shaped
QoS policy definition
shape average 128000
!
interface serial 2/1
QoS Policy attached
ip unnumbered loopback 0
to interface
service-policy output bad-boy
!
ip access-list extended ftp-downloads
ACL definition
permit tcp any eq ftp-data any
65
CAR Policing Problem
Why cannot my traffic reach CIR value?
Cause: Improper setting of Bc and Be values
CAR is aggressive, as drops excessive packets and the lost data needs to
be retransmitted by upper layers (mainly TCP) after timeout. This also
causes TCP to shrink its window reducing flow throughput.
Cisco Systems recommends the following settings:
Bc = 1.5xCIR/8
Be = 2xBc
66
Congestion Management
67
Queuing
 Traffic burst may temporarily exceed
interface capacity
 Without queuing this excess traffic will
be lost
 Queuing allows bursty traffic to be
transmitted without drops
 Queuing strategy defines order in
which packets are transmitted through
egress interface
 Queuing introduced additional delay
which signals to adaptive flows (like
TCP) to back off their throughput
68
Queuing Algorithms
 FIFO
 Priority (Absolute)
 Weighted Round Robin (WRR)
 Fair
69
FIFO
 Simplest queuing method with the least CPU
overhead
 No congestion control
 Transmits packets in the order of arrival
 High volume traffic can suppress interactive flows
 Default queuing for interfaces > 2Mbps (i.e. Ethernet)
70
FIFO
FIFO average queue depth dependence on load
71
Absolute Priority Queuing
 Generic Priority Queuing
 Custom Queuing
 RTP Priority Queuing
 Low Latency Queuing (LLQ)
72
Simplest QoS Algorithm: Priority
Queuing
Stated requirement:
–“If <application> has traffic waiting,
send it next”
Commonly implemented
–Defined behavior of IP precedence
73
Priority Queuing Implementation
Approach
Identify interesting traffic
–Access lists
Place traffic in various queues
Dequeue in order of queue precedence
74
Priority Queuing (PQ)
High
Traffic
Destined
for Interface
Medium
Classify
Interface Hardware
• Ethernet
• Frame Relay
• ATM
• Serial Link
• Etc.
Normal
Low
Transmit
Queue
Output
Line
Q Length Defined
by Q Limit
Classification by:
• Protocol (IP, IPX, AppleTalk,
SNA, DecNet, Bridge, etc.)
• Incoming Interface
(EO, SO, S1, etc.)
75
Interface Buffer
Resources
Absolute Priority
Scheduling
Priority Queuing Scheme
Y
High Empty?
N
Send packet
from High
76
Y
Medium Empty?
N
Send Packet
from Medium
Y
Normal Empty?
N
Send Packet
from Normal
Y
Low Empty?
N
Send Packet
from Low
Generic PQ Drawbacks
 Needs thorough admission control
 No upper limit for each priority level
 High risk of low priority queues` starvation effect
77
Generic PQ Configuration Sample
priority-list 1 protocol ip high tcp telnet
priority-list 1 protocol ip high list 100
PQ Definition
priority-list 1 protocol ip medium lt 1000
priority-list 1 interface ethernet 0/0 medium
priority-list 1 default low
!
interface serial 2/1
ip unnumbered loopback 0
PQ Attached
priority-group 1
to Interface
!
access-list 100 permit tcp host 10.0.0.1 any eq http
ACL definition
78
Custom Queuing (CQ)
(Weighted Round Robin)
1/10
Interface Hardware
• Ethernet
• Frame Relay
• ATM
• Serial Link
• Etc.
2/10
Traffic
Destined
for Interface
3/10
Classify
2/10
Transmit
Queue
Output
Line
3/10
Up to 16
Q Length
Deferred by
Queue Limit
79
Classification by:
• Protocol (IP, IPX, AppleTalk,
SNA, DecNet, Bridge, etc.)
• Incoming interface
(EO, SO, S1, etc.)
Interface
Buffer
Resources
Link
Utilization Weighted Round
Robin Scheduling
Ratio
(byte count)
Allocate
Proportion of
Link Bandwidth)
WRR Drawbacks
 Unpredictable jitter
 Fairness significantly depends on MTU and TCP
window size
 Complex calculations to achieve desired traffic
proportions
80
CQ Byte-count Calculus
Distribute bandwidth to 3 queues with proportion x:y:z and packet sizes qx, qy, qz.
1.Calculate ax=x/qx, ay=y/qy, az=z/qz.
2.Normalize and round ax, ay, az.
ax’= round(ax/min(ax, ay, az)); ay’= round(ay/min(ax, ay, az)); az’= round(az/min(ax, ay, az)).
3.Convert obtained packet proportion into byte count
bcx = ax’·qx; bcy = ay’·qy; bcz = az’·qz.
4.Actual bandwidth share of i-th queue can be calculated with the following formula:
sharei 
bci
C
n
 bc
j 1
j
5.For better approximation obtained byte-counts can be multiplied by some positive whole
number.
Starting with IOS 12.1 CQ employs Deficit Round Robin
algorithm and there is no need in such byte-count tuning.
81
CQ Configuration Sample
queue-list 1 protocol ip 1 tcp telnet
queue-list 1 protocol ip 2 list 100
queue-list 1 protocol ip 3 udp 53
queue-list 1 interface ethernet 0/0 4
queue-list 1 queue 1 byte-count 3000
CQ List Definition
queue-list 1 queue 2 byte-count 4500
queue-list 1 queue 3 byte-count 3000
queue-list 1 queue 4 byte-count 1500
queue-list 1 default 4
!
interface serial 2/1
CQ Attached
ip unnumbered loopback 0
to Interface
custom-queue-list 1
!
access-list 100 permit tcp host 10.0.0.1 any eq http
ACL Definition
82
“Bitwise Round Robin” Fair Queuing
TDM Model
Time Division
Multiplexer
Keshav, Demers, Shenker, and Zhang
Simulates a TDM
One flow per channel
83
TDM Message Arrival Sequence
6
4
5
1
2
3
84
Time Division
Multiplexer
TDM Message Delivery Sequence
5
Time Division
Multiplexer
85
6
4
1
3
2
Fair Queuing Algorithm
Employs virtual bit-by-bit round robin model (BRR)
R


BRR dynamics are described by the equation:
t N ac (t )
i-th packet from flow  arriving at time t0 is services at
time t :
R(ti )  R(ti 0 )  Pi
Servicing of i-th packet from flow  will start at Si and finish at Fi :
Si  MAX ( Fi1 , R(ti ))
Fi  Si  Pi
Additional  parameter is added for priority assignment to inactive flows :
Bi  MAX ( Fi1 , R(ti )   )
Packets are ordered for transmission according to Bi values.
86
Fair Queuing Approach
Enqueue traffic in the sequence
the TDM would deliver it
As a result, be as fair as the TDM
87
Effects of Fair Queuing
Low-bandwidth flows get
–As much bandwidth as they can use
–Timely service
High-bandwidth flows
–Interleave traffic
–Cooperatively share bandwidth
–Absorb latency
88
What Weighting Does
In TDM
–Channel speed determines message “duration”
In WFQ
–Multiplier on message length changes
simulated message “duration”
Result:
–Flow’s “fair” share predictably unfair
89
Weighted Fair Queuing (WFQ)
Traffic
Destined
for Interface
Transmit
Queue
Classify
Configurable
Number of
Queues
90
Flow-Based Classification by:
• Source and destination address
• Protocol
• Session identifier (port/socket)
Output
Line
Weighted Fair
Scheduling
Interface Weight Determined by:
Buffer
• Requested QoS (IP Procedure, RSVP)
Resources • Frame Relay FECN, BECN, DE
(For FR Traffic)
• Flow throughput (weighted-fair)
Weighted Fair Queuing (WFQ)
 Fair bandwidth per flow allocation
 Low delay for interactive applications
 Protection from ill-behaved sources
91
Weighted Fair Queuing (WFQ)
Flow classified by the following fields:





Source address
Source port
Destination address
Destination port
ToS
Weight of each flow (queue) depends on ToS:
weight = 1/(precedence+1)
Bandwidth distributed in 1/weight proportions
92
Weighted Fair Queuing (WFQ)
 Packets are ordered according to the expected virtual departure time
of their last bit.
 Low volume flows have preference over high volume transfers.
 Low volume flow is identified as using less than its share of
bandwidth.
 The special queue length threshold value is established, after which
only low volume flows can enqueue. All the packets, that belong to
high volume flows are dropped.
93
Drawbacks of Weighted Fair
Queuing
Requires more sorting
than other approaches
94
Weighted Fair Queuing (WFQ)
Delay
FTP
Telnet
t
95
Weighted Fair Queuing (WFQ)
FTP
Delay
Telnet
t
96
WFQ Configuration Sample
interface serial 2/1
ip unnumbered loopback 0
fair-queue 32 128 0
Queue Threshold
(packets)
Number of
reservable queues
Maximal number
of queues
97
RTP Priority Queuing
 Classifies only by UDP port range
 Only even ports from the range are classified
 Establishes upper limit via integrated policer
 Excess traffic dropped during congestion periods
 RTP PQ has priority over LLQ
98
RTP PQ Configuration Sample
interface serial 2/1
ip unnumbered loopback 0
ip rtp priority 16384 16383 256
Starting UDP port
Bandwidth Limit
(kbps)
Range length
99
Low Latency Queuing (LLQ)




100
Implemented using MQI
Very rich classification criteria (class-map)
Establishes upper limit via integrated policer
Excess traffic dropped during congestion periods
LLQ Configuration Sample
IOS 12.0(5)T
class-map match-all voice
match access-group name voip
!
policy-map llq
class voip
priority 30
class class-default
fair-queue 64
!
interface serial 2/1
ip unnumbered loopback 0
service-policy output llq
!
ip access-list extended voip
permit ip host 10.0.0.1 any
101
Class definitions
LLQ policy definition
LLQ Policy attached
to interface
ACL definition
Class Based WFQ (CBWFQ)
 Based on the same algorithm as WFQ
 Weights can be manually configured
 Allows to easily specify guaranteed bandwidth
for a class
 Configuration based on Cisco MQI
102
CBWFQ Configuration Sample
IOS 12.0(5)T
103
class-map match-all premium
match access-group name premium-cust
class-map match-all low-priority
match protocol napster
!
policy-map cbwfq-sample
class premium
bandwidth 512
class low-priority
shape average 128
shape peak 512
class class-default
fair-queue 64
!
interface serial 2/1
ip unnumbered loopback 0
max-reserved-bandwidth 85
service-policy output cbwfq-sample
!
ip access-list extended premium-cust
permit ip host 10.0.0.1 any
Class definitions
Qos policy definition
QoS Policy attached
to interface
ACL definition
CBWFQ Configuration Sample
Hierarchical Design
class-map match-all premium
match access-group name premium-cust
class-map match-all voice
match ip precedence flash
!
policy-map total-shaper
class class-default
shape average 1536
service-policy class-policy
policy-map class-policy
class premium
bandwidth 512
class voice
priority 64
class class-default
fair-queue 128
104
IOS 12.1(5)T
interface fastethernet 1/0
ip unnumbered loopback 0
max-reserved-bandwidth 85
service-policy output total-shaper
!
ip access-list extended premium-cust
permit ip host 10.0.0.1 any
Hierarchical CBWFQ Limitations
 Only two levels of hierarchy are supported
 set command not supported in child policy
 Shaping allows only in parent policy
 LLQ can be configured only either in child or
parent policies but not in both
 FQ allowed only in child policy
105
Congestion Avoidance
106
Load
Global Synchronization Effect
Link Capacity
Avg. Throughput
t
107
Tail Drop and TCP Flow Control
 Packet drops from all TCP sessions
simultaneously
 High probability of multiple drops from the same
TCP session
 Uniformly distributed drops from high volume and
interactive flows
Result: Low average throughput!
108
Random Early Detection (RED)
Developed by Van Jacobson in 1993
 Starts randomly dropping packets before actual
congestion occurs
 Keeps average queue depth low
 Increases average throughput
109
Load
Global Synchronization Removed
Link Capacity
Avg. Throughput
t
110
Random Early Detection (RED)
p
p
Tail Drop
RED
1
1

Adjustable
0
111
0
qmax
qavg
 min
 max
qavg
Random Early Detection (RED)
RED Parameters:
 min – Minimal threshold after which RED starts packet drops.
Minimal recommended value is 5 packets.
 max – Maximal threshold after which all packets are dropped.
Recommended value is 2-3 times min.
  - Mark probability denominator denotes packet drop probability
at max average queue depth. Optimal value – 0.1 .
  - Exponential weighting factor determines the level of
backward value-dependence in average queue depth
calculation:
qavg = (qold · (1 - 2-)) + (qcur · 2-)
General recommendation  = 9.
112
TCP Rate Control - 1
 In TCP, the spacing of ACKs and the window size in the
ACKs controls the transmitter’s rate.
 Rate Control manipulates the ACKs as they pass through
the rate control device by:
– Adjusting the size of TCP ACK window
– Inserting new ACKs
– Re-spacing existing ACKs
 Rate Control works only with TCP; other methods, such
as Token Bucket, must be used with UDP.
 Rate Control violates the protocol layering design, as it
allows network devices to manipulate a higher-layer
protocol’s operation. Nevertheless, it usually functions
well and provides fine-grained control.
TCP Rate Control - 2
 Example:
Transmitter
Rate-control device
8000
:
w
o
wind
2000
:
w
o
wind
2000
:
w
o
wind
2000
:
w
o
wind
0
: 200
w
o
d
n
wi
Receiver
Weighted Random Early Detection
(WRED)
 Modified version of RED
 Weights determine the set of parameters: min ,
max and  .
 Weight depends on ToS field value
 Interactive flows are preserved
115
WRED Configuration Sample
Interface based
interface serial
ip unnumbered
random-detect
random-detect
random-detect
random-detect
random-detect
…
116
2/1
loopback 0
0
1
2
3
32
32
32
32
64
64
64
64
20
20
20
20
min
max

WRED Configuration Sample
MQI based
policy-map red
class class-default
random-detect
random-detect 0 32 64
random-detect 1 32 64
random-detect 2 32 64
random-detect 3 32 64
…
interface Serial2/1
ip unnumbered loopback 0
service-policy output red
min
20
20
20
20
max

WRED is incompatible with LLQ feature!
117
Link Optimization
118
Link Fragmentation and
Interleaving (LFI)
For links < 128kbps
Jumbogram
Voice
Packet
64 kbps
1500 bytes  190ms
119
Link Fragmentation and
Interleaving (LFI)
64 kbps
Supported interfaces:
 Multilink PPP
 Frame Relay DLCI
 ATM VC
120
LFI Configuration Sample
MLP version
interface virtual-template 1
ip unnumbered loopback 0
ppp multilink
ppp multilink interleave
ppp multilink fragment-delay 30
ip rtp interleave 16384 1024 512
…
121
Signaling
122
Resource Reservation Protocol
(RSVP)
 End-to-end QoS signaling protocol
 Used to establish dynamic reservations over the
network
 Always establishes simplex reservation
 Supports unicast and multicast traffic
 Actually uses WFQ and WRED mechanisms
123
Resource Reservation Protocol
(RSVP)
124
Resource Reservation Protocol
(RSVP)
125
Resource Reservation Protocol
(RSVP)
Reservation Types:
 Guaranteed Rate (uses WFQ and LLQ)
 Controlled Load (uses WRED)
126
Distinct
Shared
Explicit
Fixed Filter (FF)
Shared Explicit (SE)
Wildcard
X
Wildcard Filter (WF)
Resource Reservation Protocol
(RSVP)
127
QoS Policy Propagation over BGP
 QoS policy can be shared inside single AS or
among different ASs.
 Community attribute is usually used for color
assignments
 Prevents manual policy changes in network
devices
128
QoS Policy Propagation over BGP
129
QPPB Configuration Sample
Router A
ip bgp-community new-format
!
router bgp 10
neighbor 10.0.0.1 remote-as 20
neighbor 10.0.0.1 send-community
neighbor 10.0.0.1 route-map cout out
!
route-map cout permit 10
match ip address 20
set community 60:9
!
access-list 20 permit 192.168.0.0
0.0.0.255
130
Router B
ip bgp-community new-format
!
router bgp 20
neighbor 10.0.0.2 remote-as 10
table-map mark-pol
!
route-map mark-pol permit 10
match community 1
set ip precedence flash
!
ip community-list 1 permit 60:9
!
interface Serial 0/1
ip unnumbered loopback 0
bgp-policy source ip-prec-map
Topics not Covered
 Multiprotocol Label Switching (MPLS)
 Frame Relay QoS
 ATM QoS
 Distributed Queuing Algorithms
 Multicast
131
Conclusion
 QoS is not an exotic feature any more
 QoS allows specific applications (VoIP, VC) to
share network infrastructure with best-effort
traffic
 QoS in IP networks simplifies their
functionality avoiding Frame Relay and ATM
usage
132
Questions???
133