Тогда критерий оптимальности маршрутизации (векторы
λ
=
λ
∗
,
z
∗
=
Aλ
∗
)
для
k
-й тяготеющей пары принимает следующий вид:
∇
λ
H
=
fA
−
μ
(1
, . . . ,
1) 0
,
∀
j λ
j
((
fA
)
j
−
μ
) = 0
.
(6)
Здесь векторзадержек
f
= (
f
1
, f
2
, . . . , f
n
)
вычислен в точке
z
∗
.
Если
λ
j
= 0
, то из соотношений (6) следует равенство
(
fA
)
j
=
μ
,
а иначе
(
fA
)
j
μ
. По определению матрицы маршрутов и из урав-
нения (1)
(
fA
)
j
=
ρ
(
L
j
, z
∗
)
. Полученные соотношения означают, что
все маршруты, применяемые произвольной
k
-й парой, являются крат-
чайшими (имеющими длину
μ
)
. Отсюда следует, что решение задачи
маршрутизации, отвечающее вектору потоков
z
∗
, равновесно, так как в
соответствии с определением доказана оптимальность маршрутизации
всех тяготеющих пар.
Эффективность равновесия.
На множестве допустимых маршру-
тизаций ведем отношение эквивалентности. Именно, маршрутизации
M
1
, M
2
(всей сети или только отдельной пары) эквивалентны, если
они приводят к одному и тому же вектору потоков
z
на линиях сети.
Класс эквивалентности маршрутизации
M
обозначим как
R
z
(
M
)
.
Для упрощения записи опустим индекс
z
, а множество применя-
емых
k
-й парой маршрутов
{
L
k
j
}
при маршрутизации
M
— обозна-
чим
M
k
.
Из доказательства теоремы 1 вытекает
Следствие 1.
Равновесной является всякая маршрутизация, кото-
рая эквивалентна равновесной маршрутизации.
Считаем, что в сети с потоками
z
может применяться произволь-
ная эквивалентная маршрутизация. Это предположение имеет место
в пакетных сетях, в которых управление передачей осуществляется с
помощью маршрутных таблиц [1]. Тогда время доставки продуктов
k
-й пары вычисляется по следующей формуле:
T
k
(
z
;
M
k
) = max
M
∈
R
z
(
M
k
)
max
L
j
k
∈
M
ρ
(
L
j
k
, z
)
, k
= 1
,
2
, . . . , K.
(7)
Подстановка в уравнение (7) равновесной маршрутизации дает зна-
чения критериев (7), совпадающие с длинами применяемых (кратчай-
ших) маршрутов (следствие 1).
Теорема 2.
Пусть все пары узлов графа сети являются тяготеющи-
ми и для любых попарно смежных ребер
k, l, m
выполнены неравен-
ства треугольника
f
k
(0)
f
l
(0) +
f
m
(0)
. Тогда равновесная маршру-
тизация Парето эффективна.
Доказательство.
Рассуждая от противного, найдем такую допусти-
мую маршрутизацию
M
=
{{
L
k
j
}
,
{
λ
k
j
}
, k
= 1
,
2
, . . . , K
}
, для которой
∀
k T
k
(
z
)
T
k
(
z
∗
)
.
(8)
80 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
