Регистрация / Вход
Прислать материал

Анализ динамики числа отказов при использовании различных алгоритмов динамической маршрутизации

ФИО: Попов Д. С.

Направление: Информационные технологии

Научный руководитель: с.н.с. Центра распределенных вычислений ИППИ РАН к.т.н. Курочкин И.И.

Институт: Институт информационных технологий и автоматизированных систем управления

Кафедра: Кафедра Инженерной кибернетики

Академическая группа: ММ-12-2

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

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

Целью эксперимента является сравнительный анализ различных алгоритмов динамической маршрутизации с учетом динамики числа отказов. Рассмотрены два вида: с кумулятивным (накапливаемым) и с локальным усредненным числом отказов.

Имитационная модель функционирования телекоммуникационной сети, разработанная в Центре распределенных вычислений ИППИ РАН, имеет следующие особенности: заявка – прокладка пути между парой вершин, заявки поступают последовательно во времени, для дуг есть пропускная способность, которая уменьшается при прохождении заявки по ней, заявки имеют время жизни, при окончании которого происходит освобождение ресурсов сети.

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

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