Tiempo mínimo de difusión en redes

Abstract

El problema en estudio es el tiempo mínimo de difusión (MBT). A partir de un grafo conexo no dirigido y de un nodo origen que posee un mensaje, el objetivo es transmitir ese mensaje lo antes posible a todos los nodos restantes del grafo. La comunicación tiene lugar entre nodos vecinos de forma selectiva y cada reenvío toma un intervalo de tiempo. Históricamente, el MBT encuentra aplicaciones en servicios telefónicos, sin embargo, sirve como problema inspirador para el diseño de esquemas actuales de reenvío en sistemas de comunicación modernos como redes de entrega de contenido y redes de pares. El MBT pertenece a la clase de problemas NP-Completos. Como consecuencia, la literatura ofrece heurísticas, algoritmos de aproximación y soluciones exactas de tiempo exponencial. Así mismo, se encuentran diferentes propuestas de ingeniería inversa, donde se construyen topologías de grafos para minimizar el tiempo total de difusión. La contribución principal de este trabajo es desarrollar una heurística competitiva llamada TreeBlock. TreeBlock explota la optimalidad para el MBT en grafos de tipo árbol, y el hecho de que los grafos conexos arbitrarios acepten una descomposición en una estructura de arbol de bloques, donde los bloques de construcción son componentes biconexas. Además, como consecuencia de un trabajo conjunto con investigadores locales y externos, hemos medido el potencial de nuestra heurística comparando con una solución exacta desarrollada mediante una técnica de programación lineal entera. Estos resultados complementan el estudio sobre la eficacia de TreeBlock en relación a la correctitud de los resultados arrojados. Una comparación justa entre TreeBlock y heurísticas anteriores resalta también la efectividad de la propuesta.