Communication capabilities of product networks

Instead of providing separate solutions for each individual network, a unified theory is desirable to cover the study of a class of networks. Cartesian product graphs provide a common framework to investigate the performance of several individual networks. This paper addresses communication capabilities of product networks. Communication cost is generally characterized by the diameter, the average distance, the total number of paths, the traffic intensity, the saturation level, the queue length in each node, the communication delay and the network throughput. The diameter and average distance of product networks have been studied. However, no work has addressed the remaining measures for product networks. This paper presents a unified theory to evaluate the traffic intensity and the saturation level of product networks. We have theoretically computed the traffic intensity and the saturation level. Intensive simulations have been conducted to validate the analytical results and to compute the other measures for different workloads, different networks, and different network sizes. Examples of product networks that have been investigated are multidimensional meshes, multidimensional toruses, and r‐ary n‐cube networks. We have also shown that the structure (geometry) of a network is a primary factor for network high performance. For meshes and toruses, square networks present an optimal structure. While in case of an r‐ary n‐cubes, networks with higher radix outperform those with smaller radix. In particular, cross‐cubes (4‐ary n‐cube) are shown to perform better than binary cubes. This revised version was published online in June 2006 with corrections to the Cover Date.