Исследование структурных свойств сети Интернет на основе метаграфовых моделей
Ключевые слова:
сеть Интернет, автономная система, точка присутствия оператора связи, маршрутизация, BGP, метаграф, разрезающее подмножество, Python, MGtoolkit, объекты критической информационной инфраструктурыАннотация
При исследовании сети Интернет ее структуру разделяют на уровни: уровень автономных систем, уровень точек присутствия операторов связи, уровень оборудования и так далее. На каждом из них глобальная сеть может быть описана в виде графа на основании исходных данных, получаемых из открытых источников. Рассмотрение сети в рамках отдельного уровня упрощает анализ, однако не позволяет системно оценить ее структурные свойства при решении задач обеспечения связности нескольких сегментов сети, относящихся, в частности, к объектам критической информационной инфраструктуры. Для преодоления этого противоречия разработана математическая модель глобальной сети на стыке уровня автономных систем и уровня точек присутствия операторов связи в виде метаграфа, которая учитывает особенности каждого из уровней и позволяет находить «узкие» места как в системе междоменной маршрутизации, так и в топологии внутренних сетей интернет-провайдеров.
На основе предложенной модели описаны некоторые структурные феномены глобальной сети: тупиковые, многоинтерфейсные и транзитные автономные системы, контент-провайдеры. С учетом доступных в открытых источниках данных о структуре сети Интернет предложен способ построения метаграфа. Проведен сравнительный анализ инструментов, автоматизирующих процесс анализа модели сети. Сформулированы ориентированные на практику задачи поиска разрезающего подмножества в метаграфе. Определены направления дальнейших исследований – программная реализация инструментов анализа структуры глобальной сети с использованием общедоступного модуля MGtoolkit на языке Python и оценивание структурных феноменов российского сегмента сети Интернет.
Литература
2. Anwar R. et al. Investigating Interdomain Routing Policies in the Wild. URL: http://conferences2.sigcomm.org/imc/2015/papers/p71.pdf (дата обращения: 16.08.2019).
3. McDonald A. et al. 403 Forbidden: A Global View of CDN Geoblocking // 2018 Internet Measurement Conference. URL: http://delivery.acm.org/10.1145/3280000/3278552/p218-McDonald.pdf (дата обращения: 26.06.2019).
4. Filer M. Elastic Optical Networking in the Microsoft Cloud // Optical Society of America. 2016. vol. 8. no. 7. URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/JOCN_Microsoft_EONs_2016_published.pdf (дата обра-щения: 15.08.2019).
5. Luckie M. et al. bdrmap: Inference of Borders Between IP Networks // 2016 Internet Measurement Conference. URL: https://www.caida.org/publications/papers/2016/bdrmap/bdrmap.pdf (дата обраще-ния: 26.03.2019).
6. Giotsas V. et al. Detecting Peering Infrastructure Outages in the Wild // Proceedings of SIGCOMM ’17. URL: https://eprints.lancs.ac.uk/id/eprint/123508/1/SIGCOMM2017.pdf (дата обращения: 21.01.2019).
7. Magharei N., Rejaie R., Rasti A. Eyeball ASes: From Geography to Connectivity // // 2011 Internet Measurement Conference. URL: confer-ences.sigcomm.org/imc/2010/papers/p192.pdf (дата обращения: 21.01.2019).
8. Feldman D., Shavitt Y., Zilberman N. A Structural Approach for PoP Geo-Location // 2010 INFOCOM IEEE Conference on Computer Communications Workshops. 2010. URL: https://www.semanticscholar.org/paper/A-Structural-Approach-for-PoP-Geo-Location-Feldman-Shavitt/030c9d38121227b89523e063f241e52b472d5909 (дата обращения: 26.03.2019).
9. Smaragdakis G., Huffaker B., Giotsas V. Mapping Peering Interconnections to a Facil-ity // Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies. 2015. URL: caida.org/publications/papers/2015/map-ping_peering_interconnections/mapping_peering_interconnections.pdf (дата обращения: 26.03.2019).
10. Shavitt Y., Zilberman N. Improving IP geolocation by crawling the internet PoP level graph // 2013 IFIP Networking Conference. 2013 URL: https://www.semanticscholar.org/paper/Improving-IP-geolocation-by-crawling-the-internet-Shavitt-Zilberman/0277fca9f0e80438ac298cd78ffb0f883781f249 (дата обращения: 26.03.2019).
11. 2018 Global Internet Phenomena Report. URL: https://www.sandvine.com/2018-internet-phenomena-report (дата обращения: 26.03.2019).
12. Робачевский А.М. Интернет изнутри // М.: Альпина Паблишер. 2015. 223 c.
13. Официальный сайт Routing Information Service. URL: www.ripe.net/projects/ris/docs/index.html (дата обращения: 26.03.2019).
14. Официальный сайт University of Oregon Route Views Project. URL: www.routeviews.org (дата обращения: 26.03.2019).
15. Официальный сайт Packet Clearing House. URL: www.pch.net/home/index.php (дата обращения: 26.03.2019).
16. Ardelean D. libBGPdump. URL: https://bitbucket.org/ripencc/bgpdump/wiki/Home (дата обращения: 06.04.2019).
17. Yamauchi Y., Kiso N.I.T. MRT format data parser. URL: https://github.com/t2mune/mrtparse (дата обращения: 06.04.2019).
18. Иванов М.В., Филимонов П.А. Модель сети Интернет на уровне автономных систем в виде безмасштабного графа // Телекоммуникации: Наука и технология. 2016. № 11. С. 22–26.
19. Официальный сайт проекта об IT linkmeup. URL: http://linkmeup.ru/blog/65.html (дата обращения: 26.03.2019).
20. Roughan M., Willinger W. Internet Topology Research Redux // Recent Advances in Networking. 2013. URL: sigcomm.org/education/ebook/SIGCOMMe-Book2013v1_chapter1.pdf (дата обращения: 26.09.2018).
21. Официальный сайт проекта PeeringDB. URL: peeringdb.com (дата обращения: 26.03.2019).
22. Zilberman N. The Internet PoP Level Graph : PhD thesis / Tel-Aviv University, 2013. URL: cl.cam.ac.uk/~nz247/publications/zilber-man_PhdThesis.pdf (дата обращения: 06.01.2020).
23. Официальный сайт MSK-IX. Города и адреса узлов. URL: https://kb.msk-ix.ru/ix/locations (дата обращения: 12.08.2019).
24. Gaur D., Shastri A., Biswas R. Introducing 'Meta-Network': A New Concept in Net-work Technology. URL: https://www.researchgate.net/publication/263638974_Intro-ducing_’Meta-Network’_A_New_Concept_in_Network_Technology (дата обраще-ния: 26.03.2019).
25. Nykl J., Hrncir J., Jakob M. Achieving Full Plan Multimodality by Integrating Multiple Incomplete Journey Planners // IEEE 18th International Conference on Intelligent Transportation Systems (ITSC). 2015. URL: https://www.researchgate.net/publication/283495853_Achieving_Full_Plan_Multimodality_by_Integrating_Multiple_Incomplete_Journey_Planners (дата обращения: 22.07.2019).
26. Papadopoulos S., Kompatsiaris Y., Vakali A., Spyridonos P. Community detection in Social Media // Data Mining and Knowledge Discovery. 2012. URL: https://www.researchgate.net/publication/233790771_Community_detection_in_Social_Media (дата обращения: 22.07.2019).
27. Fang Y. et al. Semantic Proximity Search on Graphs with Metagraph-based Learn-ing // IEEE 32nd International Conference on Data Engineering (ICDE). 2016. URL: https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=5063&context=sis_research(дата обращения: 26.03.2019).
28. Basu A., Blanning R.W. Metagraphs and their applications // Springer Science & Business Media. 2007. 172 с.
29. Dovrolis A., Dhamdhere C. Twelve Years in the Evolution of the Internet Ecosys-tem // IEEE/ACM Transactions on Networking. 2011. vol. 19. no. 5. pp. 1420–1433. URL: caida.org/publications/papers/2011/twelve_years_evolution/twelve_years_evolu-tion.pdf (дата обращения: 26.03.2019).
30. Huston G. The Death of Transit? URL: http://www.potaroo.net/ispcol/2016-10/xtransit.html (дата обращения: 26.11.2018).
31. Дробышев Е. деПИР во имя статус-кво CDN платежей: Comcast против Level3. URL: https://nag.ru/articles/article/19954/depir-vo-imya-status-kvo-cdn-platejey-comcast-protiv-level3.html (дата обращения: 26.03.2018).
32. Кипчатов А. Магистральный Интернет транзит России 2009, часть I. URL: https://nag.ru/articles/blogs/17525/magistralnyiy-internet-tranzit-rossii-2009-chast-i-.html (дата обращения: 26.10.2017).
33. Blunk L., Karir M., Labovitz C. Multi-Threaded Routing Toolkit (MRT) Routing Information Export Format // Internet Engineering Task Force (IETF). 2011. URL: https://tools.ietf.org/html/rfc6396 (дата обращения: 26.03.2019).
34. Официальный сайт исходных кодов проекта PeeringDB. URL: https://github.com/peeringdb/peeringdb (дата обращения: 06.06.2020).
35. Официальный сайт проекта mgtoolkit. URL: https://github.com/dinesharanathunga/mgtoolkit (дата обращения: 26.03.2019).
36. Ranathunga D., Nguyen H., Roughan M. MGtoolkit: A python package for imple-menting metagraphs // SoftwareX. 2017. vol. 6. pp. 91–93. URL: https://doi.org/10.1016/j.softx.2017.04.001 (дата обращения: 26.11.2019).
37. Huston G. The 32-bit AS Number Report. URL: www.potaroo.net/tools/asn32 (дата обращения: 06.06.2020).
38. Официальный сайт Routing Information Service. RIS Raw Data. URL: da-ta.ris.ripe.net/rrc13 (дата обращения: 06.06.2020).
39. Richter P et ap. Advancing the Art of Internet Edge Outage Detection // In 2018 Internet Measurement Conference. URL: http://delivery.acm.org/10.1145/3280000/3278563/p350-Richter.pdf (дата обраще-ния: 26.11.2019).
40. Федеральный закон от 01.05.2019 № 90-ФЗ «О внесении изменений в Федераль-ный закон «О связи» и Федеральный закон «Об информации, информационных технологиях и о защите информации». URL: http://publication.pravo.gov.ru/Document/View/0001201905010025 (дата обраще-ния: 20.05.2020).
Study of Internet Structure Properties based on Metagraph Models
Abstract
Studying the Internet its structure is usually divided into levels: Autonomous Systems Level (AS), Point of Presence Level (PoP), Router Level, etc. The global network can be represented on each of them as a graph based on the initial data obtained from open sources. Consideration of a network within the framework of a separate level facilitates analysis, but does not allow to systematically assess its structural properties when providing the connectivity between several segments of the network related, particularly, to the objects of critical information infrastructure. To overcome this contradiction, a mathematical model of the global network in the form of a metagraph was developed at the interface between AS-level and PoP-level that takes into account the characteristics of each level and allows to find bottlenecks both in the interdomain routing system and in the topology of internal networks of Internet providers.
Based on the proposed model some structural phenomena of the global network are described: stub, multihomed and transit autonomous systems, content providers. Taking into account available data from open sources about Internet structure, a method for constructing a metagraph is proposed. A comparative analysis of tools that automate the process of analyzing a network model is carried out. The practice-oriented problems of finding a cutting subset in a metagraph were set. Certain areas of further research are software implementation of the models using module MGtoolkit in Python and the assessment of structural phenomena of Russian segments of the Internet.
Опубликован
Как цитировать
Раздел
Copyright (c) Максим Владимирович Иванов, Иван Витальевич Калашников, Мехран Мирзожонович Нуруллаев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).