The evolution of Internet topology is not always smooth but sometimes with unusual sudden changes. Consequently, identifying patterns of unusual topology evolution is critical for Internet topology modeling and simula...The evolution of Internet topology is not always smooth but sometimes with unusual sudden changes. Consequently, identifying patterns of unusual topology evolution is critical for Internet topology modeling and simulation. We analyze IPv6 Internet topology evolution in IP-level graph to demonstrate how it changes in uncommon ways to restructure the Internet. After evaluating the changes of average degree, average path length, and some other metrics over time, we find that in the case of a large-scale growing the Internet becomes more robust; whereas in a top–bottom connection enhancement the Internet maintains its efficiency with links largely decreased.展开更多
This paper theoretically and empirically studies the degree and connectivity of the Internet's scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normali...This paper theoretically and empirically studies the degree and connectivity of the Internet's scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normalization constant of degree distribution p(k). It develops a new mathematic model for describing the power-law relationships of Internet topology. From this model we theoretically obtain formulas to calculate the average degree, the ratios of the kmin-degree (minimum degree) nodes and the kmax-degree (maximum degree) nodes, and the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. It finds that the average degree is larger for a smaller power-law exponent A and a larger minimum or maximum degree. The ratio of the kmin-degree nodes is larger for larger λ and smaller kmin or kmax. The ratio of the kmax-degree ones is larger for smaller λ and kmax or larger kmin. The richer nodes hold most of the total degrees of Internet AS-level topology. In addition, it is revealed that the increased rate of the average degree or the ratio of the kmin-degree nodes has power-law decay with the increase of kmin. The ratio of the kmax-degree nodes has a power-law decay with the increase of kmax, and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the 73/27 rule'). Finally, empirically calculations are made, based on the empirical data extracted from the Border Gateway Protocol, of the average degree, ratio and fraction using this method and other methods, and find that this method is rigorous and effective for Internet AS-level topology.展开更多
Our current understanding about the AS level topology of the Internet is based on measurements and inductive-type models which set up rules describing the behavior (node and edge dynamics) of the individual ASes and...Our current understanding about the AS level topology of the Internet is based on measurements and inductive-type models which set up rules describing the behavior (node and edge dynamics) of the individual ASes and generalize the consequences of these individual actions for the complete AS ecosystem using induction. In this paper we suggest a third, deductive approach in which we have premises for the whole AS system and the consequences of these premises are determined through deductive reasoning. We show that such a deductive approach can give complementary insights into the topological properties of the AS graph. While inductive models can mostly reflect high level statistics (e.g., degree distribution, clustering, diameter), deductive reasoning can identify omnipresent subgraphs and peering likelihood. We also propose a model, called YEAS, incorporating our deductive analytical findings that produces topologies contain both traditional and novel metrics for the AS level Internet.展开更多
Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology migh...Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems(ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales(i.e., nodes,edges and 3 network components: single-edge component M1, binary component M2 and triangle component M3). The results indicate that: a) 95% of the Internet edges are internal edges(as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series,which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes,edges and components, and therefore our study represents an innovative approach to the subject.展开更多
Alias resolution,mapping IP addresses to routers,is a critical step in obtaining a network topology.The latest work on alias resolution is based on special fields in the packet,such as IP ID,port number,etc.However,fo...Alias resolution,mapping IP addresses to routers,is a critical step in obtaining a network topology.The latest work on alias resolution is based on special fields in the packet,such as IP ID,port number,etc.However,for security reasons,most network devices block packets for setting options,and some related fields exist only in IPv4,so these methods cannot be used for alias resolution of IPv6.In order to solve the above problems,we propose an alias analysis method based on delay sequence analysis.In this article,we present a new model to describe the distribution of Internet delays and give a mathematical proof.After experimental measurements using the Macroscopic Internet Topology Data Kit(ITDK)and Ark IPv6 Topology Dataset,it was found that the statistical differences in most alias delay models were very small.The statistical differences in the non-alias delay models are spread over a wide range.Using the wavelet decomposition in delay sequence,it was found that the approximate components and the detail components of the delay sequence of aliases were the same after filtering out the noise,which provided a theoretical explanation for the experimental results.This technology is applicable to both IPv4 and IPv6.展开更多
A brief survey on the state-of-the-art research of determining geographic location of IP addresses is presented. The problem of determining the geographic location of routers in Internet Service Provider (ISP) topol...A brief survey on the state-of-the-art research of determining geographic location of IP addresses is presented. The problem of determining the geographic location of routers in Internet Service Provider (ISP) topology measurement is discussed when there is inadequate information such as domain names that could be used. Nine empirical inference rules are provided, and they are respectively (1) rule of mutual inference, (2) rule of locality, (3) rule of ping-pong assignment, (4) rule of bounding from both sides, (5) rule of preferential exit deny, (6) rule of uureachable/timeout, (7) rule of relay hop assignment, (8) rule of following majority, and (9) rule of validity checking based on interface-finding. In totally 2,563 discovered router interfaces of a national ISP topology, only 6.4% of them can be located by their corresponding domain names. In contrast, after exercising these nine empirical inference rules, 38% of them have been located. Two methods have mainly been employed to evaluate the effectiveness of these inference rules. One is to compare the measured topology graph with the graph published by the corresponding ISP. The other is to contact the administrator of the corresponding ISP for the verification of IP address locations of some key routers. The conformity between the locations inferred by the rules and those determined by domain names as well as those determined by whois information is also examined. Experimental results show that these empirical inference rules play an important role in determining the geographic location of routers in ISP topology measurement.展开更多
Precisely understanding the business relationships between autonomous systems(ASes)is essential for studying the Internet structure.To date,many inference algorithms,which mainly focus on peer-to-peer(P2P)and provider...Precisely understanding the business relationships between autonomous systems(ASes)is essential for studying the Internet structure.To date,many inference algorithms,which mainly focus on peer-to-peer(P2P)and provider-to-customer(P2C)binary classification,have been proposed to classify the AS relationships and have achieved excellent results.However,business-based sibling relationships and structure-based exchange relationships have become an increasingly nonnegligible part of the Internet market in recent years.Existing algorithms are often difficult to infer due to the high similarity of these relationships to P2P or P2C relationships.In this study,we focus on multiclassification of AS relationship for the first time.We first summarize the differences between AS relationships under the structural and attribute features,and the reasons why multiclass relationships are difficult to be inferred.We then introduce new features and propose a graph convolutional network(GCN)framework,AS-GCN,to solve this multiclassification problem under complex scenes.The proposed framework considers the global network structure and local link features concurrently.Experiments on real Internet topological data validate the effectiveness of our method,that is,AS-GCN.The proposed method achieves comparable results on the binary classification task and outperforms a series of baselines on the more difficult multiclassification task,with an overall metrics above 95%.展开更多
基金the National Natural Science Foundation of China(Grant No.60973022)
文摘The evolution of Internet topology is not always smooth but sometimes with unusual sudden changes. Consequently, identifying patterns of unusual topology evolution is critical for Internet topology modeling and simulation. We analyze IPv6 Internet topology evolution in IP-level graph to demonstrate how it changes in uncommon ways to restructure the Internet. After evaluating the changes of average degree, average path length, and some other metrics over time, we find that in the case of a large-scale growing the Internet becomes more robust; whereas in a top–bottom connection enhancement the Internet maintains its efficiency with links largely decreased.
基金supported by the National Natural Science Foundation of China (Grant Nos. 60973129,60903058 and 60903168)the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 200805331109)+1 种基金the China Postdoctoral Science Foundation (Grant No. 200902324)the Program for Excellent Talents in Hunan Normal University,China (Grant No. ET10902)
文摘This paper theoretically and empirically studies the degree and connectivity of the Internet's scale-free topology at an autonomous system (AS) level. The basic features of scale-free networks influence the normalization constant of degree distribution p(k). It develops a new mathematic model for describing the power-law relationships of Internet topology. From this model we theoretically obtain formulas to calculate the average degree, the ratios of the kmin-degree (minimum degree) nodes and the kmax-degree (maximum degree) nodes, and the fraction of the degrees (or links) in the hands of the richer (top best-connected) nodes. It finds that the average degree is larger for a smaller power-law exponent A and a larger minimum or maximum degree. The ratio of the kmin-degree nodes is larger for larger λ and smaller kmin or kmax. The ratio of the kmax-degree ones is larger for smaller λ and kmax or larger kmin. The richer nodes hold most of the total degrees of Internet AS-level topology. In addition, it is revealed that the increased rate of the average degree or the ratio of the kmin-degree nodes has power-law decay with the increase of kmin. The ratio of the kmax-degree nodes has a power-law decay with the increase of kmax, and the fraction of the degrees in the hands of the richer 27% nodes is about 73% (the 73/27 rule'). Finally, empirically calculations are made, based on the empirical data extracted from the Border Gateway Protocol, of the average degree, ratio and fraction using this method and other methods, and find that this method is rigorous and effective for Internet AS-level topology.
基金supported by Ericsson and partially supported by the Hungarian Scientific Research Fund(Grant No.OTKA 108947)
文摘Our current understanding about the AS level topology of the Internet is based on measurements and inductive-type models which set up rules describing the behavior (node and edge dynamics) of the individual ASes and generalize the consequences of these individual actions for the complete AS ecosystem using induction. In this paper we suggest a third, deductive approach in which we have premises for the whole AS system and the consequences of these premises are determined through deductive reasoning. We show that such a deductive approach can give complementary insights into the topological properties of the AS graph. While inductive models can mostly reflect high level statistics (e.g., degree distribution, clustering, diameter), deductive reasoning can identify omnipresent subgraphs and peering likelihood. We also propose a model, called YEAS, incorporating our deductive analytical findings that produces topologies contain both traditional and novel metrics for the AS level Internet.
基金Project supported by the National Natural Science Foundation of China(Grant No.61671142)
文摘Studying the topology of infrastructure communication networks(e.g., the Internet) has become a means to understand and develop complex systems. Therefore, investigating the evolution of Internet network topology might elucidate disciplines governing the dynamic process of complex systems. It may also contribute to a more intelligent communication network framework based on its autonomous behavior. In this paper, the Internet Autonomous Systems(ASes) topology from 1998 to 2013 was studied by deconstructing and analysing topological entities on three different scales(i.e., nodes,edges and 3 network components: single-edge component M1, binary component M2 and triangle component M3). The results indicate that: a) 95% of the Internet edges are internal edges(as opposed to external and boundary edges); b) the Internet network consists mainly of internal components, particularly M2 internal components; c) in most cases, a node initially connects with multiple nodes to form an M2 component to take part in the network; d) the Internet network evolves to lower entropy. Furthermore, we find that, as a complex system, the evolution of the Internet exhibits a behavioral series,which is similar to the biological phenomena concerned with the study on metabolism and replication. To the best of our knowledge, this is the first study of the evolution of the Internet network through analysis of dynamic features of its nodes,edges and components, and therefore our study represents an innovative approach to the subject.
基金This work is supported by The National Key Research and Development Program of China(2018YFB1800202,2018YFB0204301,2016YFB1000302,SQ2019ZD090149).
文摘Alias resolution,mapping IP addresses to routers,is a critical step in obtaining a network topology.The latest work on alias resolution is based on special fields in the packet,such as IP ID,port number,etc.However,for security reasons,most network devices block packets for setting options,and some related fields exist only in IPv4,so these methods cannot be used for alias resolution of IPv6.In order to solve the above problems,we propose an alias analysis method based on delay sequence analysis.In this article,we present a new model to describe the distribution of Internet delays and give a mathematical proof.After experimental measurements using the Macroscopic Internet Topology Data Kit(ITDK)and Ark IPv6 Topology Dataset,it was found that the statistical differences in most alias delay models were very small.The statistical differences in the non-alias delay models are spread over a wide range.Using the wavelet decomposition in delay sequence,it was found that the approximate components and the detail components of the delay sequence of aliases were the same after filtering out the noise,which provided a theoretical explanation for the experimental results.This technology is applicable to both IPv4 and IPv6.
文摘A brief survey on the state-of-the-art research of determining geographic location of IP addresses is presented. The problem of determining the geographic location of routers in Internet Service Provider (ISP) topology measurement is discussed when there is inadequate information such as domain names that could be used. Nine empirical inference rules are provided, and they are respectively (1) rule of mutual inference, (2) rule of locality, (3) rule of ping-pong assignment, (4) rule of bounding from both sides, (5) rule of preferential exit deny, (6) rule of uureachable/timeout, (7) rule of relay hop assignment, (8) rule of following majority, and (9) rule of validity checking based on interface-finding. In totally 2,563 discovered router interfaces of a national ISP topology, only 6.4% of them can be located by their corresponding domain names. In contrast, after exercising these nine empirical inference rules, 38% of them have been located. Two methods have mainly been employed to evaluate the effectiveness of these inference rules. One is to compare the measured topology graph with the graph published by the corresponding ISP. The other is to contact the administrator of the corresponding ISP for the verification of IP address locations of some key routers. The conformity between the locations inferred by the rules and those determined by domain names as well as those determined by whois information is also examined. Experimental results show that these empirical inference rules play an important role in determining the geographic location of routers in ISP topology measurement.
基金This workwas partially supported by the Key R&D Program of Zhejiang(Grant No.2022C01018)the National Natural Science Foundation of China(Grant Nos.U21B2001 and 61973273)+1 种基金the Zhejiang Provincial Natural Science Foundationof China(Grant Nos.LY21F030017 andLR19F030001)the Major Key Project of PCL(Grant Nos.PCL2022A03,PCL2021A02,and PCL2021A09).
文摘Precisely understanding the business relationships between autonomous systems(ASes)is essential for studying the Internet structure.To date,many inference algorithms,which mainly focus on peer-to-peer(P2P)and provider-to-customer(P2C)binary classification,have been proposed to classify the AS relationships and have achieved excellent results.However,business-based sibling relationships and structure-based exchange relationships have become an increasingly nonnegligible part of the Internet market in recent years.Existing algorithms are often difficult to infer due to the high similarity of these relationships to P2P or P2C relationships.In this study,we focus on multiclassification of AS relationship for the first time.We first summarize the differences between AS relationships under the structural and attribute features,and the reasons why multiclass relationships are difficult to be inferred.We then introduce new features and propose a graph convolutional network(GCN)framework,AS-GCN,to solve this multiclassification problem under complex scenes.The proposed framework considers the global network structure and local link features concurrently.Experiments on real Internet topological data validate the effectiveness of our method,that is,AS-GCN.The proposed method achieves comparable results on the binary classification task and outperforms a series of baselines on the more difficult multiclassification task,with an overall metrics above 95%.