Bluemoon: Tutorial

Veamos qué ofrece Bluemoon con un ejemplo sencillo: la tandem queue.

Modelo del sistema

Una cola tandem consiste en dos buffers conectados secuencialmente. Paquetes llegan a cierta tasa λ al primer buffer q1, donde son almacenados temporalmente hasta que un servidor los atiende a tasa μ1. De allí pasan al segundo buffer, q2, donde se da el mismo proceso a una tasa de atención μ2, tras lo cual el paquete sale y se pierde de vista.

En un archivo de texto plano, digamos tandem.prism, podemos representar este sistema como una cadena de Markov de tiempo continuo en la sintaxis de PRISM de la siguiente forma:

 0  ctmc
 1 
 2  const int c;              // Queues capacity
 3  const double lambda = 3;  // rate(--> q1           )
 4  const double    mu1 = 2;  // rate(    q1 --> q2    )
 5  const double    mu2 = 6;  // rate(           q2 -->)
 6  
 7  module ContinuousTandemQueue
 8  
 9      q1: [0..c-1] init 0;
10      q2: [0..c-1] init 1;
11      arr:  [0..2] init 0;  // Arrival: (0:none) (1:lost) (2:successfull)
12      lost: [0..1] init 0;  // Package loss in q2: (0:none) (1:lost)
13      
14      // {- Package arrival at first queue -}
15      [] q1<c-1 -> lambda: (arr'=2) & (lost'=0) & (q1'=q1+1);
16      [] q1=c-1 -> lambda: (arr'=1) & (lost'=0);
17      
18      // {- Passing from first to second queue -}
19      [] q1>0 & q2<c-1 -> mu1: (arr'=0) & (lost'=0) & (q1'=q1-1) & (q2'=q2+1);
20      [] q1>0 & q2=c-1 -> mu1: (arr'=0) & (lost'=1) & (q1'=q1-1);
21      
22      // {- Package departure from second queue -}
23      [] q2>0 -> mu2: (arr'=0) & (lost'=0) & (q2'=q2-1);
24  
25  endmodule

Usando la herramienta: Análisis transitorio

Notemos que ambos buffers son finitos. Para simplificar el ejemplo ambos tienen la misma capacidad 'c', elegida por el usuario al momento de invocar la herramienta. Lo mismo podría haberse hecho con las tasas 'lambda', 'mu1' y 'mu2'.

Si observamos la línea 20, veremos que se puede descartar o perder un paquete. Esto ocurre cuando el primer servidor saca uno del primer buffer para llevarlo al segundo, pero el segundo buffer está al máximo de su capacidad. Como no se lo puede recibir, en nuestra implementación decidimos descartar dicho paquete, tomando nota de lo ocurrido en la variable booleana lost.

Ese será nuestro hecho de interés: la pérdida de un paquete en el segundo buffer. Para indicarle a Bluemoon cual es el evento raro añadimos una línea a tandem.prism, definiendo una etiqueta de PRISM con la palabra clave goal:

label "goal" = lost=1;

Supongamos que en particular nos interesa la probabilidad de perder un paquete antes de que se vacíe el segundo buffer, el cual siempre comienza conteniendo un paquete. Estamos pues estudiando la ocurrencia del evento raro en un intervalo específico de la vida del sistema: desde sus comienzos hasta que ocurre un evento que marca el fin. Este es un tipo de propiedad transitoria y puede ser analizada con Bluemoon. Todo lo que tenemos que hacer es indicarle a la herramienta cual es el evento "fin del mundo", a través de una nueva línea en tandem.prism con una etiqueta con la palabra clave stop:

label "stop" = q2=0;

¡Ya todo está listo para que estimemos la probabilidad del evento raro! Bluemoon utiliza intervalos de confianza para brindar garantías sobre la estimación que computa. El usuario elije el coeficiente de confianza y la precisión deseadas, y las indica a través de la línea de comandos, o como constantes de punto flotante en el archivo del modelo:

const double confidence = 0.90;
const double precision  = 5.0E-5;

La precisión puede ser un número concreto o un valor relativo al estimador. La segunda opción nos permite especificarla por ejemplo como un diez por ciento de la probabilidad de perder un paquete antes de que se vacíe el segundo buffer.

La invocación de la herramienta se realiza por línea de comandos de la misma manera que PRISM, especificando que deseamos usar el motor de simulación de eventos raros a través del switch -rarevent. Si queremos correr una simulación Monte Carlo estándar (i.e. sin la maravillosa división por importancia) sobre buffers con capacidad para cinco paquetes, la línea sería:

~$ prism-bm tandem.prism -const c=5 -rarevent fhit nosplit

El nombre del comando es "prism-bm" haciendo referencia a que es una versión de PRISM construida con el módulo bluemoon integrado. Notemos las dos palabras clave luego del switch. Con 'fhit' le indicamos a Bluemoon que estamos realizando un análisis transitorio, y mediante 'nosplit' apagamos el splitting, es decir que no se realizará división por importancia y se utilizarán sólo simulaciones Monte Carlo comunes y silvestres. El resultado debería ser algo como ésto:

PRISM
=====
 . . .

[DEV] Rare event simulation chosen.
[DEV] Simulation type: FIRST_HIT
[DEV] Simulation strategy: MONTECARLO

Confidence parameters
 - Looking inside modulesFile for confidence level
 - Looking inside modulesFile for precision
 - Confidence level: 90.0%
 - Precision to achieve: 5.0E-5

Special specifications
 - Techlog: rarevent_FIRST_HIT_MONTECARLO.log
 - CI build strategy: wilson
 - Splits: 1

Building model...
Model constants: c=5

Computing reachable states...

Reachability (BFS): 6 iterations in 0.00 seconds (average 0.000000, setup 0.00)

Time for model construction: 0.015 seconds.

Type:        CTMC
States:      19 (1 initial)
Transitions: 47

Rate matrix: 128 nodes (4 terminal), 47 minterms, vars: 7r/7c

Building sparse matrix for rarevent, from Prism (symbolically) built model.
Identifying special states... done.
Building importance function... done.
Setting up RESTART simulation environment....
Estimating rare event probability    {14}{15}{36} done:
 - Confidence interval: [ 4.711E-4 , 5.211E-4 ]
 - Precision: 5E-5
 - Point estimate: 4.961E-4

Processing times information
 - Total elapsed time: 0.86 s
 - Setup time: 0.04 s
    > Initial setup: 0.02 s
    > Rare/Reference states identification: 0.01 s
    > Importance function building: 0 s
 - Simulation time: 0.82 s

[DEV] Skipping other model checks.

Precisión relativa

Supongamos ahora que nos interesa estudiar buffers con capacidad para ocho paquetes. Entonces invocamos la herramienta como lo hicimos antes pero para la constante 'c=8', lo que podría darnos el siguiente resultado:

· · ·
Estimating rare event probability {7}{8} done:
 - Confidence interval: [ -1.891E-5 , 3.109E-5 ]
 - Precision: 5E-5
 - Point estimate: 6.089E-6

Notemos que el intervalo de confianza tiene un límite inferior negativo. Esto no huele muy bien que digamos, pues el mismo sugiere valores posibles para la probabilidad de observar el evento raro, y las probabilidades existen en el intervalo real [0,1]. El problema radica en que dicha probabilidad es más chica que la precisión que pedimos para el intervalo de confianza. La pregunta es entonces ¿cómo saber qué precisión pedir, sin saber de antemano cual es la probabilidad de mi evento raro?

Para estos casos existe la opción de precisión relativa. La misma debe ser pasada por línea de comandos con el switch -rareconf, se especifica como un porcentaje y se interpreta dinámicamente sobre las estimaciones que la herramienta va computando para el evento raro.

Digamos que queremos un intervalo muy preciso, que no se desvíe más de un diez por ciento del valor estimado a izquierda y otro tanto a derecha. La precisión relativa deseada es entonces de un 20%, y le indicamos esto a la herramienta con el siguiente comando:

~$ prism-bm tandem.prism -const c=8 -rarevent fhit nosplit \
   -rareconf .90 20%

El primer valor luego de -rareconf es el nivel de confianza deseado, que mantuvimos en un 90%, y el segundo es la precisión relativa. El resultado en este caso es:

· · ·
Estimating rare event probability {7}{24} done:
 - Confidence interval: [ 5.713E-6 , 6.983E-6 ]
 - Precision: 1.27E-6
 - Point estimate: 6.348E-6

Notemos que el veinte por ciento de 6.348 x 10-6 es 1.27 x 10-6, tal como lo pedimos, y en esta ocasión obtuvimos un intervalo de confianza sin valores negativos. Mucho mejor.

Terminación temprana

Bluemoon fue preparado para un fácil manejo en los casos de presupuesto computacional acotado. Ante una interrupción soft, por ejemplo cuando el usuario presiona Ctr+C, el programa se cierra ordenadamente y reporta los valores estimados hasta el momento. Para el caso anterior el resultado podría ser por ejemplo:

 · · ·
Estimating rare event probability {7}{8}^C

[rarevent.RareventSimulatorEngine] Interrupted, shutting down
 - Point estimate: 4.408E-6
 - 90% confidence: precision = 3.322E-6
                    interval = [ 2.747E-6 , 6.068E-6 ]
 - 95% confidence: precision = 3.99E-6
                    interval = [ 2.413E-6 , 6.402E-6 ]
 - 99% confidence: precision = 5.344E-6
                    interval = [ 1.735E-6 , 7.08E-6 ]

Como el cómputo fue interrumpido arbitrariamente por el usuario antes de su finalización, no se alcanzó el criterio de confianza exigido. En estos casos la herramienta reporta la probabilidad estimada hasta el momento de la interrupción. Además construye y reporta intervalos para tres de los niveles de confianza más populares en la estimación estadística: 90%, 95% y 99%.

Simulaciones con importance splitting

Muy bien, muy bonito, pero ahora querríamos usar aquello para lo cual Bluemoon fue construido: simulación eficiente con técnicas de división por importancia. Sólo que hay un pequeño problema, y es que dichas técnicas requieren la definición de una función de importancia diseñada específicamente para el sistema bajo estudio.

Por fortuna ¡eso no es ningún problema! Bluemoon realiza un análisis estático sobre el modelo alimentado, construyendo automáticamente esta función que de otra manera debería haber sido provista por el usuario. Para seleccionar este modo operativo invocamos a la herramienta con la opción 'auto' en reemplazo de 'nosplit':

~$ prism-bm tandem.prism -const c=5 -rarevent fhit auto

La primer diferencia que notaremos es que el preámbulo ahora nos saludará con la siguiente leyenda:

[DEV] Rare event simulation chosen.
[DEV] Simulation type: FIRST_HIT
[DEV] Simulation strategy: RESTART_AUTO

La otra diferencia la notaremos en los tiempos de simulación. Mientras más raro sea el evento estudiado, más veloz será la simulación con división por importancia en comparación con la Monte Carlo estándar. Las diferencias pueden ser realmente considerables.

Bluemoon también le permite al usuario escoger su propia función de importancia ad hoc, donde la única restricción es que debe tener imagen en los enteros. Para especificarla se puede usar la línea de comandos, o escribirla directamente sobre el archivo del modelo como una fórmula de PRISM llamada 'importance'. Por ejemplo si escribimos

formula importance = q2;

en tandem.prism, estamos especificando que la importancia del estado actual del sistema está dado por el número de paquetes que contiene el segundo buffer. La invocación por línea de comandos en este caso debería ser:

~$ prism-bm tandem.prism -const c=5 -rarevent fhit adhoc

Usando la herramienta: Análisis de estado estacionario

Hasta ahora hemos estudiado propiedades del tipo transitorio, pero Bluemoon también permite analizar propiedades de estado estacionario como por ejemplo la frecuencia de observación de eventos raros. Supongamos que nos interesa saber cual es la proporción de paquetes perdidos de entre todos aquellos que ingresan al sistema. En particular también consideraremos aquellos paquetes que intentaron entrar en el primer buffer, pero fueron descartados al encontrarse éste lleno.

Este nuevo tipo de evento, llamado "de referencia" en la literatura, marca el paso del tiempo para la simulación. Nos interesa la proporción de paquetes perdidos en función de todos los que ingresaron. Para indicarle a Bluemoon como identificar dichos eventos añadimos una nueva línea a tandem.prism con una etiqueta con la palabra clave reference:

label "reference" = arr!=0;

Muchas veces en cambio nos interesa saber la frecuencia absoluta de la anomalía, y no en función de otro evento específico del sistema. Para ello utilizamos la palabra clave '_TIME_' a la hora de definir el evento de referencia, aclarando que todo pasaje de tiempo es relevante para nuestro análisis:

label "reference" = _TIME_;

Finalmente invocamos la herramienta escribiendo 'freq' en el lugar donde antes habíamos escrito 'fhit', indicando así que las simulaciones harán corridas largas para computar la frecuencia buscada:

~$ prism-bm tandem.prism -const c=5 -rarevent freq adhoc

Esa línea de comando producirá el siguiente preámbulo:

[DEV] Rare event simulation chosen.
[DEV] Simulation type: FREQUENCY
[DEV] Simulation strategy: RESTART_AD_HOC

y podría terminar en un resultado similar al siguiente:

· · ·
Building sparse matrix for rarevent, from Prism (symbolically) built model.
Identifying special states... done.
Building importance function... (is Ad hoc: q2) done.
Setting up RESTART simulation environment... done.
Estimating rare event probability    {30} done:
 - Confidence interval: [ 6.001E-4 , 6.501E-4 ]
 - Precision: 5E-5
 - Point estimate: 6.251E-4

Processing times information
 - Total elapsed time: 5.07 s
 - Setup time: 0.05 s
    > Initial setup: 0.02 s
    > Rare/Reference states identification: 0.02 s
    > Importance function building: 0.01 s
 - Simulation time: 5.03 s
Powered by Drupal