Network utility problem and easy reliability polynomials

Abstract : We model a communication system by a network, were the terminals are perfect but links may fail randomly, with identical probability q = 1 - p. This defines a partial random network. The all-terminal reliability R(p) is the probability that this random graph is connected, and it is a polynomial in p. Finding the reliability polynomial can be reduced to a hard counting problem. The contributions of this paper are two-fold. First, we fully determine all subgraphs that accept an easy counting technique, and as a consequence, the reliability polynomial is directly retrieved. More specifically, we define the “level of difficulty” of a graph, and find the reliability polynomials of all graphs with non-positive level of difficulty. The second contribution is to propose a fundamental problem from survivable network design, called the Network Utility Problem. The goal is to maximize the network utility, under a minimum edge-connectivity requirement. The network utility is defined as the opposite of the level of difficulty minus one, and it is never greater than unity. The upper-bound is achieved only in trees and cycles. We prove that Harary graphs achieve the optimal value for the Network Utility Problem. Finally, we present open problems that provide hints for future work.
Type de document :
Communication dans un congrès
RNDM 2016 - 8th International Workshop on Resilient Networks Design and Modeling, Sep 2016, Halmstad, Sweden. 2016, 〈10.1109/RNDM.2016.7608271〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01423584
Contributeur : Yassine Hadjadj Aoul <>
Soumis le : vendredi 30 décembre 2016 - 13:16:29
Dernière modification le : mercredi 16 mai 2018 - 11:23:18

Identifiants

Citation

Eduardo Canale, Pablo Romero, Gerardo Rubino, Warnes Xavier. Network utility problem and easy reliability polynomials. RNDM 2016 - 8th International Workshop on Resilient Networks Design and Modeling, Sep 2016, Halmstad, Sweden. 2016, 〈10.1109/RNDM.2016.7608271〉. 〈hal-01423584〉

Partager

Métriques

Consultations de la notice

334