Diameter-constrained reliability : theory and applications
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 scenari...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , , |
| Format: | report |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.12008/9203 |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1868890252455706624 |
|---|---|
| author | Canale, Eduardo |
| author2 | Robledo, Franco Cancela, Héctor Romero, Pablo Sartor, Pablo |
| author2_role | author author author author |
| author_browse | Canale, Eduardo Cancela, Héctor Robledo, Franco Romero, Pablo Sartor, Pablo |
| author_facet | Canale, Eduardo Robledo, Franco Cancela, Héctor Romero, Pablo Sartor, Pablo |
| author_role | author |
| collection | COLIBRI |
| dc.contributor.none.fl_str_mv | Canale Eduardo, Universidad de la República (Uruguay). Facultad de Ingeniería. Robledo Franco, Universidad de la República (Uruguay). Facultad de Ingeniería. Cancela Héctor, Universidad de la República (Uruguay). Facultad de Ingeniería. Romero Pablo, Universidad de la República (Uruguay). Facultad de Ingeniería. Sartor Pablo, Universidad de la República (Uruguay). Facultad de Ingeniería. |
| dc.creator.none.fl_str_mv | Canale, Eduardo Robledo, Franco Cancela, Héctor Romero, Pablo Sartor, Pablo |
| dc.date.none.fl_str_mv | 2016 2017-07-19T23:05:59Z 2017-07-19T23:05:59Z |
| dc.format.none.fl_str_mv | 4 p. aplication/pdf |
| dc.identifier.none.fl_str_mv | CANALE, Eduardo, ROBLEDO, Franco, CANCELA, Héctor, y otros. Diameter-constrained reliability : theory and applications [en línea]. Montevideo : UR.FI-INCO, 2016 0797-6410 http://hdl.handle.net/20.500.12008/9203 |
| dc.language.none.fl_str_mv | en eng |
| dc.publisher.none.fl_str_mv | UR.FI-INCO |
| dc.relation.none.fl_str_mv | Reportes Técnicos; |
| dc.rights.none.fl_str_mv | info:eu-repo/semantics/openAccess Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
| dc.source.none.fl_str_mv | reponame:COLIBRI instname:Universidad de la República instacron:Universidad de la República |
| dc.subject.none.fl_str_mv | Network reliability Diameter-constrained reliability Monte-Carlo methods Monma graphs |
| dc.title.none.fl_str_mv | Diameter-constrained reliability : theory and applications |
| dc.type.none.fl_str_mv | Reporte técnico info:eu-repo/semantics/report info:eu-repo/semantics/publishedVersion |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | report |
| id | anni_ff543ebfec2cf4c965dfdb516eae7f10 |
| identifier_str_mv | CANALE, Eduardo, ROBLEDO, Franco, CANCELA, Héctor, y otros. Diameter-constrained reliability : theory and applications [en línea]. Montevideo : UR.FI-INCO, 2016 0797-6410 |
| instacron_str | Universidad de la República |
| institution | Universidad de la República |
| instname_str | Universidad de la República |
| language | eng |
| language_invalid_str_mv | en |
| network_acronym_str | anni |
| network_name_str | oai-lr-anni |
| oai_identifier_str | oai:colibri.udelar.edu.uy:20.500.12008/9203 |
| publishDate | 2016 |
| publishDateSort | 2016 |
| publisher.none.fl_str_mv | UR.FI-INCO |
| reponame_str | COLIBRI |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
| spelling | Diameter-constrained reliability : theory and applicationsCanale, EduardoRobledo, FrancoCancela, HéctorRomero, PabloSartor, PabloNetwork reliabilityDiameter-constrained reliabilityMonte-Carlo methodsMonma graphsA 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.UR.FI-INCOCanale Eduardo, Universidad de la República (Uruguay). Facultad de Ingeniería.Robledo Franco, Universidad de la República (Uruguay). Facultad de Ingeniería.Cancela Héctor, Universidad de la República (Uruguay). Facultad de Ingeniería.Romero Pablo, Universidad de la República (Uruguay). Facultad de Ingeniería.Sartor Pablo, Universidad de la República (Uruguay). Facultad de Ingeniería.2017-07-19T23:05:59Z2017-07-19T23:05:59Z2016Reporte técnicoinfo:eu-repo/semantics/reportinfo:eu-repo/semantics/publishedVersion4 p.aplication/pdfCANALE, Eduardo, ROBLEDO, Franco, CANCELA, Héctor, y otros. Diameter-constrained reliability : theory and applications [en línea]. Montevideo : UR.FI-INCO, 20160797-6410http://hdl.handle.net/20.500.12008/9203reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicaenengReportes Técnicos;Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)info:eu-repo/semantics/openAccessLicencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)oai:colibri.udelar.edu.uy:20.500.12008/92032026-04-14T10:16:18Z |
| spellingShingle | Diameter-constrained reliability : theory and applications Canale, Eduardo Network reliability Diameter-constrained reliability Monte-Carlo methods Monma graphs |
| status_str | publishedVersion |
| title | Diameter-constrained reliability : theory and applications |
| title_full | Diameter-constrained reliability : theory and applications |
| title_fullStr | Diameter-constrained reliability : theory and applications |
| title_full_unstemmed | Diameter-constrained reliability : theory and applications |
| title_short | Diameter-constrained reliability : theory and applications |
| title_sort | Diameter-constrained reliability : theory and applications |
| topic | Network reliability Diameter-constrained reliability Monte-Carlo methods Monma graphs |
| url | http://hdl.handle.net/20.500.12008/9203 |