Detailed Information on Publication Record
2018
Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks
SCHMID, Stefan and Jiří SRBABasic 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
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
Publication form
electronic version available online
References:
RIV identification code
RIV/00216224:14330/18:00105976
Organization unit
Faculty of Informatics
ISBN
978-1-5386-4128-6
ISSN
UT WoS
000509768900202
Keywords in English
network verification; MPLS networks; pushdown automata
Tags
International impact, Reviewed
Změněno: 1/6/2022 12:39, RNDr. Pavel Šmerk, Ph.D.
Abstract
V originále
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.