On Uniformly Optimal Networks: A Reversal of Fortune?

Abstract

In this article, 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 Uniformly 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 20 years, the findings in the present article 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 uniformly 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.

Keywords:

• Networks
• Network Signatures
• Reliability
• Stochastic ordering
• Stochastic precedence
• Total ordering
• Uniform optimality

Mathematics Subject Clssification:

• Primary 68M10, 90B25
• Secondary 60E15, 65K10