Publication

Libra: Divide and Conquer to Verify Forwarding Tables in Huge Networks

USENIX Symposium on Networked Systems Design and Implementation (NSDI)


Abstract

Data center networks often have errors in the forwarding tables, causing packets to loop indefinitely, fall into black-holes or simply get dropped before they reach the correct destination. Finding forwarding errors is possible using static analysis, but none of the existing tools scale to a large data center network with thousands of switches and millions of forwarding entries. Worse still, in a large data center network the forwarding state is constantly in flux, which makes it hard to take an accurate snapshot of the state for static analysis.

We solve these problems with Libra, a new tool for verifying forwarding tables in very large networks. Libra runs fast because it can exploit the scaling properties of MapReduce. We show how Libra can take an accurate snapshot of the forwarding state 99.9% of the time, and knows when the snapshot cannot be trusted. We show results for Libra analyzing a 10,000 switch.

Related Publications

All Publications

TSE - May 6, 2021

Comparative Analysis of Constraint Handling Techniques for Constrained Combinatorial Testing

Huayao Wu, Changhai Nie, Justyna Petke, Yue Jia, Mark Harman

EASE - May 10, 2021

Facebook’s Cyber–Cyber and Cyber–Physical Digital Twins

John Ahlgren, Kinga Bojarczuk, Sophia Drossopoulou, Inna Dvortsova, Johann George, Natalija Gucevska, Mark Harman, Maria Lomeli, Simon Mark Lucas, Erik Meijer, Steve Omohundro, Rubmary Rojas, Silvia Sapora, Jie M. Zhang, Norm Zhou

International Workshop on Mutation Analysis at ICST - May 6, 2021

An Empirical Comparison of Mutant Selection Assessment Metrics

Jie M. Zhang, Lingming Zhang, Dan Hao, Lu Zhang, Mark Harman

NSDI - April 12, 2021

A Social Network Under Social Distancing: Risk-Driven Backbone Management During COVID-19 and Beyond

Yiting Xia, Ying Zhang, Zhizhen Zhong, Guanqing Yan, Chiun Lin Lim, Satyajeet Singh Ahuja, Soshant Bali, Alexander Nikolaidis, Kimia Ghobadi, Manya Ghobadi

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy