Система опроса

В теории массового обслуживания , дисциплине математической теории вероятностей , система опроса или модель опроса — это система, в которой один сервер посещает набор очередей в определенном порядке. ^[1] Модель имеет применение в компьютерных сетях и телекоммуникациях . ^[2] производство ^[3]^[4] и управление дорожным движением . Термин «система голосования» был придуман как минимум еще в 1968 году. ^[5]^[6] и самое раннее исследование такой системы было проведено в 1957 году, когда было смоделировано работу одного ремонтника, обслуживающего машины в британской хлопковой промышленности. ^[7]

Обычно предполагается, что сервер циклически посещает различные очереди. ^[1] Существуют точные результаты для времени ожидания, предельной длины очереди и длины совместной очереди. ^[8] в периоды опроса в определенных моделях. ^[9] анализа средних значений . Для расчета средних величин можно применять методы ^[10]

В гибком пределе , когда поступает очень большое количество небольших заданий, отдельные узлы ведут себя аналогично текучим очередям (с процессом с двумя состояниями). ^[11]

Определение модели

Группа из n очередей обслуживается одним сервером, обычно в циклическом порядке 1, 2, …, n , 1, …. Новые задания поступают в очередь i в соответствии с процессом Пуассона со скоростью λ _i и обслуживаются в порядке очереди, причем время обслуживания каждого задания обозначается независимыми и одинаково распределенными случайными величинами S _i .

Сервер выбирает, когда перейти к следующему узлу, в соответствии с одним из следующих критериев: ^[12]

исчерпывающее обслуживание, при котором узел продолжает получать обслуживание до тех пор, пока буфер не станет пустым.
закрытая служба, при которой узел обслуживает весь трафик, который присутствовал в момент прибытия сервера и начал его обслуживание, но последующие поступления в течение этого времени обслуживания должны ждать до следующего посещения сервера.
ограниченный сервис, при котором за каждое посещение сервера может обслуживаться максимально фиксированное количество заданий. ^[13]

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

Время, необходимое для переключения с обслуживающего узла i - 1 на узел i, обозначается случайной величиной d _i .

Использование

Определим ρ _i = λ _i E( S _i ) и напишем ρ = ρ ₁ + ρ ₂ + … + ρ _n . Тогда ρ — это долгосрочная доля времени, которую сервер тратит на обслуживание клиентов. ^[14]

Время ожидания

Ожидаемое время ожидания

Для закрытого сервиса ожидаемое время ожидания в узле i равно ^[12]

\mathbb {E} (W_{i})={\frac {1+\rho _{i}}{2}}\mathbb {E} (C)+{\frac {(1+\rho _{i}){\text{Var}}(C_{i})}{2\mathbb {E} (C)}}

и для исчерпывающего обслуживания

\mathbb {E} (W_{i})={\frac {1-\rho _{i}}{2}}\mathbb {E} (C)+{\frac {(1-\rho _{i}){\text{Var}}(C_{i+1})}{2\mathbb {E} (C)}}

где C _i — случайная величина, обозначающая время между входами в узел i и ^[15]

\mathbb {E} (C)=\sum _{i=1}^{n}{\frac {\mathbb {E} (d_{i})}{1-\rho }}

Дисперсия C _i более сложна, и для простого расчета требуется решить n ² линейные уравнения и n ² неизвестные, ^[16] однако можно вычислить из n уравнений. ^[17]

Плотное движение

Процесс рабочей нагрузки можно аппроксимировать отраженным броуновским движением в сильно нагруженной и соответствующим образом масштабируемой системе, если переключение серверов происходит немедленно. ^[18] и процесс Бесселя, когда переключение серверов требует времени. ^[19]

Приложения

Системы опроса использовались для моделирования сетей Token Ring . ^[20]

Внешние ссылки

Библиография по моделям опросов (статьи, опубликованные в 1984–1993 гг.) Хидеаки Такаги.

Ссылки

^ Перейти обратно: ^а ^б Боксма, Огайо ; Вестстрат, Дж. А. (1989). «Время ожидания в системах опроса с марковской маршрутизацией серверов» . Измерение, моделирование и оценка вычислительных систем и сетей . Технические отчеты по ИТ. Том 218. с. 89. дои : 10.1007/978-3-642-75079-3_8 . ISBN 978-3-540-51713-9 .
^ Карстен, Р.; Ньюхолл, Э.; Познер, М. (1977). «Упрощенный анализ времени сканирования в асимметричном контуре Ньюхолла с исчерпывающим обслуживанием». Транзакции IEEE в области коммуникаций . 25 (9): 951. doi : 10.1109/TCOM.1977.1093936 .
^ Кармаркар, США (1987). «Размеры партий, сроки выполнения заказов и незавершенные запасы». Наука управления . 33 (3): 409–418. дои : 10.1287/mnsc.33.3.409 . JSTOR 2631860 .
^ Зипкин, ПХ (1986). «Модели проектирования и управления стохастическими системами серийного производства нескольких изделий». Исследование операций . 34 (1): 91–104. дои : 10.1287/opre.34.1.91 . JSTOR 170674 .
^ Лейбовиц, Массачусетс (1968). «Очереди». Научный американец . 219 (2): 96–103. doi : 10.1038/scientificamerican0868-96 .
^ Такаги, Х. (2000). «Анализ и применение моделей опроса». Оценка эффективности: истоки и направления . ЛНКС . Том. 1769. стр. 423–442. дои : 10.1007/3-540-46506-5_18 . HDL : 2241/530 . ISBN 978-3-540-67193-0 .
^ Мак, К.; Мерфи, Т.; Уэбб, Нидерланды (1957). «Эффективность N машин, однонаправленно патрулируемых одним оперативником, когда время ходьбы и время ремонта постоянны». Журнал Королевского статистического общества. Серия Б (Методическая) . 19 (1): 166–172. дои : 10.1111/j.2517-6161.1957.tb00253.x . JSTOR 2984003 .
^ Резинг, JAC (1993). «Системы опроса и многотипные ветвящиеся процессы» . Системы массового обслуживания . 13 (4): 409–426. дои : 10.1007/BF01149263 .
^ Борст, Южная Каролина (1995). «Системы опроса с несколькими связанными серверами» (PDF) . Системы массового обслуживания . 20 (3–4): 369–393. дои : 10.1007/BF01245325 .
^ Вирман, А .; Винандс, ЕММ; Боксма, О.Дж. (2007). «Планирование в системах опроса» (PDF) . Оценка производительности . 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326 . дои : 10.1016/j.peva.2007.06.015 .
^ Черняк, О.; Йечиали, У. (2009). «Жидкие системы опроса» (PDF) . Системы массового обслуживания . 63 (1–4): 401–435. дои : 10.1007/s11134-009-9129-6 .
^ Перейти обратно: ^а ^б Эверитт, Д. (1986). «Простые приближения для Token Ring». Транзакции IEEE в области коммуникаций . 34 (7): 719–721. дои : 10.1109/TCOM.1986.1096599 .
^ Такаги, Х. (1988). «Анализ очередей моделей опроса». Обзоры вычислительной техники ACM . 20 :5–28. дои : 10.1145/62058.62059 .
^ Гаутам, Натараджан (2012). Анализ очередей: методы и приложения . ЦРК Пресс. ISBN 9781439806586 .
^ Айзенберг, М. (1972). «Очереди с периодическим обслуживанием и временем переналадки». Исследование операций . 20 (2): 440–451. дои : 10.1287/опре.20.2.440 . JSTOR 169005 .
^ Фергюсон, М. (1986). «Расчет дисперсии времени ожидания для Token Ring». Журнал IEEE по избранным областям коммуникаций . 4 (6): 775–782. дои : 10.1109/JSAC.1986.1146407 .
^ Саркар, Д.; Зангвилл, Висконсин (1989). «Ожидаемое время ожидания для несимметричных циклических систем массового обслуживания - точные результаты и приложения». Наука управления . 35 (12): 1463. doi : 10.1287/mnsc.35.12.1463 . JSTOR 2632232 .
^ Коффман, Э.Г .; Пухальский А.А.; Рейман, Мичиган (1995). «Системы опроса с нулевым временем переключения: принцип усреднения при интенсивном трафике» . Анналы прикладной теории вероятности . 5 (3): 681. doi : 10.1214/aoap/1177004701 . JSTOR 2245120 .
^ Коффман, Э.Г .; Пухальский А.А.; Рейман, Мичиган (1998). «Системы опроса в условиях интенсивного движения: предел бесселевского процесса». Математика исследования операций . 23 (2): 257–304. CiteSeerX 10.1.1.27.6730 . дои : 10.1287/moor.23.2.257 . JSTOR 3690512 .
^ Букс, В. (1989). «Локальные сети Token-Ring и их производительность». Труды IEEE . 77 (2): 238–256. дои : 10.1109/5.18625 .

[boxma-1] Перейти обратно: ^а ^б Боксма, Огайо ; Вестстрат, Дж. А. (1989). «Время ожидания в системах опроса с марковской маршрутизацией серверов» . Измерение, моделирование и оценка вычислительных систем и сетей . Технические отчеты по ИТ. Том 218. с. 89. дои : 10.1007/978-3-642-75079-3_8 . ISBN 978-3-540-51713-9 .

[2] Карстен, Р.; Ньюхолл, Э.; Познер, М. (1977). «Упрощенный анализ времени сканирования в асимметричном контуре Ньюхолла с исчерпывающим обслуживанием». Транзакции IEEE в области коммуникаций . 25 (9): 951. doi : 10.1109/TCOM.1977.1093936 .

[3] Кармаркар, США (1987). «Размеры партий, сроки выполнения заказов и незавершенные запасы». Наука управления . 33 (3): 409–418. дои : 10.1287/mnsc.33.3.409 . JSTOR 2631860 .

[4] Зипкин, ПХ (1986). «Модели проектирования и управления стохастическими системами серийного производства нескольких изделий». Исследование операций . 34 (1): 91–104. дои : 10.1287/opre.34.1.91 . JSTOR 170674 .

[5] Лейбовиц, Массачусетс (1968). «Очереди». Научный американец . 219 (2): 96–103. doi : 10.1038/scientificamerican0868-96 .

[6] Такаги, Х. (2000). «Анализ и применение моделей опроса». Оценка эффективности: истоки и направления . ЛНКС . Том. 1769. стр. 423–442. дои : 10.1007/3-540-46506-5_18 . HDL : 2241/530 . ISBN 978-3-540-67193-0 .

[7] Мак, К.; Мерфи, Т.; Уэбб, Нидерланды (1957). «Эффективность N машин, однонаправленно патрулируемых одним оперативником, когда время ходьбы и время ремонта постоянны». Журнал Королевского статистического общества. Серия Б (Методическая) . 19 (1): 166–172. дои : 10.1111/j.2517-6161.1957.tb00253.x . JSTOR 2984003 .

[8] Резинг, JAC (1993). «Системы опроса и многотипные ветвящиеся процессы» . Системы массового обслуживания . 13 (4): 409–426. дои : 10.1007/BF01149263 .

[9] Борст, Южная Каролина (1995). «Системы опроса с несколькими связанными серверами» (PDF) . Системы массового обслуживания . 20 (3–4): 369–393. дои : 10.1007/BF01245325 .

[10] Вирман, А .; Винандс, ЕММ; Боксма, О.Дж. (2007). «Планирование в системах опроса» (PDF) . Оценка производительности . 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326 . дои : 10.1016/j.peva.2007.06.015 .

[11] Черняк, О.; Йечиали, У. (2009). «Жидкие системы опроса» (PDF) . Системы массового обслуживания . 63 (1–4): 401–435. дои : 10.1007/s11134-009-9129-6 .

[everitt-12] Перейти обратно: ^а ^б Эверитт, Д. (1986). «Простые приближения для Token Ring». Транзакции IEEE в области коммуникаций . 34 (7): 719–721. дои : 10.1109/TCOM.1986.1096599 .

[takagi-13] Такаги, Х. (1988). «Анализ очередей моделей опроса». Обзоры вычислительной техники ACM . 20 :5–28. дои : 10.1145/62058.62059 .

[14] Гаутам, Натараджан (2012). Анализ очередей: методы и приложения . ЦРК Пресс. ISBN 9781439806586 .

[15] Айзенберг, М. (1972). «Очереди с периодическим обслуживанием и временем переналадки». Исследование операций . 20 (2): 440–451. дои : 10.1287/опре.20.2.440 . JSTOR 169005 .

[16] Фергюсон, М. (1986). «Расчет дисперсии времени ожидания для Token Ring». Журнал IEEE по избранным областям коммуникаций . 4 (6): 775–782. дои : 10.1109/JSAC.1986.1146407 .

[17] Саркар, Д.; Зангвилл, Висконсин (1989). «Ожидаемое время ожидания для несимметричных циклических систем массового обслуживания - точные результаты и приложения». Наука управления . 35 (12): 1463. doi : 10.1287/mnsc.35.12.1463 . JSTOR 2632232 .

[18] Коффман, Э.Г .; Пухальский А.А.; Рейман, Мичиган (1995). «Системы опроса с нулевым временем переключения: принцип усреднения при интенсивном трафике» . Анналы прикладной теории вероятности . 5 (3): 681. doi : 10.1214/aoap/1177004701 . JSTOR 2245120 .

[19] Коффман, Э.Г .; Пухальский А.А.; Рейман, Мичиган (1998). «Системы опроса в условиях интенсивного движения: предел бесселевского процесса». Математика исследования операций . 23 (2): 257–304. CiteSeerX 10.1.1.27.6730 . дои : 10.1287/moor.23.2.257 . JSTOR 3690512 .

[20] Букс, В. (1989). «Локальные сети Token-Ring и их производительность». Труды IEEE . 77 (2): 238–256. дои : 10.1109/5.18625 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

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