{"id":35290,"date":"2022-08-04T13:12:46","date_gmt":"2022-08-04T13:12:46","guid":{"rendered":"https:\/\/harchi90.com\/researchers-discover-major-roadblock-in-alleviating-network-congestion-mit-news\/"},"modified":"2022-08-04T13:12:46","modified_gmt":"2022-08-04T13:12:46","slug":"researchers-discover-major-roadblock-in-alleviating-network-congestion-mit-news","status":"publish","type":"post","link":"https:\/\/harchi90.com\/researchers-discover-major-roadblock-in-alleviating-network-congestion-mit-news\/","title":{"rendered":"Researchers discover major roadblock in alleviating network congestion | MIT News"},"content":{"rendered":"
\n

When users want to send data over the internet faster than the network can handle, congestion can occur \u2014 the same way traffic congestion snarls the morning commute into a big city.<\/p>\n

Computers and devices that transmit data over the internet break the data down into smaller packets and use a special algorithm to decide how fast to send those packets. These congestion control algorithms seek to fully discover and utilize available network capacity while sharing it fairly with other users who may be sharing the same network. These algorithms try to minimize delay caused by data waiting in queues in the network.<\/p>\n

Over the past decade, researchers in industry and academia have developed several algorithms that attempt to achieve high rates while controlling delays. Some of these, such as the BBR algorithm developed by Google, are now widely used by many websites and applications.<\/p>\n

But a team of MIT researchers has discovered that these algorithms can be deeply unfair. in a new study, they show 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 “starvation” cannot be avoided.<\/p>\n

\u201cWhat is really surprising 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 basically impossible for delay-controlling congestion control algorithms to avoid starvation using current methods,\u201d says Mohammad Alizadeh, associate professor of electrical engineering and computer science (EECS).<\/p>\n

While Alizadeh and his co-authors weren’t able 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 changing how these algorithms work, so that they allow for larger variations in delay, could help prevent starvation in some network situations.<\/p>\n

Alizadeh wrote the paper with first author and EECS graduate student Venkat Arun and senior author Hari Balakrishnan, the Fujitsu Professor of Computer Science and Artificial Intelligence. The research will be presented at the ACM Special Interest Group on Data Communications (SIGCOMM) conference.<\/p>\n

Controlling congestion<\/strong><\/p>\n

Congestion control is fundamental problem in networking that researchers have been trying to tackle since the 1980s.<\/p>\n

A user’s computer does not know how fast to send data packets over the network because it lacks information, such as the quality of the network connection or how many other senders are using the network. Sending packets too slowly makes poor use of the available bandwidth. But sending them too quickly can overwhelm the network, and in doing so, packets will start to get dropped. These packets must be resent, which leads to longer delays. Delays can also be caused by packets waiting in queues for a long time.<\/p>\n

Congestion control algorithms use packet losses and delays as signals to infer congestion and decide how fast to send data. But the internet is complicated, and packets can be delayed and lost for reasons unrelated to network congestion. For instance, data could be held up in a queue along the way and then released with a burst of other packets, or the receiver’s acknowledgment might be delayed. The authors call delays that are not caused by congestion \u201cjitter.\u201d<\/p>\n

Even if a congestion control algorithm measures delay perfectly, it can’t tell the difference between delay caused by congestion and delay caused by jitter. Delay caused by jitter is unpredictable and confuses the sender. Because of this ambiguity, users start estimating delay differently, which causes them to send packets at unequal rates. Eventually, this leads to a situation where starvation occurs and someone gets shut out completely, Arun explains.<\/p>\n

\u201cWe started the project because we lacked a theoretical understanding of congestion control behavior in the presence of jitter. To place it on a firmer theoretical footing, we built a mathematical model that was simple enough to think about, yet able to capture some of the complexities of the internet. It has been very rewarding to have math tell us things we didn’t know and that have practical relevance,\u201d he says.<\/p>\n

Studying Starvation<\/strong><\/p>\n

The researchers fed their mathematical model to a computer, gave it a series of commonly used congestion control algorithms, and asked the computer to find an algorithm that could avoid starvation, using their model.<\/p>\n

\u201cWe couldn’t do it. We tried every algorithm that we are aware of, and some new ones we made up. Nothing worked. The computer always found a situation where some people get all the bandwidth and at least one person gets basically nothing,\u201d Arun says.<\/p>\n

The researchers were surprised by this result, especially since these algorithms are widely believed to be reasonably fair. They started suspecting that it may not be possible to avoid starvation, an extreme form of unfairness. This motivated them to define a class of algorithms they call \u201cdelay-convergent algorithms\u201d that they proved will always suffer from starvation under their network model. All existing congestion control algorithms that control delay (that the researchers are aware of) are delay-convergent.<\/p>\n

The fact that such simple failure modes of these widely used algorithms remained unknown for so long illustrates how difficult it is to understand algorithms through empirical testing alone, Arun adds. It underscores the importance of a solid theoretical foundation.<\/p>\n

But all hope is not lost. While all the algorithms they tested failed, there may be other algorithms which are not delay-convergent that might be able to avoid starvation This suggests that one way to fix the problem might be to design congestion control algorithms that vary the delay range more widely, so the range is larger than any delay that might occur due to jitter in the network.<\/p>\n

\u201cTo control delays, algorithms have tried to also bound the variations in delay about a desired equilibrium, but there is nothing wrong in potentially creating greater delay variation to get better measurements of congestive delays. It is just a new design philosophy you would have to adopt,\u201d Balakrishnan adds.<\/p>\n

Now, the researchers want to keep pushing to see if they can find or build an algorithm that will eliminate starvation. They also want to apply this approach of mathematical modeling and computational proofs to other thorny, unsolved problems in networked systems.<\/p>\n

\u201cWe are increasingly reliable on computer systems for very critical things, and we need to put their reliability on a firmer conceptual footing. We’ve shown the surprising things you can discover when you put in the time to come up with these formal specifications of what the problem actually is,\u201d says Alizadeh.<\/p>\n

The NASA University Leadership Initiative (grant #80NSSC20M0163) provided funds to assist the authors with their research, but the research paper solely reflects the opinions and conclusions of its authors and not any NASA entity. This work was also partially funded by the National Science Foundation, award number 1751009.<\/p>\n<\/p><\/div>\n

.<\/p>\n","protected":false},"excerpt":{"rendered":"

When users want to send data over the internet faster than the network can handle, congestion can occur \u2014 the same way traffic congestion snarls the morning commute into a big city. Computers and devices that transmit data over the internet break the data down into smaller packets and use a special algorithm to decide …<\/p>\n

Researchers discover major roadblock in alleviating network congestion | MIT News<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-global-header-display":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","spay_email":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[4],"tags":[14800,14797,14798,14799],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":33192,"url":"https:\/\/harchi90.com\/post-quantum-encryption-container-is-taken-out-by-single-core-pc-and-1-hour\/","url_meta":{"origin":35290,"position":0},"title":"Post-quantum encryption container is taken out by single-core PC and 1 hour","date":"August 2, 2022","format":false,"excerpt":"Getty Images In the US government's ongoing campaign to protect data in the age of quantum computers, a new and powerful attack that used a single traditional computer to completely break a fourth-round candidate highlights the risks involved in standardizing the next generation of encryption algorithms. Last month, the US\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":49844,"url":"https:\/\/harchi90.com\/vpns-for-ios-are-broken-and-apple-knows-it-says-security-researcher\/","url_meta":{"origin":35290,"position":1},"title":"VPNs for iOS Are Broken and Apple Knows It, Says Security Researcher","date":"August 19, 2022","format":false,"excerpt":"Third-party VPNs made for iPhones and iPads routinely fail to route all network traffic through a secure tunnel after they have been turned on, something Apple has known about for years, a longtime security researcher has claimed (via ArsTechnica). Writing on a continually updated blog post, Michael Horowitz says that\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"settings","src":"https:\/\/i0.wp.com\/images.macrumors.com\/t\/y_9LPTUwaW5u1jhso1SbHoF7Ou4=\/400x0\/article-new\/2022\/08\/vpn-ios-settings.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":29210,"url":"https:\/\/harchi90.com\/new-hardware-offers-faster-computation-for-artificial-intelligence-with-much-less-energy\/","url_meta":{"origin":35290,"position":2},"title":"New hardware offers faster computation for artificial intelligence, with much less energy","date":"July 29, 2022","format":false,"excerpt":"An analog deep learning processor powered by ultrafast protonics. Credit: Ella Maru Studio, Murat Onen As scientists push the boundaries of machine learning, the amount of time, energy, and money required to train increasingly complex neural network models is skyrocketing. A new area of \u200b\u200bartificial intelligence called analog deep learning\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"New hardware offers faster computation for artificial intelligence, with much less energy","src":"https:\/\/i0.wp.com\/scx1.b-cdn.net\/csz\/news\/800a\/2022\/new-hardware-offers-fa.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":22932,"url":"https:\/\/harchi90.com\/5g-is-here-sort-of-these-are-the-innovations-were-waiting-for\/","url_meta":{"origin":35290,"position":3},"title":"5G Is Here, Sort Of: These Are the Innovations We’re Waiting For","date":"July 23, 2022","format":false,"excerpt":"Sure, 5G networks are expanding, and we're starting to get higher-quality video, lag-free gaming and even wireless-based home internet. But that's just scratching the surface of what's possible. The wilder ideas of 5G promise things like connected cars that warn one another in milliseconds so as to avoid crashes, or\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"Cars driving on a road with awareness circles around tires and a data stream in the road.","src":"https:\/\/i0.wp.com\/www.cnet.com\/a\/img\/resize\/fabddc8a7f889794f91bc2bea8b0b36bf0bdc184\/2022\/07\/20\/287b0cd7-be70-47d5-9d3d-31dced4f333f\/cars.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":51631,"url":"https:\/\/harchi90.com\/protons-could-contain-a-smaller-particle-that-is-heavier-than-the-proton-itself-sciencealert\/","url_meta":{"origin":35290,"position":4},"title":"Protons Could Contain a Smaller Particle That Is Heavier Than The Proton Itself : ScienceAlert","date":"August 21, 2022","format":false,"excerpt":"Protons may have more \"charm\" than we thought, new research suggests.A proton is one of the subatomic particles that make up the nucleus of an atom. As small as protons are, they are composed of even tinier elementary particles known as quarks, which come in a variety of \"flavors,\" or\u2026","rel":"","context":"In "Technology"","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"fifu_image_url":"https:\/\/news.mit.edu\/sites\/default\/files\/images\/202208\/MIT-Starvation-Avoidance-01-press.jpg","_links":{"self":[{"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/posts\/35290"}],"collection":[{"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/comments?post=35290"}],"version-history":[{"count":0,"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/posts\/35290\/revisions"}],"wp:attachment":[{"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/media?parent=35290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/categories?post=35290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/harchi90.com\/wp-json\/wp\/v2\/tags?post=35290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}