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

Сервер опроса, обслуживающий n узлов очередей

В теории массового обслуживания , дисциплине математической теории вероятностей , система опроса или модель опроса — это система, в которой один сервер посещает набор очередей в определенном порядке. ^[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]

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

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

${\displaystyle \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]

${\displaystyle \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 гг.) Хидеаки Такаги.

Рекомендации

1. Боксма, О.Дж .; Вестстрат, Дж. А. (1989). «Время ожидания в системах опроса с марковской маршрутизацией серверов». Messung, Modellierung und Bewertung von Rechensystemen und Netzen . Информатик-Fachberichte. Том. 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. Зипкин, PH (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. doi :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.
12. Эверитт, Д. (1986). «Простые приближения для Token Ring». Транзакции IEEE в области коммуникаций . 34 (7): 719–721. дои : 10.1109/TCOM.1986.1096599.
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. doi : 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.