поступают в узлы-источники, разделяются в них на маршрутные по-
токи величины
{
λ
k
j
}
и по маршрутам
{
L
k
j
}
передаются в соответству-
ющие узлы-стоки, из которых покидают ТС. Функционирование сети
происходит с задержками
f
l
(
z
l
)
на линиях сети
l
= 1
,
2
, . . . , n
, завися-
щими от величин потоков
z
l
.
Например, в пакетных сетях передачи данных величина задержки
всякого пакета на любой линии складывается из времени определения
направления дальнейшей передачи (с помощью маршрутной табли-
цы), времени ожидания в очереди и собственно из времени пересылки
пакета по этой линии связи в следующий (транзитный) узел сети.
Определение функций задержек составляет самостоятельную задачу
(см. [1]).
Время доставки продуктов вдоль маршрута
L
(или длина маршру-
та) равно сумме задержек
ρ
f
(
L, z
) =
X
l
2
L
f
l
(
z
l
)
.
(1)
Это — метрика сети. Индекс
f
в обозначении метрики будем опускать,
считая, что векторная функция
f
= (
f
1
, f
2
, . . . , f
n
)
зафиксирована. Ме-
трика есть время передачи сообщения, а все потоки — интенсивности
передачи, измеряемые в одинаковых единицах. По смыслу введенных
обозначений для всех допустимых значений индексов
k, l
должны вы-
полняться балансовые соотношения
J
k
X
j
=1
λ
k
j
=
λ
k
,
X
j,k
:
l
2
L
k
j
λ
k
j
=
z
l
.
(2)
Через
z
l
в (2) обозначен суммарный поток по
l
-му каналу. В любой
ТС пропускные способности всех линий передачи ограничены:
z
l
6
ˉ
z
l
, l
= 1
,
2
, . . . , n.
(3)
Под допустимой маршрутизацией сети (для
k
-й тяготеющей пары)
будем понимать совокупность маршрутов
{
L
k
j
}
и маршрутных потоков
{
λ
k
j
}
(интенсивностей передачи) такую, что выполняются соотноше-
ния (2), (3) и
ρ
(
L
k
j
, z
)
<
∞
.
Выбор допустимой маршрутизации однозначно задает вектор до-
пустимых потоков по линиям ТС
z
= (
z
1
, z
2
, . . . , z
n
)
.
Любая
k
-я тяготеющая пара “заинтересована” в уменьшении вре-
мен передачи своих продуктов, равных длинам маршрутов
{
L
k
j
}
. По-
этому, располагая векторным критерием качества маршрутизации
F
k
= (
ρ
(
L
k
1
, z
)
, . . . , ρ
(
L
k
J
k
, z
))
, k
= 1
,
2
, . . . , K,
(4)
всякая пара стремится его минимизировать (в векторном смысле) за
счет выбора допустимой маршрутизации.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 1
71
