Volební systém - Polling system

Podávání dotazovacích serverů n uzly ve frontě

v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, a volební systém nebo volební model je systém, kde jeden server navštěvuje sadu front v určitém pořadí.[1] Model má aplikace v počítačových sítích a telekomunikace,[2] výrobní[3][4] a řízení silničního provozu. Termín volební systém byl vytvořen přinejmenším již v roce 1968[5][6] a první studie takového systému v roce 1957, kdy byl modelován jediný opravář opravárenských strojů v britském bavlnářském průmyslu.[7]

Obvykle se předpokládá, že server cyklicky navštěvuje různé fronty.[1] Přesné výsledky existují pro čekací doby, délky okrajových front a délky společných front[8] u volebních epoch v určitých modelech.[9] Analýza střední hodnoty k výpočtu průměrných množství lze použít techniky.[10]

V limit kapaliny, kde dorazí velmi velký počet malých úloh, lze jednotlivé uzly chovat podobně fronty tekutin (s dvoustavovým procesem).[11]

Definice modelu

Skupina n fronty obsluhuje jeden server, obvykle v cyklickém pořadí 1, 2,…, n, 1,…. Nové úlohy dorazí do fronty i podle a Poissonův proces sazby λi a jsou podávány na a kdo dřív přijde, ten dřív mele základ pro každou práci s dobou služby označenou nezávislé a identicky distribuované náhodné proměnné Si.

Server zvolí, kdy postupovat do dalšího uzlu podle jednoho z následujících kritérií:[12]

  • vyčerpávající služba, kde uzel nadále přijímá službu, dokud není vyrovnávací paměť prázdná.
  • gated service, kde uzel obsluhuje veškerý provoz, který byl přítomen v okamžiku, kdy server dorazil a začal sloužit, ale následná příjezdy během této doby služby musí počkat do další návštěvy serveru.
  • omezená služba, kde server může při každé návštěvě obsloužit maximální pevný počet úloh.[13]

Pokud je uzel fronty prázdný, server se okamžitě přesune, aby sloužil dalšímu uzlu fronty.

Čas potřebný k přepnutí z obsluhujícího uzlu i - 1 a uzel i je označena náhodnou proměnnou di.

Využití

Definovat ρi = λi E(Si) a piš ρ = ρ1 + ρ2 + … + ρn. Pak ρ je dlouhodobý zlomek času, který server věnuje zákazníkům.[14]

Čekací doba

Očekávaná doba čekání

U služby gated očekávaná čekací doba v uzlu i je[12]

a za vyčerpávající služby

kde Ci je náhodná proměnná označující čas mezi vstupy do uzlu i a[15]

Rozptyl Ci je složitější a přímý výpočet vyžaduje řešení n2 lineární rovnice a n2 neznámí,[16] je však možné počítat z n rovnice.[17]

Silný provoz

Hlavní článek: Přibližování hustého provozu

Proces pracovního vytížení lze aproximovat pomocí a odráží Brownův pohyb v silně načteném a vhodně upraveném systému, pokud je změna serveru okamžitá[18] a a Besselův proces když přepínání serverů nějakou dobu trvá.[19]

Aplikace

K modelování byly použity volební systémy tokenový prsten sítí.[20]

externí odkazy

Reference

  1. ^ A b Boxma, O. J.; Weststrate, J. A. (1989). „Čekací doby v hlasovacích systémech se směrováním serverů Markovian“. Messung, Modellierung und Bewertung von Rechensystemen und Netzen. Informatik-Fachberichte. 218. str. 89. doi:10.1007/978-3-642-75079-3_8. ISBN  978-3-540-51713-9.
  2. ^ Carsten, R .; Newhall, E .; Posner, M. (1977). "Zjednodušená analýza časů skenování v asymetrické Newhall Loop s vyčerpávající službou". Transakce IEEE na komunikaci. 25 (9): 951. doi:10.1109 / TCOM.1977.1093936.
  3. ^ Karmarkar, USA (1987). "Velikosti šarží, dodací lhůty a meziskladové zásoby". Věda o řízení. 33 (3): 409–418. doi:10,1287 / mnsc.33.3.409. JSTOR  2631860.
  4. ^ Zipkin, P. H. (1986). „Modely pro návrh a řízení stochastických systémů dávkové produkce s více položkami“. Operační výzkum. 34 (1): 91–104. doi:10.1287 / opre.34.1.91. JSTOR  170674.
  5. ^ Leibowitz, M. A. (1968). „Fronty“. Scientific American. 219 (2): 96–103. doi:10.1038 / scientificamerican0868-96.
  6. ^ Takagi, H. (2000). "Analýza a aplikace volebních modelů". Hodnocení výkonu: Počátky a směry. LNCS. 1769. str. 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, N.L. (1957). „Účinnost strojů N jednosměrně hlídaných jedním pracovníkem, když doba chůze a doba opravy jsou konstantní“. Journal of the Royal Statistical Society. Řada B (metodická). 19 (1): 166–172. doi:10.1111 / j.2517-6161.1957.tb00253.x. JSTOR  2984003.
  8. ^ Resing, J. A. C. (1993). "Pollingové systémy a procesy větvení více typů". Systémy řazení do fronty. 13 (4): 409–426. doi:10.1007 / BF01149263.
  9. ^ Borst, S. C. (1995). „Pollingové systémy s více spojenými servery“ (PDF). Systémy řazení do fronty. 20 (3–4): 369–393. doi:10.1007 / BF01245325.
  10. ^ Wierman, A.; Winands, E. M. M .; Boxma, O. J. (2007). „Plánování ve volebních systémech“ (PDF). Hodnocení výkonnosti. 64 (9–12): 1009. CiteSeerX  10.1.1.486.2326. doi:10.1016 / j.peva.2007.06.015.
  11. ^ Czerniak, O .; Yechiali, U. (2009). „Systémy dotazování tekutin“ (PDF). Systémy řazení do fronty. 63 (1–4): 401–435. doi:10.1007 / s11134-009-9129-6.
  12. ^ A b Everitt, D. (1986). Msgstr "Jednoduché aproximace pro prsteny tokenů". Transakce IEEE na komunikaci. 34 (7): 719–721. doi:10.1109 / TCOM.1986.1096599.
  13. ^ Takagi, H. (1988). Msgstr "Analýza front volebních modelů". ACM Computing Surveys. 20: 5–28. doi:10.1145/62058.62059.
  14. ^ Gautam, Natarajan (2012). Analýza front: Metody a aplikace. CRC Press. ISBN  9781439806586.
  15. ^ Eisenberg, M. (1972). "Fronty s periodickou službou a dobou přechodu na jiný server". Operační výzkum. 20 (2): 440–451. doi:10.1287 / opre.20.2.440. JSTOR  169005.
  16. ^ Ferguson, M. (1986). Msgstr "Výpočet odchylky čekací doby na tokenové prsteny". IEEE Journal on Selected Areas in Communications. 4 (6): 775–782. doi:10.1109 / JSAC.1986.1146407.
  17. ^ Sarkar, D .; Zangwill, W. I. (1989). „Očekávaná čekací doba pro nesymetrické systémy cyklického řazení do fronty - přesné výsledky a aplikace“. Věda o řízení. 35 (12): 1463. doi:10,1287 / mnsc.35.12.1463. JSTOR  2632232.
  18. ^ Coffman, E. G.; Puhalskii, A. A .; Reiman, M. I. (1995). „Volební systémy s nulovými časy přepnutí: zásada průměrování v hustém provozu“. Annals of Applied Probability. 5 (3): 681. doi:10.1214 / aoap / 1177004701. JSTOR  2245120.
  19. ^ Coffman, E. G.; Puhalskii, A. A .; Reiman, M. I. (1998). „Volební systémy v hustém provozu: Besselovy limity procesu“ (PDF). Matematika operačního výzkumu. 23 (2): 257. CiteSeerX  10.1.1.27.6730. doi:10,1287 / bř. 23.2.257. JSTOR  3690512.[trvalý mrtvý odkaz ]
  20. ^ Bux, W. (1989). "Token-ring lokální sítě a jejich výkon". Sborník IEEE. 77 (2): 238–256. doi:10.1109/5.18625.