Deductive way of reasoning about the internet AS level topology

doi:10.1088/1674-1056/24/11/118901

中国物理B ›› 2015, Vol. 24 ›› Issue (11): 118901-118901.doi: 10.1088/1674-1056/24/11/118901

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇下一篇

Deductive way of reasoning about the internet AS level topology

Dávid Szabó^a, Attila Kőrösi^{a c}, József Bíró^{a b}, András Gulyás^{a 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

收稿日期:2015-04-08 修回日期:2015-07-09 出版日期:2015-11-05 发布日期:2015-11-05
通讯作者: Dávid Szabó E-mail:szabod@tmit.bme.hu
基金资助:
Project supported by Ericsson and partially supported by the Hungarian Scientific Research Fund (Grant No. OTKA 108947).

Deductive way of reasoning about the internet AS level topology

Dávid Szabó^a, Attila K?rösi^{a c}, József Bíró^{a b}, András Gulyás^{a 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

Received:2015-04-08 Revised:2015-07-09 Online:2015-11-05 Published:2015-11-05
Contact: Dávid Szabó E-mail:szabod@tmit.bme.hu
Supported by:
Project supported by Ericsson and partially supported by the Hungarian Scientific Research Fund (Grant No. OTKA 108947).

摘要/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.

关键词: internet topology, complex network analysis, model

Abstract:

Key words: internet topology, complex network analysis, model

中图分类号: (Structures and organization in complex systems)

89.75.Fb

89.20.Hh (World Wide Web, Internet)

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[J]. 中国物理B, 2015, 24(11): 118901-118901.

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[J]. Chin. Phys. B, 2015, 24(11): 118901-118901.

参考文献 40

[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.

Deductive way of reasoning about the internet AS level topology

Deductive way of reasoning about the internet AS level topology

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 40

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Junjun Xu(许军军)^†. An optimized infinite time-evolving block decimation algorithm for lattice systems[J]. 中国物理B, 2023, 32(4): 40303-040303.
[2]	Zhilei Xu(许之磊), Guoqiang Gao(高国强), Pengyu Qian(钱鹏宇), Song Xiao(肖嵩), Wenfu Wei(魏文赋), Zefeng Yang(杨泽锋), Keliang Dong(董克亮), Yaguang Ma(马亚光), and Guangning Wu(吴广宁). Drift characteristics and the multi-field coupling stress mechanism of the pantograph-catenary arc under low air pressure[J]. 中国物理B, 2023, 32(4): 45202-045202.
[3]	Soheil Oveissi, Aazam Ghassemi, Mehdi Salehi, S.Ali Eftekhari, and Saeed Ziaei-Rad. 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[J]. 中国物理B, 2023, 32(4): 46201-046201.
[4]	Hengchun Hu(胡恒春) and Yaqi Li(李雅琦). Lie symmetry analysis and invariant solutions for the (3+1)-dimensional Virasoro integrable model[J]. 中国物理B, 2023, 32(4): 40503-040503.
[5]	Alexander S Sharipov, Alexey V Pelevkin, and Boris I Loukhovitski. A simple semiempirical model for the static polarizability of electronically excited atoms and molecules[J]. 中国物理B, 2023, 32(4): 43301-043301.
[6]	Xin-Yu Xie(谢新宇), Jian Li(李健), Xiao-Lang Qiu(邱小浪), Yong-Li Wang(王永丽), Chuan-Chuan Li(李川川), Xin Wei(韦欣). Mode characteristics of VCSELs with different shape and size oxidation apertures[J]. 中国物理B, 2023, 32(4): 44206-044206.
[7]	Fei Gao(高飞), Fanghua Xu(徐芳华), Zhenglin Li(李整林), Jixing Qin(秦继兴), and Qinya Zhang(章沁雅). Acoustic propagation uncertainty in internal wave environments using an ocean-acoustic joint model[J]. 中国物理B, 2023, 32(3): 34302-034302.
[8]	Zheng-Yu Cai(蔡征宇), Ru Zhou(周汝), Yin-Kai Cui(崔银锴), Yan Wang(王妍), and Jun-Cheng Jiang(蒋军成). Simulation based on a modified social force model for sensitivity to emergency signs in subway station[J]. 中国物理B, 2023, 32(2): 20507-020507.
[9]	Xiao-Qiang Su(苏晓强), Zong-Ju Xu(许宗菊), and You-Quan Zhao(赵有权). Entanglement and thermalization in the extended Bose-Hubbard model after a quantum quench: A correlation analysis[J]. 中国物理B, 2023, 32(2): 20506-020506.
[10]	Guangbao Lu(陆广宝), Jun Liu(刘俊), Chuanguo Zhang(张传国), Yang Gao(高扬), and Yonggang Li(李永钢). Dynamic modeling of total ionizing dose-induced threshold voltage shifts in MOS devices[J]. 中国物理B, 2023, 32(1): 18506-018506.
[11]	Guang-Han Peng(彭光含), Chun-Li Luo(罗春莉), Hong-Zhuan Zhao(赵红专), and Hui-Li Tan(谭惠丽). A novel lattice model integrating the cooperative deviation of density and optimal flux under V2X environment[J]. 中国物理B, 2023, 32(1): 18902-018902.
[12]	Wei-Li Wang(王维莉), Hai-Cheng Li(李海城), Jia-Yu Rong(戎加宇), Qin-Qin Fan(范勤勤), Xin Han(韩新), and Bei-Hua Cong(丛北华). A modified heuristics-based model for simulating realistic pedestrian movement behavior[J]. 中国物理B, 2022, 31(9): 94501-094501.
[13]	Minghao Yu(喻明浩)^†, Zeyang Qiu(邱泽洋), Bo Lv(吕博), and Zhe Wang(王哲). Numerical simulation of the thermal non-equilibrium flow-field characteristics of a hypersonic Apollo-like vehicle[J]. 中国物理B, 2022, 31(9): 94702-094702.
[14]	Yue-Ran Shi(石悦然), Jin-Ge Chen(陈金鸽), Kui-Yi Gao(高奎意), and Wei Zhang(张威). Non-universal Fermi polaron in quasi two-dimensional quantum gases[J]. 中国物理B, 2022, 31(8): 80305-080305.
[15]	Ya-Xiao Mo(莫亚枭), Chao-Jin Zhang(张朝金), Li-Cheng Lu(鹿力成), and Sheng-Ming Guo(郭圣明). Three-dimensional coupled-mode model and characteristics of low-frequency sound propagation in ocean waveguide with seamount topography[J]. 中国物理B, 2022, 31(8): 84301-084301.