Международная конференция разработчиков
и пользователей свободного программного обеспечения

Измеряем океан мензуркой (оценка характеристик глобальной сети)

Александра Кононова, Moscow/Zelenograd, Russian Federation

LVEE 2019

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.

\documentclass[10pt, a5paper]{article}
\input{preamble.tex}
\switchlang{ru}
\begin{document}
\title{Измеряем океан мензуркой (оценка характеристик глобальной сети)\footnote{\url{illinc@bk.ru}, \url{https://lvee.org/???}}}
% \author{Александра Кононова, Moscow/Zelenograd, Russian Federation, \linebreak Алексей Городилов, Russian Federation} % не лезет!
\author{Александра Кононова, Алексей Городилов, Russian Federation}
\maketitle
\begin{abstract}
% Описан эксперимент по оцениванию распределения длин путей между узлами в~глобальной сети и~его характеристик.
% В~частности, показана методика измерения длины пути от узла к узлу при помощи утилиты GNU/Linux traceroute и~ограничения выбора узлов и~, налагаемые этим инструментом.
% Приведены результаты измерений.
% Описана имитационная модель эксперимента, разработанная для проверки корректности полученных оценок распределения длин путей между узлами в~глобальной сети.
% Показано, что глобальная сеть не описывается моделью Барабаши"—~Альберт, но может быть в~некотором приближении описана разработанной предфрактальной моделью.
An experiment to estimate the distribution of path lengths between nodes in the global network and its characteristics is described.
In particular, the technique of measuring the path length from node to node using the GNU/Linux traceroute utility and limiting the choice of and nodes imposed by this tool is shown.
The results of measurements are given.
Describes a simulation model of the experiment, designed to check the accuracy of the obtained estimates of the distribution of the lengths of the paths between the nodes in the global network.
It is shown that the WAN is not described by the model of Barabasi-albert, but can be in some approximation we develop a model pre-fractal graphs.
\end{abstract}

\subsection*{Введение}

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

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

% Тогда количество пересылок узел-узел в этом маршруте будем называть длиной пути от узла к узлу :
%
div.

Тогда длина %5Calpha,%20%5Cbeta пути от узла к узлу "—- количество пересылок узел-узел в этом маршруте.
При этом , … .

Со временем глобальная сеть изменяет свою структуру, и как маршрут передачи данных, так и~его длина %5Calpha,%20%5Cbeta могут изменяться.
Кроме того,
из-за особенностей маршрутизации может быть %5Cbeta,%20%5Calpha.
% ; кроме того, как %5Calpha,%20%5Cbeta, так и маршрут передачи данных от к может изменяться во времени. При этом в каждый момент времени и т. д.

Таким образом, под распределением длин путей графа
понимается ряд чисел x, показывающий, как часто длина встречается среди всех возможных путей в~:

Непосредственно измерить распределение длин путей x для глобальной сети (то есть измерить и~проанализировать длины %5Calpha,%20%5Cbeta для всех возможных пар %5Calpha,%20%5Cbeta) невозможно как из-за её гигантских размеров, так и~из-за отсутствия в~стеке TCP/IP средств для измерения расстояния между двумя произвольно взятыми узлами.

\subsection*{Выбираем мензурку}

Для исследования маршрутов сетевого уровня в~GNU/Linux предназначена утилита traceroute.
При запуске в~командной строке узла команды \mbox{\texttt{traceroute }} результатом будет маршрут передачи данных , причём одна строка вывода traceroute соответствует одному узлу маршрута.
Далее путём синтаксического анализа можно определить длину пути %5Calpha,%20%5Cbeta.

Таким образом, для измерения длины пути %5Calpha,%20%5Cbeta необходимо иметь право на запуск программ на узле
(в~дальнейшем будем называть его корневым, рис.~\ref{ei_rdp}) и~знать IP-адрес или имя узла (будем называть его оконечным).
\begin{figure}[h!]
\centering
\includegraphics[width=0.7\linewidth]{2019_miet_kai_gav_ei_rdp}
\caption{Схема измерений выборочных длин путей}
\label{ei_rdp}
\end{figure}%
Также необходима возможность соединения с~, то есть оконечный узел должен иметь белый IP-адрес либо находиться в~одной подсети с~.

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

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

%Соответственно, граф, вершинами которого являются все доступные узлы глобальной сети (с белыми IP-адресами), а рёбрами "—- ???, является деревом.
В ходе этого эксперимента были сформированы три различных множества оконечных узлов ( размерами 564, 5222 и~540 уникальных белых IP-адресов соответственно)
и~три корневых узла ().

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

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

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

\subsection*{Оцениваем}

От корневых узлов и~ было выполнено по четыре разнесённых во времени измерения расстояний до каждого из наборов , , ;
от узла , из-за ограниченного времени доступа "—- только по одному измерению до каждого из наборов , , .
Таким образом, всего было выполнено 27~измерений и~получено 27 оценок x распределения длин путей, включающих подсеть провайдера корневого узла (рис.~\ref{zplot_2x1}, а)
\begin{figure}[h!]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_zplot_2x1}
\caption{Экспериментально полученное распределение длин путей:
а) включая подсеть провайдера корневого узла,
б)~исключая подсеть провайдера корневого узла
}
\label{zplot_2x1}
\end{figure}%
и~27 оценок~x распределения длин путей, исключающих подсеть провайдера корневого узла (рис.~\ref{zplot_2x1}, б).

В~соответствии с~множеством оконечных узлов, корневым узлом и~порядковым номером измерения
обозначены как
и~перечислены на рис.~\ref{5x2_experiment_moments} именно в~таком порядке.

\begin{figure}[p]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_5x2_experiment_moments}
\caption{Характеристики экспериментально полученных оценок распределения длин путей:
а) включая подсеть провайдера корневого узла,
б)~исключая подсеть провайдера корневого узла
}
\label{5x2_experiment_moments}
\end{figure}

Рис.~\ref{5x2_experiment_moments}, а) показывает разброс характеристик (моды , среднего , среднеквадратического отклонения , асимметрии и~эксцесса ) оценок x распределения длин путей, включающих подсеть провайдера корневого узла.
% По оси абсцисс
Ось абсцисс соответствует номеру измерения, как сказано выше;
% измерения сгруппированы по множеству оконечных узлов (, , "—- границы групп показаны линиями сетки), затем по корневому узлу
% % , внутри каждой группы упорядочены по
% и~времени (, , , , далее и~, , , ).
границы между измерениями, соответствующими множествам оконечных узлов , , показаны линиями сетки.
%
Слева от оси ординат разброс показан в~виде ящика с~усами (усы соответствуют минимальному и~максимальному значениям, края ящика "—- первой и~третьей квартилям, линия внутри ящика "—- медиане, кружок "—- среднему значению характеристики).

Рис.~\ref{5x2_experiment_moments}, б) аналогично показывает разброс характеристик оценок x распределения длин путей, исключающих подсеть провайдера корневого узла.

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

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

\subsection*{Поверяем}

Насколько корректны полученные оценки x?
%
Для их проверки было сгенерировано некоторое количество графов , размеры которых позволяют:
\begin{itemize}
\item[—]рассчитать расстояние %5Calpha,%20%5Cbeta для всех возможных пар узлов и~рассчитать истинное (полное) распределение длин путей x;

\item[—] %а~также
выполнить имитацию эксперимента и~оценить x по
заданным корневому узлу и~множеству оконечных узлов .
\end{itemize}
Размеры множеств , использованных в~экспериментальном исследовании, составляют узлов.
Соответственно, минимальным количеством вершин в~ в~расчётах было узлов.
Максимальным размером , при котором можно выполнить расчёт менее чем за месяц "—- узлов.

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

% Как для расчёта
Для расчёта длин путей использован поиск в~ширину,
позволяющего для заданной вершины рассчитать расстояния до всех прочих вершин графа .
Таким образом, результат соответствует экспериментальным измерениям для корневой вершины и~множества оконечных вершин , включающего все вершины графа.
Сложность поиска в~ширину для представления графа в~виде равна %7CG%7C%20+%7CE_G%7C, где "—- количество рёбер~\cite{Sedgewick2002_AlgorithmsinC_Fundamentals}.
Таким образом, при расчёте полного распределения длин путей все вершины графа поочерёдно рассматриваются в~качестве корневых, и~сложность возрастает в~ раз.
Для ускорения расчёта использован компилируемый язык C++ (стандарт C++11) и~распараллеливание OpenMP.

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

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

Таким образом, аналогом выполненных в~эксперименте измерений (оценивания распределения длин путей глобальной сети по нескольким корневым узлам и~нескольким выборкам оконечных узлов)
является один прогон модели, включающий
% :
% \begin{itemize}
% \item[—]
% \end{itemize}
генерацию графа (модели сети), расчёт полного распределения длин путей x в~нём и~его оценок x (моделей экспериментальных оценок).
Вид полного x и~его оценок x для одного из прогонов модели представлен на рис.~\ref{rdp_fullpart_ba}).

\begin{figure}[!h]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_rdp_fullpart_ba}
\caption{Распределение длин путей между узлами (жирная линия "—- полное x, тонкие “- его оценки~x) в~дереве Барабаши”—~Альберт}
\label{rdp_fullpart_ba}
\end{figure}

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

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

Были использованы несколько алгоритмов для генерации связного дерева .
Прежде всего исследована знаменитая модель Барабаши"—~Альберт~\cite{ba} (типичные результаты прогона модели, то есть полное x и~его оценки, показаны на рис.~\ref{rdp_fullpart_ba}).
% На рис.~\ref{rdp_fullpart_ba} показан типичный пример графика x (жирная линия) и~x (множество тонких линий) РДП для модели Барабаши"—~Альберт.

Полное x для деревьев Барабаши"—~Альберт очень похоже на дискретизацию нормального.
Все они унимодальны.
Большинство оценок x рис.~\ref{rdp_fullpart_ba} выглядит более островершинными, чем полное x, но менее островершинными, чем распределения, полученные экспериментально (рис.~\ref{zplot_2x1}, а, б).
Рассмотрим характеристики полных распределений и~их оценок подробнее (рис.~\ref{5_moments_ba}).

\begin{figure}[p]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_5_moments_ba}
\caption{Характеристики полного распределения длин путей в~дереве Барабаши"—~Альберт (чёрные точки) и~разброс характеристик его оценок (ящики с~усами)}
\label{5_moments_ba}
\end{figure}

Так как один прогон модели соответствует множеству
% экспериментальных измерений,
оценок, а~в~процессе исследования было выполнено множество прогонов, визуализировать характеристику каждой конкретной оценки аналогично рис.~\ref{5x2_experiment_moments} нерационально.
Соответственно, один прогон на рис.~\ref{5_moments_ba} соответствует одной вертикали (по оси абсцисс откладывается номер смоделированного графа; измерения сгруппированы по количеству вершин в~графе).
Для каждого прогона и~каждой характеристики показан разброс значений характеристики x в~виде ящика с~усами (аналогично показанному слева на рис.~\ref{5x2_experiment_moments});
кроме того, чёрной точкой на рис.~\ref{5_moments_ba} показано значение характеристики x (для экспериментальных данных его аналог "—- характеристика x глобальной сети "—- недоступна и~поэтому отсутствует на рис.~\ref{5x2_experiment_moments}).

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

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

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

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

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

\begin{figure}[!h]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_rdp_fullpart_pfk_32}
\caption{Распределение длин путей между узлами (жирная линия "—- полное x, тонкие "—- его оценки~x) в~предфрактальном дереве}
\label{rdp_fullpart_pfk_32}
\end{figure}

\begin{figure}[p]
\centering
\includegraphics[width=\linewidth]{2019_miet_kai_gav_6_moments_pfk_32}
\caption{Характеристики полного распределения длин путей в~предфрактальном дереве (чёрные точки) и~разброс характеристик его оценок (ящики с~усами)}
\label{6_moments_pfk_32}
\end{figure}%

Вид полного x и~его оценок x для одного из прогонов модели представлен на рис.~\ref{rdp_fullpart_pfk_32}.
На рис.~\ref{6_moments_pfk_32} этот прогон "—- первый в~группе .

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

Распределение x на рис.~\ref{rdp_fullpart_pfk_32} отличается от рис.~\ref{5_moments_ba} наличием толстого правого хвоста.
% ,
% % который, хотя и~не формирует
% Это “- наиболее типичная форма x предфрактального дерева.
% Тем не менее, в~зависимости от соотношения размеров подсетей x может иметь
В~целом, в~зависимости от соотношения размеров подсетей
% % а~также соединений
x предфрактального дерева может иметь как более или менее толстый правый хвост, аналогичный рис.~\ref{rdp_fullpart_pfk_32}, так и~
один или несколько ярко выраженных побочных максимумов (второй прогон в~группе ), либо, наоборот, может иметь тонкий хвост, как для x деревьев Барабаши”—~Альберт (первый прогон в~группе "—- в~процессе роста сформировалась только одна крупная подсеть).

Соответственно, разброс как характеристик x для разных прогонов, так и~их оценок x для одного прогона модели на~рис.~\ref{6_moments_pfk_32} больше, чем на~рис.~\ref{5_moments_ba}.

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

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

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

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

\subsection*{Заключение}

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

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

\begin{thebibliography}{9}
\bibitem{muchos} {Кононова А. И., Городилов А. В., Шаньгин В. Ф. Особенности передачи
данных в децентрализованных пиринговых сетях // Изв. вузов. Электроника
(ВАК). 2012. No 6(98). С. 95.
}
\bibitem{Sedgewick2002_AlgorithmsinC_Fundamentals} {Седжвик Р. Фундаментальные алгоритмы на С++: Алгоритмы на графах.
СПб: Диа Софт, 2003. 1136 с.
}

\bibitem{ba} {Jeong H., Tombor B., Albert R. et al. The Large-Scale Organization of Metabolic Networks. 2000. \url{https://arxiv.org/pdf/cond-mat/0010278.pdf}
}

\end{thebibliography}

\end{document}

Abstract licensed under Creative Commons Attribution-ShareAlike 3.0 license

Назад