Download - Características del Tráfico de Redes
![Page 1: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/1.jpg)
1
Características del Tráfico de Redes
Prof. Dr. Claudio Enrique RighettiAplicaciones Escalables en Redes Globales
2 Cuatrimestre 2006 – Segundo CursoDepartamento de Computación
Facultad de Ciencias Exactas y NaturalesUniversidad de Buenos Aires
![Page 2: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/2.jpg)
2
Motivación Comprender el comportamiento del tráfico de red es esencial
para todos los aspectos relacionados con el diseño/operación de una red o sistema:– Provisioning– Administración – Modelización– Simulación– Diseño de Componentes– Diseño de Protocolos
![Page 3: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/3.jpg)
3
Lecturas recomendadas
• [LTW+94] W. Leland, M. Taqqu, W. Willinger, D. Wilson, On the Self-Similar Nature of Ethernet Traffic, IEEE/ACM TON, 1994.
– Baker Award winner
• [PF95] V. Paxson, S. Floyd, Wide-Area Traffic: The Failure of Poisson Modeling, IEEE/ACM TON, 1995.
• [CB97] M. Crovella, A. Bestavros, Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes, IEEE/ACM TON, 1997.
![Page 4: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/4.jpg)
4
Características del Tráfico
![Page 5: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/5.jpg)
5
Características del Tráfico
Dado un periodo T podemos medir:
Medio Pico Varianza Burstiness Parámetro de Hurst (H)
![Page 6: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/6.jpg)
6
Intensidad del Tráfico o Tráfico Medio La llegada media de un flujo de tráfico (m) describe la intensidad del tráfico
kik
AAEm i
i
,,2,1,][
donde Ai es el número de llegadas en el tiempo i.
![Page 7: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/7.jpg)
7
Tráfico Pico
El tráfico pico p, mide el valor más alto del número de llegadas en una instancia en particular sobre un periodo de tiempo
kAAAAp ,,,,max 321
Donde Ai número de llegadas al tiempo i.
![Page 8: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/8.jpg)
8
Varianza
La varianza mide la dispersión de un flujo de tráfico
k
mAA i
i
i
2
22 AEEAVar
donde Ai número de llegadas en el tiempo i. i = 1,2,…,k.
• Desviación Standard =
![Page 9: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/9.jpg)
9
Burstiness
Burstiness describe “how bursty” es un flujo de tráfico
m
]E[
)Var(Burstiness
A
A
donde desviación m valor medio del tráficoSe suele denominar también “coeficiente de dispersión “
![Page 10: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/10.jpg)
10
Parámetro de Hurst
n: intervalo temporal de agregación V(A)n: varianza de A en el intervalo n.
log n
log V(A)n
nAV n loglog
![Page 11: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/11.jpg)
11
Parámetro de Hurst
Si 1 (o H0.5), tráfico es LRD ( Long Range Dependent )
Si 1 (o H0.5), tráfico es SRD (Short Range Dependent)
H = /2
log n
log VnLRD
SRD
![Page 12: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/12.jpg)
12
Teorema del limite Central
Sean X1, X2, …, Xn una secuencia de variables random independientes idénticamente distribuidas con un valor medio y una varianza 2.Entonces la distribución :
Tiende a la Standard normal cuando n es grande
n
nn
XXX 21
![Page 13: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/13.jpg)
13
Auto-Similar o Poisson ?
![Page 14: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/14.jpg)
14
![Page 15: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/15.jpg)
15
Un primer modelo
• La modelizacion de tráfico en la telefonía por conmutación de circuitos fue la base en los modelos iniciales de red – Se asume que los procesos de llegada son de Poisson– La duración de una llamada es de Poisson – Basados en esas suposiciones se estableció una bien
conocida literatura sobre teoría de colas
![Page 16: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/16.jpg)
16
Modelo Poisson• Marco de trabajo establecido desde hace décadas
• Los eventos de red (llegadas de paquetes, llegadas de conexiones) se modelan como independientes, dichos eventos son producidos por un “gran” # de clientes
• Tiempo entre “llamadas” (eventos) están distribuidos exponencialmente ( # de llamadas ~ Poisson )
• con un único parámetro de “” ( velocidad media )
• Esto implica (Si asumimos un modelo de Poisson):
– Correlaciones son “fugaces” y los bursts son limitados
– La agregación de tráfico tiende a suavizarse rápidamente
![Page 17: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/17.jpg)
17
El inicio de un trabajo fundacional …
• En 1989, Leland et al comenzaron a recolectar trazas de tráfico – Tráfico Ethernet de un gran laboratorio [1]– Time stamps de 100 m sec. – Packet length, status, 60 bytes de data– Principalmente tráfico IP (una suerte de mini backbone NFS)– Periodo de 3 años , 4 conjuntos de datos– Trazas consideradas representativas de un uso normal
[1] Bellcore Morristown Research and Engineering Center
![Page 18: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/18.jpg)
18
Tráfico Ethernet vs. Poisson
Taqqu et al., (1997)
![Page 19: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/19.jpg)
19Vern Paxson (March 5th, 2004)
![Page 20: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/20.jpg)
20
10
Previous Region
Vern Paxson (March 5th, 2004)
![Page 21: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/21.jpg)
21
100
![Page 22: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/22.jpg)
22
600
![Page 23: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/23.jpg)
23
![Page 24: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/24.jpg)
24
Tráfico Real - Burstiness
• Las correlaciones son fuertes en un gran rango
• Espectro de Potencia:
– Es plano para procesos de Poisson
– Para el medido diverge a cuando 0
![Page 25: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/25.jpg)
25
Caracterizando Tráfico con Fractales
• Leland et al [LTW+94] proponen capturar tales características utilizando auto-similaridad, una forma de modelar basada en fractales:
– Parametrizado por parámetro de “ Hurst”
– Valor medio y varianza finitos
– La serie temporal debe ser muy gran grande para poder testear dicho comportamiento
• El Modelo predice burstiness en todas las escalas de tiempo delays de encolado/probalidad de drop mucho mas
alta que las que se predicen con modelos basados en procesos de Poisson
![Page 26: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/26.jpg)
26
Proceso Auto-Similar vs. Poisson
• Poisson – Cuando observamos en una escala pequeña de
tiempo el mismo presenta ráfagas– Cuando agregamos “coarse time scale” tiende a
suavizarse (smooth) a ruido blanco• Auto-Similar
– Cuando agregamos sobre amplias escalas de tiempo se mantienen las características de ráfagas
![Page 27: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/27.jpg)
27
Procesos Auto-Similares
• Propiedades :
a) Decaimiento lento de la varianza
b) Dependencia a largo plazo
Las cuales se hacen presentes al aumentar el nivel de agregación
Def.
,.......2,1,...1
1 kXXm
X kmmkmm
k
![Page 28: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/28.jpg)
28
Agregación
• Cada
• Se tiene
Donde se crea una nueva serie en el tiempo obtenida por el promedio de la serie original con bloques que no se solapan de tamaño m
X
.....3,2,1m
.....3,2,1: kXX mk
m
![Page 29: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/29.jpg)
29
Auto- Similaridad• Los procesos Auto-Similares (SS Self-similar) es la forma mas simple de
modelar procesos con dependencia de largo plazo (LRD long-range dependence ) ( correlaciones que persisten a lo largo de largas escalas de tiempo )
• La funcion de autocorrelacion r(k) de un proceso con LRD :
– r(k) =
– r(k) k-b as k para 0 < b < 1• La funcion de autocorrelacion sigue una “power law”• Decaimiento lento
– Espectro de potencia es hiperbolico cuando 0
– Si r(k) < SRD short-range dependence
![Page 30: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/30.jpg)
30
Auto-Similar• Si consideramos las serie temporal X = (Xt ; t = 1,2,3,…), definimos la
serie de agregación m a X(m) = (Xk(m);k = 1,2,3,…) a la sumatoria de X
sobre bloques de tamaño m. Decimos que X es H-Auto-similar (H-self-similar) si para todos los valores positivos de m, X(m) tiene la misma distribución que X “reescalado” por mH.
• Si X es H-self-similar tiene la misma función de auto correlación r(k) que la serie X(m) para todo m.
• El grado de Auto-Similaridad SS se expresa como la velocidad de decaiminiento de la serie de la función de auto correlación usando como parámetro H ( Hurst)
– H = 1 - b /2– Para series SS con LRD, ½ < H < 1– El grado de SS y la LRD se incrementan cuando H 1
![Page 31: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/31.jpg)
31
Estimadores Gráficos• Grafico Varianza-tiempo ( Varianza de los agregados )
– Se basa en el decaimiento lento de la varianza de un serie auto-similar
– Se grafico la varianza de X(m) versus m en escala log-log– Pendiente (-b) menor que –1 indica SS (self-similarity)
• Grafico R/S– Se basa en el grafico reescalado (R/S) el cual crece
estadísticamente en forma similar a una power law con H como una función del numero de puntos n ploteados
– Describe la propiedad de LRD mediante un estudio de las autocorrelaciones del trafico agregado
– Se grafica R/S versus n en una escala log-log la pendiente estima H
• Periodogram plot• Wavelet
![Page 32: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/32.jpg)
32
VT plot
![Page 33: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/33.jpg)
33
Plot R/SPlot R/SR
/S
Tamano bloque n
Pendiente 0.5
Pendiente 1.0
![Page 34: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/34.jpg)
34
Plot R/SPlot R/SR
/S
Tamano bloque n
Pendiente 0.5
Pendiente 1.0
Pendiente H (0.5 < H < 1.0)(Hurst )
![Page 35: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/35.jpg)
35
Ejemplo R/S plot
![Page 36: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/36.jpg)
36
Análisis del Tráfico Ethernet [LTW+94]
• Del análisis de los logs de trafico desde la perspectiva de la unidad paquetes/tiempo se encontró que el mismo tiene un comportamiento auto-similar con un parámetro entre 0.8 y 0.95.– Agregaciones sobre muchos ordenes de magnitud– Los tráficos WAN tendrían comportamiento similar
• Fue el primer uso de un conjunto MUY grande de mediciones en investigación de red
• Condujo al modelo de trafico ON-OFF
![Page 37: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/37.jpg)
37
Modelos de Tráfico No Auto-Similares
![Page 38: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/38.jpg)
38
Modelos
ON-OFF Poisson Autoregresivo Gaussiano Markov Modulated M/Pareto
![Page 39: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/39.jpg)
39
Modelo ON-OFF (1)
• El tráfico alterna entre dos periodos: ON - OFF• ON: se genera tráfico a una velocidad r.• La longitud de ON y OFF son independientes y pueden
tener distribuciones distintas
Pon Poff
r
t
Velocidad
(en %)
m = Pon rvarianza= r2 (Pon)(1Pon) = m (r m)
![Page 40: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/40.jpg)
40
Si consideramos N fuentes independientes :
Donde m es el valor medio de cada fuente ON-OFF y r es la velocidad de datos de cada una
Modelo ON-OFF (2)
Valor medio Agregado = N m Varianza Agregada = N [m (r m)]
![Page 41: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/41.jpg)
41
• Función densidad de probabilidad, PDF (Probability density function )
• Poisson esta categorizado, por un parámetro .• La agregación de tráfico de Poisson es también Poisson
Poisson
Pn(t) = et (t)n
n!
PoissonPoissonPoisson
…Poisson
…=> Poisson
![Page 42: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/42.jpg)
42
• Procesos Gaussianos con tres parametros son suficientes para estimar performance de encolado
• Procesos autorregresivos de 1-orden :
donde Un es Gaussiana con valor medio y varianza 2. a, b son reales con |a| < 1.
• Para caracterizar el tráfico real, necesitamos encontrar la mejor forma de ajuste de los parámetros: a, b, , .
Modelo Autorregresivo Gaussiano
nnn bUaAA 1
![Page 43: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/43.jpg)
43
Modelo MMPPMMPP = Markov Modulated Poisson Process
rate 1 rate 2
r1
r2
1t
data rate
2
![Page 44: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/44.jpg)
44
Modelo de Tráfico Auto-Similares
![Page 45: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/45.jpg)
45
Modelo M/Pareto
• Tráfico Fractal está caracterizado por “long bursts”
• Long bursts son causados por– descarga de archivos grandes– alto nivel de variable bit rate (VBR) producto de video– intensive burst por la actividad de BD
• M/Pareto caracteriza el tráfico Fractal.
![Page 46: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/46.jpg)
46
Modelo M/Pareto (1)
• El proceso de llegada es de Poisson
• Cada llegada trasnporta una ráfaga de transmisiones
• La duración de la transmisión está distribuida Pareto
t
arrival
La duración distribución de Pareto
r data rate
![Page 47: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/47.jpg)
47
Modelo M/Pareto (2)
t
Llegadas Poisson con parametro
La duración distribución de Pareto
![Page 48: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/48.jpg)
48
Modelo M/Pareto (3)
Distribución de Pareto
maneraotra de,1
,Pr
xx
xX
0,21 dondey
XX var,1
E
![Page 49: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/49.jpg)
49
Modelo M/Pareto (4)
1
m
rt
tt
t
r
tt
tr
,321
21
1
1
1
2
1
321
1
22
1
3
12
0,1
11
22
var
3
2
32
22
Consideremos el tráfico dentro un intervalo de tiempo t en el modelo M/Pareto
2
3 H
El tráfico M/Pareto está categorizado por cuatro parámetros:
, , (indice tail), r
![Page 50: Características del Tráfico de Redes](https://reader031.vdocumento.com/reader031/viewer/2022012919/568158da550346895dc6215a/html5/thumbnails/50.jpg)
50
Modelo M/Pareto (5)
• En un enlace LAN- BACKBONE LOCAL
pequeño• En enlace BACKBONE LOCAL- Router a
Internet
grande• Enlace Router – Router de un AS
grande