Fault Tolerance and Node Mapping Algorithm Hierarchical Graph HCN

Abstract

Embedding in an interconnection network maps the interconnection network G to H and analyzes the relationship between G and H. Hypercubes and toruses are widely known as interconnection networks, and various algorithms have been developed. The HCN graph is a network with a hierarchical structure to improve the network cost of hypercube. In this study, we analyze the fault tolerance and embedding properties of HCN graphs. As a result of the research, the HCN graph has the same node connectivity and degree, so it has the maximum fault tolerance property. In addition, an algorithm that can one-to-one node map the HCN structure to the torus structure was proposed. The embedding results showed that it was possible to embed the torus structure in the HCN graph at an extension rate of 3 and dilation of 1. The results of the embedding study mean that various algorithms developed in Torus can be efficiently used in the HCN structure.