Sabes ¿cómo simular un sistemas de colas? Analizaremos la asignacion de recursos en un sistema complejo, basándonos en las redes de Jackson.
Este estudio realiza un análisis sobre la simulación, comportamiento y resultado de un sistema complejo de colas, sus datos de entrada son números pseudoaleatorios, algoritmos en JS y su resolución se basa en las ecuaciones sobre las redes abiertas de Jackson.
El estudio de la teoría de colas inicia con el análisis de problemas de tráfico en sistemas telefónicos cuando, debido el crecimiento del servicio, las llamadas empiezan a tomar mucho más tiempo de espera (del esperado) para ser conmutadas a su destino.
Este estudio fue realizado por el ingeniero telefonista danés, A. K. Erlang. Formalizando la investigación como teoría de colas, la cual revisa la espera y los factores que intervienen.
Medio siglo después, Jackson analiza redes abiertas y cerradas y evidencia que las tasas de llegada que siguen la propiedad de Markov ** son independientes del estado de la red.
** Es equivalente a establecer una probabilidad condicional de cualquier "evento" futuro dados cualquier "evento" pasado y el estado actual Xi = i, es independiente del evento pasado y sólo depende del estado actual del proceso.
Bajo una demostración matemática Jackson concluyó que era posible analizar la red como un conjunto de sistemas de espera independientes de la tasa de llegada.
El estudio de Jackson ha cambiado la teoría de colas y su aporte ha trascendido a lo largo de los años. Desde entonces, la teoría de las redes de espera permite analizar sistemas complejos que reflejan mejor la estructura de los sistemas reales.
Simulación Redes de Jackson
TALK DE LA SEMANA
Redes de Jackson
Una red de Jackson es un sistema de m nodos, donde:
nodo (o instalaciones) serán (i=1,2,...,m)
Una cola de capacidad infinita
El Ingreso al sistema será de acuerdo a la entrada de Poisson, de parámetro a(i)
Un número de servidores, que tendrán la misma distribución exponencial μi, en los tiempos de servicio.
Un ingreso al nodo i puede salir del sistema o ir a otro nodo j (j=1,2,...,m y j≠i), con probabilidad Pij. Donde la probabilidad de salir del sistema es:
Las Redes de Jackson reciben el nombre de su descubridor, porque fue él quien encontró una propiedad vital: Bajo condiciones estables, cada nodo de una red, se comporta como un sistema de colas M/M/s independiente, con tasa de llegadas m:
Las redes de colas se clasifican en dos grupos:
Redes abiertas, cuando existen llegadas de entidades al sistema desde el exterior de la red y estas pueden salir del sistema.
Redes cerradas, donde no entran nuevas entidades, y las existentes no salen, es decir, los nodos forman un ciclo que nunca permite el flujo de entidades al exterior de la misma. El número de clientes será constante a lo largo del tiempo.
Se supone que la capacidad debe ser infinita, porque analizar redes de colas en un solo nodo cuando hay límites es más complejo:
Puede que haya un efecto de bloqueo
Si un ingreso termina en nodo i y quiere ir al nodo j que está al máximo de su capacidad, entonces debe esperar en i hasta que haya sitio y el sistema se bloquea.
Las llegadas al nodo i se rechazarían.
El ingreso rebosaría el nodo j, y deberá irse inmediatamente a otro nodo en su lugar.
Una última opción es que ese ingreso sea rechazado y deba abandonar el sistema.
Teniendo en cuenta el siguiente ejemplo a simular, podemos calcular las tasas de llegadas a los nodos por el teorema de Jackson:
Para esto implementamos Arena simulador, que recreará una simulación de eventos discretos para la optimización de procesos, es decir, este software simulará comportamientos de este sistema complejo (Se añade complejidad agregando recursos en las colas: VIP y general) con una serie de eventos definidos y ordenados en el tiempo.
Lo que haremos, es suponer el comportmiento del sistema diagramado anteriormente, y agregar algunas variables aleatorias de entrada y de decisión, permitiéndonos analizar rápidamente el comportamiento de un proceso o sistema que tomaría mucho más tiempo en un escenario real.
Acá te dejo más detalles sobre la construcción del proceso, cómo se planea construir el algoritmo en JavaScript y algunas suposiciones de la simulación generada:
Si existe algún error en el reproductor, puedes ver el video en el siguiente LINK.
Números aleatorios y pseudoaleatorios
ⓘ Los Números aleatorios son base esencial de la simulación.
Toda la aleatoriedad que se encuentra en el modelo se obtiene a partir de un generador de números aleatorios, que produce valores supuestamente de una secuencia de variables aleatorias independientes e idénticamente distribuidas. Posteriormente estos se transforman convenientemente para simular distribuciones de probabilidad que se requieran validar.
Un generador de números aleatorios es un algoritmo determinístico, el cual genera (valga la redundancia) valores reales distribuidos entre 1 y O, tal que O <= X < l:
La ocurrencia de cualquier valor es equiprobable o uniforme.
El valor de la muestra previa no afecta la probabilidad del valor de la próxima muestra (independencia).
Existen varios métodos, los más populares son los métodos congruenciales, que pueden ser: aditivos (+), multiplicativos (*) o mixtos (+ *). Por ejemplo en JavaScript, podemos generar números aleatorios utilizando Math.random(), produce un número aleatorio de punto flotante (decimal) entre 0 y 1 (incluido 0, pero no 1).
El generador de números pseudoaleatorios (PRNG) se refiere a la creación de un algoritmo basado en fórmulas matemáticas para producir secuencias de números que se aproximan a las propiedades de los números aleatorios.
No existe la aleatoriedad en la computación, es difícil lograr que una computadora haga algo por casualidad, los no serán números verdaderamente aleatorios, por lo que PRNG es la técnica para generar números aleatorios, deterministas y eficientes usando una computadora.
Un ejemplo de PRNG es el método de middle-square o cuadrado medio. En este método, se toma una semilla la cual es un número aleatorio y luego esta se eleva al cuadrado.
Un buen algoritmo NO depende de la semilla, pero sí su período deberá ser lo más largo posible, logrando que sean tomados casi todos los números del rango antes de repetirse. Cuanto más largo es el período, más aleatorio será el número.
Si tenemos una semilla de N dígitos y elevamos la semilla al cuadrado, el número resultante deberá ser de 2N dígitos, sino se agregarán ceros antes del número para que alcance sí o sí esta cantidad de 2N dígitos, luego sacarás la mitad y repetirás el proceso. Por jemplo:
19 --> (19^2 = 361) 0361 --> 36 +Cero así tiene doble de longitud
36 --> 1296 --> 29 Se toman los valores del medio y
29 --> 0841 --> 84 se repite el proceso...
84 --> 7056 --> 05
05 --> 0025 --> 02
02 --> 0004 --> 00
00 --> 0000 --> 00Esta línea de número: 36, 29, 84, 05, 02, 00 parecen ser selecciones aleatorias, pero en algún punto:
Volverán a repetirse
Si encontramos un 00, la cadena será de 0's
Si obtenemos un 50, los términos intermedios son 50 nuevamente: 50^2: 2500 y así se entra en un círculo de 50's.
Debido a estas desventajas, este método no se usa para generar números aleatorios. Para el algoritmo de nuetsro modelo, se implementaron los siguientes generadores de números:
Si existe algún error en el reproductor, puedes ver el video en el siguiente LINK.
Para nuestro esquema, los valores de decisión existen como 50% y 25% correspondientemente, y para que las entidades de estos nodos vayan al exterior según un proceso de Poisson las tasas serían dadas con la fórmula λ5= λ3 + λ4 por tiempo. Los trabajos que salen del nodo 1 pasan a procesarse en el nodo 2 con proba-bilidad p2=0.23. Además, para aquellos trabajos que no van hacia el nodo 2, la probabilidad de ramificación hacia el nodo 3 es p3=0.7
Te dejamos el resumen del diagrama dibujado por el algoritmo y algunas conclusiones:
Si existe algún error en el reproductor, puedes ver el video en el siguiente LINK.
Esta aplicación fue desarrollada y presentada para la clase de Simulación en la universidad, su contenido fue investigado en internet y las refencias son públicas. Encuéntralas al final del post.
Cifrado de Flujo
Los generadores de números pseudoaleatorios (PRNG) se utilizan en muchas aplicaciones de seguridad. Estamos hablando de un generador que se puede implementar en un gran número de funciones criptográficas para que los datos resultantes logren ser impredecibles.
El cifrado de flujo es un algoritmo de cifrado simétrico que genera la salida de texto cifrado bit a bit de texto plano (y sin formato) a la vez. Muchos algoritmos y protocolos de seguridad de red son basados en la criptografía con los números aleatorios binarios, el cifrado de este tipo más utilizado es RC4.
Un verdadero generador de números aleatorios TRNG, utiliza fuentes impredecibles para generar números aleatorios. Usualmente, la salida de un verdadero generador de números aleatorios debe estar sesgada, donde:
El número 1, que es mayor al número 0, o viceversa
Reducir o eliminar la desviación de una cadena de bits
Implementación de algoritmos de despolarización
Sí se pueden usar generadores de números pseudoaleatorios (PRNG), pero su algoritmo generará un flujo de bits ilimitado. es decir, la entrada de un cifrado de flujo simétrico.
Por otro lado tenemos las funciones pseudoaleatoria (PRF), con las cuales se podrá generar una cadena de bits pseudoaleatoria con longitud fija como las claves de cifrado simétricas y los valores variables en el tiempo, mientras que la entrada de PRF es semilla.
Excepto por el número de bits generados, no hay diferencia entre PRNG y PRF, puesto que ambas aplicaciones pueden utilizar el mismo algoritmo, ambas necesitan semillas, deben ser aleatorios e impredecibilidad. Además, es posible que las aplicaciones PRNG también necesiten utilizar entradas sensibles al contexto.
Cuando se usa PRNG o PRF en aplicaciones de criptografía, la idea es que no se conozca la semilla y por ende no se pueda determinar la cadena pseudoaleatoria.
Referencias
Martínez, C. (2009). Análisis de redes de colas modeladas con tiempos entre llegadas exponenciales e híper erlang para la asignación eficiente de los recursos. PONTIFICIA UNIVERSIDAD JAVERIANA. Disponible en internet: <https://repository.javeriana.edu.co/bitstream/handle/10554/7286/tesis285.pdf>
DOWNB, Bonalda D. Stability of mixed generalized Jackson networks. En: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Vol. 7 (1998); p. 24 – 56.
JACKSON, J. R. Networks of waiting lines. En: Operation Research. Vol. 5 (1957); p. 518–521.
GONGA, Qiguo y SHOUYANG, Laib. Supply chain networks: Closed Jackson network models and properties. En: Int. J. Production Economics, Vol. 113 (2008); p. 567–574.
JACKSON, J. R. Jobshop-like queueing systems. En: management science, Vol. 10 (1963); p. 131-142.
_________________________________________________________________________________________
¡Gracias por leer!
📍 Conéctate con nosotros en instagram👇
Comments