When users want to send data over the Internet faster than the network can handle, congestion can occur, in the same way that traffic congestion hinders morning commuting in a big city.
Computers and devices that transmit data over the Internet break down the data into smaller packets and use a special algorithm to decide how fast to send those packets. These congestion control algorithms seek to discover and fully utilize available network capacity by sharing it fairly with other users who may be sharing the same network. These algorithms try to minimize the delay caused by data waiting in queues on the network.
Over the past decade, researchers from industry and academia have developed several algorithms that attempt to achieve high rates by controlling lags. Some of these, such as the BBR algorithm developed by Google, are now widely used by many websites and applications.
But a team of MIT researchers has found that these algorithms can be deeply unfair. In a new study, they show that there will always be a network scenario where at least one sender receives almost no bandwidth compared to other senders; that is, a problem known as hunger cannot be avoided.
“What is truly amazing about this paper and the results is that when you take into account the real-world complexity of network paths and all the things they can do to data packets, it is virtually impossible to avoid congestion control algorithms. to control late starvation with current methods, ”says Mohammad Alizadeh, associate professor of electrical and computer engineering (EECS).
Although Alizadeh and his co-authors were unable to find a traditional congestion control algorithm that could avoid starvation, there may be algorithms in a different class that could prevent this problem. Their analysis also suggests that modifying the way these algorithms work, to allow for greater delay variations, could help prevent hunger in some network situations.
Alizadeh wrote the article with first author and EECS graduate student Venkat Arun and senior author Hari Balakrishnan, Fujitsu’s professor of computer science and artificial intelligence. The research will be presented at the ACM Special Interest Group on Data Communications (SIGCOMM) conference.
Congestion control is a fundamental problem in networks that researchers have been trying to address since the 1980s.
A user’s computer does not know how fast to send data packets over the network because they lack information, such as the quality of the network connection or how many other senders are using the network. Sending packets that are too slow makes little use of available bandwidth. But sending them too quickly can overwhelm the network, and in doing so, packets will begin to be dropped. These packets need to be resent, which leads to longer delays. Delays can also be caused by packets waiting in a queue for a long time.
Congestion control algorithms use packet losses and delays as signals to infer congestion and decide how fast the data is sent. But the internet is complicated, and packets can be delayed and lost for reasons unrelated to network congestion. For example, data might be held in a queue along the way and then released with a barrage of other packets, or recipient acknowledgment might be delayed. The authors call delays that are not caused by congestion “jitter”.
Although a congestion control algorithm measures the delay perfectly, it cannot distinguish between the delay caused by congestion and the delay caused by jitter. The delay caused by jitter is unpredictable and confuses the sender. Due to this ambiguity, users start estimating the delay differently, which causes them to send packets at unequal speeds. Eventually, this leads to a situation where hunger occurs and someone is completely left out, explains Arun.
“We started the project because we didn’t have a theoretical understanding of congestion control behavior in the presence of jitter. To place it on a firmer theoretical foundation, we built a mathematical model that is simple enough to think about, but capable of capturing some of the intricacies of the internet. It was very rewarding to see math tell us things we didn’t know and that have practical relevance, ”he says.
The researchers fed their mathematical model to a computer, provided it with a set of commonly used congestion control algorithms, and asked the computer to find an algorithm that could avoid hunger using their model.
“We couldn’t do it. We have tried all the algorithms we are aware of and invented new ones. Nothing worked. The computer has always encountered a situation where some people get all the bandwidth and at least one person gets practically nothing, “says Arun.
The researchers were surprised by this result, especially since these algorithms are believed to be reasonably fair. They have begun to suspect that it may not be possible to avoid hunger, an extreme form of injustice. This prompted them to define a class of algorithms they call “converging delay algorithms” which they have shown will always starve in their network model. All existing congestion control algorithms that control lag (that researchers are aware of) are lagging convergent.
The fact that such simple ways of failing these widely used algorithms have remained unknown for so long illustrates how difficult it is to understand algorithms through empirical testing alone, adds Arun. He stresses the importance of a solid theoretical foundation.
But not all hope is lost. Although all the algorithms they tested have failed, there may be other algorithms that are not convergent in terms of delay that may be able to avoid starvation. This suggests that one way to solve the problem might be to design congestion control algorithms that vary the delay interval more widely, so the interval is greater than any delay that might occur due to jitter in the network.
“To control the delays, the algorithms have tried to constrain the delay variations to a desired equilibrium as well, but there is nothing wrong with potentially creating more delay variation to get better measurements of congestive delays. It’s just a new design philosophy that you should adopt, ”adds Balakrishnan.
Now, the researchers want to keep pushing to see if they can find or build an algorithm that will eliminate hunger. They also want to apply this mathematical modeling and computational proofing approach to other thorny and unsolved problems in networked systems.
“We are increasingly dependent on information systems for very critical things and we need to place their reliability on a more solid conceptual basis. We’ve shown the amazing things you can discover when you take the time to work out these formal specifications of what the problem actually is, ”says Alizadeh.