Congestion Control
All real subnets have a finite capacity. Too much traffic offered to a
subnet will cause congestion. How does the subnet react when it runs out
of buffers? By throwing packets away. Here's how it looks as traffic increases:
<figure 5-22 showing packets delivered versus packets sent - ideal,
desireable, and congested performance of subnet>
Congestion control is different than flow control. Flow control is a
data link issue, and concerns only one sender outrunning a single receiver
(e.g. a point-to-point link). Congestion control is a network layer issue,
and is thus concerned with what happens when there is more data in the
network than can be sent with reasonable packet delays, no lost packets,
etc. Flow control is a local, congestion control is global. One means of
handling congestion is by using a flow control mechanism to reduce the
traffic put on the net by a particular host, hence the confusion.
Many design parameters at the data link, network and transport layers
effect congestion. Setting each of these with a mind to preventing congestion
helps to eliminate the problem. For example, a flooding routing algorithm
is fast, but generates a lot of redundant packets. Timers in the data link
layer which are set too tight may cause needless retransmission of packets.
You can try to prevent congestion by careful design, or you can use
a more dynamic approach, sensing the presence of congestion and then either
increasing subnet capacity (spare lines and routers) or decreasing the
traffic offered to the subnet. These strategies are feedback strategies.
Traffic shaping
One of the causes of congestion is the inherent burstiness of computer
network traffic. Traffic shaping means to smooth, or otherwise alter, the
offered traffic as a function of time. Smooth traffic is easier to deal
with the bursty traffic. A subnet may be able to handle on average 10 M
packets in an hour, but it probably can't handle 10M packets in one minute
and nothing for the next 59 minutes.
Related to traffic shaping is the whole idea of agreeing with a network
service provider to a flow specification. A flow specification describes
what sort of traffic you will put into the net, and what sort of quality
if service you expect from it. Some of the quality of service parameters
are:
-
loss sensitivity (number of lost bytes per unit of time)
-
loss interval (the unit of time for calculating loss)
-
burst loss sensitivity (how long of a loss burst can be tolerated)
-
minimum delay (how large of a delay before the app notices)
-
maximum delay variation (the variance or jitter in the inter-packet delay)
-
quality of guarantee (how serious the spec is to the application)
Leaky bucket algorithm
A buffer tha converts an unregulated, bursty traffic flow into a regulated,
smooth, predictable flow. You put the buffer in between a traffic source
and the subnet. The buffer acts like a single server queue with a finite
queue length. Packets put in the buffer when it is full are thrown away.
The buffer may drain onto the subnet either by some number of packets per
unit time, or by some total number of bytes per unit time (helpful if packets
vary greatly in size).
A variant on the leaky bucket is the token bucket. The bucket is filled
with tokens at a certain rate. A packet must grab and destroy a token to
leave the bucket. Packets are never lost, they just have to wait for an
available token. Some bursts are allowed (up to the number tokens in the
bucket) which is a good match for some applications (compromise with congestion
and source needs).
Choke packets
Routers monitor the utilization of their output line and send special choke
packets back to hosts using output lines whose utilization has exceeded
some warning level. The utilization can be estimated by sampling it periodically
and blending the new value (either in use, f = 1 or not in use, f = 0)
with the current value for U. The weight a controls how rapidly the router
adjusts to changes:
Unew = a * Uold + (1-a) * f
When the sending host receives the choke packet it reduces the flow of
traffic it is sending to the subnet (often times done by factors of 1/2,
1/4, 1/8, ... as needed). Then it stops watching for choke packets, since
other packets which are in transit will probably also cause the congested
router to send more choke packets. When a packet is forwarded on a congested
line it is marked so that downstream routers don't also generate choke
packets for the sending host corresponding to the same packet.
Potential problems
What makes a host throttle back when it receives a choke packet?
What about high speed data rates and long transmission channels?
Load shedding
This is what routers do when they run out of buffers. If they must throw
away a packet then they can at least try to pick the best packets to pitch.
This depends on the application and on the error strategy used in the data
link layer. Older packets will be worse to throw away for a file transfer
than newer ones, since they will cause a gap in the received packets and
a go-back-n strategy may be employed by the data link layer. For real-time
voice or video it is probably better to throw away old data (already obsolete?)
and keep new packets.
Who knows best which packets can be dropped? The application. Getting
the application to mark packets with priority requires some incentive like
cheaper transmission rates for lower priority packets.
It appears to be better for routers to start dropping packets as soon
as congestion seems likely, rather than wait for congestion to take over.