Verifying maximum link loads in a changing world

Authors: Tibor Schneider, Stefano Vissicchio, and Laurent Vanbever
22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 2025)

Abstract

To meet ever more stringent requirements, network operators often need to reason about worst-case link loads. Doing so involves analyzing traffic forwarding after failures and BGP route changes. State-of-the-art systems identify failure scenarios causing congestion, but they ignore route changes.

We present Viper, the first verification system that efficiently finds maximum link loads under failures and route changes. The key building block of Viper is its ability to massively reduce the gigantic space of possible route changes thanks to (i) a router-based abstraction for route changes, (ii) a theoretical characterization of scenarios leading to worst-case link loads, and (iii) an approximation of input traffic matrices. We fully implement and extensively evaluate Viper. Viper takes only a few minutes to accurately compute all worst-case link loads in large ISP networks. It thus provides operators with critical support to robustify network configurations, improve network management and take business decisions.

People

BibTex

@INPROCEEDINGS{schneider2025verifying,
	copyright = {In Copyright - Non-Commercial Use Permitted},
	year = {2025-04-28},
	type = {Conference Paper},
	author = {Schneider, Tibor and Vissicchio, Stefano and Vanbever, Laurent},
	size = {19 p.},
	abstract = {To meet ever more stringent requirements, network operators often need to reason about worst-case link loads. Doing so involves analyzing traffic forwarding after failures and BGP route changes. State-of-the-art systems identify failure scenarios causing congestion, but they ignore route changes.We present Viper, the first verification system that efficiently finds maximum link loads under failures and route changes. The key building block of Viper is its ability to massively reduce the gigantic space of possible route changes thanks to (i) a router-based abstraction for route changes, (ii) a theoretical characterization of scenarios leading to worst-case link loads, and (iii) an approximation of input traffic matrices. We fully implement and extensively evaluate Viper. Viper takes only a few minutes to accurately compute all worst-case link loads in large ISP networks. It thus provides operators with critical support to robustify network configurations, improve network management and take business decisions.},
	language = {en},
	title = {Verifying maximum link loads in a changing world},
	Note = {22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 2025); Conference Location: Philadelphia, PA, USA; Conference Date: April 28-30, 2025}
}

Research Collection: 20.500.11850/711664