PDF de programación - Traffic Analysis - Introducción

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

Traffic Analysis

- Introducción -

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Programa 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

• Ejemplos introductorios
• Introducción al Teletraffic Engineering
• Traffic Measurement
• Internet Traffic
• Descripción del tráfico

1

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

Ejemplos introductorios



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 de red

Cada usuario:
• Recibe de un servidor a

100Kbps cuando está activo

• Activo cada uno un 10% del

tiempo

10 usuarios a 100Kbps = 1Mbps

¿ Cuál es la probabilidad de que
más de 10 usuarios reciban
tráfico a la vez ?

Activo

Lee e-mail

Inactivo

Navega

tiempo

A

D

S

L 12

8

K
bps

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

1Mbps

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

Ejemplo de red

¿ Cuál es la probabilidad de que
más de 10 usuarios reciban
tráfico a la vez ?

• Usuario activo un 10% del

tiempo

• Supongamos pues que en un

momento cualquiera:
P(usuario _ activo) = 0.1 = p
• Probabilidad de más de 10

activos:

A

D

S

L 12

8

K
bps

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

P(> 10activos) = 1" P(# 10activos)

!

!

1Mbps

4

Ejemplo de red

¿ Cuál es la probabilidad de que
más de 10 usuarios reciban
tráfico a la vez ?

P(> 10activos) = 1" P(# 10activos)

P(" 10activos) = P(0 _ activos) + P(1_ activo) + ...+ P(10 _ activos) =

!

10

#

i= 0

P(i _ activos)

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

!

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

A

D

S

L 12

8

K
bps

1Mbps

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 de red

¿ Cuál es la probabilidad de que
más de 10 usuarios reciban
tráfico a la vez ?

P(0 _ activos) = (1" p)N

P(1_ activo) = Np(1" p)N "1

P(2 _ activos) =

N(N "1)

2

p2(1" p)N " 2

P(i _ activos) =

"
N
$
#

i

%
’ pi(1( p)N ( i
&

!

!

!

!

1Mbps

6

A

D

S

L 12

8

K
bps

L
S
D
A

s
o
i
r
a
u
s
u

5
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



Ejemplo de red

¿ Cuál es la probabilidad de que
más de 10 usuarios reciban
tráfico a la vez ?

P(" 10activos) =

10

*

i= 0

#
N
%
$

i

&
( pi (1) p)N ) i
’

P(> 10activos) = 1"

!

10

)

i= 0

#
N
%
$

i

&
( pi (1" p)N " i
’

p = 0.1 " P(> 10activos) < 0.0005

!

A

D

S

L 12

8
!
K
bps

1Mbps

7

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

Ejemplo de red

• 35 usuarios x 128 Kbps/usuario = 4,48Mbps
• 4,48Mbps > 1Mbps
• Congestión en enlace de acceso sin dar 128Kbps a todos los

usuarios

• Sobresuscripción (overbooking)



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

A

D

S

L 12

8

K
bps

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

1Mbps

8

Ejemplo de red

• Si ahora un usuario quiere emplear una aplicación de voz
• Pérdidas, excesivo retardo
• Necesitaríamos implementar un mecanismo de QoS
• Pero también en ese caso tendríamos el problema, solo que

con las fuentes con prioridad



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

A

D

S

L 12

8

K
bps

L
S
D
A

s
o
i
r
a
u
s
u

5
3

.
.
.

1Mbps

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



Ejemplo de aplicación

1.000 peticiones por segundo ⇒ nueva petición cada 0,001 segs

• Peticiones a un servidor web
•
• Tamaños de los ficheros 100KBytes
• Discos sirven a 10MBps (80Mbps) ⇒ 1 fichero servido en 0,01 seg ⇒

100 ficheros servidos por segundo
¡ Hay 10 veces más peticiones por segundo que las que soportan los
discos !

•

10MBps

Gigabit Ethernet

10

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

Teletraffic Engineering



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

Teletraffic Engineering

•

“The application of probability theory to the solution of problems
concerning planning, performance evaluation, operation, and
maintenance of telecommunication systems”

• Nos interesa su aplicación a systemas de comunicaciones (de datos y

telefónicos)

• Pero aplica también a tráfico rodado y aéreo, cadenas de montaje,

distribución, gestión de almacén, etc.

• Multidisciplinar:

– Teoría de probabilidad
– Teoría de procesos estocásticos
– Estadísticas
– Queueing theory
– Simulación
– Modelado de tráfico
– Optimización
– Fiabilidad

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

Teletraffic Theory

• Para proveedores de servicio

– ¿Cómo distribuir los puntos de acceso al servicio?
– ¿Cuánto servidores se necesitan para satisfacer las peticiones de

los usuarios?

• Operadoras de red

– ¿Cómo distribuir la carga de red?
– ¿Cuánto buffering requieren los conmutadores/routers?
– ¿Cuáles son las capacidades óptimas?

• Fabricantes

– ¿Cómo utilizar de mejor manera los recursos del equipamiento de

conmutación/enrutado?

– ¿Qué mejoras se debería hacer al mismo?

• Usuarios finales

– ¿Qué calidad de servicio voy a obtener de la red?

13



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

Problema clásico

• Dimensionar el buffer de un ruter dada una carga:

– Determinar tamaño del buffer y velocidad del enlace de

salida

– Asumir encaminamiento estático

14

S Problema clásico: Procedimiento



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

• Tráfico de entrada a cada enlace

– Medirlo
– Determinar estadísticas importantes
– Elegir un modelo apropiado
– Ajustar los parámetros del modelo

• Superposición de procesos en la cola del puerto de

salida
– Usar

propiedades

de

los

modelos

(ej:

Poisson+Poisson=Poisson)

• Analizar la cola bajo una carga determinada
• Determinar el buffer y velocidad de enlace requeridos

– Formular y resolver esta tarea inversa

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



Problema clásico: Resolución

• Analítica

– Modelado de tráfico
– Teoría de colas
– Optimización

• Simulación

– Modelado de tráfico
– Simulación
– Ventaja: menos hipótesis restrictivas
– Desventaja: no es adecuada para optimizaciones

16

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

Terminología y modelos



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

Terminología

• Peticiones recibidas: “Tasa de llegadas” = “Arrival rate” = λ

(1.000 peticiones/seg)

• Hemos supuesto que cada 0,001 segs una nueva: llegadas

Deterministas

• Los discos sirven a 80Mbps
• Los tamaños de los ficheros son constantes (100KBps)
• Capacidad

servidor: Velocidad/Tamaños

del
peticiones/seg = µ

=

100

• El sistema es estable si y solo si:

Tasa de llegadas < Capacidad del servidor (λ<µ)

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

Terminología

• Cn : Llegada n-ésima
•
•
•

τn : instante de la llegada Cn
tn : tiempo entre la llegada Cn-1 y la Cn (tn= τn- τn-1)
xn : tiempo de servicio de la llegada Cn

Llegadas
“arrivals”

Salidas
“departures”

Llegadas:

C0

τ0

C1 C2 C3

t1

t2

t4

τ1

τ2 τ3

C4

τ4

C5

τ5

tiempo

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

Aleatoriedad en las llegadas

• Generalmente los instantes de llegada serán aleatorios
• Cada tn es una variable aleatoria
• Forman un proceso estocástico de tiempo discreto
• Suposiciones más habituales (i.i.d.)

– Todas las vv.aa. tn siguen la misma distribución t
– Todas las tn son vv.aa. independientes

• A(t) función de distribución del tiempo entre llegadas:

A(t) = P(tiempo entre llegadas ≤ t)

" =

1

E[t]

Llegadas:

nº medio de llegadas por unidad de tiempo

Llegadas
“arrivals”

Salidas
“departures”

!

C0

τ0

C1 C2 C3

t1

t2

t4

τ1

τ2 τ3

C4

τ4

C5

τ5

tiempo

20



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

Aleatoriedad en los servicios

• Generalmente las duraciones de los servicios serán aleatorias
• Cada xn es una variable aleatoria
•
• Suposiciones más habituales (i.i.d.)

Forman un proceso estocástico de tiempo discreto

– Todas las vv.aa. xn siguen la misma distribución x
– Todas las xn son vv.aa. independientes

• B(x) función de distribución del tiempo entre llegadas:

B(x) = P(tiempo de servicio ≤ x)

µ=

1

E[ x]

nº medio de usuarios servidos por unidad de tiempo
cuando el servidor está permanentemente ocupado

Llegadas:

!

C0

τ0

C1 C2 C3

t1

t2

t4

τ1

τ2 τ3

C4

τ4

C5

τ5

tiempo

Llegadas
“arrivals”

Salidas
“departures”

21



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

Pérdidas

Llegadas
“arrivals”

Salidas
“departures”

C0

C1

C4

Tiempo
(salidas)

x0

x1

x4

En el servidor

t1

t2

t4

τ0
C0

τ1
C1

τ2 τ3
C2 C3

τ4
C4

τ5
C5

Tiempo
(llegadas)

22



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



Con cola

Llegadas
“arrivals”

Salidas
“departures”

• Cola infinita o con

tamaño máxi