Задавая маршрутизацию, будем перечислять только применяемые
маршруты передачи, для которых маршрутные потоки положитель-
ны. В процессе управления ТС за счет ограничения входного потока
обеспечивается его допустимость. Выбордопустимой маршрутизации
M
=
{{
L
k
j
}
,
{
λ
k
j
}
, k
= 1
,
2
, . . . , K
}
однозначно задает вектордопусти-
мых потоков по линиям ТС
z
= (
z
1
, z
2
, . . . , z
n
)
, от которого зависит
время передачи продуктов (изменяется метрика сети (1)).
Любая
k
-я тяготеющая пара “заинтересована” в уменьшении вре-
мени доставки продуктов, которое определяется длинами применяе-
мых маршрутов передачи (1). В сети с потоками
z
минимально воз-
можное время доставки продуктов
k
-й пары составляет
T
k
(
z
) = min
{
L
k
}
ρ
(
L
k
, z
)
,
где
{
L
k
}
— множество всех маршрутов, соединяющих эту пару.
Маршрутизацию
k
-й тяготеющей пары назовем оптимальной, если
все применяемые маршруты передачи имеют минимальную длину,
равную
T
k
(
z
)
.
Поскольку вектор
z
зависит от выбираемой маршрутизации
(см. (2)), то оптимальным решением этой задачи для
k
-й пары является
выбор ее кратчайших маршрутов соединения в сети с изменяющейся
метрикой (1) [5].
Далее исследуется игровая задача об оптимальной маршрутизации
ТС. Тяготеющие пары
k
= 1
,
2
, . . . , K
рассматриваются как игроки
в бескоалиционной игре, выбирающие свою стратегию — маршрути-
зацию [2, 4]. Равновесие по Нэшу в этой игре назовем равновесной
(оптимальной) маршрутизацией ТС. Соответствующий вектор потоков
в сети также будем называть равновесным.
В равновесии каждой тяготеющей паре “невыгодно” отклоняться
от своей маршрутизации (из-за этого время передачи продуктов только
увеличится) при условии, что все остальные пары придерживаются
своих маршрутизаций.
На практике выбор маршрутизации может проводиться не самими
тяготеющими парами, а с помощью некотор ого алгор итма, постр оен-
ного на этом принципе. Таковы, например, сетевые протоколы [1].
Существование равновесия.
Введем вспомогательную задачу
математического программирования, определив функции
t
l
=
t
l
(
z
l
)
(
l
= 1
,
2
, . . . , n
) как решения задачи Коши для обыкновенного диффе-
ренциального уравнения (ОДУ):
z
l
dt
l
dz
l
+
t
l
=
f
l
(
z
l
)
, t
l
(0) = 0
.
(4)
78 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
