In the 21st century, design contests have emerged as a way to make rapid progress on tough computational problems. The million-dollar Netflix Prize, which sought to improve Netflix’s movie recommendation algorithm, is probably the most high-profile example. But similar, if lower-stakes, contests have addressed problems in computer vision, medical-data analysis, and weather prediction.
In 2012, two PhD students in the lab of Hari Balakrishnan, the Fujitsu Professor of Computer Science and Engineering, hatched the idea of bringing that type of contest into the classroom. The next semester — spring 2013 — the graduate-level networking course that Balakrishnan taught featured a two-week research project in which 20 two-person student teams designed competing protocols for managing congestion in cellular networks.
That same spring, Balakrishnan’s research group was scheduled to present such a protocol — dubbed Sprout — at a major networking conference. So the prize for any team that could better Sprout’s performance was co-authorship of a paper describing both the contest and its results. Two teams of students — both consisting of undergraduates — are on the paper, which appeared in July in the Association of Computing Machinery’s Computer Communications Review.
“It was a privilege to be able to work with 40 MIT students and to harvest their creativity,” says Anirudh Sivaraman, one of the graduate students who helped design the contest, and first author on the paper published last month. “You don’t get this kind of access to really smart people working on a problem in a focused manner elsewhere.”
Decongestant
Congestion arises when devices connected to a network flood it with too many requests. Congestion protocols generally throttle senders’ transmissions when they detect evidence of congestion, such as delays or lost data packets.
Networks are typically evaluated according to two criteria: Delay is one of them, and throughput — the total amount of data that the network can handle in a given span of time — is the other. Students’ submissions were evaluated according to the ratio of throughput to delay.
In a two-week span, the students tested nearly 3,000 variations on several dozen protocols designs. The protocols’ performance, Sivaraman says, suggests a clear trade-off between delay and throughput, which could be useful information for protocol designers.
“There are theoretical characterizations for much more well-defined problems,” Sivaraman says. “But the kind of problem that we were interested in, which was defined by a trace of packet deliveries for a cellular network — it’s much harder to characterize this mathematically.”
“We were able to actually trace out this design space and say that our own protocol, Sprout, was somewhere on the frontier — that hey, people can do better than us on throughput, or on delay, but probably not on both,” he continues. “That was scientifically probably a bigger deal for us than getting a student to do better or worse on a particular metric.”
Joining Sivaraman and Balakrishnan on the Computer Communications Review paper are Keith Winstein, then a graduate student at MIT and now an assistant professor at Stanford University, who first proposed the idea of the contest; Pauline Varley, an undergraduate who, under the auspices of MIT’s Undergraduate Research Opportunity Program, helped Sivaraman and Winstein administer and build the computational infrastructure to support the contest; and the four contest winners: João Batalha ’13, Ameesh Goyal ’14, Somak Das ’14, and Joshua Ma ’14.
Both winning protocols throttled transmission across the network according to a moving average of the intervals between packets’ arrival times. Many of the candidate protocols that the winners canvassed differed only in how the averages were calculated — how much weight they gave to measurements made at different times.
Hands on
Project-based educational initiatives like the protocol design contest are of particular interest on the MIT campus these days, as the Institute offers more and more courses through the edX online-education initiative it launched with Harvard University. Many in the education community believe that, as online resources enable students to watch lectures and find answers to questions on their own time, the classroom experience will need to evolve. One possibility is that it will become more project-focused.
“The students definitely liked the aspect of working on a cutting-edge research problem,” Sivaraman says. “Pedagogically, it helped to be working toward a realistic objective that people were publishing on.”
“We are seeing more and more new uses of the Internet, and probably networking protocols are going to adapt and evolve,” says Augustin Chaintreau, an assistant professor of computer science at Columbia University who was one of the paper’s referees. “One way to explore all the options is to organize contests like that.”
The MIT experiment also demonstrates, Chaintreau says, that as protocols evolve, contests could help define their performance goals. In protocol design, he says, “you have to trade off power for efficiency and compatibility. And having an idea of how much you lose by making one of these sacrifices and how much you gain is a very important problem for what we have to do today.”
