Sistema de votación

Servidor de sondeo que atiende a n nodos de cola

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , un sistema de sondeo o modelo de sondeo es un sistema en el que un solo servidor visita un conjunto de colas en algún orden. ^[1] El modelo tiene aplicaciones en redes informáticas y telecomunicaciones , ^[2] fabricación ^{[3] [4]} y gestión del tráfico por carretera . El término sistema de sondeo se acuñó al menos en 1968 ^{[5] [6]} y el primer estudio de un sistema de este tipo en 1957, donde se modeló a un solo reparador que reparaba máquinas en la industria algodonera británica. ^[7]

Generalmente se supone que el servidor visita las diferentes colas de manera cíclica. ^[1] Existen resultados exactos para tiempos de espera, longitudes de cola marginales y longitudes de cola conjuntas ^[8] en épocas de sondeo en ciertos modelos. ^[9] Se pueden aplicar técnicas de análisis de valor medio para calcular cantidades promedio. ^[10]

En un límite fluido , donde llega una gran cantidad de trabajos pequeños, se puede considerar que los nodos individuales se comportan de manera similar a las colas fluidas (con un proceso de dos estados). ^[11]

Definición del modelo

Un grupo de n colas son atendidas por un único servidor, normalmente en un orden cíclico 1, 2, …, n , 1, …. Los nuevos trabajos llegan a la cola i según un proceso de Poisson con una tasa λ _i y son atendidos por orden de llegada, y cada trabajo tiene un tiempo de servicio indicado por una variable aleatoria independiente e idénticamente distribuida S _i .

El servidor elige cuándo avanzar al siguiente nodo según uno de los siguientes criterios: ^[12]

• servicio exhaustivo, donde un nodo continúa recibiendo servicio hasta que el búfer esté vacío.
• servicio cerrado, donde el nodo atiende todo el tráfico que estaba presente en el instante en que el servidor llegó y comenzó a prestar servicio, pero las llegadas posteriores durante este tiempo de servicio deben esperar hasta la siguiente visita al servidor.
• servicio limitado, donde se puede atender un número máximo fijo de trabajos en cada visita del servidor. ^[13]

Si un nodo de cola está vacío, el servidor se mueve inmediatamente para atender al siguiente nodo de cola.

El tiempo que tarda en cambiar del nodo de servicio i  − 1 al nodo i se denota por la variable aleatoria d _i .

Utilización

Defina ρ _i  =  λ _i  E( S _i ) y escriba ρ  =  ρ ₁  +  ρ ₂  + … +  ρ _n . Entonces ρ es la fracción de tiempo a largo plazo que el camarero pasa atendiendo a los clientes. ^[14]

Tiempo de espera

Tiempo de espera previsto

Para el servicio cerrado, el tiempo de espera esperado en el nodo i es ^[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)}}}$

y para un servicio exhaustivo

${\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)}}}$

donde C _i es una variable aleatoria que denota el tiempo entre entradas al nodo i y ^[15]

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

La varianza de C _i es más complicada y un cálculo directo requiere resolver n ² ecuaciones lineales y n ² incógnitas, ^[16] sin embargo es posible realizar el cálculo a partir de n ecuaciones. ^[17]

Tránsito pesado

El proceso de carga de trabajo se puede aproximar mediante un movimiento browniano reflejado en un sistema altamente cargado y adecuadamente escalado si el cambio de servidores es inmediato ^[18] y un proceso de Bessel cuando el cambio de servidores lleva tiempo. ^[19]

Aplicaciones

Se han utilizado sistemas de sondeo para modelar redes Token Ring . ^[20]

Enlaces externos

• Bibliografía sobre modelos de sondeo (artículos publicados entre 1984 y 1993) de Hideaki Takagi

Referencias

1. Boxma, DO ; Weststrate, JA (1989). "Tiempos de espera en sistemas de sondeo con enrutamiento de servidores Markovianos". Messung, Modellierung und Bewertung von Rechensystemen und Netzen . Informatik-Fachberichte. vol. 218. pág. 89. doi :10.1007/978-3-642-75079-3_8. ISBN 978-3-540-51713-9.
2. Carsten, R.; Newhall, E.; Posner, M. (1977). "Un análisis simplificado de los tiempos de escaneo en un bucle Newhall asimétrico con servicio exhaustivo". IEEE Transactions on Communications . 25 (9): 951. doi :10.1109/TCOM.1977.1093936.
3. Karmarkar, EE. UU. (1987). "Tamaños de lotes, tiempos de entrega e inventarios en proceso". Management Science . 33 (3): 409–418. doi :10.1287/mnsc.33.3.409. JSTOR  2631860.
4. Zipkin, PH (1986). "Modelos para el diseño y control de sistemas de producción por lotes estocásticos de múltiples artículos". Investigación de operaciones . 34 (1): 91–104. doi :10.1287/opre.34.1.91. JSTOR  170674.
5. Leibowitz, MA (1968). "Colas". Scientific American . 219 (2): 96–103. doi :10.1038/scientificamerican0868-96.
6. Takagi, H. (2000). "Análisis y aplicación de modelos de sondeo". Evaluación del desempeño: orígenes y direcciones . LNCS . Vol. 1769. págs. 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). "La eficiencia de N máquinas patrulladas unidireccionalmente por un operario cuando el tiempo de marcha y los tiempos de reparación son constantes". Revista de la Royal Statistical Society. Serie B (Metodológica) . 19 (1): 166–172. doi :10.1111/j.2517-6161.1957.tb00253.x. JSTOR  2984003.
8. Resing, JAC (1993). "Sistemas de sondeo y procesos de ramificación multitipo". Sistemas de colas . 13 (4): 409–426. doi :10.1007/BF01149263.
9. Borst, SC (1995). "Sistemas de sondeo con múltiples servidores acoplados" (PDF) . Queueing Systems . 20 (3–4): 369–393. doi :10.1007/BF01245325.
10. Wierman, A .; Winands, EMM; Boxma, DO (2007). «Programación en sistemas de votación» (PDF) . Evaluación de Desempeño . 64 (9–12): 1009. CiteSeerX 10.1.1.486.2326 . doi :10.1016/j.peva.2007.06.015. 
11. Czerniak, O.; Yechiali, U. (2009). "Sistemas de sondeo fluido" (PDF) . Queueing Systems . 63 (1–4): 401–435. doi :10.1007/s11134-009-9129-6.
12. Everitt, D. (1986). "Aproximaciones simples para Token Rings". IEEE Transactions on Communications . 34 (7): 719–721. doi :10.1109/TCOM.1986.1096599.
13. Takagi, H. (1988). "Análisis de colas de modelos de sondeo". ACM Computing Surveys . 20 : 5–28. doi :10.1145/62058.62059.
14. Gautam, Natarajan (2012). Análisis de colas: métodos y aplicaciones . CRC Press. ISBN 9781439806586.
15. Eisenberg, M. (1972). "Colas con servicio periódico y tiempo de cambio". Investigación de operaciones . 20 (2): 440–451. doi :10.1287/opre.20.2.440. JSTOR  169005.
16. Ferguson, M. (1986). "Cálculo de la varianza del tiempo de espera para Token Rings". Revista IEEE sobre áreas seleccionadas en comunicaciones . 4 (6): 775–782. doi :10.1109/JSAC.1986.1146407.
17. Sarkar, D.; Zangwill, WI (1989). "Tiempo de espera esperado para sistemas de colas cíclicas no simétricas: resultados exactos y aplicaciones". Management Science . 35 (12): 1463. doi :10.1287/mnsc.35.12.1463. JSTOR  2632232.
18. Coffman, EG ; Puhalskii, AA; Reiman, MI (1995). "Sistemas de sondeo con tiempos de conmutación cero: un principio de promediado de tráfico pesado". Anales de probabilidad aplicada . 5 (3): 681. doi : 10.1214/aoap/1177004701 . JSTOR  2245120.
19. Coffman, EG ; Puhalskii, AA; Reiman, MI (1998). "Sistemas de sondeo en tráfico pesado: un límite de proceso de Bessel". Matemáticas de la investigación de operaciones . 23 (2): 257–304. CiteSeerX 10.1.1.27.6730 . doi :10.1287/moor.23.2.257. JSTOR  3690512. 
20. Bux, W. (1989). "Redes de área local en anillo y su rendimiento". Actas del IEEE . 77 (2): 238–256. doi :10.1109/5.18625.