SCD-Universite de Rennes 1 Propriétés et méthodes de calcul de la fiabilité diamètre-bornée des réseaux Diameter-constrained network reliability : properties and computation Fiabilité de réseaux Diamètre borné Complexité Monte Carlo Théorie de graphes Network reliability Diameter constraintsComplexity Monte Carlo Graph theory Systèmes de télécommunicationsFiabilitéThèses et écrits académiques Monte-Carlo, Méthode deThèses et écrits académiques Graphes, Théorie desThèses et écrits académiques Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité. Consider a communication network whose links fail independently and a set of sites named terminals that must communicate. In the classical stochastic static model the network is represented by a probabilistic graph whose edges occur with known probabilities. The classical reliability (CLR) metric is the probability that the terminals belong to a same connected component. In several contexts it makes sense to impose the stronger condition that the distance between any two terminals does not exceed a parameter d. The probability that this holds is known as the diameter-constrained reliability (DCR). It is an extension of the CLR. Both problems belong to the NP-hard complexity class; they can be solved exactly only for limited-size instances or specific network topologies. In this thesis we contribute a number of results regarding the problem of DCR computation and estimation. We study the computational complexity of particular cases parameterized by the number of terminals, nodes and the parameter d. We survey methods for exact computation and study particular topologies for which computing the DCR has polynomial complexity. We give basic results on the asymptotic behavior of the DCR when the network grows as a random graph. We discuss the impact that the diameter constraint has in the use of Monte Carlo techniques. We adapt and test a family of methods based on conditioning the sampling space using structures named d-pathsets and d-cutsets. We define a family of performability measures that generalizes the DCR, develop a Monte Carlo method for estimating it, and present numerical evidence of how these techniques perform when compared to crude Monte Carlo. Finally we introduce a technique that combines Monte Carlo simulation and polynomial interpolation for reliability metrics. Electronic Thesis or DissertationText en application/pdf1 : 1714 Kohttps://ecm.univ-rennes1.fr/nuxeo/site/esupversions/b6a9b2fd-e995-4d58-b9b2-cc00fc251159 Sartor del Giudice Pablo Enrique 1975-08-22 UY 176240055psartor@um.edu.uy 2013REN1S102 http://www.theses.fr/2013REN1S102 2013-12-18 Informatique Universite de Rennes 1thesis.degree.grantor_1 02778715X Université européenne de Bretagnethesis.degree.grantor_2 139075119 Universidad de la República (Montevideo)thesis.degree.grantor_3 02642990X Doctorat non ouiRubinoGerardointervenant_1063461196CancelaHéctorintervenant_2095112502 Mathématiques, informatique, signal, électronique et télécommunicationsecoleDoctorale_1 139007164 ddc:004 RubinoGerardoCancelaHéctorUniversite de Rennes 1Sciences et technologie, medecine, pharmacie, odontologie, droit, economie, gestion, philosophieUniversité européenne de BretagnePôle de recherche et d'enseignement supérieur de BretagneUniversidad de la República (Montevideo)Mathématiques, informatique, signal, électronique et télécommunicationsÉcole doctorale Mathématiques, informatique, signal, électronique et télécommunications (Rennes) ASCII PDF 1755545