Теорема о прибытии

В теории массового обслуживания (дисциплине математической теории вероятностей) существует теорема прибытия. ^[1] (также называемое свойством случайного наблюдателя , ROP или свойством наблюдателя заданий) . ^[2]) утверждает, что «по прибытии на станцию задание наблюдает за системой так, как будто оно находится в устойчивом состоянии в произвольный момент времени для системы без этого задания». ^[3]

Теорема о прибытии всегда справедлива в открытых сетях в форме продукта с неограниченными очередями в каждом узле, но она также справедлива и в более общих сетях. Необходимое и достаточное условие выполнения теоремы прибытия в сетях в форме продукта дано в терминах вероятностей Палма в Boucherie & Dijk, 1997. ^[4] Аналогичный результат верен и в некоторых закрытых сетях. Примеры сетей в форме продукта, в которых теорема о прибытии не выполняется, включают обратимые сети Кингмана. ^[4]^[5] и сети с протоколом задержки. ^[3]

Митрани предполагает, что «состояние узла i , наблюдаемое входящим заданием, имеет распределение, отличное от состояния, наблюдаемого случайным наблюдателем. Например, входящее задание никогда не может видеть все ' k заданий, присутствующих в узле i , потому что оно само по себе не может быть среди уже существующих рабочих мест». ^[6]

Теорема о прибытиях, определяемых процессом Пуассона

Для пуассоновских процессов это свойство часто называют свойством PASTA (пуассоновские прибытия см. средние значения времени) и утверждают, что вероятность состояния, наблюдаемая внешним случайным наблюдателем, такая же, как вероятность состояния, наблюдаемого прибывающим клиентом. ^[7] Это свойство также справедливо для случая дважды стохастического процесса Пуассона , когда параметр скорости может меняться в зависимости от состояния. ^[8]

Теорема для сетей Джексона

В открытой сети Джексона с m очередями напишите ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ для состояния сети. Предполагать ${\textstyle \pi (\mathbf {n} )}$ — равновесная вероятность того, что сеть находится в состоянии ${\textstyle \mathbf {n} }$ . Тогда вероятность того, что сеть находится в состоянии ${\textstyle \mathbf {n} }$ непосредственно перед приходом в любой узел также ${\textstyle \pi (\mathbf {n} )}$ .

Заметим, что эта теорема не следует из теоремы Джексона , где рассматривается установившееся состояние в непрерывном времени. Здесь нас интересуют конкретные моменты времени, а именно время прибытия. ^[9] Эта теорема впервые опубликована Шевчиком и Митрани в 1981 году. ^[10]

Теорема для сетей Гордона – Ньюэлла.

В закрытой сети Гордона–Ньюэлла с m очередями напишите ${\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$ для состояния сети. Для клиента, находящегося в пути в штат $i$ , позволять ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ обозначают вероятность того, что непосредственно перед прибытием клиент «увидит» состояние системы, которое должно быть

\mathbf {n} -\mathbf {e} _{i}=(n_{1},n_{2},\ldots ,n_{i}-1,\ldots ,n_{m}).

Эта вероятность, ${\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}$ , совпадает с вероятностью установившегося состояния для состояния ${\mathbf {n} -\mathbf {e} _{i}}$ для сети того же типа с одним клиентом меньше . ^[11] Он был опубликован независимо Шевчиком и Митрани. ^[10] и Райзер и Лавенберг, ^[12] где результат был использован для разработки анализа средних значений .

Примечания

^ Асмуссен, Сорен (2003). «Сети массового обслуживания и нечувствительность». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 114–136. дои : 10.1007/0-387-21525-5_4 . ISBN 978-0-387-00211-8 .
^ Эль-Таха, Мухаммад (1999). Анализ путей выборки систем массового обслуживания . Спрингер. п. 94 . ISBN 0-7923-8210-2 .
^ Jump up to: ^а ^б Ван Дейк, Нью-Мексико (1993). «О теореме прибытия для сетей связи» . Компьютерные сети и системы ISDN . 25 (10): 1135–2013. дои : 10.1016/0169-7552(93)90073-D .
^ Jump up to: ^а ^б Бушери, Р.Дж.; Ван Дейк, Нью-Мексико (1997). «О теореме прибытия для сетей массового обслуживания продуктовой формы с блокировкой». Оценка производительности . 29 (3): 155. дои : 10.1016/S0166-5316(96)00045-4 .
^ Кингман, JFC (1969). «Марковские популяционные процессы». Журнал прикладной вероятности . 6 (1). Прикладное вероятностное доверие: 1–18. дои : 10.2307/3212273 . JSTOR 3212273 .
^ Митрани, Иси (1987). Моделирование компьютерных и коммуникационных систем . ЧАШКА. п. 114 . ISBN 0521314224 .
^ Вольф, RW (1982). «Прибытие по Пуассону показывает средние значения времени». Исследование операций . 30 (2): 223–231. дои : 10.1287/опре.30.2.223 .
^ Ван Доорн, Э.А.; Регтершот, GJK (1988). «Условная ПАСТА» (PDF) . Письма об исследованиях операций . 7 (5): 229. дои : 10.1016/0167-6377(88)90036-3 .
^ Харрисон, Питер Г .; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли. п. 228 . ISBN 0-201-54419-9 .
^ Jump up to: ^а ^б Шевчик, КЦ; Митрани, И. (1981). «Распределение состояний сети массового обслуживания в моменты ввода и вывода» . Журнал АКМ . 28 (2): 358. дои : 10.1145/322248.322257 .
^ Брейер, Л.; Баум, Дэйв (2005). «Марковские сети массового обслуживания». Введение в теорию массового обслуживания и методы матричного анализа . стр. 63–61 . дои : 10.1007/1-4020-3631-0_5 . ISBN 1-4020-3630-2 .
^ Райзер, М.; Лавенберг, СС (1980). «Анализ средних значений закрытых многоцепных сетей массового обслуживания» . Журнал АКМ . 27 (2): 313. дои : 10.1145/322186.322195 .

[1] Асмуссен, Сорен (2003). «Сети массового обслуживания и нечувствительность». Прикладная вероятность и очереди . Стохастическое моделирование и прикладная теория вероятности. Том. 51. С. 114–136. дои : 10.1007/0-387-21525-5_4 . ISBN 978-0-387-00211-8 .

[2] Эль-Таха, Мухаммад (1999). Анализ путей выборки систем массового обслуживания . Спрингер. п. 94 . ISBN 0-7923-8210-2 .

[dijk-3] Jump up to: ^а ^б Ван Дейк, Нью-Мексико (1993). «О теореме прибытия для сетей связи» . Компьютерные сети и системы ISDN . 25 (10): 1135–2013. дои : 10.1016/0169-7552(93)90073-D .

[boucherie-dijk-4] Jump up to: ^а ^б Бушери, Р.Дж.; Ван Дейк, Нью-Мексико (1997). «О теореме прибытия для сетей массового обслуживания продуктовой формы с блокировкой». Оценка производительности . 29 (3): 155. дои : 10.1016/S0166-5316(96)00045-4 .

[5] Кингман, JFC (1969). «Марковские популяционные процессы». Журнал прикладной вероятности . 6 (1). Прикладное вероятностное доверие: 1–18. дои : 10.2307/3212273 . JSTOR 3212273 .

[6] Митрани, Иси (1987). Моделирование компьютерных и коммуникационных систем . ЧАШКА. п. 114 . ISBN 0521314224 .

[7] Вольф, RW (1982). «Прибытие по Пуассону показывает средние значения времени». Исследование операций . 30 (2): 223–231. дои : 10.1287/опре.30.2.223 .

[8] Ван Доорн, Э.А.; Регтершот, GJK (1988). «Условная ПАСТА» (PDF) . Письма об исследованиях операций . 7 (5): 229. дои : 10.1016/0167-6377(88)90036-3 .

[9] Харрисон, Питер Г .; Патель, Нареш М. (1992). Моделирование производительности сетей связи и компьютерных архитектур . Аддисон-Уэсли. п. 228 . ISBN 0-201-54419-9 .

[sevcik-10] Jump up to: ^а ^б Шевчик, КЦ; Митрани, И. (1981). «Распределение состояний сети массового обслуживания в моменты ввода и вывода» . Журнал АКМ . 28 (2): 358. дои : 10.1145/322248.322257 .

[11] Брейер, Л.; Баум, Дэйв (2005). «Марковские сети массового обслуживания». Введение в теорию массового обслуживания и методы матричного анализа . стр. 63–61 . дои : 10.1007/1-4020-3631-0_5 . ISBN 1-4020-3630-2 .

[12] Райзер, М.; Лавенберг, СС (1980). «Анализ средних значений закрытых многоцепных сетей массового обслуживания» . Журнал АКМ . 27 (2): 313. дои : 10.1145/322186.322195 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Теория массового обслуживания
Одиночные узлы массового обслуживания	Д/М/1 хвост М/Д/1 хвост М/Д/Ц хвост Очередь М/М/1 Теорема Берка Очередь М/М/Ц Очередь М/М/∞ Очередь M/G/1 Формула Поллачека – Хинчина Матричный аналитический метод Очередь M/G/k Очередь G/M/1 Очередь G/G/1 Формула Кингмана Уравнение Линдли Разветвить очередь – присоединиться к ней Массовая очередь
Процессы прибытия	Точный процесс Пуассона Марковский процесс прибытия Рациональный процесс прибытия
Сети массового обслуживания	Сеть Джексона Уравнения дорожного движения Теорема Гордона – Ньюэлла Анализ среднего значения Алгоритм Бузена сеть Келли G-сеть Сеть BCMP
Политика обслуживания	ФИФО ЛИФО Совместное использование процессора Круговой Самая короткая работа следующая Кратчайшее оставшееся время
Ключевые понятия	Цепь Маркова с непрерывным временем Обозначения Кендалла Закон Литтла Решение в форме продукта Уравнение баланса Квазиобратимость Потоко-эквивалентный серверный метод Теорема о прибытии Метод разложения метод Бенеша
Предельные теоремы	Предел жидкости Теория среднего поля Приближение интенсивного движения Отраженное броуновское движение
Расширения	Жидкая очередь Многоуровневая сеть массового обслуживания Система опроса Состязательная сеть массового обслуживания Сеть потерь Очередь повторных попыток
Информационные системы	Буфер данных Эрланг (единица измерения) Распределение Эрланга Управление потоком (данные) Очередь сообщений Перегрузка сети Сетевой планировщик Конвейер (программное обеспечение) Качество обслуживания Планирование (вычисления) Телетрафик инжиниринг
Категория