PDF de programación - Herramienta: Simulación

SERVICIOS EN LA WEB Y DISTRIBUCIÓN DE CONTENIDOS
Área de Ingeniería Telemática

Herramienta: Simulación

Grupo de Redes, Sistemas y Servicios Telemáticos

http://www.tlm.unavarra.es

Programa de doctorado de

Tecnologías para la gestión distribuida de la información



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Contenido

• Introducción
• Ejemplos
• Simulación de eventos discretos
• Variables aleatorias

1

SERVICIOS EN LA WEB Y DISTRIBUCIÓN DE CONTENIDOS
Área de Ingeniería Telemática

Introducción

S ¿ Cómo evaluar un sistema ?

• Medirlo (experimentos)

– ¿Y si no existe?
– ¿Y si es muy caro o costoso hacer cambios en él?

I



O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

(para preguntas “what if”)

• Análisis matemático

– Solo para sistemas simples
– Sistemas reales son complejos

• Simulación

programa
• Emulación

programa

– Reconstruir el comportamiento del sistema en un

– Reproducir el comportamiento mediante un

3



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Simulación

•

Imitar el funcionamiento de un sistema
real con el tiempo

• Esto no es nuevo…
• Trataremos simulaciones informáticas

• Se necesita un modelo del sistema real
• Se genera una historia artificial de sucesos en el sistema y sus

repercusiones

• Se obtienen medidas (de prestaciones)
• Si el modelo es muy simple se puede

matemáticamente

resolver

• Modelos realistas son demasiado complejos para una solución

analítica

4

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I



I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S

I

I



Ejemplo

• Desplazar una escalera de la pared tirando de la

parte inferior

• ¿ Qué figura dibuja el centro de la escalera ?

5



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Ejemplo

• Clientes solicitan un servicio a través de una red

– Clientes: usuario y navegador web
– Servidor: servidor web
– Servicio: página web
– Red: Internet

• Analizar el rendimiento del servidor y de la red

6



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Ejemplo
• Mobile Ad-hoc NETwork (MANET)
• Dos nodos se pueden comunicar si están dentro del

alcance

• Los nodos pueden reenviar tráfico de otros
• Se mueven
• Modelar su movimiento
• Modelar el tráfico
• Resultados: prestaciones

7



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Cuándo no es apropiada

• Si el sentido común nos da la respuesta
• Si el problema se puede resolver analíticamente
• Si es más sencillo realizar experimentos
• Si el coste (€) del estudio de simulación es mayor
que el ahorro posible con el conocimiento que se
obtiene

• Si el sistema es demasiado complejo
• Si creemos que es

la respuesta a cualquier

problema.

8

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I



I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Simuation & Emulation

• La emulación obtiene eventos del sistema real
• Devuelve eventos tras una simulación de lo que les ha sucedido
• Esos eventos de salida deben producirse en el instante real que

les corresponda

Real

Computer
simulation

9



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Componentes

– Grupo de objetos con una interacción o interdependencia

orientada hacia un propósito

• Sistema (system)

• Componentes

– Entidad (entity)

• Un objeto de interés en el sistema

– Atributo (attribute)

• Propiedad de una entidad

– Actividad (activity)

• Un periodo de tiempo de una longitud especificada

• Ejemplo: Sucursal de un banco
– Los clientes podrían ser entidades
– Su saldo en cuenta sería un atributo
– Hacer depósitos una actividad

10



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Estado del sistema

• Grupo de variables necesarias para describir el sistema en un

momento cualquiera, en relación con los objetivos del estudio

• Ejemplo: banco

– Número de cajeros ocupados
– Número de clientes esperando en cola
– Instante en que llegará el siguiente cliente

• Evento: suceso instantáneo que puede cambiar el estado del

sistema (endógenos u exógenos)

• Ejemplo:

– Llegada de un nuevo cliente (exógeno)
– Cliente termina de ser atendido (endógeno)

11

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Tipos de sistemas

• Discretos o continuos

• Sistema discreto

– Las variables de estado cambian
solo en un conjunto discreto de
puntos en el tiempo

– Ejemplo: banco con llegadas y

salidas

• Sistema continuo

– Las variables de estado cambian

de forma continua con el tiempo

– Ejemplo: nivel de agua en un

pantano

• Difícil ser solo de un tipo pero normalmente suelen predominar

los cambios de uno de los dos tipos

12

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I



I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Modelo del sistema

• Representación de un sistema para

estudiarlo

• Simplifica el sistema
• Considera solo los aspectos que afectan al

problema en estudio

• Debe ser lo suficientemente detallado para
poderse obtener conclusiones que apliquen
al sistema real

• Tipos:

– Matemático/Físico
– Estático (Monte Carlo)/Dinámico
– Determinista/Estocástico
– Discreto/Continuo

• Nos interesan los estocásicos, dinámicos

y discretos.

13

SERVICIOS EN LA WEB Y DISTRIBUCIÓN DE CONTENIDOS
Área de Ingeniería Telemática

Ejemplos de simulación



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

•
•

•

Simulation table

Método para seguir el estado del sistema con el tiempo
Metodología

1.

2.
3.

Determinar las características de los inputs a la simulación (normalmente
distribuciones de probabilidad)
Construir una tabla de simulación
Para cada iteración i generar una valor de cada uno de los p inputs y
evaluar la función calculando la respuesta yi que normalmente depende
de los inputs y de respuestas previas

Tabla:

p inputs xij , j = 1,2,…,p
Una respuesta yi
Para cada iteración i

•
•
•

xi1

xi2

…

xij

…

xip

Inputs

Response

yi

Repetitions

i
1
2
3
…
n

15

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D



I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S

I

I



Ejemplo: Servidor Web

• Un servidor web single-threaded
• Recibe peticiones de ficheros que debe obtener del disco duro
• El S.O. atiende las peticiones en serie, completando una antes

de atender la siguiente

• Si el disco está ocupado el hilo del servidor web se bloqueará a

la espera de que el disco finalice

• El disco es capaz de servir datos a 80 Mbps (aprox. 10MBps)

16



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Ejemplo: Servidor Web

• Número infinito de clientes (las llegadas no cambian porque estemos

atendiendo a varios)

• Entre cada par de peticiones consecutivas pasa un tiempo aleatorio

•
•

(uniforme) entre 10 y 90 milisegundos
– Media 50 mseg ⇒ 20 peticiones/seg
Independientes
Los ficheros que se solicitan son de 100xN KBytes donde N está entre
1 y 5 (igual probabilidad, independientes)
– Media 300 KBytes ≈ 2.4 Mbits/petición

• En media se solicitan 48 Mbps
• Caso peor: 500 KBytes a 80 Mbps ⇒ 51 mseg > 10 mseg
• Se formará una cola de peticiones en el servidor

17



I

S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

Ejemplo: Servidor Web

• Más hipótesis:

– Ignoramos los efectos de la red
– Servidor no es multi-hilo
– El disco no atiende a varias peticiones a la vez
– No contamos tiempos de búsqueda en el disco
– Puede mantener a la espera tantas peticiones como necesite

• Preguntas:

– ¿ Cuántas peticiones tienen que esperar a que se atienda otra ?
– ¿ Cuánto tiene que esperar un usuario a que empiecen a servirle el

fichero que ha solicitado ? ¿ Caso peor ? ¿ Media ? ¿ El 95% ?

– ¿ Cuánto podría aumentar la carga y seguir “funcionando” el

sistema ?

– ¿ Qué velocidad de discos se necesita para una “calidad” ojetivo ?

18

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S

I

I



Ejemplo: Servidor Web

• Pregunta simple: ¿ Cuánto tiene que esperar un usuario a que

empiecen a servirle el fichero que ha solicitado ?

Ejemplo con Hoja de cálculo…
Ejemplo en PHP…

19

I



S
O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S

I

I



Ejemplo: Servidor Web

• ¿ Es realista el modelo de usuario ?
– ¿Uniforme el tiempo entre llegadas?
– ¿Y peticiones a ráfagas? (html + imágenes)
– ¿Ficheros tamaños uniformes?
– ¿A partir de cuántos usuarios es razonable suponer una población

“infinita”?

• ¿ De verdad puedo ignorar la red ?

– ¡ Es un flujo en media de 48 Mbps y con picos de 240 Mbps !
– TCP: RTT, pérdidas, control de flujo

20

SERVICIOS EN LA WEB Y DISTRIBUCIÓN DE CONTENIDOS
Área de Ingeniería Telemática

Simulación de eventos discretos

S Simulación de eventos discretos



I

O
D
N
E
T
N
O
C
E
D
N
Ó
C
U
B
R
T
S
D

I

I

I



Y
B
E
W
A
L
N
E
S
O
C
V
R
E
S



I

I

• Modelado con el tiempo de un sistema en el que todos los
cambios de estado se producen en un conjunto discreto de
puntos en el tiempo

• Empleo de métodos numéricos
– En vez de métodos analíticos
– El modelo se “corre” en vez de se “resuelve”

• Se lleva a cabo produciendo una secuencia de snapshots del

sistema con el tiempo

• El snapshot en un instante t incluye
– El estado del sistema en el instante t
– Una lista de las actividades en progreso y cuándo terminarán
– El esta