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

D 2018

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

SCHMID, Stefan a Jiří SRBA

Základní údaje

Originální název

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

Autoři

SCHMID, Stefan a Jiří SRBA

Vydání

USA, IEEE International Conference on Computer Communications (INFOCOM'18), od s. 1799-1807, 9 s. 2018

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/18:00105976

Organizační jednotka

Fakulta informatiky

ISBN

978-1-5386-4128-6

ISSN

DOI

https://doi.org/10.1109/INFOCOM.2018.8486261

UT WoS

000509768900202

EID Scopus

2-s2.0-85047344286

Klíčová slova anglicky

network verification; MPLS networks; pushdown automata

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 6. 2022 12:39, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Citovat

SCHMID, Stefan a 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, s. 1799-1807. ISBN 978-1-5386-4128-6. Dostupné z: https://doi.org/10.1109/INFOCOM.2018.8486261.

@inproceedings{1492173,
   author = {Schmid, Stefan and Srba, Jiří},
   address = {USA},
   booktitle = {IEEE International Conference on Computer Communications (INFOCOM'18)},
   doi = {https://doi.org/10.1109/INFOCOM.2018.8486261},
   keywords = {network verification; MPLS networks; pushdown automata},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-5386-4128-6},
   pages = {1799-1807},
   publisher = {IEEE},
   title = {Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks},
   url = {https://ieeexplore.ieee.org/document/8486261},
   year = {2018}
}

TY  - CONF
ID  - 1492173
AU  - Schmid, Stefan - Srba, Jiří
PY  - 2018
TI  - Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks
PB  - IEEE
CY  - USA
SN  - 9781538641286
KW  - network verification
KW  - MPLS networks
KW  - pushdown automata
UR  - https://ieeexplore.ieee.org/document/8486261
N2  - 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.
ER  -

SCHMID, Stefan a Jiří SRBA. Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks. Online. In \textit{IEEE International Conference on Computer Communications (INFOCOM'18)}. USA: IEEE, 2018, s.~1799-1807. ISBN~978-1-5386-4128-6. Dostupné z: https://doi.org/10.1109/INFOCOM.2018.8486261.

Přehled o publikaci