Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
3 МОДЕЛИ СИСТЕМ РАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ Теория телетрафика оперирует не с самими системами распределения информации, а с их математическими моделями. Для полного описания СРИ необходимо указать вероятностные процессы, описывающие входной поток требований, структуру системы и дисциплину обслуживания. Следовательно, математическая модель СРИ содержит такие основные элементы: 1. Входной поток требований на обслуживание (трафик) – классифи- цируется по признакам стационарности, ординарности и последействия. Основными характеристиками потока есть его параметр и интенсивность λ. 2. Структура системы распределения информации – это информация о количестве обслуживающих устройств или серверов (дающих услуги), их взаимное соединение (схема) и доступность для входных требований. 3. Дисциплина обслуживания потока требований – характеризует взаимодействие потока требований с системой распределения информации. В теории телетрафика дисциплина обслуживания описывается: способом обслуживания требований; порядком обслуживания требований; режимами поиска выходов схемы (произвольный или групповой); законами распределения продолжительности обслуживания; наличием преимуществ (приоритетов) в обслуживании требований; наличием ограничений при обслуживании (по продолжительности ожидания или обслуживания, количеству ожидающих требований); законами распределения вероятностей поломки элементов схемы. Входной поток требований описывается функцией распределения вероятностей длины интервалов времени между соседними требованиями A(z): A(z) = P(≤ z), (3.1) где P(≤ z) – вероятность того, что время между соседними требованиями ≤ z. Если интервалы времени между соседними требованиями независимые и одинаково распределенные случайные величины, то входной поток образует стационарный процесс восстановления. При этом неизменны во времени вероятностные характеристики случайных процессов, что соответствует реальным процессам в СМО на небольших отрезках времени. Значит, функция распределения интервалов A(z) достаточна для описания потока требований. Время, в течении которого требование находится в сервере, описывается функцией распределения вероятностей продолжительности обслуживания В(x): В(x) = P(≤ x), (3.2) где P(≤ x) – вероятность того, что время обслуживания ≤ x. Для описания интервала времени между соседними требованиями или продолжительности обслуживания применяются разные законы. Чаще всего используются распределения, данные ниже и обозначенные буквами: – M – экспоненциальный (M – марковская модель) – коэф. вар. v x = 1; – H – гиперэкспоненциальный (Hyper-exponential) – вар.v x = 1 … ∞; – D – детерминированный (Determined) – коэф. вар.v x = 0; 17 – U – равномерный (Uniform) – коэф. вар. v x = 0,58; – E – распределение Эрланга – коэф. вар.v x = 0 … 1; – G – произвольный или обобщенный (General). Дисциплина обслуживания потока требований определяет правила обслуживания и судьбу требований при их поступлении в систему. Различают такие типы СМО, которые определяются способом обслуживания требований: 1. Системы с потерями – требования, которые при поступлении в систему не находят в ней ни одного свободного сервера, получают отказ в обслуживании и теряются. 2. Системы с очередями – требования, которые не могут быть обслужены сразу из-за занятости всех серверов системы, становятся в очередь, и с помощью некоторой дисциплины обслуживания очереди определяется, в каком порядке ожидающие требования выбираются из очереди для обслуживания. Наиболее распространенными дисциплинами обслуживания очереди есть: – FF (FIFO – first in first out) – требования из очереди обслуживаются в порядке их поступления (упорядоченная очередь); – LF (LIFO – last in first out) – каждый раз преимущество для обслуживания имеет требование, поступившее в очередь последним; – SR (SIRO – service in random order) – следующее требование для обслуживания из очереди выбирается случайно (случайная очередь). 3. Комбинированные системы с очередями и потерями (системы с очередью при ограничениях). Например, ожидать может только конечное количество требований, обусловленное количеством мест ожидания, меньше бесконечности. Возможно и так – требование теряется тогда, когда время ожидания в очереди или пребывание в системе превышает заданные границы. 4. Приоритетные системы – для требований предусмотрены разные приоритеты в обслуживании. Если требование, которое поступило, имеет высокий приоритет, а все серверы заняты, то оно или занимает одно из первых мест в очереди, или временно прекращает обслуживание требования низкого приоритета и занимает его место в сервере. При этом могут быть применены такие приоритетные правила: – абсолютный приоритет с прерыванием (pre-emptive discipline) – требование высокого приоритета перерывает обслуживание требования низкого приоритета. Может быть: абсолютный приоритет с потерями (pre-emptive loss discipline), абсолютный приоритет с дообслуживанием (pre-emptive resume discipline) и абсолютный с обслуживанием сначала (pre-emptive repeat different discipline); – относительный приоритет (head of the line priority discipline) – требова- ние высшего приоритета станет в начало в очереди без прерывания. Смешанные приоритеты предопределяют выбор абсолютного или относительного приоритетного правила в зависимости от уже реализованной части продолжительности обслуживания, а динамические – в зависимости от типа текущих требований и соотношения количества требований разных приоритетов, который есть в серверах и в очереди. 18 Основные характеристики, представляющие структуру СРИ такие: кол-во обслуживающих устройств (серверов, линий, каналов, портов); количество мест ожидания или максимальная длина очереди (емкость памяти, в которой накапливаются ожидающие требования); доступность – способ включения серверов, где каждому требованию доступны все или не все (всем требованиям в совокупности доступны все) серверы. Схема бывает полнодоступной или неполнодоступной; взаимное соединение (схема) – способ включения серверов, где каждое требование обслуживается одним сервером или не одним, но поэтапно. Схема бывает однокаскадной или многокаскадной (цепной). Структурные характеристики системы частично предопределяют дисциплину обслуживания потока требований. Например, при количестве мест ожидания r = 0 будет система с потерями, при 0 < r < ∞ – комбинированная система с очередью и с потерями, a при r = ∞ – чистая система с очередью. Для сокращения записи Д. Кендаллом предложено специальное условное обозначение базовой модели, где из всех параметров математической модели СРИ представлены четыре элемента и записывается это так: A/B/m/r. Элемент А характеризует поток требований и определенной буквой из приведенных выше видов распределений помечается функция распределения вероятностей интервалов времени между соседними требованиями. Элемент В характеризует случайные последовательности длительности обслуживания на отдельных серверах системы и аналогично предыдущему может использовать такие же распределения. Элементы m и r характеризуют количество обслуживающих устройств и мест ожидания в системе соответственно. Сокращенная запись базовой модели кроме основных обозначений может содержать еще и дополнительные символы, которые указываются после знака „:” и могут уточнять особенности системы. Например. Запись M/D/120/r = ∞ означает, что СМО с m = 120 обслуживающими устройствами обслуживает простейший поток требований (M), где каждое требование имеет постоянную длительность обслуживания (D). Есть бесконечное количество мест ожидания (r = ∞), что и определяет дисциплину обслуживания с очередями. Запись G/M/120:Loss означает, что СРИ обслуживает произвольный поток требований с экспонентным распределением их длительности. Емкость накопительной памяти, где требования ожидают в случае занятия всех 120 серверов системы, равна нулю (не записывается), и поэтому данная система с потерями (Loss). Итак, базовая математическая модель СМО описывается рядом символов: первый – функция распределения интервалов времени между требованиями, второй – функция распределения продолжительности обслуживания, третий и следующий (необязательный) символы – схема и дисциплина обслуживания. Построение математической модели (рис. 3.1), адекватно отображающей реальную систему распределения информации, во многих случаях является непростой задачей. От правильного выбора модели зависит точность решения задач анализа, синтеза и оптимизации. 19 Р ис унок 3 .1 – К л ас сиф и к ац и я с ис те м м ас сов ог о об сл у ж и в ан и я СИ СТЕМЫ МАССОВОГ О ОБ СЛ У Ж И В АНИ Я Р аз ом к н у - ты е За м к н ут ы е С оч ере д я м и С п от еря м и М н ог о к ан ал ь н ы е О д н ок ан ал ь н ы е С пос об в ы б ора т ре б ов ан ий С пос об об сл уж и ван и я К ол -в о к ан ал ов С н еог ра н и ч оч ере д ь ю С ог ра н и ч оч ере д ь ю Б ез п ри ори те та С п р и ори - те том О д н о - род н ы е Н е од н о - р о д н ы е П ар ал л ел ьн о П ос л ед о - в ат ел ь н н о О гран ич ен ия н а оч ере д ь Д ис ципл и н а о ч ер ед и Х арак т ерис т ик а к ан а ло в В к лю ч ен ие к ан ал о в Н а д л и н у о ч ер ед и Н а в ре м я п ре б ы в ан и я в о ч ер ед и « П ер в ы м п ри ш ел – п ер в ы м о б сл уж ен » «П ос л ед н и м п ри ш ел – п ер в ы м о б сл уж ен » С л уч ай н ы й в ы б ор А б сол ю т- н ы й п р и ори те т О тн ос и - те л ь н ы й п р и ори те т С п ец и - ал ь н ы е п ра в и л а п р и ори те та В ид ог ран и ч ен ия В ы б ор т ре б ов ан ий и з о ч ер ед и Х арак т ерис т ик а пр и орит ет а 20 4 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПОТОКА ТРЕБОВАНИЙ В теории массового обслуживания одним из основных понятий есть случайная последовательность требований, поступающих в систему на обслуживание. Совокупность (последовательность) событий поступления в систему в моменты t 1 …t n требований образуют поток требований (рис. 4.1). Рисунок 4.1 – Поток требований на обслуживание Поток определяется моментами поступлений t x и количеством требова- ний k n , поступивших в момент t n . При этом k n и t n в общем случае случайны. У рекуррентного потока требований k n = 1для всех n = 1, 2, … , а интервалы времени между событиями поступления требованийz n = t n – t n-1 есть стохастично независимые и одинаково распределенные случайные величины. При постоянном интервале времени между требованиями z n поток есть детерминированным, однако, в телекоммуникациях потоки чаще случайные. Случайный поток требований может быть описанным двумя способами. 1. Случайный поток требований описывается функцией распределения вероятностей интервалов времени между соседними требованиями F(t): F(t) = P(z n ≤ t), (4.1) где P(z n ≤ t) – вероятность того, что время между соседними требованиями z n ≤ t. Основная характеристика потока – это среднее значение длительности интервалов z, что для случайной величины есть математическое ожидание z . Параметр, обратный к математическому ожиданию z , есть интенсивность потока поступления требований λ за единицу времени, коими измеряется z : z 1 (4.2) Например, при z = 0,1 с интенсивность потока λ = 10 требований в секунду, а при z = 100 мс – интенсивность потока λ = 0,01 требования в миллисекунду. Наиболее распространенной математической моделью потока требований в телефонных сетях связи является модель экспонентного распределения интервалов времени между требованиями (вызовами АТС) с параметром λ: t n e t z P 1 ) ( (4.3) Плотность этого распределения позволяет рассчитать вероятность любой продолжительности z x = t случайной величины z (интервалов между требованиями) по заданной интенсивности поступления требований λ: t e t p ) ( (4.4) Среднее значение случайной величины t, распределенной по экспонент- ному закону (4.4), равно λ -1 и потому из (4.2) следует, что параметр данного распределения λ – это среднее количество требований за единицу времени, в t 0 t 1 t 2 t 3 t 4 t 5 t 6 21 которых измеряется z . Поток, где все z n имеют одинаковое экспонентное распределение с параметром λ, очень важный пример рекуррентного потока. На рис. 4.2 представлены два графика экспонентного распределения (4.4), обозначеные p(z) и p1(z) с параметрами λ = 0,5 и λ1 = 0,25 соответственно. Рисунок 4.2 – Экспонентное распределение интервала z Из графиков видно, что в потоке, заданного функцией p(z), значительно больше доля вероятностей коротких интервалов между требованиями, чем в потоке, заданного функцией p1(z). Это говорит о большей интенсивности потока требований, которая в первом случае составляет λ = 0,5, а во втором – λ1 = 0,25 требований в единицу времени. Среднее значение интервала времени между требованиями такое: z = 2 и 1 z = 4 единицы времени соответственно. 2. Случайный поток требований описывается функцией P i (t) – распреде- лением вероятностей количества требований i за условную единицу времени t. Например, если диаграмму процесса поступления требований, представленную на рис. 4.1, условно поделить на одинаковые промежутки времени длительностью t, что в разы или десятки раз превышает среднее значение интервалов z , то на каждый из таких условных интервалов припадет случайное количество требований i. Функция распределения случайной величины i будет описывать поток требований, поступающих в систему на обслуживание. Известно, если интервал времени между событиями (требованиями) z распределен по экспонентному закону, то количество таких событий i за условную единицу времени t будет распределено по закону Пуассона: t e i t t P i i ! ) ( ) ( (4.5) Величина λt это параметр распределения Пуассона. По нему можно рассчитать вероятность поступления в систему точно i требований за условную единицу времени длительностью t, зная интенсивность потока требований λ. Для приведенного выше примера экспонентного потока с интенсивностью λ = 0,5 построено распределение Пуассона случайного количества требований, которое приходится на условные интервалы времени, например, продолжительностью t = 20 c (рис. 4.3). 22 Рисунок 4.3 – Распределение Пуассона при λ = 0,5 и t = 20 c Среднее значение случайной величины i, распределенной по закону (4.5), определяется как t i , и в этом случае λt = 10. Из рис. 4.3 видно, что вероятность такого значения количества требований i за условную единицу времени t есть наибольшей, и это есть вероятность среднего значения i . При возрастании i от нуля к i вероятность P i (t) постепенно возрастает, а потом – уменьшается. Данный график почти симметричный, а форма аппроксими- рующей кривой приближается к форме нормального закона распределения. Таким образом, математическую модель потока требований, поступающего в СРИ на обслуживание, можно отобразить двумя способами с помощью вероятностных функций распределения: интервалов времени между соседними требованиями z, (4.4); количества требований i за условную единицу времени t, (4.5). В первом случае, применяются непрерывные законы, а во втором – дискретные. Каждый из потоков называется по виду вероятностного закона распределения интервалов времени между требованиями или их количества за условную единицу времени. Модель потока, определяемая распределением (4.5) называется пуассоновским потоком (используется в телефонных сетях). Пуассоновские потоки делятся на потоки первого и второго рода. Для потоков первого рода вероятность поступления требований в систему не зависит от того, сколько требований уже есть в ней. СМО с такими потоками называются системами с бесконечным числом источников или открытыми системами. Потоки первого рода возникают из-за наложения многих потоков отдельных источников, причем поведение каждого источника независимо. Потоки требований второго рода получаются в СМО с конечным числом источников или в так называемых замкнутых системах. Поскольку в момент, когда требование обслуживается или ожидает, ее источник уже не может порождать новых требований, то вероятность того, что поступит требование из совокупности требований всех источников, зависит от того, сколько требований в системе и от каких они источников. Такие потоки называются примитивными. 23 Оценка качества обслуживания или пропускной способности СРИ требует учета всех элементов ее модели. Наиболее сложно учесть математическую модель входного потока требований. Именно по этой причине весь пакет задач анализа и синтеза СРИ для любых из ее схем и дисциплин обслуживания решен только для случая простейшей модели трафика – пуассоновского потока. Для неё известны все аналитические формулы расчета основных характеристик качества обслуживания в системах распределения информации [1-3]. Стремительное развитие телекоммуникационных технологий, новые принципы построения сетей связи, изменение структурного состава абонентов и спектра предоставляемых услуг влияет на изменение характера трафика. Эти факторы увеличивают неравномерность интенсивности потоков требований, измеряемую дисперсией интенсивности. Результаты статистических измерений, выполняемых на разных сетях связи, дают возможность выделить 3 типа трафика, к которым следует употреблять следующие математические модели: I тип – в моносервисных сетях с однородным трафиком. Это телефонные сети с единственной услугой телефонной связи, а поэтому трафик однородный. Простейшая модель пуассоновского потока соответствует таким условиям, а значения интенсивности трафика и ее дисперсии достаточно близки. ІІ тип – в мультисервисных сетях с разнородным трафиком. Интегральный характер мультисервисной сети с расширенным спектром предоставляемых услуг предопределяет разнородность трафика, которая сильно изменяет его параметры и математическую модель. Реальным потокам присуща повышенная неравномерность трафика, при которой дисперсия интенсивности трафика превышает ее математическое ожидание от 2 до 15 раз. Иногда данное превышение бывает и большим, но это происходит или за пределами ЧНН, или на небольших пучках каналов [4]. ІІІ тип – в пакетных сетях с мультисервисным трафиком. Трафик имеет долгосрочные зависимости в интенсивности и еще более существенно отличается от пуассоновского потока. Адекватной моделью потоков в таких сетях есть самоподобные процессы. В мультисервисных пакетных сетях трафик есть разнородным и с определенными требованиями к QoS. Здесь передачу потоков разных служб обеспечивает одна и та же сеть с едиными протоколами и законами управления. Поскольку источники каждой службы могут иметь разные скорости передачи информации или изменять ее в процессе сеанса связи, то объединенному потоку пакетов присуща так называемая «пачечность» трафика (burstness), измеряемая коэффициентом пачечности [1]. Эта пачечность обуславливает еще большую неравномерность трафика, при которой дисперсия интенсивности трафика превышает ее математическое ожидание от 20 до 60 раз и большее. Независимо от способа задания математической модели потока требований выбранная модель обязательно должна быть адекватной реальным потокам трафика телекоммуникационных сетей, поскольку от этого существенно зависит точность расчета характеристик качества обслуживания и пропускной способности СРИ при их анализе, синтезе и оптимизации. |