The hierarchical Petersen network: a new interconnection network with fixed degree.

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(<italic>n</italic>) is 5, and HPN(<italic>n</italic>) has 10n<inline-graphic></inline-graphic> nodes and 2.5×10n<inline-graphic></inline-graphic> edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(<italic>n</italic>) are 3log10N-1<inline-graphic></inline-graphic> and 15log10N-1<inline-graphic></inline-graphic>, respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(<italic>n</italic>) can be embedded into FPk<inline-graphic></inline-graphic> with expansion 1, dilation 2<italic>k</italic> and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require O(N)<inline-graphic></inline-graphic> and the degree of the graph requires <italic>O</italic>(<italic>N</italic>). However, HPN(<italic>n</italic>) requires <italic>O</italic>(1) for the degree and O(log10N)<inline-graphic></inline-graphic> for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph. [ABSTRACT FROM AUTHOR]