Система голосования

Опрашивающий сервер, обслуживающий 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. doi :10.1287/mnsc.33.3.409. JSTOR  2631860.
4. Зипкин, PH (1986). «Модели для проектирования и управления стохастическими системами серийного производства множества изделий». Исследование операций . 34 (1): 91–104. doi :10.1287/opre.34.1.91. JSTOR  170674.
5. Лейбовиц, MA (1968). «Очереди». Scientific American . 219 (2): 96–103. doi :10.1038/scientificamerican0868-96.
6. Такаги, Х. (2000). «Анализ и применение моделей опроса». Оценка производительности: истоки и направления . LNCS . Том 1769. стр. 423–442. doi :10.1007/3-540-46506-5_18. hdl :2241/530. ISBN 978-3-540-67193-0.
7. Mack, C.; Murphy, T.; Webb, NL (1957). «Эффективность N машин, патрулируемых в одном направлении одним оператором, когда время ходьбы и время ремонта являются константами». Журнал Королевского статистического общества. Серия B (Методическая) . 19 (1): 166–172. doi :10.1111/j.2517-6161.1957.tb00253.x. JSTOR  2984003.
8. Resing, JAC (1993). «Системы опроса и многотипные ветвящиеся процессы». Системы очередей . 13 (4): 409–426. doi :10.1007/BF01149263.
9. Борст, СК (1995). "Системы опроса с несколькими связанными серверами" (PDF) . Системы очередей . 20 (3–4): 369–393. doi :10.1007/BF01245325.
10. Вирман, А .; Винандс, ЕММ; Боксма, О.Дж. (2007). «Планирование в системах опроса» (PDF) . Оценка производительности . 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326 . дои :10.1016/j.peva.2007.06.015. 
11. Czerniak, O.; Yechiali, U. (2009). "Системы опроса жидкости" (PDF) . Системы очередей . 63 (1–4): 401–435. doi :10.1007/s11134-009-9129-6.
12. Everitt, D. (1986). «Простые аппроксимации для маркерных колец». IEEE Transactions on Communications . 34 (7): 719–721. doi :10.1109/TCOM.1986.1096599.
13. Такаги, Х. (1988). «Анализ очередей моделей опроса». ACM Computing Surveys . 20 : 5–28. doi :10.1145/62058.62059.
14. Гаутам, Натараджан (2012). Анализ очередей: методы и приложения . CRC Press. ISBN 9781439806586.
15. Эйзенберг, М. (1972). «Очереди с периодическим обслуживанием и временем переключения». Исследование операций . 20 (2): 440–451. doi :10.1287/opre.20.2.440. JSTOR  169005.
16. Фергюсон, М. (1986). «Вычисление дисперсии времени ожидания для маркерных колец». Журнал IEEE по избранным областям в коммуникациях . 4 (6): 775–782. doi :10.1109/JSAC.1986.1146407.
17. Саркар, Д.; Зангвилл, В.И. (1989). «Ожидаемое время ожидания для несимметричных циклических систем очередей — точные результаты и приложения». Management Science . 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 . doi :10.1287/moor.23.2.257. JSTOR  3690512. 
20. Bux, W. (1989). «Локальные сети Token-Ring и их производительность». Труды IEEE . 77 (2): 238–256. doi :10.1109/5.18625.