ALGEBRAIC METHODOLOGY FOR MODELING LOOP-FREE ROUTING
Authors: Хаю Х. , Орлова М.А. , Абросимов Л.И. 
Published: March 2022

Задачу маршрутизации можно сформулировать следующим образом: учитывая сеть G , необходимо найти наилучший путь между узлами i и j из сети. Однако понятие «лучшее» расплывчато, и оно зависит от того, какие параметры в составной метрике сетевые операторы пытаются оптимизировать. Для разделения проблем была введена алгебра маршрутизации для моделирования того, что пытается решить протокол маршрутизации, сохраняя при этом общий алгоритм маршрутизации. Тем не менее все протоколы маршрутизации должны решать проблему свободы от циклов. Цель этой статьи - представить теорию бесцикловой маршрутизации с произвольной метрикой. Показано, что выбор базовой алгебры может повлиять на производительность самого алгоритма, как в представленном примере для протокола маршрутизации (EIGRP). Кроме того, модификация алгебры маршрутизации может помочь во внедрении новых алгоритмов маршрутизации. Примером может служить протокол DSN (Распределенный порядковый номер), который использует гибридный алгоритм состояния каналов и дистанционно-векторный. В метрику DSN добавлены новые компоненты, которые представляют собой порядковый номер и бит флага для запроса увеличения порядкового номера. Это помогло, как показано в этой статье, решить проблему бесцикловой маршрутизации с незначительными изменениями в исходном дистанционно-векторном алгоритме. В данной работе решены следующие задачи. Условия для бесцикловой маршрутизации и отношения между ними были представлены алгебраически и доказаны. Введена концепция монотонной маршрутизации. Была исследована бесцикловая маршрутизация при наличии и отсутствии монотонности. На основании сформулированных теорем разработана алгебраическая модель и валидация бесциклового алгоритма, используемого в протоколе DSN

The routing problem can be formulated as follows: given a network, it is necessary to find the best path between nodes and from the network. However, the concept of “best” is obscure, and it depends on which parameters in the composite metric network operators are trying to optimize. For separation of concerns, routing algebras were introduced to model what the routing protocol is trying to solve while maintaining a generic routing algorithm. However, all routing protocols must address the problem of loop-freedom. The purpose of this article is to present a theory of loop-free routing with an arbitrary metric. It is shown that the choice of the basic algebra can affect the performance of the algorithm itself, as in the presented example for the routing protocol (EIGRP). In addition, the modification of the routing algebra can help in the introduction of new routing algorithms. An example is the DSN protocol (Distributed Sequence Number), which uses a hybrid link-state and distance vector algorithm. New components are added to the DSN metric, which are the sequence number and a flag bit denoting a request to increase the sequence number. This helped, as shown in this article, to solve the problem of loop-free routing with minor changes in the original distance vector algorithm. In this paper, the following tasks have been solved. The conditions for loop-free routing and the relations between them were presented algebraically and proved. The concept of monotonous routing is introduced. Loop-free routing was investigated in the presence and absence of monotony. Based on the formulated theorems, an algebraic model and validation of a loop-free algorithm used in the DSN protocol have been developed