Разработка телетрафика и планирование сетей

Процессы поступления заявок

Разбить на страницы
Показывать лекцию целиком

Описание точечных процессов

Далее мы рассматриваем только простые точечные процессы, то есть, исключаем множественное прибытие, например, одновременное поступления двух вызовов. Для телефонных звонков это обеспечивается выбором достаточно малого интервала времени. Рассмотрим времена поступления вызова, где i -тый вызов поступает в момент времени $$Т_i$$:

$$0=T_0 < T_1 < T_2 < \dots < T_i < T_{i+1} < \dots.$$

Первое наблюдение происходит в момент времени $$Т_0 = 0$$.

Число вызовов в полуоткрытом интервале $$[0, t] $$ обозначим как $$N_t$$. Здесь $$N_t$$ - случайная переменная с непрерывными параметрами времени и дискретным пространством. С увеличением $$t N_t$$ никогда не уменьшаются.

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

$$X_i=T_i-T_{i-1}, i=1,2,\dots.$$

Это называется временем интервала, а распределение этого процесса называется распределением времени интервала.

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

  • Числовое представление $$N_t$$: при этом способе временной интервал $$t$$ сохраняется постоянным, и мы наблюдаем случайную переменную $$N_t$$ для числа вызовов в интервале $$t$$.

    (рис 5.1) Процесс поступления вызовов на входящих линиях транзитной станции.
  • Представление с помощью интервала $$Т_i$$: при этом способе число поступлений вызова сохраняется постоянным, а мы наблюдаем случайную переменную $$Т_i$$ для временного интервала до тех пор, пока не поступят $$п$$ заявок. Фундаментальные отношения между этими двумя представлениями отображаются следующим простым отношением:
  • $$T_n=\sum_{i=1}^n \begin{matrix} N_t < n, if\\ X_i \ge t, n=1,2, \dots \end{matrix} \lright \}$$

    Это может быть выражено формулой Феллера-Дженсена (Feller-Jensen's).

    $$p\{N_t < n\}=p\{ T_n \ge t\}, n=1,2,\dots$$

    Анализ точечного процесса может быть основан на обоих этих представлениях. В принципе они эквивалентны. Представление с помощью интервала соответствует обычному анализу временных рядов. Если мы, например, рассмотрим $$i = 1$$, то получим математическое ожидание вызова, иначе говоря, статистику, основанную на поступлении вызова.

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

    Статистика интересов при изучении точечных процессов может быть классифицирована согласно этим двум представлениям.

    Основные свойства числового представления

    Есть два свойства, которые представляют теоретический интерес.

  • Общее количество поступлений в интервале $$[t_1, t_2] $$ равно

    $$N_{t2}-N_{t1}.$$

    Среднее число вызовов в одном и том же самом интервале называется функцией обновления $$Н$$:

    $$H(t_1, t_2)=E\{N_{t2}-N_{t1}\}.H(t_1, t_2)=E\{N_{t2}-N_{t1}\}$$.
  • Плотность поступлений вызова за время $$t$$ (математическое ожидание времени):

    $$\lambda_t=lim_{\Delta t \to 0}\frac{N_{t+ \Delta t}-N_t}{\Delta t}=N_t'.$$

    Мы предполагаем, что $$\lambda_t$$ существует и конечна. Мы можем интерпретировать $$\lambda_t$$ как интенсивность, с которой происходит поступление заявок за время $$t$$ (сравните с материалом секции 3.1.2). Для простых точечных процессов мы имеем:

    $$p\{N_{t+\Delta t}-N_t \ge 2\}=o(\Delta t)$$, $$p\{N_{t+\Delta t}-N_t =1\}=\lambda_t \Delta t+o(\Delta t)$$, $$p\{N_{t+\Delta t}-N_t =0\}=1- \lambda_t \Delta t+o(\Delta t)$$

    где, по определению,

    $$lim_{\Delta t \to 0}\frac{o(\Delta t)}{\Delta t}=0$$
  • Индекс рассеяния для расчетов, (IDC - Index of Dispersion for Counts). Чтобы описывать свойства второго порядка числового представления, мы используем индекс рассеяния для расчетов - IDC. Он описывает отклонения процесса поступления вызовов в течение временного интервала $$t $$ и определяется как:

    $$IDC=\frac{Var\{N_t\}}{E\{N_t\}}.$$

    Разделив временной интервал $$t $$ на интервалы продолжительностью $$t=x $$, наблюдая число событий в течение этих интервалов, мы получаем оценку IDC (t). Для Пуассоновского процесса IDC равен единице. IDC равен "пиковости", свойство, которое мы введем позже, чтобы характеризовать число занятых каналов в процессе обслуживания нагрузки (7.7).

  • Основные свойства представления с помощью интервала

  • Распределение $$f(t) $$ временных интервалов $$Х_i(5.2) $$ (свертка самого распределения времен интервалов $$i- 1 $$ для времени до $$i $$ - ого поступления ).

    $$F_i(t)=p\{X_i \le t\}$$, $$E\{X_i\}=m_{1,i}$$

    Средняя величина - математическое ожидание вызова. Процесс возобновления - точечный процесс, где последовательные интервалы поступления стохастические независимы друг от друга и имеют то же самое распределение (исключая $$X_1 $$ ), то есть $$m_{1,i}=m_i $$ ( IID = Identically and Independently Distributed - Тождественно и Независимо Распределенный ).

  • Распределение $$V(t) $$ временного интервала от случайной точки до первого поступления заявки. Средняя величина $$V(t) $$ - математическое ожидание времени, которое рассчитывается на единицу времени.
  • Индекс рассеяния для интервалов, IDI. Чтобы описывать свойства второго порядка для представления с помощью временных интервалов, мы используем Указатель Дисперсия Интервалов, IDI. Он определяется как:

    $$IDI=\frac{Var\{X_i\}}{E\{X_i\}^2,}$$

    где $$X_i $$ - интервал поступления.

    Для Пуассоновского процесса, который имеет экспоненциально распределенное время обслуживания, IDIстановятся равными единице. IDI равен коэффициенту формы Пальмы - минус единица (3.10). Вообще, IDI получить из наблюдений более трудно, чем IDC. IDI более чувствителен к точности измерений и к процессу сглаживания нагрузки. Для наблюдения IDC более подходит цифровая технология, но она усложняет наблюдение IDI (Лекция 15).

  • Какое из рассмотренных двух представлений нужно использовать на практике, зависит от конкретного случая? Это можно проиллюстрировать следующими примерами.

    Пример 5.1.1: Методы измерения

    Измерение рабочих характеристик телетрафика проводятся одним из двух основных методов.

  • Пассивные измерения. Измерение оборудования делается путем записи числа поступления заявок в регулярные временные интервалы, начиная с последней записи. Это метод сканирования, который очень подходит для компьютеров. Он соответствует числовому представлению, где временной интервал постоянный (устанавливается в начале).
  • Активные измерения. При измерении оборудования записывается событие в тот момент, когда оно происходит. Мы запоминаем число событий, фиксируем и наблюдаем измеряемый интервал. Это соответствует представлению с помощью интервала, где мы получаем статистику каждого отдельного вызова.
  • Пример 5.1.2: Испытательные вызовы

    Исследование качества нагрузки на практике проводится двумя способами.

  • Качество нагрузки оценивается по результатам собранной статистики сделанных испытательных вызовов к заданному (испытательному) абоненту. Вызовы генерируются независимо от фактической нагрузки в течение часа наибольшей нагрузки. Испытательное оборудование записывает числа блокированных вызовов и т.д. Полученная статистика соответствует критерию качества работы - математическому ожиданию времени. К сожалению, этот метод увеличивает предложенную нагрузку на систему. Теоретически полученные рабочие характеристики измерений будут отличаться от истинных значений.
  • Испытательное оборудование собирает данные о числе вызовов $$N, 2N,3N, \dots$$, где, например, $$N= 1000 $$. Характер нагрузки не изменяется, и статистика рабочих характеристик - математическое ожидание вызова.
  • Пример 5.1.3: Статистика вызова

    Абонент оценивает качество работы станции по той части вызовов, которые не установлены, то есть по математическому ожиданию не прошедших вызовов. Оператор оценивает качество по соотношению времени, когда все направления заняты, то есть по математическому ожиданию времени. Часто путают эти два типа средних значений (время/вызов), составляя противоречивые инструкции.

    Пример 5.1.4: Вызываемый абонент занят (В-Занят)

    Когда на телефонной станции 10 % абонентов заняты, то 20 % попыток вызовов получают отказ из-за занятости В (вызываемый абонент занят). Это явление можно объяснить тем фактом, что половина абонентов является пассивной (то есть не делает никаких попыток вызова и не получает никаких вызовов), тогда как 20 % остающихся абонентов заняты. G. Lind (1976 [73]) анализировал проблему исходя из предположений, что на каждого абонента в среднем приходится одно и то же число входящих и исходящих вызовов. Если средняя величина и коэффициент формы распределения абонента - $$b $$ и $$\varepsilon $$, соответственно, то вероятность, что вызов - это попытка пройти к занятому абоненту $$b \cdot \varepsilon $$.

    Характеристики точечного процесса

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

    Стационарность (однородность по времени)

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

    Определение: Для произвольного $$t_2 > 0 $$ и каждого $$k \ge 0$$ вероятность поступления к заявок на отрезке $$[t_1, t_1 + t_2 [$$ не зависит от $$t_1 $$, то есть для всех $$t $$ и $$k $$ мы имеем:

    $$p\{N_{t_1+t_2}-N_{t1}=k\}=p\{N_{t_1+t_2+t}-N_{t_1+t}=k\}.$$

    Есть много других определений стационарности - некоторые из них более строгие, другие более слабые.

    Стационарность может также быть представлена с помощью интервала, если поставить требование, что все $$X_i $$ независимы и тождественно распределены ( IID ).

    Более слабое определение - это то, что все первые и вторые моменты второго (например, средняя величина и дисперсия) точечного процесса должны быть инвариантным относительно сдвига времени. Эрланг ввёл концепцию статистического равновесия, которое требует, чтобы производные процесса по времени были нулевыми.

    Независимость (отсутствие последействия)

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

    Определение: вероятность, что имеет место $$k $$ событий ( $$k $$ являются целым числом и $$\ge 0 $$ ), в промежутке $$[t_1, t_1 +t_2 [$$ не зависит от событий, которые были перед моментом $$t_1 $$

    $$p\{N_{t2}-N_{t1}=k|N_{t1}-N_{t0}=n\}=p\{N_{t2}-N_{t1}=k\}$$

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

    Пример5.2.1: Точки равновесия (точки регенерации)

    Примеры точечного процесса с точками равновесия.

  • Пуассоновский процесс - как мы увидим в следующей лекции, без памяти, и все точки оси времени - точки равновесия.
  • Процесс сканирования, где сканирование делается с регулярным циклом с ограниченной памятью. Последний момент сканирования имеет полную информацию о процессе сканирования, и поэтому все точки сканирования - точки равновесия.
  • Если мы предположим, что вышеупомянутый Пуассоновский процесс - сканирующий процесс (например, исследует процессы поступления вызовов в компьютерной системе), то единственные точки равновесия в этом составном процессе - моменты сканирования.
  • Рассмотрим систему организации очереди с Пуассоновским потоком вызовов, постоянным временем обслуживания и одним обслуживающим прибором. Число позиций при организации очереди может быть конечно или бесконечно. Пусть к моменту времени, когда начинается обслуживание, существует точечный процесс. Все временные интервалы, если система - простая, будут точками равновесия. В течение периодов, где система занята, моменты времени ввода новых запросов на обслуживание зависят от того, когда начато обслуживание первого вызова в этом периоде занятости.
  • Простой точечный процесс (ординарность)

    Мы уже упомянули (5.7), что исключаем процессы с поступлением в один момент нескольких вызовов.

    Определение: точечный процесс называется простым (ординарным), если вероятность, что в данной точке существует больше чем одно событие, является нулевым:

    $$p\{N_{t+\Delta t}-N_t \ge 2\}=o(\Delta t).$$

    В случае представления с помощью интервала распределение интервала поступления не должно иметь нулевой вероятности, то есть распределение в нулевой точке непрерывно (3.1):

    $$F(0+)=0$$

    Пример 5.2.2: Множественные события

    Моменты времени дорожных происшествий представляют простой процесс. Число поврежденных автомобилей или погибших людей - непростой точечный процесс с множественными событиями, когда заявки от многих объектов поступают одновременно.

    Формула Литла

    Это единственный общий результат, который справедлив для всех систем организации очереди. Он был сначала издан Литлом (1961 [75] ). Ниже мы приводим доказательство, применяя теорию стохастического процесса в (Eilon, 1969 [24]).

    Мы рассматриваем систему организации очереди, куда поступление заявок от клиентов соответствует стохастическому процессу. Клиенты входят в систему в случайный момент времени и ждут обслуживания. Когда они будут обслужены, они покинут систему. На рис.5.2 процессы и поступления и выхода из системы рассматриваются как стохастические процессы с накопленным числом клиентов (показанным на оси ординат).

    Рассмотрим пространство времени $$Т $$ и предположим, что система в начальное время $$t=0 $$ находится в статистическом равновесии. Мы используем следующую систему обозначений (рис.5.2):

    $$N(T)$$ - число поступления заявок в период $$Т $$ ;

    $$А(Т) $$ - полные времена обслуживания всех клиентов в период Т = затененная область между кривыми = величина обслуженной нагрузки;

    $$\lambda(T)=\frac{N(T)}{T}$$ - средняя интенсивность вызовов в период $$Т $$ ;

    $$W(T)=\frac{A(T)}{N(T)}$$ - среднее время обслуживания одного вызова в период $$Т $$ ;

    $$L(T)=\frac{A(T)}{T}$$ - среднее число вызовов в системе за период $$Т $$.

    Выпишем важное соотношение между этими переменными:

    $$L(T)=\frac{A(T)}{T}=\frac{W(T)*N(T)}{T}=\lambda(T)*W(T)$$

    Если существуют пределы $$\lambda = lim_{T \to \infty} \lambda (T)$$ и $$W=lim_{T \to \infty} W(T)$$, то также существует конечное значение $$L(T) $$, равное:

    $$L=\lambda *W \mbox{(формулa Литтла)}$$

    Эта простая формула справедлива для любых систем организации очереди. Доказательство было получено и улучшалось в течение нескольких лет. Мы будем использовать эту формулу в Лекциях 12 -14.

    (рис 5.2) Система организации очереди с поступлением в систему и выходом из системы клиентов. Вертикальное расстояние между двумя кривыми равно фактическому числу обслуживаемых клиентов. Строго говоря, клиенты не выходят из системы в том же порядке, как поступают в нее, так что горизонтальное расстояние между кривыми не описывает фактическое время пребывания клиента в системе.

    Пример5.3.1: Формулы Литла

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

    Если мы рассматриваем только обслуживающие приборы, формула показывает, что обслуженная нагрузка равна интенсивности поступления заявок, умноженной на среднее время обслуживания ( $$A=y*s=\frac{\lambda}{\mu}$$ )-

    Это соответствует определению предложенной нагрузки в секции. 2.1.

    Краткие итоги

  • Процессы поступления заявок, таких, как телефонные вызовы, прибывающие на станцию, отображаются математически как стохастические точечные процессы.
  • В лекции рассматриваются только простые точечные процессы, то есть мы исключаем множественное прибытие, например, одновременное поступления двух вызовов.
  • При анализе точечного процесса можно использовать два представления. Представление с помощью интервалов времени соответствует обычному анализу последовательности отсчетов времени; числовое представление не анализирует времени.
  • При числовом представлении временной интервал $$t $$ сохраняется постоянным, и мы наблюдаем случайную переменную $$N_t $$ для числа вызовов длительностью $$t $$.
  • При представлении с помощью интервалов времени число поступлений вызова сохраняется постоянным, а мы наблюдаем случайную переменную $$Т_i $$ для временного интервала до тех пор, пока не поступят $$п $$ заявок.
  • У числового представления есть два свойства, которые представляют теоретический интерес.

  • Общее количество поступления заявок в интервале $$[t_1, t_2] $$ равно $$(N_{t^2}-N_{t^1}) $$.
  • Плотность поступлений вызова за время $$t $$ (математическое ожидание времени):

    $$\lambda_t=N_t'$$
  • Чтобы описывать свойства второго порядка для числового представления, мы используем индекс рассеяния для подсчетов - IDC

    $$IDC=\frac{Var\{N_t\}}{E\{N_t\}}$$

    и индекс рассеяния для временных интервалов - IDI

    $$IDI=\frac{Var\{X_i\}}{E\{X_i\}^2}$$,
  • Стационарность характеризуется следующим свойством: для произвольного $$t_2 > 0 $$ и каждого $$k > 0 $$ вероятность поступления к заявок на отрезке $$[t_1; t_1 + t_2 ] $$ не зависит от $$t_1 ,$$ то есть для всего $$t $$ и $$k $$ мы имеем:

    $$p\{N_{t_1+t_2} - N_{t_1} = k\} = p\{N_{t_1+t_2+t} - N_{t_1+t}= k\}$$.
  • Независимость может быть выражена как требование, что будущая эволюция процесса зависит только от существующего состояния.
  • Точечный процесс называется простым, если вероятность, что в данной точке существует больше чем одно событие, является нулевым.
  • Для любых систем организации очереди среднее число вызовов в системе за период $$T $$ равно

    $$L = \lambda * W\mbox{ (формула Литтла)}$$.
  • Страницы:

    Описание точечных процессов

    Далее мы рассматриваем только простые точечные процессы, то есть, исключаем множественное прибытие, например, одновременное поступления двух вызовов. Для телефонных звонков это обеспечивается выбором достаточно малого интервала времени. Рассмотрим времена поступления вызова, где i -тый вызов поступает в момент времени $$Т_i$$:

    $$0=T_0 < T_1 < T_2 < \dots < T_i < T_{i+1} < \dots.$$

    Первое наблюдение происходит в момент времени $$Т_0 = 0$$.

    Число вызовов в полуоткрытом интервале $$[0, t] $$ обозначим как $$N_t$$. Здесь $$N_t$$ - случайная переменная с непрерывными параметрами времени и дискретным пространством. С увеличением $$t N_t$$ никогда не уменьшаются.

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

    $$X_i=T_i-T_{i-1}, i=1,2,\dots.$$

    Это называется временем интервала, а распределение этого процесса называется распределением времени интервала.

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

  • Числовое представление $$N_t$$: при этом способе временной интервал $$t$$ сохраняется постоянным, и мы наблюдаем случайную переменную $$N_t$$ для числа вызовов в интервале $$t$$.

    (рис 5.1) Процесс поступления вызовов на входящих линиях транзитной станции.
  • Представление с помощью интервала $$Т_i$$: при этом способе число поступлений вызова сохраняется постоянным, а мы наблюдаем случайную переменную $$Т_i$$ для временного интервала до тех пор, пока не поступят $$п$$ заявок. Фундаментальные отношения между этими двумя представлениями отображаются следующим простым отношением:
  • $$T_n=\sum_{i=1}^n \begin{matrix} N_t < n, if\\ X_i \ge t, n=1,2, \dots \end{matrix} \lright \}$$

    Это может быть выражено формулой Феллера-Дженсена (Feller-Jensen's).

    $$p\{N_t < n\}=p\{ T_n \ge t\}, n=1,2,\dots$$

    Анализ точечного процесса может быть основан на обоих этих представлениях. В принципе они эквивалентны. Представление с помощью интервала соответствует обычному анализу временных рядов. Если мы, например, рассмотрим $$i = 1$$, то получим математическое ожидание вызова, иначе говоря, статистику, основанную на поступлении вызова.

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

    Статистика интересов при изучении точечных процессов может быть классифицирована согласно этим двум представлениям.

    Основные свойства числового представления

    Есть два свойства, которые представляют теоретический интерес.

  • Общее количество поступлений в интервале $$[t_1, t_2] $$ равно

    $$N_{t2}-N_{t1}.$$

    Среднее число вызовов в одном и том же самом интервале называется функцией обновления $$Н$$:

    $$H(t_1, t_2)=E\{N_{t2}-N_{t1}\}.H(t_1, t_2)=E\{N_{t2}-N_{t1}\}$$.
  • Плотность поступлений вызова за время $$t$$ (математическое ожидание времени):

    $$\lambda_t=lim_{\Delta t \to 0}\frac{N_{t+ \Delta t}-N_t}{\Delta t}=N_t'.$$

    Мы предполагаем, что $$\lambda_t$$ существует и конечна. Мы можем интерпретировать $$\lambda_t$$ как интенсивность, с которой происходит поступление заявок за время $$t$$ (сравните с материалом секции 3.1.2). Для простых точечных процессов мы имеем:

    $$p\{N_{t+\Delta t}-N_t \ge 2\}=o(\Delta t)$$, $$p\{N_{t+\Delta t}-N_t =1\}=\lambda_t \Delta t+o(\Delta t)$$, $$p\{N_{t+\Delta t}-N_t =0\}=1- \lambda_t \Delta t+o(\Delta t)$$

    где, по определению,

    $$lim_{\Delta t \to 0}\frac{o(\Delta t)}{\Delta t}=0$$
  • Индекс рассеяния для расчетов, (IDC - Index of Dispersion for Counts). Чтобы описывать свойства второго порядка числового представления, мы используем индекс рассеяния для расчетов - IDC. Он описывает отклонения процесса поступления вызовов в течение временного интервала $$t $$ и определяется как:

    $$IDC=\frac{Var\{N_t\}}{E\{N_t\}}.$$

    Разделив временной интервал $$t $$ на интервалы продолжительностью $$t=x $$, наблюдая число событий в течение этих интервалов, мы получаем оценку IDC (t). Для Пуассоновского процесса IDC равен единице. IDC равен "пиковости", свойство, которое мы введем позже, чтобы характеризовать число занятых каналов в процессе обслуживания нагрузки (7.7).

  • Основные свойства представления с помощью интервала

  • Распределение $$f(t) $$ временных интервалов $$Х_i(5.2) $$ (свертка самого распределения времен интервалов $$i- 1 $$ для времени до $$i $$ - ого поступления ).

    $$F_i(t)=p\{X_i \le t\}$$, $$E\{X_i\}=m_{1,i}$$

    Средняя величина - математическое ожидание вызова. Процесс возобновления - точечный процесс, где последовательные интервалы поступления стохастические независимы друг от друга и имеют то же самое распределение (исключая $$X_1 $$ ), то есть $$m_{1,i}=m_i $$ ( IID = Identically and Independently Distributed - Тождественно и Независимо Распределенный ).

  • Распределение $$V(t) $$ временного интервала от случайной точки до первого поступления заявки. Средняя величина $$V(t) $$ - математическое ожидание времени, которое рассчитывается на единицу времени.
  • Индекс рассеяния для интервалов, IDI. Чтобы описывать свойства второго порядка для представления с помощью временных интервалов, мы используем Указатель Дисперсия Интервалов, IDI. Он определяется как:

    $$IDI=\frac{Var\{X_i\}}{E\{X_i\}^2,}$$

    где $$X_i $$ - интервал поступления.

    Для Пуассоновского процесса, который имеет экспоненциально распределенное время обслуживания, IDIстановятся равными единице. IDI равен коэффициенту формы Пальмы - минус единица (3.10). Вообще, IDI получить из наблюдений более трудно, чем IDC. IDI более чувствителен к точности измерений и к процессу сглаживания нагрузки. Для наблюдения IDC более подходит цифровая технология, но она усложняет наблюдение IDI (Лекция 15).

  • Какое из рассмотренных двух представлений нужно использовать на практике, зависит от конкретного случая? Это можно проиллюстрировать следующими примерами.

    Пример 5.1.1: Методы измерения

    Измерение рабочих характеристик телетрафика проводятся одним из двух основных методов.

  • Пассивные измерения. Измерение оборудования делается путем записи числа поступления заявок в регулярные временные интервалы, начиная с последней записи. Это метод сканирования, который очень подходит для компьютеров. Он соответствует числовому представлению, где временной интервал постоянный (устанавливается в начале).
  • Активные измерения. При измерении оборудования записывается событие в тот момент, когда оно происходит. Мы запоминаем число событий, фиксируем и наблюдаем измеряемый интервал. Это соответствует представлению с помощью интервала, где мы получаем статистику каждого отдельного вызова.
  • Пример 5.1.2: Испытательные вызовы

    Исследование качества нагрузки на практике проводится двумя способами.

  • Качество нагрузки оценивается по результатам собранной статистики сделанных испытательных вызовов к заданному (испытательному) абоненту. Вызовы генерируются независимо от фактической нагрузки в течение часа наибольшей нагрузки. Испытательное оборудование записывает числа блокированных вызовов и т.д. Полученная статистика соответствует критерию качества работы - математическому ожиданию времени. К сожалению, этот метод увеличивает предложенную нагрузку на систему. Теоретически полученные рабочие характеристики измерений будут отличаться от истинных значений.
  • Испытательное оборудование собирает данные о числе вызовов $$N, 2N,3N, \dots$$, где, например, $$N= 1000 $$. Характер нагрузки не изменяется, и статистика рабочих характеристик - математическое ожидание вызова.
  • Пример 5.1.3: Статистика вызова

    Абонент оценивает качество работы станции по той части вызовов, которые не установлены, то есть по математическому ожиданию не прошедших вызовов. Оператор оценивает качество по соотношению времени, когда все направления заняты, то есть по математическому ожиданию времени. Часто путают эти два типа средних значений (время/вызов), составляя противоречивые инструкции.

    Пример 5.1.4: Вызываемый абонент занят (В-Занят)

    Когда на телефонной станции 10 % абонентов заняты, то 20 % попыток вызовов получают отказ из-за занятости В (вызываемый абонент занят). Это явление можно объяснить тем фактом, что половина абонентов является пассивной (то есть не делает никаких попыток вызова и не получает никаких вызовов), тогда как 20 % остающихся абонентов заняты. G. Lind (1976 [73]) анализировал проблему исходя из предположений, что на каждого абонента в среднем приходится одно и то же число входящих и исходящих вызовов. Если средняя величина и коэффициент формы распределения абонента - $$b $$ и $$\varepsilon $$, соответственно, то вероятность, что вызов - это попытка пройти к занятому абоненту $$b \cdot \varepsilon $$.

    Характеристики точечного процесса

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

    Стационарность (однородность по времени)

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

    Определение: Для произвольного $$t_2 > 0 $$ и каждого $$k \ge 0$$ вероятность поступления к заявок на отрезке $$[t_1, t_1 + t_2 [$$ не зависит от $$t_1 $$, то есть для всех $$t $$ и $$k $$ мы имеем:

    $$p\{N_{t_1+t_2}-N_{t1}=k\}=p\{N_{t_1+t_2+t}-N_{t_1+t}=k\}.$$

    Есть много других определений стационарности - некоторые из них более строгие, другие более слабые.

    Стационарность может также быть представлена с помощью интервала, если поставить требование, что все $$X_i $$ независимы и тождественно распределены ( IID ).

    Более слабое определение - это то, что все первые и вторые моменты второго (например, средняя величина и дисперсия) точечного процесса должны быть инвариантным относительно сдвига времени. Эрланг ввёл концепцию статистического равновесия, которое требует, чтобы производные процесса по времени были нулевыми.

    Независимость (отсутствие последействия)

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

    Определение: вероятность, что имеет место $$k $$ событий ( $$k $$ являются целым числом и $$\ge 0 $$ ), в промежутке $$[t_1, t_1 +t_2 [$$ не зависит от событий, которые были перед моментом $$t_1 $$

    $$p\{N_{t2}-N_{t1}=k|N_{t1}-N_{t0}=n\}=p\{N_{t2}-N_{t1}=k\}$$

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

    Пример5.2.1: Точки равновесия (точки регенерации)

    Примеры точечного процесса с точками равновесия.

  • Пуассоновский процесс - как мы увидим в следующей лекции, без памяти, и все точки оси времени - точки равновесия.
  • Процесс сканирования, где сканирование делается с регулярным циклом с ограниченной памятью. Последний момент сканирования имеет полную информацию о процессе сканирования, и поэтому все точки сканирования - точки равновесия.
  • Если мы предположим, что вышеупомянутый Пуассоновский процесс - сканирующий процесс (например, исследует процессы поступления вызовов в компьютерной системе), то единственные точки равновесия в этом составном процессе - моменты сканирования.
  • Рассмотрим систему организации очереди с Пуассоновским потоком вызовов, постоянным временем обслуживания и одним обслуживающим прибором. Число позиций при организации очереди может быть конечно или бесконечно. Пусть к моменту времени, когда начинается обслуживание, существует точечный процесс. Все временные интервалы, если система - простая, будут точками равновесия. В течение периодов, где система занята, моменты времени ввода новых запросов на обслуживание зависят от того, когда начато обслуживание первого вызова в этом периоде занятости.
  • Простой точечный процесс (ординарность)

    Мы уже упомянули (5.7), что исключаем процессы с поступлением в один момент нескольких вызовов.

    Определение: точечный процесс называется простым (ординарным), если вероятность, что в данной точке существует больше чем одно событие, является нулевым:

    $$p\{N_{t+\Delta t}-N_t \ge 2\}=o(\Delta t).$$

    В случае представления с помощью интервала распределение интервала поступления не должно иметь нулевой вероятности, то есть распределение в нулевой точке непрерывно (3.1):

    $$F(0+)=0$$

    Пример 5.2.2: Множественные события

    Моменты времени дорожных происшествий представляют простой процесс. Число поврежденных автомобилей или погибших людей - непростой точечный процесс с множественными событиями, когда заявки от многих объектов поступают одновременно.

    Формула Литла

    Это единственный общий результат, который справедлив для всех систем организации очереди. Он был сначала издан Литлом (1961 [75] ). Ниже мы приводим доказательство, применяя теорию стохастического процесса в (Eilon, 1969 [24]).

    Мы рассматриваем систему организации очереди, куда поступление заявок от клиентов соответствует стохастическому процессу. Клиенты входят в систему в случайный момент времени и ждут обслуживания. Когда они будут обслужены, они покинут систему. На рис.5.2 процессы и поступления и выхода из системы рассматриваются как стохастические процессы с накопленным числом клиентов (показанным на оси ординат).

    Рассмотрим пространство времени $$Т $$ и предположим, что система в начальное время $$t=0 $$ находится в статистическом равновесии. Мы используем следующую систему обозначений (рис.5.2):

    $$N(T)$$ - число поступления заявок в период $$Т $$ ;

    $$А(Т) $$ - полные времена обслуживания всех клиентов в период Т = затененная область между кривыми = величина обслуженной нагрузки;

    $$\lambda(T)=\frac{N(T)}{T}$$ - средняя интенсивность вызовов в период $$Т $$ ;

    $$W(T)=\frac{A(T)}{N(T)}$$ - среднее время обслуживания одного вызова в период $$Т $$ ;

    $$L(T)=\frac{A(T)}{T}$$ - среднее число вызовов в системе за период $$Т $$.

    Выпишем важное соотношение между этими переменными:

    $$L(T)=\frac{A(T)}{T}=\frac{W(T)*N(T)}{T}=\lambda(T)*W(T)$$

    Если существуют пределы $$\lambda = lim_{T \to \infty} \lambda (T)$$ и $$W=lim_{T \to \infty} W(T)$$, то также существует конечное значение $$L(T) $$, равное:

    $$L=\lambda *W \mbox{(формулa Литтла)}$$

    Эта простая формула справедлива для любых систем организации очереди. Доказательство было получено и улучшалось в течение нескольких лет. Мы будем использовать эту формулу в Лекциях 12 -14.

    (рис 5.2) Система организации очереди с поступлением в систему и выходом из системы клиентов. Вертикальное расстояние между двумя кривыми равно фактическому числу обслуживаемых клиентов. Строго говоря, клиенты не выходят из системы в том же порядке, как поступают в нее, так что горизонтальное расстояние между кривыми не описывает фактическое время пребывания клиента в системе.

    Пример5.3.1: Формулы Литла

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

    Если мы рассматриваем только обслуживающие приборы, формула показывает, что обслуженная нагрузка равна интенсивности поступления заявок, умноженной на среднее время обслуживания ( $$A=y*s=\frac{\lambda}{\mu}$$ )-

    Это соответствует определению предложенной нагрузки в секции. 2.1.

    Краткие итоги

  • Процессы поступления заявок, таких, как телефонные вызовы, прибывающие на станцию, отображаются математически как стохастические точечные процессы.
  • В лекции рассматриваются только простые точечные процессы, то есть мы исключаем множественное прибытие, например, одновременное поступления двух вызовов.
  • При анализе точечного процесса можно использовать два представления. Представление с помощью интервалов времени соответствует обычному анализу последовательности отсчетов времени; числовое представление не анализирует времени.
  • При числовом представлении временной интервал $$t $$ сохраняется постоянным, и мы наблюдаем случайную переменную $$N_t $$ для числа вызовов длительностью $$t $$.
  • При представлении с помощью интервалов времени число поступлений вызова сохраняется постоянным, а мы наблюдаем случайную переменную $$Т_i $$ для временного интервала до тех пор, пока не поступят $$п $$ заявок.
  • У числового представления есть два свойства, которые представляют теоретический интерес.

  • Общее количество поступления заявок в интервале $$[t_1, t_2] $$ равно $$(N_{t^2}-N_{t^1}) $$.
  • Плотность поступлений вызова за время $$t $$ (математическое ожидание времени):

    $$\lambda_t=N_t'$$
  • Чтобы описывать свойства второго порядка для числового представления, мы используем индекс рассеяния для подсчетов - IDC

    $$IDC=\frac{Var\{N_t\}}{E\{N_t\}}$$

    и индекс рассеяния для временных интервалов - IDI

    $$IDI=\frac{Var\{X_i\}}{E\{X_i\}^2}$$,
  • Стационарность характеризуется следующим свойством: для произвольного $$t_2 > 0 $$ и каждого $$k > 0 $$ вероятность поступления к заявок на отрезке $$[t_1; t_1 + t_2 ] $$ не зависит от $$t_1 ,$$ то есть для всего $$t $$ и $$k $$ мы имеем:

    $$p\{N_{t_1+t_2} - N_{t_1} = k\} = p\{N_{t_1+t_2+t} - N_{t_1+t}= k\}$$.
  • Независимость может быть выражена как требование, что будущая эволюция процесса зависит только от существующего состояния.
  • Точечный процесс называется простым, если вероятность, что в данной точке существует больше чем одно событие, является нулевым.
  • Для любых систем организации очереди среднее число вызовов в системе за период $$T $$ равно

    $$L = \lambda * W\mbox{ (формула Литтла)}$$.
  • Вернуться к учебному плану