Please wait a minute...
Chin. Phys. B, 2015, Vol. 24(11): 118901    DOI: 10.1088/1674-1056/24/11/118901
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.

Keywords:  internet topology      complex network analysis      model  
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.
[1] An optimized infinite time-evolving block decimation algorithm for lattice systems
Junjun Xu(许军军). Chin. Phys. B, 2023, 32(4): 040303.
[2] Drift characteristics and the multi-field coupling stress mechanism of the pantograph-catenary arc under low air pressure
Zhilei Xu(许之磊), Guoqiang Gao(高国强), Pengyu Qian(钱鹏宇), Song Xiao(肖嵩), Wenfu Wei(魏文赋), Zefeng Yang(杨泽锋), Keliang Dong(董克亮), Yaguang Ma(马亚光), and Guangning Wu(吴广宁). Chin. Phys. B, 2023, 32(4): 045202.
[3] Analytical determination of non-local parameter value to investigate the axial buckling of nanoshells affected by the passing nanofluids and their velocities considering various modified cylindrical shell theories
Soheil Oveissi, Aazam Ghassemi, Mehdi Salehi, S.Ali Eftekhari, and Saeed Ziaei-Rad. Chin. Phys. B, 2023, 32(4): 046201.
[4] Lie symmetry analysis and invariant solutions for the (3+1)-dimensional Virasoro integrable model
Hengchun Hu(胡恒春) and Yaqi Li(李雅琦). Chin. Phys. B, 2023, 32(4): 040503.
[5] A simple semiempirical model for the static polarizability of electronically excited atoms and molecules
Alexander S Sharipov, Alexey V Pelevkin, and Boris I Loukhovitski. Chin. Phys. B, 2023, 32(4): 043301.
[6] Mode characteristics of VCSELs with different shape and size oxidation apertures
Xin-Yu Xie(谢新宇), Jian Li(李健), Xiao-Lang Qiu(邱小浪), Yong-Li Wang(王永丽), Chuan-Chuan Li(李川川), Xin Wei(韦欣). Chin. Phys. B, 2023, 32(4): 044206.
[7] Acoustic propagation uncertainty in internal wave environments using an ocean-acoustic joint model
Fei Gao(高飞), Fanghua Xu(徐芳华), Zhenglin Li(李整林), Jixing Qin(秦继兴), and Qinya Zhang(章沁雅). Chin. Phys. B, 2023, 32(3): 034302.
[8] Entanglement and thermalization in the extended Bose-Hubbard model after a quantum quench: A correlation analysis
Xiao-Qiang Su(苏晓强), Zong-Ju Xu(许宗菊), and You-Quan Zhao(赵有权). Chin. Phys. B, 2023, 32(2): 020506.
[9] Simulation based on a modified social force model for sensitivity to emergency signs in subway station
Zheng-Yu Cai(蔡征宇), Ru Zhou(周汝), Yin-Kai Cui(崔银锴), Yan Wang(王妍), and Jun-Cheng Jiang(蒋军成). Chin. Phys. B, 2023, 32(2): 020507.
[10] Dynamic modeling of total ionizing dose-induced threshold voltage shifts in MOS devices
Guangbao Lu(陆广宝), Jun Liu(刘俊), Chuanguo Zhang(张传国), Yang Gao(高扬), and Yonggang Li(李永钢). Chin. Phys. B, 2023, 32(1): 018506.
[11] A novel lattice model integrating the cooperative deviation of density and optimal flux under V2X environment
Guang-Han Peng(彭光含), Chun-Li Luo(罗春莉), Hong-Zhuan Zhao(赵红专), and Hui-Li Tan(谭惠丽). Chin. Phys. B, 2023, 32(1): 018902.
[12] A modified heuristics-based model for simulating realistic pedestrian movement behavior
Wei-Li Wang(王维莉), Hai-Cheng Li(李海城), Jia-Yu Rong(戎加宇), Qin-Qin Fan(范勤勤), Xin Han(韩新), and Bei-Hua Cong(丛北华). Chin. Phys. B, 2022, 31(9): 094501.
[13] Numerical simulation of the thermal non-equilibrium flow-field characteristics of a hypersonic Apollo-like vehicle
Minghao Yu(喻明浩), Zeyang Qiu(邱泽洋), Bo Lv(吕博), and Zhe Wang(王哲). Chin. Phys. B, 2022, 31(9): 094702.
[14] Green's function Monte Carlo method combined with restricted Boltzmann machine approach to the frustrated J1-J2 Heisenberg model
He-Yu Lin(林赫羽), Rong-Qiang He(贺荣强), and Zhong-Yi Lu(卢仲毅). Chin. Phys. B, 2022, 31(8): 080203.
[15] Effect of astrocyte on synchronization of thermosensitive neuron-astrocyte minimum system
Yi-Xuan Shan(单仪萱), Hui-Lan Yang(杨惠兰), Hong-Bin Wang(王宏斌), Shuai Zhang(张帅), Ying Li(李颖), and Gui-Zhi Xu(徐桂芝). Chin. Phys. B, 2022, 31(8): 080507.
No Suggested Reading articles found!