Abstract :
[en] (abstract) Since the 1980’s, the Internet has steadily grown in size to deliver various services to an increasingly large public, which amounts to billions of users as of the beginning of the 2020’s. As a consequence, its infrastructure has considerably evolved too, which prompted the research community to investigate the topology of the Internet at multiple levels. The highest level is the AS-level (Autonomous System), an Autonomous System being a vast computer network operated by a single company, such as an ISP (Internet Service Provider). Not only the way Autonomous Systems communicate with each other has been investigated, but also their internal networks has drawn the attention of the research community, as many works focused on the mapping and the modeling of the router-level, i.e., how routers are interconnected either within a single AS or at the borders of adjacent ASes.
The Internet router-level has been investigated not only to discover its structure, but also to understand its dynamics. Starting from the 2000’s, the research community focused on how the routers balance the traffic between several links to handle the increasingly large amount of network traffic, a process which is commonly denoted as load balancing (a form of traffic engineering). Additionnal works on the router-level aimed at characterizing meshes of routers, i.e., routers that are directly connected at the data link layer (or Layer-2) to manage a large number of links as if they were a single router. In the meantime, the research community also explored other levels of the Internet to complement router-level maps, such as a subnet-level, a subnet (short for subnetwork) being a group of network interfaces that can contact each other directly at the data link layer.
This thesis aims at designing new topology discovery techniques to efficiently map the intra-domain topologies of large networks by exploring their different levels and the relationships that exist between these levels, all while dealing with the effects of load balancing. Three different levels are investigated: the router-level, the subnet-level, and the hop-level. The hop-level characterizes how routers or meshes exchange packets at the network layer (or Layer-3), and can therefore be used to study the internal forwarding of a network without extensively discovering its router-level.
Not only this thesis provides new topology discovery schemes to map each level, but it also combines them to increase their accuracy. In particular, it introduces a new subnet inference methodology that takes advantage of alias resolution (i.e., the process of determining whether or not a group or pair of network interfaces belong to the same device) to solve ambiguous scenarios, as well as a topology mapping scheme that relies on both subnet-level data and alias resolution to build comprehensive hop-level maps of intra-domain topologies. Moreover, these maps can be interpreted with bipartite formalisms to more easily study their topological features. All topology discovery methods developed for this thesis are comprehensively elaborated and assessed in this document. The tools that implement these methods ( WISE and SAGE ), their source code, and the data they could collect on various Autonomous Systems are publicly available.
