Система типа G/G/1

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

C_n - n-е требование, поступающее в систему,

t_n- промежуток времени между поступлениями n-го и n-1 требований, плотность вероятности a(t) - не зависит от n.

x_n - время обслуживания n-го требования, плотность вероятности b(x) -также не зависит от n,

w_n - время ожидания n- го требования в очереди.

. Рассмотрим два случая поступления требования С_n в систему - поступление в занятую систему (Рис. 1) и в свободную систему (Рис. 2).

Рис. 1 Случай, когда требование C_n+1 поступает в занятую систему.

Рис. 2 Случай, когда требование C_n+1 поступает в свободную систему.

Нетрудно видеть, что для первого случая

.

Для второго случая .

Системы массового обслуживания с немарковским распределением времени обслуживания
Для входных потоков марковость будет сохранена. В качестве типичной СМО рассмотрим M/G/1. G-произволь. Распр.времени.Обозначим функцию распределения промежутков времени между последовательными поступлениями заявок на входе системы A (t).

По определению марковского процесса

.

Значение λ определяет интенсивность потока заявок, среднее значения промежутка времени между требованиями 1/λ, а дисперсия промежутка равна:

.

Марковская цепь описывается вероятностями перехода. Определим вероятности перехода за один шаг .

q_n – число требований, остающихся в системе в момент ухода требования C_n , а число требований, поступающих в систему за время обслуживания этого требования – v_n. C_n – n-ое требование, поступающее в систему; τ_n- время поступления n-го требования, а t_n=τ_n-τ_n-1 = x_n – время обслуживания n-го требования.

Матрица переходов будет иметь вид:

Рис. 1 Диаграмма вероятностей переходов для вложенной марковской цепи типаM/G/1.

Эта формула полностью представляет матрицу перехода.

Формула Полячека –Хинчина
Одной из наиболее важных характеристик СМО является значение средней длины очереди.

Для системы M/G/1 она дается формулой Полячека-Хинчина. Определим в пределе длину очереди как .

Анализируя два случая ухода требования С_n когда система остается непустой (Рис. 2) и случай ухода требования, когда система остается пустой (Рис.3),

Получаем два соотношения, связывающие случайные величины, определяющие число требований:

Для непустой .

Для пустой .

Рис. 2 Случай q_n >0.

Рис. 3 Случай q_n =0.

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

то можно объединить эти соотношения в одно:

.

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

Переходя к пределу при n→∞ , можно получить

.

и запишем сразу соотношение для числителя

.

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

Эта формула и получила название формулы Полячека –Хинчина

Обозначим T –среднее время пребывания требования в системе. По формуле Литтла:

Виды функции плотности вероятности системы типа G/G/1
Определение функции комплексной переменной W(s) из последнего уравнения согласно методам теории функций комплексной переменной сводится к представлению разности в квадратных скобках в виде отношения функций комплексной переменной, имеющих специальное расположение нулей в правой и левой полуплоскости комплексной переменной s:

.

При Re(s)>0 функция в числителе должна быть аналитической и не иметь нулей в этой полуплоскости. Функция в знаменателе должна быть аналитической в левой полуплоскости и не иметь там нулей. Решение для преобразования Лапласа функции плотности вероятности времени ожидания в очереди может быть записано в виде

Константа K есть вероятность того, что требование не будет стоять в очереди. Вычисления показывают, что, несмотря на то, что приведенный подход позволяет выразить функцию плотности вероятности времени ожидания в любом конкретном случае заданных плотностей a(t) и b(x), записать в общем случае решение для характеристик качества обслуживания системы G/G/1 не удается. Так для среднего времени ожидания требования в очереди удается получить формулу только в виде, содержащем некоторые неизвестные параметры

.

Здесь известные параметры s_a, s_b - среднеквадратичные отклонения для входного потока требований и времени обслуживания , - среднее значение интервала времени между входными требованиями. Последнее слагаемое есть отношение второго момента к среднему значению случайной величины I - продолжительности свободного состояния в системе G/G/1. Это слагаемое не определяется в явном виде и формула для M<W> не позволяет непосредственно вычислить среднюю задержку в системе.

Найдем приближенное значение этой величины при больших значениях нагрузки. Используем разложение функций комплексной переменной A(s) и B(s) в ряд Маклорена:

Поскольку нас интересует значение функции плотности вероятности при большой нагрузке, можно ограничиться рассмотрением функции W(s) при малых значениях s. Нетрудно видеть, что последнее выражение как функция комплексной переменной имеет два нуля. Первый из них очевиден: s₁=0. Для нахождения второго корня будем пренебрегать квадратом разности между средним временем обслуживания и среднем интервалом между поступлениями. Приближенное значение корня будет равно

.

Таким образом, в качестве приближения в окрестности нуля можно считать

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

Кроме полученной здесь формулы для больших значений r, во многих случаях более точные результаты могут быть найдены с использованием верхней и нижней границы для времени ожидания, без предположения о величине нагрузки. Строгое значение для верхней границы можно найти, используя полученную выше формулу для M<W>. Путем простых преобразований нетрудно показать, что для любых значений нагрузки будет выполняться неравенство

.

Можно видеть, что верхняя граничная оценка оказывается тем более точной, чем больше величина нагрузки. Другими исследователями (Marchall) была получена другая формула для верхней границы. При ее выводе автор исходил из требования превращения оценки в точное выражение для задержки в системе M/G/1 при подстановке в формулу соотношений, справедливых для пуассоновского входного потока.

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

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

В этом случае нижняя граница для среднего времени ожидания требования в очереди может быть определена следующей формулой

.

В более общем случае нахождение нижней границы дается через решение нелинейного уравнения:

Графически решение нелинейного уравнения y = g(y) дается точкой пересечения (см. Рис. 3) прямой Y = y и Y=g(y). Это решение и определяет собой величину точной нижней границы для среднего значения времени ожидания требования в очереди W_Low

.

Рис. 3 Определение нижней границы W_M.

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

Граф Ли трехзвенной коммутации

Рис. 1 Граф Ли для трехзвенной схемы коммутации

На рис. 1 представлен вероятност­ный граф, который отражает две группы каналов, которые должны со­единяться друг с другом. Блокировка может возникнуть, если k<2n-1 . Кроме того, будем считать, что в системе не используется концентрация, т.е. k>n и блокировка входных или выходных коммутаторов исключена.

вероятность занятия входного канала .

Тогда вероятность занятия ПЛ будет равна

.

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

.

Интеграция на основе стратегии подвижной границы
При этом методе интеграции N канальных интервалов делятся на две части. Одна часть, содержащая N₁ канальных интервалов, предназначается для обслуживания нагрузки первого класса (запросов на соединение). Другая часть, содержащая N₂=N-N₁ канальных интервалов, резервируется для пакетов – обслуживания нагрузки второго класса. . Однако при поступлении заявки первого класса она имеет абсолютный приоритет перед нагрузкой второго класса и сбрасывает при необходимости пакет, занимающий один из N₁ канальных интервалов. В этом и состоит смысл подвижной границы между группами каналов, отведенных для двух различных классов нагрузки. На рис. 1 приведена иллюстрация этого метода.

Рис. 1 Стратегия подвижной границы.

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

.

Здесь вероятность блокировки для нагрузки первого класса определяется по В - формуле Эрланга. .

Общий анализ системы с подвижной границей оказывается слишком сложным с алгебраической точки зрения. Поэтому при аналитическом исследовании применяются приближенные методы. Раздельно изучаются два возможных режима – не перегруженный (ρ₂<N₂) и режим перегрузки при нарушении этого неравенства.

Рис. 2 Диаграмма состояний системы с подвижной границей; N=2 канала; N₁=N₂=1 канал.

Рис.3 Сравнение систем с подвижной и фиксированной границей; N=2; N₁=N₂=1.

Оптимизация назначения приоритетов
Задача: когда с потоком заявок связывается некоторая неотрицательная функция, значение которой для каждой заявки может интерпретироваться как стоимость обслуживания. Рассмотрим систему M/G/1 с интенсивностью поступающего пуассоновского потока l требований в секунду и произвольной функцией плотности вероятности для времени обслуживания с заданным средним временем обслуживания. Пусть плата за требование Y является случайной величиной с произвольной функцией распределения .

Система функционирует следующим образом: новое требование, поступившее в систему «предлагает» неотрицательную плату Y «организатору очереди». После этого требованию предоставляется место в очереди такое, что все требования внесшие меньшую плату оказываются позади , большую впереди данного требования. В каждый момент времени сервер, завершив обслуживание очередного требования, принимает на обслуживание требование, оказавшееся впереди всей очереди. До полного завершения обслуживания требование не покидает сервер. Требования, внесшие одинаковую плату, обслуживаются в порядке поступления.

Найдем среднее время ожидания в очереди для требования, внесшего плату Y=y. Это время складывается из трех составляющих. Во-первых, это время на дообслуживание требования, находящегося в данный момент в сервере. Во-вторых – время обслуживания требований, которые поступили раньше и внесли большую или равную плату. Наконец меченому требованию придется ждать обслуживания всех требований поступивших позже его, но внесли большую плату. Среднее число требований, плата которых лежит в интервале (u,u+du) определяется по формуле Литтла : , где .

Используя обозначения для нижнего и верхнего предела функции b(u) можно записать суммарное выражение для времени ожидания в очереди для меченого требования в виде:

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

При абсолютно непрерывной функции плотности вероятности получим

.

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

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

Это известный результат для СМО типа M/G/1 при обслуживании в порядке поступления, как и следовало ожидать, поскольку равная плата равносильна ее отсутствию с точки зрения распределения приоритетов.

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

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

Пусть для всей совокупности клиентов можно определить функцию распределения вероятностей коэффициентов нетерпения

Сформулируем следующую задачу оптимизации: найти функцию y_a , которая минимизирует среднюю стоимость С при условии ограничения всей средней платы некоторой заданной величиной B.

Определим

Преобразуя минимизируемый интеграл, получим

Из закона сохранения в непрерывной форме

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

.

В то время как площадь под кривой, определяемой первым сомножителем должна оставаться постоянной.

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

Множество S такое, что .

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

.

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

получим, что, если считать средний коэффициент нетерпения равный A

Это и есть функция оптимальной платы.

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

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

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

Следовательно, средняя стоимость получается:

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

Теорема Джексона
Рассмотрим сеть (рис. 1), содержащую N узлов

Рис. 1 Сеть, содержащая N узлов.

Должно выполняться условие баланса

Вероятность, того, что заявка после обслуживания в i-том узле вообще покинет сеть будет равна .

Джексоном было доказано далеко не тривиальноe утверждение, что каждый узел в сети ведет себя так, как если бы он был независимой СМО типа M/M/m с входящим пуассоновским потоком λ_i . В общем случае полный входящий поток не является пуассоновским. Состояние сети с N узлами описывается вектором, компонентами которого являются число заявок в каждом из узлов сети .

Джексону удалось доказать, что стационарная вероятность этого состояния разлагается в произведение безусловных распределений:

.

Которые представляют собой стационарные вероятности для классической системы M/M/m. Этот удивительный результат называют теоремой Джексона.

Пусть в замкнутой сети с тремя (N=3) узлами циркулирует ровно два требования (K=2).

Состояние сети описывается тройками: .

Всего в сети возможно различных состояний .

На рис. 3 показана диаграмма интенсивностей переходов между этими состояниями.

Рис. 3 Диаграмма интенсивностей переходов для замкнутой сети с тремя узлами.

Рис. 2 Замкнутая сеть с тремя узлами.

Трехзвенная схема коммутации

Рис1 Трехзвенная схема коммутации.

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

.

Для трехзвенной схемы условие неблокируемости было получено Ч.Клосом:

k=2n-1.

Число точек коммутации для неблокирующей трехзвенной схемы будет равно

.

Очевидно, что это существенно меньше, чем NxN для однозвенной схемы. Например, при N=100 000 для однозвенной схемы число точек коммутации составило бы фантастическое число 10¹⁰. Для трехзвенной неблокирующей схемы оно составит около 1.7 10⁸. Еще большей экономии в сложности схемы можно достигнуть, применяя многозвенные схемы с блокировкой, но на очень низком уровне.

Характеристика качества обслуживания в сетях с коммутацией каналов и коммутацией пакетов
Пусть нагрузка на узел λ/μ =0.8 Эрл и в одном случае узел имеет один исходящий канал N=1, а в другом – пять (N=5). Вычислим С(1,0.8)=0.8 и С(5.0.8)=0.0018. Таким образом, применение пяти каналов вместо одного сокращает вероятность задержки более чем в 400 раз.

Найдем теперь среднее число сообщений, ожидающих обслуживание. Оно равно разности между средним числом сообщений в системе и средним числом сообщений, находящихся на обслуживании

.

В качестве подтверждения правильности сделанного вывода можно найти значение среднего числа ожидающих сообщений для N=1. Оно получится в точности таким, как было выведено ранее для СМО типа M/M/1.

.

Теперь найдем среднее число сообщений, находящихся в системе M<n> и число сообщений, находящихся в обслуживании M<s>. Вычисление показывает, что

Пользуясь формулой Литтла теперь можно найти задержку в узле M<T> и среднее время ожидания для сообщения М<W>: