![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Компьютерные сети
|
16.01.2005
|
![]() |
![]() |
|||
3.4. Задача РП(распределение потоков). Имеется коммуникационная сеть: Задана структура сети G = (X,E), матрица Н =
и пропускные способности всех КС найти такой МП-поток F = задержка минимальна: Тср= 1/hå(frs/(mrs - frs) Rmin (3.6) при условии, что F = [frs] - МП поток, совместимый с матрицей Н и frs < mrs Л. Клейнрок получил условие оптимальности текущего потока F*= [frs*]:
3.4.1. Метод отклонения потоков: Алгоритм РП: Включает два этапа: 1) предварительный; 2) основной - состоит из однотипных итераций по оптимизации текущего потока. Предварительный этап состоит в нахождении начального допустимого потока. Основной этап (k+1) итерации: 1) Находим условные длины каналов или дуг: lrs = Tср = 2) Находим кратчайшие пути вданной метрике: пусть 3) Находим поток Vk= [vrsk] по кратчайшим путям, для чего используем специальный алгоритм. 4) Находим оценочные коэффициенты для старого и нового потоков:
bk= Условие оптимальности потока
5) Проверяем условие: если 6) Состовляем комбинацию нового и старого потоков:
Ищем такое l*, для которого Тср (F¢(l)) Rmin - любым методом одномерной оптимизации, например, Фибоначчи. 7) F(k+1) =(F¢(l*)) k=k+1 Rпереход к следующей итерации |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |