Основы теории телетрафика

2. ОСНОВЫ ТЕОРИИ ТЕЛЕТРАФИКА 2.1. Теория телетрафика как научная дисциплина Теория телетрафика как самостоятельная дисциплина возникла из необходимости рассчитывать вероятности блокировки и времена задержки сообщений при их передаче по коммутируемым сетям[7,11]. Методы расчета этих характеристик: необходимы для количественного обоснования решений, которые принимаются специалистами при проектировании и построении сетей; зависят от используемых алгоритмов коммутации и технологий их реализации. Поэтому для разных сетей нужно разрабатывать разные методы расчета. Главная проблема, решаемая в рамках теории телетрафика, может быть сформулирована следующим образом см. рис. 12 и 13: какими должны быть пропускные способности общих цепей передачи сигналов (исполнительной системы) и устройств обработки управляющей информации (управляющей системы) сетей и сетевых центров коммутации? Аб.1 ... Аб.N С какой скоростью должна переносить данные каждая линия связи? Центр коммутации ? Центр коммутации Сколько должно быть линий связи? Аб.1 ... Аб.M Рис. 12. Аспекты пропускной способности исполнительной системы К понижению эффективности использования сетей связи приводят две следующие ошибки, которые можно допустить в процессе проектирования: 1) слишком много линий связи, имеющих слишком высокую скорость передачи данных и (или) слишком высокое быстродействие управляющих систем. В результате качество обслуживания пользователей высокое, а использование сетевых ресурсов низкое; 2) слишком мало линий связи, имеющих слишком малую скорость передачи данных и (или) слишком маленькое быстродействие управляющих систем. В результате использование сетевых ресурсов высокое, а качество обслуживания пользователей низкое. ЗАПРОСЫ Служебная (управляющая) информация Упрапвляющая система центра коммутации ОТВЕТЫ Каким должно быть время реакции управляющей системы центра коммутации (или сервера) на поступающие запросы? Рис. 13. Аспекты пропускной способности управляющей системы Поиск компромисса между качеством обслуживания пользователей и эффективностью использования сетевых ресурсов относится к числу главных аспектов построения сетей. Теория телетрафика – это инженерная дисциплина, разрабатывающая такие методы анализа и синтеза телекоммуникационных сетей и информационных систем, которые позволяют найти разумный компромисс между качеством обслуживания пользователей сетей и уровнем использования сетевых ресурсов. Теория телетрафика является одной из ветвей теории массового обслуживания (англ. queueing theory – теория очередей), но ориентирована не на разработку сложного математического аппарата, а на инженерное приложение математических методов к практическим задачам проектирования информационных сетей и систем[1218]. Объектом исследования в рамках теории телетрафика являются математические модели сетей и систем, которые называются СМО – системы массового обслуживания. СМО считается заданной, если полностью известны ее следующие компоненты: 1) входящий поток заявок (вызовов, запросов, требований, сообщений); 2) количество и типы обслуживающих устройств (ресурсов, приборов, каналов обслуживания); 3) времена обслуживания заявок (занятости приборов); 4) емкости накопителей (буферов), где заявки ожидают начала обслуживания, образуя очереди; 5) дисциплина обслуживания (она определяет порядок обработки заявок в системе, начиная с момента его поступления в систему и до момента, когда он покидает СМО). Предметом теории телетрафика является количественная сторона процессов обслуживания потоков заявок в сетях связи и информационных системах. Основная цель теории телетрафика заключается в разработке методов оценки вероятностно-временных характеристик (ВВХ) процессов функционирования сетей связи и информационных систем при разных вариантах их построения. Задачи, которые стоят перед теорией телетрафика, можно разделить на две группы: задача анализа – это отыскание зависимостей и значений величин ВВХ от параметров входящего потока заявок, времен и дисциплины обслуживания; задача синтеза – это определение структурных параметров сетей и систем при заданных потоках, дисциплине и качестве обслуживания (выбор вариантов построения систем и сетей). Основным математическим аппаратом теории телетрафика являются: теория вероятностей, математическая статистика, комбинаторика. Поскольку события, которые определяют правила поступления заявок на обслуживание, занятие и освобождения ресурсов, происходят в случайные моменты времени, процесс обслуживания пользователей является случайным процессом. Кроме того, СМО относятся к числу динамических систем и подлежащие оценке показатели их работы меняются со временем, что затрудняет анализ. Значительные результаты теории телетрафика получены благодаря понятию статистического равновесия, которое ввел Эрланг: вероятностный процесс находится в состоянии статистического равновесия, если его вероятностные характеристики не зависят от времени. Следует различать три метода решения задач теории телетрафика: аналитические методы позволяют решать задачи теории телетрафика в тех случаях, когда структура СМО, характеристики потока и дисциплина обслуживания относительно просты; для решения задач большой размерности с помощью ЭВМ используются специальные алгоритмы, позволяющие находить приближенные решения итерационными или другими численными методами; наиболее универсальным методом, который пригоден для решения задач практически любой сложности, является метод имитационного моделирования. 2.2. Описание систем массового обслуживания. Общие ресурсы центра коммутации 1 { Входной трафик ны й н я р е Пот фик тр а . . . n { Пользователи N>>n Урегулирование коллизий, возникающих при попытке нескольких пользователей одновременно занять один и тот же ресурс, могут быть урегулированы при помощи нескольких дисциплин обслуживания[7,12]. При дисциплине с потерями (рис. 14) число обслуживаемых заявок не может превышать количество ресурсов и заявка на занятие сетевых ресурсов получает отказ в обслуживании и не сохраняется в системе, если все ресурсы в момент попытки их занятия уже заняты обслуживанием других заявок. Обслуженный трафик Обслуженный меньше входного на величину потерянного Рис. 14. Дисциплина с потерями Общие ресурсы центра коммутации 1 Входной трафик { . . . Очередь на n обслуживание { Пользователи N>>n При дисциплине с ожиданием (рис. 15) заявка не покидает систему даже если заняты все ресурсы, а сохраняется в буфере и удовлетворяется по мере освобождения ресурсов. Промежуточное положение занимают дисциплины урегулирования коллизий с ограниченным временем ожидания (заявка теряется при превышении некоторого допустимого времени пребывания в буфере) и с ограниченным числом мест ожидания (потери возникают, если при поступлении заявки заняты не только требуемые ресурсы, но и все места ожидания в буфере). Обслуженный трафик Обслуженный равен входному Рис. 15. Дисциплина обслуживания с ожиданием Джорджем Кендаллом была предложена символика, которая кратко описывает СМО при помощи четырех символов, разделенных вертикальными чертами: A / B / n / m . Символ A описывает функцию распределения интервалов времени между заявками (поток заявок на обслуживание). Символ В описывает функцию распределения времени обслуживания заявок. Символ n задает число идентичных параллельных обслуживающих устройств. Символ m задает число мест для ожидания в буфере. Если используется система с потерями, то четвертый символ в описании СМО отсутствует. Для обозначения распределений, в частности, используются следующие символы: М – показательное распределение, Еr – распределение эрланга порядка r, Hr - гиперэкспоненциальное распределение с r этапами, D – постоянное (детерминированное) распределение, G – произвольное распределение и др. Например, СМО, которая характеризуется показательным распределением интервалов времени между заявками, показательным временем обслуживания заявок, содержит 10 обслуживающих устройств и работает по системе с потерями, обозначается M / M / 10 . Если же используется система с ожиданием, время обслуживания постоянно и емкость буфера равна 8, то M / D / 10 / 8. Рассмотрим последовательно каждый из элементов СМО. 2.3. Потоки заявок СМО Заявка на обслуживание – это событие, которое заключается в возникновении потребности в выполнении некоторых действий обслуживающими приборами СМО в интересах источника заявки. Обслуживание связано с занятием обслуживающего прибора на время предоставления услуги. Поток заявок – это развернутая во времени последовательность таких событий. Он является первым и самым важным аспектом СМО, который описывает (моделирует) массовость процессов обслуживания. Детерминированный поток заявок – это последовательность, в которой заявки поступают в определенные, строго фиксированные неслучайные моменты времени. Он может задаваться в явном виде моментами поступления заявок t1, t 2 , ..., t m ,... , или в виде последовательности промежутков времени между заявками z1  t 2  t1, z 2  t3  t 2 , ..., z m  t m 1  t m , ... , так, как это показано на рис 16. Во втором случае моменты поступления заявок могут быть вычислены рекуррентно. z1 t0 z2 t1 zm t2 ... tm 1 tm ... Рис. 16. Задание детерминированного потока заявок В случайном потоке моменты поступления заявок и промежутки между ними являются случайными величинами. В этом случае необходимо задать совместный закон распределения случайных моментов возникновения заявок или промежутков времени между заявками: PT1  t1, T2  t 2 , ..., Tm  t m , ... или PZ1  z1, Z 2  z 2 , ..., Z m  z m , ..., а точками на оси времени можно задать лишь одну реализацию случайного процесса поступления заявок. Задание многомерных законов распределения является задачей трудновыполнимой при инженерном проектировании сетей и систем. Реально используемые модели случайных потоков заявок подразумевают существование у них ряда свойств, позволяющих существенно упростить формальные описания. Важными свойствами такого рода являются рекуррентность, однородность и финитность потоков. Рекуррентным называется поток, у которого промежутки времени между соседними заявками независимы друг от друга и распределены по одинаковому закону. В однородном потоке каждая заявка обслуживается в соответствии в одной и той же дисциплиной обслуживания. В неоднородном потоке разные заявки могут требовать обслуживания разного вида и поэтому должны помечаться дополнительными характеристиками. Поток называется финитным, если на любом конечном отрезке времени поступает конечное число заявок и математическое ожидание числа поступающих заявок также является конечной величиной. Финитный поток может быть задан количеством заявок, поступивших в систему в течение последовательных промежутков времени (рис. 17). Это третий способ задания потока заявок наряду с заданием моментов времени поступления заявок и интервалов времени между заявками. t0 k1 t1 t2 k2 ... tm 1 tm ... ki  количество заявок в интервале времени t0 , ti  km Рис. 17. Задание финитного потока заявок Важными свойствами для классификации потоков заявок являются стационарность, ординарность и последействие. Поток называется стационарным, если число заявок, поступивших за какой-либо промежуток времени, зависит только от длительности этого промежутка и не зависит от места его нахождения на оси времени. Реальные потоки являются нестационарными, однако при решении практических задач можно допустить, что поток стационарен на ограниченном отрезке времени. Поток заявок является ординарным, если вероятность поступления двух и более заявок за бесконечно малый промежуток времени много меньше, чем вероятность поступления одной заявки. Поток является потоком без последействия, если вероятность поступления заявок за некоторый промежуток времени не зависит от процесса поступления заявок до этого промежутка. Основными характеристиками случайного потока заявок являются интенсивность и параметр. Они описывают законы поступления заявок и моменты времени, в которые поступают заявки, соответственно. Интенсивностью стационарного случайного потока называется математическое ожидание числа заявок, поступающих в потоке за единицу времени. Она характеризует именно поток заявок, а не моменты времени, когда эти заявки поступали в систему. Параметр стационарного потока определяет плотность вероятности наступления момента поступления хотя бы одной заявки в произвольный момент времени. Рассчитывается как предел отношения вероятности поступления не менее одной заявки за интервал времени к величине этого интервала, стремящегося к нулю. Стационарный ординарный поток без последействия называется пуассоновским или простейшим. В теории телетрафика при построении моделей СМО наиболее часто используют именно простейший поток. Это оправдано, поскольку потоки, циркулирующие в реальных сетях, близки к простейшему по следующим причинам: поток, полученный в результате объединения n независимых рекуррентных потоков, имеющих равномерно малую интенсивность, при увеличении n сходится к простейшему; объединение двух простейших потоков дает простейший поток; просеивание простейшего потока, когда поступившая заявка принимается с вероятностью P, а с вероятностью 1-P игнорируется, дает простейший поток; рекуррентный поток с показательной функцией распределения интервалов времени между заявками является простейшим; интенсивность простейшего потока равна его параметру. Вероятность поступления k заявок за время t у простейшего потока задается формулой Пуассона: pk (t )  ( t ) k  t e , k! где λ – интенсивность потока заявок. Функция, плотность распределения, математическое ожидание и дисперсия случайного времени между заявками для простейшего потока равны, соответственно: 1 1 f (t )  Ae  t ; F (t )  1  e  t ; M [t ]  ; D[t ]  .  2 Процесс обслуживания потока заявок сопровождается занятием и освобождением обслуживающих приборов. Занятие – это событие, которое заключается в выделении одного (или нескольких) из свободных приборов в распоряжение одной из поступивших заявок. Занятие характеризуется типом заявки, моментом и длительностью. В момент занятия прибор становится недоступен для других заявок того же типа. Освобождение – это событие, которое заключается в окончании процесса обслуживания заявки обслуживающим прибором. Освобождение характеризуется моментом времени. В момент освобождения прибор становится доступен для обслуживания других заявок. В теории телетрафика исследуют потоки занятий и освобождений применительно как к группе обслуживающих приборов, так и к каждому прибору в отдельности. Поток освобождений зависит от свойств потока заявок, дисциплины обслуживания и времени обслуживания заявок. В теории телетрафика предполагают, что обслуживание рекуррентно. Это означает, что времена обслуживания последовательных запросов являются независимыми одинаково распределенными случайными величинами. Если дисциплина обслуживания предполагает потерю заявок без предоставления им обслуживания, то возникает задача исследования потока потерянных заявок (рис. 18). заявок оте ок п т о П { рь 1 . . . n { Поток Поток освобождений Приборы занимаются на время обслуживания Рис. 18. Образование потоков занятий, освобождений и потерь Поток заявок обладает последействием если его параметр на некотором промежутке времени зависит от процесса поступления заявок до этого промежутка времени. Исследование последействия в общем виде трудноразрешимая задача, однако в теории телетрафика рассматриваются модели некоторых частных случаев последействия. Симметричный поток – это поток, параметр которого λi в момент времени t зависит от числа обслуживаемых заявок: λi  F (t , i ), где F – функция, задающая вид зависимости, i – число обслуживаемых заявок (учитывает последействие). Примитивный поток – это такой симметричный поток, у которого функция F линейна и параметр λi прямо пропорционален числу свободных пользователей: λi   N-i  , где N – число пользователей, α – параметр потока заявок от одного пользователя. При моделировании примитивного потока предполагается, что занятый пользователь не генерирует заявки. Поэтому количество обслуживающих устройств не должно превышать число пользователей. Если N→∞ и α→0, а знания Nα и i ограничено, то примитивный поток превращается в простейший. Поток с повторными заявками представляет собой смесь первичных и повторных заявок. Если первичный поток простейший, то параметр суммарного потока равен: Λ  λ  j , где j – число источников повторных заявок, зависящее от потока потерь (учитывает последействие), β – параметр потока повторных заявок от одного источника. На рис. 19 приведена временная диаграмма, иллюстрирующая процесс обслуживания 11 заявок СМО G/G/2 и механизмы формирования потоков занятий, потерь и освобождений. Временная диаграмма на рис. 20 относится к СМО G/G/2/1. Сравнение рис. 19 и 20 показывает, насколько существенно изменяется процесс обслуживания при, как кажется, незначительном изменении алгоритмов обслуживания. Использование дисциплины с ожидание и ограниченным по размеру буфером (рис. 20) приводит к существенному повышению использования обслуживающих приборов и уменьшению числа потерянных заявок. В тоже время заявкам 3, 4, 6, 8, 10 приходится ожидать начала обслуживания, находясь в буфере. 2.4. Время обслуживания. Двумя «предельными» случаями распределения времени обслуживания заявок являются детерминированное и показательное (экспоненциальное) распределения. 1 2 4 3 6 5 7 9 8 10 11 Поток заявок ... Прибор занят Занят Занят Занят Первый прибор Занят Время занятия (обслуживания) Второй прибор Занят Прибор занят Время занятия (обслуживания) Поток занятий 1 2 4 6 7 8 11 9 Поток потерь 3 10 5 Поток освобождений 1 4 2 6 8 7 9 11 Рис.19. Временная диаграмма функционирования СМО G/G/2 Детерминированное время обслуживания задается константой. Это означает, что для обслуживания любой заявки затрачивается одинаковое время. Этот случай характерен для автоматических систем, когда обслуживается однородный поток заявок и процесс обслуживания не зависит от поведения людей. Если время обслуживания имеет экспоненциальное распределение с параметром μ, то функция распределения, плотность распределения, математическое ожидание, дисперсия и коэффициент вариации равны, соответственно: B(t )  1  e  t ; b(t )  e  t ; M  X   1  ; D X   1 2 ;  X   D X   1. M X  Физический смысл параметра μ – это интенсивность освобождения обслуживающих приборов, измеряемая в единицах, обратных единицам времени. 1 2 4 3 6 5 7 9 8 11 10 Поток заявок ... Первый прибор Занят, заявка 1 Заявка 3 Заявка 4 Заявка 7 Заявка 8 Заявка 10 Время занятия (обслуживания) Заявка 6 Прибор занят, заявка 2 Заявка 9 Второй прибор 10 Ячейка буфера Время занятия (обслуживания) 3 4 6 8 Поток занятий 1 3 2 4 6 7 8 9 11 5 1 10 3 2 4 76 Поток потерь Поток освобождений 8 9 Рис.20. Временная диаграмма функционирования СМО G/G/2/1 Экспоненциальное распределение часто имеют процессы, продолжительность которых зависит от человека, например, такие как продолжительность телефонного разговора. В случае автоматических систем показательное распределение можно использовать для неоднородного потока заявок, где заявка каждого типа имеет свое постоянное время обслуживания, а смесь заявок уже может рассматриваться как однородный поток с экспоненциальным временем обслуживания. Предположение об экспоненциальном времени обслуживания существенно упрощает анализ, т.к. это единственное распределение, которое не имеет последействия. Если параметр показательного распределения равен μ=0,5 1/сек., то математическое ожидание, дисперсия и среднеквадратическое отклонение времени обслуживания равны, соответственно, 2 сек., 4 сек. и 2 сек. На рис. 21 и 22 приводятся графики функции распределения вероятностей и плотности распределения экспоненциального распределения при значениях μ=0,5; 1 и 2 1/сек. Экспоненциальное распределение имеет «легкий хвост». Это означает, что по мере увеличения времени плотность распределения вероятностей быстро стремиться к нулю и вероятность того, что случайная величина примет большие значения мала. Рис. 21. Функция распределения вероятностей экспоненциального распределения Один из путей получения аналитических результатов при неэкспоненциальном характере времени обслуживания заключается в аппроксимации реальных распределений фазовыми, такими, которые представляют собой композицию экспоненциальных распределений. Рассмотрим следующие фазовые распределения: гиперэкспоненциальное, эрланговское, нормализованное эрланговское, гиперэрланговское. Рис.22. Плотность экспоненциального распределения Гиперэкспоненциальное распределение порядка n представляет собой аддитивную смесь n экспоненциальных распределений (рис. 23) и содержит (2n-1) параметров: вероятности α1,…, αi,…, αn, где α1+ αi+αn=1; интенсивности µ1,…, µi,…, µn. График функции плотности гиперэкспоненциального распределения представлен на рис. 24. Такое распределение обычно используется для аппроксимации произвольных распределений с коэффициентом вариации 1<υ, поскольку у таких распределений вероятность появления значений случайной величины меньших математического ожидания больше, чем у экспоненциального распределения. 1 i n 1 ... i ... n Рис.23. Параметры гиперэкспоненциального распределения Функция распределения, плотность вероятностей, математическое ожидание и дисперсия гиперэрланговского распределения имеют, соответственно, следующий вид: n b(t )    i i e i 1  i t ; n  M X    i ; i 1 i n  D X    i ; 2 i 1 i n B (t )  1    i e  i t . i 1 Рис.24. Плотность гиперэкспоненциального распределения Распределение Эрланга порядка r представляет собой сумму r случайных величин (рис. 25), распределенных по одному и тому же экспоненциальному закону с параметром µ. 1  j ... r  ...  Рис.25. Параметры распределения Эрланга Функция распределения, плотность вероятности, математическое ожидание, дисперсия и коэффициент вариации зависят от двух параметров µ и r и имеют вид: r 1 t  t  r r 1 t ; D X   ; B (t )  1  e  ; b(t )  e t ; M X   . X    r r  1! 2 j  0 j! i Рис.26. Плотность распределения Эрланга r Графики функции плотности гиперэкспоненциального распределения в разных масштабах времени представлены на рис. 26 и 27, из которых следует, что распределение вероятностей существенно зависит от параметра r. Рис. 27. Плотность распределения Эрланга Коэффициент вариации распределения Эрланга принимает значения меньше 1 и вероятность появления значений случайной величины, которые больше математического ожидания выше, чем у экспоненциального распределения. Зависимость математического ожидания случайной величины, имеющей распределение Эрланга, от порядка (ранга) распределения r затрудняет его использование при аппроксимации реальных распределений. Поэтому чаще используют нормированное распределение Эрланга. У нормированного распределения Эрланга на каждой фазе имеется экспоненциальное распределение с параметром rµ и математическое ожидание не зависит от параметра r: D X   1 r 2 ; M X   1  ; b(t )  e  rt r 1 rt  j rrt r ; B (t )  1  e  rt  . r  1! j ! j 0 Если допустить, чтобы разные фазы распределения имели разные в параметры μi , то эрланговское распределение превращается гипоэкспоненциальное, у которого: D X   r  1 i 1 i  2 ; M X   r 1  i 1 i . Графики плотности распределения нормированного распределения Эрланга приведены на рис. 28. Рис. 28. Плотность нормированного распределения Эрланга По мере увеличения порядка r нормированное распределение Эрланга приближается к детерминированной величине 1/ µ. Гиперэрланговское распределение представляет собой аддитивную смесь n нормированных распределений Эрланга (рис. 29) и является наиболее общим из всех рассмотренных фазовых распределений. Коэффициент вариации гиперэрланговского распределения изменяется в пределах от 0 до ∞. Гиперэрланговское распределение задается (3n-1) параметрами: порядок (ранг) нормированных распределений Эрланга r1,…, ri,…, rn; вероятности α1,…, αi,…, αn, где α1+ αi+αn=1; интенсивности µ1,…, µi,…, µn. Подбором значений этих параметров можно достаточно точно аппроксимировать практически любую функцию распределения вероятностей. 1 1 i n μ1 1 i 1 n ... j μ1 ... ... ... j i ... j n ... ... μ1 r1 ri i rn ... n Рисунок 29. Параметры гиперэрланговского распределения Плотность вероятностей, математическое ожидание и дисперсия гиперэрланговского распределения равны: n  n r  1  n  2 i i     ; M X    i ; D X      2 i 1 i i 1 ri i  i 1 i  n r  r  t ri 1 b(t )    i e  ri i t i i i i .   r  1 ! i i 1 2.5. Дисциплина обслуживания Заявка на обслуживание – это событие, которое заключается в заказе источником заявки некоторых услуг, которые могут быть предоставлены ему при помощи обслуживающих приборов[7]. Заявки являются в СМО представителями пользователей (источников заявок). С каждой заявкой связана та или иная информация, которая отличает ее от других заявок и влияет на процесс дальнейшего обслуживания. Примером такой информации могут служить: момент времени возникновения заявки, приоритет (преимущественное право на обслуживание) по отношению к другим заявкам, время, которое потребуется для обслуживания заявки, время, которое источник заявки согласен ждать начала (или окончания) обслуживания выработанной им заявки и др. Чем выше однородность потока заявок, тем меньше данных следует хранить о каждой заявке в отдельности. В СМО с однородным потоком заявок информация о каждой заявке ограничивается самим фактом ее возникновения в некоторый момент времени. В информационных и телекоммуникационных системах поступление заявки сопровождается записью информации о ней в некоторый буфер. Буфер – это область памяти, которая используется для синхронизации процессов поступления заявок и процессов их обслуживания. Информация о заявках хранится в буфере с момента их возникновения до момента поступления на обслуживание или удаления из системы. Объем памяти, выделенной под буфер, называется размером (емкостью) буфера. Ячейкой буфера называется такая часть емкости буфера, которая необходима для хранения информации об одной заявке. Применительно к СМО емкость буфера измеряется количеством ячеек, на которое он может быть разделен. Если заявка принимается на обслуживание в момент возникновения, то считается, что заявке не требуется свободная ячейка в буфере, а время пребывания в буфере такой заявки принимается равным 0. СМО может не иметь ни одного буфера или иметь несколько буферов разной емкости. При моделировании, как правило, предполагают, что заявки разного вида (с разными приоритетами, с разными требованиями к качеству обслуживания, поступающие от источников разного типа и т.п.) фиксируются в разных буферах. Заявки, хранящиеся в буфере в некоторый момент времени, образуют очередь – это некоторым специальным образом упорядоченная структура данных, элементами которой являются данные о каждой поступившей в систему и зафиксированной заявке. Длина очереди – это количество заявок, зафиксированных в ней в некоторый момент времени. Длина очереди является случайной величиной и может изменяться в процессе функционирования СМО от 0 до величины емкости буфера. В процессе функционирования СМО над очередью должны реализовываться следующие три операции: добавление в очередь вновь поступившей заявки, выборка из очереди очередной заявки для передачи ее на обслуживание, удаление из очереди заявки, принятой на обслуживание или покидающей систему. Время пребывания в очереди – это интервал времени с момента добавления заявки в очередь до момента ее выборки или удаления из очереди. Время пребывания является случайной величиной и зависит, в том числе, от реализованных в СМО алгоритмов выбора и удаления заявок из очереди. Правило, по которому осуществляется движение заявок в СМО, называют дисциплиной обслуживания. Количество заявок в СМО в произвольный момент времени складывается из количества заявок, находящихся в очередях и на обслуживающих приборах. Для среднего числа L заявок, находящихся в СМО в стационарном режиме при произвольном потоке заявок, любом распределении времени обслуживания и независимо от дисциплины обслуживания справедлива формула Литтла: L  W , где W – среднее время пребывания заявок в СМО, которое складывается из средних времен их пребывания в очереди и на обслуживающих приборах, λ – интенсивность потока заявок. С точки зрения возможных исходов пребывания заявок в системе различают дисциплины обслуживания без потерь, с условными потерями, с явными потерями[19]. При обслуживании без потерь не устанавливаются нормы на качество обслуживания и ситуация, когда необслуженная заявка покидает систему, возникнуть не может. К числу таких СМО относятся системы с бесконечным числом обслуживающих приборов и с неограниченной емкостью буфера. Под условными потерями понимают события, заключающиеся в обслуживании с нарушением установленного для заявки времени пребывания в очереди или в системе. Под явными потерями (или просто потерями) понимают такие события, в результате которых заявка покидает систему, не получив обслуживания, например: в системе с потерями. Буферы для организации очередей отсутствуют, и заявка покидает систему (теряется), если в момент ее поступления заняты все обслуживающие приборы; в системе с ограниченной емкостью буферов. Заявка занимает свободную ячейку буфера, если в момент ее поступления заняты все обслуживающие приборы или покидает систему (теряется), если в момент ее поступления кроме того заняты все ячейки в буферах; в системе с ограниченным временем ожидания. Буферы неограниченны по размеру. В момент поступления заявки устанавливается момент времени, до которого заявка может ожидать начала (или окончания) обслуживания. Если до этого момента обслуживание не закончилось, то заявка покидает систему (теряется). Возможны различные комбинации перечисленных дисциплин обслуживания. К числу дисциплин обслуживания, учитывающих при выборке заявок из очереди только момент возникновения заявок, относятся два алгоритма управления очередями. Дисциплина FIFO (First Input, First Output – первой пришла, первой обслужена) обеспечивает равноправность заявок перед системой обслуживания. Время ожидания в очереди начала обслуживания одинаково распределено у всех заявок, независимо от момента поступления или какихлибо других характеристик заявки. Дисциплина LIFO (Last Input, First Output – последней пришла, первой обслужена) используется при обработке прерываний, а для организации очередей заявок на обслуживание не используется. Если СМО располагает дополнительной информацией о времени обслуживания заявок и о допустимом времени их пребывания в системе, то возможны такие правила управления, при которых первыми обслуживаются заявки с меньшим временем обслуживания или допустимым временем пребывания в системе. В первом случае преимущество, которое получают «короткие» заявки, позволяет сократить не только время их пребывания в системе, но и среднюю длину очереди и, следовательно, стоимость ресурсов, необходимых для создания буферов. Преимущество, которое возникает при упорядочении заявок по допустимому времени пребывания, получают «срочные» заявки и уменьшаются вероятности явных и условных потерь. Дисциплиной обслуживания, которая не учитывает никаких характеристик заявок, является дисциплина RAND, в соответствии с которой заявки выбираются из очереди случайным образом, например, в соответствии с равномерным законом распределения. В процессе обслуживания заявки могут прерываться. Прерывание – это событие, в соответствии с которым СМО приостанавливает обслуживание заявки, уже занимающей обслуживающий прибор, и возвращает ее в очередь. Различают прерывания с дообслуживанием (общее время пребывания заявки на обслуживающем приборе не зависит от количества прерываний) и с повторным обслуживанием (каждый раз обслуживание прерванной заявки начинается заново). Прерывание заявок используется при обслуживании по ∆-расписанию. В этом случае заявка, поступившая на обслуживание, занимает обслуживающий прибор не дольше чем на квант времени ∆. Если за это время обслуживание не закончилось, то производится прерывание с дообслуживанием и заявка возвращается в очередь. Для полного обслуживания ей необходимо занять прибор несколько раз. ∆-расписание может быть реализовано без предоставления и с предоставлением преимущества при доступе к обслуживанию. Первый режим реализует параллельную обработку заявок. Каждая заявка быстро получает доступ к обслуживанию и начинает выполняться. Используется в тех случаях, когда процесс обслуживания имеет самостоятельное значение наряду с фактом окончания обслуживания. Если квант времени ∆ достаточно мал и на обработку прерываний расходуется небольшое время, то этот алгоритм обеспечивает одновременную обработку многих заявок, предоставляя им часть ресурса системы. Преимущество в обслуживании может быть реализовано либо за счет увеличения кванта времени, которое выделяется заявкам определенного вида, либо за счет составления расписания, в соответствии с которым заявки, нуждающиеся в преимуществе, будут чаще направляться на обслуживающие приборы. Задание преимущества тем или иным типам заявок может быть обеспечено и при помощи приоритетов. Приоритет – это число, которое сопоставляется заявкам и классифицирует их в соответствии с преимуществом при обслуживании. Все заявки, поступающие в СМО, делятся на группы и получают приоритеты 1, 2, …, N. Обычно заявки с более высоким приоритетом имеют меньший номер. Среди заявок с одинаковым приоритетом образуется очередь FIFO. Различают относительные и абсолютные приоритеты. В СМО с относительными приоритетами обслуживание заявок не прерывается. Если заявка с приоритетом i (i=1, 2, …, N) поступила в систему и застала все обслуживающие приборы занятыми, то она встает в отдельную очередь заявок с таким же приоритетом. В момент освобождения какоголибо обслуживающего прибора на обслуживание будет взята первая заявка из очереди с наивысшим приоритетом. В СМО с абсолютными приоритетами заявка с приоритетом i (i=1, 2, …, N) прерывает обслуживание заявки с приоритетом j (j=1, 2, …, N) если iV) получим формулу для расчета потерь по времени (она же вероятность ожидания начала обслуживания), которая называется второй формулой Эрланга:  EV ( A) 1 AV Pt  P( 0)   Pi  P0  . A ! 1 / V A V  i V 1  1  EV ( A)  V Для средней длины очереди справедливо соотношение:  A  EV ( A) V n   (k  V ) * Pk  , ( V  A )  A  E ( A ) V  A V k V где A < V. Контрольные вопросы ко 2 главе 1. Как можно сформулировать основную проблему, решаемую в рамках теории телетрафика? 2. Какие ошибки в процессе проектирования сетей связи ведут к понижению эффективности их использования? 3. Что является объектом исследования теории телетрафика? 4. Цели и задачи теории телетрафика? 5. Какие различают методы решения задач теории телетрафика? 6. Описание СМО с использованием систематики Кендалла? 7. Что такое поток заявок(ПЗ)? Детерминированный ПЗ? Рекуррентный ПЗ? Однородный ПЗ? Финитный ПЗ? Симметричный ПЗ? 8. Перечислите основные характеристики случайного ПЗ? 9. Какими свойствами обладает простейший ПЗ? 10. Для каких реальных процессов в сетях связи характерно экспоненциальное распределение времени обслуживания? 11. Чему равно математическое ожидание и дисперсия времени обслуживания, если время обслуживания имеет экспоненциальное распределение с параметром μ=0,1 1/сек.? Каков физический смысл параметра μ? 12. Что означает выражение: “Экспоненциальное распределение имеет «легкий хвост»”? 13. Что в теории телетрафика называется ячейкой буфера? 14. Какие операции над очередью реализуются в процессе функционирования СМО? 15. Какие, с точки зрения возможных исходов пребывания заявок в системе, различают дисциплины обслуживания в СМО? 16. Какие особенности алгоритмов управления очередью FIFO и LIFO? 17. Каким образом в СМО задается преимущество в обслуживании заявок? 18. Что позволяет сделать использование приоритетных процедур обслуживания? 19. Какой случайный процесс называется марковским? 20. Какая случайная последовательность называется марковской цепью, чем характеризуются марковские цепи? 21. Процесс функционирования систем называется процессом рождения и гибели? 22. Что позволяет вычислить первая формула Эрланга? При каких предположениях она справедлива? 23. Что позволяет вычислить вторая формула Эрланга? При каких предположениях она справедлива?