Network Reliability: A Fresh Look at Some Basic Questions

In this paper, the general problem of comparing the performance of two communication networks is examined. The standard approach, using stochastic ordering as a metric, is reviewed, as are the mixed results on the existence of uniformly optimal networks (UONs) which have emerged from this approach. While UONs have been shown to exist for certain classes of networks, it has also been shown that no UON network exists for other classes. Results to date beg the question: Is the problem of identifying a Universally Optimal Network (UON) of a given size dead or alive? We reframe the investigation into UONs in terms of network signatures and the alternative metric of stochastic precedence. While the endeavor has been dead, or at least dormant, for some twenty years, the findings in
the present paper suggest that the question above is by no means settled.
Specifically, we examine a class of networks of a particular size for which it was shown that no individual network was universally optimal relative to the standard metric (the uniform ordering of reliability polynomials), and we show, using the aforementioned alternative metric, that this class is totally ordered and that a uniformly optimal network exists after all. Optimality with respect to "performance per unit cost" type metrics is also discussed.