ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ
ТЕХНИКА
УДК 621.865.8-5.001.5
Н. С. В а с и л ь е в
ЗАДАЧА О РАВНОВЕСНОЙ МАРШРУТИЗАЦИИ
ТРАНСПОРТНЫХ СЕТЕЙ
Доказано существование равновесия по Нэшу в векторной зада-
че маршрутизации. Установлено, что равновесие обладает свой-
ствами устойчивости и эффективности по Парето. Обоснована
сходимость игрового алгоритма поиска равновесия, уравнивающего
длины маршрутов.
Ключевые слова:
многопродуктовые сети, маршрутизация, теория игр,
равновесие по Нэшу, оптимальность по Парето, устойчивость решения.
Рассмотрим многокритериальную оптимизационную задачу марш-
рутизации многопродуктовой сети. Создание эффективных систем
управления потоками в транспортных сетях (ТС), например в пакет-
ных телекоммуникационных системах, основано на моделях сетей с
переменной метрикой [1–5]. Изменяемая метрика присуща даже од-
нопродуктовой пакетной сети из-за наличия обратной связи между
потоками и задержки в передаче пакетов (задержка — это метрика).
Игнорирование такой зависимости не позволяет обеспечивать устой-
чивого управления потоками ТС [1].
Свойства ТС с переменной метрикой ранее изучались в связи с
поиском равновесной маршрутизации глобальной пакетной сети пе-
редачи данных [2, 3]. При этом существование равновесной маршру-
тизации установлено лишь для сетей с близкой к кольцевой тополо-
гией. В результате проведения вычислительных экспериментов найде-
но равновесие по Нэшу в модели сети Интернет [4]. Таким образом,
численный поиск равновесного решения задачи уже прошел экспе-
риментальную апробацию, но не получил должного теоретического
обоснования.
Настоящая статья посвящена доказательству общей теоремы суще-
ствования равновесия и установлению его свойств — устойчивости и
эффективности по Парето, сходимости алгоритма поиска равновесной
маршрутизации, в котором, уравниваясь, уменьшаются длины марш-
рутов передачи продуктов.
Оптимизационная модель ТС.
Топологию ТС представим в виде
связного неориентированного графа
Γ
= (
U, V
)
, вдоль ребер
l
∈
V
(
l
= 1
,
2
, . . . , n
) которого расположены линии (каналы) передачи про-
дуктов, а в узлах
u
∈
U
размещены источники и стоки передавае-
мых потоков. Доставка продуктов каждой
k
-й пары источник–сток,
76 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
