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

Предположим теперь, что пропускные способности каналов известны и требуется найти оптимальное распределение потоков в сети. Сначала необходимо рассмотреть распределение потоков и те ограничения, которым оно должно удовлетворять. Поток в канале li состоит из пакетов, идущих от множества источников ко множеству адресатов. Поскольку матрица требований определяет график, который должен идти от каждого источника s ко всем адресатам t, нужно указать распределение потоков по всей сети для каждого из (s,t) типов пакетов. Следовательно, для каждого канала необходимо найти индивидуальные потоки f(s,t,i), а полный поток в канале l _i есть сумма индивидуальных потоков f(s,t,i) от всех пар источник - адресат (s,t), протекающих через этот канал. Это трехпараметрическое пространство неотрицательных величин назовем "потоком" и будем обозначать символом f. Заметим, что индексы s и t пробегают множество узлов сети, а индекс i - множество ее каналов.

Поток f удовлетворяет двум видам ограничений, накладываемых матрицей требований и пропускными способностями каналов связи. Для каждого узла сети можно написать уравнение сохранения для каждого класса пакетов. Эти уравнения представляют собой линейные ограничения, в которых для каждого s и t разность между входящими и выходящими из выделенного узла потоками равна нулю (с учетом пакетов, поступающих извне и покидающих ее).

Если имеются два потока f₁ и f₂, удовлетворяющие всем ограничениям, то на их основании можно вычислить третий поток, также удовлетворяющий этим ограничениям, а именно, a f₁+(1-a )f₂, где 0£ a £ 1. Допустимые потоки образуют выпуклое множество, вершины которого (экстремальные потоки) представляют особый интерес.

Метод минимизации T на пространстве допустимых потоков, который описывается в общих чертах, известен под названием "метода девиации потока". При этом методе начав с некоторого допустимого потока с помощью частных производных в данной точке определяют градиент отклонения потока для уменьшения T. Затем определяют величину отклонения потока, при которой T будет наименьшим. Этот процесс повторяется до тех пор, пока изменения T на каждом шаге не станут достаточно малыми, что бывает вблизи оптимальной точки. Известно, что задача не имеет локальных оптимумов, и поэтому метод сходится к искомому глобальному оптимуму.

Ключевым моментом метода девиации потоков является способ определения "направления" отклонения потока. Для этого каждому каналу приписывается величина ¶ T/¶ l _i=m C_i/g (m C_i-l _ii)², которая может считаться "весом" этого канала. Эта величина характеризует влияние малого изменения потока в канале на среднюю задержку, т.е. "сопротивление" увеличению потока. Затем определяется экстремальный поток f₁, обладающий минимальным весом при заданном выборе весов. Если e₁ является начальным потоком, а e₂ - потоком, указывающим направление отклонения потока из e₁, то для определения величины отклонения необходимо исследовать все точки a e₁+(1-a )e₂, где 0£ a £ 1.

Поток f₁, который минимизирует T, является наилучшим решением, достижимым на первом шаге алгоритма девиации потока. На следующем шаге частные производные от T и экстремальный поток пересчитываются уже относительно точки f₂. Процесс продолжается до тех пор, пока изменения T не станут достаточно малыми.

Для определения начального потока целесообразно использовать веса алгоритма девиации потока, получаемые при нулевых значениях потоков, и по ним построить поток, соответствующий минимальным весам. Если случайно окажется, что этот поток удовлетворяет ограничениям на пропускные способности каналов, то поиск заканчивается. Если нет, можно уменьшить пропорционально все элементы матрицы требований так, чтобы потоки в каналах не превосходили их пропускных способностей. При этом получим допустимый поток, но он слишком мал, чтобы являться решением задачи оптимизации с заданной матрицей требований. На следующем шаге применяем алгоритм девиации потока для минимизации T с уменьшенной матрицей требований; после этого вновь увеличиваем матрицу требований настолько, чтобы получить максимально возможный поток в пределах заданных ограничений на пропускные способности каналов.

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