Welcome to the Networked Systems Lab!

About

Founded in 2002, our laboratory conducts research on the design and implementation of a wide range of networked computing systems.

Selected Recent Publications

  1. NSDI
    Solving Max-Min Fair Resource Allocations Quickly on Large Graphs
    Namyar, Pooria, Arzani, Behnaz, Kandula, Srikanth, Segarra, Santiago, Crankshaw, Daniel, Krishnaswamy, Umesh, Govindan, Ramesh, and Raj, Himanshu
    In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24) 2024

    We consider the max-min fair resource allocation problem. The best-known solutions either use a sequence of optimizations or waterfilling, which only applies to a narrow set of cases. These solutions have become a practical bottleneck in WAN traffic engineering and cluster scheduling, especially at larger problem sizes. We improve both approaches: (1) we show how to convert the optimization sequence into a single fast optimization, and (2) we generalize waterfilling to the multi-path case. We empirically show our new algorithms Pareto-dominate prior techniques: they produce faster, fairer, and more efficient allocations. Some of our allocators also have theoretical guarantees: they trade off a bounded amount of unfairness for faster allocation. We have deployed our allocators in Azure’s WAN traffic engineering pipeline, where we preserve solution quality and achieve a roughly 3× speedup.

  2. OSDI
    Jawa: Web Archival in the Era of JavaScript
    Goel, Ayush, Zhu, Jingyuan, Netravali, Ravi, and Madhyastha, Harsha V.
    In 16th USENIX Symposium on Operating Systems Design and Implementation 2022

    By repeatedly crawling and saving web pages over time, web archives (such as the Internet Archive) enable users to visit historical versions of any page. In this paper, we point out that existing web archives are not well designed to cope with the widespread presence of JavaScript on the web. Some archives store petabytes of JavaScript code, and yet many pages render incorrectly when users load them. Other archives which store the end-state of page loads (e.g., screen captures) break post-load interactions implemented in JavaScript. To address these problems, we present Jawa, a new design for web archives which significantly reduces the storage necessary to save modern web pages while also improving the fidelity with which archived pages are served. Key to enabling Jawa’s use at scale are our observations on a) the forms of non-determinism which impair the execution of JavaScript on archived pages, and b) the ways in which JavaScript’s execution fundamentally differs between live web pages and their archived copies. On a corpus of 1 million archived pages, Jawa reduces overall storage needs by 41%, when compared to the techniques currently used by the Internet Archive.

  3. MobiSys
    AutoCast: Scalable Infrastructure-Less Cooperative Perception for Distributed Collaborative Driving
    Qiu, Hang, Huang, Po-Han, Asavisanu, Namo, Liu, Xiaochen, Psounis, Konstantinos, and Govindan, Ramesh
    In Proceedings of the 20th Annual International Conference on Mobile Systems, Applications and Services 2022

    Autonomous vehicles use 3D sensors for perception. Cooperative perception enables vehicles to share sensor readings with each other to improve safety. Prior work in cooperative perception scales poorly even with infrastructure support. AUTOCAST1 enables scalable infrastructure-less cooperative perception using direct vehicle-to-vehicle communication. It carefully determines which objects to share based on positional relationships between traffic participants, and the time evolution of their trajectories. It coordinates vehicles and optimally schedules transmissions in a distributed fashion. Extensive evaluation results under different scenarios show that, unlike competing approaches, AUTOCAST can avoid crashes and near-misses which occur frequently without cooperative perception, its performance scales gracefully in dense traffic scenarios providing 2-4x visibility into safety critical objects compared to existing cooperative perception schemes, its transmission schedules can be completed on the real radio testbed, and its scheduling algorithm is near-optimal with negligible computation overhead.

  4. NSDI
    CloudCluster: Unearthing the Functional Structure of a Cloud Service
    Pang, Weiwu, Panda, Sourav, Amjad, Jehangir, Diot, Christophe, and Govindan, Ramesh
    In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22) 2022

    In their quest to provide customers with good tools to manage cloud services, cloud providers are hampered by having very little visibility into cloud service functionality; a provider often only knows where VMs of a service are placed, how the virtual networks are configured, how VMs are provisioned, and how VMs communicate with each other. In this paper, we show that, using the VM-to-VM traffic matrix, we can unearth the functional structure of a cloud service and use it to aid cloud service management. Leveraging the observation that cloud services use well-known design patterns for scaling (e.g., replication, communication locality), we show that clustering the VM-to-VM traffic matrix yields the functional structure of the cloud service. Our clustering algorithm, CloudCluster, must overcome challenges imposed by scale (cloud services contain tens of thousands of VMs) and must be robust to orders-of-magnitude variability in traffic volume and measurement noise. To do this, CloudCluster uses a novel combination of feature scaling, dimensionality reduction, and hierarchical clustering to achieve clustering with over 92% homogeneity and completeness. We show that CloudCluster can be used to explore opportunities to reduce cost for customers, identify anomalous traffic and potential misconfigurations.

  5. SIGCOMM
    Semi-Automated Protocol Disambiguation and Code Generation
    Yen, Jane, Lévai, Tamás, Ye, Qinyuan, Ren, Xiang, Govindan, Ramesh, and Raghavan, Barath
    In Proceedings of the 2021 ACM SIGCOMM 2021 Conference 2021

    For decades, Internet protocols have been specified using natural language. Given the ambiguity inherent in such text, it is not surprising that protocol implementations have long exhibited bugs. In this paper, we apply natural language processing (NLP) to effect semi-automated generation of protocol implementations from specification text. Our system, Sage, can uncover ambiguous or under-specified sentences in specifications; once these are clarified by the author of the protocol specification, Sage can generate protocol code automatically.Using Sage, we discover 5 instances of ambiguity and 6 instances of under-specification in the ICMP RFC; after fixing these, Sage is able to automatically generate code that interoperates perfectly with Linux implementations. We show that Sage generalizes to sections of BFD, IGMP, and NTP and identify additional conceptual components that Sage needs to support to generalize to complete, complex protocols like BGP and TCP.

News

Jul 1, 2023
Hang Qiu joins University of California, Riverside as an assistant professor. Congrats!

May 30, 2023
Our lab's work on estimating energy usage of Android apps receives the Impact Award at ISSTA 2023!

Nov 7, 2022
Our Wisden paper receives the Test of Time Award at Sensys 2022!

Sep 5, 2022
Quadrant accepted to SoCC 2022

May 4, 2022
Sarah Cooney accepts position at Villanova University. Congrats!

April 20, 2022
Fawad Ahmad accepts position at Rochester Institute of Technology. Congrats!

April 1, 2022
CloudCluster accepted to NSDI 2022

March 20, 2022
Autocast accepted to MobiSys 2022

December 3, 2021
Optimal Oblivious Routing accepted to Infocom 2022

... see all News