Chinese Journal of Computers   Full Text
Title	Chinese AS-Level Topology Measurement and Analysis
Authors	ZHANG Yu FANG Bin-Xing ZHANG Hong-Li
Address	(Research Center of Computer Network and Information Security Technology, Harbin Institute of Technology, Harbin 150001)
Year	2008
Issue	No.4(611—619)
Abstract &   Background	Abstract To describe the prospect of Chinese autonomous system(AS) level topology, the authors adopt the meta-synthetic methodology to investigate the differences of topology data in themselves and their statistical characterization. Firstly, the topology snapshots and ten-year history are collected from various data sources with the BGP-, traceroute- and IRR-based methods. Secondly, topology snapshots are compared by groups with set operations, and a relatively complete and credible Chinese AS graph is obtained. Three growth mechanisms are analyzed from the view of the birth-death progress. The miss of death progress in related models is pointed out. Then, the topological characteristics and their significances of three typical snapshots are compared with complex network characterization methodologies. The fact that the average degree can determine most of discrepancies is discovered. Finally, four observations on the evolution of topological characteristics are presented, including the phenomenon of average degree growth which wasn’t replayed by related models. keywords topology measurement; topology modeling; topology evolution; complex network; autonomous system; meta-synthetic background Internet AS-level topology is a graph of thousands of networks each of which is constituted by many routers and maintained by a single political or economical entity. The structural and dynamical characteristics of Internet topology have received a great interest from the computer science, physics, and mathematics. Researchers generally believe that understanding Internet topology will be a key of discovering universal laws inside complex networks and developing scalable next generation Internet. In the computer networking, topology measurement and analysis are the basic research to enable prediction of how new technologies, policies, or economic conditions will impact the Internet’s connectivity structure. Unlike the most of fields in the computer science deal with the formalized problems and develop their corresponding algorithms, the research on network topology follows methodologies in physics, i.e. observation, hypothesis, and experiments. Three open problems need to be solved: (1)There is a lack of comprehensive and realistic topological data; (2)The framework of describing massive graphs hasn’t been constructed; (3)The first principles of the origin and evolution of inter- and intra-AS topologies seem to be outside topologies themselves. To describe the landscape of Chinese AS-level network, the authors adopt the meta-synthetic methodology to analyze the differences among a comprehensive set of Chinese AS-level topology snapshots and history. One of key ideas in the meta-synthetic methodology is to build the relationship between the previous isolated works. Although Chinese AS-level topology is only about 3% of the global topology, the investigation on this small part gave us some insights into the macroscopic picture, which may be concealed by the population statistics in the previous works. This work is supported by the National Natural Science Foundation of China (60203021) and the National Basic Research Program(973 Program) of China (2007CB311100).