litceysel.ru
добавить свой файл
1 2 3
ОБ ОПТИМАЛЬНОМ ВЫБОРЕ ПРОПУСКНЫХ СПОСОБНОСТЕЙ


КАНАЛОВ И УЗЛОВ СЕТЕЙ ПЕРЕДАЧИ ДАННЫХ


В.М. Гостев, Р.Ф. Хабибуллин


Одна из классических постановок задачи оптимального выбора пропускных способностей каналов сети передачи данных [1] состоит в минимизации средней задержки пакета при передаче по каналам связи при условии, что суммарная стоимость использования (аренды) каналов не превосходит заданной величины. В предположении, что функции стоимости аренды каналов передачи данных линейны, в [1] получено точное решение рассматриваемой задачи в аналитической форме. В этом решении оптимальная пропускная способность каждого канала определяется отдельно для каждого из двух его направлений передачи данных в зависимости от интенсивности потоков на этих направлениях. Поэтому, если на некотором канале интенсивности потоков на двух его направлениях передачи данных окажутся различными, то на этом канале оптимальные пропускные способности для обоих направлений передачи данных также будут различны. В современных условиях, когда в компьютерной сети выделяются специализированные серверы обработки и серверы баз данных, случай несимметричных потоков на каналах типичен. В то же время пропускные способности каналов в обоих направлениях передачи данных, как правило, должны быть одинаковыми.

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

Задача оптимального выбора пропускных способностей узлов коммутации сетей передачи данных (СПД) в известной литературе (см., например, [1 - 6]) не рассматривалась. По-видимому, это можно объяснить тем, что критичными компонентами СПД считались каналы передачи данных с относительно низкими пропускными способностями, в то время как процессоры обработки данных в узлах коммутации обладали относительно более высокой скоростью. В современных условиях, когда имеются высокоскоростные (например, оптоволоконные) каналы, неоптимальный выбор производительности узлов коммутации СПД может оказать существенное влияние на эффективность сети.


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


Задача оптимального выбора пропускных способностей каналов передачи данных для случая несимметричных потоков


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

Пусть, далее, для всех пар узлов сети заданы средние интенсивности потоков данных, порожденных внешними обращениями к СПД. Обозначим через p суммарную интенсивность этих потоков в бит/сек. Предполагается, что в СПД используется фиксированная однопутевая маршрутизация, т.е. пакеты от одного УК до другого проходят по одному и тому же заранее выбранному фиксированному маршруту. Задание маршрутов передачи пакетов для всех пар узлов источник-адресат при заданной топологии СПД однозначно определяет распределение потоков данных по сети, т.е. средние интенсивности потоков данных через все компоненты сети - как узлы коммутации, так и каналы передачи данных.

Обозначим через и средние интенсивности потоков (в бит/сек), проходящих по каналу передачи данных в обоих направлениях, , и через - средний размер сообщения. Как и в [1, 2] будем рассматривать каждый КПД как систему массового обслуживания типа М/М/1, т.е. для упрощения задачи предполагается, что входной поток на каждое из двух направлений передачи данных канала пуассоновский, а время передачи сообщения по каналу с пропускной способностью есть экспоненциально распределенная случайная величина со средним значением . Обозначим для . Считаем не ограничивая общности, что все для .


Тогда при выборе пропускных способностей каналов , для , средняя задержка пакета на каналах передачи данных при передаче по сети [1] при введенных обозначениях выразится величиной

. (1)

На это выражение опираются многочисленные исследования и методы оптимизации проектирования СПД. Допустимость сделанных предположений и полученных на их основе приближений, приемлемость полученных результатов для инженерных расчетов были неоднократно проверены путем моделирования и сопоставления с обширным фактическим материалом многими исследователями (см., например, [1 - 6]).

Сформулируем задачу оптимального выбора пропускных способностей каналов передачи данных.

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

, (2)

где , для всех .

Пусть допустимые затраты на аренду каналов передачи данных составляют величину . Учитывая, что и являются константами, целевую функцию (1) задачи можно определить следующим образом:

, (3)

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

, для всех ,

и минимизируют функцию (3).

Очевидно, что для обеспечения выполнения условий , , величина допустимых затрат при заданных функциях стоимости (2) должна быть больше величины

.

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

.


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

,

где - множитель Лагранжа. Дифференцируя функцию по , , и приравнивая частные производные нулю, получаем:



для всех или, что то же самое,

. (4)

Дифференцируя по и приравнивая нулю, получаем

. (5)

Согласно правилу множителей Лагранжа в данном случае решение системы уравнений (4), (5) является решением поставленной задачи оптимизации. Эта система состоит из уравнений с неизвестными , , и . Уравнения (4) являются уравнениями четвертой степени относительно , и их не удается разрешить аналитически в явном виде. Поэтому для решения системы уравнений (4), (5) применим численный метод.



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


Обозначим функции, стоящие в левых частях уравнений (4), через для , т.е.

,

а функцию в левой части уравнения (5) через , т.е.

.

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

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


для и для . (6)

Определим для произвольного и

. (7)

У т в е р ж д е н и е 1. Для произвольного фиксированного выполняется

(8)

для всех .

Д о к а з а т е л ь с т в о. Считая для определенности, что и, следовательно, , имеем



= .

Итак, . Отсюда, учитывая (6), и поскольку строго монотонно убывает по , следует, что для всех выполняется (8).


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

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

У т в е р ж д е н и е 2. Если для некоторых , выполняется , то для всех справедливо .


Д о к а з а т е л ь с т в о. Если предположить обратное, т.е. что для некоторого выполняется , тогда из (4) имеем



,

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

Определим

.

У т в е р ж д е н и е 3. Имеет место .

Д о к а з а т е л ь с т в о. Из (7) следует

, . (9)

Для имеем

(10)


.

Если предположить, что в противоположность доказываемому выполняется , то согласно утверждению 2 имеем

для всех ,

а согласно утверждению 1 , т.е. , следовательно выполняется

.

Полученное противоречие показывает, что предположение о том, что , неверно, и это завершает доказательство утверждения 3.

Согласно утверждению 3 имеет место , и для нахождения можно применить метод дихотомии. Выберем среднюю точку интервала локализации и, решив систему (4) для этого значения , получим . Если , то это означает, что , т.е. . Если же , то имеет место , т.е. . Таким образом, длина отрезка локализации уменьшается вдвое. Процесс продолжается до получения с необходимой точностью.



следующая страница >>