Computer Networking Lecture Notes
2013 October 15 • Network Congestion Control
Outline
Review and definitions.
The congestion-control continuum.
Prevention: network provisioning.
Avoidance: admission control, throttling.
Reaction: load shedding
The Territory
Network Resources
Attached subnetworks treat the network (links + routers) as a resource.
Bandwidth, routing, and so on.
Network resources are finite and relatively static.
Subnetwork resource demands are practically unbounded and dynamic.
How can subnetwork demands be matched to network capabilities?
Resource Management
Resource management can be
proactive
or
reactive
.
Proactive management tries to manage demand to fit the resources.
Reactive management tries to manage resources to fit the demand.
Although it also tries to influence demand too.
Congestion control is reactive management.
Quality of service (QoS) is proactive management (next lecture).
Network Resources
Routers are the network resource of interest.
Time resources: router CPU, but also link bandwidth.
Space resources: buffer space, but also routing table size.
A simplified view, but a useful one.
Congestion
Congestion occurs when demand (traffic) outstrips supply (resources).
The router can handle
M
bits/sec maximum.
Congestion occurs when
\(\Sigma\)
j
i
j
bits/sec >
M
This is a first-cut definition.
More Congestion
Link 4 can handle
M
4
bits/sec maximum.
Congestion occurs when \(\Sigma\)
j
i
j
, 4
bits/sec >
M
4
.
Even though \(\Sigma\)
j
i
j
, 4
bits/sec ≤
M
.
Congestion Pictured
Controlling Congestion
Network congestion control should
Protect the network from congestion collapse but
run the network as close to limits as possible.
Higher utilization makes better economic sense.
A continuum of network congestion control.
From slower preventative techniques to faster reactive techniques.
Network Provisioning
Network provisioning
adds and upgrades resources to handle traffic.
Prevents congestion, but is slow to react.
Expected traffic demands can be forecast, but not easily.
Particularly in dynamic environments.
Technologically-driven
over-provisioning
is helpful here.
But Parkinson’s law.
Congestion Costs
Congestion is a cost to the network and to its users.
Routing algorithms are good at handling, and optimizing, costs.
Condition edge and vertex weights (costs) on congestion.
And use them in routing algorithms.
The result is
congestion-aware routing
algorithms.
Example
Congestion-aware routing algorithms
have poor convergence properties, and
can cause wild instabilities.
Evaluation
Possible fixes for congestion-aware problems include
multi-path routing
dampened reaction to congestion changes.
Congestion-aware routing algorithms used to be used in the Internet.
Not a solution in itself, but helpful elsewhere.
An Analogy
What do you do when you have more people than seats?
Admission Control
Only admit traffic when the network can handle it without congestion.
Easier for circuit-based networks than it is for datagram networks.
But still not easy.
Example: no dial tone on overloaded phone networks.
The big questions in the Internet now are related to admission control.
Describing Traffic
Traffic can be described by its average rate in bits/sec.
But much traffic is
bursty
, or on-off variable.
Think Web traffic over persistent connections.
Traffic also has a
shape
, or instantaneous burst size in bits/sec.
The maximum rate.
Admission Decisions
Fitting advertised rate + shape into the network can be tricky.
Given applications with
100 kbit/sec average rate, and
1 mbit/sec burst rate
how many applications fit in a 100 mbit/sec network?
Deciding Admissions
(100 mbit/sec)/(100 kbit/app-sec) = 1000 applications.
(100 mbit/sec)/(1 mbit/app-sec) = 100 applications.
Deciding on average rates overcommits the network.
Deciding on burst rates under-utilizes the network.
And all this assumes the traffic parameters are accurate.
Congestion Awareness
Congestion-aware routing is unstable for whole networks.
But works well for routing specific circuits.
Congestion is also more manageable, smaller and better behaved.
Congestion-aware routes can more finely partition the network into congested and uncongested regions.
Recovering From Mistakes
Admission control can err on the wrong side.
And datagram services are harder to manage in the network.
And networks are (should be) run close to congestion.
What happens when congestion results?
The network has failed, in some sense.
It’s up to the senders to respond.
Traffic Throttling
When too much traffic causes congestion, cut back (or
throttle
) the traffic.
A move from prevention and avoidance to reaction and mitigation.
Any traffic-throttling scheme has two problems:
Recognizing or anticipating congestion.
Signaling congestion to the senders.
Recognizing Congestion
Routers monitor network conditions and draw conclusions.
Observable conditions include
output link utilization,
buffer or queue length, or
resource exhaustion.
Average utilization misses burstiness; resource exhaustion is too late.
Average queue length works well.
Congestion Signaling
A sender receiving congestion signals should throttle back transmissions.
By some amount for some time.
Further signals, or their absence, determine future behavior.
More signals, more throttling.
Fewer or no signals, try for more capacity.
How should these signals be conveyed?
Choke Packets
A router nearing or in congestion sends
choke packets
back to senders.
Which sender does the router choke?
Sender Choice
Choking the last-in packet sender may not help.
That sender may not be a high-rate sender.
Randomly pick a queued packet and choke its sender.
High-rate senders queue many packets.
Not perfect, but low overhead.
Aiding and Abeting
Sending choke packets adds congestion.
Congested routers flag packets encountering congestion anyway.
Let the destination relay the congestion flag back to the sender in an ack.
This is
Explicit Congestion Notification
(
ECN
).
Implemented in DECNet (1980s), used in the Internet.
ECN Example
Long Fast Networks
Seattle is using a fast network to send to Boston via Toronto.
Toronto is getting congested, and uses choke packets or ECN.
What happens?
The Seattle-Toronto segment is
filled with packets
.
The segment dumps all its packets into Toronto after Seattle is notified.
Network Action
If the sender can’t help, the network has to.
Each router forwarding a choke packet devotes extra buffer space to the exuberant flow.
Congestion relief flows backwards to the sender, which then stems the flow.
Up-stream routers recover as the sender throttles.
This is
hop-by-hop backpressure
.
The Last Resort
What do you do with more stuff than you can handle?
Load Shedding
Last-resort congestion control throws packets on the floor.
Dropping
or
shedding
packets.
Electric power distribution does something similar.
The important decision: what packets to drop?
There are non-trivial decisions to be made.
Random choice works, but are there better choices?
Dropping Knowledge
Choice based on application-type can improve matters.
Drop later (newer) packets in a file transfer.
Drop earlier (older) packets in media streams.
Wine vs milk.
MPEG-encoded video packets.
Chose based on packet-type too.
Sender Assistance
The sender can mark packets as droppable or precious.
There should be incentives for accurate marking.
Too many precious packets can be penalized (by high cost, for example).
A predominance of droppable packets can be rewarded (by improved priority, for example).
This didn’t work in the Internet.
Definitive Signaling
Sending signals in heterogeneous environments is tricky.
Signals can be misinterpreted, misunderstood, or ignored.
Dropped packets are a definitive congestion signal.
But dropping packets in congestion is too late.
Drop packets in near-congested conditions.
An obvious and possibly timely signal.
Random Early Detection
The
Random Early Detection
(
RED
) algorithm:
Drop packets at random in near-congestion conditions.
This is a TCP-specific solution.
Datagram based.
TCP throttles on packet loss.
Tuning RED parameters improves results.
The Internet uses ECN with RED fall-back.
Summary
Network congestion control drives the network up to but not into congestion.
There is a continuum of congestion-control measures.
From slow avoidance to fast recovery.
Networks use several points in the continuum.
Congestion problems and solutions are constantly shifting in response to technological and operational events.
Credits
Admission (Found Object)
by
Tom Fassbender
under a Creative Commons
BY NC ND license
.
Overflowing trash bin
by
Matti Mattila
under a Creative Commons
BY NC SA
license.
This page last modified on 2012 October 18.