close

Вход

Забыли?

вход по аккаунту

?

Lihttsinder Intervalnij metod analiza trafika multiservisnyh setej dostupa

код для вставкиСкачать
Лихтциндер Б. Я.
ИНТЕРВАЛЬНЫЙ МЕТОД АНАЛИЗА
ТРАФИКА МУЛЬТИСЕРВИСНЫХ
СЕТЕЙ ДОСТУПА
МОНОГРАФИЯ
2015
1
УДК 621.324
Научное издание
Рецензент: заведующий кафедрой «Системы связи»
ФГОБУ ПГУТИ, д.т.н., профессор Васин Н.Н.
Лихтциндер Б. Я.
ИНТЕРВАЛЬНЫЙ МЕТОД АНАЛИЗА ТРАФИКА МУЛЬТИСЕРВИСНЫХ
СЕТЕЙ ДОСТУПА. Монография.- ПГУТИ, Самара 2015. - 121 с.
ISBN……
.
ISBN……
2
Оглавление
Введение……………………………………………………..5
Глава 1. Интервальные характеристики
потоков заявок...………………..…………………….…...9
1.1 Особенности мультисервисного трафика………….....9
1.2 Исследуемая модель…………………………………..12
1.3 Число заявок на интервале обслуживания…………..14
1.4 Влияние законов распределения вероятностей….….19
1.5 Определение коэффициента загрузки…………….…20
1.6 Среднее число поступивших заявок, приходящееся
на каждую обслуженную……………………………........25
1.7 Взаимные корреляционные моменты……….…..…...27
Глава 2. Обслуживание очередей……………....…..30
2.1 Алгоритм последовательного определения средней
длины очереди в СМО…….………………………...…....30
2.2 Средняя доля недообслуженных заявок…………….34
2.3 Дообслуживание очередей………………….………..37
2.4 Уравнение баланса…………………………………....39
2.5 Автокорреляционные моменты……………………...42
2.6 Частные примеры…………………………………..…45
2.7 Многоканальные СМО……………………………….50
3
2.8 Аппроксимация………………………………………..55
2.9 Скорость и дисперсия изменения очереди……….....57
2.10 Мультиплексирование………………………..……..60
2.11 Относительные приоритеты………………………...62
Глава 3. Распределения заявок на интервалах
обслуживания………………………………………….....65
3.1 Образующие функции…………………………...............65
3.2 Г- распределение интервалов между заявками……..68
3.3 Квазипуассоновское распределение вероятностей
чисел заявок……….....……………………………..….....75
3.4 Г- распределение вероятностей чисел заявок на
ин тервале  ………………………………………………….….…77
3.5 Гиперпуассоновское распределение вероятностей
чи сел заявок на интервале  …..…………………........................79
3.6 Гипер Г- распределение вероятностей чисел заявок
на интервале  ……………………………………………….…...81
Глава 4. Программный анализ трафика…….....86
4.1 Средства мониторинга и анализа трафика…..……....86
4.2 Анализаторы протоколов……………………..……....86
4.3 Анализатор протоколовWireShark…………...……...93
4.4 Подготовка данных…………………...……………....97
4.5 Программа интервального анализа трафика……....105
4.6 Запуск программы……………..………………….....111
Заключение.………………………………… …………..114
Литература.……...……………….................…………...116
Приложение: 1 Программа анализа.....................118
Приложение: 2 Таблица обозначений..................121
4
ВВЕДЕНИЕ
Трафик мультисервисных сетей очень неоднороден и носит пачечный характер. Особенно это
относится к трафику сетей доступа. Поэтому, на
границах сетей оператор вынужден очень четко
контролировать неравномерность трафика, определяя его пиковые значения. Неравномерность трафика приводит к возникновению очередей в коммутаторах, где коммутаторы рассматриваются , как
некоторые системы массового обслуживания
(СМО). При анализе СМО, обычно, рассматриваются две вероятностные характеристики: это распределение вероятностей интервалов между соседними заявками, и не зависящее от него, распреде5
ление вероятностей длительности времен обслуживания заявок. В качестве заявок, рассматривается
поток пакетов, а в качестве времени обслуживания
рассматривается время передачи пакета.
Неравномерность трафика может вызвать появление больших очередей, требует больших дополнительных объемов памяти и может вызвать большие задержки при обслуживании трафика в коммутаторах. Основным соотношением, определяющим
размер очередей в системах массового обслуживания, является известная формул а Хинчина - Поллячека, устанавливающая зависимость между средним размером очереди и коэффициентом загрузки
системы. Особенно, следует отметить, что средние
размеры очередей зависят, по отдельности, не от
распределения интервалов между заявками и распределения интервалов обработки, а от их совокупности, а именно, от распределения чисел заявок,
поступающих в течение интервалов обработки каждой из заявок. Указанная величина характеризует
изменение коэффициента загрузки системы. Зависимость эта нелинейная, и, при больших значениях
коэффициента загрузки, очереди резко возрастают.
Целью контроля трафика и является недопущение
образования очередей, и, как следствие, возникновения больших задержек. Нелинейный характер зависимости очередей от загрузки, вызывает также
трудности, при мультиплексировании трафика.
Формула Хинчина - Поллячека справедлива только
6
для пуассоновских потоков. Поэтому, возникает
необходимость нахождения зависимостей, пригодных для определения размеров очередей в системах, с потоками общего вида. Такие зависимости
были получены , в результате применения рассматриваемого ниже интервального метода, основанного на определении чисел заявок, поступающих в
течение интервалов обслуживания. Вместо анализа
использовавшихся ранее двух вероятностных распределений, предлагается анализировать одну характеристику -распределение вероятностей коэффициентов загрузок, при этом , вводится такое понятие, как мгновенный коэффициент загрузки. Под
мгновенным коэффициентом загрузки понимается,
число заявок, поступающее в течение интервала
обслуживания одной заявки. При этом, в течение
указанного интервала может поступить более одной заявки, а также, не поступить ни одной заявки.
Полученная случайная величина считается мгновенным коэффициентом загрузки, а ее математическое ожидание является коэффициентом загрузки, в
обычном понимании этого слова. Характерно, что
коэффициент загрузки растет строго пропорционально увеличению среднего интервала обработки
заявок, вне зависимости от характера исследуемого
потока.
Итак, первым наиболее важным результатом
является предложение исследовать не две случайные величины, а одну - мгновенный коэффициент
загрузки. Эта случайная величина дает полную ин7
формацию о возможных очередях системы массового обслуживания.
Вторым результатом, для любых потоков, является установление пропорциональной зависимости
среднего размера очереди от значений дисперсии и
коэффициентов корреляции этой случайной величины.
Третьим важным результатом, полученным при
исследовании формулы Хинчина- Поллячека одноприборных систем массового обслуживания , является установление независимости функции ее знаменателя от характера потока заявок.
Анализу трафика МСС посвящено большое
число самых различных публикаций, и предлагаемая работа, несомненно, является «одной из многих». Однако полученные в ней аналитические соотношения позволяют охарактеризовать трафик
различных приложений МСС с единых позиций, а
сами характеристики непосредственно определяют
средние размеры возникающих очередей.
На наш взгляд, публикуемый материал носит
дискуссионный характер, а некоторые его положения не всегда являются бесспорными. Поэтому автор, с удовлетворением, воспримет возможность
возникновения дискуссии.
8
ГЛАВА 1. ИНТЕРВАЛЬНЫЕ ХАРАКТЕРИСТИКИ ПОТОКОВ ЗАЯВОК
1.1
ОСОБЕННОСТИ
ТРАФИКА
МУЛЬТИСЕРВИСНОГО
В МСС с пакетной коммутацией поток пакетов
существенно отличается от пуассоновского – поскольку эти потоки формируются множеством источников запросов на предоставление услуг, существенно отличающихся между собой.
Любой пакетный трафик является продуктом
компьютерной обработки, выполняемой процессором при решении задач приложений. Решение любой задачи состоит из трех последовательных этапов: получение исходных данных, процесс обработки и процесс выдачи результатов, причем, трафик образуется именно на третьем этапе. Это и
обуславливает его пачечный характер. На структуру трафика оказывают влияние и особенности применяемых алгоритмов обслуживания. Например,
моменты возникновения запросов на обслуживание
сильно коррелированны, если в используемых протоколах применяется повторная передача ошибочно принятых пакетов. Все это приводит к тому, что
для МСС-потоков характерна неравномерность поступления заявок и пакетов. Пакеты группируются
в «пачки» в одних промежутках времени и практически отсутствуют – в других промежутках. Случайный процесс поступления заявок (пакетов) в
систему характеризуется законом распределения,
9
устанавливающим связь между значениями случайной величины и вероятностями появления указанных значений. В большинстве случаев, такой
поток характеризуется функцией распределения
временных интервалов между соседними заявками.
Имеется также множество работ, в которых потоки
заявок характеризуются функцией распределения
числа заявок за условную единицу времени.
В настоящей работе, в качестве указанной единицы времени, рассматривается постоянный интервал времени  обработки одной заявки. Показано,
что дисперсия и корреляционные свойства числа
заявок, поступающих за интервал обработки, оказывают определяющее влияние на средний размер
очереди.
Рассмотрим особенности функции распределения вероятностей числа заявок на интервале для
МСС-потока.
1. В большинстве случаев, для характеристики
числа заявок, поступающих за некоторый интервал
времени, используется нормальный закон распределения.
Однако исследования показали, что для МССтрафика аппроксимация нормальным законом распределения не согласуется с действительностью.
Реальные распределения обладают существенной
асимметрией, в то время как нормальный закон
предполагает симметричное распределение.
10
2. МСС-поток заявок обладает существенной
неравномерностью. Даже в течение небольших
промежутков времени наблюдаются периоды высокой активности, периоды пониженной активности и периоды полного отсутствия заявок.
3. Большая «пачечность» потока приводит к появлению значительного числа интервалов, в течение которых заявки вообще не поступают. Именно
эта весьма высокая вероятность «нулевого состояния» приводит к отличию реального закона распределения от «нормального».
4. Характер закона распределения числа заявок,
поступающих за некоторый интервал времени 
существенно зависит от величины указанного интервала. Так, для всех значений  , не превышающих минимальный промежуток времени  min между двумя соседними заявками, на интервале может
поступить не более одной заявки. Поэтому распределение вероятностей числа заявок имеет всего
лишь две составляющие, соответствующие поступлению одной заявки или «ноль» заявок.
С другой стороны, средний интервал времени
обработки  не может превышать значения 1  , где
 – средняя интенсивность поступления заявок в
потоке. Это равносильно тому, что значение суммарного коэффициента загрузки    не должно
превышать единицу. Именно в указанных пределах
следует рассматривать изменение интервала  при
построении модели закона распределения числа
заявок, поступающих за интервал времени. Вместе
11
с тем, в большинстве исследований интервал времени анализа выбирается произвольно, независимо
от реального времени обработки заявок МССпотока. В связи с тем, что МСС-поток заявок обладает существенной неравномерностью, в нем наблюдаются периоды с различной активностью.
Указанные периоды чередуются между собой во
времени с различными вероятностями появления,
причем, в течение каждого периода присутствует
лишь один вид потока. Отсутствию заявок соответствует период нулевой активности.
1.2 ИССЛЕДУЕМАЯ МОДЕЛЬ
В качестве исследуемой модели нами будет рассматриваться стационарный ординарный поток
заявок, поступающих на обработку в систему массового обслуживания (СМО).
При анализе СМО наиболее часто применяются
две вероятностные характеристики распределения.
Это распределение интервалов υ между соседними
заявками и распределение интервалов времени обработки заявок  . На основе указанных распределений легко определяются параметры  
 2 
D
,
( ) 2
Поллячека:
12
входящие
в
формулу


и
Хинчина-
 2 (1   2 )
q
,
2(1   )
(1)
где
 – коэффициент загрузки;
q – средняя длина очереди;
 – средне время обслуживания заявки;
 – средний интервал между соседними заявками;
D – дисперсия времени обслуживания заявок.
Существенным ограничением (1) является ее
применимость исключительно к СМО с простейшими потоками, для которых интервалы между заявками распределены экспоненциально.
Имеется много попыток модернизации формулы (1) с целью ее применения для «не экспоненциальных» потоков заявок [1]. Однако, все полученные результаты применимы лишь для слабо изменяющихся входных потоков, для которых коэффициент вариации интервалов между заявками не
превышает единицу. Хотя современные МСС имеют входные потоки пакетов, для которых коэффициент вариации в несколько раз превышает единицу. К таким потокам применение аналитических
соотношений, указанных в [1], становится невозможным. Это обусловлено тем, что в качестве основного параметра, характеризующего длину очереди, в аналитических соотношениях используется
коэффициент ρ загрузки по времени. Он отображает среднюю долю времени, приходящуюся на обра13
ботку одной заявки, по отношению к среднему интервалу между заявками.
1.3 ЧИСЛО ЗАЯВОК НА ИНТЕРВАЛЕ
ОБСЛУ ЖИВАНИЯ
Вместе с тем, Л. Клейнроком [2] показано, что
длина очереди одноприборной СМО, в общем случае, определяется случайной величиной m – числом поступивших заявок, приходящихся на одну
обработанную заявку. Обозначим через m математическое ожидание, а через m2 – второй начальный
момент указанной случайной величины.
На Рис.1.1 показаны результаты имитационного
моделирования.
mi
mi
для   0,1
для   1,0
Рис. 1.1 - Числа заявок для пуассоновского потока,
с параметром   1,0 , на интервалах  , соответствующие различным значениям коэффициента загрузки 
Так, для всех значений  , не превышающих минимальный промежуток времени  min между двумя
14
соседними заявками, на интервале  может поступить не более одной заявки. Поэтому распределение вероятностей числа заявок имеет всего лишь
две составляющие, соответствующие поступлению
одной заявки или «ноль» заявок.
При значениях коэффициента загрузки   0,1, в
интервал  поступает, не более двух заявок, а при
значениях   1,0 , в интервал  может поступить до
четырех заявок, что и следует из Рис. 1.1.
Соответствующие распределения вероятностей
подчиняются закону Пуассона и показаны на
Рис. 1.2 .
P ( )
P ( )
для   0,1
m
для   1,0
m
Рис. 1.2 - Пуассоновские распределения вероятностей
чисел заявок с параметром   1,0 , на интервалах  ,
соответствующих различным значениям коэффициента
загрузки 
Вместе с тем, в большинстве исследований интервал времени анализа выбирается произвольно,
независимо от реального времени обработки заявок
МСС-потока. В связи с тем, что МСС-поток заявок
15
обладает существенной неравномерностью, в нем
наблюдаются периоды с различной активностью.
Указанные периоды чередуются между собой во
времени с различными вероятностями появления,
причем, в течение каждого периода присутствует
лишь один вид потока. Отсутствию заявок соответствует период нулевой активности.
для   0,1
для   1,0
Рис. 1.3 - Числа пакетов от видео трафика , на
интервалах  , соответствующих различным значениям
коэффициента загрузки 
На Рис. 1.3 показаны числа пакетов от видео
трафика , на интервалах  , соответствующих различным значениям коэффициента загрузки  .
В отличие от пуассоновского, ввиду пачечного
характера трафика, даже при малых значениях загрузки, он образует на интервалах  пачки, содержащие до 15 пакетов, а на интервалах, соответствующих предельной загрузке, пачки содержат до 40
пакетов.
16
На Рис. 1.4 показаны распределения вероятностей чисел заявок видеотрафика на интервалах  ,
соответствующих различным значениям коэффициента загрузки  .
P ( )
P ( )
m
для   0,1
для   1,0
Рис.1.4 - Распределения вероятностей чисел заявок
видеотрафика на интервалах  , соответствующих
различным значениям коэффициента загрузки 
m
На графиках не приведены вероятности P0 (  )
отсутствия пакетов на интервалах  , значения которых в обоих случаях превышают 0,95. Оставшиеся, приблизительно, 5% приходится на все остальные вероятности. Однако, при малых загрузках основные вероятности сосредоточены в пределах 10
пакетов на одном интервале  , а при больших загрузках, числа заявок увеличивается до 50. Это и
вызывает появление больших очередей.
На Рис.1.5 показаны зависимости среднего значения очередей от коэффициента загрузки  .
17
q(  )
q(  )
 10
 10
Для пуассоновского трафика. Для видео трафика.
Рис.1.5 - Средние значения очередей, в зависимости
от коэффициента загрузки 
Разница очевидна! Например, при коэффициенте загрузки   0,5 , средняя длина очереди для пуассоновского трафика составляет 0,25 пакета, в то
время, как для видеотрафика она превышает 200
пакетов. Следовательно, известная формула Хинчина-Поллячека (1), справедливая для очередей с
пуассоновскими потоками, совершенно не применима для потока видеотрафика.
1.4 ВЛИЯНИЕ ЗАКОНОВ РАСПРЕДЕЛЕНИЯ
ВЕРОЯТНОСТЕЙ
Принято считать, что, при постоянном времени
обслуживания, характер очередей в СМО полностью определяется распределением вероятностей
интервалов времени  i между соседними заявками.
И, если закон распределения является экспонен18
циалиным, а, следовательно, распределение вероятностей чисел заявок на интервале времени  подчиняется закону Пуассона, то коэффициент загрузки  однозначно характеризует размер очереди,
согласно (1). При этом подразумевается, что интервалы времени  i взаимно независимы, и между ними отсутствует корреляция. Если же указанные интервалы взаимно коррелированны, то , даже при их
экспоненциальном распределении, применение
формулы (1) становится невозможным. Это обусловлено тем, что в качестве основного параметра,
характеризующего длину очереди, в аналитических
соотношениях используется коэффициент ρ загрузки по времени, который не учитывает корреляционные свойства заявок.
В качестве примера рассмотрим реализацию
простейшего стационарного потока заявок, с экспоненциальным распределением интервалов времени между соседними заявками, на длительном
промежутке времени T. Переставим местами полученные значения интервалов, с начала промежутка
времени Т, по мере их возрастания. Полученный
таким образом поток также, как и исходный поток,
имеет экспоненциальное распределение интервалов
времени между соседними заявками. Однако, средний размер очереди для такого потока будет во
много раз превышать значения, полученные по (1)
для исходного потока. Этим примером мы хотим
еще раз подтвердить, что, при заданном времени
обслуживания, знание закона распределения веро19
ятностей, далеко не полностью определяет размер
очередей, получающихся при обработке заявок в
СМО. Большое, (а часто определяющее) влияние на
размеры очередей оказывают корреляционные
свойства потоков.
1.5 ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА
ЗАГРУЗКИ
Что же такое коэффициент загрузки, и какова
методика его определения? Анализ будем проводить для стационарных, ординарных, потоков событий (заявок) во времени. Выбираем на оси времени произвольный момент, обозначаемый t 0 . Поскольку поток стационарный, выбор начального
момента времени не имеет значения. Рассмотрим
интервал времени T (начиная с момента t 0  0 ), на
котором сохраняется стационарность потока и происходит достаточно большое число K событий.
Параметр средней интенсивности  на указанном
интервале
времени
определяется
как:
T

К
T
[сооб / С ]
.
(2)
Разделим весь интервал T на достаточно большое число равных промежутков времени t таких,
на которых могло бы произойти не более одного
события (поступления заявки). Условие ординарности потока событий всегда позволяет выбрать
20
такой малый промежуток времени t . Число таких
промежутков на интервале T обозначим через
M 
T
t
(3)
На каждом из промежутков t i может возникнуть событие (с вероятностью
P
K
M
) или отсутст-
вовать событие (с вероятностью (1  P) ). Обозначим
через mi число событий на промежутке времени
t i , i = 1, М :
1  с вероятностью P;
mi  
0  с вероятностью 1  P.
Введем в рассмотрение понятие дифференциальной интенсивности событий на промежутке
времени t
i 
mi
t
,
1

mi  i  t. i   t
 0
 при
наличии
события ;
 при
отсутствии
события .
(4)
Рассмотрим на оси времени некоторое временное «окно» длительностью  и включающее в себя
r промежутков t
r

t
.
(5)
Число событий (заявок) наступивших за интервал времени  , начинающийся на промежутке t i ,
обозначим как
21
r-1
r-1
s 0
s 0
mi ( )   mi s   i s  t .
Среднее число событий m i ( ) , наступивших на
интервалах  , по всем промежуткам t i , i = 1, М ,
обозначим через
1 M
 mi ( ) .
М i1
m( ) 
(6)
После подстановки получим:
m( ) 
1
M
M
r-1
 is  t 
i 1 s  0
1
M
r 1 M
 is  t 
s  0 i 1
1
M
r 1
K
s 0
s
где K s – суммарное число событий, возникающих на достаточно большом интервале времени T ,
сдвинутом относительно начала отсчета t 0 на s
промежутков времени t .
Поскольку процесс стационарен, значения K s не
зависят от сдвига s и остаются неизменными и
равными K . Следовательно,
m( ) 
K
M
r 1
K
s  M r .
(7)
s 0
С учетом (2), (3) и (5), окончательно получим
m( )     .
(8)
Среднее число событий, наступающее за постоянный интервал времени  , пропорционально указанному интервалу и не зависит от вида закона
распределения потока событий. Если предположить, что рассматриваемые события представляют
22
собой заявки, поступающие в некоторую СМО, и
любая из заявок обслуживается полностью за одинаковое, постоянное время  , то параметр
m( ) точно совпадает с коэффициентом загрузки
    указанной СМО.
Итак, коэффициент загрузки  может быть получен в результате усреднения случайных чисел
m i ( ) заявок, попадающих в интервалы времени  ,
начинающиеся на промежутках t i , i = 1, М . Второй
начальный момент m2 ( ) и дисперсия Dm ( ) могут
быть получены соответствующим усреднением
квадратов указанных величин. В дальнейшем, в качестве аргумента, мы будем использовать не интервал времени  , а соответствующее ему значение
коэффициента загрузки  .
На рис.1.6 показаны зависимости m( ) для рассмотренных выше экспоненциального потока и потока пакетов видео трафика, полученные в результате имитационного моделирования.
Несмотря на существенные различия потоков,
указанные зависимости для них полностью совпадают.
23
m( )
 10
Рис.1.6 - Зависимости m( ) для пуассоновского
потока и потока пакетов видео трафика
В отличие от математических ожиданий, зависимости дисперсий Dm (  ) , показанные на рис.1.7,
для указанных потоков существенно различны.
Dm (  )
Dm (  )
 10
Пуассоновский
Пачечный
Рис.1.7 - Зависимости Dm (  ) для пуассоновского
потока и потока пакетов видео трафика
24
 10
Как и следовало ожидать, зависимость дисперсии для пуассоновского потока совпадает с математическим ожиданием.
Зависимость дисперсии для видео трафика не
линейна, а ее значение, при максимальной загрузке,
более, чем в 30 раз превышают соответствующее
значение для пуассоновского потока.
1.6 СРЕДНЕЕ ЧИСЛО ПОСТУПИВШИХ
ЗАЯВОК, ПРИХОДЯЩЕЕСЯ НА КАЖДУЮ
ОБРАБОТАННУЮ ЗАЯВКУ
Выделим среди всех промежутков t i , i = 1, М ,
лишь те промежутки времени t i k , k=1,K , на которых возникают очередные заявки ( mik  1 ). На каждом из указанных промежутков возникает по одной
заявке. Число заявок, поступающих за интервал
времени  , следующий непосредственно за промежутком
r 1
ti k
обозначим, как mi k ( )   mi.k  s , где
s 0
k=1,K означает порядковый номер заявки, начиная с первой заявки, на интервале времени T . Все-
го, на указанном интервале времени возникает K
заявок. Среднее число заявок, приходящееся на каждую обслуженную заявку n( ) , определяется соотношением n( ) 
1 K
 mi k ( ) , k=1,K .
K k 1
В отличие от (6), здесь усреднение производится только по промежуткам t , на которых возниik
25
кают заявки на обслуживание. Число таких промежутков K равно числу заявок на всем интервале T .
Аналогично определяется второй начальный момент n 2 ( ) числа заявок, приходящегося на одну
обслуженную заявку:
n 2 ( ) 
1 K 2
 mik ( ) .
K k 1
Следует подчеркнуть, что при определении значений n( ) , отсчет интервала  обязательно начинается непосредственно от момента поступления очередной заявки, которая не считается принадлежащей указанному интервалу. При этом отсчеты интервалов  производятся последовательно от каждой вновь поступившей заявки. Поскольку исследуется стационарный поток, выбор заявок, от которых производятся отсчеты интервалов  , может
быть произвольным.
Рассмотрим порядок выбора начальных заявок.
Все заявки расположенные на интервале времени T
делится на пачки, длительностью  . Каждая пачка
обязательно начинается с заявки. Начальная заявка
каждой очередной пачки следует за конечной заявкой предыдущей пачки. Среднее число заявок n( )
определяется как отношение суммарного числа
заявок K к общему числу пачек на интервале времени T :
26
n( ) 
K
.
N П ( )
Разделим, как и прежде, весь интервал времени
T на N ( ) промежутков, равных  . Число пачек
N П ( ) всегда будет меньше N ( ) .
Отношение P( )  N П ( ) определяет вероятность
N ( )
того, что на любом промежутке времени  присутствует одна пачка событий. Очевидно, что произведение
n( )  P( ) 
N ( )
K
K
. П

 m( )   , где,
N П ( ) N ( ) N ( )
в соответствии с (8), m( ) – это среднее число заявок, приходящееся на любой промежуток  на всем
интервале времени T . Следовательно, величина
1
n( )
 k ( ) 
P( )

характеризует неравномерность или
пачечность потока. Для пуассоновского потока указанный коэффициент равен единице, для пачечных
потоков он превышает единицу, а для потоков, с
высокой степенью детерминированности, он существенно меньше единицы.
1.7 ВЗАИМНЫЕ КОРРЕЛЯЦИОННЫЕ МОМЕНТЫ
Возникновению заявки на очередном промежутке t i сопутствует процесс ее обработки, длящийся в течение интервала времени  . При отсутствии заявки на t i ( mi  0 ), процесс обслуживания
не возникает. Теперь разделим весь рассматривае27
мый интервал времени T на N одинаковых интервалов длительностью  . Порядковый номер интервалов обозначим через i . Вследствие ординарности
потоков заявок, в течение каждого i -го интервала
времени поступает целое число заявок mi ( ) ( i = 0;
1; 2;…). Число заявок, поступающих в течение заданного времени  , является дискретной случайной
величиной с математическим ожиданием m( ) , вторым начальным моментом m2 ( ) и дисперсией
Dm ( ) .
Допустим, что в течение каждого i -го интервала
времени в СМО находится qi ( ) заявок, ожидающих в очереди. Длина очереди также является дискретной случайной величиной с математическим
ожиданием q( ) . Обозначим через qi  j ( ) элемент
последовательности случайных чисел, сдвинутый
влево относительно qi ( ) на j промежутков времени  . Значение  для каждого эксперимента задано
и остается постоянным.
Определим вторые взаимные начальные моменты последовательностей mi ( ) и qi  j ( ) , как математические ожидания произведений их соответствующих элементов:
q
i  j mi
( )  qi  j ( )mi ( ), i, j  0;1; 2...
9)
Вторые взаимные центральные моменты указанных последовательностей, называемые корреляционными моментами или ковариацией, определя28
ются, как математические ожидания произведений
центрированных значений их элементов:
Сo varqi j mi ( )  [qi  j ( )  q( )]  [mi ( )  m( )],
(10)
Между указанными моментами существует известное соотношение
q
i  j mi
( )  Сo varqi j mi ( )  q( )  m( ).
(11)
где q( )  m( ) - произведение математических
ожиданий соответствующих величин.
В дальнейшем, мы покажем, что вторые взаимные начальные и центральные моменты указанных
величин оказывают определяющее влияние на размеры очередей пачечного трафика.
29
ГЛАВА 2. ОБСЛУЖИВАНИЕ ОЧЕРЕДЕЙ
2.1 АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО
ОПРЕДЕЛЕНИЯ СРЕДНЕЙ ДЛИНЫ ОЧЕРЕДИ
В СМО
Рассмотрим предлагаемый алгоритм на конкретном примере. Предположим, что в данном эксперименте все заявки, поступающие в одноприборную СМО, имеют одинаковое постоянное время
обслуживания  и алгоритм обслуживания FIFO.
Естественно, что в другом эксперименте, время обслуживания  может иметь другое постоянное значение. Все получаемые результаты зависят от принятых значений  . Поток заявок показан на Рис.
2.1а. Числа заявок, пришедших в течение интервала времени  , не зависят от их расположения внутри интервалов. Процесс обработки заявок в такой
СМО всегда состоит из последовательности чередующихся периодов занятости обслуживающего
прибора (прибор обрабатывает заявки) и периодов
простоя, в течение которых заявки в обслуживающем приборе отсутствуют. На рис. 2.1 показан
фрагмент, соответствующий периоду занятости.
30
Предположим, что перед началом рассмотрения
СМО была свободной, поэтому с приходом первой
заявки период простоя завершается и начинается
период занятости (заявка начинает обрабатываться
обслуживающим прибором). В течение интервала
времени  вначале поступают четыре заявки Рис.
2.1б. (первая, вторая, третья и четвертая)
Рис. 2.1 - Фрагмент потока заявок в СМО
Заявка с номером 1 сразу же поступает в обслуживающий прибор, а остальные три заявки становятся в очередь (Рис. 2.1в.). В течение следующего
интервала времени  в обслуживающем приборе
находится заявка с номером 2, при этом, очередь
уменьшается на одну заявку. Аналогичное уменьшение очереди происходит при поступлении в обслуживающий прибор заявки с номером 3. В течение следующего интервала  , когда происходит
обработка 4-ой заявки, в СМО поступают еще две,
с номерами 5 и 6, которые становятся в очередь.
31
Номера интервалов обслуживания совпадают с номерами заявок, обслуживаемых на данных интервалах.
Так, последовательно происходит непрерывная
обработка всех заявок, включая заявку с номером 9.
Если интервал между очередными заявками 9 и 10
(заявка с номером 10 на Рис. 8 не показана) окажется достаточно большим, таким, что во время
обработки заявки с номером 9 не успеет поступить
очередная заявка с номером 10, то непрерывный
процесс обработки (период занятости) закончится и
наступит период простоя. Период простоя длится
до момента появления заявки с номером 10. Поступление любой заявки в систему сопровождается
появлением некоторой работы, связанной со временем, необходимым на обслуживание указанной
заявки.
Числа заявок для пуассоновского потока, с параметром   1,0 , на интервалах  , соответствующих
различным значениям коэффициента загрузки  ,
полученные в результате имитационного моделирования, были приведены на Рис.1.1.
На Рис.2.2 показаны числа заявок в очередях
для этого же потока.
Как и следовало ожидать, при малых загрузках,
на рассматриваемом временном промежутке, максимальный размер очереди не превышает одной заявки, в то время, как при единичном коэффициенте
загрузки, он составляет 10 заявок.
32
m
m
  0,1
  1,0
Рис. 2.2 - Числа заявок в очередях для пуассоновского
потока, с параметром   1,0 , на интервалах  ,
соответствующих различным значениям коэффициента
загрузки
Аналогичный характер имеют графики изменения очередей для пакетов видео трафика, представленного ранее на Рис. 1.3.
q( )
  0,1
q( )
  1,0
Рис. 2.3 - Числа пакетов в очередях для видео трафика, с
параметром  ,соответствующим различным значениям
коэффициента загрузки 
33
Числа пакетов в очередях для видео трафика, с
параметром  , соответствующим аналогичным значениям коэффициента загрузки  , показаны на
Рис.2.3.
При одинаковых загрузках, максимальные размеры очередей для экспоненциального потока
(Рис. 2.2) и потока видео трафика (Рис. 2.3) отличаются более, чем на два порядка!
Аналогично, отличаются зависимости среднего
значения очередей, для экспоненциального потока
и потока видео трафика, представленные ранее на
Рис. 1.5.
2.2 СРЕДНЯЯ ДОЛЯ НЕДООБСЛУЖЕННЫХ
ЗАЯВОК
Одной из фундаментальных характеристик
СМО является среднее время дообслуживания заявок T0 [3]. Оно определяет среднее время, необходимое для завершения обслуживания ранее выбранной заявки. Это время, в частности, учитывает,
что на момент поступления очередной заявки в
СМО может не оказаться ни одной заявки, то есть
предыдущая заявка была обслужена полностью, и
время ее дообслуживания равно нулю. В [8] показано, что среднее время W ожидания в очереди любой из заявок, в случае бесприоритетного обслуживания пуассоновских потоков, пропорционально
значению T0 :
34
W
T0
1 
(12)
где  – коэффициент загрузки. Если принять
время обслуживания всех заявок постоянным и
равным  , то средняя длина очереди q( ) , в соответствии с теоремой Литтла, определяется соотношением
q( ) 
  T0 ( )
,
1 
(13)
где  – параметр интенсивности потока заявок.
Обозначим выражение, стоящее в числителе (13)
через величину a( ) , которая представляет собой
среднюю долю недообслуживания заявок. В дальнейшем мы покажем, что она определяет среднюю
длину очереди q( ) , образуемую пачками заявок,
поступающих в течение промежутков времени  ,
при условии, что каждая из пачек успевает полностью обработаться до поступления заявок следующей пачки.
Рассмотрим пачечный поток заявок, поступающих в СМО в течение достаточно большого промежутка времени T (см. Рис. 2.4). Длительность
каждого интервала времени обработки выберем постоянной и равной  . Разделим весь промежуток
времени T на N одинаковых интервалов времени,
длительностью  . Значения m j ( ) j  1...N представляют числа заявок, поступающих на каждом интервале (число заявок в пачке). Некоторые «пачки»
35
могут иметь нулевое количество заявок. Так, в течение первого интервала поступает m1 ( )  4 заявки,
причем заявка с номером 1 сразу же поступит на
обработку, поскольку она застает обслуживающий
прибор свободным.
Рис. 2.4 - Пачечный поток заявок в СМО
Появление заявок на первом интервале приведет
к возникновению очереди. Суммарную очередь,
возникающую в период обслуживания j -ой пачки,
при условии, что первая заявка застает обслуживающий прибор свободным, а в период обслуживания всех заявок пачки, других заявок не поступает,
назовем числом недообслуженных заявок в пачке:
a j ( ) 
36
m j ( )
m j ( )
l 1
l 1
 q jl ( ) 
 m
j

( )  l ,
(14)
где l – порядковый номер заявки в j -ой пачке,
j = 1, N П . Сумма элементов в (14) представляет собой сумму членов убывающей арифметической
прогрессии. Следовательно,
a j ( ) 
m 2j ( )  m j ( )
2
.
(15)
Общее число заявок на рассматриваемом интервале времени T равно
N
K   mj
.
j 1
Суммируя значения a j ( ) по всем интервалам,
определим среднее значение числа недообслуживания, приходящееся на один интервал обслуживания, как
a( ) 
N
N
j 1
j 1
 m2j ( )   m j ( )
2 N

m2 ( )  m ( )
.
2
(16)
2.3 ДООБСЛУЖИВАНИЕ ОЧЕРЕДЕЙ
Если рассмотренное выше условие не выполняется и поступающие заявки последующей пачки
вынуждены ожидать окончания обработки всех
заявок предыдущих пачек, то возникает некоторая
дополнительная доля недообслуживания d j ( ) , показанная на рис. 2.5.
На Рис. 2.5а показано поступление заявок с номерами 5 и 6 в период обработки заявки с номером
37
2. Указанные заявки остаются в очереди до момента освобождения обслуживающего прибора, то есть
в нашем случае, до момента окончания обработки
заявки, с номером четыре. На Рис. 2.5б и 2.5в показано поступление указанных заявок в моменты обработки заявок, с номерами 3 и 4 соответственно.
Площадь образуемых прямоугольников соответствует дополнительному дообслуживанию, возникающему из-за взаимного влияния пачек заявок.
Очередь размером q j 1 на промежутке, предшествующем появлению пачки m j должна полностью
обработаться. Поэтому обработка пачки m j начинается с задержкой, равной q j 1 промежутков.
Рис. 2.5 Образование дополнительной доли
недообслуживания
Из рис. 2.5в следует, что для определения площадей рассматриваемых прямоугольников может
быть получено рекуррентное соотношение:
di ( )  qi 1 ( )  mi ( )
38
(17)
Средняя доля дообслуживания, приходящаяся
на один интервал обслуживания, есть
N
d ( ) 
 di ( )
i 1
N
N

 qi 1 ( )  mi ( ) 



i 1
N
 Сo varq m ( )  q( )  m( ).
i j
i

(18)
2.4 УРАВНЕНИЕ БАЛАНСА
Для любой одноприборной СМО справедливо
рекуррентное соотношение, устанавливающее
связь между поступающими и обработанными заявками:
qi ( )  qi 1 ( )  mi ( )   i ( ).
0, если qi 1 ( )  mi ( )  0 ;
 i ( )  
1 в противном случае.
(19)
(20)
Обратим внимание на некоторые особенности
 i ( ) :
 i2 ( )   i ( );
 i ( )mi ( )  mi ( );
(21)
 i ( )  m( ),
 i ( )qi 1 ( )  qi 1 ( ).
Предпоследнее равенство легко получить, найдя
математическое ожидание левой и правой частей
(19).
Возведем в квадрат левую и правую части (19) и
найдем математические ожидания от полученных
39
выражений. С учетом (11) получим
m 2 ( ) - m( )

2
Сo varqi j mi ( )  q( )  m( ).
q( ) 
(22)
Откуда,
q( ) 
m( )   m( )  1  Dm ( )  2Сo varqi j mi ( )
2 1  m( ) 
,
(23)
где Dm ( ) – дисперсия mi . Тогда, окончательно,
q( ) 
Dm ( )  2Сo varqi j mi ( )
2[1  m( )]

m( )
.
2
(24)
Обратим внимание, что в формулу (22) входят
составляющими средняя доля недообслуженных
заявок a( ) и средняя доля дообслуживания заявок
d ( ) , которые вместе и формируют среднюю длину
очереди q( ) .
Учитывая, что m( )   , получим окончательно:
q(  ) 
Dm (  )  2Сo varqi j mi ( )
2(1   )


2
.
(25)
Соотношение (25) обобщает формулу ХинчинаПоллячека и справедливо для любых стационарных
40
и ординарных потоков заявок, при постоянном
времени обслуживания  .
Обозначим Sm (  )  Dm (  )  2q (  ) , а
i-1;mi
Em (  )  Sm (  )   (1   )
Тогда,
q(  ) 
Sm (  ) 
E ( )
.
  m
2(1   ) 2 2(1   )
(26)
(27)
Очевидно, что для пуассоновского потока,
Sm (  )  Dm (  )   , а Em (  )   2 .
Выражение (26) дает простой алгоритм определения Sm (  ) .
На основании уравнения баланса (19), последовательно находятся значения qi1 (  ) и [mi (  )   ] , усредняются их произведения и полученный результат суммируется с дисперсией Dm (  ) .
Формула ( 27) также дает возможность непосредственно определить значения Sm (  ) и Em (  ) :
Sm (  )  [2q(  )   ](1   ) и Em (  )  2q(  )(1   ) . (28)
Однако, в результате значительных погрешностей имитационного моделирования при больших
коэффициентах загрузки, формула дает хорошие
результаты лишь в диапазоне изменения  от 0,1до
0.5.
41
На Рис. 2.6 показаны графики изменения Sm (  )
для экспоненциального потока и потока пакетов
видео трафика.
Зависимости Sm (  ) и Em (  ) могут быть аппроксимирована и из них определены характеристические коэффициенты потока заявок общего вида.
Sm (  )
Sm (  )
 10
 10
Экспоненциальный
Видеотрафик
Рис.2.6 - Зависимости Sm (  ) для экспоненциального
потока и потока пакетов видео трафика
2.5 АВТОКОРРЕЛЯЦИОННЫЕ МОМЕНТЫ
Для определения значений Сo varq
i  j mi
( ) , выразим
qi 1 ( ) через значения чисел заявок на предыдущих
интервалах. Рассмотрим участок с достаточно
большим числом интервалов N. Очевидно, что при
42
Сo varqi j mi ( ) 
усреднении
1 N
 qi1 ( ) [mi ( )  m( )] .
N i 1
(29)
Используя метод математической индукции,
получим:
N
N
j 1
j 1
qi 1 ( )  qi ( N 1) ( )   mi  j ( )    i  j ( ) .
После подстановки в (10)
Сo varqi j mi ( ) 
N
+1
N
 m
N
i 1 j 1
N
i j
1
N
q
i 1
i  ( N 1)
( )  [mi ( )  m( )] 
( )  [mi ( )  m( )] 
 [mi ( )  m( )]
i 1
N
1
N
N

j 1
i j
(30)
( ).
Учитывая, что значения qi ( N 1) ( ) и mi ( ) находятся на промежутках, удаленных друг от друга на
( N  1) интервалов, значение N всегда можно выбрать настолько большим, чтобы корреляционные
связи между указанными величинами отсутствовали. Следовательно, первое слагаемое в выражении
(30) равно нулю.
Не трудно показать, что нулю равно и третье
слагаемое, поскольку
1 N
 i j ( )  m( )   ( ). Второе
N j 1
43
слагаемое представляет автокорреляцию между
значениями
и
mi ( )
mi  j ( )
i, j  1, N :
Сo varmi mi j ( ) 
1 N N
 mi j ( )  mi ( )  m( ). Итак, убежN j 1 i 1
даемся,
Сo varqi1mi ( )(
что
N
1
1
Сo varmi mi j ( )  Сo varm ( ) .

2 i , j 1
2
Подставив указанный результат в (24), получим
q( ) 
Dm ( )  Сo varm ( ) m( )

,
2
2[1  m( )]
(31)
или, с учетом (8)
q(  ) 
где rm (  ) 
Dm (  )  1  rm (  ) 
2(1   )


2
,
(32)
Сo varm (  )
– суммарный приведенный
Dm (  )
коэффициент автокорреляции значений mi (  ) .
Соотношение (32) обобщает формулу ХинчинаПоллячека и справедливо для любых стационарных
и ординарных потоков заявок при постоянном времени обслуживания  . Действительно, формула
Хинчина-Поллячека справедлива только при пуас44
соновском потоке, когда Dm ( )   , а rm ( )  0 . Получим
q( ) 

2(1   )


2

2
2(1   )
.
Не трудно показать, что числитель выражения
(23) определяется соотношением
Сo var( q
i 1  qi ) mi
( )  [qi 1 (  )  qi (  )][mi (  )   ].
Действительно, подставив значение qi (  ) из (19)
и производя усреднение с учетом (8), имеем:
Сo var( q
i 1  qi ) mi
(  )  Dm (  )  2Сo varqi-1;m (  )   (1   )
i
Таким образом, получено еще одно соотношение, определяющее значение очереди q( ) :
q(  ) 
Обозначим
Сo var( q
i 1  qi ) mi
( )
.
2(1   )
Sm (  )  Dm (  )  2qi-1;m (  ) ;
(33)
i
Em (  )  Dm (  )  2qi-1;m (  )   (1   ) .
i
Тогда,
q(  ) 
Sm (  ) 
E ( )
.
  m
2(1   ) 2 2(1   )
Сравнивая с (32), убеждаемся, что
Sm (  )  Dm (  )  1  rm (  ) ,
как и следовало ожидать.
Выражение (33) дает простой алгоритм определения Em (  ) : на основании уравнения баланса (19)
последовательно находятся значения qi 1 (  )  qi (  ) и
mi (  )   , а затем усредняются их произведения. Зависимость Em (  ) может быть аппроксимирована и
из нее определены характеристические коэффициенты потока заявок общего вида.
45
2.6 ЧАСТНЫЕ ПРИМЕРЫ
Рассмотрим некоторые частные случаи.
1. Интервал времени обработки  всегда остается меньше, чем минимальный промежуток времени
min между двумя соседними заявками (Рис. 2.7-1). В
этом случае в интервал  не может попасть более
одной заявки. Будем считать, что корреляционные
связи отсутствуют (rm ( )  0) . Дисперсия Dm (  ) , при
этом, определяется соотношением
Dm (  )   (1   ).
Подставляя значение для дисперсии в (25), получим, q(  )  0, что
и
следовало
ожидать.
1
t
2
t
3
t
4

t
Рис. 2.7 - Различные виды потоков заявок на
интервале обслуживания 
2. Рассмотрим пуассоновский поток заявок (Рис.
2.7-2). Для такого потока Dm (  )   . Коэффициент
46
корреляции Сo varq m (  ) для пуассоновского потока
равен нулю. После подстановки в (25) получаем
формулу Хинчина-Поллячека в ее обычном виде
(1).
3. Рассмотрим поток заявок (Рис. 2.7-3), имеющий пачечный характер, с максимальной интенсивностью поступления заявок, равной max и средней интенсивностью  . Времена обслуживания
заявок постоянны и равны  . Максимальное число
заявок, поступающих в течение интервала времени
 обозначим через mmax ( )  max   . Выберем некоторый, достаточно большой промежуток времени,
на котором подряд размещается N интервалов обслуживания. Поскольку поток носит пачечный характер, на K интервалах заявки поступают, а на остальных интервалах отсутствуют. Расположение
интервалов независимое.
Рассмотрим наихудший случай, когда на каждом из указанных K интервалов поступает одинаковое, максимально-возможное число заявок
mmax ( ) . Очевидно, что должно выполняться условие
i 1 i
K  mmax ( )  N  m( )
отношение:
K
N



или K  max  N  . Обозначим
 P,
где P – вероятность того,
max
что интервал  заполнен заявками. Обратная величина k 
1
P
характеризует пачечность потока. С
учетом сказанного, получим:
47
m( )  mmax  P       ;
Dm (  )   ( k  1) .
2
,
Поскольку расположение интервалов выбрано
независимое, коэффициент корреляции между ними равен нулю.
Подставляя значения дисперсии Dm (  ) в (25),
q(  ) 
получим:
 (k    1)
.
2(1   )
Убеждаемся в том, что повышение пачечности
потока приводит к существенному (в несколько
раз) увеличению очередей. И лишь при значениях
  k  max   1 , приходим к рассмотренному выше, первому случаю, когда очередь отсутствует
(пачки содержат не более одной заявки).
4.Рассмотрим пуассоновский поток, с коэффициентом загрузки 1 . Математическое ожидание
числа заявок на интервале  : m1 ( )  1   . Второй
начальный момент числа заявок на интервале  :
m1 (  )   (1   )
2
.
Сформируем из него пачечный поток, так, чтобы каждой заявке пуассоновского потока соответствовала узкая пачка из k заявок (Рис. 2.7-4). Примем, что kmin   , где min - минимальное расстояние
между соседними событиями в пачке.
48
Математическое ожидание числа заявок на интервале  для указанного потока : mk ( )  k  k  .
Второй начальный момент числа заявок на интервале  для указанного потока
mk (  )  Dk (  )  k 1
2
2
2
.
С другой стороны,
тельно,
m k ()  k m 1 () 
mki 2 (  )  k 2 m1i 2 (  ) .
k  (1  
Окончательно, дисперсия
2
2
2
2
1
1
Следова-
).
Dk (  )  k 2 1 (1  1 )  k 2 12  k 2 1  k  .
После подстановки в (25), с учетом взаимной
независимости пачек, получим окончательно:
q(  ) 
(k  1)    2
2(1   )
.
На Рис.2.8. показаны размеры очередей для пуассоновского и пачечного (k=5) потоков, при одинаковых загрузках.
q(  )
q(  )
 10
 10
Пуассоновский
Пачечный
Рис. 2.8 - Размеры очередей для пуассоновского и
пачечного потоков при одинаковых загрузках
49
Таблица 1.
Описание
Длина очереди
Sm (  )
Трафик общего вида.
Dm (  )  2qi1mi (  )
Интервал
времени обработки   min .
Пуассоновский поток.
 (1   )
Поток с широкими пачками k.
Поток с узкими
Пачками - k.

(k  1) 
q(  ) 
q(  )  0
q(  ) 
2
2(1   )
2
k
Sm (  ) 

2(1   ) 2
q(  ) 
q(  ) 
 (k    1)
2(1   )
(k  1)    2
2(1   )
Полученные результаты для различных потоков
представлены в Таблице 1.
2.7 МНОГОКАНАЛЬНЫЕ СМО
Рассмотрим СМО, имеющую K однотипных
приборов обслуживания. Сообщения поступают к
любому свободному прибору, в соответствии с
дисциплиной обслуживания FIFO и образуют единую очередь. Для упрощения, будем считать, как и
прежде, что времена обслуживания одинаковы. Для
такой СМО справедливо рекуррентное соотношение, устанавливающее связь между поступающими
и обработанными заявками:
50
qi ( )  qi 1 ( )  mi ( )  Ki ( ) ,
(34)
K, если qi 1 ( )  mi ( )  K ;
Ki ( )  


qi 1 ( )  mi ( )  в противном случае.
Ki ( ) -число приборов обслуживания, задейство-
ванных на i-м промежутке времени  .
В отличие от  i ( ) , случайная величина Ki ( ) может принимать не два, а K  1 различных целых
значений (включая нулевое). Если, как и прежде,
считать, mi ( )   , то загрузка одного прибора определится соотношением  
mi ( ) 
.

K
K
Математическое ожидание Ki ( )  mi ( )  K  .
В [5] показано, что для многоприборных СМО,
с пуассоновскими потоками и постоянным временем обслуживания, справедлива обобщенная формула
q(  ) 
B(  ) 
2(1   )
,
(34)
где B(  ) - вероятность того, что в системе заняты
все K приборов обслуживания. Вероятность может
быть вычислена по формуле:
51
( K  )i
 i!
B(  )  1  i K0
( K  )i

i!
i 0
K 1
( K  )i
 i!
1   i K0
( K  )i

i!
i 0
K 1
Очевидно, что для одноканальной СМО,
B(  )   , и формула пригодна для расчета очередей
одноканальных систем.
Значениям B(  ) ,полученным по указанной формуле, соответствуют результаты имитационного
моделирования пуассоновского потока, показанные
на рис. 2.9 .
B(  )
B(  )
B(  )
 10
K=1
 10
K=5
 10
K=10
Рис. 2.9 - Зависимости B(  ) пуассоновского потока для
систем с различным числом каналов
С увеличением числа приборов обслуживания,
для пуассоновских потоков, при малых загрузках,
52
наблюдается существенное уменьшение размеров
очередей.
q(  )
q(  )
 10
K=1
 10
K=10
Рис. 2.10 - Средние размеры очередей для
пуассоновских потоков, при различных числах
приборов обслуживания
К сожалению, для потоков общего вида, рассмотренная формула определения вероятности
B(  ) того, что в системе заняты все K приборов обслуживания, не применима.
Результаты имитационного моделирования по
формуле (34) подтвердили, что для рассмотренных
выше потоков, имеющих пачечный характер (видеотрафик), значения B(  ) существенно отличаются от пуассоновских.
53
B(  )
B(  )
B(  )
 10
K=1
 10
K=5
 10
K=10
Рис. 2.11 - Зависимости B(  ) пачечного потока для
систем с различным числом каналов
При одинаковой загрузке, приходящейся на
один прибор обслуживания, число каналов практически не влияет на вероятность полного занятия
всех приборов (все приборы обслуживания либо
одновременно заняты, либо одновременно свободны).
Как и следовало ожидать, при одинаковой загрузке, приходящейся на один прибор обслуживания, увеличение числа приборов не приводит к
уменьшению размеров очередей, как это происходит с пуассоновскими потоками.
54
q(  )
q(  )
 10
K=1
 10
K=10
Рис.2.12 - Средние размеры очередей для пачечных
потоков, при различных числах приборов
обслуживания
2.8 АППРОКСИМАЦИЯ
Аппроксимация производится на интервале изменения коэффициента загрузки  , в пределах от
нуля, до единицы.
Анализ результатов, представленных в таблице
1, показывает возможность аппроксимации функции Sm (  ) и Em (  ) полиномами второй степени, вида:
Sm (  )  [(  1)  (  1)  ]
Em (  )   (   )
,
,
(35)
где  и  постоянные коэффициенты.
Действительно, для пуассоновского потока
Sm (  )   , что и следо  0 , коэффициент   1 ,
вало ожидать.
55
Для потока с широкими пачками (поток 4,
Табл.1), коэффициент  =k+1, а коэффициент
  1.
Для потока с узкими пачками (поток 5, Табл.1),
коэффициент  = k-1, а коэффициент  =1. Для потоков общего вида указанные коэффициенты могут
определяться, методом наименьших квадратов отклонений. Наиболее информативными следует считать участки, соответствующие интервалу изменения коэффициента загрузки  , в пределах от 0 до
0,7.
Для многоприборных СМО, учитывая (34),
предлагается функцию E m (  ) аппроксимировать соотношением
(36)
Em (  )  B(  )(   ) ,
которое обобщает (35), пригодное для одноприборных систем. При этом значения коэффициентов
 и  , полученные для одноприборных систем,
остаются неизменными.
Для расчетов очередей следует применять формулу
q(  ) 
B(  )(   )
.
2(1   )
Функцию B(  ) предлагается аппроксимировать
степенной зависимостью:
K
(37)
B(  )   .

56
Подобная аппроксимация учитывает следующие
особенности функции:
При,   0 ,значение B(  )  0 , при   1 , значение
B(  )  1 , при К=1, B(  )   , для потоков любого вида.
Для функций B(  ) пачечного видеотрафика,
представленных на Рис. 2.11 коэффициент  следует положить равным нулю. Следовательно, размер очереди в многоканальных системах при одинаковой загрузке, приходящейся на один прибор
обслуживания, незначительно зависит от числа каналов. В то же время, для пуассоновского потока,
как это следует из Рис. 2.10, указанная зависимость
весьма значительная. Окончательная формула для
расчета средних значений очередей СМО, содержащих K приборов обслуживания, определяется
соотношением:

q(  )   K 
(     )
2(1   ) .
(38)
Таким образом, для расчета средней длины очереди в K- приборных системах, помимо коэффициента загрузки, каждый вид трафика характеризуется тремя параметрами, которые легко определяются экспериментально.
2.9 СКОРОСТЬ И ДИСПЕРСИЯ ИЗМЕНЕНИЯ
ОЧЕРЕДИ
Одним из показателей качества поддержания
сетью некоторых служб является изменчивость задержки пакетов или джиттер. Он характеризует
57
различия в задержках прохождения по определенному маршруту пакетов, принадлежащих одному
соединению.
Этот показатель имеет особое значение для тех
служб, где необходимо сохранять определенные
соотношения между временами поступления отдельных пакетов, прошедших через сеть. В литературе имеется два определения джиттера, закрепленные в стандартах: одноточечный и двухточечный. Однако часто используется и другое, не вошедшее в стандарт определение, согласно которому значение джиттера J i ( )  wi ( )  wi 1 ( ) , где
wi ( ) – задержка прохождения i-го пакета.
При постоянном времени обработки  , можно
считать, что разница задержек определяется разницей задержек в очереди:
  Ji ( )    wi ( )    wi  ( )  qi ( )  qi 1 ( )  i ( ) .
Полученное соотношение устанавливает связь
между джиттером, возникающим в рассматриваемой СМО, и приращением очереди i ( ) на i-ом
интервале  .
Найдем из соотношения (19) приращение очереди в течение i-го промежутка времени 
ui ( )  qi ( )  qi1 ( )  mi ( )   i ( ).
(39)
1
0, если qi 1 ( )  mi ( )  0 ;
 i ( )  
1 в противном случае.
Указанное приращение, отнесенное к времени  ,
определяет скорость изменения очереди на i-м
58
промежутке, а значение длины очереди на указанном промежутке, при нулевых начальных условиях,
определяется суммой:
i
i
j 0
j 0
qi ( )   u j ( )  [m j ( )   j ( )].
(40)
Случайная величина u j ( ) целочисленная, и может принимать любые положительные, и нулевые
значения, а также, отрицательные значения, равные
единице.
Таким образом, случайная величина qi ( ) , определяющая длину очереди на i-м промежутке времени, представляет сумму значений величины u j ( )
на всех промежутках, начиная с нулевого.
Известно [4], что дисперсия случайной функции Y(t) ,являющейся интегралом от случайной
функции X(t) , определяется соотношением
t
DY(t)  2 (t   )  K X (t) ( )d ( ) ,
0
где K X (t) ( ) -значение автокорреляционной функции случайной величины X(t) , при сдвиге на промежуток времени  . Размер очереди qi ( ) на i-м
промежутке является случайной величиной, представляющей сумму (40).
Дисперсия подобной суммы определяется соотношением:
59
i
Dqi ( )  2 (i  j )  Ku j ( ) ,
(41)
j 0
Ku j ( ) -
где
значение
автокорреляционной
функции случайной величины u j ( ) при сдвиге на j
промежутков времени  .
Ku j ( )  ui j ( )  ui ( )
2.10 МУЛЬТИПЛЕКСИРОВАНИЕ
Известно, что математические ожидания, дисперсии, коэффициенты корреляции и коэффициенты загрузки сумм независимых потоков заявок равны сумме значений соответствующих величин исходных потоков. Соотношение (24) позволяет легко получить выражение для суммарной очереди от
Q независимых потоков, при их мультиплексировании:
Q
Dm ( )   Dmj ( ) ,
j 1
Q
Сo varm ( )   Сo varmj ( ) ,
j 1
Q
R ( )    j ( ) .
j 1
Следовательно
q m( ) 
Dm ( )  R ( )[1  R ( )]  2Сo varm ( )
2[1  R ( )]
(42)
или,
60
q m( ) 
Dm ( )  2Сo varm ( ) R ( )

.
2[1  R ( )]
2
Указанное соотношение справедливо при суммировании любого числа потоков заявок с одинаковыми приоритетами и одинаковыми временами обслуживания  .
При суммировании Q одинаковых независимых
потоков, получим:
Q  [ Dm ( )  2Сo varm ( )] Q ( )
.

2[1  Q ( )]
2
q m( ) 
Если суммируются потоки с различными постоянными временами обслуживания, то предлагается
определить суммарные величины для каждого из
значений  j . j = 1, 2,…Q:
Q
Q
q 1
q 1
Dm ( j )   Dmq ( j ) ; Сo varm ( j )   Сo varmq ( j ) ;
Q
Q
q 1
q 1
R ( j )    q ( j )   q j  j ,
а затем, определить их математические ожидания, с учетом вероятностей появления заявки каждого типа:
Q
j
j
Dm ( j ) ; Сo varm   Сo varm ( j ) ;
j 1  
j 1  
Q
Q
Q
j
R   R ( j )    j j    j .
(43)
j 1  
j 1
j 1
Q
Dm  
Как и следовало ожидать, коэффициенты загрузки суммируются.
Учитывая, что все характеристики определяются, в зависимости от коэффициентов загрузки, воз61
можен и другой способ мультиплексирования.
Предлагается, для каждого из потоков определять
значения
дисперсии Dmj ( R )
и
ковариации
Сo varmj ( R ) на интервалах времени  j 
R
J
 j , соот-
ветствующих суммарному коэффициенту загрузки R .
Значения
дисперсии Dm ( R )
и
ковариации Сo varm ( R ) для суммарного потока определятся,
в соответствии с долями загрузки, создаваемыми
каждым из потоков:
Q
j
j 1
R
Q
j
j 1
R
Dm ( R )  
Сo varm ( R )  
Dmj ( R ) ;
Сo varmj ( R ) .
Аналогично, определяются значения для характеQ
j
j 1
R
ристики Sm ( R )  
Smj ( R ) .
2.11 ОТНОСИТЕЛЬНЫЕ ПРИОРИТЕТЫ
Приоритеты заявок характеризуются целыми
положительными числами 1; 2 … причем высокому
приоритету соответствует меньшее число. При относительном приоритете, обслуживание заявки не
прерывается, если даже в очередь поступила заявка
более высокого приоритета.
62
Обозначим числитель выражения (42) через
qL ( ) , и назовем его «латентной очередью». Латентная очередь возникает в тех случаях, когда заявки
любого типа, поступившие в течение промежутка
времени обработки  , успевают полностью обслужиться, до прихода в систему следующей очередной заявки. Значение латентной длины очереди не
зависит от дисциплины обслуживания, так как все
заявки, поступившие на промежутке времени  ,
успевают полностью обслужиться до поступления
следующих заявок. Латентная очередь является минимальной, поскольку заявки, поступающие на последующих промежутках времени  , не мешают обслуживанию ранее поступивших заявок. Если указанное условие не выполняется, то очередь будет
увеличиваться, по сравнению с «латентной»:
qmQ ( ) 
qL ( )
.
2 1  RQ ( ) 
(44)
Допустим, что в системе обслуживается Q потоков, с K различными приоритетами и латентной
очередью qL ( ) . Обозначим через qmk ( ) – суммарную длину очереди всех заявок, с приоритетами не
ниже k, где k = 1; 2 … K. Поскольку на размер указанной очереди влияют только заявки, имеющие
приоритеты не ниже k, в формулу (42) следует вместо R ( ) подставить коэффициент загрузки именно
k
указанными заявками Rk ( )    j ( ) .
j 1
63
В результате,
qmk ( ) 
qL ( )
.
2 1  Rk ( )
(45)
Среднее число заявок с приоритетом k, находящихся в очереди, есть qmk ( )  qmk ( )  qm( k 1) ( ) . После подстановки значений, получим окончательно:
qmk ( ) 
qL ( ) k ( )
.
2 1  Rk ( )  1  Rk 1 ( )
(46)
Соотношение (46) позволяет также легко определить среднее время wK ( ) нахождения заявки
приоритета k в очереди. Учитывая, что
qmk ( )  k  wk ( ) , где k – интенсивность заявок K-го
приоритета, получим
wk ( ) 
qL ( ) 
.
2 1  Rk ( )  1  Rk 1 ( )
(47)
Указанный результат полностью согласуется с
соотношениями, полученными для многоприоритетных пуассоновских потоков, и справедлив для
потоков общего вида. Если рассматриваются потоки с различными временами обслуживания, то соотношение (46) следует применять, с учетом (43).
Таким образом, соотношения (46) - (47) позволяют,
соответственно, определить средние размеры очередей и время ожидания в очередях потоков заявок
общего вида, при их многоприоритетном обслуживании.
64
ГЛАВА 3. РАСПРЕДЕЛЕНИЯ ЗАЯВОК
НА ИНТЕРВАЛАХ ОБСЛУЖИВАНИЯ
3.1 ОБРАЗУЮЩИЕ ФУНКЦИИ
Поток входных заявок общего вида может быть
задан функцией F1 ( )  P(1   ) распределения вероятностей интервалов  между соседними заявками.
Указанная функция определяет вероятности
P(   ) того, что    . Эту функцию распределения вероятностей назовем образующей функцией.
Аналогично, может быть определено семейство обn
разующих функций Fn (i   ) – как вероятностей
i 1
того, что сумма двух, трех и т.д. случайных временных интервалов между соседними заявками будет меньше интервала  . Это есть функции попадания некоторого числа событий в интервал  , где
под интервалом  мы понимаем постоянное время
обработки одной заявки, а отсчет времени начинается в момент появления первой заявки ( Рис. 3.1).
1
2
1
1
2
F1 ( )  P (1   )

F2 ( )  P (1  2   )


n
n
Fn ( )  P ( 1   )
i 1
Рис.3.1 - Образующие функции
Если такие функции известны, то на основании
их легко определить значения чисел n и n 2 . Обозначим через Pi ( ) вероятность того, что на интер65
вале  появится ровно i заявок. Тогда функция
1  F1 ( )  P(1   )  P0 ( ) определяет вероятность
отсутствия заявок на интервале  (не считая исходной). Это равносильно утверждению, что на
указанном интервале появится не более нуля заявок.
Аналогично функция
n
n
i 1
i 1
1  Fn ( )  P( 1   )   Pi 1 ( )
определяет вероятность того, что на интервале  появится не более, чем n – 1 заявок. Очевидно,
что разность
Fi ( )  Fi 1 ( )  Pi ( ) ,
(48)
а сумма всех вероятностей равна единице:

 P ( )  1 .
i0
i
Определим математическое ожидание n ( ) числа
заявок на интервале  :




i0
i 1
i 1


n( )   iPi ( )   iPi ( )   iFi ( )   iFi 1 ( ) 
i 1

F1 ( )   iFi ( )   (i  1) Fi 1 ( )   Fi 1 ( ) 
i2

i 1

 iF ( )   j F
i2
i
j2
j
( )  F1 ( )   Fi 1 ( ) 
i 1


i 1
i 1
F1 ( )   Fi 1 ( )   Fi ( ).
Следовательно,
66
i 1


n( )   Fi ( ).
(49)
i 1
Неожиданный результат!
Определим второй начальный момент n 2( ) числа заявок на интервале  :



i0
i0
2
2
2
2
n ( )   i Pi ( )   i Fi ( )   i Fi 1 ( ) 
i0



2
2
 i Fi ( )   (i  1) Fi 1 ( )  2  iFi 1 ( )
i0
i0

i0


  Fi 1 ( )  2 iFi 1 ( )   Fi 1 ( ) 
i0
i 1
50)
i0



i 1
i 1
i 1
2 iFi 1 ( )   Fi ( )  2 iFi 1 ( )  n( ).
По аналогии с (16), получим соотношение, определяющее среднее значение недообслуживания,
приходящееся на один интервал обслуживания
заявки  :
2
n ( )  n ( ) 
  iFi 1 ( ) .
2
i 1
(51)
Измерение интервала обслуживания  всегда
начинается от момента поступления заявки на вход
СМО. В отличие от (16), вычисления производятся,
исходя из образующих функций распределения вероятностей интервалов  между соседними заявками исследуемого потока. Указанные функции
F ( ) могут быть заданы аналитически.
i
67
3.2 Г-РАСПРЕДЕЛЕНИЕ ИНТЕРВАЛОВ
МЕЖДУ ЗАЯВКАМИ
Мы предлагаем аппроксимировать семейства
образующих функций семейством функций Граспределения. Функция Г-распределения хорошо
известна. Она определяется двумя параметрами: 
– средний интервал времени между двумя соседними заявками поступления заявок и η – величина,
обратная квадрату коэффициента вариации распределения интервалов между заявками.  

2
D
. Кроме
того, используется параметр средней интенсивности  
1

:

( ) 1  e
F1 ( )  
d .
Г ( )
0
(52)
Почему такая функция была выбрана? Вопервых, потому, что экспоненциальное распределение является частным случаем Г-распределения
(при η = 1). Главное же заключается в том, что
функция Fn ( ) получается из функции F1 ( ) простым умножением показателя η на величину n.
Действительно, исходное выражение для функции

(n n )n 1  ennn n
Fn ( )  
d .
Г (n )
0
68
Учитывая, что  n  n ,а n  n , получим

( )n 1  e
Fn ( )  
d .
Г (n )
0
Введем переменную x   и получим окончательно
Fn ( ) 


0
( x) n 1  e x
dx 
Г (n )


0
x n 1  e x
dx . 53)
Г (n )
Рис. 3.2 - Семейство образующих функций F(λτ)
Такая аппроксимация позволяет анализировать
уже не только экспоненциальные входные потоки,
но и потоки, с самыми различными коэффициентами вариации интервалов.
69
На Рис. 3.2 показано семейство функций распределения вероятностей при различных значениях
коэффициента η (η – величина, обратная квадрату
коэффициента вариации  2 ). Чем меньше коэффициент η, то есть чем больше его обратная величина
– коэффициент вариации, тем круче идут графики
указанных функций. Все они, так же, как и экспоненциальное распределение, описываются единым
уравнением. Зная эти функции, мы легко можем
вычислять вероятности появления n событий на
интервале τ, в соответствии с (48):
Pn ( )  Fn ( )  Fn1 ( ) ;
Pn ( ) 


0


0
( x)
( x) n 1  e  x
dx 
Г (n )
 e x
dx .
Г [(n+1) ]
( n 1) 1
(54)
При экспоненциальном распределении (η = 1)
получаем закон Пуассона в его обычном виде. Стало быть, указанное соотношение – это в интегральной форме обобщенный закон Пуассона, где мы
получаем вероятность появления n событий на интервале τ при заданных значениях параметров Граспределения.
На Рис. 3.3 показаны вероятности попадания n
событий в узкий временной интервал, соответствующий 

 0,1 . Для экспоненциального потока (η

= 1) вероятность попадания двух или более собы70
тии в указанный интервал крайне мала. В то же
время вероятность попадания двух событии для потока с коэффициентом вариации  2 =5 (η = 0,2)
значительно выше и соответствует 0,2. Это может
вызвать появление очередей.
Используя образующие функции получим простые соотношения для определения значений n ( )
и n2 ( ) , фигурирующих в формулах (49) и (51):


i 1
i 1
n2 ( )   i 2 Pi ( ) ; n( )   Fi ( ) .
Для вычисления n( ) необходимо просуммировать несколько образующих функций.
Рис. 3.3 - Вероятности Pn для различных η
71
Соответствующее выражение было получено и
для Г-распределения:
 
n ( )   
i 1 0

( x)i 1  e x
dx  
Г (i )
i 1


0
xi 1e x
dx .(55)
Г (i )
Значения по нему были рассчитаны для потоков
с различными коэффициентами вариации, и показаны на Рис. 3.4 – откуда следует, что для экспоненциального потока n( ) = λτ, что приводило
часто к путанице. На графике это прямая линия под
углом 450. Однако если мы начнем увеличивать коэффициент вариации, например до 5, то среднее
число поступающих заявок, приходящихся на одну
обработанную заявку, резко увеличивается.
Рис. 3.4 - Зависимости n( ) от λτ
72
При коэффициенте загрузки λτ = 0,4 на каждую
обработанную заявку приходится в среднем одна
необработанная. Это еще не означает, что система
неустойчива. Необработанные заявки будут образовывать очереди и обрабатываются в те промежутки времени, когда обслуживающий прибое свободен. Аналогичные соотношения были получены
нами для второго начального момента на основании (51).
Величина n( ) определяется соотношением:
2
( )  n ( )
n( )  n

2
 

i 1 0

 e x
dx  
[(i+1) ]
i 1
i ( x)
( i 1) 1


0
i  x (i 1) 1  e x
dx.
[(i+1) ]
(56)
На Рис. 3.5 показаны зависимости n( ) от λτ.
Рис. 3.5 - Зависимости n( ) от λτ
73
Значения для n( ) были рассчитаны нами для
потоков с различными коэффициентами вариации
 2 . Для экспоненциального потока ( 2 = 1) эта
кривая представляет собой квадратную параболу,
что и следовало ожидать. Если для экспоненциального потока при коэффициенте загрузки λτ = 0,4 мы
имеем менее одной десятой недообслуженной заявки, то для потока с коэффициентом вариации  2
= 6 на каждую обслуженную заявку приходится
уже одна недообслуженная заявка. При этом очереди будут возрастать, даже при малых коэффициентах загрузки ρ = λτ.
Рис. 3.6 Очереди в СМО
Мы видим, что при экспоненциальном входном
потоке существенное возрастание очереди (см. рис.
3.6) происходит при коэффициенте загрузки, равном 0,9; в то время как для потока  2 = 5 аналогич74
ного значения длина очереди достигает уже при
коэффициенте загрузки λτ = 0,1. Вот почему в
мультисервисных сетях нужно быть весьма осторожным при распределении пропускной способности между различными видами трафика.
3.3 КВАЗИПУАССОНОВСКОЕ РАСПРЕДЕЛЕНИЕ
ВЕРОЯТНОСТЕЙ ЧИСЛА ЗАЯВОК
Рассмотренное выше соотношение (54) устанавливает вероятности появления заданного числа n
заявок на интервале  при Г-распределении интервалов между соседними заявками. Рассмотрим случайную величину   n  . В соответствии с (53), ее

функция распределения
F ( ) 

0
( x) 1  e  x
Г ( )
dx . До-
пустим, что случайная величина  может принимать только целочисленные значения 0 , 1, 2…. Тогда вероятность

P ( ) 

0
( x) 1  e  x
Г ( )

dx 

0
( x)  e  x
Г (  1)
dx .
(57)
Учитывая, что   ( x) 1  e x dx   ( x)  e x dx  ( x)  e x
согласно [5], а также
Г (  1) = Г ( )   !,
имеет ме75
( x)  e x ( x)  e x
сто P ( ) 
– закон Пуассона для

Г (  1)
!
целых  . После подстановки значений   n  , по-
лучим
Pn ( ) 
( ) n  e 
,
Г (n    1)
(58)


где n  ,  = 0; 1; 2 … Закон распределения
вероятностей, подчиняющийся (58), назовем квазипуассоновским.
Ранее под величиной ni понималось целое число
событий, произошедших на интервале  , не считая
первого события, совпадающего с началом отсчета
интервала  . Это число совпадает с целым числом
интервалов  j , укладывающихся на интервале  . В
общем случае, на указанном интервале может разместиться не целое число интервалов  j между заявками, поэтому, представим величину ni в виде
суммы целой и дробной частей ni   i   i ,  i = 0; 1;
2 …; 0   i  1 . Если   i , то целая часть  i  0 . Если   i то целая часть, то есть  i . определяется из
целочисленного уравнения

i

j 0
 1.
i j
Дробная часть  i показывает долю от интервала
i  , которую составляет остаток. Таким образом,
i
76
становится ясным физический смысл нецелых значений n , получаемых в (58).
Напомним, что  есть величина, обратная коэффициенту вариации интервалов между соседними заявками исходного потока, при Граспределении интервалов, которая может принимать любые значения. В частном случае, при экспоненциальном распределении интервалов,   1
и мы приходим к закону Пуассона в его обычном
виде
( )n  e 
,
Pn ( ) 
(n)!
Следовательно, (58) обобщает закон Пуассона
на не экспоненциальные потоки, заданные Граспределением интервалов между заявками с произвольным коэффициентом вариации.
3.4 Г-РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ ЧИСЛА
ЗАЯВОК НА ИНТЕРВАЛЕ 
Предлагается плотность распределения f m ( ) –
вероятностей числа заявок на интервале  представить в виде Г-распределения:
m
f m ( ) 
где: m 
(
m
m 1
m)
e

(m )
m
m
m

m
m
,
(59)
[m( )]2
, а m  m( ) и Dm ( ) – математиDm ( )
ческое ожидание и дисперсия числа заявок на ин77
тервале  , соответственно. Нетрудно показать, что
сумма значений всех вероятностей равна единице.
Дробные значения числа заявок следует понимать в рассмотренном выше смысле. Вероятности
Pm ( ) поступления целых чисел заявок определяются соотношением
m
Pm ( ) 

m
1
2
m
(
m
m 1
x)
e

m
m
( m )
1
2
x

m
m
dx
.
(60)
где m = 1; 2; 3… Предположим, что суммарный
поток включает в себя K потоков различной активности. Поток k-го вида характеризуется распределением вероятностей Pkn ( ) числа заявок m, поступающих в течение интервалов  . (это условные
распределения вероятностей, полученные при условии, что рассматриваются периоды, соответствующие потоку k-го вида).
Поток каждого k-го вида присутствует в течение
суммарного времени Tk :
Pk 
Tk
K
T
i 1

Tk
,
T
(61)
i
где T – весь исследуемый промежуток времени.
Суммарное распределение вероятностей числа заявок, учитывающее все промежутки активности,
K
Pn ( )   k Pk  Pnk ( ).
(62)
78
3.5 ГИПЕРПУАССОНОВСКОЕ
РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ ЧИСЛА
ЗАЯВОК НА ИНТЕРВАЛЕ 
Предположим, что составляющие потоки k-го
вида характеризуются квазипуассоновскими распределениями числа заявок, соответствующими
(54). Тогда
Pn ( ) 

K
 P [

( k x )
0
( n 1) k 1
n k 1
e
k
 k x
k
dx 
(63)
 k x
Г [(n+1) k ]
0
e
Г (n k )
k
k

( k x )
dx ]
назовем гиперпуассоновский распределением.
Наиболее простой формулой гиперпуассоновского распределения является распределение второго порядка (k = 2). Оно имеет пять независимых
параметров:

Pn ( )  P1[ 
0

 (1  P1 )[ 
0
(1 x) n 1  e  x1
1
1
Г (n1 )
Г (n 2 )
dx  
0
( 2 x) n 1  e  x 2
2

2

dx 

0
(1 x)( n 1) 1  e
1
 k x
Г [(n+1)1 ]
1
dx] 
(2 x)( n 1)2 1  ek x2
dx].
Г [(n+1) 2 ]
(64) Работу одноприборной СМО можно часто
охарактеризовать двумя чередующимися интервалами времени. В течение первого интервала прибор
находится в режиме обслуживания заявок, а в течение последующего интервала – прибор находится в
79
состоянии простоя, в связи с отсутствием поступающих заявок. Предположим, что в течение интервалов занятости на вход СМО поступает гиперпуассоновский поток, в то время, как в периоды
простоя заявки не поступают. Таким образом, весь
поток заявок рассматривается как двухфазный, с
последовательным чередованием фаз.
Квазипуассоновское распределение заявок на
интервалах занятости можно рассматривать как условное, при условии, что прибор обслуживания находится в состоянии занятости. Вероятность этого
состояния определяется коэффициентом загрузки
 . Вероятность состояния простоя равна (1   ) . В
состоянии простоя заявки на вход не поступают.
В соответствии с (59), мы получили гиперпуассоновское распределение второго порядка, где
P1  (1   ) , а условное распределение вероятностей
числа заявок на интервале простоя является вырожденным:
Pn1 ( )   (n) ,
где
(65)
1  при n  0;
0  при n  0.
 (n)  {
Обозначим через Pn 2 ( ) условное квазипуассоновское распределение вероятностей случайной
величины n на фазе занятости. Тогда общее распределение вероятностей, с учетом наличия интервалов простоя, определится соотношением
80
Pn ( )   (n)  (1   )   Pn 2 ( ) , где  n  0,1, 2.... 66)
Нетрудно показать, что сумма значений всех ве
роятностей равна единице:  n0 Pn ( )  1 , m  0,1, 2...
Подставляя значения из (53), получим
( )n  e
1 2
, n  0, , .... 67)
Г (n   1)
 
Pn ( )   [n]  (1   )  
Соотношение (67) предполагает наличие Граспределения интервалов между заявками на интервалах занятости и учитывает наличие интервалов простоя, когда заявки в систему не поступают.
3.6 ГИПЕР Г-РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ
ЧИСЛА ЗАЯВОК НА ИНТЕРВАЛЕ 
Предположим, что составляющие потоки k-го
вида
характеризуются
независимыми
Граспределениями числа заявок, соответствующими
(62). Тогда
K
Рm ( )   Pk
k
1
m
2

1
m
2
mk
(
mk
mk 1 mk x
e mk 
x)
(mk )
mk
mk
dx
(68)
Нетрудно показать, что для такого распределения выполняются соотношения
K
K
k
k
m   Pk mk ; Dm ( )   Pk Dmk ( ) .
81
Наиболее простой формулой гипер Граспределения является распределение второго порядка (K = 2):
m

Рm ( )  P1
m

 (1  P1 )
1
2
m
(
1
m
2
1
2
1
m
2
m
(
1
m1
x)m1 1  e

 m1
m1
x

m
1
m1
dx

( m1 )
2
m2
x)m 2 1  e

( m 2 )
m 2
m2
(69)
x

m
2
m2
dx
,
где m = 0; 1; 2…
Трафик МСС характеризуется чередующимися
периодами активного и пассивного режимов поступления пакетов. Пассивный режим имеет весьма
малую среднюю интенсивность и высокую неравномерность поступления пакетов. Такому режиму
соответствуют малые значения математического
ожидания числа пакетов m1 ( ) , поступающих в течение интервала  , малые значения коэффициента
m ( ) и весьма большие значения дисперсии Dm ( ) .
Активный режим, наоборот, характеризуется
весьма интенсивным потоком пакетов, поступающих с максимальной, практически постоянной интенсивностью. Такому режиму соответствуют
большие значения математического ожидания числа пакетов m2 ( ) , поступающих в течение интервала
1
82
1
 , большие значения коэффициента m ( ) и весьма
малые значения дисперсии Dm ( ) .
2
2
Таким образом, весь поток заявок рассматривается как двухфазный, с последовательным чередованием фаз. Частным случаем многофазного потока
является однофазный Г-поток. Предположим, что в
течение режима активности имеется Г-поток пакетов, в то время, как в пассивном режиме заявки вообще отсутствуют. Г-распределение пакетов на интервалах активности можно рассматривать как условное, при условии, что прибор обслуживания находится в состоянии занятости. Полное отсутствие
пакетов в пассивном режиме можно считать предельным Г-распределением.
Как и прежде, разделим весь рассматриваемый
промежуток времени на N ( ) одинаковых интервалов  . Порядковые номера интервалов обозначим
через i , где i = 1; 2 … N ( ) . Числа заявок, поступающих в течение i -го интервала обозначим как
mi ( ). Предлагается модель, отображающая распределение вероятностей поступления m ( ) заявок на
интервале  . Математическое ожидание m ( ) , второй начальный момент m ( )2 и дисперсия распределения Dm ( ) .
Обозначим через N m( ) число интервалов  , в
течение которых поступило ровно m ( ) заявок,
m ( ) = 0; 1; 2… При достаточно большом объеме
83
выборки можно считать, что вероятности Pm ( ) поступления на интервалах  ровно m ( ) заявок определяется соотношением
m
Pm ( ) 
N m ( )
N ( )


1
2
m
(
1
m
2
m
m 1
m)
e

m
m
m

m
m
dm
(m )
,
(70)
где m  0,1, 2... Вероятность отсутствия заявок на
указанных интервалах обозначим как P0 ( ) 
N 0 ( )
.
N ( )
Искомое распределение вероятностей Pm ( ) представляется в виде двух составляющих, одна из которых P0 ( ) , а вторая Pm ( ) есть
Pm ( )   (m)  P0 ( )  Pm ( )[1  P0 ( )] ,
(71)
1  при m  0;
.
0  при m  0.
где  (m)  {
Окончательно,
Pm ( ) имеет вид:
распределение
вероятностей
Pm ( )   (m)  P0 ( ) 
m


1
2
1
m
2
m
(
m
m 1
x)
e

(m )
m
m
x

m
m
(72)
dx
[1  P0 ( )],
где m  0; 1; 2... Из полученных соотношений
следует, что при заданном коэффициенте загрузки
m     распределение вероятностей определяет84
ся вероятностью P0 (  ) отсутствия заявок и значениями дисперсии Dm (  ) 
2
числа заявок на интерm
вале  .
Следует подчеркнуть, что точного знания распределения числа заявок на интервале обработки 
еще недостаточно для определения средней длины
очереди. Как мы уже видели, существенное влияние оказывают корреляционные свойства потока.
Из соотношения (32) следует, что на размер очереди влияет приведенный коэффициент автокорреляции rm (  ) .
85
ГЛАВА 4. ПРОГРАММНЫЙ АНАЛИЗ
ТРАФИКА
4.1 СРЕДСТВА МОНИТОРИНГА И АНАЛИЗА
ТРАФИКА
В ходе проектирования новой или модернизации старой сети часто возникает необходимость в
количественном измерении некоторых характеристик сети таких, например, как интенсивности потоков данных по сетевым линиям связи, задержки,
возникающие на различных этапах обработки пакетов, времена реакции на запросы того или иного
вида, частота возникновения определенных событий и других характеристик.
Все многообразие средств, применяемых для
мониторинга и анализа мультисервисных сетей,
можно разделить на несколько крупных классов.
4.2 АНАЛИЗАТОРЫ ПРОТОКОЛОВ
Наиболее совершенным средством исследования сети являются анализаторы протоколов
(Protocol analyzers). Анализаторы протоколов представляют собой программные или аппаратнопрограммные системы, которые ограничиваются, в
отличие от систем управления, лишь функциями
мониторинга и анализа.
86
Системы
управления
сетью
(Network
Management Systems) - централизованные программные системы, которые собирают данные о
состоянии узлов и коммуникационных устройств
сети, а также данные о трафике, циркулирующем в
сети. Эти системы не только осуществляют мониторинг и анализ сети, но и выполняют в автоматическом или полуавтоматическом режиме действия
по управлению сетью - включение и отключение
портов устройств, изменение параметров мостов
адресных таблиц мостов, коммутаторов и маршрутизаторов и т.п. Примерами систем управления могут служить популярные системы HPOpenView,
SunNetManager, IBMNetView.
Средства
управления системой
(System
Management). Средства управления системой часто
выполняют функции, аналогичные функциям систем управления, но по отношению к другим объектам. В первом случае объектом управления является программное и аппаратное обеспечение компьютеров сети, а во втором - коммуникационное оборудование. Вместе с тем, некоторые функции этих
двух видов систем управления могут дублироваться, например, средства управления системой могут
выполнять простейший анализ сетевого трафика.
87
Встроенные системы диагностики и управления (Embeddedsystems). Эти системы выполняются
в виде программно-аппаратных модулей, устанавливаемых в коммуникационное оборудование, а
также в виде программных модулей, встроенных в
операционные системы. Они выполняют функции
диагностики и управления только одним устройством, и в этом их основное отличие от централизованных систем управления. Примером средств этого класса может служить модуль управления концентратором Distrebuted 5000, реализующий функции автосегментации портов при обнаружении неисправностей, приписывания портов внутренним
сегментам концентратора и некоторые другие. Как
правило, встроенные модули управления "по совместительству" выполняют роль SNMP-агентов,
поставляющих данные о состоянии устройства для
систем управления.
Хороший анализатор протоколов может захватывать и декодировать пакеты большого количества протоколов, применяемых в сетях - обычно несколько десятков. Анализаторы протоколов позволяют установить некоторые логические условия
для захвата отдельных пакетов и выполняют полное декодирование захваченных пакетов, то есть
88
показывают в удобной для специалиста форме
вложенность пакетов протоколов разных уровней
друг в друга, с расшифровкой содержания отдельных полей каждого пакета.
Процесс анализа протоколов включает захват
циркулирующих в сети пакетов, реализующих тот
или иной сетевой протокол, и изучение содержимого этих пакетов. Основываясь на результатах анализа, можно осуществлять обоснованное и взвешенное изменение каких-либо компонент сети, оптимизацию ее производительности, поиск и устранение неполадок. Очевидно, что для того, чтобы
сделать какие-либо выводы о влиянии некоторого
изменения на сеть, необходимо выполнить анализ
протоколов и до, и после внесения изменения.
Анализатор протоколов представляет собой либо самостоятельное специализированное устройство, либо персональный компьютер, обычно переносной, класса Notebook, оснащенный специальной
сетевой картой и соответствующим программным
обеспечением. Применяемые сетевая карта и программное обеспечение должны соответствовать топологии сети (кольцо, шина, звезда). Анализатор
подключается к сети точно также, как и обычный
узел. Отличие состоит в том, что анализатор может
принимать все пакеты данных, передаваемые по
89
сети, в то время как обычная станция - только адресованные ей. Программное обеспечение анализатора состоит из ядра, поддерживающего работу сетевого адаптера и декодирующего получаемые данные, и дополнительного программного кода, зависящего от типа топологии исследуемой сети. Кроме
того, поставляется ряд процедур декодирования,
ориентированных на определенный протокол, например, IPX. В состав некоторых анализаторов может входить также экспертная система, которая
может выдавать пользователю рекомендации о том,
какие эксперименты следует проводить в данной
ситуации, что могут означать те или иные результаты измерений, как устранить некоторые виды неисправности сети.
Несмотря на относительное многообразие анализаторов протоколов, представленных на рынке,
можно назвать некоторые черты, в той или иной
мере присущие всем им:
Пользовательский интерфейс.
Большинство анализаторов имеют развитый
дружественный интерфейс, базирующийся, как
правило, на Windows или Motif. Этот интерфейс
90
позволяет пользователю: выводить результаты анализа интенсивности трафика; получать мгновенную
и усредненную статистическую оценку производительности сети; задавать определенные события и
критические ситуации для отслеживания их возникновения; производить декодирование протоколов разного уровня и представлять в понятной
форме содержимое пакетов.
Буфер захвата.
Буферы различных анализаторов отличаются по
объему. Буфер может располагаться на устанавливаемой сетевой карте, либо для него может быть
отведено место в оперативной памяти одного из
компьютеров сети. Если буфер расположен на сетевой карте, то управление им осуществляется аппаратно, и за счет этого скорость ввода повышается. Однако это приводит к удорожанию анализатора. В случае недостаточной производительности
процедуры захвата, часть информации будет теряться, и анализ будет невозможен. Размер буфера
определяет возможности анализа по более или менее представительным выборкам захватываемых
данных. Но, каким бы большим ни был буфер захвата, рано или поздно он заполнится. В этом слу91
чае либо прекращается захват, либо заполнение начинается с начала буфера.
Фильтры.
Фильтры позволяют управлять процессом захвата данных, и, тем самым, позволяют экономить
пространство буфера. В зависимости от значения
определенных полей пакета, заданных в виде условия фильтрации, пакет либо игнорируется, либо записывается в буфер захвата. Использование фильтров значительно ускоряет и упрощает анализ, так
как исключает просмотр ненужных в данный момент пакетов.
Переключатели - это задаваемые оператором
некоторые условия начала и прекращения процесса
захвата данных из сети. Такими условиями могут
быть выполнение ручных команд запуска и остановки процесса захвата, время суток, продолжительность процесса захвата, появление определенных значений в кадрах данных. Переключатели могут использоваться совместно с фильтрами, позволяя более детально и тонко проводить анализ, а
также продуктивнее использовать ограниченный
объем буфера захвата.
92
Методология проведения анализа может быть
представлена в виде следующих пяти этапов:
1. Захват данных.
2. Просмотр захваченных данных.
3. Анализ данных.
4. Поиск ошибок. (Большинство анализаторов
облегчают эту работу, определяя типы ошибок и
идентифицируя станцию, от которой пришел пакет
с ошибкой.)
5. Исследование производительности. Рассчитывается коэффициент использования пропускной
способности сети или среднее время реакции на запрос.
4.3 АНАЛИЗАТОР ПРОТОКОЛОВ WIRESHARK
Из всего многообразия существующих анализаторов, для целей анализа трафика, был выбран
Wireshark [9].
WireShark представляет собой анализатор сетевых протоколов с графическим интерфейсом
(GUI). Программа позволяет просматривать и анализировать пакеты, полученные из сетевого интерфейса или ранее собранного файла.
В Wireshark по умолчанию используется для
файлов захвата формат libpcap, используемый про93
граммой tcpdump и другими анализаторами. Кроме
того, Wireshark может читать файлы в форматах
snoop и atmsnoop, Shomiti/Finisar Surveyor, Novell
LANalyzer, Network General/Network Associates
Sniffer2 (DOS-версии), Microsoft Network Monitor,
AIX iptrace, Cinco Networks NetXRay, Network Associates Sniffer (Windows-версии), и ряда других.
Программе даже не нужно указывать тип исходного файла, она распознает форматы автоматически.
Wireshark может также читать файлы перечисленных выше форматов, сжатые с использованием
gzip.
Подобно другим анализаторам протоколов, окно Wireshark включает 3 области просмотра с разными уровнями детализации. Верхнее окно содержит список собранных пакетов с кратким описанием, в среднем окне показывается дерево протоколов, инкапсулированных в кадр. Ветви дерева могут быть раскрыты для повышения уровня детализации выбранного протокола. Последнее окно содержит дамп пакета в шестнадцатеричном и текстовом представлении.
94
Рис. 4.1 - Интерфейс программы WireShark
Рис. 4.2 - Статистика трафика между парами хостов IP
95
Команда IO-Stat открывает одноименное диалоговое, содержащее до 5 графиков, выведенных различными цветами и показывающих число пакетов или байтов в секунду для кадров, соответствующих каждому из пяти поддерживаемых
фильтров. По умолчанию выводится один график,
показывающий количество кадров, собранных программой в секунду.
Рис. 4.3 – Статистика сбора кадров
Программа WireShark предоставляет пользователю ряд уникальных возможностей, не поддерживаемых другими анализаторами протоколов. Программа обеспечивает возможность сбора всех пакетов заданного соединения TCP и представления
данных в удобном для просмотра формате (ASCII,
EBCDIC или шестнадцатеричный).
96
Рис. 4.4 – Иерархия протоколов
При выводе пакетов можно использовать мощную систему фильтрации WireShark, отбирающую
пакеты по большему, нежели в других анализаторах, числу полей.
4.4 ПОДГОТОВКА ДАННЫХ
Интервальный метод предполагает анализ потоков заявок на интервалах их обслуживания. Программа анализа выполнена в среде Mat lab, Поэтому, полученная с помощью программы Wireshark
информация о моментах поступления пакетов,
97
должна быть представлена в виде файла, с расширением «.txt».
Преобразование следует выполнять по предлагаемой методике [7 ]:
1. Запуск Wireshark.
Рис. 4.5 - Запуск Wireshark.
2. В верхнем левом секторе рабочего окна видим пункт «Interface List» Откроем его.
98
.Рис. 4.6 - Старт
3. Появилось окно, содержащее информацию по
всем доступным на компьютере сетевым подключениям. Те из них, что активны в данный момент,
будут видны по увеличивающимся счетчикам пакетов. Нажмем кнопку «Start» напротив необходимого нам подключения.
Рис. 4.7 - Фильтрация
4.Видим окно, в котором в текущем режиме
отображается процесс «ловли» пакетов, с указанием протоколов. Произведя необходимую фильтра99
цию и прочие операции, остановим процесс нажатием в верхнем меню Capture->Stop.
5. Теперь решим вопрос правильного сохранения, учитывая то, что для дальнейшей работы с
данными, нам необходимо получить файл txt, содержащий только столбик времен прихода пакетов
и ничего больше. Для этого необходимо, чтобы в
рабочем окне остался только столбик «Time». Выбираем в верхнем меню Edit->Preferences.
Рис. 4.8 - Интерфейс пользователя
6. В открывшимся окне настроек, в дереве слева
выберем пункт Columns (Столбцы).
100
7.Видим окно настроек столбцов. Необходимо
по одному выделить мышкой НЕНУЖНЫЕ столбцы и нажать кнопку Remove внизу окна. Выделенный столбец будет удален. Сделать эту процедуру
для всех столбцов, кроме того, у которого в поле
Field type (Тип поля) написано Time (format as specified). Нажимаем Apply и Ok внизу окна.
Рис. 4.9 - Выбор столбцов
Вернемся в рабочее окно и увидим, что из всех
столбцов остался только столбец, отображающий
времена прихода пакетов.
101
Рис. 4.10 - Столбец времен поступления пакетов.
8. Есть один единственный способ правильно
сохранить требуемые данные. В верхнем меню выбираем File->Export->File…
Рис. 4.11 - Сохранение данных
102
9. Откроется окно
Рис. 4.12 - Выбор типа файла
10. В строке «Тип файла» выбираем «Plain text
(*.txt)». В строке «Имя файла» вводим необходимое нам имя файла, в который будем сохранять
данные и ОБЯЗАТЕЛЬНО дописываем в конце
имени «.txt» (без кавычек). Чуть ниже в том же окне в области «Packet Range» должны быть выбраны
пункты «All packets», «Displayed». А в поле «Packet
Format» галочками должно быть отмечено ТОЛЬКО «Packet summary line» все остальное должно
быть выключено. Прежде чем нажать «Сохранить»
ОБРАТИМ ВНИМАНИЕ на то, куда именно будет
сохранен наш файл. информация об этом находится
в верхней части окна. При необходимости выберем
103
нужное нам место («Рабочий стол» например). Теперь жмем «Сохранить» и Wireshark можно закрыть или временно свернуть.
Рис. 4.13 - Столбец с именем «Time»)
Убедимся, что в указанном месте появился файл
txt с указанным именем. откроем его.
11.Обратим внимание, что первая строка файла
имеет имя столбца с временем (по умолчанию
«Time»). Эту строку надо удалить, чтобы файл начинался с цифр и содержал только цифры.
104
Рис. 4.14 - Удаление«Time».
12. Сохраним файл. Теперь он готов к работе в
программе.
4.5 ПРОГРАММА ИНТЕРВАЛЬНОГО
АНАЛИЗА ТРАФИКА
Программа была разработана в среде Mat Lab
2007. И.С. Макаровым, в процессе работы над кандидатской диссертацией [7]. Интерфейс выполнен
в среде визуального программирования GUIDE
(Graphic User Interface Designer), являющейся подпрограммой MatLab. Дескрипторная графика позволяет конструировать детали графического пользовательского интерфейса. При этом различные
105
функции и m-файлы вызываются из графического
окна общего стандартного вида. Последние версии
Mat Lab приобрели специальные инструментальные средства для визуально-ориентированного
программирования и проектирования приложений
в GUI. Эти средства дают достаточный набор инструментов для проектирования. Такой подход характерен для ряда современных визуальноориентированных языков программирования, таких
как Visual-BASIC, Visual-C и др., что существенно
облегчает создание приложений с GUI. Это обусловлено тем, что в данном случае генерация программного кода происходит автоматически, что
минимизирует усилия пользователя по программированию.
Приложение с GUI может состоять из одного
или нескольких окон и осуществлять вывод графической и текстовой информации как в основное окно приложения, так и в отдельные окна. MatLab
имеет ряд функций создания стандартных диалоговых окон для открытия и сохранения файлов, печати, выбора шрифта для текстовых объектов, создания окон для ввода данных и др.
Приложение представляет собой набор из нескольких функциональных окон, переход между
106
которыми осуществляется с помощью меню в
верхнем левом углу. Меню включает в себя: тестовый режим, позволяющий: произвести проверку
выведенных ранее соотношений, сымитировать поток пакетов, построить график очереди; имитационное моделирование, окно обработки реальных
данных, и мультиплексирование как реальных, так
и имитационных потоков.
Рис. 4.15 - Внешний вид тестового окна
Тестовое окно аналитики позволяет выбрать коэффициент вариации etta и число итераций N. Далее, при нажатии кнопки Push Button, производится
расчет очередей, при постоянном времени обработки, и основных параметров анализа. Один из
них – среднее значение параметра n выведено на
основное окно. Остальные можно посмотреть в дополнительных окнах.
107
Рис. 4.16 - Окно имитационного моделирования
Окно имитационного моделирования работает с
созданным искусственно имитационным трафиком.
В левом верхнем углу расположен блок «Исходные
данные», в который можно ввести: число заявок в
имитационном трафике, набор коэффициентов вариации, число которых неограниченно и вводится
через пробел в строку; шаг имитационного моделирования, который задает шаг между временами
обслуживания, если они выбраны постоянными.
Ниже есть группа, которая позволяет выбрать
распределение времен между заявками. Существует
возможность выбрать Гамма распределение, Экспоненциальное распределение, Нормальное распределение. На рисунке 4.16 приведен пример окна
программы с графиками, отображающими функ108
цию и ее аппроксимацию для Г-распределения. Так
как оно двухпараметрическое, то ниже есть возможность задать оба параметра. Необходимо только учитывать, что число значений этих параметров
должно быть равным числу значений коэффициентов вариации и должно быть равно между собой.
Ниже есть возможность задать те же распределения для времен обслуживания. Но, в приведенных примерах выбран режим с постоянным временем обработки.
Еще ниже представлен ряд функциональных
кнопок. «Начать расчет» – эту кнопку необходимо
нажать сразу после всех введенных выше данных.
После чего станут доступными кнопки: Таблицы,
Результаты, и блок Построение.
Рис. 4.17 - Окно таблиц результатов
109
Таблицы позволяют в отдельном окне вывести
на экран данные, которые представлены в программе в виде матриц.
Результаты выводят дополнительное окно, в котором представлен ряд расчетных параметров не
табличного вида. Такие, например, как средние
значения или вторые начальные моменты и т.д.
Блок Построение помогает строить графики
различных функций, заданных в выпадающем списке. Если требуется построить их в отдельном окне,
то необходимо поставить метку в соответствующем
пункте того же блока. Пункт Наложение необходим, если требуется построить несколько графиков
на одном поле.
Справа есть окно, на котором непосредственно
выводятся графики.
Рис. 4.18 - окно расчета реальных данных
110
Следующее окно расчета реальных данных мало
чем отличается от предыдущего, за тем исключением, что данные берутся из файлов. И соответственно это могут быть реальные данные. Программа
способна забирать данные из текстовых файлов,
где эти данные должны быть представлены в виде
столбца, в формате «.txt». или из файлов Microsoft
Excel, где они тоже должны быть представлены в
столбце. Необходимо указать только один путь. То
же самое, и для времен обработки заявок
4.6 ЗАПУСК ПРОГРАММЫ
Для работы с программным обеспечением следует выполнить следующие действия:
1. Открыть Mat lab.
2. В верхнем меню выбираем File->Open и выберем файл с программой igor_program.m
111
Рис. 4.19 - Выбор программы
3. Откроется окно программы (см. Приложение
1).
Рис. 4.20 - Текст программы
4. Сама программа содержит в себе подробное
описание каждой переменной и функции. Соответ112
ствие переменных показано в таблице (Приложение 2).
Единственное, что стоит здесь упомянуть – это
первая строка программы:
time=load'C:\Users\Игорь\Desktop\Дисертация\M
ATLAB\Trafik\ethernet.txt');».
Эта строка содержит адрес файла, который мы
сохраняли из Wiresharka.
Эту строку следует исправить, в соответствии с
текущим адресом файла, и данные из него автоматически будут записаны как переменная Time программы. После этого нажимаем F5 для запуска программы.
Рис. 4.21 - Выбор пути к анализируемому файлу
Если появится окно просто жмем «Add to Path»
или «Change Directory».
Программа сделает все расчеты и выдаст их в
окно «Workspace» как набор переменных и массивов.
113
В результате всех расчетов производится аппроксимация и вывод коэффициентов (одного или
двух, в зависимости от выбора метода аппроксимации), характеризующих данный трафик.
Графики аппроксимаций можно наблюдать, выбрав соответствующий пункт в блоке «Построение», а табличное значение коэффициентов в окне,
вызываемом кнопкой «Таблицы».
В настоящее время ведется работа над сопряжением данного приложения с сетевым оборудованием ПК, с целью набора статистики не из файла, а
непосредственно от сетевого адаптера.
ЗАКЛЮЧЕНИЕ
Созданные в настоящее время цифровые модели
обеспечивают мониторинг состояния множества
узлов сложных телекоммуникационных сетей. Однако, при подключении новых пользователей или
предоставлении им дополнительных услуг, часто
приходится оперативно определять объемы требуемых дополнительных ресурсов и пропускной
способности выделяемых каналов. Требуемая пропускная способность зависит как от количества
пользователей, так и от характера пользовательских приложений. Ограничения на договорную
114
пропускную способность каналов, выделяемую
пользователям, зачастую приводит к существенному ухудшению качества предоставляемых услуг.
Поэтому, в зависимости от количества пользователей и числа предоставляемых услуг, абонентам
приходится выбирать требуемую пропускную способность каналов доступа.
Предлагаемые интервальные методы позволяют
охарактеризовать трафик любого приложения с
помощью четырех параметров, непосредственно
связанных с размерами очередей и задержек, возникающих в канале с заданной пропускной способностью. Достоинством указанных параметров является возможность получения характеристик агрегированного трафика путем простого суммирования соответствующих параметров исходных потоков. Полученные обобщенные аналитические соотношения позволяют легко использовать указанные
параметры при определении размеров очередей и
задержек в интерфейсах каналов.
115
Литература
1. Вентцель Е.С. Исследование операций. М.:
"Наука", 1980. – 208 с.
2. Клейнрок Л. Вычислительные системы с очередями. Том 2. Пер. с англ. М.: Мир. – 1979.
3. Лихтциндер Б. Я. Интервальный метод анализа мультисервисных сетей доступа. Приложение к
журналу «Инфокоммуникационные технологии»,
Выпуск 8, 2012, стр.101-152.
4. Свешников А.А. Прикладные методы теории
случайных функций. М. "Наука", 1968. – 460 с.
5. Дж. Мартин Системный анализ передачи
данных. Том 2. Пер. с англ. М. "МИР",1975, 431стр.
6. Лихтциндер Б.Я., Макаров И.С. Определение
средней длины очереди СМО через корреляционные моменты числа заявок на интервалах обслуживания. ИКТ, том 9, № 1, 2011год.
7. Макаров И.С. Разработка метода исследование трафика мультисервисных сетей на основе анализа распределения числа заявок на интервалах обслуживания.: дис. канд. техн.. наук. Самара., 2012 ,
146 с.
116
8. Основы теории вычислительных систем. Под
ред. Майорова. Учебное пособие для вузов. М.,
"Высшая школа", 1978. 408с. с ил.
9. Анализ трафика мультисервисных сетей.
Учебное пособие для лабораторно практических
занятий. Лихтциндер Б.Я., Поздняк И.С. Самара,
2012, 96 с.
117
Приложение: 1. Программа анализа
timeA=load('G:\для магистров 2014\Программа Игоря\видеотрафик.txt');
for i=1:2000
time(i)=timeA(i);
end
T=time(numel(time)-1)-time(1);
%Время эксперимента
for i=1:numel(time)-1;
%
z(i)=time(i+1)-time(i); %Промежутки времени между пакетами
end
%
lbd=(numel(time)-1)/T;
%Интенсивность потока
ro=0.1:0.1:1;
%Коэффициент загрузки
канала
for k=1:10
%
dt=ro(k)/lbd;
%Временной интервал
N=floor(T/dt);
%Число нтервалов dt
j=1;
%
if k==1;
%
A=zeros(10,N-1); %Массив числа пакетов на
интервале dt
end
%
for i=1:N-1;
%
while time(j)<=dt*i;
%
A(k,i)=A(k,i)+1;
%
j=j+1;
%
end
%
end
%
end
q(1:10,1)=A(1:10,1)-1;
for k=1:10
dt=ro(k)/lbd;
N=floor(T/dt);
for i=2:N-1
if q(k,i-1)==0 && A(k,i)==0
118
q(k,i)=0;
else
q(k,i)=q(k,i-1)+A(k,i)-1;
end
end
q_sr(k)=mean(q(k,1:N-1));
q_disp(k)=var(q(k,1:N-1));
%E(k)=q_sr(k).*(1-ro(k));
%EE(k)=E(k)./ro(k);
end
B=zeros(10,max(max(A))+1); %Число нулей, единиц,
двоек...
for k=1:10
%
dt=ro(k)/lbd;
%
N=floor(T/dt);
%
m=max(A(k,1:N-1));
%Максимум полезной информации в
k-й строке массива А
for h=0:m;
%
for g=1:N-1;
%
if A(k,g)==h;
%
B(k,h+1)=B(k,h+1)+1;
%
end
%
end
%
end
%
end
%
P=zeros(10,max(max(A))+1);
определнного числа пакетов
for k=1:10
dt=ro(k)/lbd;
N=floor(T/dt);
for e=1:(numel(B)/10);
сиве B
P(k,e)=B(k,e)/N;
end
end
for k=1:10
dt=ro(k)/lbd;
N=floor(T/dt);
m=max(A(k,1:N-1));
%Вероятнсти появления
%
%
%
%Длина строки в мас%
%
%
%
%
%
%
%
end
%
119
mA=zeros(1,10);
сива А
dispA=zeros(1,10);
сива А
m2A=zeros(1,10);
сива А
%Первый начальный момент Мас%Дисперсия Мас%Второй начальный момент Мас-
for k=1:10;
dt=ro(k)/lbd;
N=floor(T/dt);
m=max(A(k,1:N-1));
mA(k)=mean(A(k,1:N-1));
dispA(k)=var(A(k,1:N-1));
m2A(k)=mean(A(k,1:N-1).^2);
end
%
%
%
%
%
%
%
for k=1:10
for i=1:N-1
if i==1
E(k,i)=(A(k,i)-mA(k)).*(q(k,i)+0)./2;
else
E(k,i)=(A(k,i)-mA(k)).*(q(k,i)+q(k,i1))./2;
end
end
end
for k=1:10
mE(k)=mean(E(k,1:N-1));
end
dA=m2A-mA.^2;
персия
%Проверочная дис-
P0=zeros(10,max(max(A))+1);
%Условная вероятность при
отсутствии нулей
for k=1:10;
dt=ro(k)/lbd;
N=floor(T/dt);
for e=2:(numel(B)/10);
P0(k,e)=B(k,e)/sum(B(k,2:(numel(B)/10)));
end
end
dt=ro/lbd;
120
%
%
%
%
%
%
%
Приложение 2. Таблица обозначений
Обозначение
В программе
По тексту
A(i);
mi
Число заявок на интервале
timeA(i);
ti
Моменты прихода заявок
T
T
Общий промежуток времени анализа
z(i)

Интервалы времени между заявками
lbd

Средняя интенсивность поступления
заявок
ro

Коэффмциент загрузки
dt

Интервал обработки
N
N
Общее число заявок
q(k,i)=
qi ( )
Размер очереди на i-м интервале
B
-
Гистограмма чисел заявок
P
P
Вероятности исел заявок
P0
P0
Условная вероятность (без нулей)
mA
m( )
Мат. ожидание A(i)
dispA
Dm (  )
Дисперсия A(i)
m2A
m2 ( )
Второй начальный момент A(i)
E(k,i)
-
Числитель на i-м интервале
mE(k)
E(  )
Мат. ожидание E(k,i)
121
Документ
Категория
Без категории
Просмотров
14
Размер файла
2 851 Кб
Теги
setej, dostupa, multiservisnogo, lihttsinder, metod, analiz, intervalnij, trafika
1/--страниц
Пожаловаться на содержимое документа