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

Прикладная дискретная математика. 2026. Т. 71. С. 112–127.

Монахова Э. А., Монахов О. Г., Рзаев Э. Р., Лежнев Е. В., Романов А. Ю.

В настоящей работе исследовано совместное конструирование топологий семейств оптимальных по диаметру циркулянтных сетей $C(N; \pm 1, \pm s_2)$ и реализуемых для них оптимальных алгоритмов маршрутизации сложности $O(1)$. Предлагаемый алгоритм маршрутизации основан на использовании масштабируемых параметров $L$-образных шаблонов плотной укладки графов на плоскости для семейств оптимальных сетей.
Определены аналитические формулы зависимости этих параметров от диаметра графов семейств оптимальных сетей $C(N; \pm 1, \pm s_2)$, сокращающие сложность их расчёта до $O(1)$.
Проведено сравнение предлагаемого алгоритма с известным алгоритмом маршрутизации, модификацией которого он является, по затратам времени на маршрутизацию в семействах оптимальных графов и показано уменьшение времени его исполнения в среднем в два раза. Выполнена реализация исследуемого алгоритма маршрутизации в качестве основы маршрутизатора сети на кристалле на языке описания аппаратуры Verilog. Получены данные сравнения его с другими алгоритмами маршрутизации по занимаемым логическим ресурсам и ресурсам памяти.

Ключевые слова: сети на кристалле, неориентированные циркулянтные сети, оптимальный алгоритм маршрутизации, семейства оптимальных циркулянтов