Efficient Methods for Traffic Matrix Modeling and On-line Estimation in Large-Scale IP Networks - Pedro Casas

Resumen

En este trabajo se trata un problema de redes de datos conocido como "Network Tomography". La idea es básicamente estimar un proceso "no observable" X_t de dimensión m a partir de un proceso "medible" Y_t de dimensión r, con la restricción de que r << m. El proceso Y_t es una "agregación" del proceso X_t, donde cada elemento y(i)_t \in Y_t, i=1..r es una combinación lineal de algunos elementos x(k)_t \in X_t, k=1..m. El proceso X_t representa el volumen de tráfico dentro de una red de backbone intercambiado entre cada punto de entrada y salida de la red, mientras que el proceso Y_t representa el volumen de tráfico en los diferentes enlaces de la red que conectan las entradas y las salidas. En una red de n nodos de entrada/salida, el número de parejas entrada/salida es m = n(n-1), mientras que en gral el número de enlaces r es del orden de n. La relación entre X_t e Y_t está dada por una matriz de ruteo R, la cual básicamente indica que fracción del tráfico de la pareja k es enviada por el enlace i. La relación es lineal y es de la forma: Y_t = R X_t

La idea del trabajo es aplicar un método de estimación recursiva basado en un filtro de Kalman para estimar el valor de X_t a partir de {Y_0, Y_1, ....., Y_{t-1}, Y_t}, asumiendo un modelo muy simple para X_t, un AR(1). El método no lo desarrollé yo y viene de una de las referencias del trabajo, pero con algunas modificaciones muy chotas los resultados obtenidos son mejores. Al mismo tiempo en este trabajo se compara el desempeño de este método contra otro método de estimación no recursivo, basado en un modelo paramétrico de bajas dimensiones para la distribución espacial de X_t y utilizando un estimador de máxima verosimilitud para estimar X_t a partir de Y_t.

Ambos métodos se aplican sobre datos de redes reales, una red académica europea de gran escala y una red de backbone de Internet2. También se aplica el modelo paramétrico de bajas dimensiones a una red comercial Tier-2 francesa, y se compara el desempeño de ambos métodos contra algunos métodos aceptados en la literatura de network tomography.

Documentación

Monografía