Оптимизация размещения абонентов по сети передачи данных

В статье представлен метод оптимизации размещения абонентов по сети передачи данных.

Ключевые слова:оптимизация, абоненты, информационно-вычислительные сети.

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

Чтобы все необходимые требования к скорости и уровню надежности при передаче выполнялись, следует обратить внимание на следующие моменты:

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

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

Для решения поставленных задач предлагается алгоритм, при разработке которого использовались предложения организации сети, описанные в работах [1,3]. При описании алгоритма применим следующие обозначения:

 — текущее подмножество пунктов размещения  серверов, причем . - предварительно заданное множество пунктов начального расположения  начального расположения серверов, причем , .  — текущее число пунктов . - шаг приращения числа . - заданное множество пунктов, находящихся в окрестности сервера , причем .

Описание алгоритма:

1.     

2.     

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

4.      Проверить  на условие . Если условие выполняется, то перейти к шагу 5. Если не выполняется, то к шагу 6.

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

6.      Упорядочить все пункты  по возрастанию величин .

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

8.      , где  — множество пунктов, подключаемых к сети серверов.

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

10.  При сравнении 2-х вариантов в соответствии с рекомендациями [2] используется показатель разности затрат. При построении сетей серверов он принимает вид:, где  — затраты сравниваемых вариантов при организации сети. Вычислить и запомнить результат.

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

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

13.  Выполнить шаги 11 и 12 для следующей зоны. Закончить вычисления, когда при последовательном обходе  зон значение сохранится неизменным.

14.  Для фиксированного значения и заданного списка обслуживаемых пунктов найдена локально-оптимальная структура. Запомнить эту структуру и величину .

15.  Включить в множество очередной массив пунктов, упорядоченных в соответствии с шагом 6 и перейти к шагу 9. Если охвачено все множество пунктов , перейти к шагу 16.

16.  , перейти к шагу 2.

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

Актуальность этой задачи возрастает с каждым днем в связи со стремительным внедрением и применением кластерных вычислительных систем. Предложенный алгоритм позволяет существенно снизить затраты при проектировании сети. Точность данного алгоритма возрастет при увеличении множества пунктов, находящихся в окрестностях рассматриваемых серверов.

Литература:

1.      Давыдов Т.Б, Рогинский В. Н. Проблемы построения сетей связи. — М.: Наука. — 1968. — С. 5–29.

2.      Типовая методика определения экономической эффективности капитальных вложений. М.: Экономика. — 1969. — 16с.

3.      Шастова Г. А., Коекин А. И. Выбор и оптимизация структуры информационных систем. — М.: Энергия. — 1972. — 256с.