Open AccessAnalysis of the use of complete orders to abstract the internet connectivity at the autonomous system level
Author(s) -
ArjonaVillicaña Pedro David,
Constantinou Costas C,
Stepanenko Alexander S,
AcostaElías Jesús
Publication year - 2018
Publication title -
iet networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.466
H-Index - 21
eISSN - 2047-4962
pISSN - 2047-4954
DOI - 10.1049/iet-net.2017.0020
Subject(s) - computer science , routing (electronic design automation) , transitive relation , exploit , the internet , theoretical computer science , path (computing) , task (project management) , upper and lower bounds , routing algorithm , topology (electrical circuits) , limiting , chain (unit) , distributed computing , routing protocol , computer network , combinatorics , mathematics , world wide web , mechanical engineering , mathematical analysis , physics , computer security , management , astronomy , engineering , economics
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.