Marchetta, Pietro (2014) Issues, methodologies and solutions for Internet path tracing. [Tesi di dottorato]


Download (3MB) | Preview
[error in script] [error in script]
Item Type: Tesi di dottorato
Lingua: English
Title: Issues, methodologies and solutions for Internet path tracing
Date: 31 March 2014
Number of Pages: 180
Institution: Università degli Studi di Napoli Federico II
Department: Ingegneria Elettrica e delle Tecnologie dell'Informazione
Scuola di dottorato: Ingegneria dell'informazione
Dottorato: Ingegneria informatica ed automatica
Ciclo di dottorato: 26
Coordinatore del Corso di dottorato:
Pescapè, AntonioUNSPECIFIED
Date: 31 March 2014
Number of Pages: 180
Uncontrolled Keywords: Internet path tracing; Internet measurements; Traceroute; hidden routers; third-party addresses; RTT; active probing; alias resolution
Settori scientifico-disciplinari del MIUR: Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 - Sistemi di elaborazione delle informazioni
Date Deposited: 14 Apr 2014 05:54
Last Modified: 15 Jul 2015 01:01


We critically depend on the Internet for our professional, personal and political lives. Researchers have been developing monitoring and measurement techniques to gather an accurate and exhaustive knowledge about how this complex, critical and largely opaque ecosystem of independent networks actually operates. Among the aspects of interest, tracing Internet paths (i.e. routers and links traversed by the network traffic sent towards a given destination) has attracted large interest from the research community with several applications including the reverse engineering of the network infrastructure, the monitoring and prediction of Internet paths and their performance, the management and troubleshooting of the network, the organization of efficient overlay networks and the investigation of the network routing and its pathologies. However, the techniques developed for tracing Internet paths are affected by several severe limitations causing the information obtained about the paths under investigation to be potentially incomplete or inaccurate with a significant impact on the applications relying on them. For instance, state of the art path tracing techniques may provide inaccurate topological information causing a distortion of the inferred network topology. Furthermore, by reviewing the literature, we notice how researchers, network administrators and systems relying on path tracing techniques are often interested in exploring specific Internet paths about which they know only some characteristics such as the traversed Autonomous Systems (AS). However, the ability to explore particular Internet routes strongly depends on (i) the availability of multiple vantage points well-distributed in the Internet (i.e. the machines issuing path tracing measurement) and (ii) the ability of identifying which specific vantage point to use and destination to target in order to explore the path of interest. Regarding the first challenge, researchers might use the vantage points made available by several public experimental testbeds. However, the great heterogeneity of interfaces and internal mechanisms of these testbeds represented a strong disincentive: as a consequence, researchers tend to use always the same testbed and its relatively small amount of vantage points. Regarding the second point, to the best of our knowledge, there are no available methodologies to identify which particular path tracing measurements to perform in order to explore a particular path of interest. In this thesis, we developed methodologies, techniques and a system for advancing the state of the art in the field of Internet path tracing. After having detailed the Internet path tracing techniques currently available, we critically analize their limitations as well as the partial solutions documented in literature: while some limitations attracted great interest from the community (e.g. load balancing), several other limitations have been largely ignored or not exhaustively investigated or resolved. As a first contribution, we present a set of innovative active probing techniques augmenting state of the art path tracing techniques with the specific goal to address unresolved limitations in Internet path tracing. More precisely, we present measurement techniques to (i) detect and locate hidden routers (i.e. network device invisible to path tracing techniques); (ii) detect third-party addresses (i.e. an anomaly causing the inference of AS not actually traversed on the path towards the destination); (iii) dissect in chunks the overall delay experienced along the path; (iv) trace the path towards the destination with a totally alternative path tracing approach complementary to the one universally adopted. As a second contribution, we identify two additional limitations in Internet path tracing: state of the art path tracing techniques may induce one to overestimate the number of equal-cost paths towards the destination and to infer non-existing changes in the network routing. For this analysis, we rely on alias resolution techniques (including a technique we present in this thesis) whose goal is to identify the addresses belonging to the same network device. As a third contribution, we designed, implemented and evaluated PANDA, a first implementation of a general architecture providing a path tracing on-demand service that aggregates under a unique simple interface the vantage points made available by different experimental testbeds very rarely jointly used due to the great heterogeneity of the exposed interfaces. PANDA is designed to satisfy complex user queries requesting path tracing measurements for Internet path with a priori known characteristics. This goal is reached by relying on a BGP-based prediction engine.


Downloads per month over past year

Actions (login required)

View Item View Item