Modelamiento de Tráfico, Tráfico Autosimilar Natalia Clivio Velilla Maestría en Telecomunicaciones – Optimización de Tráfico en Redes Universidad de Buenos Aires Junio, 2012
Resumen 1. Introducción El tráfico es la medida de la demanda de los usuarios sobre los recursos de una red de Comunicaciones. Este tráfico es analizado por modelos matemáticos que caracterizan sucesiones de variables aleatorias que evolucionan en función de otra variable, normalmente el tiempo. Estos son procesos son llamados estocásticos. Inicialmente se consideraron modelos donde los tiempos de llegada de las demandas eran independientes entre sí, así como la duración de la llamada. Posteriormente se vio la necesidad de incluir nuevos servicios en las redes como imágenes y video, para este tráfico es necesario considerar modelos más elaborados donde halla correlación entre las variables involucradas y que decaigan exponencialmente con el tiempo. Sin embargo en las redes actuales se ha demostrado que este tiempo no decrece tan rápido y puede persistir a través de muchas escalas de tiempo. Este fenómeno afecta el desempeño de las redes y se pueden representar mediante modelos de tráfico Autosimilar o fractal. En este artículo se presentan los conceptos básicos del estudio de los modelos de tráfico Autosimilar compilados en varios artículos y se expone un experimento tomado del trabajo de los Ingenieros Marrone y Bravo. Palabras Clave: Modelos de Tráfico, Autosimilitud, Tráfico Fractal, Buffer de asignación dinámica.
El término de tráfico Autosimilar fue definido formalmente por Mandelbrot (1983) con su teoría geométrica fractal y la extensa bibliografía de Taqqu (1985) [1]. En este articulo se pretende iniciar el estudio del tráfico autosimilar, inicialmente se habla de Modelamiento de tráfico y los conceptos básicos que se tienen en cuenta en un análisis estocástico para servicios de voz, posteriormente con la evolución de las redes de telecomunicaciones se introducen los conceptos básicos para entender los fundamentos del tráfico Autosimilar o fractal y cómo influyen en el comportamiento de las redes de comunicaciones. Finalmente se cita el trabajo de los ingenieros Marrone y Bravo donde analizan tres fuentes de datos, introduciendo el factor H y caracterizando la probabilidad de bloqueo de la red para este experimento, aunque su trabajo es más detallado, acá solo se cita uno de los escenarios analizados.
2. Modelamiento de Tráfico El tráfico es la medida de la demanda que los usuarios de una red de comunicaciones imponen sobre la red, para esto se usan modelos matemáticos del comportamiento de los usuarios. Estos patrones de llegada se pueden medir en términos de: Paquetes, celdas, llamadas, flujos, conexiones, bits o cualquier unidad de información adecuada.
Se pueden medir en alguna secuencia de tiempo que los identifique como son: Tiempos de llegada , Números de llegadas hasta el instante t , Secuencia e tiempos entre llegadas , Como estas representaciones son el mismo fenómeno, están relacionados entre sí [2]: N(t) = max {n Tn t} An = Tn – (Tn-1) Tn = Ak Comparando el tráfico de una red de servicios integrados (voz y datos), se puede observar que Son impredecibles y se deben moderar como procesos estocásticos. Los datos pueden modelarse por un proceso de Poisson pero la voz debería ser modelada por un proceso que tenga en cuenta la correlación entre la actividad y la inactividad del usuario. Estos demuestran que se necesitan desarrollar distintos modelos de tráfico para distintos tipos de servicio. [1] En las actuales redes de telecomunicaciones se transportan nuevos servicios como imágenes y video gracias a sus cambios de capacidad. Estas suposiciones resultaran ampliamente variados por mediciones reales de tráfico permitiendo desarrollar métodos de diseño para asegurar parámetros de calidad de servicio, es decir la probabilidad de bloqueo de la red (PB) [1]. Estos modelos de Poisson dejan de ser validos cuando se quieren modelar nuevos servicios como imágenes y video, ya que no puede esperarse independencia en los tiempos de llegada. Así a partir de los 80`s se empezaron a desarrollar nuevos modelos de tráfico que tenga en cuenta la correlación entre tiempos de llegada. Podría pensarse en un modelo de dos estados, activo e inactivo donde en el activo se generan tasas de transmisión constantes y en el activo no se generan paquetes [3]. Este
comportamiento obedece a un proceso determinístico markovianamente modulado (MMDP). Esto para un servicio de voz. Para un servicio de Datos interactivos permanentes como se indica en la Figura 1 y TX esporádica se puede modelar por un proceso de Poisson markovianamente modulado (MMPP) ya que es un tráfico compuesto. Donde la llegada forma un proceso de Poisson con distinta intensidad.
Figura 1. Tráfico de TX de archivos Este tipo de modelos capturan mucha correlación entre llegadas que impactan el desempeño de la red y cuyo efecto no se observa en el modelo de Poisson. Los modelos MMPP, han sido útiles en el Modelamiento de video con tasas variables de bits como MPEG2, en las que la transición entre tipos de tramas I, P y B constituye una cadena de Markov, cada una con su respectiva tasa de promedio de llegadas tipo Poisson como indica la figura 2. [4]
Figura 2. Cadena de Markov
3. Conceptos Fundamentales Tráfico Autosimilar
de
La autosimilitud y la fractalidad deben el inicio de su estudio al matemático Benoit Mandelbrot, que define a un fractal como un objeto semigeométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas temporales o espaciales. Este fenómeno sucede en imágenes naturales, en el
subdominio de convergencia de ciertos sistemas dinámicos y en muchas series de tiempo [5] como en los procesos de tráfico que es el caso de estudio del presente artículo. En un objeto autosimilar o fractal, sus partes magnificadas se asemejan a la forma del objeto completo, donde la semejanza se mide en algún sentido adecuado. [1] a. Autosimilitud Determinística Mediante la iteración de cierto procedimiento se puede obtener, por simple construcción, la forma más sencilla de autosimilitud. Un buen ejemplo es el copo de nieve de Von Koch (Figura 3), que se construye dividiendo cada línea en tres segmentos iguales y remplazando el segmento de la mitad por dos segmentos iguales, como en un triángulo equilátero. Si el procedimiento se repite para cada nuevo segmento indefinidamente, cualquier pequeña porción de la curva de Von Koch puede magnificarse para reproducir, exactamente, una porción mayor. Esta propiedad se conoce como “Autosimilitud exacta”. [1]
N-1/D. Así pues, la dimensión de un objeto autosimilar compuesto por N partes idénticas en las que cada lado ha sido escalizado por un factor r es: D = log(N) / log (1/r). [1]
Figura 4. Figura Autosimilar de dimensión fractal 1,2 y 3. En el caso de la curva de Von Koch, cada segmento de línea se convierte en N = 4 subsegmentos, cada uno de los cuales se escaliza por un factor r = 1/3, de manera que su dimensión es D = log(4)/log(3)=1.26. Como ésta es una dimensión fraccional, a estos objetos autosimilares se les llama también fractales. [6] Otros objetos fractales pueden surgir de los subdominios de convergencia de ciertos sistemas dinámicos. Como el conjunto de Mandelbrot que está formado por los puntos c que no escapan a infinito bajo la iteración c = c + c2, como muestra la figura 5. [1]
Figura 3. Copo de Nieve de Von Kosh. Un segmento de línea como el de la figura 3 es un objeto unidimensional autosimilar pues puede dividirse en N segmentos idénticos, cada uno de ellos escalizado por el factor r = N-1. Igualmente, un cuadrado es un objeto bidimensional autosimilar pues puede dividirse en N cuadrados idénticos, donde el lado de cada uno de ellos se ha escalizado por un factor r = N1/2. Finalmente, un cubo es un objeto tridimensional autosimilar que puede dividirse en N cubos idénticos, donde el lado de cada uno de ellos se ha escalizado por un factor r = N-1/3 (Figura 4). Generalizando, un objeto Ddimensional autosimilar puede dividirse en N copias más pequeñas de si mismo donde el lado de cada copia se ha escalizado por un factor r =
Figura 5.Conjunto de Mandelbrot
b. Autosimilitud Estocástica La autosimilitud estocástica, como la determinística, se puede analizar por medio de la figura 6, donde se ilustra trafico Ethernet monitoreado en el trabajo de Leland y Willinger (1994), en la cual se observan paquetes en 5 distintas unidades de tiempo, cada muestra se obtiene de la anterior con un incremento de 10 veces de subintervalos elegidos aleatoriamente. Este comportamiento invariante o Autosimilar caracteriza el tráfico Ethernet y es drásticamente distinto al tráfico telefónico y los modelos estocásticos de paquetes que se consideran en la literatura. [1]
Figura 6. Muestras Tráfico Ethernet a 5 escalas de tiempo.
c.
Estimación parámetro H
Una definición habitual de los procesos estocásticos auto-similares se basa en un escalado de la variable aleatoria continua en el tiempo. Un proceso estocástico X(t) es estadísticamente auto-similar con parámetro 0,5 1 si para cualquier número real 0, el proceso a tiene las mismas propiedades estadísticas que x(t). Esta relación se puede expresar con las condiciones de media, varianza y Autocorrelación
El parámetro H (parámetro de Hurst o parámetro de auto-similitud), es una medida clave de la auto-similitud del proceso, de la longitud de la dependencia a largo plazo de un proceso estocástico. A medida que el valor de H se aproxima a 1 aumenta el grado de persistencia de la dependencia a largo plazo (H=0.5 indica ausencia de auto-similitud). Como ejemplo de esta definición, se considera el proceso FBM (Fractional Brownian Motion), que es utilizado frecuentemente en el análisis de tráfico de datos de auto-similar. [4] Un proceso FBM BH(t) se define como:
Donde X es una variable aleatoria normalmente distribuida con media cero y varianza 1, y H es
un parámetro del proceso. Así pues, el valor del proceso en el instante de tiempo t es igual al valor de la variable aleatoria X multiplicado por el intervalo de tiempo elevado a H.
Como se había indicado si H = 0.5, la correlación entre incrementos pasados y futuros es nula (incrementos independientes). Sin embargo, para 0,5 se observa el fenómeno de persistencia; un incremento positivo (o negativo) en algún instante de tiempo implica un nuevo incremento (o decremento) en el futuro. Este comportamiento persistente está en conflicto con lo que normalmente se ha asumido sobre el fenómeno estocástico. Así como se había demostrado con las capturas de tráfico Ethernet descritos anteriormente (Figura 6). En algunos procesos (BM - brownian motion), los incrementos son independientes, en otros la Correlación se mantiene para intervalos de tiempo pequeños, ∆ . [4]
A continuación se describe un algoritmo para la asignación dinámica de buffer y se comparará el performance del mismo, medida como la probabilidad de bloqueo, frente a dos políticas de buffering: Particionamiento Completo y Límite Dinámico en condiciones de tráfico entrante autosimilar [10]. A partir del trabajo de Choudhry Hahne [11] se propone una política de asignación de buffer basada en la idea de que la longitud máxima permisible para cualquier cola individual en cualquier instante de tiempo, es proporcional al espacio de buffering no usado en el switch. Denominado por los autores como límite Dinámico, combina la simplicidad de la política de límite estático y la adaptabilidad del pushout. En la figura 7 se muestra la variación del umbral en función de la longitud de la cola, para un valor de 1
4. Algorítmico Algebraico para asignación dinámica de Buffer Como ampliación del tema anterior, ahora se tomará como referencia el trabajo desarrollado por los Ingenieros Bravo y Marrone [8]. En una red de Switch, la asignación de los buffers y su política de manejo afectan directamente al performance de estos dispositivos. Algún esquema de manejo de buffer es necesario, para asegurar que un switch de memoria compartida con encolamiento de salida, no empeore su performance en condiciones de sobrecarga.
Figura 7.Limite [12]
Dinámico
La variación del algoritmo propuesto en el trabajo de Bravo y Marrone [10] es que la pendiente de la curva de variación del umbral vaya aumentando o disminuyendo paulatinamente de acuerdo a la variación de la longitud de la cola de manera que la pendiente de la curva crezca a medida que el grado de ocupación del buffer aumenta permitiendo un mejor aprovechamiento del espacio del buffer existente y mayor adaptación a los cambios de variación de tráfico. Así como se indica en la figura 8.
#
#$%& &' (&')* +,' #$%& &' , - .&&*+,'
El espacio total del buffer se fue incrementando y se obtuvo para cada política en cada uno de estos incrementos la probabilidad de bloqueo. Los valores de H para las series generadas en cada fuente se muestran en la siguiente tabla [3]
Figura 8. Límite Dinámico Propuesto
[12] Donde: B Espacio total del buffer T(t) umbral de control en el tiempo t Qi(t) longitud de la cola i en t Q(t) suma de todas las longitudes de las colas i y C=Q(t)/B. A continuación se analizará el algoritmo propuesto con otras políticas de asignación como Límite estático partición completa y Límite Dinámico bajo condiciones de tráfico autosimilar, para lo cual se tomaron 3 líneas conectadas a una fuente de tráfico individual que es generada por el algoritmo “Random Midpoint Displacement method”, cada línea genera 8000 paquetes con una tasa media λ= 500, con y un valor determinado H. Como se detalla en la figura 9.
Figura9. Modelo de encolamiento para el switch de memoria compartida ki, es el ancho asignado del buffer FIFO para el puerto i. La velocidad del enlace de salida esta dado por !", y B el ancho del espacio total de memoria. [12] La medida de performance empleada es la Probabilidad de Bloqueo (PB) y está definida por: [8]
Tabla 1. Valores H para cada una de las series generada en cada fuente. En la figura 10 se muestra el decaimiento de la probabilidad de bloqueo para el caso del algoritmo con particionamiento completo y con el aumento del tamaño del buffer. [8]
Figura 10. Probabilidad de Bloqueo en función de H y del ancho del buffer. Es importante analizar como la probabilidad de bloqueo va decreciendo con el tamaño del buffer más lentamente a medida que el nivel de autosimilitud va aumentando, siendo casi exponencial su decrecimiento para valores de H entre 0,5 y 0,6, y decayendo más lentamente para valores mayores, lo que da una idea del
impacto que tiene el tráfico autosimilar en el diseño de las redes. [8] Se puede observar, que la política de asignación de buffer propuesta, presenta una mejor respuesta en la probabilidad de bloqueo, que las otras dos políticas de asignación dinámica proporcional y particionamiento estático diferencia que se va incrementando a medida que el nivel de autosimilitud aumenta, lo que indica que el umbral dinámico propuesto se adapta de una mejor manera a las condiciones de tráfico autosimilar, y además, que la probabilidad de bloqueo mejora más rápidamente cuando aumenta el tamaño del buffer que con las otras políticas analizadas, lo que muestra que la política propuesta por Bravo y Marrone[10] presenta un nivel de utilización del buffer mucho mayor. Para una mejor apreciación de lo anteriormente descrito, en la figura 11 se muestra la probabilidad de bloqueo del algoritmo propuesto, en contraste con los otros dos algoritmos para un tamaño de buffer fijo B = 710 y diferentes valores de H.
especialmente en cuanto a las estructuras complejas de correlación que se extienden a muchas escalas. Los modelos de tráfico autosimilar capturan los efectos de estas estructuras de correlación,[1] por eso son el punto de partida actual para el estudio de la Ingeniería de tráfico. En esta monografía, se recopilaron de varios trabajos conceptos importantes para iniciarse en el estudio del tráfico autosimilar de autores que han estado trabajando en estos temas hace más de una década. Se definió el modelamiento de tráfico mediante procesos autosimilares, se definió la autosimilitud determinística y estocástica y la estimación del parámetro Hurst (H). Esto es parte del camino de investigación y demostración de estos modelos, todavía hay espacio para trabajos futuros tal como lo propone el trabajo de Bravo y Marrone, como extender los análisis a conjunto de trazas de tráfico real.
6. Bibliografía [1]Alzate Monroy, M. (2000). Introducción al tráfico autosimilar en redes de comunicaciones. Ingeniería, 6(2), 6-17. Consultado de: http://revistas.udistrital.edu.co/ojs/index.php/r eving/article/view/2696 [2]P. Abry and D Veitch. Wavelet Analysis of Long-Range- Dependent Traffic. IEEE Trans. Information Theory,44(1):2-15,1998.
Figura 11. Probabilidad de Bloqueo en función de H con ancho de buffer B=710
5. Conclusiones Los modelos tradicionales de tráfico son insuficientes para explicar muchas de las características observadas en el tráfico de las redes modernas de comunicaciones,
[3] M. Alzate. Conmutación de Paquetes de Voz. X Congreso Nacional y I Andino de Telecomunicaciones, 1995. [4] M. Alzate. Modelos de Tráfico en Redes de Comunicaciones. Reporte de Investigación de la Maestría en Teleinformática de la Universidad Distrital, marzo de 1995. [5]Benoît Mandelbrot, La Geometría Fractal de la Naturaleza, Tusquets, ISBN 84-8310-549-7
[6] Koch, H. von. Une méthode géométrique élémentaire pour l'étude de certaines questions de la théorie des courbes planes. Acta Math. 30, 145-174, 1906. Consultado en: http://www.archive.org/stream/actamathemati ca11lefgoog#page/n169/mode/1up [7] W. Leland, M. Taqqu, W.Willinger and D. Wilson. On the self-similar nature of Ethernet Traffic, IEEE/ACM Trans, Networking, 2:1-15, 1994. [8]Bravo Jack, Marrone Luis, Tráfico Autosimilar. Algoritmo algebráico para asignación dinámica del búffer. INGENIUS Revista de la Facultad de Ingenieria, pag 10 de la Universidad Politécnica Salesiana del Ecuador [9] Modelado fractal de tráfico de la red de Ingeniería. Telemática Patricia Bravo García. UNIVERSIDAD CARLOS III DE MADRID ESCUELA POLITECNICA SUPERIOR, España. 2004 [10] Bravo Jack, Marrone Luis. Asignación Dinámica del Buffer para sistemas de Encolamiento bajo condiciones de Tráfico Autosimilar. Tesis de Maestría. UBA. 2006 [11]M. Irland, “Buffer Managment in a Packet Switch” IEEE Trans. Commun, vol. COM-26, no 3 marzo. 1978, pp 328-37 [12]Porras Stalin, Rivera Paulo, Bravo Jack. Análisis del algoritmo algebraico de Asignación Dinámica del buffer para sistemas de encolamiento bajo condiciones de tráfico autosimilar. Tesis de Ingeniería. Universidad Politécnica Salesiana. 2008. Cap 3. Pag 11. Natalia A Clivio Velilla obtuvo su título de Ingeniera en Telecomunicaciones de la Universidad Distrital (UDFJC) de Colombia en el 2009 y actualmente hace su maestría en Telecomunicaciones en la Universidad de Buenos Aires (UBA).
[email protected]
