Analysis of the use of complete orders to abstract the internet connectivity at the autonomous system level. Issue 1 (1st January 2018)

• Record Type: Journal Article
• Authors: Arjona‐Villicaña, Pedro David; Constantinou, Costas C; Stepanenko, Alexander S; Acosta‐Elías, Jesús
• Is Part Of: IET networks. Volume 7:Issue 1(2018)
• Page Start: 23
• Page End: 32
• Publication Date: 2018-01-01
• Subjects: Internet -- routing protocols -- tree searching -- telecommunication network topology; Internet connectivity -- autonomous system level -- complete orders -- routing information abstraction -- network topological information -- virtual arc -- chain routing algorithm -- NP‐complete problem; Computer network architectures -- Periodicals; Computer network protocols -- Periodicals; Information networks -- Periodicals; Telecommunication systems -- Periodicals; 004.605
• DOI: 10.1049/iet-net.2017.0020
• Languages: English
• ISSNs: 2047-4954

Abstract

Abstract : Complete orders, also called chains, are transitive acyclic digraphs which can be employed as a topological unit to model, abstract and exploit the Internet's path diversity. The main objective behind this work is to demonstrate why complete orders are well suited in abstracting routing information at the interdomain level. In order to abstract a network's topological information, it becomes necessary to introduce another mathematical structure called virtual arc, which allows to define complete orders where these cannot be formed directly. An algorithm, called chain routing, that employs virtual arcs to define chains in a network is described and tested. Further analysis of the chain routing algorithm leads to the conclusion that this is an NP‐complete problem; however, by limiting the size of the complete orders to be used, it is possible to provide an upper bound to the computational task needed to discover these structures in the Internet.