Technologies, routing policies and relationships between autonomous systems in inter-domain routing

Abstract

A deep exploration of the issues related to routing decisions in inter-domain routing is the scope of this thesis, through the analysis of the interconnection structure and the network hierarchy, the examination of the inter-domain routing protocol used to exchange network reachability information with other systems, the examination of the routing decision process between the entities according to their attributes and policies, the study of the topology generators of the AS relationships, reviewing the most interesting proposals in this area, describing why these issues are difficult to solve, and proposing solutions allowing to better understand the routing process and optimally solve the trade-off of implementing a Peering Engagement between two Autonomous Systems, against the extra cost that this solution represent. More specifically this thesis introduces a new scheme for the routing decision in a BGP speaker through a formalization of the routing decision process, and proposes a formulation of a real and exhaustive mathematical model of a Peering Engagement between Autonomous Systems, to be solved as a problem of maximization with an ad-hoc built Decision Support System (XESS) able to find an optimal reduced set of solutions to the proposed problem. -------------------------------------------------------------------------- ABSTRACT [IT] Un’analisi approfondita delle tematiche inerenti le decisioni di routing nel routing interdominio è oggetto di questa tesi, attraverso l’esame della struttura di interconnessione e delle gerarchia del network, lo studio del protocollo utilizzato nel routing interdominio per scambiare le informazioni di reachability con gli altri sistemi, l’analisi del processo decisionale tra le entità coinvolte nello scambio di tali informazioni in accordo con le politiche e gli attributi, lo studio delle topologie sintetiche derivate dallo studio delle relazioni tra gli AS, attraverso i lavori di ricerca in quest’area, la descrizione dei problemi e delle difficoltà, e offrendo un contributo atto a fornire una maggiore comprensione del processo decisionale nel routing interdominio e una soluzione per l’implementazione di un processo di Peering tra Autonomous System. In particolare, questa tesi introduce un nuovo modello per il processo decisionale in uno speaker BGP attraverso la formalizzazione del routing decision process, e propone un modello matematico esaustivo delle meccaniche legate al processo di Peering Engagement tra Autonomous System, da analizzare come problema di massimizzazione e da risolvere con un Decision Support System (XESS) creato per trovare un sottoinsieme ottimo di soluzioni al problema matematico proposto.