Информационные процессы и конфликты обслуживания

Основу всех процессов в телекоммуникационных системах составляет передача и обработка сообщений, под которыми мы понимаем некоторое одномерное представление информации с выделенными началом и концом. Появление в системе каждого сообщения будем отождествлять с требованием (arrival) на его передачу или обработку. Обработка или передача каждого сообщения занимает некоторое конечное время, называемое в теории телетрафика время обслуживания (holding time). Часть системы, участвующая в процессе передачи или обработки сообщения так, что одновременно с ним никакое другое сообщение не может обрабатываться этой частью, назовем сервером (server). Таким образом, если система содержит ровно один сервер, то в каждый момент времени она способна обслуживать не более чем одно требование. Если на такую систему, занятую обслуживанием, в течение интервала времени обслуживания поступит еще одно требование, то оно не сможет быть обслужено. Это простейший случай ресурсного конфликта – требования, поступающие друг за другом, не могут быть обслужены немедленно при поступлении или как говорят в реальном масштабе времени из-за того, что сервер не успевает обслужить требования за время между их поступлениями. Конфликт не возникнет, если система будет содержать не один, а несколько серверов, включенных так, чтобы поступающие требования распределялись бы для обслуживания на любой свободный из них в данный момент. Однако, очевидно, что если время обработки не бесконечно мало по сравнению с интервалом между поступлением требований, то и в системе с несколькими серверами может возникнуть ресурсный конфликт – поступившее требование не сможет получить немедленного обслуживания, так как все серверы окажутся занятыми в данный момент. В этом случае система может просто проигнорировать поступившее требование. Оно будет отброшено, а система, как говорят, будет считаться заблокированной. Вероятность такого события является важной характеристикой системы. Ее принято называть вероятностью блокировки ( blocking probability). Чтобы ни одно требование не было потеряно в результате ресурсного конфликта, в системе может быть предусмотрен специальный буфер памяти, в который будут помещаться требования, которые не могут быть обслужены немедленно при поступлении из-за занятости всех серверов. В этом случае говорят, что в системе организуется очередь(queue)требований или что рассматривается система с очередями (queuing system). В очереди может оказаться не одно, а несколько требований, если число поступающих требований за некоторый интервал времени превысит число освободившихся за это время серверов. Если очередь не будет бесконечно нарастать, все требования рано или поздно будут обслужены, однако время их пребывания в очереди будет разным и может рассматриваться как случайная величина. Распределение этой случайной величины также является важнейшей характеристикой системы обслуживания. Часто для оценки качества используется только ее среднее значение – среднее время ожидания обслуживания (average waiting time). Таким образом, недостаточность ресурсов в телекоммуникационной системе может приводить либо к потерям поступающих на обработку или передачу сообщений, либо к задержке их обслуживания.

1.1.2 Основные определения теории систем массового обслуживания

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

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

.

Для системы, содержащей один сервер, максимальная работа, которая может быть выполнена за время T , равна . Если система содержит n серверов, то за это время может быть выполнена работа .

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

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

Рис. 1.1. Временная диаграмма СМО из трех серверов.

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

.

Значит в рассмотренном случае работа, выполненная тремя серверами за 10 секунд равна 15 секундозанятиям. Заметьте сразу, что максимальная работа, которая могла бы быть выполнена ими за это время, равна 30 секундозанятий.

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

,

Для каждого сервера работа равна нулю, если в интервал сервер не занят, и равна , если сервер занят, поэтому, стоящее под знаком предела отношение равно 0 или 1. Значит для системы из n серверов физический смысл мгновенной нагрузки - это число серверов, занятых обслуживанием в данный момент времени. Поскольку мгновенная нагрузка величина случайная, то обычно используется ее математическое ожидание:

,

называемое интенсивностью нагрузки (traffic intensity), т.е. среднее число серверов, занятых в данный момент времени.

Символ « М<> » обозначает здесь и далее математическое ожидание случайной величины.

На практике, интенсивность нагрузки оценивается на конечном интервале . При этом полагают:

.

Единицей измерения интенсивности нагрузки является один Эрланг(1 Эрл). Из определения интенсивности нагрузки ясно, что 1 Эрланг – это интенсивность нагрузки, которая требует полной занятости СМО с одним сервером или интенсивность, при которой одним сервером выполняется работа величиной в одно секундозанятие за время в 1 секунду. В практической телефонии говорят об интенсивности нагрузки в 1 Эрланг как об интенсивности, определяющей одно часозанятие в час.

Вернемся к приведенному выше примеру СМО с тремя серверами, функционирование которой определено диаграммой на Рис.1.1.

Приведенная выше формула позволяет рассчитать мгновенную нагрузку в момент времени t =1 как i(1)=1+1=2 Эрланга, i(9)=1. Оценить интенсивность нагрузки можно, рассматривая работу на конечных интервалах времени. Если рассмотреть первые 5 секунд, то выполненная работа будет равна 8 секундозанятиям, а за последние 5 секунд – 7 секундозанятий, и интенсивность нагрузки в первой половине рассматриваемого интервала будет оцениваться величиной 8/5=1.6 Эрланга, а во второй половине – 7/5=1,4 Эрланга. Следовательно, величина интенсивности нагрузки носит локальный характер и позволяет описывать динамику, то есть изменения нагрузки в течение времени. Рассмотренная СМО, например, первые пять секунд работала более интенсивно, чем последующие пять. Более того, мы можем количественно сравнить эти изменения.

В практической телефонии в соответствие с рекомендацией ITU E.500 интенсивность нагрузки оценивается на интервалах длительностью в 15 минут и определяется средняя нагрузка в течение часа, в пределах которого эта нагрузка была максимальной. Обычно интервал времени длиной в час, интенсивность нагрузки, в течение которого бывает максимальной, повторяется каждые сутки, например с 11 до 12 часов. Такой интервал принято называть часом наибольшей нагрузки (ЧНН).

Рекомендация ITU E.500 определяет нагрузку в фиксированный ЧНН как среднее значение за 30 наиболее загруженных дней 12-месячного периода (нормальная интенсивность нагрузки ЧНН, или уровень А) и за 5 самых нагруженных дней 30-дневного периода (повышенная интенсивность или уровень В). На рисунке 1.2 приведены результаты измерения интенсивности нагрузки на нескольких городских АТС. Как видно из рисунков час наибольшей нагрузки может быть различным на различных АТС.

Эрл

120

Час

Рис.1.2. Результаты измерения интенсивности нагрузки на нескольких городских АТС.

В американской литературе вы можете встретить и другую единицу измерения интенсивности нагрузки, называемую CCS – Centrum (or hundred) calls second (гектосекундозанятия). Это число отражает работу серверов в сто секундных единиц измерения в течение часа.

Вы всегда можете пересчитать CCS в Эрланги по формуле

36 CCS=1 Эрланга

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

Ненулевое значение потерянной или избыточной нагрузки говорит о ненулевой вероятности блокировки или пропуска требований или ненулевом значении задержки требований во входной очереди. Как было уже отмечено выше, значения вероятности блокировки или пропуска, а также параметры функции распределения задержки, чаще всего среднее значение задержки, определяют так называемые показатели качества обслуживания (QoS-Quality of Service).

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

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

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

1.1.3 Модели потока требований

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

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

Стационарность - независимость вероятностных характеристик от времени. Так вероятность поступления определенного числа требований в интервал времени длиной t для стационарных потоков не зависит от выбора начала его измерения.

Последействие - вероятность поступления требований в интервале (t₁ , t₂) зависит от событий, произошедших до момента t₁.

Ординарность - вероятность поступления двух и более требований за бесконечно малый интервал времени Δt есть величина бесконечно малая более высокого порядка, чем Δt.

К основным характеристикам случайных потоков относят ведущую функцию, параметр потока и интенсивность потока.

Ведущей функцией потока называют математическое ожидание числа требований в промежутке времени (0,t).

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

.

Для стационарного потока параметр потока постоянный и равен:

.

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

Пуассоновский (простейший) поток запросов

Стационарный ординарный поток без последействия называют простейшим. Он задается набором вероятностей P_i(t) поступления i требований в промежутке длиной t.

Можно показать, что при этих предположениях формула для P_i(t) дается формулой Пуассона (Poisson):

.

Проанализируем основные характеристики пуассоновского потока. Рассмотрим отношение P_i(t)/P_i-1(t). При i ≤ λt вероятность растет, а при обратном соотношении – убывает. Графики функции распределения Пуассона в зависимости от величины λt для различных значений k приведены на рис. 1.3.

Рис. 1.3. Графики Пуассоновского распределения в зависимости от lt для различных k.

Наряду с распределением P_i(t) используют вероятности поступления не менее i требований в интервал t или не более i требований за время t:

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

.

Дифференцируя, получаем плотность распределения вероятностей: .

Случайная величина с такой плотностью вероятностей называется экспоненциально - распределенной (с показательным распределением). Математическое ожидание экспоненциально распределенной случайной величины равно

,

а дисперсия и среднеквадратическое отклонение соответственно будут равны:

,

.

Определим математическое ожидание и дисперсию числа требований за промежуток t :

,

.

Одним из важных свойств пуассоновского потока является аддитивность.

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

При разъединении пуассоновского потока на несколько потоков так, что каждое требование исходного потока с вероятностью p_i (Sp_i =1) поступает на i-тоенаправление, поток i направления будет также пуассоновским с интенсивностью lp _i.