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

Автор(и)

  • Владимир Иванович Парфенов Воронежский государственный университет, Російська Федерація https://orcid.org/0000-0001-9815-5657
  • Сергей Владимирович Золотарев Воронежский государственный университет, Російська Федерація

DOI:

https://doi.org/10.20535/S0021347008050026

Анотація

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

Посилання

Fratta L. The flow deviation method: An approach to store and forward communication network design / L. Fratta, M. Gerla, L. Kleinrock // Networks. — 1973. — Vol. 3, No. 2. — P. 97–133.

Schwartz M. The gradient projection algorithm for multiple routing in message–switched networks / M. Schwartz, C. K. Cheung // IEEE Trans. Commun. — 1976. — Vol. 25. — P. 100–127.

Frank M. An algorithm for quadratic programming / M. Frank, P. Wolfe // Naval Research Logistics Quarterly. — 1956. — No. 3. — P. 95–110.

Пасечников И. И. Методология анализа и синтеза предельно нагруженных информационных сетей / И. И. Пасечников. — М. : Машиностроение-1, 2004. — 216 c.

Бертсекас Д. Сети передачи данных : пер. с англ. / Д. Бертсекас, Р. Галлагер. — М. : Мир, 1989. — 544 с.

Крон Г. Тензорный анализ сетей / Г. Крон ; пер. с англ. под ред. Л. Т. Кузина, П. Г. Кузнецова. — М. : Сов. радио, 1978. — 719 с.

Опубліковано

2008-05-02

Як цитувати

Парфенов, В. И., & Золотарев, С. В. (2008). Алгоритм условной минимизации целевой функции для оптимального выбора маршрутов в информационных сетях. Вісті вищих учбових закладів. Радіоелектроніка, 51(5), 12–22. https://doi.org/10.20535/S0021347008050026

Номер

Розділ

Оригінальні статті