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

Аннотация

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