1 Juan Andrés Negreira 22 de febrero de 2007Comparación de técnicas de medición estadísticas aplicadas a la estimación del RTT Tratamiento Estadístico de Señales Juan Andrés Negreira 22 de febrero de 2007

2 Introducción El RTT (Round Trip Time) constituye un parámetro fundamental en las mediciones de parámetros de redes. Algunos parámetros que pueden ser estimados a partir del RTT: Retardos de propagación Retardos de encolamiento Ancho de banda disponible

3 Introducción El RTT puede ser utilizado también para ayudar al control de congestión que realiza el protocolo TCP, a nivel de capa de transporte. Para adaptar dinámicamente las tasas de transmisión interesa medir el RTT y detectar con rapidez un cambio en su valor.

4 Filtro de Kalman Se basa en un modelo en variables de estadoRequiere menos memoria Procesamiento de datos más rápido Obtiene las muestras recursivamente en el tiempo, a partir del estado anterior y de la muestra obtenida. Bases para la familia de algoritmos recursivos de mínimos cuadrados.

5 Filtro de Kalman Modelo del sistema: Donde x es el estado del sistemau es la entrada de control al sistema A y B son matrices que definen el espacio de estados w representa el ruido del proceso

6 Filtro de Kalman Modelo de medición: Siendo z las medidas realizadasH una matriz que vincula el estado del sistema con las medidas realizadas v representa el ruido de medición

7 Filtro de Kalman Las ecuaciones del filtro de Kalman pueden agruparse en dos grandes grupos, de acuerdo a cada una de las etapas que se realizan. Estimación del valor siguiente Corrección a partir del valor medido

8 Filtro de Kalman Estas etapas funcionan en forma de ciclo, a medida que se obtienen más medidas

9 Filtro de Kalman Estimación del valor siguienteSe realiza una estimación a priori del valor que tomará el estado en el instante siguiente La estimación se realiza a partir del modelo de estados y el valor del estado en el instante previo Para el instante siguiente se estima tanto el valor del estado como la covarianza del error

10 Filtro de Kalman Estimación del valor siguienteSiendo Q la covarianza de w y P se define como la covarianza del error de estimación:

11 Filtro de Kalman Corrección a partir del valor medido:Se realiza una estimación a posteriori, a partir del valor estimado a priori y del valor medido. La diferencia entre el valor medido y la estimación a priori se denomina innovación Dicha diferencia es ponderada por la ganancia, la cual es elegida de modo tal que minimice el error de estimación a posteriori.

12 Filtro de Kalman Corrección a partir del valor medidoEn donde R es la covarianza de v y K es la ganancia de Kalman

13 Filtro de Kalman adaptivoCUSUM (Cumulative Sum): Algoritmo de detección de cambios, que dispara una alarma cuando la media de la señal de entrada (que se supone de media nula) es sensiblemente distinta de cero.

14 Filtro de Kalman adaptivoDiagrama de bloques del algoritmo CUSUM

15 Filtro de Kalman adaptivoSe combinan los filtros de Kalman y CUSUM: La entrada al bloque CUSUM será la diferencia entre la estimación a posteriori y el valor medido Se toma como hipótesis que el ruido que afecta la señal es de media nula Se disparará una alarma en el bloque CUSUM cuando haya un salto en la señal considerada

16 Estimación del RTT

17 Estimación del RTT Las implementaciones actuales de TCP utilizan un filtro pasabajos para filtrar ruidos de alta frecuencia Dicha solución tiene el inconveniente de que no le permite reaccionar con velocidad ante cambios bruscos del RTT Se propone implementar la medición del RTT con el filtro de Kalman adaptivo

18 Estimación del RTT Sea t(t) el RTT medido al llegar el paquete ACK al servidor Cada nodo impone un retardo formado por El retardo de procesamiento en el nodo El retardo de encolamiento El retardo de propagación

19 Estimación del RTT El RTT queda expresado comoEn donde se puede suponer que los retardos de procesamiento y propagación contribuyen con una constante

20 Estimación del RTT Modelo de un nodo de la red:

21 Estimación del RTT Si se toma ci como la capacidad del enlace y ti como el instante en el cual el paquete llega al nodo i, se puede expresar el RTT como Donde g representa los retardos de procesamiento y propagación

22 Estimación del RTT Modelo en variables de estadoEl ruido de alta frecuencia es modelado como ruido de medición. Los saltos en el valor del RTT son modelados como una variable aleatoria v multiplicada por una secuencia de deltas de tiempo discreto

23 Estimación del RTT A partir de las hipótesis realizadas, se estimó el RTT mediante el algoritmo de Kalman adaptivo, utilizando el algoritmo CUSUM

24 El algoritmo propuesto es el siguiente:if gt < h then dt = 1 % alarma gt = 0 else dt = 0 end

25 Simulaciones realizadas

26 Kalman – CUSUM Se modificó la forma de hallar g(t) en cada iteraciónEl algoritmo tiene dos parámetros: La constante x El umbral h

27 Kalman – CUSUM

28 Kalman – CUSUM

29 Kalman - CUSUM

30 Kalman - CUSUM Para determinar en forma “inteligente” los parámetros se buscó hallarlos en función de la covarianza del ruido

31 Kalman - CUSUM x= 0.1√Re x= √Re x= 2 √ Re

32 Kalman - CUSUM Hipótesis y limitacionesSe supone que la señal estudiada está afectada con ruido de distribución normal y de media nula. Se comprobó que los saltos, para poder ser detectados con seguridad, deben tener un módulo que sea mayor o igual al doble de la covarianza del ruido

33 Kalman “clásico”

34 Filtro de Wiener Predictor lineal Acumula M cantidad de muestras

35 Wiener

36 Wiener

37 Wiener

38 Comparación de filtrosPara comparar las distintas implementaciones se estudiará: La precisión para alertar acerca de un salto en la señal El error cometido al reconstruir la señal original

39 Comparación de filtros

40 Comparación de filtros

41 Comparación de filtros

42 Pruebas sobre Internet

43 Pruebas sobre InternetSe realizó un programa en JAVA que envía paquetes “ping” a determinada página (en este caso almacena los tiempos de ida y vuelta y los guarda en un documento de texto. Dicho documento de texto fue cargado en MatLab, en donde ya estaban implementados los algoritmos

44 Pruebas sobre Internet

45 Pruebas sobre Internet

46 Pruebas sobre Internet

47 Pruebas sobre Internet

48 Conclusiones En este trabajo se presentó un filtro de Kalman adaptivo, enfocado en medir el RTT sobre un enlace. Para ello se modeló el RTT como una variable de estado de la red, estudiando las ecuaciones de dicho modelo y observando los diversos parámetros que lo afectan. Para estudiar el funcionamiento del filtro, se estudiaron los efectos de cada uno de los parámetros del mismo, analizando su comportamiento con ciertas señales de prueba simuladas.

49 Conclusiones Además se comparó su performance con otros dos algoritmos, a modo de referencia. Por un lado se implementó otra variante con el filtro de Kalman y por otro lado se propuso la utilización de un filtro de Wiener. Se pudo observar que el filtro de Kalman adaptivo fue el más performante, seguido por la otra implementación del filtro de Kalman.

50 Bibliografía K. Jacobsson, H. Hjalmarsson, N. Möller y K. Johansson, “Round trip time estimation in communication networks using adaptive Kalman filtering”. M. Lagunas, “Sistemas adaptativos”. E. Lundin, F. Gunnarsson y F. Gustaffson, “Adaptive filtering applied to an uplink load estimate in WCDMA”. A. Bifet y R. Gavaldà, “Kalman filters and adaptive windows for learning in data streams”. G. Welch y G. Bishop, “An introduction to the Kalman filter”. S. Haykin, “Adaptive filter theory”, third ed, Prentice Hall.