Моделирование алгоритма маршрутизации

4.2 Задача распределения потока

В качестве исходного выражения для характеристики Т здесь используется формула:

,

(4.5)

представляющая среднюю задержку сообщения, проходящего по сети. Все вопросы, связанные с массовым обслуживанием, учтены и отражены этим выражением; остается лишь задача оптимизации потоков, которая входит в теорию потоков в сетях. Теорема о максимальном потоке и минимальном сечении, которая гласит, что поток в канале не может превышать максимальной пропускной способности, является основой, на которой строится эта теория. В данной задаче распределения потока, так же как и в задаче распределения потоков различных грузов, требуется минимизировать нелинейную функцию Т по потокам {i}, чтобы удовлетворялись внешние требования к потокам jk Минимизация проводится в предположении, что пропускные способности заданы. Кроме того, нужно не нарушить обычный закон сохранения потоков. Согласно этому закону, суммарный трафик jk, поступающий в узел n, равен суммарному трафику jk, выходящему из узла n, за исключением случая n=j (узел n является узлом-источником) или случая n=k (узел n является узлом назначения). Далее, имеется ограничение на пропускную способность каждого канала, состоящее в том, что поток λi в канале i должен быть неотрицательным и меньшим пропускной способности, т. е. 0 λi < C. Это ограничение показывает, что характеристика Т обладает свойством безграничного возрастания при стремлении какого-либо потока к пропускной способности соответствующего канала (т. е. при стремлении множества потоков в сети к верхней границе для этих потоков, определенной ограничениями на пропускные способности). Это означает, что характеристика Т включает дополнительное ограничение на пропускную способность как функцию штрафа. Это важное свойство обеспечивает реализуемость решения при использовании любого метода минимизации, который представляется в виде последовательности «небольших шагов» и на начальном шаге оперирует с реализуемым решением. Таким образом, если начать с реализуемого решения, то можно пренебречь ограничением на пропускную способность, и вследствие этого задача, которая выглядит как задача оптимизации с ограничением, фактически будет представлять собой задачу без ограничений по оптимизации потоков различных грузов.

Ниже рассматривается метод, который дает точное решение задачи оптимального распределения потока, которое удобно использовать при численном расчете. Начнем с рассмотрения выражения (4.5) для T. Заметим, что эта характеристика является разделимой в том смысле, что она выражается просто как сумма слагаемых, каждое из которых зависит лишь от потока в одном канале. Кроме того, из (4.5) следует, что

, i = 1, 2, …, M.

(4.6)

Отсюда видно, что T/(λi) > 0 при всех i; аналогичные рассмотрения показывают, что T/(λi)2 > 0 (оба эти неравенства справедливы при удовлетворении ограничений на пропускные способности). Таким образом, можно сделать вывод, что Т выпуклая функция потоков. Кроме того, множество реализуемых потоков само является выпуклым многогранником. Итак, если задача имеет реализуемое решение, то любой локальный минимум является глобальным минимумом для Т. Следовательно, любой метод отыскания локального минимума может быть использован при решении задачи поиска глобального минимума.

4.3 Метод отклонения потока

Метод, который применяется здесь, называется методом отклонения потока, он предназначен для поиска глобального минимума. Уясним вначале такое важное понятие как поток по кратчайшим путям. Предположим, что мы имеем сеть, каждый канал которой имеет надписанную на нем длину li,. В такой сети, естественно, можно найти кратчайший путь между узлом-источником j и узлом назначения k и пытаться посылать требуемый поток jk по этому пути. Если поступить так для всех пар (j,k), то в результате получится поток, который называется потоком по кратчайшим путям. Существует ряд хорошо известных и эффективных алгоритмов отыскания множества кратчайших путей jk.

4.3.1 Алгоритм Флойда отыскания множества кратчайших путей

Рассмотрим сеть с N узлами. Пусть D0=(djk) - матрица порядка N*N, элемент которой djk дает длину канала (которая при этом вычислении считается заданной), прямо соединяющего узел j с узлом k, если такого канала нет, то этот элемент равен бесконечности (кроме того, djj=0). При рассмотрении любого пути jk соединяющего узел j с узлом k, будем обозначать через l(jk) его длину (т. е. сумму длин каналов). Задача состоит в вычислении матрицы Н=(hjk) порядка N*N, где hjk - длина кратчайшего пути, соединяющего узел j и узел k; итак, H- матрица кратчайших путей, представляющая для нас интерес. Алгоритм кратчайших путей Флойда начинает с матрицы расстояний D0 и итеративно изменяет ее, проходя последовательность из N матриц (на n-м шаге матрица обозначается через Dn); в конце он приходит к матрице кратчайших путей DN=H. Если начать с n=0 и djk(0)=djk, то матрица Dn+1 получится из Dn с помощью итерации (7).

(4.7)

Найдя D1, мы замечаем, что djk (1) (элемент j, k в матрице D1) представляет собой длину кратчайшего пути из узла j в узел k при условии, что допускаются лишь пути с узлом 1 в качестве промежуточного. Аналогично после отыскания Dn на n-й итерации получим, что djk(n) - кратчайшее расстояние от узла j к узлу k по путям, в которых промежуточные узлы принадлежат множеству {1, 2, ..., n}.

Таким образом, дойдя до N-ой итерации, получаем искомый результат djk (N) = hjk. Весь алгоритм требует около N3 сложений и вычитаний и N3 сравнений.

Cущество метода определения  потока связано с сопоставлением «длины» с i-м ребром, величина которого дается равенством

(4.8)

Когда поток в канале равен λi. Ясно, что это линейная скорость возрастания Т при бесконечно малом увеличении потока в i-м канале. Такие «длины», или «стоимостные коэффициенты», можно затем использовать для формулировки задачи отыскания потоков по кратчайшим маршрутам, а получающиеся пути представляют собой самые дешевые (т.е. самые лучшие для снижения T) пути, к которым может быть отклонена некоторая часть потока. Вопрос теперь в том, какая часть исходного потока должна быть отклонена к этим новым путям. После того как она будет определена, можно повторить процесс, опять находя новые длины на основе обновленных потоков, решая новую задачу отыскания потоков по кратчайшим маршрутам, определяя соответствующую отклоняемую часть потока и т.д. Эта итеративная процедура продолжается до тех пор, пока не будет получена приемлемая характеристика.

Приведем конкретный алгоритм, который использует эти идеи. Для этого введем вектор потока на n-й итерации алгоритма:

(4.9)

i-я компонента  которого представляет собой полный поток по i-му каналу на n-й итерации. Будем считать, что начальный поток f(0) является реализуемым. Теперь можно представить следующий алгоритм, который используется при нахождении реализуемого начального потока (вернее, при нахождении данного потока использовались шаги 2, 4, 7 и 8).

4.3.2 Оптимальный алгоритм отыскания потока для выбора маршрутов

Шаг 1.	Положить n=0.
Шаг 2.	Для каждого i=1, 2,..., М найти .
Шаг 3.	Найти n - добавочный стоимостный коэффициент для этого потока. .
Шаг 4.	Решить задачу отыскания потоков по кратчайшим маршрутам, используя длины li. Пусть i - результирующий поток по i-му каналу, который получается, если весь поток направляется по этим кратчайшим путям. Обозначим вектор потоков через = (1,2, ..., M).
Шаг 5.	Найти bn - добавочный стоимостный коэффициент для потока по кратчайшему маршруту, bn = li i.
Шаг 6.	(Правило остановки.) Если n - bn < , где >0, надлежащим образом выбранный допуск, то STOP. В противном случае перейти к шагу 7.
Шаг 7.	Найти такое значение a из интервала 0a1, для которого поток (1 - a) f(n)+a минимизирует Т. Пусть это оптимальное значение обозначается через a. Оптимальное значение a можно найти с помощью любого подходящего метода поиска (например, с помощью метода Фибоначчи [107]).
Шаг 8.	(Отклонение потока) Положить f(n+1) = (l - a) f(n) + a.
Шаг 9.	Положить n = n + 1. Перейти к шагу 2.

Обратимся теперь к вопросу отыскания реализуемого начального потока f(0). Еще раз предположим, что задан внешний поток :

(4.10)

Введем масштабный коэффициент h так, чтобы h было равно интенсивности потока, с которым мы имеем дело при данном значении h. Опишем теперь алгоритм отыскания реализуемого начального потока. Напомним, что данный алгоритм использовался в алгоритме отыскания потоков, направляемых фиксированной процедурой выбора маршрутов.

4.3.3 Алгоритм отыскания реализуемого начального потока

Шаг 1.	Положить h0=1 и считать, что f(0) - решение задачи отыскания потоков по кратчайшим маршрутам в сети с длинами li = 1/Ci [заметим, что эти длины совпадают с длиной, представленной формулой (8) при нулевом потоке]. На этом шаге весь поток h0 направляется по сети; обозначим через i(0)/ поток в i-м канале на этом этапе. Положить n=0.
Шаг 2.	Пусть . Если hn < 1, то положить f(0) = f(n)/hn; STOP (это реализуемый начальный поток). Если hn больше 1, то положить hn+1 = hn[1-1(1n)]/n, где 1 - надлежащий параметр точности, такой, что 0<1<l.
Шаг 3.	Положить g(n+1) = (hn+1/hn)f(n). Это реализуемый поток различных грузов, который несет полный трафик с интенсивностью hn+1 < 1.
Шаг 4.	Теперь провести операцию отклонения потока на потоке g(n+1); это значит, что нужно выполнить шаги 2, 4, 7 и 8 алгоритма ОП, найти (поток по кратчайшим маршрутам с длинами, основанными на потоке g(n+1)) и оптимальное значение (т.е. a), такие, чтобы поток f(n+i) = (l-a) g(n+1) +a минимизировал T. Если n = 0, то перейти к шагу 6; в остальных случаях перейти к шагу 5.
Шаг 5.	Если и , где и - выбранные надлежащим образом положительные допуски, то STOP; задача не имеет реализуемого решения при допусках и . В остальных случаях перейти к шагу 6.
Шаг 6.	Положить n = n + 1 и перейти к шагу 2.

Эта процедура либо находит реализуемый начальный поток, либо объясняет, что задача не имеет реализуемого решения в пределах выбранных допусков.

Метод отыскания потока обеспечивает оптимальный выбор маршрутов для трафика в междугородной сети и является сравнительно эффективным с точки зрения вычислений.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ В

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ В

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ Г

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ Д

 

 

ПРИЛОЖЕНИЕ А

 

 

 

Рисунок 1.2 – Существующая междугородняя телефонная сеть Республики