On Power-Law Relationships of the Internet Topology

The power-laws for the topology of the Internet over the duration of 1998 are determined from the topology of the Internet. The power law are expression of the form y ∝ x^a, where a is a constant and x and y are measures of the interest and ∝ stands for proportional to.

The sample space during that time is rather limited, though the size of the network increased substantially (45%), making any generalizations would be premature. However, the power-laws of Internet growth the same way the power-laws describing various natural networks such as the human respiratory system and automobile network.

The topology of the Internet can be divided into two different granularies: router level and inter-domain level. The metrics used to describe the graph are mainly the node outdegree and the distances between nodes. The power laws have been used to describe traffic in communication networks but not their topology.

The first power-law is called rank exponent. The outdegree of a node is proportional to the rank of the node to the power of the constant. The second power-law called outdegree exponent states that the frequency of an outdegree is proportional to the outdegree to the power of a constant. The third power-law, eigen exponent, states that the eigenvalues of a graph are proportional to the order to the power of a constant.

The power-law can be useful for predict future Internet based on the similarity with other network.

A First-Principles Approach to Understanding the Internet’s Router-level Topology

The degree distributions and other large scale statistics are popular metrics for evaluating how representative a given topology is and proposed topology generators are often evaluated on the basis of whether or not they can reproduce the same types of macroscopic statistics, especially power-law distributions.

However the above perspective is not complete and in need of correction actions. There exists many different graphs having the same distribution of node degree, some of which may be considered opposites from the viewpoint of network engineering. The first principles approach is to understand Internet topology at the router level.

Each of the topology generators uses one of the three probabilistic generation methods: 1) preferential attachment which says the growth and each newly added node connects to some existing nodes preferentially such that it is more likely to connect with a node that already has many connections. 2) General model of random graphs with a given expected degree sequence. The construction proceeds first by assigning each node its degree then probabilistically insert edges between nodes. 3) The power law random graph involves forming a set L of nodes containing as many distinct copies of a given vertex as the degree of that vertex, choosing a random matching of the elements of L, and applying a mapping of a given matching into an appropriate graph.

The commonly-used metrics are node degree distribution; expansion, resilience, distortion; hierarchy. Given the purpose for building a network is to carry effectively a projected overall traffic demand, others performance-related metrics are considered: throughput; router utilization; end user bandwidth distribution. The likelihood metric is used to differentiate between graphs having the same vertex set and the same degree distribution.