Internet Topology Generation Based on Reverse-Engineered Design Principles: Performance Tradeoffs Between Heuristic and Optimization-Based Approaches; Master's thesis

摘要

The global Internet is a federation of computer networks that are owned and operated by Internet Service Providers (ISPs). Because ISPs do not share topology information for competitive and privacy reasons, researchers, operators, and policy makers who want to assess the performance and reliability of the system as a whole must infer structure from limited measurement data. We use reverse-engineering to infer underlying design principles of a national ISP and then develop models capable of generating ISP topologies ranging from regional to national scales. We contrast the behavior of optimal versus heuristic designs in terms of cost and performance. Unlike previous approaches that simply replicate observed network connectivity statistics, our approach yields networks that reflect the technological capabilities, economic constraints, operational requirements, and performance objectives faced by real ISPs. We complement our mathematics with computational tools that facilitate this network generation and analysis. To our knowledge, this thesis represents the first effort to incorporate these modeling principles in a process capable of generating realistic ISP networks at the national scale.