1.2 Входящий поток, время обслуживания

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

Во входящем (случайном) потоке, запросы поступают в систему в некоторые случайные моменты времени Будем обозначать — длину интервала между моментами поступления запросов, полагается равным 0) и - число моментов лежащих на временной оси левее точки

Случайный поток считается заданным, если задано совместное распределение величин для любого или задано совместное распределение величин для всех значений

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

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

Определение 2. Случайный поток называется ординарным, если для любого t имеет место соотношение

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

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

Определение 3. Говорят, что случайный поток является потоком без последействия, если числа заявок, поступивших на непересекающихся интервалах времени, являются независимыми в совокупности случайными величинами.

Определение 4. Случайный поток называется потоком с ограниченным последействием, если величины независимы в совокупности.

Определение 5. Случайный поток называется рекуррентным потоком, если поток является потоком с ограниченным последействием и величины одинаково распределены.

Их функцию распределения будем обозначать Функция полностью характеризует рекуррентный поток.

Если распределение - показательное: то в обозначениях Кендалла первый символ принимает значение М.

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

Если распределение - гиперэкспоненциальное, то есть

где то в обозначениях Кендалла первый символ принимает значение

Если распределение - эрланговское с параметрами , то есть

то первый символ принимает значение Е. Параметр к называют порядком распределения Эрланга.

Более общим классом распределений, включающим гиперэкспоненциальное и эрланговское как частные случаи, является так называемое распределение фазового типа. В обозначениях Кендалла оно кодируется как PH. Подробную информацию о PH распределении, его свойствах и содержательной интерпретации можно найти в [12].

Если о виде функции распределения не делается никаких предположений, то в качестве первого символа в обозначениях Кендалла используются буквы G (General) или GI (General Independent).

Строго говоря, использование символа G не предполагает даже требования рекуррентности потока, а символ GI означает именно рекуррентный поток. Но в литературе иногда не делается различия между этими символами.

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

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

Определение 8. Стационарный ординарный поток без последействия называется простейшим.

Справедливы следующие утверждения.

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

Утверждение 2. Для того, чтобы поток был простейшим, необходимо и достаточно, чтобы он был рекуррентным с показательным распределением длин интервалов между моментами поступления запросов:

Утверждение 3. Если известно, что на интервале длины Т поступило запросов простейшего потока, то вероятность поступления фиксированного запроса на части этого интервала длиной не зависит от того, когда поступали другие запросы, и от расположения этой части внутри интервала и равна

Утверждение 4? Для простейшего потока параметр потока и его интенсивность совпадают. Среднее число запросов, поступающих на интервале длины Т, равно

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

Утверждение 6. Поток, полученный из простейшего потока интенсивности в результате применения простейшей процедуры рекуррентного просеивания: произвольный запрос потока с вероятностью включается в просеянный поток, а с вероятностью - игнорируется, является простейшим потоком интенсивности

Утверждение 7. Поток, полученный в результате суперпозиции независимых рекуррентных потоков, имеющих равномерно малую интенсивность, при увеличении числа сходится к простейшему потоку.

Наиболее хорошо изученными системами массового обслуживания являются системы, в которых входящий поток является простейшим. Во многом это объясняется Утверждением 2 и известным свойством отсутствия последействия у показательного распределения.

Это свойство для показательной случайной величины и в терминах условных вероятностей записывается следующим образом:

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

Из этого свойства вытекает, что распределение времени от произвольного момента до момента поступления следующего запроса из простейшего потока не зависит от того, когда поступил предыдущий запрос. Этот факт существенно упрощает анализ соответствующей СМО.

Утверждение 7 объясняет тот факт, что простейшие потоки часто имеют место в практических системах (так, поток запросов, поступающий в АТС, является суммой большого числа независимых малых потоков, поступающих от отдельных абонентов телефонной сети, и поэтому близок к простейшему) и поэтому использование простейшего потока для моделирования реального потока не только облегчает исследование СМО, но и оправдано.

Полезными сведениями о рекуррентных потоках являются следующие.

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

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

Функция совпадает с функцией тогда и только тогда, когда поток является простейшим.

Определение 9. Мгновенной интенсивностью рекурентного потока называется величина, определяемая как:

где - случайное событие, заключающееся в том, что в момент О поступил запрос и за время (0, t] запросов не поступило, а ) означает величину более высокого порядка малости (при ), чем .

Мгновенная интенсивность связана с функцией распределения следующим образом:

В случае простейшего потока мгновенная интенсивность потока совпадает с его интенсивностью.

В современных интегральных цифровых сетях связи (в отличие от традиционных телефонных сетей) потоки информации уже не представляют собой суперпозицию большого числа равномерно малых независимых рекуррентных потоков. В результате эти потоки часто являются не только не простейшими, но и не рекуррентными. Для описания таких потоков Д. Лукантони предложен [245] формализм групповых марковских потоков. Для обозначения их в символике Кендалла используется аббревиатура ВМАР (Batch Markovian Arrival Process). Более подробную информацию о ВМАР потоках и соответствующих системах обслуживания можно найти в [71], [245].

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

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

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

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

Для задания типа распределения времени обслуживания в символике Кендалла используются практически те же символы, что и при задании типа потоков. Так, символ G означает либо отсутствие каких-либо предположений о процессе обслуживания, либо он отождествляется с символом GI, означающим рекуррентный процесс обслуживания, символ М означает предположение, что распределение времени обслуживания - показательное, то есть, символ D означает детерминированные времена обслуживания и т.д.

Относительно недавно в обиход вошел символ SM (Semi-Markovian) см., например, [252], означающий более общий, чем рекуррентный, процесс обслуживания, при котором времена обслуживания последовательных запросов являются последовательными временами пребывания в своих состояниях некоторого полумарковского процесса с конечным пространством состояний и фиксированным ядром.