Connect with us

Science & Technology

Researchers discover major roadblock in alleviating network congestion

Algorithms designed to ensure multiple users share a network fairly can’t prevent some users from hogging all the bandwidth

EP Staff

Published

on

Written by Adam Zewe, MIT News Office

When users want to send data over the internet faster than the network can handle, congestion can occur — 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 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.

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.

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.

“What 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,” says Mohammad Alizadeh, associate professor of electrical engineering and computer science (EECS).

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.

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.

Controlling congestion

Congestion control is a fundamental problem in networking that researchers have been trying to tackle since the 1980s.

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.

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 acknowledgement might be delayed. The authors call delays that are not caused by congestion “jitter.”

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.

“We 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,” he says.

Studying starvation

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.

“We 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,” Arun says.

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 “delay-convergent algorithms” 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.

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.

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.

“To 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,” Balakrishnan adds.

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.

“We are increasingly reliant 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,” says Alizadeh.

Science & Technology

Study: Superconductivity switches on and off in “magic-angle” graphene

A quick electric pulse completely flips the material’s electronic properties, opening a route to ultrafast, brain-inspired, superconducting electronics

EP Staff

Published

on

Written by Jennifer Chu, MIT News Office

With some careful twisting and stacking, MIT physicists have revealed a new and exotic property in “magic-angle” graphene: superconductivity that can be turned on and off with an electric pulse, much like a light switch.

The discovery could lead to ultrafast, energy-efficient superconducting  transistors for neuromorphic devices — electronics designed to operate in a way similar to the rapid on/off firing of neurons in the human brain.

Magic-angle graphene refers to a very particular stacking of graphene — an atom-thin material made from carbon atoms that are linked in a hexagonal pattern resembling chicken wire. When one sheet of graphene is stacked atop a second sheet at a precise “magic” angle, the twisted structure creates a slightly offset “moiré” pattern, or superlattice, that is able to support a host of surprising electronic behaviors.

In 2018, Pablo Jarillo-Herrero and his group at MIT were the first to demonstrate magic-angle twisted bilayer graphene. They showed that the new bilayer structure could behave as an insulator, much like wood, when they applied a certain continuous electric field. When they upped the field, the insulator suddenly morphed into a superconductor, allowing electrons to flow, friction-free.

That discovery gave rise to “twistronics,” a field that explores how certain electronic properties emerge from the twisting and layering of two-dimensional materials. Researchers including Jarillo-Herrero have continued to reveal surprising properties in magic-angle graphene, including various ways to switch the material between different electronic states. So far, such “switches” have acted more like dimmers, in that researchers must continuously apply an electric or magnetic field to turn on superconductivity, and keep it on.

Now Jarillo-Herrero and his team have shown that superconductivity in magic-angle graphene can be switched on, and kept on, with just a short pulse rather than a continuous electric field. The key, they found was a combination of twisting and stacking.

In a paper appearing today in Nature Nanotechnology, the team reports that, by stacking magic-angle graphene between two offset layers of boron nitride — a two-dimensional insulating material — the unique alignment of the sandwich structure enabled the researchers to turn graphene’s superconductivity on and off with a short electric pulse.

“For the vast majority of materials, if you remove the electric field, zzzzip, the electric state is gone,” says Jarillo-Herrero, who is the Cecil and Ida Green Professor of Physics at MIT. “This is the first time that a superconducting material has been made that can be electrically switched on and off, abruptly. This could pave the way for a new generation of twisted, graphene-based superconducting electronics.”

His MIT co-authors are lead author Dahlia Klein, Li-Qiao Xia, and David MacNeill, along with Kenji Watanabe and Takashi Taniguchi of the National Institute for Materials Science in Japan.

Flipping the switch

In 2019, a team at Stanford University discovered that magic-angle graphene could be coerced into a ferromagnetic state. Ferromagnets are materials that retain their magnetic properties, even in the absence of an externally applied magnetic field.

The researchers found that magic-angle graphene could exhibit ferromagnetic properties in a way that could be tuned on and off. This happened when the graphene sheets were layered between two sheets of boron nitride such that the crystal structure of the graphene was aligned to one of the boron nitride layers. The arrangement resembled a cheese sandwich in which the top slice of bread and the cheese orientations are aligned, but the bottom slice of bread is rotated at a random angle with respect to the top slice. The result intrigued the MIT group.

“We were trying to get a stronger magnet by aligning both slices,” Jarillo-Herrero says. “Instead, we found something completely different.”

In their current study, the team fabricated a sandwich of carefully angled and stacked materials. The “cheese” of the sandwich consisted of magic-angle graphene — two graphene sheets, the top rotated slightly at the “magic” angle of 1.1 degrees with respect to the bottom sheet. Above this structure, they placed a layer of boron nitride, exactly aligned with the top graphene sheet. Finally, they placed a second layer of boron nitride below the entire structure and offset it by 30 degrees with respect to the top layer of boron nitride.

The team then measured the electrical resistance of the graphene layers as they applied a gate voltage. They found, as others have, that the twisted bilayer graphene switched electronic states, changing between insulating, conducting, and  superconducting states at certain known voltages.

What the group did not expect was that each electronic state persisted rather than immediately disappearing once the voltage was removed — a property known as bistability. They found that, at a particular voltage, the graphene layers turned into a superconductor, and remained superconducting, even as the researchers removed this voltage.  

This bistable effect suggests that superconductivity can be turned on and off with short electric pulses rather than a continuous electric field, similar to flicking a light switch. It isn’t clear what enables this switchable superconductivity, though the researchers suspect it has something to do with the special alignment of the twisted graphene to both boron nitride layers, which enables a ferroelectric-like response of the system. (Ferroelectric materials display bistability in their electric properties.)

“By paying attention to the stacking, you could add another tuning knob to the growing complexity of magic-angle, superconducting devices,” Klein says. 

For now, the team sees the new superconducting switch as another tool researchers can consider as they develop materials for faster, smaller, more energy-efficient electronics.

“People are trying to build electronic devices that do calculations in a way that’s inspired by the brain,” Jarillo-Herrero says. “In the brain, we have neurons that, beyond a certain threshold, they fire. Similarly, we now have found a way for magic-angle graphene to switch superconductivity abruptly, beyond a certain threshold. This is a key property in realizing neuromorphic computing.”  

This research was supported in part by the Air Force Office of Scientific Research, the Army Research Office, and the Gordon and Betty Moore Foundation.

Continue Reading

Science & Technology

When should data scientists try a new technique?

A new measure can help scientists decide which estimation method to use when modeling a particular data problem

EP Staff

Published

on

Written by Adam Zewe, MIT News Office

If a scientist wanted to forecast ocean currents to understand how pollution travels after an oil spill, she could use a common approach that looks at currents traveling between 10 and 200 kilometers. Or, she could choose a newer model that also includes shorter currents. This might be more accurate, but it could also require learning new software or running new computational experiments. How to know if it will be worth the time, cost, and effort to use the new method?

A new approach developed by MIT researchers could help data scientists answer this question, whether they are looking at statistics on ocean currents, violent crime, children’s reading ability, or any number of other types of datasets.

The team created a new measure, known as the “c-value,” that helps users choose between techniques based on the chance that a new method is more accurate for a specific dataset. This measure answers the question “is it likely that the new method is more accurate for this data than the common approach?”

Traditionally, statisticians compare methods by averaging a method’s accuracy across all possible datasets. But just because a new method is better for all datasets on average doesn’t mean it will actually provide a better estimate using one particular dataset. Averages are not application-specific.

So, researchers from MIT and elsewhere created the c-value, which is a dataset-specific tool. A high c-value means it is unlikely a new method will be less accurate than the original method on a specific data problem.

In their proof-of-concept paper, the researchers describe and evaluate the c-value using real-world data analysis problems: modeling ocean currents, estimating violent crime in neighborhoods, and approximating student reading ability at schools. They show how the c-value could help statisticians and data analysts achieve more accurate results by indicating when to use alternative estimation methods they otherwise might have ignored.

“What we are trying to do with this particular work is come up with something that is data specific. The classical notion of risk is really natural for someone developing a new method. That person wants their method to work well for all of their users on average. But a user of a method wants something that will work on their individual problem. We’ve shown that the c-value is a very practical proof-of-concept in that direction,” says senior author Tamara Broderick, an associate professor in the Department of Electrical Engineering and Computer Science (EECS) and a member of the Laboratory for Information and Decision Systems and the Institute for Data, Systems, and Society.

She’s joined on the paper by Brian Trippe PhD ’22, a former graduate student in Broderick’s group who is now a postdoc at Columbia University; and Sameer Deshpande ’13, a former postdoc in Broderick’s group who is now an assistant professor at the University of Wisconsin at Madison. An accepted version of the paper is posted online in the Journal of the American Statistical Association.

Evaluating estimators

The c-value is designed to help with data problems in which researchers seek to estimate an unknown parameter using a dataset, such as estimating average student reading ability from a dataset of assessment results and student survey responses. A researcher has two estimation methods and must decide which to use for this particular problem.

The better estimation method is the one that results in less “loss,” which means the estimate will be closer to the ground truth. Conder again the forecasting of ocean currents: Perhaps being off by a few meters per hour isn’t so bad, but being off by many kilometers per hour makes the estimate useless. The ground truth is unknown, though; the scientist is trying to estimate it. Therefore, one can never actually compute the loss of an estimate for their specific data. That’s what makes comparing estimates challenging. The c-value helps a scientist navigate this challenge.

The c-value equation uses a specific dataset to compute the estimate with each method, and then once more to compute the c-value between the methods. If the c-value is large, it is unlikely that the alternative method is going to be worse and yield less accurate estimates than the original method.

“In our case, we are assuming that you conservatively want to stay with the default estimator, and you only want to go to the new estimator if you feel very confident about it. With a high c-value, it’s likely that the new estimate is more accurate. If you get a low c-value, you can’t say anything conclusive. You might have actually done better, but you just don’t know,” Broderick explains.

Probing the theory

The researchers put that theory to the test by evaluating three real-world data analysis problems.

For one, they used the c-value to help determine which approach is best for modeling ocean currents, a problem Trippe has been tackling. Accurate models are important for predicting the dispersion of contaminants, like pollution from an oil spill. The team found that estimating ocean currents using multiple scales, one larger and one smaller, likely yields higher accuracy than using only larger scale measurements.

“Oceans researchers are studying this, and the c-value can provide some statistical ‘oomph’ to support modeling the smaller scale,” Broderick says.

In another example, the researchers sought to predict violent crime in census tracts in Philadelphia, an application Deshpande has been studying. Using the c-value, they found that one could get better estimates about violent crime rates by incorporating information about census-tract-level nonviolent crime into the analysis. They also used the c-value to show that additionally leveraging violent crime data from neighboring census tracts in the analysis isn’t likely to provide further accuracy improvements.

“That doesn’t mean there isn’t an improvement, that just means that we don’t feel confident saying that you will get it,” she says.

Now that they have proven the c-value in theory and shown how it could be used to tackle real-world data problems, the researchers want to expand the measure to more types of data and a wider set of model classes.

The ultimate goal is to create a measure that is general enough for many more data analysis problems, and while there is still a lot of work to do to realize that objective, Broderick says this is an important and exciting first step in the right direction.

This research was supported, in part, by an Advanced Research Projects Agency-Energy grant, a National Science Foundation CAREER Award, the Office of Naval Research, and the Wisconsin Alumni Research Foundation.

Continue Reading

Science & Technology

How to push, wiggle, or drill an object through sand

A method for quickly predicting the forces needed to push objects through soft, granular materials could help engineers drive robots or anchor ships

EP Staff

Published

on

Written by Jennifer Chu, MIT News Office

Pushing a shovel through snow, planting an umbrella on the beach, wading through a ball pit, and driving over gravel all have one thing in common: They all are exercises in intrusion, with an intruding object exerting some force to move through a soft and granular material.

Predicting what it takes to push through sand, gravel, or other soft media can help engineers drive a rover over Martian soil, anchor a ship in rough seas, and walk a robot through sand and mud. But modeling the forces involved in such processes is a huge computational challenge that often takes days to weeks to solve.

Now, engineers at MIT and Georgia Tech have found a faster and simpler way to model intrusion through any soft, flowable material. Their new method quickly maps the forces it would take to push, wiggle, and drill an object through granular material in real-time. The method can apply to objects and grains of any size and shape, and does not require complex computational tools as other methods do.

“We now have a formula that can be very useful in settings where you have to check through lots of options as fast as possible,” says Ken Kamrin, professor of mechanical engineering at MIT.

“This is especially useful for applications such as real-time path-planning for vehicles traveling through vast deserts and other off-road terrains, that cannot wait for existing slower simulation methods to decide their path,” adds Shashank Agarwal SM ’19, PhD ’22.

Kamrin and Agarwal detail their new method in a study appearing this week in the journal Proceedings of the National Academy of Sciences. The study also includes Daniel I. Goldman, professor of physics at Georgia Tech.

A fluid connection

In order to know how much to push on an object to move it through sand, one could go grain by grain, using discrete element modeling, or DEM — an approach that systematically calculates each individual grain’s motion in response to a given force. DEM is precise but slow, and it can take weeks to fully solve a practical problem involving just a handful of sand. As a faster alternative, scientists can develop continuum models, which simulate granular behavior in generalized chunks, or grain groupings. This more simplified approach can still generate a detailed picture of how grains flow, in a way that can shave a weeks-long problem down to days or even hours.

“We wanted to see if we could do even better than that and cut that process down to seconds,” Agarwal says.

The team looked to previous work by Goldman. In 2014, he was studying how animals and robots move through dry, granular material such as sand and soil. In looking for ways to quantitatively describe their movements, he found he could do so with a quick relationship that was originally meant to describe fluid swimmers.

The formulation, Resistive Force Theory (RFT), works by considering an object’s surface as a collection of small plates. (Imagine representing a sphere as a soccer ball.) As an object moves through a fluid, each plate experiences a force, and RFT claims that the force on each plate depends only on its local orientation and movement. The equation takes all this into account, along with the fluid’s individual characteristics, to ultimately describe how the object as a whole moves through a fluid.

Surprisingly, Goldman found this simple approach was also accurate when applied to granular intrusion. Specifically, it predicted the forces lizards and snakes exert to slither through sand, as well as how small, legged robots walk over soil. The question, Kamrin says, was why?

“It was this weird mystery why this theory, which was originally derived for moving through viscous fluid, would even work at all in granular media, which has completely different flow behavior,” he says.

Kamrin took a closer look at the math and found a connection between RFT and a continuum model he had derived to describe granular flow. In other words, the physics checked out, and RFT could indeed be an accurate way to predict granular flow, in a simpler and faster way than conventional models. But there was one big limitation: The approach was mainly workable for two-dimensional problems.

To model intrusion using RFT, one needs to know what will happen if one moves a plate every which way possible — a task that is manageable in two dimensions, but not in three. The team then needed some shortcut to simplify 3D’s complexity.

Wacky twist

In their new study, the researchers adapted RFT to 3D by adding an extra ingredient to the equation. That ingredient is a plate’s twist angle, measuring how plate orientation changes as the entire object is rotated. When they incorporated this extra angle, in addition to a plate’s tilt and direction of motion, the team had enough information to define the force acting on the plate as it moves through a material in 3D. Importantly, by exploiting the connection to continuum modeling, the resulting 3D-RFT  is generalizable, and can be easily recalibrated to apply to many dry granular media on Earth, and even on other planetary bodies.

The researchers demonstrated the new method using a variety of three-dimensional objects, from simple cylinders and cubes to more complex bunny- and monkey-shaped geometries. They first tiled the objects, representing them each as a collection of hundreds to thousands of tiny plates. Then they applied the tweaked RFT formula to each individual plate and calculated the forces that would be needed over time to drill each plate, and ultimately the entire object, down through a bed of sand.

“For more wacky objects, like the bunny, you can imagine having to consistently shift your loads to keep drilling it straight down,” Kamrin says. “And our method can even predict those little wiggles, and the distribution of force all around the bunny, in less than a minute.”

The new approach provides a fast and accurate way to model granular intrusion, which can be applied to a host of practical problems, from driving a rover through Martian soil, to characterizing the movement of animals through sand, and even predicting what it would take to uproot a tree.

“Can I predict how hard it is to uproot natural plants? You might want to know, is this storm going to knock over this tree?” Kamrin says. “Here is a way to get an answer fast.”

This research was supported, in part, by the Army Research Office, the U.S. Army DEVCOM Ground Vehicle Systems Center, and NASA.

Continue Reading

Trending