Математические модели трафика

В области прикладной математики анализ вероятности блокировок называют теорией перегрузки, а анализ систем с ожиданием – теорией очередей. Эти темы исследования вместе “зарубежные” авторы называют анализом потока трафика, отечественные – теорией очередей.  

Работа коммутатора связана с потоком трафика в процессе установления соединения: поток запросов на соединение источников с пунктами назначения запрашивает, удерживает и освобождает определенные ресурсы в этом процессе.

Непредсказуемость коммутационного трафика порождается в результате двух случайных процессов: поступления вызовов и длительностью занятия (см. рис.1).

 

 

Рис.22 Профиль активности сетевой нагрузки (все вызовы обработаны)

 

Рис.22 иллюстрирует ситуацию, в которой как поступления вызовов, так и длительность занятия от 20 источников непредсказуемы. В нижней части рисунка изображена активность каждого источника, а в верхней части – суммарная активность в текущий момент времени. Кривая активности показывает число каналов, используемых в конкретный момент времени. Максимальное число каналов равно 16, в среднем – около 11.

Коммутируемые каналы называют приборами, группы каналов – группами обслуживания.

Один из показателей пропускной способности сети – объем обслуженной нагрузки – сумма всех длительностей занятия в течение определенного интервала времени.

Интенсивность нагрузки – это объем обслуженной нагрузки деленный на интервал времени обслуживания. Измеряют интенсивность в Эрлангах, обозначают символом А.

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

Если средняя интенсивность поступления вызовов равна , а средняя длительность занятия прибора равна , то интенсивность нагрузки

 

.                                                                                            (1)

 

Интенсивность нагрузки не отражает характеристик частоты поступления вызовов и длительности нагрузки. Эти два параметра изучают отдельно. Особенно важным является нагрузка в час найбольшей нагрузки (ЧНН). Эта нагрузка предельна и она определяет как состав аппаратуры, так и ее эффективное использование. Так квартирные телефоны в ЧНН заняты от 5% до 10%. Средняя длительность разговора при этом равна 3-4 мин.

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

Рис.23 Объем трафика в зависимости от времени суток

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

1) В любой достаточно малый интервал времени может поступить только один вызов.

2) Вероятность поступления вызова в достаточно малый интервал времени прямо пропорциональна длине интервала - , где - длина интервала.

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

При этом можно показать [4], что вероятность распределения промежутков времени между поступлениями вызовов

 

.                                                                                          (2)

 

Это вероятность того, в течение интервала времени  не поступит ни одного вызова. Другими словами - вероятность того, что от момента поступления одного вызова до момента поступления другого вызова пройдет  секунд.

       Используя те же допущения можно [4] определить вероятность поступления  вызовов в интервале времени . Эта вероятность будет равна

 

.                                                                                 (3)

 

Выражение (3) – закон Пуассона. Когда j  равна 0, вероятность непоступления вызова в интервале времени t определяется формулой (2).

       Вероятность поступления j  и более вызовов можно определить таким образом:

 

 

,                                                (4)

 

где  определяется равенством (3).

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

       Постоянная длительность занятия. Такие посылки могут иметь место в случаях обработки заявок на обслуживание вызова, межстанционной сигнализации, при передаче пакетов в сетях пакетной связи. Для определения вероятности такого события можно воспользоваться соотношением (3), полагая что среднее число активных каналов равно интенсивности нагрузки , тогда

 

,                                                                     (5)

 

где - интенсивность поступления вызовов,  - постоянная длительность занятия,  - интенсивность нагрузки, Эрл.

       Экспоненциальная длительность занятия. Вероятностные описания длительности занятия наиболее часто имеют экспоненциальный характер,

 

,                                                                                          (6)

 

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

 

,                                                                                      (7)

 

где  - интенсивность нагрузки, Эрл. Этот результат справедлив для любого вида длительности занятия канала.

Системы с потерями

В том случае, когда число приборов (каналов) меньше максимально возможной нагрузки (числа источников), возникает блокировка вызовов. Это иллюстрировано рис.24

На рис.3 предполагается, что только 13 каналов свободны к обслуживанию трафика. Поэтому три вызова в моменты t =2,2; 2,3 и 2,4 минуты блокируются и покидают систему. Общий объем потерянного трафика показан заштрихованной областью, которая представляет собой разность между всем трафиком, обслуженным сразу после                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   поступления, и трафиком, обслуженным системой из 13 каналов с явной блокировкой вызовов. Вызов, поступивший в момент t =2,8, не заблокирован, хотя исходный профиль показывает, что этот вызов поступил, когда были заняты все 13 каналов. Причина этого состоит в том, что предыдущий заблокированный вызов покинул систему и поэтому уменьшил нагрузку для последующих поступлений вызовов. Следовательно, доля времени, когда исходный профиль трафика находится выше 13 Эрл, не совпадает с вероятностью блокировки, когда доступны только 13 каналов.

 

        

 

Рис.24 Профиль активности сети с явной блокировкой (число доступных каналов равно 13)

 

Первым специалистом, который в 1917 г. полно и точно вычислил вероятность блокировки при явных потерях, был Эрланг. Основной аспект формулы Эрланга и ключевой вклад в современную теорию случайных процессов – понятие статистического равновесия. Чтобы система пришла в состояние статического равновесия должно пройти некоторое время значительно большее средней длительности занятия. В этот момент наиболее вероятно состояние системы, при котором она имеет  занятых каналов.

Если при этом число активных каналов превысит среднее значение  , то выход вызова из системы станет более вероятным, чем его поступление. Аналогично, если число активных каналов упадет ниже , то поступление вызова более вероятно, чем выход из системы. Таким образом, если случайно система будет выведена из равновесия, то она будет стремиться вернутся в него.

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

 

                                                                                        (8)

 

где  - число приборов (каналов);  - интенсивность поступающей нагрузки,  в эрлангах.

       Выражение (8) определяет вероятность блокировки для системы со случайным поступлением вызовов бесконечного числа источников и произвольного распределения длительности занятия. Эта вероятность представлена графически на рис.25 как функция интенсивности поступающей нагрузки для различного числа каналов. Часто более полезное представление Эрланга дает рис.26, на котором представлено использование исходящих каналов для различной вероятности блокировок и числа каналов. Использование выходных каналов  представляет собой нагрузку, обслуживаемую каждым каналом:

 

,                                                                                          (9)

 

 

Рис.25 Вероятность блокировки в системе с явными потерями: N – число каналов (приборов)

 

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

 

 

Рис. 26 Использование исходящих каналов в системе с явными потерями

 

       Объединение групп с малой нагрузкой в одну большую группу может обеспечить существенную экономию общего числа требуемых каналов. Большие группы более эффективны, чем несколько маленьких групп, поскольку маловероятно, что в малых группах перегрузка возникнет в один и тот же момент времени (допущение о независимости моментов поступления вызовов). В действительности избыточная нагрузка в одной группе может использовать свободные каналы другой группы. Поэтому каналы, которые нужны для выравнивания пиков нагрузки, но обычно свободны, используются более эффективно, когда нагрузка объединяется в одну группу. Это свойство – одна из причин интеграции речи и данных в общую сеть. Более выгодно концентрировать нагрузку на периферийной части сети. Иллюстрация такой группировки приведена на рис.27.

       Большая эффективность использования каналов получается при объединении нагрузки в большие группы, что часто называют преимуществом групп большого размера. Эта эффективность – основная причина выбора иерархических структур коммутации. Вместо взаимодействия большого числа узлов с относительно маленькими группами каналов между каждой парой узлов, более экономно объединить всю нагрузку от отдельных узлов в одну большую группу и направить нагрузку через транзитный узел коммутации. На рис.28 сопоставлены полносвязная топология и топология типа “звезда” с центральным узлом коммутации в центре. Очевидно, что затраты на установку транзитных коммутаторов будут оправданы, если экономия общей протяженности линий в канало-километрах достаточно велика.

 

                  

 

Рис. 27 Преобразования сети терминалов: a- отдельные группы нагрузки; б – нагрузка сконцентрирована в одной группе

 

 

                  

 

Рис. 28 Использование транзитного коммутатора: а – полносвязная топология; б – топология типа “звезда”

 

Системы с ожиданием

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

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

       Далее предполагается, что вся нагрузка, поступающая в систему, обязательно будет обслужена. Данное допущение имеет две стороны. Когда  < , можно представить два случая, когда обслуженная нагрузка меньше поступающей. Первый – некоторые источники могут “устать” от ожидания в длинной очереди и покинуть систему. Второй – способность накопления вызовов конечна и требования на обслуживание системой отключаются.

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

Рассматривают обычно два распределения времени обслуживания: постоянное и экспоненциальное. Эти распределения представляют диапазон от детерминированных до наиболее случайных времен обслуживания. Все остальные распределения расположены между ними.

Цель анализа системы – определить вероятность распределение времени ожидания.

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

           

                             

 

 

Рис. 29 Диаграмма активности блокированных вызовов в системе с ожиданием

 

       На рисунке представлен тот же профиль нагрузки, что и на рис.1 и 3. Однако в этом случае избыточная нагрузка задерживается до тех пор, пока разъединение вызова не освободит доступные каналы.

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

 

                                                      (10)

 

где - число приборов;  - поступающая нагрузка, Эрл;  - вероятность блокировки для потерь в системе с явными потерями [выражение (8)].

       Распределение времени ожидания для случайного поступления вызовов, случайного времени обслуживания имеет вид

 

 

                                                                      (11)

 

где  - вероятность ожидания, полученная в формуле (10);  - среднее время обслуживания при отрицательном экспоненциальном распределении времени обслуживания.

       Выражение (11) определяет вероятность того, что поступающие в случайно выбранный момент времени вызовы ожидают более чем  длительности обслуживания. На рис.9 представлено соотношение (11), показывающее пропускную способность при различном числе приборов как функцию допустимого времени ожидания.

       Интегрируя выражение (11) по времени, определим среднее время ожидания для всех поступающих вызовов

 

                                                                                          (12)

 

       Среднее время ожидания только для вызовов, которые уже ожидают обслуживания, определяется как

 

                                                                                            (13)

 

Постоянное время обслуживания. Среднее время ожидания при единственном приборе определяется как

 

                                                                                          (14)

 

где  - коэффициент использования прибора. Выражение (14) дает среднее время ожидания, точно равное половине времени для прибора с экспоненциальным временем обслуживания.

       Вероятность перегрузки при больших  относительно близка вероятности перегрузки системы с экспоненциальным временем обслуживания. Поэтому выражение (11) может быть использовано как первое приближение для p(>0)  в системе с несколькими приборами и произвольным временем распределения.

       Для системы с одним прибором и постоянным временем обслуживания вероятность ожидания больше t

 

 

                                                                                                     (15)

где - найбольшее целое число, не превышающее ;  - дробная часть ;  - коэффициент использования прибора, .

Рис. 30 Пропускная способность системы с несколькими приборами, ожиданием и экспоненциальным временем обслуживания: а – вероятность ожидания свыше времени t, p(> t)=10%; б – вероятность ожидания свыше времени t, p(> t)=1%

 

                   Рис. 31 Вероятность ожидания системы с одним прибором (экспоненциальное и постоянное распределения времени обслуживания)

       Сравнение распределения времен ожидания для системы с одним прибором, экспоненциальным временем ожидания и постоянным временем ожидания показано на рис. 31. Для каждой пары кривых верхнее распределение – для экспоненциального распределения времени обслуживания и нижнее – для постоянного времени обслуживания.

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