Understanding the topological characteristics of the Internet has been an important research issue. This understanding is not simply an intellectual curiosity but also a necessity to better design, implement, and operate the underlying network technologies, protocols, and services. It is also a requirement for protection of critical infrastructures that depend on the Internet. In general, Internet topology measurement studies involve three phases: topology collection, topology construction, and topology analysis. The first step is to collect topology information using various measurement approaches. In topology construction step, raw data obtained in the topology collection phase is converted into a corresponding topology map. Finally, the constructed network topologies are analyzed. This dissertation presents my work on topology construction from collected measurement data in the context of router-level Internet topology discovery. In general, there are several challenges in accurately sampling the Internet topology, and it includes resolving anonymous routers, IP aliases and underlying subnets. These tasks especially become challenging when large scale topologies of millions of nodes are studied. In this dissertation, I analyze each of these tasks and propose efficient algorithms to resolve them. Finally, I point out the need for characteristic oriented sampling for the measurement study at hand. I point out that one should be careful in collecting raw topology data and in constructing the corresponding network depending on the goals of the study and challenges in the sampling approach. These challenges are especially important where there is lack of methodologies to verify the correctness of topology collection and topology construction mechanisms.
展开▼
