Основные задачи оптимизации ИС

Рассмотрим некоторые типовые варианты оптимизационных задач, связанных с топологическим проектированием ИС. Возможна следующая их классификация [2].

1. Выбор оптимальной пропускной способности (ВСП).

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

2. Распределение потока.

Дано: топология сети, потоки, пропускные способности каналов. Требуется: минимизировать Т по переменной «маршрут движения» при заданных ограничениях на потоки.

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

Дано: топология сети, потоки. Требуется: минимизировать по переменным «маршрут» и «пропускная способность» пр.и заданных ограничениях на поток и время задержки.

4. Определение оптимальной топологии сети.

Дано: характеристики трафика ИС. Требуется: минимизировать по переменным «топология», «маршрут» и «пропускная способность» при ограничениях на поток, задержки и топологию.

Рассмотрим задачу оптимизации пропускных способностей линий. Высокая пропускная способность линий приводит к увеличению затрат, а при малой происходят перегрузки и задержки сообщений. Соотношение между стоимостью и пропускной способностью линий имеет вид

,

где W - полная стоимость линий; W_i - стоимостный коэффициент для i-линии; C_i-пропускная способность i-линии.

Значения W_i неравные, потому что линии имеют разные длины. В частности, соотношение между стоимостью и пропускной способностью может быть задано степенным законом

Средняя задержка для й линии задается временем ожидания в очереди при допущениях, что длина сообщений имеет экспоненциальное распределение:

,

где — интенсивность потока сообщений в м канале; — средняя длина сообщений (в битах).

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

(16)

Искомые пропускные способности, которые минимизируют Т при постоянном W, определяются методом неопределенных множителей Лагранжа. Опуская соответствующие математические преобразования, приведем результат в готовом виде:

(17)

где — определяется выражением

Первое слагаемое , в правой части формулы для - пропуск­ная способность линии в режиме насыщения, а второе слагаемое - дополнительная пропускная способность этой линии.

Величина результирующей транзитной задержки при передаче по линиям с пропускными способностями задаваемыми выше­приведенными равенствами (43), определяется так:

(18)

где - сумма интенсивностей трафика по всем линиям.

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

К числу оптимизационных задач синтеза ИС относится задача распределения потоков. В предыдущей задаче выбирали пропуск­ные способности каналов при заданной конфигурации потоков. В данной задаче пропускные способности заданы, а потоки надо распределить так, чтобы минимизировать среднюю задержку Т. Предполагается, что все пропускные способности удовлетворяют требованиям трафика, а процедуры выбора пути фиксированы и однозначны.

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

В этом случае задача оптимального распределения потоков представляет собой минимизацию нелинейной функции Т по пото­кам при условиях выполнения закона сохранения потоков в каждом узле.

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

Доказывается, что при этих условиях и ограничениях Т есть вы­пуклая функция потоков, а множество реализуемых потоков пред­ставляется математической моделью в виде выпуклого многогран­ника в -мерном пространстве параметров потоков. Рассматривае­мая задача решается симплекс-методом, который упоминался выше. Если она имеет реализуемое решение, то любой локальный минимум является глобальным минимумом для Т.

Часто при оптимизации ИС используется метод отклонения по­тока (ОП), суть которого заключается в нахождении стоимости се­ти для значений «длин» х ребер. Значения длин ребер задаются выражением

(19)

такие «длины» или «стоимостные коэффициенты», соответствующие им, используют для форму­лировки задачи отыскания потоков по кратчайшим путям и выяс­нения вопроса о том, какая часть исходного потока должна быть отклонена. Процесс решения циклически повторяется до тех пор, пока не будут получены приемлемые значения . Оптимальный ал­горитм ОП дает минимальное значение Т - среднюю задержку сообщения в сети.