article

Understanding and modeling the internet topology: economics and evolution perspective

Authors:

Dmitri LoguinovAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 18, Issue 1

Pages 257 - 270

https://doi.org/10.1109/TNET.2009.2024145

Published: 01 February 2010 Publication History

Abstract

In this paper, we seek to understand the intrinsic reasons for the well-known phenomenon of heavy-tailed degree in the Internet AS graph and argue that in contrast to traditional models based on preferential attachment and centralized optimization, the Pareto degree of the Internet can be explained by the evolution of wealth associated with each ISP. The proposed topology model utilizes a simple multiplicative stochastic process that determines each ISP's wealth at different points in time and several "maintenance" rules that keep the degree of each node proportional to its wealth. Actual link formation is determined in a decentralized fashion based on random walks, where each ISP individually decides when and how to increase its degree. Simulations show that the proposed model, which we call Wealth-based Internet Topology (WIT), produces scale-free random graphs with tunable exponent α and high clustering coefficients (between 0.35 and 0.5) that stay invariant as the size of the graph increases. This evolution closely mimics that of the Internet observed since 1997.

References

[1]

W. Aiello and F. R. K. L. ChungL, "A random graph model for massive graphs," in Proc. ACM STOC, May 2000, pp. 171-180.

[2]

R. Albert and A. Barabási, "Topology of evolving networks: Local events and universality," Phys. Rev. Lett., vol. 85, no. 24, pp. 5234-5237, Dec. 2000.

[3]

A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, Oct. 1999.

[4]

D. Ben-Avraham, A. Rozenfeld, and R. C. Havlin, "Geographical embedding of scale-free networks," Physica A, vol. 330, pp. 107-116, 2003.

[5]

S. Bornholdt and H. Ebel, "World wide web scaling exponent from Simon's 1955 model," Phys. Rev. E, vol. 64, no. 3, p. 035104, Aug. 2001.

[6]

R. Brunet and I. Sokolov, "Evolving networks with disadvantaged long-range connections," Phys. Rev. E, vol. 66, p. 026118, 2002.

[7]

T. Bu and D. Towsley, "On distinguishing between Internet power law topology generators," in Proc. IEEE INFOCOM, Jun. 2002, pp. 638-647.

[8]

J. M. Carlson and J. Doyle, "Highly optimized tolerance: A Mechanism for power laws in designed systems," Phys. Rev. E, vol. 60, pp. 1412-1427, 1999.

[9]

H. Chang and S. J. Willinger, "Internet connectivity at the AS-level: An optimization-driven modeling approach," in Proc. ACM SIGCOMM Workshop, 2003, pp. 33-46.

[10]

H. Chang and S. J. Willinger, "To peer or not to peer: Modeling the evolution of the Internet's AS-level topology," in Proc. IEEE INFOCOM, Apr. 2006, pp. 1-12.

[11]

F. K. Chung, Spectral Graph Theory, ser. CBMS Regional Conference Series in Mathematics, No. 92. Providence, RI: Amer. Math. Soc., 1997.

[12]

F. R. K. Chung and L. Lu, "Connected components in random graphs with given expected degree sequences," Ann. Combinator., vol. 6, no. 2, pp. 125-145, Nov. 2002.

[13]

S. N. Dorogovtsev, "Networks with given correlations," 2003, condmat/ 0308336v1.

[14]

P. Erdös and A. Rényi, "On random graphs I," Publication Math. Debrecen, vol. 6, pp. 290-297, 1959.

[15]

A. Fabrikant, E. Koutsoupias, and C. Papadimitriou, "Heuristically optimized tradeoffs," in Proc. ICALP, Jul. 2002, pp. 110-122.

[16]

M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On Power-law Relationships of the Internet Topology," in Proc. ACM SIGCOMM, Aug. 1999, pp. 251-262.

[17]

L. Gao, "On inferring autonomous system relationships in the Internet," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 733-745, Dec. 2001.

[18]

K. I. Goh and B. K. Kim, "Fluctuation-driven dynamics of the Internet topology," Phys. Rev. Lett., vol. 88, p. 108701, 2002.

[19]

S. Gorman and R. Kulkarni, "Spatial Small Worlds: New Geographic Patterns for an Information Economy," Environ. Plann. B, Plann. Design, vol. 31, no. 2, pp. 273-296, 2003.

[20]

A. Gupta, "Models of wealth distributions--A perspective," in Econophys. Sociophys., B. Chakrabarti, A. Chakraborti, and A. Chatterjee, Eds. Hoboken, NJ: Wiley-VCH, 2007, pp. 161-190.

[21]

Y. He, G. Siganos, M. Faloutsos, and S. V. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and impact," in Proc. USENIX/SIGCOMM NSDI, Apr. 2007, pp. 3632-3637.

[22]

S. Jaiswal, A. Rosenberg, and D. Towsley, "Comparing the structure of power-law graphs and the Internet as graph," in Proc. IEEE ICNP, Oct. 2004, pp. 294-303.

[23]

C. Jin, Q. Chen, and S. Jamin, "INET: Internet topology," Univ. Michigan, 2002, Tech. Rep. CSE-TR-456-02.

[24]

S. Jin and A. Bestavros, "Small-world Internet topologies: Possible causes and implications on scalability of end-system multicast," presented at the IEEE/ACM Int. Symp. Model., Anal. Simul. (MASCOTS), Oct. 2003.

[25]

K. Klemm and V. M. Eguiluz, "Highly clustered scale-free networks," Phys. Rev. E, vol. 65, p. 036123, 2002.

[26]

P. L. Krapivsky and S. Redner, "Finiteness and fluctuations in growing networks," J. Phys. A, vol. 35, pp. 9517-9534, 2002.

[27]

P. L. Krapivsky, G. J. Rodgers, and S. Redner, "Degree distributions of growing random networks," Phys. Rev. Lett., vol. 86, no. 23, pp. 5401-5404, 2001.

[28]

A. Lakhina, J. W. Byers, and M. C. Matta, "On the geographic location of Internet resources," IEEE J. Sel. Areas Commun., vol. 21, no. 8, pp. 934-948, Aug. 2003.

[29]

M. Levy and S. Solomon, "Dynamical explanation for the emergence of power law in a stock market model," Int. J. Mod. Phys. C, vol. 7, pp. 65-72, 1996.

[30]

M. Levy and S. Solomon, "Power laws are logarithmic Boltzmann laws," Int. J. Mod. Phys. C, vol. 7, pp. 595-601, 1996.

[31]

X. Li and G. Chen, "A local-world evolving network model," Physica A, vol. 328, pp. 274-286, 2003.

[32]

H. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in Proc. OSDI, 2006, pp. 367-380.

[33]

D. Magoni and J. Pansiot, "Analysis of the autonomous system network topology," Comput. Commun. Rev., vol. 31, pp. 26-37, 2001.

[34]

A. Medina, I. Matta, and J. Byers, "On the origin of power-laws in Internet topologies," Comput. Commun. Rev., vol. 30, pp. 18-28, 2000.

[35]

M. Mihail and C. H. Papadimitriou, "On the eigenvalue power law," in Proc. Random, Sep. 2002, pp. 254-262.

[36]

M. Mihail and N. Visnoi, "On generating graphs with prescribed degree sequences for complex network modeling applications," presented at the ARACNE, Sep. 2002.

[37]

B. Mohar, "The Laplacian spectrum of graphs," Graph Theory, Combinator., Appl., vol. 2, pp. 871-898, 1991.

[38]

M. Molloy and B. Reed, "A critical point for random graphs with a given degree sequence," Random Struct. Algor., vol. 6, pp. 161-179, 1995.

[39]

M. E. J. Newman, "Assortative mixing in networks," Phys. Rev. Lett., vol. 89, no. 20, p. 208701, Oct. 2002.

[40]

R. V. Oliveira, D. Pei, W. Willinger, and B. Z. Zhang, "In Search of the elusive ground truth: the Internet's AS-level connectivity structure," in Proc. ACM SIGMETRICS, Jun. 2008, pp. 217-228.

[41]

V. Pareto, Cours D'Èconomique Politique. London, U.K.: Macmillan, 1897.

[42]

A. R. Puniyani, R. M. Lukose, and B. A. Huberman, "Intentional walks on scale free small worlds," 2001, cond-mat/0107212.

[43]

S. Redner, "How popular is your paper? An empirical study of the citation distribution," Eur. Phys. J. B, vol. 4, pp. 131-134, 1998.

[44]

"RIPE," {Online}. Available: http://www.ripe.net/

[45]

"Route Views project," {Online}. Available: http://www.routeviews. org/

[46]

P. O. Seglen, "The skewness of science," J. Amer. Soc. Inf. Sci., vol. 43, pp. 628-638, 1992.

[47]

Y. Shavitt and E. Shir, "DIMES: Let the Internet measure itself," Comput. Commun. Rev., vol. 35, no. 5, pp. 71-74, Oct. 2005.

[48]

H. A. Simon, "On a class of skew distribution functions," Biometrika, vol. 42, no. 3-4, pp. 425-440, Dec. 1955.

[49]

H. A. Simon, "Some further notes on a class of skew distribution functions," Inf. Contr., vol. 3, pp. 80-88, 1960.

[50]

"Skitter," {Online}. Available: http://www.caida.org/

[51]

D. Sornette, "Multiplicative processes and power laws," Phys. Rev. E, vol. 57, pp. 4811-4813, 1998.

[52]

H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Network topology generators: Degree-based vs. structural," in Proc. ACM SIGCOMM, Aug. 2002, pp. 147-159.

[53]

D. Vukadinovic, P. Huang, and T. Erlebach, "A spectral analysis of the Internet topology," ETH, 2001, Tech. Rep. TIK-NR.118.

[54]

C. Warren, L. Sander, and I. Sokolov, "Geography in a scale-free network model," Phys. Rev. E, vol. 66, p. 056105, 2002.

[55]

D. J. Watts, Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton, NJ: Princeton Univ. Press, 1999.

[56]

D. J. Watts and S. Strogatz, "Collective dynamics of small world networks," Nature, vol. 393, pp. 440-442, Jun. 1998.

[57]

B. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[58]

R. W. Wolff, Stochastic Modeling and the Theory of Queues. Englewood Cliffs, NJ: Prentice-Hall, 1989.

[59]

S. Yook, H. Jeong, and A. Barabási, "Modeling the Internet's large-scale topology," Natl. Acad. Sci., vol. 99, no. 21, pp. 13382-13386, Oct. 2002.

[60]

S. Zhou and R. J. Mondragon, "Accurately modeling the Internet topology," Phys. Rev. E, vol. 70, no. 6, p. 066108, Dec. 2004.

Cited By

Accongiagioco GGregori ELenzini L(2015)S-BITEComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.00777:C(73-89)Online publication date: 11-Feb-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.007
Fan ZChen GZhang Y(2012)Differentiating complex network modelsComputers & Mathematics with Applications10.1016/j.camwa.2011.12.06364:5(840-848)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.camwa.2011.12.063

Index Terms

Understanding and modeling the internet topology: economics and evolution perspective
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Networks
  1. Network properties
    1. Network structure

Recommendations

Inferring business relationships in the internet backbone

Several researchers during the last decade have encountered the problem of how to infer business relationships between autonomous systems ASes of the internet. Since the internet has a decentralised structure and public data sources containing inter-...
Observing the evolution of internet as topology
SIGCOMM '07: Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications

Characterizing the evolution of Internet topology is important to our understanding of the Internet architecture and its interplay with technical, economic and social forces. A major challenge in obtaining empirical data on topology evolution is to ...
Emulating internet topology snapshots in deterlab
CODASPY '13: Proceedings of the third ACM conference on Data and application security and privacy

Investigating the Internet's topology is one component towards developing mechanisms that can protect the communication infrastructure underlying our critical systems and applications. We study the feasibility of capturing and fitting Internet's ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 18, Issue 1

February 2010

332 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2010

Revised: 03 October 2007

Received: 30 March 2006

Published in TON Volume 18, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
272
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Accongiagioco GGregori ELenzini L(2015)S-BITEComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2014.11.00777:C(73-89)Online publication date: 11-Feb-2015
https://dl.acm.org/doi/10.1016/j.comnet.2014.11.007
Fan ZChen GZhang Y(2012)Differentiating complex network modelsComputers & Mathematics with Applications10.1016/j.camwa.2011.12.06364:5(840-848)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.camwa.2011.12.063

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents