Aug 05, 2022 20:00:00

It turns out that there is a problem that the algorithm that controls network congestion ``cannot provide fair communication''

In the KDDI communication failure that occurred on July 2, 2022, congestion

occurred in the network due to the concentration of access from many terminals, and the situation continued for a long time, making it difficult to use KDDI's mobile communication. rice field. A new overseas study on congestion pointed out that there may be a bias in the algorithm that manages all users to access the network fairly.

Researchers discover major roadblock in alleviating network congestion | MIT News | Massachusetts Institute of Technology
https://news.mit.edu/2022/algorithm-computer-network-bandwidth-0804

According to researchers at the Massachusetts Institute of Technology, there is a possibility that there is a bias in congestion control algorithms such as TCP BBR developed by Google. Researchers point out that this makes it impossible to avoid 'starvation', where one or more senders receive less bandwidth than others. .

Computers and devices that send data over the Internet break the data into smaller packets and use special congestion control algorithms to determine how fast to send the packets.

Without the algorithm, the user's computer lacks information such as the quality of the network connection and how busy other senders are on the network, so it cannot correctly determine how fast to send data packets over the network. thing. A well-functioning congestion control algorithm can infer congestion from packet losses and delays and decide how fast to send data.

Sending packets too slowly will not take full advantage of the available bandwidth, and sending them too fast will tax the network and cause packets to be dropped. Packets that are dropped in this way must be retransmitted, resulting in longer delays. In other words, congestion control algorithms also have the role of minimizing delays by fairly allocating available network capacity to each user.

However, the Internet is complex and packets can be delayed or lost for reasons unrelated to congestion. Congestion control algorithms are apparently unable to distinguish between 'congestion-independent delay' and 'congestion-induced delay', which researchers collectively call 'jitter'. As a result of sending packets at uneven speed, someone will be completely shut out of the network.

``Considering the complexity of network paths and all their effects on data packets, it is basically impossible for current congestion control algorithms to avoid the above problems,'' said Mohammad Alizadeh, who led the research. . Alizadeh and his colleagues experimented with as many algorithms as they knew, and even created their own new algorithms, but there were always situations where someone was shut out of the network. About. The researchers were surprised by the results, as such algorithms are widely believed to be 'fair'.

In this research, it was found that the current ``delay-intensive algorithm'' cannot prevent starvation, but it is possible that the problem can be avoided if there is an algorithm that does not concentrate delay.

The study's lead author Venkat Arun said, 'The fact that such a simple problem has been unknown for so long in a widely used algorithm shows how difficult it is to understand the algorithm just by empirical experiments. showing,' he said. Arun and his colleagues would like to continue further research to see if they can find an algorithm that can solve the problem.