Аналитические модели потоков сообщений

 

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

          Известно, что при анализе и проектировании ЛВС необходимо ответить на следующие вопросы:

- какова длина очереди сообщений?

- сколько времени сообщению приходится ждать в очереди?

- какова вероятность передачи сообщения.

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

 

 

 

 

Распределение Пуассона

 

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

– стационарности, т.е. вероятность свершения некоторого числа событий за данный интервал времени не зависит от расположения этого интервала, а зависит лишь от его длины;

– независимости событий, т.е.  сообщения поступают независимо друг от друга;

– ординарности - сообщения поступают по одному и поступление одновременно двух сообщений невозможно,

то такая система, сообщений подчиняется закону распределения вероятностей Пуассона, а поток сообщений носит название "пуассоновский".

 

 

                       

 

где  - вероятность того, что в течение интервала времени t поступит на обработку ровно n сообщений;

 

- средняя интенсивность поступления сообщений в одну секунду.

 

 

 

 

 

 

 

 

 

 

 

         

 

 

      

 

 

 

         

 

 

 

 

Очевидно, что  - среднее число сообщений, поступающих в систему за рассматриваемый интервал времени t.

                                                                                         (2)

 

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

          Нетрудно показать, что

                                                        (3)

 

 

          Дисперсия D_n(t), характеризующая отклонение числа заявок от среднего значения, определяется для закона Пуассона:

 

                                                                                             (4)

 

 

среднеквадратическое отклонение

                                                                                   (5)

 

 

          График P_n(t) = f(n) при заданном значении n показан на рис.1. Следует отметить, что в       интервале   Зs  укладывается 95% площади, ограниченной кривой Р_п (t) и осью абсцисс.

          Функция распределения вероятностей F_n(t) определяет вероятность того, что за данный интервал времени t в систему поступит не более n сообщений:

 

                                                                      (6)

 

Очевидно, что

 

                                                                                                     (7)

 

 

          График F_n (t) для заданного значения приведен на рис. 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

          Из соотношения (1), характеризующего закон Пуассона, определим вероятность того, что за время t не поступит ни одного сообщения:

                                                                                     (8)

 

          Вероятность того, что за промежуток времени t поступит хотя бы одно сообщение

 

                                                                (9)

 

          Функция F(t) - есть функция распределения вероятностей того, что действительный     интервал  между двумя соседними сообщениями  окажется меньше или равен /. Время t  называют еще периодом поступления сообщений. Плотность распределения вероятностей

 

                                                         (10)

 

определяется как производная F(t). Произведение Р(t)Dt указывает вероятность того, что период поступления соседних сообщений находится в интервале от t до t +Dt. Среднее значение интервала между двумя соседними сообщениями определяется по обычной формуле:

 

                                                                        (11)

 

          Действительно, среднее время  между двумя соседними сообщениями есть величина,   обратная   средней частоте поступления сообщений   Среднеквадратическое отклонение s(т)    определяется через дисперсию D(t).   

Откуда

                                                                                                      

                                                          (12)

 

откуда

                                                                                 (13)

          Для экспоненциального закона распределения временных характеристик справедливо соотношение:

                                                                                      (14)

 

          Соответствие экспериментальных данных соотношению (14) говорит о том, что распределение плотностей вероятностей экспоненциально.

 

 

Распределение Эрланга. Гамма-распределение

времен обслуживания сообщений

 

          Интервалы времени между сообщениями, поступающими произвольно, распределены экспоненциально. Переключение потока на различные направления описывается распределением   Эрланга. Например, пусть во  входной линии, по  которой передаются   сообщения   с  экспоненциальным    законом распределения времени их поступления, стоит трехпозиционный переключатель. Этот переключатель направляет   поочередно сообщения по различным каналам (рисунок 3).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

          Среднеквадратическое отклонение s(t) для исходного и результирующего потоков осталось неизменным. Отношение

 

                                                                                    (15)

 

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

 

                                                       (16)

 

          Очевидно, что при k = 1 имеет место простейший поток. Распределение Эрланга является частным случаем более общего гамма-распределения. Для распределения Эрланга k  - всегда целое число.

          Для гамма-распределения параметр k может принимать любое значение

 

                                                                        (17)

 

          Гамма-функция Г(k) имеется в таблицах и принимает значения (k-1)! для целых k.

          Функция распределения вероятностей F_k(t) получается интегрированием соотношения  в пределах от 0 до t:               

                                                                              (18)

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

          Экспоненциальное распределение, распределение Эрланга и постоянный набор являются частными случаями гамма-распределения. Для экспоненциального k = 1, для распределения Эрланга k - любое целое число. Для постоянного          набора значений - k = ¥.

          Графики соответствующих функций (17) и (18) для различных коэффициентов Эрланга приведены на рис. Из них очевидно, что для значений k = 1 имеет место экспоненциальный закон. При увеличении коэффициента Эрланга процесс все более приближается к детерминированному, а график зависимости P_k(t) сужается, в пределе стремясь к s функции.

          Степень детерминированности процесса можно охарактеризовать коэффициентом вариации

 

                                                                            (18а)

 

          Коэффициент вариации указывает, насколько случайная     величина интервала t   отклоняется от своего среднего значения    .

          Одним из свойств гамма-распределения является следующее: если несколько случайных          переменных подчинены гамма-распределению, то сумма этих переменных также подчинена гамма-распределению. Это позволяет суммировать времена при прохождении случайных потоков через различные устройства обработки.

          При вычислении результирующих значений среднего времени, а также среднеквадратического отклонения, необходимо иметь в виду, что для суммы N случайных величин

                                                                  (19)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

         

 

 

 

 

 

 

 

          По  указанным величинам можно определить  значение коэффициента k для результирующего потока.

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

          s₁(t) = .

 

          На обработку каждого сообщения   вторым устройством затрачивается постоянное время . Суммарные   времена обработки сообщений обоими    устройствами   подчиняются уже гамма-распределению с параметром

          Зная параметр k результирующего потока, можно по формуле (17) подсчитать вероятность того, что интервал между сообщениями в точности равен t, а по формуле (18) - вероятность того, что он не превышает t.

          Итак, процедура расчета указанной      вероятности распадается на четыре шага:

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

2. Расчет среднеквадратического отклонения  результирующего потока.

3. Определение коэффициента k для соответствующего гамма-распределения.

4. Получение по формуле (18) значения

            

          Рассмотрим еще один пример. Ранее было показано, что форма г данных подуровня УДС для ЛВС со случайным доступом содержит две составляющие: поле управления постоянной длины, содержащее 26 байт, и информационное поле переменной длины, содержащее, в среднем, 64 байта информации. При скорости передачи В=10 Мбит/с; управляющая часть кадра будет передаваться в канал в течение постоянного промежутка времени = 20,8 мкс. Время передачи информационного поля является случайной величиной со средним значением =51,2 мкс. Если принять закон распределения времени - экспоненциальным, то его среднеквадратическое отклонение  = 51,2 мкс. Полное время передачи кадра, также случайная величина. Однако закон распределения плотностей ее вероятностей уже нельзя назвать экспоненциальным.

Среднее значение

 = 72 мкс.

Учитывая детерминированный характер времени

среднеквадратическое отклонение

коэффициент Эрланга для полученного закона распределения

Соответствующее ему значение коэффициентов вариации

 

          Коэффициент вариации непосредственно связан со вторым на­чальным моментом случайной величины

                                                                              (20)

и оказывает существенное влияние на характеристики системы массово­го обслуживания.

 

 

Аналитические модели ЛВС с шинной структурой

 

            Наиболее упрощенная модель ЛВС с шинной структурой пред­ставляет собой систему массового обслуживания (СМО) с одним прибо­ром ним прибором обслуживания П, моделирующим моноканал переда­чи сообщений, как это показано на рисунок 5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

         

 

           

 

            Каждая из станций ЛВС передает в моноканал сообщения со средними интенсивностями потоков Xi... Xi ... Хм. Сообщения, предназна­ченные для передачи с каждой стан­ции, накапливаются в очередях Oi ... Oi ... Ом  и поочередно с интенсив­ностью X сообщений в секунду посту­пают на обработку в прибор обслу­живания.

            Каждое сообщение при обра­ботке задерживается прибором об­служивания на некоторый промежу­ток времени, а затем передается в ка­нал. Для сообщений, поступающих от каждой из станций, введем обозначения:

/_i   - среднее число сообщений i-ой станции, находящихся в очере­ди;

n_i - среднее число сообщений i-ой станции, находящихся в сети, включая сообщения,     

      обрабатываемые прибором обслуживания;

 - среднее время ожидания сообщения в очереди О;

 - среднее время пребывания сообщения от i-ой станции в сети;

   - среднее время обслуживания сообщения от i-ой станции прибором П;

 - среднеквадратическое отклонение времени обслуживания;

  - коэффициент загрузки канала сообщениями от i-ой станции.

          Предположим, что каждый из потоков, входящих в СМО, - пуассоновский, а его интенсивность

                                                                                     (21)

          Загрузка прибора обслуживания  потоком сообщений  от i-ой станции будет составлять

                                                                                      (22)

а суммарная загрузка прибора со стороны всех потоков

                                                                                     

          Условие существования стационарного режима в этом случае представляется в виде R<1. Для потоков сообщений от каждой из станций справедливы соотношения

                                        (23)

 

          Среднее время ожидания в очереди и пребывания в системе одной заявки суммарного потока , а также среднее время ее передачи определяются соотношениями:

                                                                                                                                                      (24)

 

где         - вероятность того, что заявка поступила от i-ой станции.

 

     - средняя суммарная длина всех очередей;

 

    -среднее число сообщений от всех станций, находящихся в системе:                                                                                                                     

                                                  (25)

 

            Если известны средние времена обслуживания и их среднеквадратические отклонения, то при бесприоритетной передаче сообщений среднее время ожидания в очередях для всех сообщений одинаково и равно

 

                                                                         (26)

 

где  - коэффициент вариации длительности обслуживания сообщений, поступающих от i-ой станции.

          Из (26) видно, что среднее время ожидания сообщений в очереди минимально при постоянной длительности обслуживания сообщений каждого типа ( ) и увеличивается по мере роста среднеквадратического отклонения времени обслуживания. Среднее время ожидания существенно зависит от загрузки R канала. По мере приближения значения R к единице, время ожидания неограниченно растет.

          Время пребывания в системе сообщения i-ой станции равно сумме времени ожидания в очереди и времени его обслуживания

 

                                              

          Поскольку   при   бесприоритетном   обслуживании   сообщений то                                                                                                                                                                                                                            (27)

 

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

                                                   (28)

 

          Среднее число сообщений, находящихся в каждой i-ой очереди

                                                                         (29)

пропорционально интенсивности потока сообщений, поступающих от соответствующей станции.

 

 

 

 

 

 

 

 

 

 

 

Пример расчета ЛВС с шинной структурой

 

        Расчет времени задержки доставки сообщений в сети со МДКН/ОК произведем на примере ЛВС Ethernet, обеспечивающий равные права доступа для всех станций подключения аппаратуры абонентов к сети. К сегменту могут подключаться не более 100 станций.

         Станция может быть удалена от сегмента не более, чем на 50 м. Максимальная длина сегмента - 500 м. Два сегмента могут быть объединены между собой при помощи ретранслятора, устанавливаемого вместо станции (см. рис.8). На пути между любыми двумя станциями не должно быть более двух ретрансляторов. Минимальное расстояние между станциями 2,5 м, максимальное - 1500. Задержка начала вывода кадра из ретранслятора (т.е. промежуток времени между приемом и выдачей кадра) не должна превышать 14,5 битовых интервала. Длина битового интервала составляет 100 нс.

         Объединяя сегменты через ретрансляторы, можно построить сложную сеть. ЛВС Ethernet имеет топологию дерева без корня. Спецификация сети предусматривает физический канал в виде коаксиального кабеля со скоростью передачи 10 Мбит/с.

Зададим следующие исходные данные сети:

- протяженность сети S=2 км, - максимальное расстояние между двумя станциями;

- скорость модуляции В = 10 Мбит/с;

- число станций М  = 50;

- скорость распространения сигнала по кабелю связи V = 2,3 ×10⁵ км/с;

- максимальное число ретрансляторов - n_р между двумя станциями n_р = 2;

- максимальная задержка одного ретранслятора в битах L_p = 14 бит;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- тип протокола,    из которого устанавливается: средняя длина информационной части 

   кадра L_H = 1600 бит;

- средняя длина служебной части кадра L_c = 320 бит;

- закон распределения длин информационной части кадра (обычно экспоненциальный) 

  ;

- закон распределения длин служебной части кадра (обычно детерминированный)

  ;

- среднее значение интенсивности сообщений, поступающих от каждой станции

l_ср =10 (1/с).

        Обычно сеть принимается однородной.

        На основании указанных исходных данных произведем расчет времени задержки в сети и определим ее пропускную способность.

1. Время  распространения сигнала по кабелю между двумя наиболее удаленными станциями:

    

2. Максимальное время задержки сигналов в ретрансляторах

  

3. Полное время распространения сигнала

  

4. Длительность информационной части кадра

  

5. Длительность служебной части кадра .

  

6. Суммарная средняя длительность кадра

   

7. Коэффициент вариации  времени передачи кадров сообщений

 

8. Суммарное значение интенсивности поступления сообщений

    

9. Суммарный коэффициент загрузки

 

10. Коэффициент дальнодействия,  с учетом времени задержки в ретрансляторах,

  

11.Относительное время задержки доставки сообщения, определенное по соотношению (59)

 

 

 

12. Время задержки доставки

13. Пропускная способность канала

 

14. Предельно допустимое значение  суммарной   интенсивности, при котором загрузка достигает пропускной способности канала.

 

15. Минимальное время задержки доставки (при R = 0)

       

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

        На рисунке 12 (кривая 1) показана зависимость нормированного времени доставки сообщений от значения коэффициента загрузки R, рассчитанная по формуле (59).

        Рассмотрим пример расчета времени доставки сообщений в шинной ЛВС с маркерным доступом. Сеть имеет топологию, аналогичную сети Ethernet, показанную на рис. 10, и характеризуется аналогичными исходными данными: S=2 км; B=10 Мбит/с; V=2,3×10⁵ км/с; n_p=2; L_p=14 бит; М=50; l_ср=10(1/с). Среднюю длину информационной части кадра L_c примем равной 1600 бит. В соответствии с ранее рассмотренным протоколом шинной сети с маркерным доступом, длина служебной части кадра L_c составляет 168 бит.

        В отличие от сети Ethernet, в рассматриваемой сети с целью обеспечения бесконфликтной передачи добавляется маркерный кадр длиной в 24 бита. L_M=24 бит.

        Полное время распространения сигнала с учетом ретрансляторов, как и прежде, будем считать t = 11,3мкс.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Длительность информационной части кадра

    

2. Длительность служебной части кадра

 

3. Длительность маркерного кадра

 

4. Суммарная средняя длительность информационного кадра

5. Коэффициент вариации времени информационных кадров

6. Суммарное значение интенсивности поступления информационных сообщений

7. Суммарный коэффициент загрузки

8. Время, необходимое для подготовки станции к передаче, примем равным длительности двух бит, т.е.    t_L = 0,26 мкс.

9. Латентный период   T_L   сети определяется соотношением

  

10. Параметр дальнодействия  a^/   определяется соотношением

 

11. Нормированное время задержки сообщений определяется    соотношением (43)

12. Время доставки

13. Пропускная способность сети С, согласно формуле (43), равна единице, поскольку с увеличением длин очередей доля маркерах сообщений уменьшается.

14. Минимальное время задержки сообщений (R ® 0) составляет

 

        При малых загрузках время доставки , рассчитанное по (43), незначительно превышает минимальное время . Зависимость нормированного времени   доставки сообщений для различных загрузок R показана на рисунке 12 (кривая 2).

        Сравнивая графики 1 и 2 на рисунке 12,  убеждаемся, что дополнительная "плата” за бесконфликтную передачу в виде маркерных сообщений приводит к несколько большим затратам времени на доставку сообщений при малых загрузках сети, зато бесконфликтность обеспечивает устойчивую работу сети с маркерным доступом при нагрузках, существенно превышающих пропускную способность сети со случайным доступом.

        Итак, сети со случайным доступом эффективнее использовать при малых загрузках, а сети с маркерным доступом - при больших загрузках.