Path computation in multi-layer multi-domain networks: A language theoretic approach

Autor: Helia Pouyllau, Mohamed Lamine Lamali, Dominique Barth
Přispěvatelé: Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), European Project: 248567,EC:FP7:ICT,FP7-ICT-2009-4,ETICS(2010)
Jazyk: angličtina
Rok vydání: 2013
Předmět:
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL)
Computer Networks and Communications
Computer science
Computation
Distributed computing
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Computer Science - Networking and Internet Architecture
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
Pseudo-Wire
Networking and Internet Architecture (cs.NI)
business.industry
Push-Down Automata
Pushdown automaton
Pseudo-wire
020206 networking & telecommunications
Graph
Encapsulation (networking)
Automaton
010201 computation theory & mathematics
Shortest path problem
Multi-layer networks
Automata theory
business
Heterogeneous network
Computer network
Zdroj: Computer Communications
Computer Communications, Elsevier, 2013, ⟨10.1016/j.comcom.2012.11.009⟩
Computer Communications, 2013, ⟨10.1016/j.comcom.2012.11.009⟩
ISSN: 0140-3664
1873-703X
DOI: 10.1016/j.comcom.2012.11.009⟩
Popis: Multi-layer networks are networks in which several protocols may coexist at different layers. The Pseudo-Wire architecture provides encapsulation and de-capsulation functions of protocols over Packet-Switched Networks. In a multi-domain context, computing a path to support end-to-end services requires the consideration of encapsulation and decapsulation capabilities. It appears that graph models are not expressive enough to tackle this problem. In this paper, we propose a new model of heterogeneous networks using Automata Theory. A network is modeled as a Push-Down Automaton (PDA) which is able to capture the encapsulation and decapsulation capabilities, the PDA stack corresponding to the stack of encapsulated protocols. We provide polynomial algorithms that compute the shortest path either in hops or in the number of encapsulations and decapsulations along the inter-domain path, the latter reducing manual configurations and possible loops in the path.
Journal on Computer Communications, 2013
Databáze: OpenAIRE
Externí odkaz: