Система опроса - 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я) и написать ρ = ρ1 + ρ2 + … + ρп. потом ρ - это длительная доля времени, которую сервер тратит на обслуживание клиентов.[14]

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

  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.