INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
Prev
Next
|
|
|
Deductive way of reasoning about the internet AS level topology |
Dávid Szabóa, Attila K?rösia c, József Bíróa b, András Gulyása c |
a High Speed Networks Laboratory, Budapest University of Technology and Economics, Hungary;
b MTA-BME Future Internet Research Group, Budapest University of Technology and Economics, Hungary;
c MTA-BME Information Systems Research Group, Budapest University of Technology and Economics, Hungary |
|
|
Abstract 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.
|
Received: 08 April 2015
Revised: 09 July 2015
Accepted manuscript online:
|
PACS:
|
89.75.Fb
|
(Structures and organization in complex systems)
|
|
89.20.Hh
|
(World Wide Web, Internet)
|
|
Fund: Project supported by Ericsson and partially supported by the Hungarian Scientific Research Fund (Grant No. OTKA 108947). |
Corresponding Authors:
Dávid Szabó
E-mail: szabod@tmit.bme.hu
|
Cite this article:
Dávid Szabó, Attila Kőrösi, József Bíró, András Gulyás Deductive way of reasoning about the internet AS level topology 2015 Chin. Phys. B 24 118901
|
[1] |
Pathan M and Buyya R 2008 Content Delivery Networks (Berlin: Springer) pp. 33-77
|
[2] |
Greenberg A, Hamilton J, Maltz A D and Patel P 2008 ACM SIGCOMM CCR 39 68
|
[3] |
Castro M, Druschel P, Hu Y C and Rowstron A 2003 Future Directions in Distributed Computing (Berlin:Springer) pp. 103-107
|
[4] |
Lua E K, Crowcroft J, Pias M, Sharma R and Lim S 2005 IEEE Commun. Surveys Tutorials 7 72
|
[5] |
Awduche D, Chiu A, Elwalid A, Widjaja I and Xiao X 2002 RFC (3272) [2002-05]
|
[6] |
Clark D, Lehr W and Bauer S 2011 TPRC, August 9, 2011, Arlington, VA
|
[7] |
Maslov S, Sneppen K and Zaliznyak A 2004 Physica A 333 529
|
[8] |
Rosato V, Issacharoff L, Meloni S, Caligiore D and Tiriticco F 2008 Physica A 387 1689
|
[9] |
Castellano C and Pastor-Satorras R 2012 Sci. Rep. 2 371
|
[10] |
Boguná M, Papadopoulos F and Krioukov D 2010 Nat. Commun. 1 62
|
[11] |
Boguna M, Krioukov D and Claffy K C 2009 Nat. Phys. 5 74
|
[12] |
Xiao B, Liu L, Guo X and Xu K 2009 Physica A 388 529
|
[13] |
Albert R, Jeong H and Barabási A L 2000 Nature 406 378
|
[14] |
The CAIDA project http://www.caida.org
|
[15] |
Routeviews project http://www.routeviews.org
|
[16] |
Shavitt Y and Shir E ACM SIGCOMM CCR 35 71
|
[17] |
Ager B, Chatzis N, Feldmann A, Sarrar N, Uhlig S and Willinger W 2012 Proceedings of the ACM SIGCOMM (2012 Conference on Applications August 13, 2012, Helsinki) p. 163
|
[18] |
Bollobas B 1998 Random Graphs (New York: Springer) pp. 215-252
|
[19] |
Barabási A L and Albert R 1999 Science 286 509
|
[20] |
Komjáthy J and Simon K 2011 Chaos, Soliton. Fract. 44 651
|
[21] |
Krioukov D, Papadopoulos F, Kitsak M, Vahdat A and BogunáM2010 Phys. Rev. E 82 036106
|
[22] |
Carlson J M and Doyle J 1999 Phys. Rev. E 60 1412
|
[23] |
Lodhi A, Dhamdhere A and Dovrolis C 2012 INFOCOM, 2012 Proceedings IEEE, March 25-30, 2012, Orlando, FL, pp. 1197-1205
|
[24] |
Holme P, Karlin J and Forrest S 2008 ACM SIGCOMM CCR 38 5
|
[25] |
Yakov R, Li T and Hares S 2006 RFC (4271) [2006-01]
|
[26] |
2005 Selecting the Best Path (Juniper Networks)
|
[27] |
2012 BGP Best Path Selection Algorithm: How the Best Path Algorithm Works (Cisco) 13753
|
[28] |
Gill P, Schapira M and Goldberg S 2013 ACM SIGCOMM CCR 44 28
|
[29] |
Huston G 1999 Internet Protocol Journal 2
|
[30] |
Jackson M O 2005 Group Formation in Economics: Networks, Clubs, and Coalitions p. 11
|
[31] |
Gao L and Rexford J 2001 ACMIEEE Trans. Netw. 9 681
|
[32] |
Boguná M and Pastor-Satorras R 2003 Phys. Rev. E 68 036112
|
[33] |
Newman M E 2005 Contemporary Phys. 46 323
|
[34] |
Gugelmann L, Panagiotou K and Peter U 2012 Automata, Languages, and Programming (Berlin: Springer) pp. 573-585
|
[35] |
We omit sibling and backup relationships for simplicity.
|
[36] |
This requirement is fully in line with the Gao-Rexford conditions[31] ensuring BGP stability.
|
[37] |
In YEAS this set represents the clique of tier-1 ASes.
|
[38] |
For reasonable value of N = 40000, R = 17.9, this probability is 0.00135.
|
[39] |
We can assume that the angle coordinate of node v is 0 without loss of generality.
|
[40] |
In case of sparse networks, the conditional distribution of T(r) is Poissonian with mean T(r), P(T(r) = x) = T (r)xe-x/x!. Deconditioning this w.r.t. r results a distribution approximately proportional to x-2, therefore the CCDF of T will be approximately proportional to x-1.
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|