english Icono del idioma   español Icono del idioma  

Por favor, use este identificador para citar o enlazar este ítem: https://hdl.handle.net/20.500.12008/9203 Cómo citar
Título: Diameter-constrained reliability : theory and applications
Autor: Canale, Eduardo
Robledo Amoza, Franco Rafael
Cancela, Héctor
Romero, Pablo
Sartor, Pablo
Tipo: Reporte técnico
Palabras clave: Network reliability, Diameter-constrained reliability, Monte-Carlo methods, Monma graphs
Fecha de publicación: 2016
Resumen: A classical requirement in the design of communication networks is that all entities must be connected. In a network where links may fail, the connectedness probability is called all-terminal reliability. The model is suitable for FTTH services, where link failures are unpredictable. In real scenarios, terminals must be connected by a limited number of hops. Therefore, we study the Diameter- Constrained Reliability (DCR). We are given a simple graph G = (V,E), a subset K V of terminals, a diameter d and independent failure probabilities q = 1 − p for each link. The goal is to find the probability Rd K,G that all terminals remain connected by paths composed by d hops or less. The general DCR computation is NP-Hard, and the target probability is a polynomial in p. In this chapter we study the DCR metric. It connects reliability with quality, and should be considered in the design of the physical layer in FTTH services together with connectivity requirements. We include a full discussion of the computational complexity of the DCR as a function of the number of terminals k = |K| and diameter d. Then, we find efficient DCR computation for Monma graphs, an outstanding family of topologies from robust network design. The computation suggests corollaries that enrich the subset of instances that accept efficient DCR computation. Given its NP-Hardness, several Monte Carlo-based algorithms algorithms are designed in order to find the DCR in general, inspired in two approaches: counting and interpolation. The results suggest that counting techniques outperform interpolation, and show scalability properties as well. Open problems and trends for future work are included in the conclusions.
Editorial: UR.FI-INCO
Serie o colección: Reportes Técnicos;
ISSN: 0797-6410
Citación: CANALE, Eduardo, ROBLEDO, Franco, CANCELA, Héctor, y otros. Diameter-constrained reliability : theory and applications [en línea]. Montevideo : UR.FI-INCO, 2016
Licencia: Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Aparece en las colecciones: Reportes Técnicos - Instituto de Computación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato   
TR1606.pdf109,12 kBAdobe PDFVisualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons