Предметная область теории распределения информации

Лекция №1

по дисциплине “Теория распределение информации»

Наименование темы: Предметная область теории распределения информации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Единицей измерения интенсивности нагрузки является один Эрланг (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-дневного периода (повышенная интенсивность или уровень В). На рисунке 2 приведены результаты измерения интенсивности нагрузки на нескольких городских АТС. Как видно из рисунков час наибольшей нагрузки может быть различным на различных АТС.

Эрл

120

100

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 час

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

PAGE 5

Предметная область теории распределения информации