Tema 02

Análisis de prestaciones e introducción al dimensionamiento en redes de conmutación de paquetes

Tema 02

Análisis de prestaciones e introducción al dimensionamiento en redes de conmutación de paquetes

Rafael Mª. Estepa AlonsoUniversidad de Sevilla

Índice del Tema 02Índice del Tema 022.1 Introducción a las Prestaciones en las redes de Ordenadores

2.1.1 Introducción a los indicadores de prestaciones y los SLA2.1.2 Modelo simple del retardo en una red de conmutación de paquetes2.1.3 Enfoques para la evaluación de prestaciones

2.2 Modelos de Colas2.2.1 Modelos de Colas2.2.2 Fórmula de Little

2.3 El proceso de Poisson2.3.1 Propiedades básicas2.3.2 Caracterización2.3.3 Adición y división de procesos de Poisson2.3.4 propiedad PASTA

2.4 Sistemas sin pérdida M/M/1: modelo básico de multiplexor

2

2.4 Sistemas sin pérdida M/M/1: modelo básico de multiplexor2.4.1 Procesos de nacimiento y muerte2.4.2 Prestaciones en un sistema M/M/1

2.5 Sistemas con pérdida M/M/1/L2.6 Introducción a las redes de colas: redes de Jackson2.7 Fuentes on-off e introducción al modelo de Fluidos

2.7.1 Modelo de una fuente on-off2.7.2 Introducción a la multiplexión de fuentes on-off2.7.3 Solución para colas de tamaño finito2.7.4 Solución para colas de tamaño infinito

2.8 Dimensionamiento 2.8.1 Dimensionamiento con el modelo de fluidos2.8.3 Dimensionamiento con el modelo del ancho equivalente de Guerin

Tema 02 – Clase 14: Fuentes on-offTema 02 – Clase 14: Fuentes on-off

Antonio J. Estepa Alonso

Universidad de Sevilla

Fuentes ON-OFFFuentes ON-OFF

� Muchas aplicaciones generan tráfico de manera intermitente� Ejemplos

� Transacciones cliente/servidor

� Voz

� El modelo ON-OFF es un artificio para emular el comportamiento de dichas aplicaciones (modelo)� Dos estados: ON (genera tráfico) , OFF (no genera tráfico)

� Tiempo de estancia en cada estado: exponencial

4

� Tiempo de estancia en cada estado: exponencial

� Alternancia entre ambos estados

� Fuente on-off: Caso simple de CTMC� Tasa nacimiento : λ

� Tasa muerte : µ

� Prob. Estancia en estado ON: ρ

0 off 1on

q0,1=λ

q1,0=µ

Fuentes ON-OFFFuentes ON-OFF

� Sea X(t) el estado de la fuente en el instante t

� La tasa instantánea generada es R(t)=RX(t) � Tasa media:

� Momento segundo orden

off on

λ

µ

R

5

EjemplosEjemplos

� Tenemos una aplicación de VoIP enviando tráfico a ráfagas. Observamos que la media de tráfico que envía a largo plazo es 3.635 bps y que en los periodos de ráfaga (en los que manda paquetes de 10 bytes cada 10 ms) se envía una media de 350 octetos. Calcule los parámetros necesarios para modelarlo como una fuente on-off

� Codec G.927a (con VAD), envía una trama de 10 octetos cada 10ms.Tras varias medidas se determina que los periodos de

6

10ms.Tras varias medidas se determina que los periodos de actividad y silencio siguen una distribución exponencial de media 420 ms y 350 ms respectivamente.� ¿cuál es la tasa de actividad vocal?� ¿cual es la tasa de pico de una fuente y la tasa media?� ¿que capacidad mínima necesito en un multiplexor estadístico para

multiplexar el tráfico proveniente de N fuentes como esta?

Ejemplos (II)Ejemplos (II)

� ¿Podría modelarse como una fuente on-off el comportamiento de A y C? (tamaño index.html = 1KB)� La petición se repite contínuamente

A

C36kbps

36 kbpsppp

GET index.html

200 OK

7

A 36 kbps

1 Mbsppp ppp

TCPTCP

TCP

TCP_SYN

TCP

TCPTCP

GET index.html TCP_ACK

TCP_SYN_ACK

HTTP: GET

HTTP: 200 OK

HTTP: GET

HTTP: 200 OK

Multiplexión de fuentes on-offMultiplexión de fuentes on-off

� Consideramos N fuentes on-off homogéneas que operan independientemente y cuyo tráfico se agrega en un multiplexor estadístico con un enlace de capacidad de salida C

off on

λ

µR

λ

Tamaño buffer

1

8

off on

λ

µR

off on

λ

µR

.

.

.

C

2

N

Mutiplexión de fuentes on-offMutiplexión de fuentes on-off

� La Dinámica del proceso es un proceso de nacimiento y muerte con N+1 estados� Número de fuentes que se encuentran en estado ON en un instante t

� En estado estable (t inf.)

… N0 1 2

9

� Tasa media a la que se generan datos

� Varianza

� Condición de estabilidad

Modelo de FluidosModelo de Fluidos

� Utilidad en el control de admisión o dimensionamiento� Es necesario obtener expresiones analíticas como solución del

problema anterior

� La condición de estabilidad nos da la capacidad mínima del enlace de salida� Ejm: N=4, λ=0.05, µ=0.2, R= 1Mbps … ¿Cmin?

10

Ejemplo de modelado de fuentes de tráficoEjemplo de modelado de fuentes de tráfico

� Vamos a modelar el traco agregado de M fuentes de vdeo con N fuentes on off. Para modelar el efecto de transicion entre escenas (cada escena va a una tasa diferente). Por supuesto (N >> M >> 1). Las medidas muestran que la media y la auto-covarianza para la tasa generada por m fuentes son respectivamente: E[R] = 3,9Mbps y CM(τ) = (3:015x1012)M e3’9τ . Aquí tambien suponemos que se envan 30 tramas por segundo y 0,25x106 pixels por trama. El ratio (N=M) es un parametro del sistema. El estudio muestra que el

11

(N=M) es un parametro del sistema. El estudio muestra que el modelo es sucientemente preciso cuando N=M = 20. El resto de parametros del modelo de uidos pueden ser encontrados sustituyendo en las ecuaciones anteriores

Soluciones al modelo de FluidosSoluciones al modelo de Fluidos

� Las soluciones ofrecen la probabilidad de desbordamiento del buffer del multiplexor para el tráfico agregado de N fuentes on-off homogéneas� Cada fuente genera una u.s. durante el periodo on.

� Dos soluciones en función del tamaño del buffer� AMS – Buffer de tamaño infinito

� Tucker – Buffer de tamaño finitoλ

12

off on

λ

µR

off on

λ

µR

off on

λ

µR

.

.

.

C

Tamaño buffer

1

2

N

Soluciones al modelo de FluidosSoluciones al modelo de Fluidos

� Las soluciones ofrecen la probabilidad de desbordamiento del buffer del multiplexor para el tráfico agregado de N fuentes on-off homogéneas� Cada fuente genera una u.s. durante el periodo on.

� Dos soluciones en función del tamaño del buffer� AMS – Buffer de tamaño infinito

� Tucker – Buffer de tamaño finitoλ

13

off on

λ

µR

off on

λ

µR

off on

λ

µR

.

.

.

C

Tamaño buffer

1

2

N

Modelo matemáticoModelo matemático

� En equilibrio (independientes del tiempo, con t�inf.), definimos� Fi(x) : probabilidad estacionaria de que i fuentes se encuentren en

estado activo y el contenido del buffer no exceda x.

… N0 1 2

14

� En forma matricial

Modelo AMSModelo AMS

� La Solución al conjunto de ecuaciones anterior trendrá la forma

� Condiciones de contorno necesarias para calcular ai

� La ocupación de la cola se incrementa cuando i > C/R

...

1 N-2 N-1 N

m 1

x

15

� La ocupación de la cola se incrementa cuando i > C/R

� Definimos la probabilidad de desbordamiento, G(x) � Probabilidad de que el contenido del buffer sea > x (aproximación de la

probabilidad de Pérdidas para un buffer de tamaño m)

c

Solución AMS, comportamiento asintóticoSolución AMS, comportamiento asintótico

� G(m) es una combinación lineal dominada por el mayor autvalor negativo (el mas cercano a 0, z0).

16

� Donde� Z0

� Zi (i distinto a 0)

– Donde

EjemploEjemplo

� Para los siguientes valores λ=2 , µ=3, N=5, R=4 y C=10� ¿Condición de estabilidad? C > 8

� Probabilidades en estado estable (F(inf.))� P0=0.0778, P1=0.2592, P2=0.3456,P3=0.2304,P4=0.0768,P5=0.01024

� Calculando la solución completa (Matlab)

17

� La solución a G(x) es:

asintótico

EjemploEjemplo

� Comportamiento asintótico frente a solución completa

Asintótico

Completa

18

Solución para búffer finitoSolución para búffer finito

� Definimos la probabilidad ui de que i fuentes estén activas y el buffer se encuentre completo a su tamaño máximo m

� Ahora tengo N+1 condiciones de contorno (puedo hallar la solucióncompleta)� Para i ≥ └ C/R ┘ � Fi(0) = 0

ui(m) = πi – F(m-)

19

� Para i ≥ └ C/R ┘ � Fi(0) = 0

� Para i < └ C/R ┘ � ui = 0 , entonces πi = Fi(m-)

� También es posible aplicar la aproximación asintótica� Donde z0 es igual que en el caso anterior

EjemploEjemplo

� Ejemplo de las diferentes aproximaciones para C=10R, N=20, codec G.729

20

EjercicioEjercicio

� Tenemos 4 fuentes on-off. Cada fuente esta en estado on una media de 5seg y en estado off una media de 20 seg. El fluido que genera una fuente en estado on es m=1 (donde m=0.5Mb)� ¿cuál es la capacidad mínima necesaria para el agregado?

� Si la capacidad del enlace de salida es C=0.1Mps, ..¿cuál es la probabilidad de pérdida para un buffer de tamaño m=2? (puede el modelo asintótico en caso de buffer finito)

21

modelo asintótico en caso de buffer finito)

Introducción a las Redes de OrdenadoresIntroducción a las Redes de Ordenadores

2.8 Dimensionamiento

2.8.1 Dimensionamiento con el modelo de fluidos

2.8.3 Dimensionamiento con el modelo del ancho equivalente de Guerin2.8.3 Dimensionamiento con el modelo del ancho equivalente de Guerin

Ancho de Banda Equivalente de GuerinAncho de Banda Equivalente de Guerin

� Método sencillo de dimensionamiento� Expresión directa de la capacidad

� Se basa en elegir el menor de dos métodos de dimensionamiento1. Aproximación ideal del comportamiento asintótico del modelo de

fluidos AMS

2. Aproximación Gausiana

23

1. Aproximación del Modelo de Fluidos1. Aproximación del Modelo de Fluidos

� Se invierte la aproximación asintótica del modelo AMS y se despeja la capacidad

24

� Ejemplo� Para N=100, λ=0.05, µ=0.2, m=1, R=0.1 y P.L.=0.01

� C = 5,5494 Mb/s

off on

λ

µR

Nm

PL

C

2. Aproximación Gaussiana2. Aproximación Gaussiana

� Para un número de fuentes tributarias suficientemente grande, podemos suponer que el ancho de banda instantáneo del agregado sigue una distribución normal centrada en E[R]=ρNR.� Distribución N(µ,δ)

. . .

MU

X

Pdf

b/s

t

t

t

t

ON

OFF

ON

OFFON

OFF

ON

Packet loss probability ),( 2

σµN

25

� Si suponemos que no existe buffer en el multiplexor, podemos aproximar la probabilidad de pérdidas como la probabilidad de que el ancho de banda agregado instantáneo sea > C� El problema se reduce a calcular un área dentro de la normal standard

� Calculo

� Donde

t

t

ON

OFFC

b/s

probability ),( 2σµN

Ejemplo de aproximación GausianaEjemplo de aproximación Gausiana

� Para el ejemplo anterior� µ = ρNR = 2 Mb/s

� δ = sum (var) = ρ ( 1- ρ)NR2 = 0.16

� Χ1-PL = 2.7152

� Entonces C = Χ1-0.99 δ + µ� C = 2,43 Mb/s

26

� Luego seleccionaría este valor C = 2,43Mbps

Para ampliarPara ampliar

� Lecturas recomendadas� Artículos

� R. Guerin, H. Ahmadi, and M. Naghshineh, (1991) Equivalent capacity and its application to bandwidth allocation in high-speed networks, IEEE J. Select. Areas Commun. 9 pag 968-981

� D. Anick, D. Mitra, and M. Shondi, (1982). Stochastic theory of a data-handling system with multiple sources, Bell System Technical Journal 61 pag 1871-1894

� Libros de la biliografía

27

� Libros de la biliografía� Hayes: sección 7.3 (ancho de banda equivalente de Guerin)

Cuestiones para revisar lo aprendidoCuestiones para revisar lo aprendido

� ¿cuál es la condición de estabilidad del modelo de fluidos?

� ¿qué ventajas tiene el modelo asintótico de AMS?

� Piense en casos de utilidad del modelo de dimensionamiento de Guerin

� ¿es el modelo de Guerin un modelo preciso?¿en qué casos puede ofrecer buenos resultados?

� ¿qué alternativas existen al modelo de Guerin?

28

� ¿qué alternativas existen al modelo de Guerin?

FIN DE LA CLASEFIN DE LA CLASE

Preguntas ?

29