<< prev | ^up^ | next >>

3.8. Нахождение максимального потока в вычислительной сети при отказах.

Важной задачей, которая решается при проектировании вычислительных сетей, является задача анализа показателей её живучести. Таким показателем живучести предлагается использовать величину максимального внешнего потока, который передаётся в сети при отказах её элементов.

Автором предложен оригинальный метод нахождения максимального многопродуктового потока в сети при ограничении на среднее время задержки в доставке информации [20], который используется при последующем решении задачи анализа живучести сетей.

3.8.1.Постановка и математическая модель задачи.

Задана распределённая вычислительная сеть (РВС) в виде орграфа  - множество узлов сети, множество её дуг (каналов) связи (КС), каждый канал характеризируется своей пропускной способностью ,, -из заданного набора. Задана матрица требований  интенсивностей передачи пакетов между узлами и .

Допустим, что при помощи известного алгоритма РП  найден МП-поток , соответствующий данной матрице H, для которого средняя задержка в передаче пакетов в сети между любой парой узлов  удовлетворяет ограничению

                                                                   (3.33)

или вероятность своевременной доставки будет удовлетворять условию

7                                                                              (3.34)

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

Допустим, что каналы связи сети ненадёжны, и обозначим вероятность безотказной работы канала связи (r,s) через .

Будем считать вероятность отказов каналов связи статистически независимыми случайными величинами. Отказы узлов  на данном этапе не будем брать во внимание, считая узлы абсолютно надёжными.

Допустим, что отказал канал(r,s). Вероятность этого события . Нужно найти такое распределение потоков в каналах , а также  величины передаваемых внешних трафиков , при которых обеспечивается передача максимального потока через сеть за среднее время  T_cp, который удовлетворяет условию .

Математическая модель этой задачи такова: найти такую матрицу   и соответствующий вектор МП-потока , для которых

                                                                                               (3.35)

при условиях                               (3.36)

                                                                                                   (3.37)

3.8.2.  Анализ и исследование оптимального решения.

Допустим, что найдено оптимальное решение задачи(3.35)-(3.37), которое обозначим через   и .Оно имеет важные свойства, которые устанавливаются в следующих теоремах [20].

Теорема 1.

Поток - это поток по кратчайшим путям в метрике

                                                                                                         (3.38)

Теорема 2.

Если в оптимальном решении пакеты требований  доминируют при передаче в сети пакеты  (т.е.  передаются, а  не передаются или передаются не полностью), то для них выполняется соотношение

                                                                                                                    (3.39)

 где  длина кратчайшего пути передачи пакетов    соответственно в метрике, определённой в (3.38).

Доказательство теоремы 1.

Допустим, что условие  теоремы 1 не выполняется для требования , т.е. она передаётся по пути , для которого , где  - длина кратчайшего пути в метрике  (3.38).  Изменим тогда  маршрут передачи только для этого  требования с  на , не меняя других.

Обозначим через  - старый поток, а через  новый поток при смене маршрута для требования  на . Рассмотрим  как некоторую вариацию  потока и найдём прирост критерия ограничения при этом:

                        (3.40)

Так как составляющие потока на каналах  уменьшились на величину , а на каналах  они увеличились на величину , то

                                 (3.41)

Тогда

          =

       (3.42)

Поэтому, в силу (3.39)

                                (3.43)

Значит, если изменить маршрут для требования на ,мы уменьшим  величину критерия и тогда

                  .

 Это означает, что при распределении потоков появляется резерв по общей пропускной способности и можно увеличить величину потока одного из требований, например   на некоторую величину без нарушения ограничения (3.36). Но это противоречит допущению, что поток   максимальный. Таким образом теорема 1 доказана.

Доказательство теоремы 2.

Итак, допустим, что есть два требования (i,j) и (r,t) с величиной  и , такие, что

                                                           (3.44 )

причем   , в частности .Пусть при этом . Увеличим значение потока от требования  на , а   уменьшим на , и найдём вариацию  :

  (3.45)

Но из (3.45) вытекает, что при таком изменении (замене одного требования на другое) общая задержка  уменьшится на величину  без изменения суммарной величины потока .Это позволяет увеличивать общую величину потока через сеть  за счёт созданного резерва по общей пропускной способности. Таким образом, поток  не максимальный МП-поток через сеть, так как он может быть увеличен. Таким образом установлена справедливость условия теоремы 2.

Заметим, что в силу линейности (а значит и выпуклости целевой функции (3.35), а также выпуклости ограничения (3.36) по переменным , данные условия будут не только необходимыми, но и достаточными.

Рассмотрим более общую задачу о нахождении максимального взвешенного потока через сеть с критерием

                                                     (3.46)

где  - вес (ценность) сообщений от узла i к узлу j. В   этом случае условия оптимальности  вида (2.21) примут такой вид:

                                             (3.47)

 где знаком > обозначается доминирование потока требований  над потоком ,т.е. первоочередная их передача.

Указанные условия оптимальности в теоремах 1,2 используются для построения алгоритма решения задачи (3.35)-(3.37).

Будем рассматривать два возможных случая.

Случай 1- известны пути передачи всех типов сообщений в сети без отказов.

Случай 2 - кратчайшие пути неизвестны.

3.8.3. Алгоритмы нахождения максимального МП-потока через сеть.

Алгоритм 4 (случай 1).

Итак, пусть отказала линия связи (r,s).

1. Находим все требования (сообщения),кратчайшие пути для которых содержат линию связи (r,s). Обозначим их множество через . Обозначим через  оставшееся множество  требований.

2.Прекращаем передачу сообщений для всех пар  и вычисляем величину оставшегося  потока через сеть:

3.Находим условные длины путей  в новой метрике: 

                       

4. Проранжируем все требования  в порядке возрастания величин :

           

5.Находим новые кратчайшие длины путей для всех требований  и проранжируем их в порядке уменьшения.

6.Проверяем условие необходимости обмена:

 т.е.                                                 (3.48)

Если условие (3.42) выполняется, то на шаг 7, иначе на шаг 8.

7.Выполняем следующую процедуру замены требования  на требование  

7.1.Пусть .Тогда полностью заменяем поток требования  на .

7.2.Пересчитываем трафики во всех каналах (составляющие МП-потока  вызванные такой заменой).

7.3.Определяем

                        

 Переходим на шаг 3 (k+1)-й итерации. Если , то приравниваем величину передаваемой части потока требования (l,t),равной .Заменяем поток требования  на  и на шаг 7.2.Выполнив шаг 7.2 и 7.3, переходим на шаг 7.4.

7.4.Вычисляем .Если , то увеличиваем величину передаваемого требования  до значения .Вычисляем новый МП-поток  и проверяем выполнение условия                     (3.49).

 Если (3.49) выполняется, то конец итерации и переходим на шаг 3 (k+1)-й итерации. Иначе уменьшаем величину потока требования  до такого значения, при котором достигается строгое выполнение условия . Далее переходим на шаг 8.

8. Конец работы алгоритма.

Указанные итерации (процедуру обмена требований)выполняем до тех пор, пока условие(3.48) не перестанет выполняться.

Алгоритм А5  (случай 2). Рассмотрим теперь алгоритм для общего случая, когда не известны маршруты .

Итак, допустим, что отказала линия связи .

1. Приравниваем .

2. Находим начальную метрику

                         

3.Находим кратчайшие пути и их условные длины в метрике .

4.Проранжируем все требования (i,j) в порядке увеличения условных длин:

         

   5.Вибираем первое требование  и передаем весь поток величиной  по пути .

   6.вычисляем составляющие МП -потока F(1):

                                 (3.50)

   7.Вычисляем . Если , то конец, иначе на шаг 8.

8.

9.  и переходим к (k+1) -й итерации.

Описание (k+1)-ой итерации.

Пусть проведено  k итераций, в результате которых построен МП-поток в сети   с величиной .Обозначим через  - множество индексов требований, поток от который уже распределён в сети. - оставшееся множество  требований.

 

1.Находим новую метрику

                                 

2. Корректируем (или перевычисляем) длины кратчайших путей для всех требований  с учётом изменения составляющих МП-потока.

3. Проранжируем все требования  по возрастанию :

        

4. Выбираем требование  с величиной .

5.Направляем поток требования  по пути  и вычисляем составляющие нового МП-потока:

                   

6. Проверяем условие  Если да, то на шаг 8, иначе на шаг 7.

7. Уменьшаем величину  до такого значения , что

                

  где - заданный резерв до насыщения по пропускной способности и переходим на шаг 5,приравнивая

8.Проверяем условие .Если да, то конец итерации, . k=k+1, переход на шаг 1 (k+1)-й  итерации. Иначе на шаг 9.

9. Уменьшаем значение  до такой величины , при которой

10.  Конец работы алгоритма.