Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами глобальной сети (Александра Кононова, LVEE-2019)

Материал из 0x1.tv

Версия от 12:20, 4 сентября 2021; StasFomin (обсуждение | вклад) (Batch edit: replace PCRE (\n\n)+(\n) with \2)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Докладчик
Александра Кононова.jpg
Александра Кононова

The experiment, aimed at finding the distribution of path lengths between nodes in the global network and estimation of parameters of that distribution is described. At particular, described the method of measurement of path length from node to the node with traceroute utility of the GNU/Linux system, and limitations on the selection of nodes and , imposed by traceroute. Measurements results are given and analyzed. Simulation model of this experiment was developed to test the experiment validity in the determination of distribution parameters in the global network. This model is also described. It is shown that the global network could not be described by Barabási-Albert model, but it could be described with some approximation by developed and proposed a pre-fractal model.

Видео

on youtube

Презентация

Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet.pdf

Thesis

The experiment, aimed at finding the distribution of path lengths between nodes in the global network and estimation of parameters of that distribution is described. At particular, described the method of measurement of path length from node to the node with traceroute utility of the GNU/Linux system, and limitations on the selection of nodes and , imposed by traceroute. Measurements results are given and analyzed. Simulation model of this experiment was developed to test the experiment validity in the determination of distribution parameters in the global network. This model is also described. It is shown that the global network could not be described by Barabási-Albert model, but it could be described with some approximation by developed and proposed a pre-fractal model.

Введение

Разработка эффективных сетевых приложений невозможна без сведений о структуре сети, в которой они будут работать. Так, в 2011 году, для получения параметров методики МУчОС[1] передачи мультимедийных данных с учётом особенностей сети, был начат эксперимент по оценке распределения длин путей сетевого уровня модели TCP/IP глобальной сети.

Определим понятие длины пути и распределения длин путей. Из-за свойств стека протоколов TCP/IP, если от узла к узлу в принципе возможна передача данных, маршрут передачи данных на сетевом уровне будет единственным. Пусть это .

Тогда длина пути от узла к узлу — количество пересылок узел-узел в этом маршруте. При этом , ... .

Со временем глобальная сеть изменяет свою структуру, и как маршрут передачи данных, так и его длина могут изменяться. Кроме того, из-за особенностей маршрутизации может быть .

Таким образом, под распределением длин путей графа понимается ряд чисел , показывающий, как часто длина встречается среди всех возможных путей в : Непосредственно измерить распределение длин путей для глобальной сети (то есть измерить и проанализировать длины для всех возможных пар ) невозможно как из-за её гигантских размеров, так и из-за отсутствия в стеке TCP/IP средств для измерения расстояния между двумя произвольно взятыми узлами.

Выбираем мензурку

Для исследования маршрутов сетевого уровня в GNU/Linux предназначена утилита traceroute. При запуске в командной строке узла команды результатом будет маршрут передачи данных , причём одна строка вывода traceroute соответствует одному узлу маршрута. Далее путём синтаксического анализа можно определить длину пути .

Таким образом, для измерения длины пути необходимо иметь право на запуск программ на узле (в дальнейшем будем называть его корневым (см. рис. ниже) и знать IP-адрес или имя узла (будем называть его оконечным).

Схема измерений выборочных длин путей
2019-lvee miet kai gav ei rdp.pdf

[ei_rdp]

Также необходима возможность соединения с , то есть оконечный узел должен иметь белый IP-адрес либо находиться в одной подсети с .

Ограничения на выбор оконечного узла гораздо мягче, чем для корневого. Соответственно, количество возможных оконечных узлов может быть намного больше (множество оконечных узлов на рис. [ei_rdp]).

Соответственно, задавшись парой из корневого узла и множества оконечных узлов и измеряя при помощи traceroute расстояния от до каждого из оконечных , можно получить некоторую оценку распределения длин путей глобальной сети. Эта оценка зависит от выбора корневого узла, от множества оконечных узлов и от времени (от текущей конфигурации глобальной сети).

В ходе этого эксперимента были сформированы три различных множества оконечных узлов ( размерами 564, 5222 и 540 уникальных белых IP-адресов соответственно) и три корневых узла ().

Так как все оконечные узлы имели белые IP-адреса, а корневые — серые, каждый маршрут передачи данных от корневого узла до оконечного узла делился на две части: маршрут от корневого узла до шлюза его провайдера и маршрут от шлюза провайдера корневого узла до оконечного узла .

Для каждой пары корневого узла и оконечного узла получались два значения длины пути: полная длина , включающая подсеть провайдера корневого узла и скорректированная длина , исключающая подсеть провайдера корневого узла (то есть включающая только пересылки между узлами с белыми IP-адресами).

После окончания измерений множества полученных значений длин путей и обрабатывались GNU Octave. Соответственно, для каждой пары корневого узла и множества оконечных узлов получались две оценки распределения длин путей: , включающая подсеть провайдера корневого узла и , исключающая подсеть провайдера корневого узла.

Оцениваем

От корневых узлов и было выполнено по четыре разнесённых во времени измерения расстояний до каждого из наборов , , ; от узла , из-за ограниченного времени доступа — только по одному измерению до каждого из наборов , , . Таким образом, всего было выполнено 27 измерений и получено 27 оценок распределения длин путей, включающих подсеть провайдера корневого узла (см. рис. ниже, часть «a») и 27 оценок распределения длин путей, исключающих подсеть провайдера корневого узла (см. рис. ниже, часть «б»)

Экспериментально полученное распределение длин путей
  • а) включая подсеть провайдера корневого узла
  • б) исключая подсеть провайдера корневого узла
2019-lvee miet kai gav zplot 2x1.pdf

[zplot_2x1]

В соответствии с множеством оконечных узлов, корневым узлом и порядковым номером измерения обозначены как и перечислены на рис. [5x2_experiment_moments] именно в таком порядке.

Характеристики экспериментально полученных оценок распределения длин путей
  • а) включая подсеть провайдера корневого узла,
  • б) исключая подсеть провайдера корневого узла
2019-lvee miet kai gav 5x2 experiment moments.pdf

[5x2_experiment_moments]

Вышележащий рисунок, часть «а», показывает разброс характеристик (моды , среднего , среднеквадратического отклонения , асимметрии и эксцесса ) оценок распределения длин путей, включающих подсеть провайдера корневого узла. Ось абсцисс соответствует номеру измерения, как сказано выше; границы между измерениями, соответствующими множествам оконечных узлов , , показаны линиями сетки. Слева от оси ординат разброс показан в виде ящика с усами (усы соответствуют минимальному и максимальному значениям, края ящика — первой и третьей квартилям, линия внутри ящика — медиане, кружок — среднему значению характеристики).

Часть «б» того же рисунка, аналогично показывает разброс характеристик оценок распределения длин путей, исключающих подсеть провайдера корневого узла.

Значение эксцесса здесь и далее вычисляется по формуле с коррекцией на три (так, чтобы эксцесс нормального распределения был бы равен нулю).

Видно, что значения асимметрии и эксцесса оценок распределения длин путей (как , так и ) существенно больше нуля.

Проверяем

Насколько корректны полученные оценки ? Для их проверки было сгенерировано некоторое количество графов , размеры которых позволяют:

  • рассчитать расстояние для всех возможных пар узлов и рассчитать истинное (полное) распределение длин путей ;
  • выполнить имитацию эксперимента и оценить по заданным корневому узлу и множеству оконечных узлов .

Размеры множеств , использованных в экспериментальном исследовании, составляют узлов. Соответственно, минимальным количеством вершин в в расчётах было узлов. Максимальным размером , при котором можно выполнить расчёт менее чем за месяц — узлов.

Граф из вершин представлялся в памяти компьютера в виде сжатой матрицы смежности, то есть вектором из списков, каждый из которых соответствует вершине графа и содержит номера смежных с ней вершин.

Для расчёта длин путей использован поиск в ширину, позволяющего для заданной вершины рассчитать расстояния до всех прочих вершин графа . Таким образом, результат соответствует экспериментальным измерениям для корневой вершины и множества оконечных вершин , включающего все вершины графа. Сложность поиска в ширину для представления графа в виде равна , где — количество рёбер[2]. Таким образом, при расчёте полного распределения длин путей все вершины графа поочерёдно рассматриваются в качестве корневых, и сложность возрастает в раз. Для ускорения расчёта использован компилируемый язык C++ (стандарт C++11) и распараллеливание OpenMP.

Кроме полного распределения длин путей , для каждого графа рассчитывались ещё несколько оценок по разным парам корневой узел-множество оконечных узлов. Эти оценки обозначались .

Корневая вершина , как и оконечные вершины для каждого выбиралась случайно. Количество оконечных вершин во время предварительных вычислений варьировалось в диапазоне узлов. Так как не было выявлено существенного различия результатов, для итогового моделирования было принято .

Таким образом, аналогом выполненных в эксперименте измерений (оценивания распределения длин путей глобальной сети по нескольким корневым узлам и нескольким выборкам оконечных узлов) является один прогон модели, включающий генерацию графа (модели сети), расчёт полного распределения длин путей в нём и его оценок (моделей экспериментальных оценок). Вид полного и его оценок для одного из прогонов модели представлен на рисунке ниже.

Распределение длин путей между узлами в дереве Барабаши–Альберт
  • жирная линия — полное ,
  • тонкие — его оценки )
2019-lvee miet kai gav rdp fullpart ba.pdf

Целью вычислительного эксперимента является сопоставление полного и его оценок , а также их характеристик, в частности, асимметрии и эксцесса.

Так как граф является моделью сетевого уровня сети, использующей стек протоколов TCP/IP, должен быть связным деревом. Сложность поиска в ширину для дерева составляет , таким образом, сложность расчёта всех возможных путей составляет .

Были использованы несколько алгоритмов для генерации связного дерева . Прежде всего исследована знаменитая модель Барабаши"– Альберт[3] (типичные результаты прогона модели, то есть полное и его оценки, показаны на рисунке выше.

Полное для деревьев Барабаши"– Альберт очень похоже на дискретизацию нормального. Все они унимодальны. Большинство оценок рис. [rdp_fullpart_ba] выглядит более островершинными, чем полное , но менее островершинными, чем распределения, полученные экспериментально (рис. [zplot_2x1], а, б). Рассмотрим характеристики полных распределений и их оценок подробнее, см. рисунок ниже:

Характеристики полного распределения длин путей в дереве Барабаши–Альберт (чёрные точки) и разброс характеристик его оценок (ящики с усами)
2019-lvee miet kai gav 5 moments ba.pdf

[5_moments_ba]

Так как один прогон модели соответствует множеству оценок, а в процессе исследования было выполнено множество прогонов, визуализировать характеристику каждой конкретной оценки аналогично рис. [5x2_experiment_moments] нерационально. Соответственно, один прогон на рис. [5_moments_ba] соответствует одной вертикали (по оси абсцисс откладывается номер смоделированного графа; измерения сгруппированы по количеству вершин в графе). Для каждого прогона и каждой характеристики показан разброс значений характеристики в виде ящика с усами (аналогично показанному слева на рис. [5x2_experiment_moments]); кроме того, чёрной точкой на рис. [5_moments_ba] показано значение характеристики (для экспериментальных данных его аналог — характеристика глобальной сети — недоступна и поэтому отсутствует на рис. [5x2_experiment_moments]).

Видно, что асимметрия полных распределений для деревьев Барабаши"– Альберт несколько больше нуля, но не достигает полученных в результате эксперимента значений . Асимметрия оценок может быть как больше, так и (что чаще) ещё меньше асимметрии . С ростом количества вершин в графе асимметрия как , так и не растёт.

Эксцесс полных распределений для деревьев Барабаши"– Альберт близок к нулю. Эксцесс оценок может быть как больше (что чаще), так и меньше эксцесса , при этом ни одна из этих величин не достигает полученных в результате эксперимента значений . С ростом количества вершин в графе эксцесс как , так и не растёт.

Погрешность оценивания асимметрии достигает 100%, а эксцесса — 1000% (последнее обусловлено близостью к нулю эксцесса ).

Таким образом, различие между асимметрией и эксцессом экспериментально полученных для сетевого уровня глобальной сети данных и распределениями длин путей в деревьях Барабаши"– Альберт обусловлено не случайными отклонениями, не методикой измерения и не отличием в размерах (асимметрия и эксцесс мало изменяются при росте ).

Соответственно, различие должно быть обусловлено моделью роста дерева. В исследовании были рассмотрены несколько моделей роста. Наиболее перспективной выглядит предфрактальная модель, описывающая рост сети как рост множества связанных друг с другом подсетей (рис. [rdp_fullpart_pfk_32] и [6_moments_pfk_32]).

Распределение длин путей между узлами (жирная линия — полное , тонкие — его оценки ) в предфрактальном дереве
2019-lvee miet kai gav rdp fullpart pfk 32.pdf

[rdp_fullpart_pfk_32]

Характеристики полного распределения длин путей в предфрактальном дереве (чёрные точки) и разброс характеристик его оценок (ящики с усами)
2019-lvee miet kai gav 6 moments pfk 32.pdf

[6_moments_pfk_32]

Вид полного и его оценок для одного из прогонов модели представлен на рис. [rdp_fullpart_pfk_32]. На рис. [6_moments_pfk_32] этот прогон — первый в группе .

Так как подсети формируются при росте графа случайным образом, полные для предфрактальных деревьев более разнообразны, чем для деревьев Барабаши"– Альберт. Некоторые из них не унимодальны. Соответственно, на рис. [6_moments_pfk_32] в числе прочих характеристик показано и количество выраженных максимумов . В остальном организация рис. [6_moments_pfk_32] аналогична рис. [5_moments_ba].

Распределение на рис. [rdp_fullpart_pfk_32] отличается от рис. [5_moments_ba] наличием толстого правого хвоста. В целом, в зависимости от соотношения размеров подсетей предфрактального дерева может иметь как более или менее толстый правый хвост, аналогичный рис. [rdp_fullpart_pfk_32], так и один или несколько ярко выраженных побочных максимумов (второй прогон в группе ), либо, наоборот, может иметь тонкий хвост, как для деревьев Барабаши"– Альберт (первый прогон в группе — в процессе роста сформировалась только одна крупная подсеть).

Соответственно, разброс как характеристик для разных прогонов, так и их оценок для одного прогона модели на рис. [6_moments_pfk_32] больше, чем на рис. [5_moments_ba].

Асимметрия и эксцесс первого прогона в группе (с единственной крупной подсетью) ожидаемо близки к асимметрии и эксцессу деревьев Барабаши"– Альберт, а их оценки имеют столь же маленький разброс.

Асимметрия полного второго прогона в группе (с двумя конкурирующими подсетями, то есть практически одинаковыми максимумами) положительна, при этом асимметрии её оценок могут принимать и отрицательные значения. Эксцесс полного и большинство его оценок отрицательны, так как два близких максимума суммарно массивнее хвостов распределения.

Для всех прочих прогонов асимметрия и эксцесс положительны, а их оценки в подавляющем большинстве завышены. При этом с ростом увеличивается и разброс распределений длин путей от прогонов, и абсолютная величина асимметрии и эксцесса.

Погрешность оценивания асимметрии достигает 100%, а эксцесса — 500%.

Заключение

Инструментальные средства, стандартные для большинства дистрибутивов GNU/Linux, а также GNU Octave, позволяют выборочно оценить распределение длин путей между узлами в глобальной сети.

Имитационное моделирование позволяет утверждать, что, несмотря на гигантскую погрешность оценивания асимметрии и эксцесса описываемым методом, полученные экспериментальные данные позволяют уверенно утверждать, что сетевой уровень глобальной сети не описывается моделью Барабаши"– Альберт, но может быть в некотором приближении описан разработанной предфрактальной моделью.

Имитационное моделирование погрешности экспериментального исследования распределения длин путей между узлами Internet!.jpg

Примечания и ссылки

  1. Кононова А. И., Городилов А. В., Шаньгин В. Ф. Особенности передачи данных в децентрализованных пиринговых сетях // Изв. вузов. Электроника (ВАК). 2012. No 6(98). С. 95.
  2. Седжвик Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах. СПб: Диа Софт, 2003. 1136 с.
  3. Jeong H., Tombor B., Albert R. et al. The Large-Scale Organization of Metabolic Networks. 2000. https://arxiv.org/pdf/cond-mat/0010278.pdf

Plays:53   Comments:5