Franco Robledo - Modelos de Confiabilidad Diámetro Acotados

Las redes de telecomunicaciones se modelan usualmente mediante grafos.
La confiabilidad de una red es una medida probabilística que indica el nivel de robustez de una red en función de las probabilidades de operación de sus componentes (links y nodos).
Por ejemplo, si los nodos son perfectos (probabilidad de operación igual a 1, i.e. no fallan), la confiabilidad de una red respecto a un conjunto de nodos distinguidos K (usualmente denominados terminales) es la probabilidad que ante la ocurrencia de fallas el subgrafo remanente tenga una componente conexa que incluya al conjunto K. (Modelos de Confiabilidad en Aristas)

Si las aristas son perfectas (probabilidad de operación igual a 1, i.e. no fallan), la confiabilidad de una red es la probabilidad que el grafo remanente se mantenga conexo ante la ocurrencia de fallas en los nodos.
(Modelos de Confiabilidad de Nodos).

En esta presentación daremos un punteo del Estado del Arte de lo que se denominamos Modelos de Confiabilidad Diámetro Acotados. Es una varianet del Modelo en Aristas donde se exige que los nodos de K estén a distancia menor o igual a un cierto parámetro d (diámetro preestablecido), en el grafo remanente.
Todo sugrafo de la red original en el cual los nodos de K se pueden comunicar por al menos un camino de menos de d arcos es un estado operativo del sistema. La suma de las confiabilidades de cada uno de estos estados operativos nos da el valor de la Diámetro Confiabilidad de la Red (DCR, Diameter Constrained Reliability).

El Cálculo de la Diámetro Confiabilidad de una Red es un problema NP-Hard. Presentaremos un estudio completo de resultados teóricos (no brindaremos demostración) vinculados al cálculo exacto de la DCR y su complejidad computacional; resultados según el tamaño de K, según el diámetro d, según las probabilidades de operación de las aristas (si son uniformes o heterogeneas), y según diferentes clases de grafos de relevancia en redes de telecomunicaciones (e.g. grafos 2-nodo-conexos, grafos outerplanares, grafos de Halin, grafos de Monma, grafos de co-rango acotado, etc).