Проектирование реляционных баз данных. Ковалев А.В - 28 стр.

      2.4.3. Метод девиации потока

        Предположим теперь, что пропускные способности каналов известны и требуется найти
оптимальное распределение потоков в сети. Сначала необходимо рассмотреть распределение
потоков и те ограничения, которым оно должно удовлетворять. Поток в канале li состоит из
пакетов, идущих от множества источников ко множеству адресатов. Поскольку матрица требо-
ваний определяет график, который должен идти от каждого источника s ко всем адресатам t,
нужно указать распределение потоков по всей сети для каждого из (s,t) типов пакетов. Следова-
тельно, для каждого канала необходимо найти индивидуальные потоки f(s,t,i), а полный поток в
канале λi есть сумма индивидуальных потоков f(s,t,i) от всех пар источник - адресат (s,t), проте-
кающих через этот канал. Это трехпараметрическое пространство неотрицательных величин
назовем "потоком" и будем обозначать символом f. Заметим, что индексы s и t пробегают мно-
жество узлов сети, а индекс i - множество ее каналов.
        Поток f удовлетворяет двум видам ограничений, накладываемых матрицей требований и
пропускными способностями каналов связи. Для каждого узла сети можно написать уравнение
сохранения для каждого класса пакетов. Эти уравнения представляют собой линейные ограни-
чения, в которых для каждого s и t разность между входящими и выходящими из выделенного
узла потоками равна нулю (с учетом пакетов, поступающих извне и покидающих ее).
        Если имеются два потока f1 и f2, удовлетворяющие всем ограничениям, то на их основа-
нии можно вычислить третий поток, также удовлетворяющий этим ограничениям, а именно,
αf1+(1-α)f2, где 0≤α≤1. Допустимые потоки образуют выпуклое множество, вершины которого
(экстремальные потоки) представляют особый интерес.
        Метод минимизации T на пространстве допустимых потоков, который описывается в
общих чертах, известен под названием "метода девиации потока". При этом методе начав с не-
которого допустимого потока с помощью частных производных в данной точке определяют
градиент отклонения потока для уменьшения T. Затем определяют величину отклонения пото-
ка, при которой T будет наименьшим. Этот процесс повторяется до тех пор, пока изменения T
на каждом шаге не станут достаточно малыми, что бывает вблизи оптимальной точки. Извест-
но, что задача не имеет локальных оптимумов, и поэтому метод сходится к искомому глобаль-
ному оптимуму.
        Ключевым моментом метода девиации потоков является способ определения "направле-
ния" отклонения потока. Для этого каждому каналу приписывается величина ∂T/∂λi=µCi/γ(µCi-
λii)2, которая может считаться "весом" этого канала. Эта величина характеризует влияние мало-
го изменения потока в канале на среднюю задержку, т.е. "сопротивление" увеличению потока.
Затем определяется экстремальный поток f1, обладающий минимальным весом при заданном
выборе весов. Если e1 является начальным потоком, а e2 - потоком, указывающим направление
отклонения потока из e1, то для определения величины отклонения необходимо исследовать все
точки αe1+(1-α)e2, где 0≤α≤1.
        Поток f1, который минимизирует T, является наилучшим решением, достижимым на пер-
вом шаге алгоритма девиации потока. На следующем шаге частные производные от T и экстре-
мальный поток пересчитываются уже относительно точки f2. Процесс продолжается до тех пор,
пока изменения T не станут достаточно малыми.
        Для определения начального потока целесообразно использовать веса алгоритма девиа-
ции потока, получаемые при нулевых значениях потоков, и по ним построить поток, соответст-
вующий минимальным весам. Если случайно окажется, что этот поток удовлетворяет ограни-
чениям на пропускные способности каналов, то поиск заканчивается. Если нет, можно умень-
шить пропорционально все элементы матрицы требований так, чтобы потоки в каналах не пре-
восходили их пропускных способностей. При этом получим допустимый поток, но он слишком
мал, чтобы являться решением задачи оптимизации с заданной матрицей требований. На сле-
дующем шаге применяем алгоритм девиации потока для минимизации T с уменьшенной матри-

                                                  30