МАТЕМАТИКА
УДК 621.865.8-5.001.5
Н. С. В а с и л ь е в
ЗАДАЧА О КРАТЧАЙШИХ МАРШРУТАХ В СЕТЯХ
С ПЕРЕМЕННОЙ МЕТРИКОЙ
Решена задача поиска кратчайших маршрутов в сетях с перемен-
ной метрикой. Обоснована сходимость алгоритмов, уравнивающих
длины выбираемых маршрутов. Доказана устойчивость решения.
Создание эффективных систем управления потоками в транспорт-
ных сетях (ТС), например, в пакетных телекоммуникационных систе-
мах, основано на моделях сетей с переменной метрикой ([1–3]). В
работе [1] отмечено, что даже в случае однопродуктовой сети имеет-
ся обратная связь между потоками и задержкой в передаче пакетов.
(Суммарная задержка — это метрика сети.)
Игнорирование этой зависимости не позволило устойчиво упра-
влять маршрутизацией (М) тем более многопродуктовых ТС. Соответ-
ствующие сетевые протоколы порождали колебательные процессы в
сетях несмотря на то, что при решении задачи М применяемая метрика
изменялась при переходе от одной тяготеющей пары абонентов к дру-
гой [1]. (Эта метрика фиксировалась в процессе поиска кратчайших
маршрутов (КМ) соединения каждой тяготеющей пары в отдельности.)
Свойства сетей с переменной метрикой изучались в работах [2,
3] в связи с поиском равновесной М глобальной пакетной сети, при
которой все пары абонентов передавали бы свои сообщения по КМ в
метрике, отвечающей искомому равновесию. На базе разработанных
методов проведены вычислительные эксперименты с ТС Интернет [4].
Построение, обоснование сходимости этих алгоритмов, а также
устойчивости получаемого решения базируются на свойствах задачи
поиска КМ в однопродуктовой сети с переменной метрикой. Pешению
этой задачи посвящена настоящая статья.
Математическая модель ТС.
Топологию ТС будем представлять
в виде связного неориентированного графа
Γ
= (
U, V
)
, вдоль ребер
l
2
V, l
= 1
,
2
, . . ., n
, которого расположены каналы (линии) передачи
продуктов, а в узлах
u
2
U
размещены “источники” и “стоки” переда-
ваемых потоков. Доставка продуктов каждой
k
-й пары источник–сток,
k
= 1
,
2
, . . . , K
, осуществляется по одному или нескольким маршру-
там графа сети
{
L
k
j
}
, соединяющим эти узлы. Входные потоки
λ
k
=
λ
k
0
70
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 1
