Kapak Resmi

The complexity of the K-reliability in networks constrained to diameter two

Consider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 -...

Ful tanımlama

Kaydedildi:
Yazar: Canale, Eduardo (author)
Diğer Yazarlar: Cancela, Héctor (author), Robledo, Franco (author), Sartor, Pablo (author)
Materyal Türü: report
Baskı/Yayın Bilgisi: 2012
Konular:
Network reliability
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
Online Erişim:http://hdl.handle.net/20.500.12008/3465
Etiketler: Etiketle
Etiket eklenmemiş, İlk siz ekleyin!
_version_ 1868889996091457536
author Canale, Eduardo
author2 Cancela, Héctor
Robledo, Franco
Sartor, Pablo
author2_role author
author
author
author_browse Canale, Eduardo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
author_facet Canale, Eduardo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
author_role author
collection COLIBRI
dc.creator.none.fl_str_mv Canale, Eduardo
Cancela, Héctor
Robledo, Franco
Sartor, Pablo
dc.date.none.fl_str_mv 2012
2014-12-02T16:06:28Z
2014-12-02T16:06:28Z
20141202
dc.format.none.fl_str_mv 7 p.
application/pdf
dc.identifier.none.fl_str_mv CANALE, E., CANCELA, H., ROBLEDO, F., y otros. "The complexity of the K-reliability in networks constrained to diameter two". Reportes Técnicos 12-09. UR. FI – INCO, 2012.
0797-6410
http://hdl.handle.net/20.500.12008/3465
dc.language.none.fl_str_mv in
dc.publisher.none.fl_str_mv UR. FI – INCO.
dc.relation.none.fl_str_mv Reportes Técnicos 12-09
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
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
dc.title.none.fl_str_mv The complexity of the K-reliability in networks constrained to diameter two
dc.type.none.fl_str_mv Reporte técnico
info:eu-repo/semantics/report
info:eu-repo/semantics/publishedVersion
description Consider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 - p(xy) respectively. Therefore, there is an \201Coperational subnetwork\201D composed by all the sites and only those links that are operational. Computing the network reliability, i.e. the probability that a given subset K of \201Cdistinguished\201D sites are connected on the operational network yielded at t is known as the K-reliability problem and has been widely studied [1]. When additionaly requiring that the operational network be d-K-connected (i.e. that the distance between any pair of sites of K be bounded by a positive integer d) the problem is known as ddiameter- constrained K-reliability (d-DCKR). In this case the reliability is denoted by Rk(G; d). First introduced in [2], this problem has recently gained relevance because it can model situations where limits exist on the acceptable delay times to propagate traffic (like in voice applications over IP networks) or in the amount of hops that packets can undergo (peer-to-peer networks). The general version is known to belong to the NP-hard complexity class [3]. In this paper we prove
eu_rights_str_mv openAccess
format report
id anni_2d17f266cb0d4e00cea28532270028eb
identifier_str_mv CANALE, E., CANCELA, H., ROBLEDO, F., y otros. "The complexity of the K-reliability in networks constrained to diameter two". Reportes Técnicos 12-09. UR. FI – INCO, 2012.
0797-6410
instacron_str Universidad de la República
institution Universidad de la República
instname_str Universidad de la República
language_invalid_str_mv in
network_acronym_str anni
network_name_str oai-lr-anni
oai_identifier_str oai:colibri.udelar.edu.uy:20.500.12008/3465
publishDate 2012
publishDateSort 2012
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 The complexity of the K-reliability in networks constrained to diameter twoCanale, EduardoCancela, HéctorRobledo, FrancoSartor, PabloNetwork reliabilitySurvivabilityDiameter constraintsCombinatorial problemsComputational complexityFormal verificationConsider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 - p(xy) respectively. Therefore, there is an \201Coperational subnetwork\201D composed by all the sites and only those links that are operational. Computing the network reliability, i.e. the probability that a given subset K of \201Cdistinguished\201D sites are connected on the operational network yielded at t is known as the K-reliability problem and has been widely studied [1]. When additionaly requiring that the operational network be d-K-connected (i.e. that the distance between any pair of sites of K be bounded by a positive integer d) the problem is known as ddiameter- constrained K-reliability (d-DCKR). In this case the reliability is denoted by Rk(G; d). First introduced in [2], this problem has recently gained relevance because it can model situations where limits exist on the acceptable delay times to propagate traffic (like in voice applications over IP networks) or in the amount of hops that packets can undergo (peer-to-peer networks). The general version is known to belong to the NP-hard complexity class [3]. In this paper we proveUR. FI – INCO.2014-12-02T16:06:28Z2014-12-02T16:06:28Z201220141202Reporte técnicoinfo:eu-repo/semantics/reportinfo:eu-repo/semantics/publishedVersion7 p.application/pdfCANALE, E., CANCELA, H., ROBLEDO, F., y otros. "The complexity of the K-reliability in networks constrained to diameter two". Reportes Técnicos 12-09. UR. FI – INCO, 2012.0797-6410http://hdl.handle.net/20.500.12008/3465reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicainReportes Técnicos 12-09Las 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/34652026-04-14T10:16:12Z
spellingShingle The complexity of the K-reliability in networks constrained to diameter two
Canale, Eduardo
Network reliability
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
status_str publishedVersion
title The complexity of the K-reliability in networks constrained to diameter two
title_full The complexity of the K-reliability in networks constrained to diameter two
title_fullStr The complexity of the K-reliability in networks constrained to diameter two
title_full_unstemmed The complexity of the K-reliability in networks constrained to diameter two
title_short The complexity of the K-reliability in networks constrained to diameter two
title_sort The complexity of the K-reliability in networks constrained to diameter two
topic Network reliability
Survivability
Diameter constraints
Combinatorial problems
Computational complexity
Formal verification
url http://hdl.handle.net/20.500.12008/3465

Benzer Materyaller