Network 'Jitters' Confuse Packet-Routing Algorithms, Make Unfair Congestion Inevitable

IEEE Spectrum reports that a new study finds that many key algorithms designed to control "congestion" delays on computer networks "may prove deeply unfair, letting some users hog all the bandwidth while others get essentially nothing."[A]lthough hundreds of congestion control algorithms have been proposed in the last roughly 40 years, "there is no clear winner," says study lead author Venkat Arun, a computer scientist at MIT. "I was frustrated by how little we knew about where these algorithms would and would not work. This motivated me to create a mathematical model that could make more systematic predictions...." Their new study finds that given the real-world complexity of network paths, there will always be a scenario where a problem known as "starvation" cannot be avoided - where at least one sender on a network receives almost no bandwidth compared to other users.... Congestion control algorithms rely on packet losses and delays as details to infer congestion and decide how fast to send data. However, packets can get lost and delayed for reasons other than network congestion. For example, data may be held up and then released in a burst with other packets, or a receiver's acknowledgement that it received packets might get delayed. The researchers called delays that do not result from congestion "jitter." Congestion control algorithms cannot distinguish the difference between delays caused by congestion and jitter. This can lead to problems, as delays caused by jitter are unpredictable. This ambiguity confuses senders, which can make them each estimate delay differently and send packets at unequal rates. The researchers found this eventually leads to situations where starvation occurs and some users get shut out completely. In the new study, the researchers analyzed whether every congestion control algorithm of which they were aware, as well as some new ones they devised, could avoid starvation. The scientists were surprised to find there were always scenarios with each algorithm where some people got all the bandwidth, and at least one person got basically nothing.... "Extreme unfairness happens even when everybody cooperates, and it is nobody's fault." Although existing approaches toward congestion control may not be able to avoid starvation, the aim now is to develop a new strategy that does, Arun says.

Read more of this story at Slashdot.