• Autonomous System
• BGP
• Crowdsourcing
• Internet Topology
• Networking
• Traceroute

Durante gli ultimi dieci anni molti studi hanno sfruttato i dati BGP forniti dai Route Collector (RC) project per dedurre la topologia di Internet a livello di Autonomous System e per condurre diverse analisi; dalla scoperta delle proprietà del grafo fino a valutare l'impatto dell'efficacia di strategie per il contenimento della diffusione di virus. Nonostante ciò, la topologia che può essere estratta da questi dati è altamente incompleta e non è possibile inferire tutte le connessioni realmente esistenti tra gli AS. Altri studi hanno tentato di estrarre la topologia di Internet usando le informazioni contenute nei dati dei traceroute. Questa tesi analizza le infrastrutture di misura basate sul traceroute maggiormente conosciute e quantifica il loro potenziale contributo nella scoperta della topologia a livello AS. Questa analisi, usando la metrica \emph{p2c-distance}, mostra che le infrastrutture di misure basate su traceroute sono efficaci nel migliorare l'attuale topologia a livello AS ottenuta tramite i dati BGP; tuttavia i traceroute forniscono anche dati ridondanti che vanno a sovrapporsi alle informazioni già conosciute tramite il BGP. Questo è principalmente dovuto al posizionamento degli agenti di misura -- ospitati da AS nei livelli alti della gerarchia di Internet o che sono anche feeder dei BGP RC -- e perchè gli AS partecipanti alle maggiori infrastrutture di misurasono tipicamente instituzioni accademiche e di ricerca che condividono il medesimo insieme di Internet provider.
Al fine di essere più pervasivi nella periferia di Internet e scoprire le connessioni fra AS di piccola e media dimensione che non possono essere rilevate attualmente usando i dati BGP, in questa tesi descriviamo un nuovo sistema di misura chiamato Portolan. Portolan è il primo sistema di misura basato sul crowdsourcing che usa dispositivi mobili come agenti di misura. Sfruttando la pervasività e l'alta mobilità degli smartphone Portolan può aggiungere nuove AS sorgenti dai quali lanciare traceroute ed avere una visuale dal bottom-up di Internet. Tuttavia, differentemente dalle altre infrastrutture di misura basate su traceroute, i monitor di Portolannon possono eseguire moltissime misure e l'impatto sui dispositivi degli utenti deve essere minimo. Perciò, Portolan dovrebbe eseguire un numero limitato di traceroute ben mirati senza perdere di efficacia nella scoperta di nuove connessioni tra AS. Quindi abbiamo ideato una metodologia di misura che, con piccole attività di misura idonee a dispositivi con risorse limitate -- es. batteria, banda ecc. -- come gli smartphone, è in grado di sondare specialmente i livelli più bassi della gerarchia di Internet e trovare connessioni tra AS che non sono presenti nelle attuali topologie ottenute tramite i dati BGP. Questa tesi mostra che applicando la nostra metodologia di misura, Portolan è in grado di migliorare considerevolmente la topologia a livello AS estratta tramite BGP eseguendo un numero di traceroute che è fino a due ordini di grandezza più basso rispetto al numero di traceroute eseguito da altre infrastrutture di misura.


In the last decade many studies have leveraged the BGP data provided by route collector (RC) projects to deduct the Internet Autonomous System level topology and to perform several analyses, from discovering its graph properties to assessing its impact on the effectiveness of worm-containment strategies. Nevertheless, the topology that can be extracted from this data is proved to be highly incomplete and it is not possible to infer all the AS connections which actually exist among ASes from this data.
Other studies have tried to infer the Internet AS-level topology using the information extracted from traceroute data.
This thesis analyses the best known measurement infrastructures based on traceroute and quantifies their potential contribution in AS-level topology discovery.
Using the \emph{p2c-distance} metric this analysis shows that the infrastructures currently deployed are very suitable in improving the current AS-level topology gathered via BGP data but traceroute data also provide redundant data that are overlapped with the connectivity inferred from BGP. This is mainly due to the placement of the measurement agents -- hosted by ASes in the high level of Internet hierarchy or that are feeders of BGP RCs -- and because the ASes participating to the major measurement infrastructures are typically academic or research institutions that share the same set of providers. In order to be more pervasive in periphery of the Internet and discover the connections among medium/small ASes that cannot be detected using the current BGP RCs, in this thesis a new measurement system named Portolan is described. Portolan is the first network measurement system based on crawdsourcing that uses mobile devices as measurement agents.
Taking advantage of the pervasiveness and high mobility of smartphones Portolan can add new source ASes from which perform traceroutes and have a bottom-up view of the Internet. However, differently from the other traceroute-based measurement infrastructures, the Portolan monitors cannot execute heavy measurement tasks and the impact on the users experience must be very slightly. Therefore, Portolan should carry out a limited number of well-target traceroutes without losing efficacy in discovering new AS links. We conceived a measurement methodology that with small traceroute tasks that are suitable for devices with limited resource -- i.e battery, bandwidth etc. -- like smartphones is able to probe especially the lowest level of the Internet hierarchy and find AS links that are not present in the current topologies gathered via BGP data. This thesis shows that applying our methodology Portolan is able to considerably improve the AS-level topology inferred via BGP data performing a number of traceroutes that is up to two order of magnitude lower than the number of traceroutes performed by other measurement infrastructures.