Analysis of the use of complete orders to abstract the internet connectivity at the autonomous system level
Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
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%27s 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%27s 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 NPcomplete 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. © The Institution of Engineering and Technology 2017.

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 NPcomplete 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. © The Institution of Engineering and Technology 2017.
publication date
published in
Research
keywords

Chains; Computational complexity; Internet; Acyclic digraph; Autonomous systems; Computational task; Internet connectivity; Mathematical structure; Path diversity; Routing information; Topological information; Topology
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue