МОДЕЛИРОВАНИЕ ИДЕАЛИЗИРОВАННОЙ ВЕРСИИ РАСПРЕДЕЛЕННОГО АЛГОРИТМА ВЫБОРА МАРШРУТОВ

С.В.Фурсов, К.В. Коняев, ВА. Ларин, Т.В. Лабуткина
(Днепропетровский государственный университет, Украина)

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

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

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

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

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

- редактор сети, который позволяет осуществлять ввод описания сета и его корректировку;

- собственно выполнение алгоритма с наглядным представлением этого процесса;

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

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

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