J. Software Engi neeri n g & Applications, 2010, 3, 901-905
doi:10.4236/jsea.2010.310106 Published Online October 2010 (http://www.SciRP.org/journal/jsea)
901
AS-Level Internet Macroscopic Topology
Centralization Evolvement Analysis
Jie Song, Hai Zhao, Bo Yang, Huali Sun
The School of Information Science & Engineering, Northeastern University, Shenyang, China.
Received July 1st, 2010; revised August 1st, 2010; accepted August 5th, 2010.
ABSTRACT
The As-level topology is a hotspot of the recent reseaches. We can understand the centralization of the network clearly
by researching the evolvement trend of the Internet macroscopic topology. The massive data we use in this paper is
from CAIDA (The Cooperative Association for Internet Data Analysis) Skitter project. And the time sp an of the data is
from July, 2001 to January, 2008. This paper introduces the background of the AS-level topology at first, then carries
out the evolvement of degree, core and layer. It is believed that the influence of the top-degree nodes on the other nodes
decreases and the centralization of network is going to fall off with the decrease of the core. And the nucleus status of
network declines.
Keywords: AS-Level, Centralization, Top-Degree, Core, Layer
1. Introduction
The Internet has been a complex self-organizing ecosys-
tem which is composed of numerous computers and is
now quite different from its prototype, ARPANET. Al-
though the Internet was built up by human personally,
none of us can describe what it looks like and how it op-
erates. The research on the Internet topology is to study
the laws which are contained in the network which seems
chaotic. It is inherently necessary to know the Internet by
recognizing the inner mechanism of the network topol-
ogy, the basis for developing and utilizing Internet in a
higher level.
Since the Internet was born, the studies on it have been
endless. In the early years people were more concerned
about the researches on the Internet architecture, the
network protocols, the connections between the com-
puters, as well as the service on the Internet. The results
of the study on the complex science and complex net-
works made the researchers at home and abro ad come to
realize that the Internet has been one part of the complex
networks in recent decades. Consequently, people began
to research the Internet from the angle of the complexity
and complex networks [1]. Recent years, people have
made a remarkable progress in this area and have found a
great number of characteristic laws which are hidden in
the network. However problems still remain such as the
small space, the short span of the data analysis and the
simple method in measuring. So we have to do more
comprehensive and further studies on it [2].
The researches on the Internet topology mainly con-
centrates on AS-level (Autonomous System) and rout-
ing-level. AS-level topology is in a higher level com-
pared to the routin g-level topology in the network [3]. Its
characteristics and changes have a great influence on the
Internet. Meanwhile, since the scale of data of the
AS-level topology is small, we can implement the com-
putation and analysis more effectively with deep-seated,
high time complexity and explore the objective charac-
ters in more depth using the existed computer power [4].
More systematic analysis strategies and reliable analysis
measures based on the results concluded by analyzing the
AS-level topology can be summarized to study the laws
in the router-level topology and to provide available
means to statistical analysis for network with ultra large
scale. Based on the main research trend in the recent
years, we take the application value and the computa-
tional cost in the practical analysis into account. So we
will focus on the data of the AS-level Internet topology.
Considering that the Internet is dynamic and its topology
changes with time, we can further understand the cen-
tralization of the network by studying the trend of the
inner topology evolvement.

AS-Level Internet Macroscopic Topology Centralization Evolvement Analysis 902
2. Evolvement Analysis of Degree
Archipelago (Ark) is the newest active measurement in-
frastructure, the next generation in evolution of the Skit-
ter infrastructure which CAIDA has operated for nearly a
decade [5]. But in this paper we will still use the meas-
uring data of the CAIDA Skitter because the time of the
appearance of the Ark is short. The measurement of the
global Internet data provided by the CAIDA Skitter
meets the results of the statistical analysis data. And the
results concluded by statistically analyzing should be
much better to reflect the status of the Internet. So all th e
calculations involved in this paper use the data provided
by the CAIDA Skitter. The time span is from July, 2001
to January, 2008.
The number of nodes is a variable to measure the scale
of the Internet. The Figure 1 shows us the evolvement
trend of the number of nodes. X-axis is the time span of
the actually measuring data from July, 2001 to January,
2008. Y-axis is the number of nodes. We can conclude
that the number of nodes increased violently and then
declined gradually in th e first three years. The number in
the last year declined stably with time. But the whole
trend in this Fig increased in this period. What this Fig
tells us is that the Internet is instable in the first three
years but the performance of the Internet gradually turns
better and more stable than before. In short, the scale of
the Internet is larger than before.
The node degree is defined as the number of the links
indicating to this node. It is one of the most used meas-
urements in the topological analysis. It shows how hot
these nodes are. If the degree o f one node is large, it will
Figure 1. The number of nodes statistically changes with
time.
explain that this AS connects massive other AS and has a
heavy task in the Internet.
The average degree of network is a basic characteris-
tics of network topology. The larger it is, the more links
the network has. At the same time, the network is likely
to have a better robustness [6].
From the Figure 2(a) we can conclude the law that the
average degree of AS-level Internet varies from time to
time. X-axis is the time span of the actually measuring
data from July, 2001 to January, 2008. Y-axis is the av-
erage degree of network. The value changed between 5
and 6.8 with small amplitude but decreased in the whole
time with the increase of the scale of the Internet. That is
to say that the connectivity of the whole network de-
creases in this period.
Figure 2(b) points out the average degree of the 0.5%,
1% and 2% of the top-degree nodes in the AS network
evolves over time. X-axis is the time span of the actually
measuring data. Y-axis is the average degree of these
three sets. The value decreases slowly with time. The
degree of the top-degree nodes declines with the drop of
network average degree. The shapes of these curves in
the Figure 2(b) are close and are similar to that in the
Figure 2(a). It indicates that the decline of the degree of
the top-degree nodes leads to the drop of network aver-
age degree.
There are some exceptional AS in the data that we
have got from the CAIDA. The degree of these nodes
usually is small but may change greatly in some months.
However, these exceptional actions would not last for
along time. For example, there is an AS whose degree
usually changes between 30 and 60 but rises to 4648 and
4596 in April and May of 2004 su ddenly. Then it returns
to normal level after July of 2004. We delete these ex-
ceptional situations in this paper in order to make the
analysis reasonable.
From Figure 3 we can conclude that the maximum
node degree in AS-level Internet topology changes with
time. X-axis is to show a time span of th e actually meas-
uring data. Y-axis is to show the maximum degree. The
value in this Fig shocks heavily with the whole trend
declining. That is to say the impact of the “hot” nodes
which are the top-degree nodes gradually drops over
time.
3. Evolvement Analysis of Core and Layer
From a given graph [7], we recursively
delete all nodes whose degree are less than k and lines
incident with these nodes. These nodes and links we have
removed make up the set W which is called

,GVE

1k

layer.
And the remained sub-graph is called k-core [8]. The
value of k decides the position of node in the topology
graph. The highest one is called the core of this topology.

AS-Level Internet Macroscopic Topology Centralization Evolvement Analysis 903
(a) (b)
Figure 2. The average degree statistically changes with time. (a) The average degree of network statistically changes with time;
(b) The average degree of the top-degree nodes statistically changes with time.
Figure 3. The maximum degree of network statistically
changes with time. Figure 4. Core of the Internet statistically changes with time.
As one of important features of the Internet topology,
core is a more complex measurement than the node de-
gree to measure the connectivity of the nodes. The core
of the nodes sometimes reflects the position of the node
in the topology. Those with a high-core have more links
and are more important to the Internet. They are in the
inner layer of the Internet. We can see the hierarchical
structure of the Internet from the nut to the outer space
by analyzing the topology core
links of the nodes with high-core may lead to the remove
of these nodes. Doing this may lead th e same bad impact
on the neighboring nodes and the core of the whole to-
pology declines. X-axis is the time span of the actually
measuring data. Y-axis is the network core. The value
changes with small amplitude but declines in the last
several years. The layer of the Inter net is going to reduce.
The Figure 5 shows us that the number of nodes de-
clines fast in th e low-layer but hard ly changes in the h igh-
layer. X-axis is the layer of the Internet in July each year.
Y-axis is the node number of each layer. The Figure 5
We can see from the definition of the core that the core
of the graph is decided by the highest core. The lost of

AS-Level Internet Macroscopic Topology Centralization Evolvement Analysis 904
Figure 5. The number of nodes statistically changes with
layer.
shows the situation: a small amount of the nodes in the
high-layer but a greater number of nodes in the low-layer.
The nodes in the high-layer are the nucleus of the Inter-
net topology.
The Figure 6 shows that the number of links gradually
declines with the increase of the layer but increases sud-
denly in the high-layer. The decline tendency of the
number is slow in the middle-layer. X-axis is to show the
layer of network in July each year from 2001 to 2007.
Y-axis is to show the number of links. When the layer of
the Internet is high enough, the number of links would
not decline but with some amplitude. The top-degree
nodes are usually in a high-layer. So the number of links
may change obviously once the number of these nodes
Figure 6. The number of links in each layer.
(a)
(b)
(c)

AS-Level Internet Macroscopic Topology Centralization Evolvement Analysis 905
changes.
Figure 7 shows the set of degree in each core. X-axis
is the set of degree in each core. Y-axis is the core of
network in July. Core of the Internet decline with time
which corresponds with the conclusion we have known
in the Figure 4. The bottom-degree distributes in each
core but top-degree only appears in the high-core. The
high-core includes the nodes whose degree changes in a
large span. So the change of the maximum degree has
impact on the high-core in network to a certain extend.
The rarefaction in the high-cor e and the denseness in th e
low-core tells us that the centralization is going to fall
off.
4. Conclusions
The data we use in this paper is massive and with a large
time span from July, 2001 to January, 2008. They are
observed by the partner of Embedded Technology Labo-
ratory in Northeastern University, CAIDA. The laws we
get by analyzing th ese data are as follows:
(d)
The influence of the top-degree nodes on the other
nodes decreases. The core of the Internet decreases with
time. We can also say that the centralization of network
is going to fall off. The nucleus status of network de-
clines.
REFERENCES
[1] S. Zhou and R. J. Mondragon, “Structural Constraints in
Complex Networks,” New Jou rnal of P hysic s, Vol. 9, No.
172, 2007, pp. 1-11.
[2] D. Y. Fu, H. Zhao and X. Ge, “AS-Level Internet Topol-
ogy Degree and Connectivity Analysis,” Compute Sci-
ence, Vol. 36, No. 10, 2009, pp. 104-105.
(e)
[3] L. Subramanian, V. N. Padmanabhan and R. H. Katz,
“Geographic Properties of Internet Routing,” Proceedings
of the USENIX Annual Technical Conference, Monterey,
2002, pp. 243-259.
[4] J. Li, M. Sung, J. Xu, et al, “Large-Scale IP Trace Back
in High-Speed Internet: Practical Techniques and Theo-
retical Foundation,” Proceeding of the IEEE Symposium
on Security and Privacy, California, USA, 2004, pp. 115-
129.
[5] CAIDA Skitter, [EB/OL], http://www.caida.org/tools/
measurement/skitter/
[6] W. Willinger and J. Doyle, “Robustness and the Interact:
Design and Evolution,” [EB/OL]. 2002. http://netlab.altech.
edu/Internet/
[7] D. B. West, “Introduction to Graph Theory,” China Ma-
chine Press, Beijing, 2006, pp. 339-348.
[8] X. F. Wang, X. Li and G. R. Chen, “The Theory and Ap-
plication of Complex Network,” TsingHua University
Press, Beijing, 2006.
(f)
Figure 7. The relationship between the degree and the core
of the nodes. (a) 2001.7; (b) 2002.7; (c) 2003.7; (d) 2004.7; (e)
2005.7; (f) 2006.7.