Three Ph.D. theses win honors in networking, machine learning

by Doug Hulette

Every few weeks, it seems that some high-profile, public network (airline operations, online services, sometimes critical infrastructure like banking) goes dark, leaving users to curse the systems and the people who run them.

Ryan Beckett, who earned a doctoral degree in computer science last year, has uncovered a path toward fixing the problems that too frequently disrupt the lives of countless people around the world. His dissertation, titled “Network Control Plane Synthesis and Verification,” was one of three by 2018 Ph.D. graduates of the Princeton Computer Science Department that have earned high honors from the Association for Computing Machinery, the industry’s main scholarly and professional society, and SIGCOMM, the ACM’s special interest group for communications and computer networks.

Beckett’s dissertation won SIGCOMM’s award as the Outstanding Ph.D. Thesis in Computer Networking and Data Communication, for “pioneering contributions in extending the field of network control plane verification and synthesis.” His fellow 2018 graduate, Arpit Gupta, won Honorable Mention in the same category for his thesis, “Flexible and Scalable Systems for Network Management,” which SIGCOMM described as “impactful work on Software Defined Internet Exchange Point design and implementation.”

Beckett’s work also won Honorable Mention in the parent organization’s Doctoral Dissertation Award for Outstanding Ph.D. Thesis, and Tengyu Ma won the only other Honorable Mention awarded by ACM in that category, for his thesis, “Non-convex Optimization for Machine Learning: Design, Analysis, and Understanding,” for developing “novel theory to support new trends in machine learning.” 

Tengyu Ma (center left) and Ryan Beckett (center right) accept Honorable Mentions for the ACM's Doctoral Dissertation Award for Outstanding Ph.D. Thesis at the awards banquet on June 15, 2019.  photo by Michael Freedman

Beckett’s award-winning SIGCOMM thesis centered on how to configure and validate network control planes, the software programs that decide which paths network traffic should follow. Doing so is especially challenging not only because of the mind-boggling number of variables in large networks but because of the dynamic nature of control planes’ decision making, according to professor David Walker, who was Beckett’s thesis adviser. A bad routing decision can bring down an entire system.

Walker highlighted Beckett’s development of Propane, a high-level language that he said represented a “shocking reduction in complexity” in the coding process for configuring network control planes. “Whereas a data center might need 100,000 lines of assembly-language-like code to specify routing across all of its devices, Propane might specify the equivalent policy in less than 100 lines (plus a few hundred more to define groups of prefixes and peer groups),” he wrote in a summary of the dissertation. 

Beckett also developed another significant tool, called MineSweeper, that analyzes network configurations and then converts them to logical formulas for analysis. 

Beckett won an ACM SIGCOMM Distinguished Paper Award in 2016 for Propane, which works on routers that are used in most networks in the world and enables coders to specify preferences between routes, so the control plane can recover from failures automatically.

“When it comes to problems at the intersection of networking and formal methods, Ryan Beckett is the most knowledgeable and effective researcher in the world, of any seniority level, and his thesis puts his full range of skills on display,” Walker said.

Beckett is now a researcher in the Mobility and Networking group at Microsoft Research in Redmond, Washington. 
 

Gupta will join the computer science department at UC Santa Barbara as a tenure-track assistant professor in September 2019, after completing postdoctoral research at Columbia. On his personal site, he said his research aims to answer a question that has bedeviled network-management professionals as the fast-growing number of networked devices, systems, and applications has multiplied problems related to security, availability, and performance: How can networks run themselves?  

“My goal is to design and build self-driving networks that automatically (with no or little human intervention) make holistic (not protocol-specific) control decisions in real time,” he said.

Gupta’s thesis adviser, professor Nick Feamster, said, “Arpit’s work is among the most highly cited networking papers of his generation. One of his projects, the Software Defined Internet Exchange Point (SDX), is a phenomenal success—a home run that ranks among our field’s ‘greatest hits’ in the last five years. Arpit’s dissertation is among the best bodies of work that our community has seen in years, and will likely be the best for years to come.”

Feamster said Gupta’s development of SDX and Sonata, a network telemetry system, together point the way to answering two compelling questions: “Can we close the control loop, finally allowing networks to perform certain network management tasks in a completely automated fashion? More specifically: Can we completely automate certain aspects of traffic engineering or network security?”

“The concept of a ‘self-driving network’ is compelling and is as close to a ‘moonshot’ as our community has seen in perhaps the last decade. I fully expect Arpit to be at the forefront of driving this new frontier of networking research,” Feamster said.

Ma’s thesis adviser, professor Sanjeev Arora, said the dissertation “breaks new ground on developing theory to support new trends in machine learning.” At issue is the growing application of nonconvex optimization, which can produce multiple solutions derived from diverse factors, while traditional theory has largely centered on algorithms that produce a single global solution or prove that there is no solution.

“With the rise of deep learning, it is a pressing problem to understand conditions under which nonconvex optimization can be carried out to provably yield optimal solutions (or near-optimal solutions),” Arora said. “Ma’s thesis advances the state of the art in this field. He studies a range of problems—sparse coding, topic models, word embeddings, linear dynamical systems, etc.—and formalizes clear and natural conditions under which one can design provably correct and efficient optimization algorithms. These problems can be seen as simple/shallow subcases of deep models.”

Ma is an assistant professor of computer science and statistics at Stanford. His personal site says, “My research interests broadly include topics in machine learning and algorithms, such as non-convex optimization, deep learning and its theory, reinforcement learning, representation learning, distributed optimization, convex relaxation (e.g., sum of squares hierarchy), and high-dimensional statistics.”

SIGCOMM created its Doctoral Dissertation Award in 2011 to recognize “excellent thesis research by doctoral candidates in the field of computer networking and data communication.” The award winner will receive a plaque, a $1,500 honorarium and a complimentary registration to the following year’s ACM SIGCOMM Conference.  The ACM Honorable Mention Award winners get a prize totaling $10,000.