Diseño y análisis de algoritmos para encaminamiento en redes de comunicación con fallos

Abstract

En el presente trabajo estudiamos el problema de encaminamiento en redes de comunicación utilizando el modelo de Aprendizaje y Predicción con Ayuda de Expertos, incorporando el supuesto de que los caminos presentes puedan fallar. Efectuamos una presentación del modelo y su adaptación al problema considerado. Posteriormente introducimos una nueva noción a la cual denominamos ambientes, la cual nos permite modelar la aparición de los fallos en los caminos (llamados también expertos). Estudiamos qué ocurre con los predictores (cualquiera sea) cuando actúan bajo estos supuestos de fallo. En particular, mostramos cotas para el valor esperado de fallos de predictores que actúan bajo los ambientes probabilista y markoviano, además de mostrar, en casos específicos donde las probabilidades de fallo se mantienen constantes en el tiempo para cada experto, que el valor esperado de fallos se obtiene explícitamente y es independiente del predictor considerado. En una siguiente etapa, estudiamos los predictores PUNIF y FTPL, y mostramos cotas para los valores esperado de fallo en los distintos ambientes, para luego dar paso a nuevos predictores definidos por nosotros, MFTPL probabilista y MFTPL markoviano, que corresponden a una generalización del predictor FTPL, pero que buscan utilizar la información de la aparición de los fallos bajo un ambiente probabilista y markoviano, respectivamente. Finalizamos esta etapa resumiendo todas las cotas encontradas para los predictores mencionados. Para finalizar el trabajo, sometemos a todos los predictores estudiados a simulaciones numéricas bajo ambientes adversarial, probabilista y markoviano, además de datos reales facilitados por el proyecto PANACEA. En estos experimentos se evidencia que el mejor predictor es MFTPL markoviano, quien generaliza el comportamiento de MFTPL probabilista en todos los ambientes.