Protocol Design Contests

A. Sivaraman, K. Winstein, P. Varley, J. Batalha, A. Goyal, S. Das, J. Ma, H. Balakrishnan
Appears in: 
CCR July 2014

In fields like data mining and natural language processing, design contests have been successfully used to advance the state of the art. Such contests offer an opportunity to bring the excitement and challenges of protocol design - one of the core intellectual elements of research and practice in networked systems - to a broader group of potential contributors, whose ideas may prove important. Moreover, it may lead to an increase in the number of students, especially undergraduates or those learning via online courses, interested in pursuing a career in the field. We describe the creation of the infrastructure and our experience with a protocol design contest conducted in MIT's graduate Computer Networks class. This contest involved the design and evaluation of a congestion-control protocol for paths traversing cellular wireless networks. One key to the success of a design contest is an unambiguous, measurable objective to compare protocols. In practice, protocol design is the art of trading off conflicting goals with each other, but in this contest, we specified that the goal was to maximize log(throughput/delay). This goal is a good match for applications such as video streaming or videoconferencing that care about high throughput and low interactive delays. Some students produced protocols whose performance was better than published protocols tackling similar goals. Furthermore, the convex hull of the set of all student protocols traced out a tradeoff curve in the throughput-delay space, providing useful insights into the entire space of possible protocols. We found that student protocols diverged in performance between the training and testing traces, indicating that some students had overtrained ("overfitted") their protocols to the training trace. Our conclusion is that, if designed properly, such contests could benefit networking research by making new proposals more easily reproducible and amenable to such "gamification," improve networked systems, and provide an avenue for outreach.

Public Review By: 
Augustin Chaintreau

“I entered a local singing competition called Stratford Idol. I wasn’t taking it too seriously at the time. I was only 12 and I got second place.” – widely attributed on the web to Justin Bieber Our culture abounds with artists triaged and discovered through local contest. But TCP did not win Apollo theater’s Amateur nights. Can this change? What would it take to make network protocol design a topic of contests open to a wide audience? and what can we learn from the process? This paper answers the questions above as it reports on the first design contest for network protocols. Focusing on a specific case – handling congestion in cellular wireless networks – that was the subject of recent research, the authors prove that design contests work. Not only are superior protocols discovered, but the collective results of 3,000 submissions provide additional insight: performance tradeoff in protocols, and over-optimization, just like overfitting sometimes fool elaborate machine learning algorithms with bias in the data, both appear in a new light. In the end, it’s reassuring that a network protocol designed traditionally within our peer-reviewed system beats most submissions, but it also shows we have room to improve. The paper also points to additional advantages of design contests, including reproducibility, that greatly benefit our community as a whole. If more protocol contests are to be organized to gather similar insights – and the paper overall makes a strong case that this should be the case – there is no doubt that this work will stimulate more research on problems that remain open: How to ensure and encourage participation, especially outside an educational setting? What to do with a protocol that performs extremely well but seems difficult to interpret? Network problems in general, and congestion control in particular, are rarely solved for an isolated flow. Since cellular networks maintain a per-user queue that isolates traffic from different users, this problem is not posed here. But more generally, how would a contest account for fairness? One could caricature protocol contests as a great way to have all of us out of job. After reading this paper, however, you may believe that the reality is more nuanced. First, it certainly seems to help us do our job better, and poses exciting new challenges on the way. We hence have reasons to believe protocol contests and more traditional approaches are great complements. Second, the nature of protocol design and our Internet standards has been to embrace open contributions. The fact that many other fields benefitted from this approach and that networking has yet to prove itself compatible with it, in retrospect, appears as an oddity. It's not this paper’s least merit to challenge that status quo.