Optimization Problem Of Two-terminal Networks Reliability Under Expectation Path Constraint

Network reliability has always been an important parameter to index the network performance and its importance reflects in network design,maintenance strategy and so on.The definition of expected-path length based on the reliability indicates the average s-t path length with the probability of communication in the network.It is meaningful to analyze the important communication part in the network based on the expected-path length for network design and evaluation.The main conclusions of this paper are as follows:1.As for unreliable-edge model,a two-terminal network reliability model with the expected-path length constraint is proposed.We give definitions of the original graph,the positive and negative s-t paths,the maximal graph,the redundant effective sub-graph and the optimal sub-graph.The optimization problem of finding the maximum reliability sub-graph with expected-path constraint is transformed into the problem of finding the maximal graph.By the rules of deleting redundant efficient sub-graphs,the optimal sub-graph algorithm is designed.2.As for unreliable-vertex model,we give the network a diameter constraint and give the definition of redundant vertexes.The properties of the expected-path function with diameter constraint are discussed.We design an algorithm to transform expected-path constraint into diameter constraint by using the properties of the function.