Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks

SCHMID, Stefan and Jiří SRBA. Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks. Online. In IEEE International Conference on Computer Communications (INFOCOM'18). USA: IEEE, 2018, p. 1799-1807. ISBN 978-1-5386-4128-6. Available from: https://dx.doi.org/10.1109/INFOCOM.2018.8486261.

Basic information

• Original name: Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks
• Authors: SCHMID, Stefan (756 Switzerland) and Jiří SRBA (203 Czech Republic, guarantor, belonging to the institution).
• Edition: USA, IEEE International Conference on Computer Communications (INFOCOM'18), p. 1799-1807, 9 pp. 2018.
• Publisher: IEEE

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: electronic version available online
• WWW: URL
• RIV identification code: RIV/00216224:14330/18:00105976
• Organization unit: Faculty of Informatics
• ISBN: 978-1-5386-4128-6
• ISSN: 0743-166X
• Doi: http://dx.doi.org/10.1109/INFOCOM.2018.8486261
• UT WoS: 000509768900202
• Keywords in English: network verification; MPLS networks; pushdown automata
• Tags: core_A, firank_1
• Tags: International impact, Reviewed

Abstract

While automated network verification is emerging as a critical enabler to manage large complex networks, current approaches come with a high computational complexity. This paper initiates the study of communication networks whose configurations can be verified fast, namely in polynomial time. In particular, we show that in communication networks based on prefix rewriting, which include MPLS networks, important network properties such as reachability, loop-freedom, and transparency, can be verified efficiently, even in the presence of failures. This enables a fast what-if analysis, addressing a major concern of network administrators: while configuring and testing network policies for a fully functional network is challenging, ensuring policy compliance in the face of (possibly multiple) failures, is almost impossible for human administrators. At the heart of our approach lies an interesting connection to the theory of prefix rewriting systems, a subfield of language and automata theory.