Моделирование процессов информационного обмена в корпоративных сетях на основе теории массового обслуживания

Размещено на http://www.allbest.ru/

УДК 681.324

Моделирование процессов информационного обмена в корпоративных сетях на основе теории массового обслуживания

Константинов И.С.

В настоящее время основными коммуникационными устройствами кампусных сетей являются коммутаторы, а не маршрутизаторы или концентраторы. Это обуславливается несколькими причинами. Во-первых, стоимость коммутаторов в последнее время значительно снизилась и приблизилась к стоимости концентраторов. Так как полная пропускная способность коммутатора значительно больше, чем у концентратора, при одинаковой стоимости предпочтение отдается коммутаторам. Во-вторых, в качестве магистральных коммутационных устройств в настоящее время применяются коммутаторы третьего уровня, которые позволяют фильтровать широковещательный трафик, и в то же время обладают большим быстродействием, чем маршрутизаторы. Показатель «цена/производительность», рассчитанный для одного порта у таких коммутаторов ниже, чем аналогичный показатель маршрутизаторов. Многие проектировщики сетей придерживаются принципа «коммутаторы - где возможно, маршрутизаторы - где необходимо» [2].

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

Предположим, что в системе имеется J станций, J ? 1, на каждой из которых N приборов, N ? 1, причем все приборы на станциях одинаковы. Эту систему будем обозначать SNJ.

На систему SNJ поступает несколько пуассоновских потоков От, 1 ? m ? М < ?, интенсивностей Nлт. Потоку От соответствует непустое подмножество станций Кm {1, 2, ..., J}, на каждую из которых может быть направлено сообщение из потока От.

Заявка из потока От выбирает на i-ой станции приборы (i Кm) rm(i), rт(i) ? 1 и направляется в кратчайшую из всех выбранных очередей.

Времена обслуживания сообщений независимы и распределены экспоненциально со средним единица. Подчеркнем, что число выбранных на станции приборов rт(i) зависит как от т, так и от i, и приборы, из которых приходится выбирать, могут принадлежать разным станциям. Обозначим общее число приборов, которое первоначально выбирается потоком От, через |rm|, |rm| = УiКmrт(i).

Приведем необходимые и достаточные условия неперегруженности системы. Назовем входной поток От потоком, направленным на Кm.

Система не перегружена, если для любого подмножества станций К {1, .., J} (включается и само {1, ..., J}) сумма всех потоков, направленных на это подмножество, не превосходит числа станций #К в К:

(1)

где < 1, К К

Смысл этого условия достаточно ясен: средняя нагрузка на каждую из станций ( с N приборами) не должна превосходить N. При условии (1) имеет место по крайней мере, экспоненциальное убывание вероятностей длинных очередей в предельной системе (N = ?), а если |rm| > 1 т, то убывание будет сверхэкспоненциальным.

Обратим внимание на то, что в условие (1) не входят значения rт(i).

Приведем несколько примеров.

1) Пусть имеется две станции и три потока. Из потока О1 интенсивности Nл1 сообщение направляется на первую станцию (К1 = {1}), где выбор идет из r1 (1) приборов. Из потока О2 интенсивности Nл2 сообщение направляется на вторую станцию (К2 = {2}), где выбор идет из r2 (2) приборов. Из потока О3 интенсивности Nл3 сообщение может быть направлено на любую из станций (К3 = {1,2}), там выбор идет из r3(1) приборов первой станции и из r3(2) приборов второй станции. Условие неперегруженности имеет вид л1 < 1, л2 < 1, л1 + л2 + л3 < 2.

2) Система из четырех станций, К1 = {1, 2} , К2 = {2, 3, 4}, К3 = {4}, условие неперегруженности имеет вид л1 < 2, л2 < 3, л3 < 1, л1 + л2 + л3 < 4.

3) Пусть имеется J станций, на систему SNJ поступает пуассоновский поток интенсивности NЛ, с приходом сообщения на SNJ наудачу дважды выбирается по станции и в каждой из них выбирается по прибору. Вероятность выбрать станцию j равна pj, Уjpj = 1. Нетрудно видеть, что такой выбор станций и приборов соответствует тому, что множества Кm состоят из одной или двух станций, интенсивность потока, направленного на станцию j, равна NЛрj2, а интенсивность потока, направленного на пару станций {i, j}, равна 2NЛрipj. Можно считать, что p1 ? … ? pJ. Условия неперегруженности имеют здесь вид:

Систему примера 3) естественно сравнить с «линейной» системой, в которой имеется J станций, J ? 2, на каждой станции по N, N ? 1 приборов, на систему направлен пуассоновский поток интенсивности NЛ, и при поступлении сообщения на обслуживание с вероятностью рj выбирается одна из станций, а на этой станции выбирается один из N приборов, куда и направляется сообщение. Для такой системы условие неперегруженности имеет вид Лрj < 1, и в стационарном состоянии вероятность того, что на j-ой станции длина очереди не меньше, чем k равна (Лрj)k, это условие жестче, чем условие неперегруженности в примере 3).

Рассматривая систему SNJ, введем, как и выше, векторы uj = (u0,j, u1,j, …), где uk,j - доля приборов на j-ой станции, у которых очереди не короче чем k. Ясно, что 1 = u0,j ? u1,j ? … ? 0.

Поведение системы описывается цепью Маркова (точнее, фактор-цепью), пространство ее состояний мы обозначим через .

Выпишем производящий оператор АNJ этой цепи, который действует на функциях ѓ(u), u. Начнем со случая, когда имеется J станций, множества Кm состоят из одной или двух станций, и выбор делается из двух приборов (на одной или на двух станциях). Интенсивность потока направленного на станцию j, равна лj, а интенсивность потока, направленного на пару станций {i, j},- лij. Тогда:

ANJ ѓ(u) = (2)

где en,j - j-й вектор, у которого все координаты равны 0, а n-ая координата равна 1. Пояснения к этому выражению совпадают с пояснениями к выражению (1.5).

В случае общей системы выражение для производящего оператора очень громоздко, и мы опишем входящие в него члены по-отдельности. Переход от ѓ(u) к ѓ(u_) происходит с частотой, пропорциональной (un,j - un+1,j). Переход от ѓ(u) к ѓ(u+), j = 1,…,J означает, что у всех выбранных приборов очереди не короче чем n-1 и есть хоть один прибор с очередью n-1. Вероятность этого (при данном u) пропорциональна:

(3)

Поясним это выражение. Здесь обозначено - число приборов, выбранных

в потоке Оm на станции l, в которых оказалось по n-1 сообщений, а - число приборов, выбранных на станции l, в которых оказалось не меньше чем n сообщений (в и опущена переменная n).

Если выбрано || приборов, || = , с очередями длины n - 1, то сообщение направляется на j-ую станцию с вероятностью, пропорциональной .

Поэтому выбор прибора со станции j с длиной очереди n - 1 происходит с вероятностью:

.

При N > ? эволюция системы описывается динамической системой, заданной на последовательностях u = (u0,j, u1,j, ...,) 1 ? j ? J, 1 = u0,j ? u1,j ? …? 0. Динамическая система рассматривается в множестве последовательностей u. Вводятся также множества

Метрика в задается соотношением:

(4)

В случае двух станций и || = 2, соответствующим оператору (2), предельная динамическая система имеет вид:

(4.4)

i ? j, 0 ? n ? ?, i, j = 1, 2, i ? j.

Начально-краевые условия:

, , , .

Общему случаю отвечают предельные уравнения:

.

Правую часть уравнения (6) мы будем сокращенно обозначать Р(иn,j(t)). Обозначим еще

, , , .

Аналогично тому, как это было ранее, обозначим через динамическую систему, которая задается отображением g > u(t,g), , где u(t,g) - решение задач (5),(6). Этой динамической системе отвечает полугруппа Т = Т(t), действующая в пространстве L = C непрерывных функций ѓ: > R1 . Пусть T(t)ѓ(g) = ѓ(u(t,g)), .

Система SNJ определяет марковский процесс = (t) с пространством состояний , заданный операторами (3). Процессу

соответствует полугруппа ТN = ТN(t) в пространстве функций на :

ТN(t) ѓ(u) = E(ѓ((t))| (0) = u), u .

Описанная выше система обобщается нами на более общий случай: на сеть типа быстрой сети Джексона. Напомним, что открытая сеть Джексона - это система, состоящая из J приборов, на которые поступают потоки сообщений. Поступившее на станцию i, i = 1,…, J сообщение после окончания обслуживания с вероятностью рij снова направляется на обслуживание на прибор j, а с вероятностью 1 - покидает систему. В быстрой сети Джексона имеется J станций с N приборами каждая. Поступившее на станцию i сообщение выбирает на этой станции ri, ri > 1, приборов и направляется в тот из них, где очередь короче. После окончания обслуживания сообщение с вероятностью рij снова направляется на обслуживание на станцию j (и там выбирает ri приборов), а с вероятностью 1 - покидает систему. Условия неперегруженности такой сети совпадают с условиями для «обычной» сети Джексона, но в быстрой сети при N > ? и minjrj > 1 вероятности длинных очередей убывают сверхэкспоненциально.

В настоящей работе понятие быстрой сети обобщается. А именно, рассматривается открытая сеть, в которой в каждом узле-станции имеется N приборов. На сеть снова поступают пуассоновские потоки От интенсивностей Nлm. Каждому потоку От соответствует непустое подмножество станций Km {1, 2, ..., J}. Заявка из потока От выбирает на каждой станции i, i Km, rт(i) приборов и направляется в кратчайшую из очередей. По окончанию обслуживания на станции i сообщение покидает сеть с вероятностью 1 - , а с вероятностью остается в сети и с вероятностью Рi,(т) направляется на станции Km, т.е. в поток От , где снова выбирает приборы, и т.д. Времена обслуживания независимы и распределены экспоненциально со средним единица.

Такая сеть описывается цепью Маркова со счетным числом состояний.

Трудность, в частности, состоит в том, что без численных расчетов не удается по параметрам задачи определить долю загруженных приборов на каждой из станций. Но если раньше при = 0, это не мешало найти условия неперегруженности системы, на этот раз удается указать лишь достаточные условия неперегруженности сети при конечном N, т.е. удается привести лишь достаточные условия эргодичности цепи Маркова, описывающей работу сети (необходимые и достаточные условия известны только для случая J = 2, N = 1). Для предельной динамической системы в общем случае тоже даются лишь достаточные условия существования единственного стационарного решения, к которому при t > ? сходятся все суммируемые решения.

Приведем простые достаточные условия эргодичности, которые имеют вид:

, где v < 1, .

Смысл этих условий (и их достаточность) состоит в предположении, что система не перегружена даже если “вторичные” потоки сообщений поступают со всех приборов всех станций, а не только с тех, на которых есть обрабатываемые сообщения.

Мы снова не приводим здесь производящего оператора сети ввиду его громоздкости.

При N > ? эволюция системы описывается динамической системой, заданной на последовательностях u = (u0,j, u1,j,…,) 1 ? j ? J, 1 = u0,j ? u1,j ?…? 0, un,j R1.

Приведем сначала уравнения для предельной динамической системы в случая двух станций, при K1 = 1, K2 = 2, K12 = 1, 2, r1(1) = 2, r2(2) = 2, r12(1) = 1, r12(2) = 1, т.е. когда всегда выбор делается из двух приборов. Уравнения имеют при этом вид:

u0,j(t) ? 1, uk,j(0) = gk,j, 1 ? gk,j ? gk+1,j ? 0, j = 1, 2, j ? j, k = 1, 2, …

В общем случае предельная динамическая система имеет вид

Для системы дифференциальных уравнений (13) с начально-краевыми условиями (12) мы даем необходимые и достаточные условия того, что при t > ? решения (11)-(12) сходятся к единственному стационарному решению а = где убывают сверхэкспоненциально по k. Подчеркнем, что для соответствующего Марковского процесса даются только достаточные условия эргодичности (10).

Здесь мы впервые сталкиваемся с ситуацией, когда эргодичность цепи Маркова при конечном N не удалось доказать при всех значениях параметров, при которых предельная система имеет единственное стационарное решение, лежащее в пространстве суммируемых последовательностей. информационный кампусный сеть

Для рассматриваемой сети связи верны Теоремы 1-4 с заменой в них условия (1) на условие (10).

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

ЛИТЕРАТУРА

1. Бусленко, Н.П. Моделирование сложных систем [Текст] / Н.П. Бусленко // М.: «Наука», 1978. - 400 с.

2. Зайченко, Ю.П. Структурная оптимизация сетей ЭВМ [Текст] / Ю.П. Зайченко, Ю.В. Гонта // - К.: Технiка, 1986. - 168 с.

3. Шварц, М. Сети ЭВМ. Анализ и проектирование [Текст] /М. Шварц // Пер. с англ. / Под ред. В.А.Жожикашвили. - М.: Радио и связь, 1981. - 336 с.

Размещено на Allbest.ru