Research On Modeling Of The Internet As-level Topology Based On Complex Network Theory

Internet has been developed into a giant and complex system. Studying on its topological structure, investigating its evolving mechanisms, establishing its topological evolving model are crucial for providing research objects for network simulation and scientific experiment, and laying a solid theoretical foundation for high-performance network protocol designing, which has an important meaning for optimizing the performance and evaluating the safety and invulnerability of the network. As a typical instance of the newly flourishes complex networks, researching and modeling on the Internet topology can also promote the development of the study on complex network theory.At present, the people's understanding about inner structure and evolution rule of the bottom Internet topology supporting various network applications is far from mature. The Internet topology can be divided into autonomous system level topology and routing-level topology according to the different division size degree. Autonomous system level topology is the most macro network topology, its characteristics and the changes show tremendous influence on the Internet. Research on AS topology's structure is curial for the development of the next generation Internet. Due to the Internet domain routing protocols based on the strategy of BGP protocol, which cause the existing business relationships among autonomous systems. AS relationships not only influence the Internet domain of routing protocols, but also put forward the new modeling requirement on AS level Internet topology.This thesis aims at the needs of AS-level Internet topology modeling, the main work and contributions are outlined as follows:1. Research from the aspect of topology data measurement and characteristics analysis, analyzing existing problems in the topological measurement of AS level and its impacts on measurement data, give evolution analysis of basic characteristics after the massive real AS level topology data are obtained. Accurate Internet topology data acquisition is the cornerstone of the work for all analysis and modeling of topological structure characteristics. First, analyzing the emerging problems during the AS level topology measure and their impacts on the mearutement in detail, the correct understanding about the real AS level topology data has been set up. Second, the authoritative real topology data of the Routerview and CAIDA Skitter projects are obtained from Internet. Third, the recognition on the macro structure of AS level topology is given after the evolution analysis of basic characteristics. What have done provide theoretical base for the succeeding study on the AS-level Internet topology modeling.2. Research from the aspect of hierarchy of topology, finding that the inner characteristics of AS Internet topology based on division of coreness, propose a dynamic evolution network model framework named HMF based on the node's coreness. Based on the massive real AS level topology data of k-core decomposition, network core and peripheral following different evolution rule, and inherent characteristics of hierarchy are discovered, they are hierarchy based on coreness, hierarchical correlation, disassortative and centripetal structure. Then, after the in-depth hierarchy analyzing of the massive real AS-level topology data, a material way about network's hierarchical partition are introduced and a number of optimized parameters for modeling in quantitative are given, and then a hierarchical network model to fully portray the characteristics of hierarchical correlation, disassortative and centripetal structure is presented. Finally reference classic BA modeling methods, a Hierarchical Model Framework named HMF is proposed. This model is different from the former static layered model such as Transit-Stub etc. HMF is a dynamic evolutinal model and modeling in accordance with topology internal hierarchical performance based on node's coreness layered. The new perspective of partition is more reasonable, careful. The numerical simulations and analysis results showed that most of macroscopic statistics closed to real networks', including power-law degree distribution and network hierarchy etc, and satisfied the power law and small world characteristics at the same time. HMF model can also be used for a kind of basic AS level Internet topology dynamic evolution model framework and then continue to model.3. Research from the aspect of AS relationships of topology, reveal the inner relationships between AS relationships and hierarchy, proposing a novel model named ASRM about modeling AS relationships base on k-core decomposition. Based on the analysis of the massive real AS-level topology data, which contains AS relationships information, the multi characteristics which describing AS-level topology's AS relationships are extracted. They are proportion in the AS relationships, annotation-degree distributions, annotation-degree correlation. Then, after the in-depth AS relationships analyzing on hierarchy of the massive real AS-level topology data, a material way about network's AS relationships are introduced and a number of optimized parameters for modeling in quantitative are given, and then a AS relationships model based on hierarchical correlation is presented. Finally a novel algorithm for generating synthetic graphs annotated with AS relationships named ASRTM is proposed based on the model framework of HMF. This model can output directly a annotated graph with AS relationships, which is different from others AS-level topology models. ASRM is a dynamic evolutinal model and modeling in accordance with proportion and connection probability of various business relationships within and among layers. The numerical simulations and analysis results compared with the real AS-level topology data showed that most of AS relationships properties closed to real networks'and realistically expressed the Business Relationships rules between ASs. Meanwhile, ASRM as a conferring algorithm about AS relationships can give a annotated graph with AS relationships for given undirected topology graph, expanding the application of ASRM model.4. According to the demand for modeling on AS-level Internet topology, considering actual influence factors of the AS level Internet construction and evolution, proposing a novel AS-level Internet topology dynamic evolution model named ASTDEM, which fully reflecting the macro characteristics of real Internet topology and contains of AS relationships. What are faced actual influence factors? Such as the types of AS node, exponential growth and aging of AS-level Internet size, local world,local clustering and self organization. Based on the analysis of the internal rules and external exhibition of above mentioned factors, a node model which contains 6-elements is defined, a detailed method about exponential adding new nodes and dying out old nodes are introduced, a material way about the dynamic size and choosing of local-world are introduced, and various local connectivity preference are discovered. Combined with HMF and ASRM model, a novel AS-level Internet topology dynamic evolution model named ASTDEM is proposed. This model can output directly a graph annotated with AS relationships too, which is different from other AS-level topology models. ASTDEM is a dynamic evolutinal model and modeling accordance with self-organizational characteristics of the Internet and constructing according to the development of the network's internal triggers. ASTDEM model will be more realistic, reasonable and effective. Theoretical analytical derivation and numerical simulations demonstrate that the ASTDEM model not only satisfiy the characteristic of power-law, but also have distinct consistency with real networks in macroscopic statistics and other key parameters, meanwhile, it can simulate the AS relationships'properties and network hierarchy exactly.5. Exploration from the aspect of the internal relations of the Internet topological properties, combined with analysis of the hierarchy and business relationships of the real Topology data, the interpretation of inner factors of Internet topology structure is introduced, which is based on cores of the k-core decomposition and the self-organization characteristics. According to research on the HMF model, ASRM model, ASTDEM model, this thesis preliminary revealed the inherent relations among power law, hierarchy and AS relationships through self-organization and k-core decomposition. There is inner relation between hierarchy and AS relationships based on nodes coreness. Hierarchy is one of the explaination of the mechanism of power law. The self-organizational characteristics of AS-level Internet determine the macro performance of AS-level Internet topology.The conclusions of this thesis offer a material AS-level Internet topology model which contains AS relationships, which is great valuable to accurately grasp the macro features of AS-level Internet topology. And it can provide theoretical foundation and research model directly for the research on the Internet topology structure based on AS relationships and a basic issues solution to inter-domain domain routing system.