Product networks:a family of symmetric interconnection networks from a group model

Abstract

Alters and Krishnamurthy developed a formal group-theoretic modelCayley graph model, for designing and analyzing proccssor/communication interconnection networks. Using this model they have developed two classes of interconnection networks, the star graph and the pancake graph. Analysis has shown that star graphs are markedly superior to the widely used n-cube. In this paper, applying the concept of internal direct product of groups, we study a family of interconnection networks–product networks. Both the n-cube and the star graph are member of this family of networks. We study such properties of product networks as degree, diameter, connectivity, and fault-tolerance. We show that product networks are hierarchical in structure. Using this hierarchical property we have developed an optimal one-to-all broadcasting algorithm for the product graph.

Keywords:

• Interconnection networks
• one-to-all broadcasting
• parallel algorithms
• parallel machines
• product graphs
• star graphs
• time complexity

C.R. Categories:

• C.2.4
• D.3.3
• F.2.2
• G.2.2