UNIVERSIDAD NACIONAL DE INGENIERIA

Centro de Tecnologías de Información

PROGRAMAS DE ALTA ESPECIALIZACION TECNOLÓGICA

Analisis de Redes usando

Procesos de Markov

Los sistemas de transmisión pueden ser muy frecuentemente modelados según un esquema como el de

la siguiente figura:

Este esquema aparece de forma natural al estudiar las redes de transmisión. Muestra una fuente de datos, una cola de espera o almacenamiento temporal a la espera de que las unidades que en ella se acumulen sean atendidas por un servidor.

De este modelo tenemos los siguientes

aspectos fundamentales

λ Tasa de llegada de informacion

u Tasa de servicio

Siendo las medias de las estadisticas de estos

flujos, pero no aportan sobre la forma como se

generan estos datos, rafaga, uniforme, etc.

• Un conjunto de servidores podria ser un

ejemplo que ilustre este modelo donde las

tasas λ y u corresponden a velocidad en

que se solicita el servicio, y la salida de la

informacion o del servicio que se entregue

ya procesado

• En un sistema como el de este ejemplo,

debe considerarse que todas las unidades

de datos tienen las mismas características

y requieren el mismo esfuerzo desde el

punto de vista de su generación y servicio.

En ciertos casos, ello puede implicar que

sean de tamaño fijo.

• Supóngase una tasa de llegadas de información

al sistema de = 5 paquetes/seg.

• Para u<λ, el sistema sirve las unidades en cola

a un ritmo inferior al que llegan a ella.

• Por lo tanto, no es capaz de servir las unidades

que se reciben a razón de 5 por segundo en

media, por lo cual el tamaño de la cola en cada

instante dependerá de la estadística de las

llegadas y en régimen permanente tenderá

hacia infinito.

• Para u>λ , el sistema es capaz de servir

más de 5 paquetes por segundo, por lo

cual la cola tendrá un tamaño finito. Ahora

bien, el tamaño en general no será nulo,

puesto que aunque las llegadas tengan

una media , podrían producirse en

ráfagas.

• El último caso a considerar es la situación

límite = . En este caso, el sistema se

encuentra al límite de estabilidad.

• En resumen,

• De este razonamiento aparentemente se deriva la necesidad de evitar sistemas cuyas colas de espera queden muy ocupadas, para lo cual emplear valores de u suficientemente mayores a λ. Aunque no es incorrecto, no siempre es oportuno considerar este criterio.

• Una condición muy empleada en el diseño de sistemas, en general razonable, es la previsión de una cierta congestión de modo que se puedan rentabilizar económicamente los recursos invertidos.

• Es evidente que el diseño de sistemas con

servidores exageradamente dimensionados

favorece la calidad de servicio entregada al

cliente, aunque perjudica la amortización de

equipos.

• Un dimensionado adecuado debe efectuarse

ajustando el diseño a niveles de congestión

moderados donde se garanticen unas cotas

mínimas de calidad (retardo y pérdidas de

paquetes).

• De estos conceptos, se define el

parámetro utilización o intensidad de

tráfico en el enlace como la relación entre

la tasa de llegadas y la de servicio. Esto

es,

• ρ=λ/u de donde

• Consideraciones para el analisis

a)Cómo es la estadística de las llegadas de unidades al sistema.

b) Cómo es la estadística del servicio de unidades de la cola.

c) Cuántos servidores trabajan en paralelo (es decir, cuantas unidades pertenecientes a la misma cola de espera pueden servirse simultáneamente)

d) Cuántos clientes generan unidades hacia la cola.

e) De que manera operan las colas, desde el punto de vista de almacenar unidades y entregarlas a los servidores para que sean atendidas.

Cadenas de Markov

• Considérese un sistema con diversos estados. Denominemos Ei al estado i. Por ejemplo, el estado Ei puede simbolizar el estado asociado a que i usuarios estén en un instante dado efectuando una llamada telefónica.

• Si hubiera n circuitos en total para cursar las llamadas, habría que definir desde un estado E0 hasta un estado En.

• En esta situación, se denota la

probabilidad de estar en el estado Em en

el instante ti como Pr[Em(t=ti)],

• que de forma abreviada puede escribirse

como Pm(ti).

• Se define el Vector de Estado del sistema

como:

• Se puede demostrar que:

• En el caso que la evolucion dependa

solamente del estado presente, se

denomina Cadena de Markov, o proceso

sin memoria:

• En(t=ti), se puede escribir que:

• Según las posibles transiciones entre los estados, queda definida la cadena de Markov, tal como se muestra a continuacion. Nótese que no es necesario que las flechas alcancen todos los posibles estados.

• Cada flecha va asociada a una probabilidad de transición entre estados que debe ser definida.

Sistemas de tiempo Continuo y

Sistemas de tiempo Discreto

• La clasificación de los sistemas según si consideran transiciones de estado en instantes de tiempo determinados o indefinidos conduce a definir los sistemas como de tiempo discreto o continuo respectivamente.

• Las señales de reloj de los sistemas digitales son un ejemplo de sistema discreto. La llegada del público a la entrada de un cine es un ejemplo de sistema continuo, puesto que se efectúan sin ningún instante de tiempo predeterminado.

Cadenas de Markov de tiempo

continuo

• En este caso, la notación que anteriormente habíamos expresado en general como Pr[Em(t=ti+1)] ahora se puede expresar simplemente como Pr[Em(t)], o más abreviadamente Pm(t).

• En este caso, que sea una cadena de Markov conduce a que la notación sea

• Pr[En(t) | Em(u), Ep(v), Eq(w),…] = Pr[En(t) | Em(u)], donde t>u>v>w>... (3.26)

• que abreviadamente expresaremos como

• Pr[En(t) | Em(u)] = Pmn(u,t)

• Estado

• Dado que la probabilidad de estar en el

estado n en el instante t puede

descomponerse según todos los

• caminos procedentes de cada uno de los

estados hasta n, podemos escribir que:

• Disponiendo todos los valores Pmn(u,t) en

forma matricial se define P(u,t).

• Con esta nueva notación, puede

expresarse que

Modelos de colas

• La forma más usual de denotar de forma abreviada el tipo de cola empleado es mediante la notación de Kendall, que sigue el siguiente formato:

A / B / X / Y / Z

• Estas variables caracterizan las colas de espera por los siguientes elementos:

• .

• Tipo o distribución de las llegadas de las unidades. Se denota mediante A. Hace referencia alparámetro . Ejemplo son las llegadas a tasa constante

• Tipo o estadística del servicio ofrecido. Se denota mediante B. Hace referencia al parámetro

• Número de servidores dispuestos en paralelo que atienden a la misma cola. Este valor corresponde a X de acuerdo a la notación anterior.

• Tamaño de la cola Y (o lo que es equivalente, número de unidades en el sistema. En este caso, el tamaño de la cola es el número de unidades en el sistema menos el número de servidores).

• En caso de omitirse este parámetro, se asume que el tamaño es infinito..

La cola M/M/1

Modelo de cola

• Considérese una tasa de llegadas y una tasa

de servicio . Cada estado representa el número

de unidades en la cola de espera.

• Dado que las llegadas se producen a tasa ,

independientemente del número de unidades en

el sistema ésa será la tasa de nacimientos, y así

se pone de manifiesto en la cadena

representada en la figura

Representacion de una cola M/M/I

• Probabilidades de estado

• considerando que λi= λ, y ui=u se tiene

que

• Para el cálculo de P0 se ha tenido en

cuenta que λ/u <1, es decir, que la tasa de

llegadas es menor a la tasa de servicio.

• Definiendo la utilizacion caracterizaremos el

sistema:

• Las cuales son las probabilidades del estado

Número medio de unidades en el

sistema

• Este valor puede obtenerse mediante

simple cálculo estadístico, teniendo en

cuenta que cada estado refleja el número

de unidades en el sistema. Esto es, en el

estado 0 hay cero unidades, en el estado

1 hay una unidad, etc.

•

Tiempo medio de permanencia de una

unidad en el sistema

• Para el cálculo del tiempo de

permanencia, basta con usar la expresión

de Little:

• Nótese que este resultado contiene tanto

el tiempo de espera en cola como el

tiempo de servicio:

• Por tanto, el tiempo medio de espera en la

cola será:

• Y aplicando el numero de unidades de

cola es: