Minimal fault diameter for highly resilient product networks

Abstract

We present a number of results related to the fault tolerance of Cartesian product networks. We start by presenting a method for building containers (i.e., sets of node-disjoint paths) between any two nodes of a product network based on given containers for the factor networks. Then, we show that the best achievable fault diameter (i.e., diameter under maximum fault conditions), under reasonable network regularity and connectivity conditions, is equal to the fault-free diameter plus one. The concept of high fault resilience is then defined. We then prove that if each factor network is highly resilient, then their Cartesian product has minimal fault diameter. We derive from these results that Cartesian products of several popular networks are highly resilient and have minimal fault diameter equal to diameter plus one. These results spare future efforts that would be needed to individually determine the fault diameter of such networks as has been the practice with previously studied networks.