Особенности программной реализации метода оценки пропускной способности сети на основе оптимизированного метода бисекций

В современном информационном мире достаточно много разнообразных информационных технологий, которые широко используются в различных сферах деятельности [3, с. 67]. Спектр допустимых технологий передачи данных охватывает все возможные средства беспроводных и проводных сетей.

Важным требованием, предъявляемым к современным сетям, является их производительность, которая, в свою очередь, характеризуется пропускной способностью. Пропускная способность сети (network bandwidth) характеризуется количеством информации, которое может быть передано по сети в единицу времени [4, с. 528]. Она непосредственно характеризует качество выполнения основной функции сети — транспортировки сообщений. При проектировании сетей пропускная способность является ключевым параметром, от которого будет зависеть архитектура сети в целом [2, с.122]. При недостаточной пропускной способности сеть не сможет обеспечить требуемые скорость и качество связи между узлами. Оценка пропускной способности сети – задача, имеющая практический аспект в настоящее время.

По рассматриваемой теме имеется ряд публикаций, посвященных методам оценки пропускной способности сети. Разработано множество методов расчета пропускной способности сети, однако они довольно сложны, их результаты связаны с огромным количеством факторов (в особенности присущих современным мультисервисным сетям), которые довольно сложно предугадать. Поэтому в большинстве случаев при построении сетей оценка пропускной способности фактически обусловлена общими рекомендациями производителей, исследованиями и опытом других организаций [2, с. 118].

Анализ публикаций о существующих методах оценки пропускной способности сети и прикладных программ выявил следующие недостатки:

1. Комбинационность алгоритма расчета пропускной способности сети.

2. Непростой интерфейс прикладных программ, требующий специальной подготовки пользователя.

3. Недостатки программного обеспечения: отсутствие поддержки нескольких операционных систем.

Целью работы является устранение перечисленных недостатков оценки пропускной способности сети посредством оптимизированного метода бисекций.

Для достижения поставленной цели решены следующие задачи:

1. Выбран метод оценки пропускной способности сети.

2. Выбран алгоритм поиска бисекций для оценки пропускной способности сети.

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

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

Бисекция сети — это срез сети, разделяющий её примерно пополам, то есть так, что |N₂|<=|N₁|<=|N₂|+1. Ширина бисекции позволяет оценить число сообщений, которые могут быть переданы по сети одновременно, при условии что это не вызовет конфликтов из-за попытки использования одних и тех же узлов или линий связи. Ширину бисекции B характеризуют минимальным числом каналов, разрываемых при всех возможных бисекциях сети:

 B = min_bisection |C(N₁,N₂)|.                                                                                                (1)

Полоса бисекции (bisection bandwidth) — это наименьшая полоса пропускания по всем возможным бисекциям сети. Она характеризует пропускную способность тех линий связи, которые разрываются при бисекции сети, и позволяет оценить наихудшую пропускную способность сети при попытке одномоментной передачи нескольких сообщений, если эти сообщения должны проходить из одной половины сети в другую [4, с. 528]. Полоса бисекции b определяется выражением:

 b = min_bisection B(N₁,N₂).                                                                                                (2)

Топологию сети межсоединений (СМС) определяет множество узлов N объединенных множеством каналов С. Связь между узлами обычно реализуется по двухточечной схеме (point – to - point) [4, с. 524]. Кардиальным вопросом при выборе СМС является способ маршрутизации данных, то есть правило выбора очередного узла, которому пересылается сообщение. Функция маршрутизации данных задает правило вычисления возможного адреса одного из смежных узлов по адресу второго узла [4, с. 529].

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

· Формируется начальная числовая последовательность из введенного пользователем графа.

· Числовая последовательность делится пополам.

· Осуществляется проверка каждой половины числовой последовательности на существование бисекций.

· Если бисекция существует, то числовая последовательность добавляется в матрицу.

· Формируется новая числовая последовательность за счет перестановки предыдущей. И так повторяется до тех пор, пока не будут перебраны все комбинации.

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

При решении третьей задачи была разработана прикладная программа «Анализ пропускной способности сети на основе метода бисекций» [1], которая предназначена для оценки пропускной способности сети при передаче информации по распределенной маршрутной сети на основе метода бисекций.

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

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

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

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

· Все возможные бисекции распределенной маршрутной сети и соответствующее значение пропускной способности для каждой из них.

· Значение минимальной и максимальной пропускной способности сети.

· Ранжированный список бисекций в соответствии с их значениями пропускной способности.

Представленная прикладная программа имеет следующие достоинства:

1) Поддержка нескольких операционных систем (Windows, Linux, macOS).

2) Минимальные системные требования (Windows 2000 и выше).

3) Удобный и понятный пользовательский интерфейс программы: автоматический перенос данных из графа в таблицы, контроль вводимых данных, функция ранжирования результатов.

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