РАЗДЕЛ 2
МАТЕМАТИЧЕСКИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
Описание сетей в терминах теории массового обслуживания
Наиболее часто при проектировании вычислительных сетей теоретической базой
используется классическая теория систем массового обслуживания (СМО) [23, 24].
Математический аппарат данной теории является достаточно точным и позволяет
осуществлять выбор альтернативных вариантов, расчет и оптимизацию характеристик
сети.
При описании вычислительной сети как СМО задаются следующие ключевые
характеристики модели:
* входящий поток запросов;
* количество и тип обслуживающих устройств;
* емкости накопителей (буферов), где запросы, заставшие все приборы занятыми,
ожидают обслуживания;
* времена обслуживания запросов на приборах;
* дисциплина обслуживания.
Для обозначения основных допущений, принимаемых при моделировании, используется
так называемая нотация Кендалла. Нотация имеет вид A/B/m/K/M, где A – описывает
входящий поток запросов, B – распределение времени обслуживания, m – число
обслуживающих устройств, K - емкость накопителя, M – число источников нагрузки.
Наиболее часто встречающиеся распределения обозначаются следующим образом:
G – произвольное распределение интервалов времени обслуживания запросов или
интервалов времени между поступлениями запросов (General);
M – экспоненциальное распределение (Markovian);
D – поступление запросов с постоянным периодом или фиксированное время
обслуживания (Deterministic).
Классической моделью простейшей системы, представляющей интерес, принято
считать систему М/М/1 с интенсивностью поступления требований , интенсивностью
обслуживания и одним обслуживающим прибором [25]. В такой системе длина
промежутка между соседними заявками (пакетами, сообщениями, ячейками) равна и
среднее время обслуживания равно , поскольку обе случайные величины
распределены по показательному закону. Обслуживание заявок осуществляется в
порядке их поступления. Диаграмма переходов такой системы представлена на рис.
2.1.
Рис.2. 1 Диаграмма интенсивности переходов для СМО типа М/М/1
Данная система является эргодичной при выполнении условия . В установившемся
режиме вероятность нахождения в системе k требований pk зависят от и только
через их отношение r - коэффициент использования системы:
Среднее число заявок и дисперсия числа заявок в такой системе соответственно
равно:
и .
Среднее время пребывания заявки в системе рассчитывается как
Вероятность того, что в системе содержится по меньшей мере k заявок можно найти
из выражения
Однако реальные системы редко могут быть описаны простейшей математической
моделью. Более адекватной может быть модель с конечным числом источников
нагрузки, m обслуживающих приборов и ограниченным размером очереди – система
М/М/m/К/М.
В такой системе интенсивность поступления каждой из М заявок равна , m
обслуживающих приборов, каждый из которых описывается параметром и ограниченное
число мест ожидания (очередь плюс обслуживаемые заявки) не превышает К.
Предполагается, что . Заявки, заставшие систему занятой, теряются и немедленно
возвращаются в группу поступающих так, как будто бы они полностью обслужены
(рис. 2.2).
Рис.2. 2 Диаграмма интенсивностей переходов для системы М/М/m/К/М
Вероятность нахождения в системе k заявок вычисляется в двух областях. В
области 0 ? k ? m-1 , когда очередь отсутствует, имеем
В противном случае, области m ? k ? K , когда заявки находятся в очереди, имеем
Одним из наиболее важных элементов в общей сетевой модели является характер
входящего потока. Следует отметить, что модели, построенные на основе
классической теории СМО, не всегда могут адекватно описать сложные процессы,
протекающие в современных вычислительных сетях, поскольку основываются на ряде
упрощающих предположений и допущений о характеристиках входящего потока.
Например, классическими моделями информационных потоков принято считать:
пуассоновский входящий поток, простейший поток вызовов, поток Эрланга порядка
r, гамма распределение (модели потока Эрланга для дробных r). В то время как
все чаще упоминается, что трафик современных высокоскоростных сетей обладает
особой структурой, при которой использование классических пуассоновских моделей
не может считаться адекватным [15]. Особенности, о которых идет речь, принято
называть проявлением эффекта самоподобия трафика.
Это свойство проявляется на практике в том, что пакеты поступают на узел не по
отдельности, а целой пачкой. Описанное явление значительно ухудшает
характеристики при прохождении самоподобного трафика через сеть даже в случаях,
когда средняя интенсивность трафика намного ниже потенциально достижимой
скорости передачи в канале, поскольку увеличиваются задержка в сети, джиттер,
что приводит к потерям пакетов из-за ограниченности буфера, рассчитанного по
классическим методикам.
Таким образом, правильное описание потока запросов, поступающих в случайные
моменты времени в реальную систему, и идентификация его параметров во многом
определяют характеристики производительности функционирования СМО и являются
одной из важнейших задач.
К основным методам, с помощью которых могут быть представлены современные
модели трафика вычислительных сетей можно отнести следующие (рис. 2.3) [26]:
методы, представляющие трафик с помощью модулированных потоков, в частности
пуассоновского (МРР, Modulated Poisson Process) [27, 28, 29, 30, 31];
методы, представляющие трафик с помощью хаотических отображений, модели
фрактального гауссового шума (ФГС) и фрактального броуновского движения (ФБД)
[32, 33, 34, 35, 36];
методы, которые позволяют создавать имитационные последовательности на основе
образца реального трафика [37, 38, 39, 4
- Київ+380960830922