Hispanopedia Wiki
Articulo de referencia

Sistema de votación

Servidor de sondeo que da servicio 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 ...

Hispanopedia WikiContenido en espanolLectura gratuita
Servidor de sondeo que da servicio 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 donde un único servidor visita un conjunto de colas en algún orden. [ 1 ] El modelo tiene aplicaciones en redes informáticas y telecomunicaciones , [ 2 ] manufactura [ 3 ] [ 4 ] y gestión del tráfico rodado . El término sistema de sondeo se acuñó al menos ya en 1968 [ 5 ] [ 6 ] y el primer estudio de dicho sistema data de 1957, donde se modeló a un único técnico de reparación que daba servicio a máquinas en la industria algodonera británica. [ 7 ]

Normalmente se asume que el servidor visita las diferentes colas de forma cíclica. [ 1 ] Existen resultados exactos para los tiempos de espera, las longitudes marginales de las colas y las longitudes conjuntas de las colas [ 8 ] en los momentos 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, los nodos individuales pueden considerarse como colas fluidas (con un proceso de dos estados). [ 11 ]

Definición del modelo

Un grupo de n colas son atendidas por un único servidor, típicamente en un orden cíclico 1, 2, …, n , 1, …. Los nuevos trabajos llegan a la cola i según un proceso de Poisson de tasa λ i y se atienden según el principio de primero en llegar, primero en ser atendido, teniendo cada trabajo un tiempo de servicio denotado 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, en el que un nodo continúa recibiendo servicio hasta que el búfer esté vacío.
  • Servicio controlado, donde el nodo atiende todo el tráfico 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 del servidor.
  • servicio limitado, donde el servidor puede atender un número fijo máximo de trabajos en cada visita. [ 13 ]

Si un nodo de la cola está vacío, el servidor pasa inmediatamente a atender al siguiente nodo de la cola.

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

Utilización

Definimos ρ i  = λ i E( S i ) y escribimos ρ = ρ 1 + ρ 2 + … + ρ n . Entonces ρ es la fracción a largo plazo del tiempo que el servidor dedica a atender a los clientes. [ 14 ]          

Tiempo de espera

Tiempo de espera estimado

Para el servicio con acceso controlado, el tiempo de espera esperado en el nodo i es [ 12 ].

mi(Wi)=1+ρi2mi(do)+(1+ρi)Var(doi)2mi(do){\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

mi(Wi)=1−ρi2mi(do)+(1−ρi)Var(doi+1)2mi(do){\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 ]

mi(do)=∑i=1nortemi(di)1−ρ{\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 2 ecuaciones lineales y n 2 incógnitas, [ 16 ] sin embargo, es posible calcularla a partir de n ecuaciones. [ 17 ]

Tránsito pesado

El proceso de carga de trabajo puede aproximarse mediante un movimiento browniano reflejado en un sistema con mucha carga 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

Los sistemas de sondeo se han utilizado para modelar redes Token Ring . [ 20 ]

  • Bibliografía sobre modelos de encuestas (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, US (1987). "Lot Sizes, Lead Times and In-Process Inventories". 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". Operations Research . 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. pp. 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 desplazamiento y los tiempos de reparación son constantes". Journal of the 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 de múltiples tipos" . Queueing Systems . 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 fluidos" (PDF) . Queueing Systems . 63 ( 1–4 ): 401–435 . doi : 10.1007/s11134-009-9129-6 .
  12. 1 2 Everitt, D. (1986). "Aproximaciones simples para anillos de token". 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". Operations Research . 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 anillos de token". IEEE Journal on Selected Areas in Communications . 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 intenso" . The Annals of Applied Probability . 5 (3): 681. doi : 10.1214/aoap/1177004701 . JSTOR 2245120 . 
  19. ↑ Coffman, EG ; Puhalskii, AA; Reiman, MI (1998). "Sistemas de votación en tráfico intenso: un límite de proceso de Bessel". Matemáticas de la investigación operativa . 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 de anillo de token y su rendimiento". Actas del IEEE . 77 (2): 238– 256. doi : 10.1109/5.18625 .