There are few things more frustrating than being on an online real-time phone call when it suddenly gets the jitters, your caller’s voice doesn’t match up to his or her facial expressions, and your conversation doesn’t sync correctly. Likewise, gamers are infuriated when sudden lags cause them to lose at what they’ve been playing for hours. These lags and jitters are caused by a phenomenon known as “bufferbloat.”
Now there is a fix for bufferbloat founded on research conducted at the University of Massachusetts Amherst more than a decade ago. During the late 1990s and early 2000s, current Columbia University Professor and UMass alumnus Vishal Misra (M.S. ’96, Ph.D. ’00) was conducting his doctoral and post-doctoral research in the UMass Amherst Electrical and Computer Engineering (ECE) Department with professors Weibo Gong, Kris Hollot, and Don Towsley. Based on this groundbreaking UMass research, Cisco Systems, Inc. has recently developed a bufferbloat-fix called “PIE” (for Proportional Integral controller Enhanced), a software algorithm soon to be deployed on most cable modems.
Bufferbloat is an issue in packet-switched networks, in which excess buffering of packets—meant to keep a congested link as busy as possible—causes high latency (a measure of the time delay experienced by a system) and packet delay variation, or jitter, while also reducing the overall network throughput. When a router device is configured to use excessively large buffers, even very high-speed networks can become practically unusable for many interactive applications such as voice calls, chat, and even web surfing. And this can occur even when there is more than enough bandwidth available to support these applications. In order to achieve low packet loss, the buffers become “bloated” and introduce unnecessary latency.
“This is a problem with modern Internet routers, including cable modems, which all have large buffers built in to absorb the variations in the traffic and congestion levels on the Internet and prevent packet loss,” says Misra.
As Cisco has explained its new bufferbloat-busting product, based on Misra’s research at UMass Amherst: “We present here a lightweight design, PIE, that can effectively control the average queueing latency to a target value. Simulation results, theoretical analysis, and Linux testbed results have shown that PIE can ensure low latency and achieve high link utilization under various congestion situations.” Link to PIE website written by Cisco employees citing papers published by Misra et al. in early 2000s as foundational work: https://tools.ietf.org/html/draft-pan-aqm-pie-02.
The foundational work for Cisco’s PIE was done as part of Misra’s Ph.D. thesis work on modeling the Transmission Control Protocol (TCP). TCP is the protocol that carries nearly all of the traffic on the Internet and is the key to understanding and solving the problem of bufferbloat.
The story of Misra’s bufferbloat research really began with an historic workshop that inspired the initial interaction between two disparate research groups, the feedback control community and the computer network community.
In 1996, program managers Dr. Kishan Baheti of the National Science Foundation and Dr. Linda Bushnell of the Army Research Office envisioned the need to bring the control systems community and the Internet community together to tackle new issues in network congestion. Gong and Towsley helped to organize a workshop entitled “Systems and Control Methods for Communication Networks” in Airlie, Virginia.
While the need for control theory in the Internet was clear, the lack of a dynamical model for the digital Internet, a starting point for control theory application, was a serious barrier. Then, in 1999, while Misra was listening to a lecture on stochastic differential equations by his Ph.D. advisor Gong when he realized he could use similar equations to model Internet TCP. So he approached Towsley, his co-advisor and an expert in network modeling. Towsley was intrigued because he had recently written a paper on modeling TCP throughput and had a lot of detailed TCP measurements.
“I gave the data to Vishal to validate his model,” Towsley says, “and he came back with a careful statistical study that showed a great match.”
At the SIGCOMM (the Association for Computing Machinery’s Special Interest Group on Data Communications, which specializes in the field of communication and computer networks) conference in 2000, Misra, Gong, and Towsley presented a highly influential paper on the TCP model based on the above idea that has received over 1,500 citations and forms the basis of TCP analysis by almost every researcher around the world.
“What separated Vishal’s model from what had been done prior to that,” notes Gong, “was the fact that it opened up entire new directions in TCP analysis, from understanding its dynamics to developing fast simulators.”
Misra adds that “As soon as I finished writing the TCP modeling paper, I realized that the way control was being done on the Internet was inefficient, and our model could help develop better control mechanisms. I decided to approach Hollot, a control theorist whom I had never spoken to before, and invited him to my Ph.D. defense. I told Kris that I have a very interesting model for traffic on the Internet that is ripe for some formal control theoretic analysis, and I will be presenting it at my dissertation defense if he’d like to come and see it.”
Hollot did come to Misra’s Ph.D. defense, got extremely interested, and he and Vishal started working on it the next day.
“Vishal and I often joke that I was his first graduate student,” Hollot laughs.
Hollot, Misra, Towsley, and Gong went on to produce a series of papers that have together received more than 3,000 citations. One of the first papers they wrote was on the Proportional Integral (PI) controller. In this study, they demonstrated that by observing the direction in which the router buffer queues change, they could provide a feedback signal that could proactively prevent bufferbloat. They also ensured that their controller algorithm was inexpensive to implement on routers.
That key paper and the research it described contained the panacea for Bufferbloat. But nothing much happened in the commercial world until 10 years later, in 2010. By this point cheaper memory and faster links had made the problem of bufferbloat even more acute, and Cisco researchers developed a mechanism to tackle bufferbloat by enhancing PI. Now this brilliant solution has been made the standard for the next version of cable modem software.
“It is very gratifying when you learn that your research has made a difference in the real world,” adds Misra. “That’s what you live for as a researcher.” (February 2015)