When one part of the subnet (e.g. one or more routers in an area) becomes overloaded, congestion results. Because routers are receiving packets faster than they can forward them, one of two things must happen:
See Fig. 5-24 for possible sources.
We now consider the problem of congestion and some possible solutions.
Preallocation schemes aim to prevent congestion from happening in the first place. For example, we can require that resources be preallocated before any packets can be sent, guaranteeing that resources will be available to process each packet.
In virtual circuit networks, for example, the sender opens a connection before sending data. The circuit setup operation selects a path through the subnet, and each router on the path dedicates buffer space and bandwidth to the new circuit.
What happens when a user attempts to open a virtual circuit and the subnet is congested? The subnet can refuse to open the connection, forcing the user to wait until sufficient resources become available.
Note: The ability of the subnet to reject requests to open connections is an important property of connection oriented networks.
Control the rate at which packets are sent (not just how many). Widely used in ATM networks.
At set up, the sender and carrier negotiate a traffic pattern (shape).
Leaky Bucket Algorithm used to control rate in a datagram network. See Fig. 5-25. A single-server queue with constant service time. If bucket (buffer) overflows then packets are discarded.
Enforces a constant output rate regardless of burstiness of input. Does nothing when input is idle. In contrast the Token Bucket Algorithm causes a token to be generated periodically, which during idle periods can be saved up.
Related to traffic shaping is flow specification, where a particular quality of service is agreed upon between sender, receiver and carrier.
At the other end of the spectrum, we could preallocate no resources in advance, and take our chances that resources will be available when we need them. When insufficient resources are present to process existing packets, discard queued packets to make room for newly arriving ones.
Who retransmits the discarded packets? Two cases: connection oriented and connectionless. In datagram (connectionless) networks, the sending host (transport layer) retransmits discarded packets (if appropriate). In virtual circuit networks, the previous-hop router retransmits the packet when it fails to receive an acknowledgment.
Failure to preallocate resources leads to two problems: potential deadlock and unfairness. First, let us consider deadlock.
Suppose that all of an router's buffers hold packets. Because the router has no free buffers, it cannot accept additional frames. Unfortunately, it also ignores frames containing ACKs that would free up some of those buffers!
Suppose further, that two adjacent routers, A and B, are sending packets to each other. Since both are waiting for the other to accept a packet, neither can proceed. This condition is known as a deadlock.
Solution: Reserve at least one buffer for each input line and use it to hold incoming packets. Note that we can extract the ACK field and still discard the packet, if we don't have buffers to hold it.
Advantage of discarding packets when congested: Easy to implement.
Another approach to congestion avoidance is to limit the total number flow of packets in the subnet at any one time. The idea is similar to the token ring:
Refuse to set up new connections if congestion is present.
Flow control is aimed at preventing a fast sender from overwhelming a slow receiver. Flow control can be helpful at reducing congestion, but it can't really solve the congestion problem.
For example, suppose we connect a fast sender and fast receiver (e.g., two Crays) using a 9.6 kbps line:
Note how the window size limits the total number of packets that can be in transmission at one time.
Flow control can take place at many levels:
routers can monitor the level of congestion around them, and when congestion is present, they can send choke packets to the sender that say ``slow down''.
How can an router measure congestion? An router might estimate the level of congestion by measuring the percentage of buffers in use, line utilizations, or average queue lengths.
Advantage: Dynamic. Host sends as much data as it wants, the network informs it when it is sending too much.
Overall: Varying methods for congestion control with different levels of effectiveness.
More attention being paid to reserving resources so that chances of congestion are reduced and the quality of service is more reliable.