What is congestion collapse?

Question

My understanding is that it involves multiple copies of the same packet existing in the network. But how does that situation end up happening? And why is it so harmful?

Answer 1

To start off I'm going to first ask you to ignore queueing. Imagine that routers in the following text have no queues at all. It is possible to understand congestion without bringing queues into the picture. So in the text below, a packet enters a router, and either gets transmitted immediately or gets dropped. (I will write a couple of lines about queueing at the end of this answer.)

The first thing to understand about congestion is this: interfaces can only operate at a finite speed. A 10Gbps ethernet interface can transmit packets at maximum rate of 10Gbps, no more (this translates to about a million packets per second, if the packets are about 1000 bytes in length).

OK, now consider a router like this:

                +----------------------+
  --------------o a                    |
                |                      |
  --------------o b                    |
                |                    x o----------------
  --------------o c                    |
                |                      |
  --------------o d                    |
                +----------------------+

Assume that packets are entering on interfaces (a, b, c, d) and leaving on x (i.e. from left to right)

Assume that x is a 100Mbps interface.

Lets say to start off the traffic rate on (a + b + c + d) is exactly 100Mbps. All these packets go out on x. So far so good.

Lets say now one of the interfaces, say d starts getting more traffic. Now (a + b + c + d) > 100Mbps

At this point, some packets have to get dropped. Which ones, it's hard to say. The dropped packets could be from a, b, c or d, or from some, or from all of these interfaces. This is when congestion is said to have taken place.

OK, now assume that the hosts that are sending traffic (i.e. the hosts located on the left hand side of the diagram) implemented a naive version of TCP. The naive implementation says: "lets send 15 packets (a "window"), then wait for 50ms for an Ack. If there isn't one, lets send those 15 packets again. Let's do this 100 times before we give up and declare the connection dead".

OK, back to our scenario. Let's say when congestion started on account of increased traffic on d, the victim was a single packet that happened to be received on interface a.

On account of the naive implementation, the sender of the original ill-fated packet now realizes: "hey what happened to the ack for the window I sent? Looks like my peer didn't get it, let me resend" and proceeds to do so. So now 'a' ends up receiving a fresh copy of 15 packets.

In the meanwhile, x is still congested. The fresh batch of 15 packets on 'a' only makes the situation worse, and leads to drops for packets that were received on 'b', 'c' and 'd' as well.

As long as the naive implementation is in action, this situation will only get worse and worse with time.

The solution: replace the naive implementation with something more intelligent. E.g. on the failure to receive an ack, don't send the entire 15 packet window; instead send progressively smaller windows. Don't have a fixed timeout, wait for progressively longer times before retransmission. And other similar clever techniques.

I hope the above explanation suffices to provide an intuitive picture. There is documentation elsewhere on the exact avoidance mechanisms.

[Queues: the presence of router queues does not change the overall scenario described above. The only difference is that instead of getting dropped straightaway the packets will get enqueued for some time. Queue depths are not infinite; in the congestion scenario described above, queues will also eventually get full, and stay that way (they will get filled faster than they get drained), leading to subsequent packets getting "tail-dropped". In other words, in the face of the naive TCP implementation on the part of end hosts, the presence of queues on routers does not improve the situation. Routers have queues for entirely unrelated purposes: (1) to temporarily absorb small bursts of traffic, (2) as a mechanism to implement prioritization, and (3) as an opportunity to implement RED which is one of the avoidance mechanisms]

"multiple copies of the same packet" This phrase confused me until I realized you meant "retransmissions of the same packet". As far as the network is concerned, retransmissions are new packets. They may have the same content as earlier transmitted packets from the host's point-of-view, but they are still considered new packets as far as the network is concerned. In particular, the IPv4 "Identifier" field will be different on retransmissions.

Anyhow, you can see that in the scenario I described above, eventually the situation will get so bad that all (or most) traffic received on a, b, c and d will just be retransmissions of earlier packets, i.e. the network is not really doing anything useful.

Answer 2

When incoming traffic exceeds a nodes forwarding capacity the excess is stored in a queue buffer. If this condition continues for more than a (very) short time the buffer overflows and received packets are dropped. The network is congested.

Dropped packets need to be retransmitted by the source. These retransmissions represent previously wasted bandwidth on the links in front of the bottleneck.

When congestion occurs, the source nodes need to detect this and reduce their transmission bandwidth to stop or at least reduce packet loss. If this doesn't work correctly, the retransmissions continue to add ingress traffic to the bottleneck node and worsen the problem. With a significantly large ingress-to-egress capacity ratio, the congestion condition can lead to a extremely low useful-to-useless traffic ratio.