Исследование структурных свойств сети Интернет на основе метаграфовых моделей
Ключевые слова:
сеть Интернет, автономная система, точка присутствия оператора связи, маршрутизация, BGP, метаграф, разрезающее подмножество, Python, MGtoolkit, объекты критической информационной инфраструктурыАннотация
При исследовании сети Интернет ее структуру разделяют на уровни: уровень автономных систем, уровень точек присутствия операторов связи, уровень оборудования и так далее. На каждом из них глобальная сеть может быть описана в виде графа на основании исходных данных, получаемых из открытых источников. Рассмотрение сети в рамках отдельного уровня упрощает анализ, однако не позволяет системно оценить ее структурные свойства при решении задач обеспечения связности нескольких сегментов сети, относящихся, в частности, к объектам критической информационной инфраструктуры. Для преодоления этого противоречия разработана математическая модель глобальной сети на стыке уровня автономных систем и уровня точек присутствия операторов связи в виде метаграфа, которая учитывает особенности каждого из уровней и позволяет находить «узкие» места как в системе междоменной маршрутизации, так и в топологии внутренних сетей интернет-провайдеров.
На основе предложенной модели описаны некоторые структурные феномены глобальной сети: тупиковые, многоинтерфейсные и транзитные автономные системы, контент-провайдеры. С учетом доступных в открытых источниках данных о структуре сети Интернет предложен способ построения метаграфа. Проведен сравнительный анализ инструментов, автоматизирующих процесс анализа модели сети. Сформулированы ориентированные на практику задачи поиска разрезающего подмножества в метаграфе. Определены направления дальнейших исследований – программная реализация инструментов анализа структуры глобальной сети с использованием общедоступного модуля MGtoolkit на языке Python и оценивание структурных феноменов российского сегмента сети Интернет.
Литература
1. Huffaker B. Autonomous Systems (AS) Introduction and Topology. URL: www.caida.org/publications/presentations/2016/as_intro_topology_wind/as_intro_topology_wind.pdf (дата обращения: 26.03.2019).
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).
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).
Опубликован
2020-08-01
Как цитировать
Иванов, М. В., Калашников, И. В., & Нуруллаев, М. М. (2020). Исследование структурных свойств сети Интернет на основе метаграфовых моделей. Труды СПИИРАН, 19(4), 880-905. https://doi.org/10.15622/sp.2020.19.4.7
Раздел
Цифровые информационно-телекоммуникационные технологии
Copyright (c) Максим Владимирович Иванов, Иван Витальевич Калашников, Мехран Мирзожонович Нуруллаев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).