2 Модели и методы для анализа функционирования сетей передачи данных

2.1 Математическая модель распределения нагрузки в сети локального обмена данными "Эллипсоид".

Экспресс информация

Редколлегия журнала

Подписка на новости

Гостевая книга

Предоставление материалов

Письмо в редакцию

На начало

Математическая модель распределения нагрузки в сети локального обмена данными "Эллипсоид".

Климанов В.П., Дёмин К.В.

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

1. за счет совершенствования технической среды СЛОД путем существенного увеличения скорости обработки и обмена данными (например, в ходе развития сети Ethernet скорость обмена удалось повысить с 10 Мбит/c до Гбит/c);

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

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

Для решения указанных задач используется методология разработки СЛОД составных топологий, предложенная Климановым В.П.[1]. В ходе проведенных исследований авторами были предложены несколько вариантов таких сетей, относящихся к классу простых составных топологий типа "Решетка" (рис.1).

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

1. абоненты связываются через единственный моноканал, если они оба лежат на одном моноканале;

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

Такой подход к проектированию сети позволяет получить следующие положительные результаты:

• высокая надежность - достигнута за счет наличия нескольких независимых маршрутов связи и применением децентрализованного управления;

• высокая пропускная способность - подразумевает не только использование высокоскоростных базовых сетей, но и равномерное распределение нагрузки по всем элементам ЛВС;

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

• малое время связи между абонентами - как следствие высокой пропускной способности и эффективного алгоритма потокораспределения.

Однако проектирование подобных СЛОД сопряжено со значительными трудностями, а достаточно высокие затраты на их реализацию делают недопустимым создание физического прототипа для исследования особенностей функционирования. Выходом из подобной ситуации становится создание математических моделей СЛОД. Результаты моделирования дают возможности на этапе проектирования принимать решения по выбору архитектуры связи, определять требуемые характеристики отдельных компонентов, т.е. позволяют без существенных затрат проводить оптимизацию системы. Авторами были разработаны и подробно представлены аналитические модели для СЛОД "КУБ" топологии "Кубическая решетка" на базе шинных Ethernet моноканалов [2-4] и СЛОД "ТОР" топологии "Квадратная решетка" на базе кольцевых каналов связи с маркерным методом доступа [5]. При использовании в качестве базы кольцевых каналов связи возможно два случая их объединения модулями сопряжения, а именно:

1. ортогональные каналы связи соединены между собой в одной точке, что соответствует СЛОД "ТОР" (рис.1)

2. ортогональные каналы соединены в двух точках.

Во втором случае мы получаем СЛОД "Эллипсоид" топологии "Квадратная решетка" (рис.2).

Рассмотрим модель позволяющую проанализировать потокораспределение по каналам связи и модулям сопряжения такой сети.

В общем случае, СЛОД "Эллипсоид" содержит m вертикальных и n горизонтальных каналов связи и 2*m*n абонентов (рис.1). Соответственно имеем два множества каналов Mk_i (i = 1..n) и Mk_j (j = 1..m). Каждый абонент A и модуль сопряжения Mc определяется тремя индексами A_ijk и Mc_ijk где третий индекс k = 1..2 необходим для различия абонентов, у которых совпадают индексы обоих каналов. При последующих рассуждениях примем допущение, что связь любого абонента со всеми остальными происходит равно вероятностно.

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

Поток сообщений на выходе модуля сопряжения имеет пуассоновское распределение с интенсивностью A_ijk.

Если в рассматриваемый момент времени маркер принадлежит модулю сопряжения Mc_ijk и он не содержит пакет сообщения для передачи в канал связи, то время использования канала определяется суммой T₀ + t, где T₀ = b_сл/V.

Если же пакет сообщения отсутствует, то маркер передается следующему модулю сопряжения за время t:

(1)
где:
L_k - среднее расстояние между абонентами;
L_max - максимальное расстояние между абонентами;
C - скорость распространения сигнала в физической среде;
V - скорость передачи информации в канале связи;
R - коэффициент, зависящий от метода передачи ответа
b_сл - длина маркера в битах.
Среднее время обслуживания пакета одного абонента A_ijk в вертикальном Mk_j канале определяется по формуле (2):

(2)
Среднее время обслуживания всех абонентов канала Mk_j за один цикл определяется по формуле (3):
(3)
Аналогично определяется среднее время обслуживания t_i в горизонтальных каналах Mk_i.
Вероятность того, что за время цикла обслуживания t_j в модуле сопряжения Mc_ijk появится хотя бы одна заявка (при пуассоновском входном потоке) находится по формуле (4):
(4)
Поскольку модуль сопряжения в данной СЛОД кроме непосредственной функции сетевого адаптера для подключенного абонента выполняет еще и функции моста, то выходной поток информации у него можно разделить на три составляющие:

1. поток информации, передаваемый абонентом A_ijk для всех абонентов непосредственно связанных с каналом. Для вертикального канала Mk_j используем формулу (5):
   (5)
   где l_ijk интенсивность абонента A_ijk. Для горизонтального канала Mk_i используем формулу (6):
   (6);

2. поток информации, передаваемый абонентом A_ijk для всех абонентов непосредственно не связанных с горизонтальным и вертикальным каналами. Для вертикального канала Mk_j используем формулу (7):
   (7)
   Для горизонтального канала Mk_i используем формулу (8):
   (8)

3. поток информации проходящей транзитом через рассматриваемый модуль сопряжения.

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

Таким образом, через модуль сопряжения A_ij2 проходит транзитный поток заявок от тех абонентов A_xyz, для которых выполняется условие (j = y) З (i > x), а через модуль сопряжения A_ij1 проходит транзитный поток заявок тех абонентов A_xyz, которые удовлетворяют требованию (j = y) З (i < x). Величина этого потока определяется выражениями (9), при к = 1, и (10), при при к = 2:
(9)
(10)

Если в ситуации отправления сообщения абонентом А первым придет маркер горизонтального канала, то транзитный поток поступит уже в вертикальный канал через модуль сопряжения F. Этот транзитный поток через произвольный модуль сопряжения A_ijk, отправляемый в вертикальный моноканал, определяется выражениями (11), при при к = 1, и (12), при при к = 2:
(11)
(12)

В результате, поток информации, выдаваемый в канал произвольным модулем сопряжения Mc_ijk, определяется выражениями (13) для вертикальных каналов и (14) для горизонтальных каналов:
(13)
(14)

Интенсивность общего потока по произвольному вертикальному каналу получаем суммированием потоков каждого модуля сопряжения (15):
(15)
Соответственно для произвольного горизонтального канала это значение определяем выражением (16):
(16)

Выражения (15) и (16) для совокупности всех каналов дают нам систему с количеством уравнений соответствующему числу каналов m+n. Решение этой системы осуществляется методом Зейделя. Для определения вероятностно временных характеристик этой сети можно использовать модель аналогичную представленной в [5].

Для рассматриваемого класса СЛОД "Эллипсоид" были разработаны аналитические модели распределения потоков данных в сети и реализована программная среда моделирования.

Литература

1. Климанов В.П. Методы разработки аналитических моделей для анализа многоканальных вычислительных сетей, используемых в управлении технологическими процессами. М.- МЭИ. 1995. 115с.

2. Климанов В.П., Демин К.В. Многоканальная локальная сеть обмена данными "Трехмерная квадратная решетка" и ее аналитическая модель. Доклады международной конференции "Информационные средства и технологии". Том 1. -М.,1997.с. 84-91.

3. Климанов В.П., Демин К.В. Аналитическая модель локальной сети обмена данными "Трехмерная квадратная решетка" для анализа вероятностно - временных характеристик. Доклады международной конференции "Информационные средства и технологии". Том 1. -М.,1998.с. 137-142.

4. Климанов В.П., Демин К.В. Аналитическая модель сети локального обмена данными "ТОР". Доклады международной конференции "Информационные средства и технологии". Том 3. -М.,1999.с. 15-22.

5. Klimanov V., Diomin K. Multichannel Local Network "Three - Demensional Lattice" And Its Analytical Model. 43 INTERNATIONALES WISSENSCHAFTLICHES KOLLOQUIUM. BAND 1. : Technische universitat ilmenau thuringen, 1998.