2

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?

9
  • A simple search will yield the answer to your question.
    – Ron Maupin
    Apr 10 '18 at 19:50
  • 1
    @RonMaupin I searched Google, Wikipedia and this StackExchange. I didn't see anything on this StackExchange. Of course there were some results on Google and Wikipedia, but they were all dense and not accessible to a beginner like me. Apr 10 '18 at 21:02
  • I thought the Wikipedia article summed it up nicely. What part don’t you understand?
    – Ron Trunk
    Apr 10 '18 at 21:04
  • 1
    @RonTrunk en.wikipedia.org/wiki/Network_congestion#Congestive_collapse is what I found on Wikipedia. I get that "incoming traffic exceeds outgoing bandwidth" is a necessary condition, but it doesn't seem sufficient. Routers have queues, so the excess traffic should be held in the queues. If the queue overflows, then the sender would just retransmit. That's my understanding. With that understanding, I don't see how multiple copies of the same packet can ever occur. Apr 10 '18 at 21:09
  • @RonTrunk also, I'm not quite sure what exactly congestion collapse is. That Wikipedia article says that it "is the condition in which congestion prevents or limits useful communication". Does the queue need to be full for that condition to occur? Even when the queue is empty, but incoming traffic exceeds outgoing bandwith, that seems to meet the "limits useful communication" condition, but I'm not sure. Apr 10 '18 at 21:13
3
+50

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.

4
  • Thanks for taking the time to describe this! I find the diagram and concrete example really useful. I also think it seems like a good idea to ignore queues initially. "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." I'm not sure why this makes the situation worse. If Sender A decided to just give up right away, Senders B, C and D wouldn't get their packets dropped. But Sender A would. By Sender A retransmitting too soon, it seems to me that... Apr 14 '18 at 17:04
  • ...it could cause Senders A, C and D to have their packets accepted rather than Senders B, C or D. Or perhaps A, B and D are accepted and C gets dropped. Regardless, it seems that someone is going to get dropped, so I don't see why it is a worse situation than it already was. Apr 14 '18 at 17:06
  • The thing to remember is that we are talking about entire segments getting retransmitted, not just individual packets. In the "naive" implementation above, a segment is 15 packets wide. If even one of those 15 were dropped, all 15 would get retransmitted. This is why things would get worse; the loss of a single packet is responded to by a retransmit of 15 packets. Since x is already congested, this retransmit is also not successful; e.g. 6 of these may get dropped and 9 may go through. This serves no purpose because the entire lot of 15 will now have to get re-re-transmitted. And ...
    – mere3ortal
    Apr 15 '18 at 3:10
  • ... the 9 that did go through did so at the expense of packets coming in on other interfaces, so hosts connected to those interfaces start retransmitting entire segments as well. What started off as a single packet drop has now become a retransmit nightmare with hundreds of packets involved. Remember that the diagram above is a transit router somewhere in the internet with potentially thousands of TCP end points connected to each of a, b, c and d.
    – mere3ortal
    Apr 15 '18 at 3:16
1

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.

10
  • "These retransmissions represent previously wasted bandwidth on the links in front of the bottleneck." Suppose the bottleneck has packets A, B and C in it's queue, and that the queue is full. Then the sender tries sending packet D, but since the queue is full, packet D is dropped. And then after some time, packet D is retransmitted. I'm not seeing where there is wasted bandwidth. A, B and C are never interfered with by D. Are you referring to the actual wire being occupied? Apr 13 '18 at 17:46
  • "If this doesn't work correctly, the retransmissions continue to add ingress traffic to the bottleneck node and worsen the problem." I guess this is similar to my previous comment, but I don't understand this either. If the sender doesn't reduce its transmission, it'd keep trying to send D and D would keep getting dropped. But I don't see how that interferes with the packets that are already in the bottlenecks queue, or with other senders. Apr 13 '18 at 17:49
  • "... but since the queue is full, packet D is dropped. And then after some time, packet D is retransmitted. I'm not seeing where there is wasted bandwidth." - packet D is transmitted twice = wasted bandwidth. Additionally, D might be retransmitted while still being in the queue (the retransmission is triggered by the missing ACK, not the drop event which can't be detected) which in turn causes another packet to get dropped that would otherwise have made it.
    – Zac67
    Apr 13 '18 at 18:18
  • "packet D is transmitted twice = wasted bandwidth" So bandwidth means simply occupying the wire? If so, I don't understand why simply occupying the wire is harmful. I know this is a newb question, but I am imagining that one wire connects two routers, and so it isn't like there are other routers who won't be able to use the wire because it is occupied... Apr 13 '18 at 19:01
  • ...However, even if there are other routers competing for the same wire, I am also imagining that the packets moving across the wire move at the same speed, and so occupying doesn't necessarily mean blocking, if that makes sense. Like how just because there are other cars on the road doesn't necessarily mean that they are blocking you or slowing you down. Apr 13 '18 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.