Система опроса - Polling system

Сервер опроса обслуживает п узлы очередей

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

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

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

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

Группа п очереди обслуживаются одним сервером, обычно в циклическом порядке 1, 2,…, п, 1,…. Новые вакансии поступают в очередь я согласно Пуассоновский процесс скорости λ_я и подаются на первым прибыл - первым обслужен Эквивалент в русском языке: поздний гость гложет и кость время обслуживания каждой работы обозначено независимые и одинаково распределенные случайные величины S_я.

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

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

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

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

Утилизация

Определить ρ_я = λ_я E (S_я) и написать ρ = ρ₁ + ρ₂ + … + ρ_п. потом ρ - это длительная доля времени, которую сервер тратит на обслуживание клиентов.^[14]

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

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

Для закрытой службы ожидаемое время ожидания на узле я является^[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_я случайная величина, обозначающая время между входами в узел я и^[15]

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

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

Интенсивное движение

Основная статья: Приближение интенсивного движения

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

Приложения

Системы голосования использовались для моделирования маркерное кольцо сети.^[20]

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

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

использованная литература

1. Боксма, О.; Вестстрат, Дж. А. (1989). «Время ожидания в системах опроса с марковской серверной маршрутизацией». Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte. 218. п. 89. Дои:10.1007/978-3-642-75079-3_8. ISBN  978-3-540-51713-9.
2. Carsten, R .; Newhall, E .; Познер, М. (1977). «Упрощенный анализ времени сканирования в асимметричной петле Ньюхолла с исчерпывающим обслуживанием». IEEE Transactions on Communications. 25 (9): 951. Дои: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). «Очереди». Scientific American. 219 (2): 96–103. Дои:10.1038 / scientificamerican0868-96.
6. Такаги, Х. (2000). «Анализ и применение моделей опроса». Оценка эффективности: истоки и направления. LNCS. 1769. С. 423–442. Дои:10.1007/3-540-46506-5_18. HDL:2241/530. ISBN  978-3-540-67193-0.
7. Mack, C .; Мерфи, Т .; Уэбб, Н. Л. (1957). «Эффективность N машин, патрулируемых в одном направлении одним оператором, когда время прогулки и время ремонта постоянны». Журнал Королевского статистического общества. Серия B (Методологическая). 19 (1): 166–172. Дои:10.1111 / j.2517-6161.1957.tb00253.x. JSTOR  2984003.
8. Ресинг, Дж. А. С. (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. Черняк, O .; Yechiali, U. (2009). «Системы опроса жидкости» (PDF). Системы массового обслуживания. 63 (1–4): 401–435. Дои:10.1007 / s11134-009-9129-6.
12. Эверитт, Д. (1986). «Простые приближения для токен-ринг». Транзакции IEEE по коммуникациям. 34 (7): 719–721. Дои:10.1109 / TCOM.1986.1096599.
13. Такаги, Х. (1988). «Анализ очередей моделей опроса». Опросы ACM Computing. 20: 5–28. Дои:10.1145/62058.62059.
14. Гаутам, Натараджан (2012). Анализ очередей: методы и приложения. CRC Press. ISBN  9781439806586.
15. Айзенберг, М. (1972). «Очереди с периодическим обслуживанием и временем переключения». Исследование операций. 20 (2): 440–451. Дои:10.1287 / opre.20.2.440. JSTOR  169005.
16. Фергюсон, М. (1986). «Вычисление дисперсии времени ожидания токен-колец». Журнал IEEE по избранным областям коммуникаций. 4 (6): 775–782. Дои:10.1109 / JSAC.1986.1146407.
17. Sarkar, D .; Зангвилл, В. И. (1989). «Ожидаемое время ожидания для несимметричных циклических систем массового обслуживания - точные результаты и приложения». Наука управления. 35 (12): 1463. Дои:10.1287 / mnsc.35.12.1463. JSTOR  2632232.
18. Коффман, Э.; Пухальский, А. А .; Рейман М. И. (1995). «Системы опроса с нулевым временем переключения: принцип усреднения интенсивного трафика». Анналы прикладной теории вероятностей. 5 (3): 681. Дои:10.1214 / aoap / 1177004701. JSTOR  2245120.
19. Коффман, Э.; Пухальский, А. А .; Рейман, М. И. (1998). «Системы опроса в условиях интенсивного движения: предел бесселевского процесса» (PDF). Математика исследования операций. 23 (2): 257. 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.