Optimización del ruteo en redes sobrepuestas con sistemas de decisión en base a medidas.

Abstract

El tema de esta Tesis es el diseño de sistemas de decisión recurrentes en el tiempo y basados en medidas. El objetivo del tomador de decisiones es optimizar alguna función de desempeño, minimizando el costo de las mediciones y de la incertidumbre asociada al sistema. En particular, se trabaja sobre una aplicación al ruteo en redes sobrepuestas con calidad de servicio. Las redes sobrepuestas son redes virtuales compuestas por nodos pertenecientes a diferentes redes (subyacentes), conectados entre sí por enlaces virtuales. En general, la política de ruteo entre las redes subyacentes suele no ser óptima, por lo que puede convenir establecer políticas propias. En esta aplicación se busca elegir la mejor ruta en cuanto a algún parámetro de calidad de servicio. Para decidir cuál es la mejor de las rutas posibles, es necesario medir el parámetro de calidad en cuestión. Estas mediciones habitualmente tienen costos asociados, por ejemplo, la interferencia que se genera para realizar la medida en cada ruta, que impacta en el tráfico de los usuarios. Lo ideal sería no tener que medir en todos los tiempos de decisión y poder predecir cuál es la calidad de servicio en función de las medidas anteriores. Sin embargo, el "no medir" genera una incertidumbre en la calidad de servicio y es posible que se elija una ruta que diferente de la óptima en el momento de decisión, por lo que también la decisión de "no medir" tiene un costo asociado: el de la calidad perdida por no escoger la ruta óptima. El objetivo es decidir en cada tiempo de decisión cuáles rutas medir y qué camino elegir, minimizando el costo total acumulado en el tiempo. En un primer abordaje se modela el problema como un Proceso de Decisión Markoviano, se prueban algoritmos de programación dinámica y se propone una solución innovadora : la aproximación por horizonte errante. Luego se liberan las asunciones sobre modelos y se propone una formulación para la utilización de técnicas de aprendizaje supervisado, para lo que se emplean clasificadores bien conocidos como son los árboles de decisión. El método de horizonte errante alcanza resultados casi-óptimos, que permiten reducir el costo de medida manteniendo el menor tiempo de ida y vuelta posible. El algoritmo de aprendizaje supervisado logra un rendimiento comparable, con otras propiedades como robustez frente a escenarios no-markovianos y un menor tiempo de procesamiento.