Network congestion algorithms have design flaw, says MIT
- Reference: 1661184009
- News link: https://www.theregister.co.uk/2022/08/22/network_congestion_algorithms/
- Source link:
Published ahead of a conference presentation this week, [1]the MIT paper [PDF] found that, regardless of approach, CCAs like Google's BBR, FAST, and others all suffer from the physical limitations of networks, leading to an unavoidable problem where some users are starved of bandwidth.
"Our theorem shows that CCAs have to choose at most two out of three properties: high throughput, convergence to a small and bounded delay range, and no starvation," the researchers said in the paper.
[2]
The paper cites a number of non-congestive network issues, like ACK aggregation and end-host scheduling, which serve to upset tight algorithmic controls that rely on estimates to account for happenings on a network it can't control.
[3]
[4]
In an ideal situation, the researchers wrote, CCAs operating on a single network are designed to converge and work together to create the smallest possible delay range. According to the researchers, here's where the problem lies.
"Because most CCAs attempt to work across many orders of magnitude of rates, they must map a large rate range into a small delay range. Thus, even small changes in estimated queuing delay would induce enormous changes," the team wrote.
[5]Tencent lines up to deploy Broadcom's co-packaged optical switches
[6]Interconnect innovation key to satiating soaring demand for fiber capacity
[7]DIY 5G specialist FreedomFi acquired by Nova Labs
[8]Broadcom challenges Nvidia's Spectrum-4 with 51.2T switch silicon
In other words, algorithms account for a lot, but they simply can't factor physical imperfections in the real world or non-congestion delays into their calculations.
Can we build better CCAs?
The paper admits its conclusions are "pessimal for delay-bounding CCAs," and raises the question of "whether we are doomed to choose between bounding delays and avoiding starvation."
Speaking to IEEE Spectrum , lead study author and MIT computer scientist Venkat Arun [9]said that his team's discovery sheds new light on CCA problems previously attributed to poor algorithmic decision-making and insufficient network capacity.
[10]
Instead, Arun and his team's research shows that the algorithms themselves simply aren't designed to account for network jitter, which the paper uses to refer to non-congestive causes of network delays. "We do not believe it is possible to circumvent this problem with algorithms that map loss rates (or delays) to sending rates," the team wrote.
This doesn't mean the MIT team doesn't have suggestions on how to solve this seemingly unavoidable network management problem. In the paper, the team makes several suggestions that basically amount to increasing algorithmic queue times to account for jitter.
Still, even that might not be enough, the team concluded. "It is also possible that purely end-to-end CCAs might always suffer from the issues we found, and in-network support such as active queue management, explicit congestion signaling, or stronger isolation is required." ®
Get our [11]Tech Resources
[1] http://people.csail.mit.edu/venkatar/cc-starvation.pdf
[2] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/networks&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=2&c=2YwP8eGe5kEkuz8Hsq1@vHAAAABE&t=ct%3Dns%26unitnum%3D2%26raptor%3Dcondor%26pos%3Dtop%26test%3D0
[3] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/networks&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YwP8eGe5kEkuz8Hsq1@vHAAAABE&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[4] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/networks&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=3&c=33YwP8eGe5kEkuz8Hsq1@vHAAAABE&t=ct%3Dns%26unitnum%3D3%26raptor%3Deagle%26pos%3Dmid%26test%3D0
[5] https://www.theregister.com/2022/08/22/cpo_switch_broadcom_tencent/
[6] https://www.theregister.com/2022/08/20/interconnect_innovation_fiber_capacity/
[7] https://www.theregister.com/2022/08/18/freedomfi_nova/
[8] https://www.theregister.com/2022/08/16/broadcom_nvidia_switch/
[9] https://spectrum.ieee.org/internet-congestion-control
[10] https://pubads.g.doubleclick.net/gampad/jump?co=1&iu=/6978/reg_onprem/networks&sz=300x50%7C300x100%7C300x250%7C300x251%7C300x252%7C300x600%7C300x601&tile=4&c=44YwP8eGe5kEkuz8Hsq1@vHAAAABE&t=ct%3Dns%26unitnum%3D4%26raptor%3Dfalcon%26pos%3Dmid%26test%3D0
[11] https://whitepapers.theregister.com/
Congestion algorithm solution
We've seen congestion issues for years but the current solution is to privatize the organization, pay big bonuses to the people running the organization and then, when congestion becomes a problem, just flush the untreated issues into a river. Congestion issues are being solved everywhere in the UK nowadays in a very profitable manner but let's not go swimming.
Re: Congestion algorithm solution
To many people flushing their buffers?
Too many big buffers in too many nodes
The internet was designed to run with packets (occaisionally) being thrown away.
And every timet that happens now to get a new packet for the data stream you want all those buffers need to be gone through.
Unless you split out the jitter and delay sensitive packets and give them priority (IE your VoIP packets and game control packets Vs that big dowload of pron you've got going on) that's always going to be the case.
Duh
Given the inputs available to the algorithm, not all scenarios can be uniquely detected. For some of those scenarios, you may choose greedy or cooperative solutions. This is why TCP is still around despite so many claims of amazingly better algorithms.
Re: Duh
There are a variety of TCP congestion control algorithms....
TCP Tahoe, TCP Reno, TCP New Reno and TCP Vegas...
Three guesses as to why the developers tend to rely on, umm, gambling towns as motivation for their codes.
Arguably, there's too much reliance on good behaviour
The interesting thing about this is that these attempts at "fair" capacity sharing is that they're pretty much dependent on transport implementations that are entirely under the control of end users doing "the right thing". There are things a "greedy" system could do (such as unnecessary retransmissions) that might reduce the likelihood of its traffic being dropped compared with that of another user. I don't think we can for ever rely on Internet users simply using the protocol stack that came with their operating system.
Complexity Theory?
I wonder if the mathematical complexity theorists have looked at this problem and determined whether or not it is, in general, NP-complete? This sounds like designing an effective CCA is related to the 'travelling salesman problem', which is known to be in general a difficult problem, as are many concerning graphs and networks.
Not necessarily related
MIT is also rebranding itself simply as "Karen"