Congestion Control

Computer Networks 24-1

 Traffic Descriptors
• Traffic descriptor are qualitative values that represent a data flow
• Average data rate = amount of data/time
• Peak data rate: the max. data rate of the traffic
• Max. burst size: the max. length of time the traffic is generated at the peak rate
• Effective bandwidth: bandwidth that the network needs to allocate for traffic flow

Computer Networks 24-2

 Traffic Profiles
• Constant-bit-rate (CBR)
• Variable-bit-rate (VBR)
• Bursty

Computer Networks 24-3

 Congestion
• Congestion: the load on the network is greater than the capacity of the network
• Congestion control: the mechanisms to control the congestion and keep the load
below the capacity
• Congestion occurs because routers and switches have queues- buffers that hold the
packets before and after processing
• The rate of packet arrival > packet processing time  input queue longer
• The packet departure time < packet processing time  output queue longer

Computer Networks 24-4

 Network Performance-1
• Packet delay versus network load

Computer Networks 24-5

 Network Performance-2
• Throughput versus network load
• Throughput: the number of packets passing through the network in a unit of time

Computer Networks 24-6

 Congestion Control
• Congestion control refers to techniques and mechanisms that can either prevent
congestion, before it happens, or remove congestion, after it has happened.

• Two broad categories: open-loop congestion control (prevention) and closed-loop

congestion control (removal).

Computer Networks 24-7

 Open Loop Control: Prevention
• Retransmission policy and timers must to be designed to optimize efficiency and at
the same time prevent congestion

• Window policy: Selective Repeat is better than Go-back-N

• Acknowledgement policy: does not ACK every packet

• Discard policy: prevent congestion and at the same time may not harm the integrity
of the transmission

• Admission policy: Switch first check the resource requirement of a flow before
admitting it to the network

Computer Networks 24-8

Closed-Loop Congestion Control: Removal
• Back pressure: inform the previous upstream router to reduce the rate of outgoing
packets if congested
• Choke point: a packet sent by a router to the source to inform it of congestion,
similar to ICMP’s source quench packet
• Implicit signaling: slow down its sending rate by detecting an implicit signal
concerning congestion
• Explicit signaling: Backward signaling / Forward signaling

Computer Networks 24-9

 Congestion Control in TCP
• TCP assumes that the cause of a lost segment is due to congestion in the network.
• If the cause of the lost segment is congestion, retransmission of the segment does
not remove the cause—it aggravates it.
• The sender has two pieces of information: the receiver-advertised window size and
the congestion window size
• TCP Congestion window
– Actual window size = minimum (rwnd, cwnd)
(where rwnd = receiver window size, cwnd = congestion window size)

Computer Networks 24-10

 TCP Congestion Policy
• Based on three phases: slow start, congestion avoidance, and congestion detection
• Slow Start: Exponential Increase
– In the slow-start algorithm, the size of the congestion window increases
exponentially until it reaches a threshold

Computer Networks 24-11

 TCP Congestion Policy
• Congestion Avoidance: Additive Increase
– The size of the congestion window increases additively until
congestion is detected

Computer Networks 24-12

 TCP Congestion Policy
• Congestion Detection: Multiplicative Decrease
• An implementation reacts to congestion detection in one of two ways:
– If detection is by time-out, a new slow start phase starts
– If detection is by three ACKs, a new congestion avoidance phase starts
• Summary

Computer Networks 24-13

Congestion Example

Computer Networks 24-14

 Quality of Service (QoS)
• Flow Characteristics:
– Reliability
– Delay
– Jitter: the variation in delay for packets belonging to the same flow
– Bandwidth
• Flow Classes:
– Based on the characteristics, we can classify flows into groups, with each
group having similar levels of characteristics

Computer Networks 24-15

 QoS Techniques
• Scheduling: FIFO queuing, priority queuing, and weighted fair queuing
• Traffic shaping: Leaky bucket, token bucket
• Resource reservation
• Admission control: accept or reject a flow based on predefined parameters called
flow specification

• FIFO queuing

Computer Networks 24-16

 Priority Queuing
• Packets are first assigned to priority class. Each priority class has its own queue
• The packets in the highest-priority queue are processed first

Computer Networks 24-17

 Weighted Fair Queuing
• The queues are weighted based on the priority of the queues
• The system processes packets in each queue in a round-robin fashion with the
number of packets selected from each queue based on the weight

Computer Networks 24-18

 Traffic Shaping: Leaky Bucket
• Traffic shaping: to control the amount and the rate of the traffic sent to network
• Two techniques: leaky bucket and token bucket
• A leaky bucket algorithm shapes bursty traffic into fixed-rate traffic by averaging
the data rate. It may drop the packets if the bucket is full.

Computer Networks 24-19

 Leaky Bucket Implementation

• Algorithm for variable-length packets:

1) Initialize a counter to n at the tick of the clock
2) If n is greater than the size of the packet, send packet and decrement the
counter by the packet size. Repeat this step until n is smaller than the
packet size
3) Reset the counter and go to step 1

Computer Networks 24-20

 Token Bucket
• The token bucket allows bursty traffic at a regulated maximum rate.

Computer Networks 24-21

Congestion Avoidance
• TCP’s strategy
• control congestion once it happens
• repeatedly increase load in an effort to find the point at
which congestion occurs, and then back off
• Alternative strategy
• predict when congestion is about to happen
• reduce rate before packets start being discarded
• call this congestion avoidance, instead of congestion control
• Two possibilities
• router-centric: DECbit and RED Gateways
• host-centric: TCP Vegas
 Random Early Detection (RED)
• Basic idea of RED
• Router notices that the queue is getting backlogged
• … and randomly drops packets to signal congestion
• Packet drop probability
• Drop probability increases as queue length increases
• If buffer is below some level, don’t drop anything
• … otherwise, set drop probability as function of queue

Average Queue Length

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

• Drops packet in proportion to each flow’s rate

• High-rate flows have more packets
• … and, hence, a higher chance of being selected

• Drops are spaced out in time

• Which should help desynchronize the TCP senders

• Tolerant of burstiness in the traffic

• By basing the decisions on average queue length
 Problems with RE
D
• Hard to get the tunable parameters just right
• How early to start dropping packets?
• What slope for the increase in drop probability?
• What time scale for averaging the queue length?

• Sometimes RED helps but sometimes not

• If the parameters aren’t set right, RED doesn’t help
• And it is hard to know how to set the parameters

• RED is implemented in practice

• But, often not used due to the challenges of tuning right

• Many variations
• With cute names like “Blue” and “FRED”… 
Random Early Detection (RED)

• Notification is implicit
• just drop the packet (TCP will timeout)
• could make explicit by marking the packet
• Early random drop
• rather than wait for queue to become full, drop each arriving packet with
some drop probability whenever the queue length exceeds some drop level
RED Details
• Compute average queue length
AvgLen = (1 - Weight) * AvgLen +
Weight * SampleLen
0 < Weight < 1 (usually 0.002)
SampleLen is queue length each time a packet arrives

MaxThreshold MinThreshold

AvgLen
 RED Details (cont
)
• Two queue length thresholds

if AvgLen <= MinThreshold then enqueue the

packet
if MinThreshold < AvgLen < MaxThreshold then
calculate probability P
drop arriving packet with probability P if
MaxThreshold <= AvgLen then
drop arriving packet
RED Details (cont
)
• Computing probability P
TempP = MaxP * (AvgLen - MinThreshold)/
(MaxThreshold - MinThreshold)
P = TempP/(1 - count * TempP)

• Drop Probability Curve

P(drop)

1.0

MaxP
AvgLen
MinThresh MaxThresh
Explicit Congestion Notification

• Early dropping of packets

• Good: gives early feedback
• Bad: has to drop the packet to give the feedback
• Explicit Congestion Notification
• Router marks the packet with an ECN bit
• … and sending host interprets as a sign of congestion
• Surmounting the challenges
• Must be supported by the end hosts and the routers
• Requires two bits in the IP header (one for the ECN mark, and one
to indicate the ECN capability)
• Solution: borrow two of the Type-Of-Service bits in the IPv4 packet
header
 Explicit Congestion Notificati
on
 ECN is an AQM mechanism

 Routers notify TCP senders/receivers about incipient congestion – without

packet drops

 How?
 Through IP and TCP headers

 TCP treats ECN signals exactly the same as when a single dropped packet is
detected – but packets are not actually dropped
 ECN bits in IP head
er
Differentiated Services Codepoints Reserved
ECN
6 bits 22 bits
bit
s

VER HLEN DS Total Length 16 bits

Fragmentation offset
4 bits 4 bits 8 bit
Identification s Flags 13 bits
16 bits 3
Time to Live Protocol bits Header Checksum
8 bits 8 bits 16 bits
Source IP address
32 bits
Destination IP address
32 bits

Options (if any)

Data
 ECN bits in IP header (cont’
d)
ECN Field
ECT: ECN
ECT CE Capable Transport
CE: Congestion
2 bits = 4 ECN Experienced
Codepoints
ECT CE Names for the ECN bits
0 0 Not-ECT (Not ECN Capable Transport)

0 1 ECT(1) (ECN Capable Transport (1))

1 0 ECT(0) (ECN Capable Transport(0))

1 1 CE (Congestion Experienced)
 ECN bits in TCP head
er
Reserved 4 C
Reserved
E U A P R S F
W CR K C S S Y I
bits6 bits R E H T N N
G

Source port address Destination port address

16 bits 16 bits CWR: Congestion
Sequence Number 32 Window Reduced Flag
bits ECE: ECN-Echo Flag
Acknowledgement
Number 32 bits
HLEN Reserved U A P R S F Window size
RCSSYI 16 bits
4 bits 6 bits T N
Checksum
GKH N Urgent
16 bits pointer
16 bits
Options (if any)

Data
 Advantages of ECN
 Prevents unnecessary packet drops at routers  less retransmissions 
• improvement in the “GOODPUT”
 Avoids timeouts by getting faster notification to end hosts
 Less time to identify congestion
 Non-ECN flows infer congestion from 3 duplicate ACKs or even worse from timeouts as opposed
to ECN flows that get congestion notification in the first ACK
 Fewer retransmissions also means less traffic on the network
REFERENCES

1. Data Communications and Networking

by Forouzan
2. Data and Computer Communications by
William Stallings