Reliable network topologies in a model with node failures.
Item
-
Title
-
Reliable network topologies in a model with node failures.
-
Identifier
-
AAI9009777
-
identifier
-
9009777
-
Creator
-
Salizkiy, Olga.
-
Contributor
-
Adviser: Gary Bloom
-
Date
-
1989
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Mathematics
-
Abstract
-
In the study of network reliability, one is interested in the effects of node and line failures on the communication capabilities of a network. The vulnerability of a network may be gauged by whether or not the network remains connected after such failures. Herein we consider a probabilistic model with node failures. In particular, we wish to study network topologies which are optimal in their invulnerability to disconnection in this model.;Let a network with n nodes and e lines be represented by a graph G with n vertices and e edges. Assume that lines never fail. If all the nodes in the network have an equal and independent probability of failure q and if {dollar}\ell\sb{lcub}\rm i{rcub}{dollar} is the number of disconnecting node sets of size i, then the probability that the network represented by G is disconnected due to node failure is given by the unreliability polynomial{dollar}{dollar}\rm P\sb{lcub}n{rcub}(G,q)=\sum\limits\sbsp{lcub}i=1{rcub}{lcub}n{rcub}\ell\sb{lcub}i{rcub}q\sp{lcub}i{rcub}(1-q)\sp{lcub}n-i{rcub}.{dollar}{dollar}.;Of interest are network topologies with a fixed cost of n nodes and e lines which minimize the unreliability polynomial. It has been shown that such optimal networks may not exist for certain n and e since different topologies may be optimal for different q. However, for a fixed q, n, and e, an optimal topology can always be found. To that end, we examine the cases with large q.;For sufficiently large q, (n,e)-graphs which minimize the term {dollar}\rm\ell{lcub}n-3{rcub}{lcub}q{rcub}\sp{lcub}n-3{rcub}(1-q)\sp3{dollar} minimize the unreliability polynomial. Such graphs have the maximum number of induced connected subgraphs on 3 vertices. The number of such subgraphs is given by{dollar}{dollar}\rm\sum\limits\sbsp{lcub}i=1{rcub}{lcub}n{rcub} \left({lcub}d\sb{lcub}i{rcub}\atop2{rcub}\right)-2\tau(G){dollar}{dollar}where {dollar}\tau{dollar} is the number of triangles in G and d{dollar}\sb{lcub}\rm i{rcub}{dollar} is the degree of vertex v{dollar}\sb{lcub}\rm i{rcub}{dollar}. Graphs which maximize the above expression for a fixed n and e are called 3-optimal.;There are few known results on 3-optimal graphs. Boesch, Li, Stivaros, and Suffel have found all 3-optimal graphs with n vertices and n {dollar}-{dollar} 1 {dollar}\leq{dollar} e {dollar}\leq{dollar} 2n {dollar}-{dollar} 4 and n(n {dollar}-{dollar} 1)/2 {dollar}-{dollar} 2n {dollar}\leq{dollar} e {dollar}\leq{dollar} n(n {dollar}-{dollar} 1)/2 edges. We have found all 3-optimal graphs for the cases 2n {dollar}-{dollar} 3 {dollar}\leq{dollar} e {dollar}\leq{dollar} 3n {dollar}-{dollar} 10 and, along with Bloom, Stivaros, and Suffel, we have shown that K{dollar}\sb{lcub}\rm n1,n2{rcub}{dollar} is 3-optimal.;We have also found several properties of 3-optimal graphs which make them useful topologies for networks. For example, we have shown that 3-optimal graphs have diameter {dollar}\leq{dollar}3. We have also shown that the distance from a node with maximum degree in the network to any other node is no more than 2. Several other results pertaining to circuits and cutpoints have been proved.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
