6.2.2 Оптимизация пропускной способности и выбор маршрутов

Простое аналитическое выражение (6.1), полученное в разделе 6.2.1 для оценки времени задержки пакетов, эффективно используется для решения различных оптимизационных задач, важных при проектировании базовой сети передачи данных. К числу таких задач относятся оптимизация пропускной способности каналов, выбор маршрутов и синтез топологической структуры сети.

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

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

при ограничении , где - заданная пропускная способность канала. Легко видеть, что

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

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

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

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

Решение этой задачи можно получить методом множителей Лагранжа. Составим функцию Лагранжа

Дифференцируя (6.7), получаем систему уравнений МП

решение которой дает искомые значения в виде

Для определения множителя умножим равенство (6.8) на просуммируем по и после преобразований получим

Подставляя последнее равенство в (6.8), имеем окончательно

Минимальная средняя задержка сети, пропускные способности каналов в которой выбраны оптимально, имеет вид

и определяется путем подстановки значения С в формулу (6.1).

Легко сформулировать и двойственную задачу отыскания вектора С, минимизирующего стоимость сети при ограничении на время задержки,

при условии

Снова используя для решения задачи (6.9), множителей Лагранжа, получаем:

где

Описанные задачи выбора потоков и определения оптимальных пропускных способностей каналов решались в предположении, что топологическая структура сети задана. Однако на практике при проектировании сети передачи данных топологическая структура сети неизвестна и подлежит выбору. Таким образом, проектировщик сети сталкивается со сложной комбинаторной проблемой совместного решения задач синтеза топологической структуры сети, выбора маршрутов и пропускной способности. Для решения этой проблемы обычно привлекаются численные методы [56,57,83,85,115], описание которых будет дано в главе 8.