Queue Management
Quality of Service in IP
Networks
Prof. Jean-Yves Le Boudec
Prof. Andrzej Duda
Prof. Patrick Thiran
LCA-ISC-I&C, EPFL
CH-1015 Ecublens
http://icawww.epfl.ch
Queue Management
Contents
o Principles
o Traffic shaping
l leaky bucket
l token bucket
o Scheduling strategies
l FIFO
l Priority
l Round Robin
l Fair Queueing
l RED
o IntServ
o DiffServ
Queue Management
Improving QOS in IP Networks
o IETF groups are working on proposals to provide better QOS
control in IP networks, i.e., going beyond best effort to provide
some assurance for QOS
o Work in Progress includes Differentiated Services, and Integrated
Services (RSVP)
o Simple model
for sharing and
congestion
studies:
Queue Management
Principles for QOS Guarantees
o Consider a phone application at 1Mbps and an FTP application sharing
a 1.5 Mbps link.
l bursts of FTP can congest the router and cause audio packets to be dropped.
l want to give priority to audio over FTP
o PRINCIPLE 1: Marking of packets is needed for router to
distinguish between different classes; and new router policy to treat
packets accordingly
Queue Management
Principles for QOS Guarantees (more)
o Applications misbehave (audio sends packets at a rate higher than 1Mbps
assumed above);
o PRINCIPLE 2: provide protection (isolation) for one class from other
classes
o Require Policing Mechanisms to ensure sources adhere to bandwidth
requirements; Marking and Policing need to be done at the edges:
Queue Management
Principles for QOS Guarantees (more)
o Alternative to Marking and Policing: allocate a set portion of bandwidth
to each application flow; can lead to inefficient use of bandwidth if one
of the flows does not use its allocation
o PRINCIPLE 3: While providing isolation, it is desirable to use
resources as efficiently as possible
Queue Management
Principles for QOS Guarantees (more)
o Cannot support traffic beyond link capacity
o PRINCIPLE 4: Need a Call Admission Process; application flow
declares its needs, network may block call if it cannot satisfy the
needs
Queue Management
Policing Mechanisms
o Three criteria:
l (Long term) Average Rate (100 packets per sec or 6000 packets per min??), crucial
aspect is the interval length
l Peak Rate: e.g., 6000 p p minute Avg and 1500 p p sec Peak
l (Max.) Burst Size : Max. number of packets sent consecutively, ie over a short
period of time
Queue Management
Traffic shaping
o How to prevent congestion?
l it may result from burstiness
l arrivals more deterministic, better performance
– example : nbr of customers in D/D/1 vs. G/D/1
l control the rate and burst size
– traffic description
o Service contract
l if the network knows the type of the traffic, it can reserve resources to support
the traffic
l contract between the source and the network
– source: traffic description
– network: QoS guarantee if the traffic conformsto the description
– if the traffic is not conformant, penalty: reject a packet, no guarantees of the QoS
(traffic policing)
o More details in Network Calculus course
Queue Management
10
Leaky bucket
o Limited size buffer with constant departure rate
l r if buffer not empty
l 0 if buffer empty
o Equivalent to the queue G/D/1/N
o Fixed size packets
l one packet per clock tick
o Variable size packets
l number of bytes per clock tick
o Packet loss if buffer filled B
r
Queue Management
11
Token bucket
arrival of tokens :
rate r
packet buffer B
test
Queue Management
12
Token bucket
o Tokens generated with rate r
l 1 token : 1 packet or k bytes
o Packet must wait for a token before transmission
l no losses
l allows limited bursts (a little bit more than B)
o When packets are not generated, tokens accumulate
l n tokens - burst of n packets
l if bucket filled, tokens are lost
o Mean departure rate : r
Queue Management
13
Burst duration
o Burst duration - S sec
o Size of the bucket - B bytes
o Maximal departure rate - p bytes/s
o Token arrival rate - r bytes /s
l burst of B + r S bytes
l burst of pS
l B + rS = pS → S = B/(r - p)
o Example
l B = 250 Kb, p = 25 Mb/s, r = 2 Mb/s
l S = 11 ms
Queue Management
14
Traffic description
rate
3 MB/s
Flow B
2 MB/s
Flow A
1 MB/s
1s 2s 3s 4s time
o Flow A : r = 1 MB/s, B = 1 byte
o Flow B : r = 1 MB/s, B = 1 Mbyte
l during 2 s, the flow saves 2 s × 0.5 MB/s = 1 MB
Queue Management
15
Scheduling strategies
packets
transmission
queue
o Scheduler
l defines the order of packet transmission
o Allocation algorithms
l bandwidth/delay
– which packet choosen for transmission
l buffers
– which packet dropped
Queue Management
16
FIFO
o Last packets are dropped
o Current state of Internet routers
l TCP adapt bandwidth based on losses
o Decouple the order of transmission and drop
l RED (Random Early Discard) techniques
– choose a packet randomly and drop it
o Allows to share bandwidth
l proportionally to the offered load
o No isolation
l elastic flows (rate controlled by the source eg. TCP) may suffer from other flows
– a greedy UDP flow may obtain an important part of the capacity
– real time flows may suffer from long delays
Queue Management
17
Priority Queue
o Several queues of different priority
l source may mark paquets with priority
– eg. ToS field of IP
o Problem
l how to avoid everybody sending high priority packets?
Queue Management
18
Round Robin
flow 1
flow 2
flow 3
o Similar to Processor Sharing or Time Sharing
l one queue per flow
l cyclic service, one packet at a time
Queue Management
19
Characteristics
o It modifies the optimal strategy of sources
l FIFO: be greedy - send as much as possible
l RR: use your part the best
– a greedy source will experience high delays and losses
o Isolation
l good sources protected from bad ones
o Problem
l flows sending large packets get more
l cost of flow classification
Queue Management
20
Fair Queueing
flow 1
flow 2
flow 3
temps
o Round robin "bit per bit"
l each packet marked with the transmission instant of the last bit
l served in the order of instants
Queue Management
21
Weighted Fair Queueing
o Fair queueing
l equal parts : 1/n
o Weighted fair queueing
l each flow may send different number of bits
o Example - weights wi
l flow 1 weight 2 flow 2 weight 1 flow 3 weight 3
l 1/3 1/6 1/2
xi=C
wi
C : link capacity
∑wi
Queue Management
22
Rate guarantee
o Weights expressed as proportions (wi - guaranteed weight)
xi =C wi
, ∑ wi ≤1
∑ wi
xi≥C×wi
o Weights to guarantee a given rate
wi= xi /C
Queue Management
23
Random Early Detection
o Family of techniques used to detect congestion and signal sources
l when a queue is saturated, packets are dropped
l losses interpreted as congestion signals → decrease rate
o Idea
l act before congestion and reduce the rate of sources
l threshold for starting to drop packets
o Losses are inefficient
l result in retransmissions - dropped packets should be retransmitted
l enter Slow Start
o Synchronization of TCP sources
l several packet dropped
l several sources detect congestion and enter slow start at the same
instant
Queue Management
24
RED
th-max average th-min
o Estimation of the average queue length
l average ← q × measure + (1 - q) × average
o If average ≤ th-min
l accept the packet p
o If th-min < average < th-max
1
l drop with probability p
o If th-max ≤ average
l drop the packet
max-p
th-min th-max
Queue Management
25
RED Characteristics
o Tends to keep the queue reasonably short
l low delay
o Suitable for TCP
l single loss recovered by Fast Retransmit
o Probability p of choosing a given flow is proportional to the rate of the
flow
l more packets of that flow, higher probability of choosing one of its packets
Queue Management
26
RED Characteristics
o Dynamic probability p
l p-tmp = max-p × (average - th-min)/ (th-max - th-min)
l p = min(1,p-tmp/(1 - nb-packets × p-tmp))
l nb-packets: number of packets that have been accepted since last rejected packet
l p increases slowly with nb-packets
l nb-packets is uniformly distributed in [1,1/(p-tmp)]
o Example:
l max-p = 0.02 p-tmp
l If average = (th-max + th-min)/2,
one packet is rejected every 50 packets 1
max-p
th-min th-max
