Research On Large Scale Network Topology Measurement And Analysis

The Internet as a'network of networks'consists of thousands of interconnectednetworks named as Autonomous Systems (AS), each of which also consists of agroup of interconnected routers. The structures at those two layers are named as AS-level topology and IP-level topology respectively. The large scale network topologymeasurement and analysis have received a great interest from the computer science,physics and mathematics. Researchers generally believe that understanding the na-ture of Internet topology is not only the base of developing an effective, robust andscalable next generation Internet, but also an important way to discover universal lawsinside complex networks. However, there exit three open problems to be solved:(1)There is a lack of comprehensive and realistic topological data; (2) The frameworkof describing massive graphs hasn't been constructed; (3) The origin and evolutionmechanisms of network topologies aren't well understood.This dissertation aims to describe the structural and dynamical properties ac-curately. First, we investigate the completeness of the target sampling and measurethe IP-level topology. Second, we compare the characteristics of IP-level topologieswith different completeness. Then, we measure the AS-level topology and analyzethe diversity of AS-level topology characteristics. Finally, we observe the history ofAS-level topology evolution and validate the related models.Considering the insufficiency of target sampling in related IP-level measurementpractice and the distortion of measurement models, we carry on a brute-force mea-surement experiment and discover that a great deal of information is missed by theusual random sampling with a low density. By analyzing the routing behavior, wefind that the subnet structure diversity is the primary factor for the incompleteness,while the path diversity is the minor one. Through the routing behavior analysis, wealso prove that an optimized sampling can be competent for a long-term measurementtask. We develop'fastrace', an IP-level topology measurement tool, in which thenew techniques are used to reduce the probing load into a half. At the end of 2004,we measured the Chinese IP-level topology and discovered a topology consisting ofabout 80,000 nodes, which is 4 times larger than that discovered by CAIDA's skitter. We also investigate the correlation between the regional network size and its economicsituation with those measurement data.To provide insight into the differences among the characteristics of the IP-leveltopologies with various completeness, we first introduce a list of the topology char-acterization metrics and analyze the correlation between those metrics. With a visu-alization technique, we observe the intuitive differences among the topologies. Then,we present a new graph-theoretic concept, Subgraph Coverage Pattern (SCP), whichquantifies how a subgraph covers nodes/edges with different importance in the wholegraph. By using the SCP, we find that the Chinese network locates at the margin ofglobal Internet, namely the centripetal SCP, and that the SCPs of the topologies dis-covered by fastrace and skitter in the topology merged by both them are centrifugaland centripetal respectively. Finally, applying the SCP into the taxonomy of charac-teristic differences, we find that the most of power-law exponents are robust, while theother metrics are sensitive to the graph sizes and the SCP.In order to understand the diversity of AS-level topology data, we adopted themeta-synthetic methodology to collect the topology data widely and to analyze the dif-ferences among the collected topologies. Firstly, the topology snapshots are collectedfrom various data sources with the BGP (Border Gateway Protocol) , traceroute andIRR (Internet Routing Registry)-based methods. During data collecting, we presentan update-time based IRR information filtering method and a hierarchy based methodfor the peering relationship inference. Then, we compare the topology snapshots bygroups with the set operations, and find that the BGP update based data have bettercompleteness and consistency, while the consistency of the traceroute based data ispoor. We obtain a relatively complete and credible Chinese AS graph, which has 65%more links than the usual graph from the RouteViews route tables. By comparingsome typical AS graphs, we find that the average degree is the principal characteristicto determine most of the quantitative discrepancies. We also find that the character-istics themselves of the tree graphs are similar qualitatively, while the significance ofcharacteristics are dissimilarity. The connectivity may be underestimated by the BGP-based measurement and overestimated by the traceroute-based measurement. Thesediscoveries are confirmed by the comparison of global AS-level topologies and pro-vide a new way to resolve a recent argument on the Rich-club phenomenon.To understand AS-level topology evolution trend and mechanisms, we observe and measure the history of AS-level topology comprehensively. First, we present themethods to measure the growth manners and the preferential attachment functions.Then we observe the history of Chinese AS-level topology and find the phenomenonsof the non-interactive death, average degree growth and characteristic significancecumulation. Through observing the history of global AS-level topology, we find therestrained growth of maximal degree and present a hypothesis that the scale-free prop-erty is temporary. We also find the weakening disassortative correlation and presenta hypothesis that the correlation is changing to neutral. We find the maximal core-ness can describe the core growth phenomenon instead of the Rich-club connectivity.Finally, the distortions of related evolution models are reported at three aspects ofdescription, forecast and explanation. The suggestion for further improvement is pre-sented.