A master thesis from Aalborg University
Quantitative Analysis of MPLS Networks in AalWiNes: Shortest Trace Reachability Analysis of Weighted Pushdown Systems
[Quantitative Analysis of MPLS Networks in AalWiNes]
Author(s)
Term
4. term
Education
Publication year
2020
Submitted on
2020-06-08
Pages
58 pages
Abstract
Safe, reliable and efficient computer networks are essential for modern digital communication. Configuring these networks is a challenging task, which today is mostly performed manually. To aid in this task, the tool AalWiNes provides polynomial-time analysis of the behaviour of a type of network, called MPLS network, even under the scenario of multiple link failures. AalWiNes answers queries on MPLS networks by translating them into reachability queries on pushdown systems. We extend AalWiNes with quantitative properties of network traces and implement an efficient algorithm to find traces minimizing these properties. We also define an algorithm for automatically generating MPLS networks, and we implement algorithms for pushdown system reachability in the library PDAAAL used by AalWiNes. Our experimental evaluation demonstrates that we outperform the state-of-the-art tool previously used by AalWiNes for pushdown reachability checking, and that our shortest trace algorithm for weighted pushdown systems only incurs a small overhead compared to unweighted reachability checking.
Keywords
MPLS ; Pushdown automata ; Network ; Verification ; AalWiNes
Documents
Colophon: This page is part of the AAU Student Projects portal, which is run by Aalborg University. Here, you can find and download publicly available bachelor's theses and master's projects from across the university dating from 2008 onwards. Student projects from before 2008 are available in printed form at Aalborg University Library.
If you have any questions about AAU Student Projects or the research registration, dissemination and analysis at Aalborg University, please feel free to contact the VBN team. You can also find more information in the AAU Student Projects FAQs.