On the Complexity of Network-Wide Configuration Synthesis
Abstract
Configuration Synthesis promises to increase automation in network hardware configuration but is generally assumed to constitute a computationally hard problem. We conduct a formal analysis of the computational complexity of network-wide Configuration Synthesis to establish this claim formally. To that end, we consider Configuration Synthesis as a decision problem, whether or not the selected routing protocol(s) can implement a given set of forwarding properties. We find the complexity of Configuration Synthesis heavily depends on the combination of the forwarding properties that need to be implemented in the network, as well as the employed routing protocol(s). Our analysis encompasses different forwarding properties that can be encoded as path constraints, and any combination of distributed destination-based hop-by-hop routing protocols. Many of these combinations yield NP-hard Configuration Synthesis problems; in particular, we show that the satisfiability of a set of arbitrary waypoints for any hop-by-hop routing protocol is NP-complete. Other combinations, however, show potential for efficient, scalable Configuration Synthesis.
Research Area: Verification and Synthesis
People
BibTex
@INPROCEEDINGS{schneider2022complexity,
isbn = {978-1-6654-8234-9},
doi = {10.1109/ICNP55882.2022.9940325},
year = {2022},
booktitle = {2022 IEEE 30th International Conference on Network Protocols (ICNP)},
type = {Conference Paper},
institution = {EC},
author = {Schneider, Tibor and Schmid, Roland and Vanbever, Laurent},
size = {11 p.},
abstract = {Configuration Synthesis promises to increase automation in network hardware configuration but is generally assumed to constitute a computationally hard problem. We conduct a formal analysis of the computational complexity of network-wide Configuration Synthesis to establish this claim formally. To that end, we consider Configuration Synthesis as a decision problem, whether or not the selected routing protocol(s) can implement a given set of forwarding properties. We find the complexity of Configuration Synthesis heavily depends on the combination of the forwarding properties that need to be implemented in the network, as well as the employed routing protocol(s). Our analysis encompasses different forwarding properties that can be encoded as path constraints, and any combination of distributed destination-based hop-by-hop routing protocols. Many of these combinations yield NP-hard Configuration Synthesis problems; in particular, we show that the satisfiability of a set of arbitrary waypoints for any hop-by-hop routing protocol is NP-complete. Other combinations, however, show potential for efficient, scalable Configuration Synthesis.},
keywords = {Automation; Computational modeling; Routing; Routing protocols; Hardware; Space exploration; Internet},
language = {en},
address = {Piscataway, NJ},
publisher = {IEEE},
title = {On the Complexity of Network-Wide Configuration Synthesis},
PAGES = {9940325},
Note = {30th IEEE International Conference on Network Protocols (ICNP 2022); Conference Location: Lexington, KY, USA; Conference Date: October 30 - November 2, 2022}
}Research Collection: 20.500.11850/594510
Slide Sources: https://gitlab.ethz.ch/projects/35904