PDF de programación - Predecibilidad del tráfico en redes modernas de comunicaciones

Predecibilidad del Tráfico en Redes Modernas de Comunicaciones

Marco Aurelio Alzate Monroy y José Félix Vega Stavro


Resumen

En este artículo se presentan los resultados de
algunos experimentos que permiten determinar la
predecibilidad de una traza real de tráfico con
características fractales. Se concluye que, sin
necesidad de ajustar las observaciones a un modelo
autosemejante particular, es posible utilizar
estadísticas muestrales típicas para predecir con
sorprendente exactitud la intensidad de tráfico en el
futuro inmediato. Por último, se discute cómo
podría explotarse esta característica para mejorar
los mecanismos actuales de control de congestión
en redes modernas de comunicaciones. Tanto el
tratamiento del tema como la presentación de los
experimentos se hacen de una manera tutorial.

Palabras

óptima,
predicción lineal, Tráfico autosimilar, Control de
Congestión.

Predicción

claves:

es muy probable que

memoria en estas colas, tales como RED, REM,
BLUE y todas sus variantes [2,3,4]. Sin embargo,
excepto por un posible procedimiento de ajuste del
tráfico en los nodos de ingreso (básicamente Leaky
Bucket), ninguno de estos mecanismos de control
de congestión prestan atención a las características
estadísticas de cada flujo de tráfico ni del flujo
agregado. De acuerdo con muchas medidas
recientes de tráfico en muy distintos contextos
[5,6,7,8,9,10],
esas
características correspondan a un proceso con
dependencia de rango largo, LRD, lo cual implica
una alta variabilidad y presencia de ráfagas en
muchas escalas de tiempo [11]. Este tipo de
variabilidad induce extensos períodos de sobrecarga
y subutilización que degradan significativamente el
desempeño de la red. De hecho, se ha reportado que
bajo tráfico LRD los períodos de congestión pueden
ser tan extensos y con una pérdida de paquetes tan
concentrada que nisiquiera un gingantesco
incremento en el tamaño de la memoria podría
decrementar la tasa de pérdida de paquetes de una
manera notoria [13]. En consecuencia, las técnicas
de control por realimentación son poco útiles si el
tiempo de respuesta del control no alcanza a
considerar las muchas escalas a las cuales se puede
presentar la congestión, especialmente en redes en
las que el producto retardo×ancho de banda es muy
alto [14].

Si bien la variabilidad LRD tiene estos efectos
negativos sobre el desempeño, imponiendo serias
dificultades a
los algoritmos de control de
congestión, también es cierto que este tipo de
procesos poseen una compleja estructura de
correlación que puede ser explotada para "predecir
el futuro" [14]. Algunos autores han trabajado en
esta idea con promisorios resultados, aunque sus
trabajos se han basado en modelos particulares de
tráfico en los que la predicibilidad está garantizada
por la estructura misma del modelo (básicamente,
movimiento browniano fraccional, fbm, sintetizado
aproximadamente mediante el multiplexaje de
procesos on/off con distribuciones de cola pesada
en sus períodos de actividad y/o inactividad) [14,
15, 16, 17, 18]. En este artículo revisamos la
predecibilidad de una traza real de tráfico para
verificar su aplicabilidad en los esquemas de
control de congetión, asignación de recursos,
balanceo de carga, etc. En particular, utilizamos la
traza BC-pAug89 medida en la red Ethernet de
Bellcore en 1989 [19], para la cual ya se ha
establecido plenamente su autosemejanza [9].



1. Introducción


(por ejemplo

Los procedimientos de control de congestión
mediante realimentación entre extremos, como
TCP, consisten en que las fuentes de tráfico ajusten
su tasa de datos según las medidas de congestión
obtenidas de la red. Estas medidas suelen ser
indirectas
la ausencia de un
reconocimiento o el incremento en el tiempo de
"ida-y-vuelta", RTT) y llegan a las fuentes después
de un retardo significativo. Inclusive cuando se usa
notificación explicita de la congestión (ECN), que
es una medida directa que tarda menos en llegar
que las medidas indirectas anteriores, el tiempo que
transcurre entre la detección de la congestión y su
notificación a las fuentes de tráfico es del orden de
un RTT, el cual suele ser mucho mayor
precisamente durante los períodos de congestión.
Este retardo en el camino de la realimentación
implica muchas dificultades en el control efectivo
de la congestión pues las acciones de control que se
toman no corresponden al estado actual de
congestión en la red, sino a algún estado previo. Por
supuesto, una acción retardada suele traducirse en
oscilaciones e inestabilidades que traen efectos
desastrosos en la calidad del servicio ofrecido por
la red [1].

Muchos esfuerzos de investigación se han
concentrado en tratar de mitigar estos efectos
negativos del retardo en el lazo de realimentación
mediante la estabilización de las colas en los nodos
congestionados o próximos a congestionarse. Como
resultado de estos esfuerzos se han desarrollado
diferentes estrategias de administración de
la

)
s


1
0

.

0
(

)
s


1

.

0
(

)
s


1
(

)
s


0
1
(



Puesto que no estamos asumiendo ningún
modelo de tráfico, no podemos utilizar técnicas
óptimas de predicción basadas en modelos. En
cambio de esto utilizaremos dos esquemas en el
dominio del tiempo que aprovechan la supuesta
dependencia de rango largo: uno es un método
particular de estimación de la media condicional
[14] y otro es un método tradicional de predicción
lineal [16]. En ambos casos, compararemos los
resultados de predecibilidad con una traza muestral
de un proceso Poisson 'equivalente', esto es, con el
mismo tiempo promedio entre llegadas y la misma
longitud promedio de los paquetes.

la sección 2 describimos

trazas
muestrales del tráfico. En la sección 3 discutimos la
predicción óptima e implementamos un método
aproximado de predicción óptima. En la sección 4
describimos la predicción lineal de mímino error
cuadrado promedio. Por último, en la sección 5,
discutimos la posibilidad de usar estas predicciones
para mejorar los mecanismos actuales de control de
congestión en redes modernas de comunicaciones,
con lo cual concluimos el artículo.

las

En



2. Trazas de Tráfico

los

red Ethernet de


La traza muestral BC-pAug89 [19], medida en
una
laboratorios de
investigación Bell (hoy Telcordia technologies) en
1989, corresponde a dos series de tiempo que
representan los instantes de llegada y las longitudes
de un millón de paquetes, medidos en un lapso de
3142.82 segundos. En promedio llegan 318,185
paquetes por segundo, cada uno con una longitud
promedio de 434,29 bytes. Esta traza muestral
exhibe alta variabilidad en un amplio rango de
escalas de tiempo, como se puede ver en la Figura
1. En efecto, en la figura 1(a) observamos el
número promedio de bytes por segundo que llegan
durante los primeros 2 segundos, considerando los
promedios durante períodos de 0.01 segundos; esto
es, la barra que aparece en el instante t de la gráfica
corresponde al número de bytes por segundo que,
en promedio, pasaron por un segmento de la red en
el intervalo [t, t+0.01 s). En la figura 1(b)
extendemos el
rango de 2 a 20 segundos
aumentando la granularidad de los intervalos de
0.01 s a 0.1 s. Este proceso lo repetimos en las
figuras 1(c) y 1(d), que tienen granularidades de 1 y
10 segundos respectivamente; esto es, la barra que
aparece en el
la figura 1(d)
corresponde al número de bytes por segundo que,
en promedio, pasaron por ese segmento de la red en
el intervalo [t, t+10 s). Se puede observar la
presencia de ráfagas en cada una de estas escalas,

instante

t de

de manera que la variabilidad parece ser una
característica autosemejante en esta traza.

x 105

15

10

Tasa promedio de llegadas (bytes/s)

0
x 105

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

0
x 105

2

4

6

8

10

12

14

16

18

20

0
x 105

20

40

60

80

100

120

140

160

180

200

5

0

6

4

2

0

6

4

2

0

4

2

0

0

200

400

600

800

1000

1200

1400

1600

1800

2000

tiempo en segundos



Figura 1. Número de bytes que pasan por un

segmento de red en intervalos de (a) .

0.01 s, (b) 0.1 s, (c) 1 s y (d) 10 s

En contraste, la figura 2 muestra el mismo
procedimiento de conteo de bytes con diferentes
granularidades en el tiempo, pero considerando un
proceso de Poisson con longitud de paquetes
exponencialmente distribuida. Nótese cómo en este
caso, a diferencia de la traza BC-pAug89, cualquier
segmento de 10 segundos que consideremos servirá
para hacer un adecuado estimativo del número de
bytes que llegan por segundo: la presencia de
ráfagas sólo se da en un rango muy limitado de
escalas de tiempo, en el orden del intervalo
promedio entre llegadas

x 105

Tasa promedio de llegadas (bytes/s)

0
x 105

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

0
x 105

2

4

6

8

10

12

14

16

18

20

)
s

1
0
.
0
(

)
s

1
.
0
(

6

4

2

0

3

2

1

0

2

)
s

1
(

1

0
x 104

20

0

15

10

40

60

80

100

120

140

160

180

200

5

0

0

200

400

600

800

1000

1200

1400

1600

1800

2000

tiempo en segundos

)
s


0
1
(

Figura 2. Tráfico de Poisson a diferentes escalas

de tiempo .


La invarianza a la escala en la traza BC-
pAug89 puede expli