QoS Building Blocks

QoS Functionality at Network Edge:

• Signaling and admission control: if everything is
allowed, QoS cannot be guaranteed. Signaling is
usually needed to setup the network so that QoS
can be guaranteed. Decide how much resources to
set aside.
• Packet classification/marking (tagging): What kind
of service do you want to apply to the packet?
• Traffic shaping: traffic with a certain shape is
easier to guarantee service
• Packet classification/marking and traffic shaping is
also called traffic conditioning.
• Traffic policing: packets out of the service
agreement should be stopped at the edge.
 QoS Functionality at Routers
• Classification and scheduling: FCFS won't work,
need more advanced packet scheduling scheme
(Fair Queuing)
• Routing algorithm need to improve: find a path
that satisfies QoS constraints (QoS- policy- or
constraint based routing, traffic engineering, load
balancing).
• Buffer management.
• Traffic monitoring: find problems as early as
possible
• Traffic reshaping (at merge and fork points)
 QoS Big Picture: Control/Data Planes
Control Plane: Signaling + Admission Control or
SLA (Contracting) + Provisioning/Traffic Engineering

Router

Internetwork or WAN
Workstation Router
Router Workstation

Data Plane: Traffic conditioning (shaping, policing, marking

etc) + Traffic Classification + Scheduling, Buffer management

• QoS: set aside resources for premium services

QoS Router Functional Requirements
Differentiate between traffic
or service types so that routers
can treat some classes of
traffic differently than other
types

Treat the different classes of

traffic differently by
providing resource assurance
and service differentiation in
a network
 Outline

• Traffic Management: metering, shaping and

policing
• Buffer Management
• Link Scheduling
 Traffic Management Functions
• Traffic Measurement
• Traffic Shaping
• Traffic Policing
 Traffic Shaping
• Issue: Need traffic shaping to meet allocated
resources
• Source promises that data traffic will conform to a
particular shape
• Why describe and shape traffic?
• Network knows what to expect, can manage traffic better
• Better admission control decisions
• Network can police flows
• Bursty traffic costly to router, network
 Traffic Shaping Example

Data Queue
Flow 1

Flow 2

Data Queue
 Traffic Shapers
• Simple leaky bucket
• Isosynchronous flow: regular intervals between
packets
• Token bucket
• Bursty flow
 Simple Leaky Bucket
Data
Data packets leak from a bucket of
depth β at a rate ρ

 = bucket size
= rate data is sent onto network

Flow will never inject traffic at a rate higher than ρ incoming

traffic is bounded
- Easy to implement
- Easy for the network to police
Works well for fixed-rate flows (rate ρ), but does not work with
variable-rate (bursty) flows unless ρ is set to peak rate, which is
wasteful
Leaky Bucket
 Token Bucket
 •The counter counts tokens: increment by
 every time unit   
 
 = bucket size in tokens
= rate tokens are added
•Decrement the counter by L when a

to bucket in time unit packet of size L bytes is sent,
•Stop transmission when the counter
Data Queue
reaches 0
Data •Discards tokens (not packets) when the
C – link rate
bucket is full

Maximal output burst duration B:

CB=B  B=C – )
• Sends bursty traffic onto network
• Bucket filled with tokens at rate 
• Data transmitted when enough tokens exist
• Allows bursts, but enforces upper bound
Token Bucket

a)  A bucket holds three

tokens, five packets
waiting to be transmitted.
For a packet to be
transmitted, it must capture
and destroy one token.  
b) Three of the five packets
have gotten through, but
the other two are stuck
waiting for two more
tokens to be generated.
 Shaping Examples
(a) Input to a leaky bucket.
(b) Output from a leaky
bucket.

Output from a token bucket

with capacities of
(c) β=250 KB,
(d) β =500 KB,
(e) β =750 KB,
Link Rate – C = 25MBps
Token Rate – ρ = 2MBps
Burst duration B= β /(C – ρ)
 Leaky Bucket vs Token Bucket
• When the bucket is full…
• leaky bucket discards packets
• token bucket throws away tokens but never discards
packets
• Bursty traffic
• Leaky bucket forces bursty traffic to smooth
• Token bucket permits burstiness but bounds it. 
 Packet Marking And Classification
• Setting the bits of appropriate fields in the IP
header to specific values to distinguish one type
of IP packet from another.
• Examples:
• A packet may be distinguished by its source address,
its destination address, or a combination of both.
• Setting the DiffServ Code Point (DSCP) of the
DiffServ field of a packet to a specific value.
 Traffic Policing: Token Bucket
• Token bucket: limits input to specified Burst Size (β) and
Average Rate (ρ).
• Traffic sent over any time T less than ρ *T + β

• Excess traffic may be queued, marked Yellow, or simply

dropped
 Traffic policing
• Used to support metering and marking
• Token bucket policer can be used to mark traffic
(in-packet or out-packet)
• But for DiffServ, traffic needs to be divided into
more than two groups. For example, for AF
PHB, traffic needs to be divided into three drop
priorities.
• Hence for AF, dual token bucket is used.
 IETF Packet Marking
• Two types of markers are available:
• RFC 2697: A Single-Rate, Three-Color Marker
• Committed Information Rate (CIR),
• Committed Burst Size (CBS),
• Excess Burst Size (EBS)
• RFC 2698: A Dual-Rate, Three-Color Marker
• Peak Information Rate (PIR)
• Committed Information Rate (CIR),
• Committed Burst Size (CBS),
• Peak Burst Size (PBS)
• Suggested in the context of DiffServ
 Single-Rate Three-Color Marker
Usage:
•Mark conforming traffic with a low drop precedence
•Mark exceeding traffic with a high drop precedence
•Drop violating traffic

Definitions:
•CIR – Committed Information Rate
•CBS – Committed Burst Size (max)
•EBS – Excess Burst Size (max)
•Tc – Current size of CBS bucket
•Te – Current size of EBS bucket Mark Mark Drop
 Two-Rate Three-Color Marker
Usage:
•Mark packets within CIR as conforming
•Mark packets between CIR and PIR as exceeding
•Drop packets above the PIR

Definitions:
•CIR – Committed Rate
•PIR – Peak rate
•CBS – Committed burst size (max)
•PBS – Peak burst size (max)
•Tc – Current size of CBS bucket
•Tp – Current size of PBS bucket
Drop Mark Mark
 Traffic policing (cont.)
• Metering operates on two modes :
• Color blind mode
• Packets assumed to be uncolored
• Color-aware mode
• Packets may be colored when arriving at the meter
• Policer can demote the color by remarking the packet with
a worse color e.g. policer can change the color from yellow
to red
 DSCP Field (former IPv4 TOS field)

•By using the (until now unused) IP precedence bits, we can color packets so they can be
easily identifiable by the routers and end-nodes
 Outline

• Traffic Management: metering, shaping and

policing
• Buffer Management
• Link Scheduling
 Tail-Drop Queue

Buffer level

packet drop
Drop Probability
at buffer-full
1

Queue Length
Buffer Limit
 Bursty Loss From Drop-Tail Queuing
• TCP depends on packet loss
• Packet loss is indication of congestion
• TCP additive increase drives network into loss
• Drop-tail leads to bursty loss
• Congested link: many packets encounter full queue
• Synchronization: many connections lose packets at once

27
 Slow Feedback from Drop Tail

• Feedback comes when buffer is completely full

• … even though the buffer has been filling for a while

• Plus, the filling buffer is increasing RTT

• … making detection even slower

• Better to give early feedback

• Get a few connections to slow down before it’s too
late!

28
 Random Early Detection (RED) Queue
• Router notices that queue is getting full
• … and randomly drops packets to signal congestion
• Packet drop probability
• Drop probability increases as queue length increases
• Else, set drop probability f(avg queue length)
Probability
1
Drop

Average Queue Length

29
Random Early Detection (RED) Queue

Buffer level
TH max TH min
0

Discard Discard with increasing Do not discard

Probabilistic probability Pa
packet drop

Drop Probability
1
Pmax

Pmin
THmin THmax
Average Queue Length
 RED – Using Averaging
• RED computes average queue length
• qlen-avg = (1-w) * qlen-avg + w * qlen-curr
• Average queue length captures the notion of congestion more accurately
• Because of bursty nature of Internet traffic, queues can become full very
quickly and become empty again
• Weighted running average tries to detect long-lived congestions

Instantaneous queue
Queue length

Average queue

time
 Properties of RED
• Drops packets before queue is full
• In the hope of reducing the rates of some flows

• Tolerant of burstiness in the traffic

• By basing the decisions on average queue length

• Which of the following are true?

(A)Drops packet in proportion to each flow’s rate
(B)High-rate flows selected more often
(C)Helps desynchronize the TCP senders
(D)All of the above

32
 Problems With RED
• Hard to get tunable parameters just right
• How early to start dropping packets?
• What slope for increase in drop probability?
• What time scale for averaging queue length?

• Needs extensive design efforts (simulations and

tests)

33
 WRED (Weighted RED) Queue
RED with multiple drop profiles.
Drop Probability

1
(Note: THmin(i) =
Pmax (1/2 + i/8)*THmax
(0..7)

Average Queue Length

THmin(0) THmin(7) THmax(0…7)

(a) Default WRED Drop Probability Configuration
Drop Probability
Drop Probability

1
1
Pmax(0)
Pmax(0)

Pmax(7) Average Pmax(7) Average

Queue Queue
Length Length
THmin(0) THmin(7) THmax(0…7)
THmin(0) THmax(0) THmin(7) THmax(7)
(b) WRED case 1 (c) WRED case 2
 RIO (RED with In/Out-Profile) Queuing

Buffer level (average In_profile)

In-Profile (Green) Avg_in 0

Out-Profile (Yellow)

Avg_total
Buffer level
(average_Total) Drop Probability

1
Probabilistic
Pmax_out
packet drop

Pmax_in
Pmin_out Pmin_in
min_out min_in max_out max_in
Average Queue Length
 Outline

• Traffic Management: metering, shaping and

policing
• Buffer Management
• Link Scheduling
 First-In First-Out Scheduling
• First-in first-out scheduling
• Simple, but restrictive
• Example: two kinds of traffic
• Voice over IP needs low delay
• E-mail is not that sensitive about delay
• Voice traffic waits behind e-mail

37
 Strict Priority

• Multiple levels of priority

• Always transmit high-priority traffic, when present
• Isolation for the high-priority traffic
• Almost like it has a dedicated link
• Except for (small) delay for packet transmission of
low priority traffic (non-preemptive policy)

38
 Priority Queuing
• Classes have different priorities; class may depend on explicit
marking or other header info, eg IP source or destination, TCP
Port numbers, etc.
• Preemptive and non-preemptive versions
• Problem:
• lower priority traffic may starve
 Weighted Fair Queuing
• Round Robin: scan class queues serving one from each class that has a
non-empty queue
 Weighted Fair Queuing

• Weighted fair scheduling

• Assign each queue a fraction of the link bandwidth
• Rotate across queues on a small time scale

50% red, 25% blue, 25% green

41
 Weighted Fair Queuing (Round Robin)
Discussion
• Advantages: protection among flows
• Misbehaving flows will not affect the performance of
well-behaving flows
• Misbehaving flow – a flow that does not implement any
congestion control
• FIFO does not have such a property

• Disadvantages:
• More complex than FIFO: per flow queue/state
• Biased toward large packets – a flow receives service
proportional to the number of packets
 Generalized Processor Sharing(GPS)
• Assume a fluid model of traffic
• Visit each non-empty queue in turn (RR)
• Serve infinitesimal from each
• Leads to “max-min” fairness
• each connection gets no more than what it wants
• the excess, if any, is equally shared

GPS is un-implementable!
We cannot serve
infinitesimals, only packets
 DRR (Deficit RR) algorithm
• Choose a quantum of bits to serve from each connection in
order.
• For each Head of Line packet,
• credit := credit + quantum
• if the packet size is ≤ credit; send and save excess,
• otherwise save entire credit.
• If no packet to send, reset counter (to remain fair)
• If some packet sent: counter = min{ excess, quantum }
• Each connection has a deficit counter (to store credits) with
initial value zero.
• Easier implementation than other fair policies
• WFQ
 Deficit Round-Robin
• Packet-based implementation of the ideal Generalized Processor
Sharing
• DRR can handle variable packet size almost fairly
• 1st Round
Quantum size : 1000 A. credit 1000; count : 1000
byte B. credit 1000,
2000 1000 0
served twicecount : 200
1500 A C. credit 1000; count : 1000
• 2nd Round
500 300 B A. credit 2000;
served  count : 500
1200 C
B. credit 1000 count : 0
C. credit 2000;
Second First Head of
Round Round Queue served  count : 800
 DiffServ Packet Scheduler (1)
• Priority-based, Weight-based Packet Scheduler

priority weight

priority weight Rate-based

Rate-based
Priority
Priority scheduler
scheduler
Scheduler (WRR
priority Scheduler weight (WRRoror
WFQ)
WFQ)
priority weight

(a) Priority-based Scheduler (b) Weight-based Scheduler

 DiffServ Packet Scheduler (2)
• Hierarchical Packet Scheduler

priority
NCT1 priority
NCT0
priority shaping rate
(PIR/PBS,
EF
CIR/CBS+EBS)

Shaper
TrafficShaper
Min rate
Priority
AF4 Min rate Priority
Scheduler
Rate-based priority Scheduler

Traffic
AF3 Min rate Rate-based
scheduler
scheduler
AF2 Min rate (WRR
(WRRororWFQ)
WFQ)
AF1
priority
BE