Three-degree graph and design of an optimal routing algorithm

Abstract: Learning, as well as the importance of a high-performance computer is significantly emerging. In parallel computing, we denote the concept of interconnection between the single memory and multiple processors as multi-processor. In a similar context, multi-computing signifies the connection of memory-loaded processors through the communication link. The relationship between the performance of multi-computing and the processor’s linkage structure is extremely proximate. Let the connection structure of the processor be an interconnection network. The interconnection network can be modeled through a classical graph consisting of node and edge. In this regard, a multi-computing processor is expressed as a node, communication link as an edge. When categorizing the suggested interconnection network through the criteria of the number of nodes, it can be classified as follows: Mesh class type consisted of the n×k nodes (Torus, Toroidal mesh, Diagonal mesh, Honeycomb mesh), Hypercube class type with 2^n nodes (Hypercube, Folded hypercube, Twisted cube, de Breijin), and Star graph class type (Star graph, Bubblesort star, Alternating group, Macro-star, Transposition) with n! nodes. The mesh type structure is a planar graph that is widely being utilized in the domains such as VLSI circuit design and base station installing (covering) problems in a mobile communication network. Mesh class types are comparatively easier to design and could potentially be implemented in algorithmic domains in a practical manner. Therefore, it is considered as a classical measure that is extensively preferred when designing a parallel computing network system. This study suggests the novel mesh structure De3 with the degree of three and designs an optimal routing algorithm as well as a parallel route algorithm (병렬경로알고리즘) based on the diameter analysis. The address of the node in the De3 graph is expressed with n-bit binary digits, and the edge is noted with the operator %. We built the interval function (구간 함수) that computes the locational property of the corresponding nodes to derive an optimal routing path from node u to node v among the De3 graph structure. We represent the optimal routing algorithm based on the interval function, calculating and validating the diameter of the De3 graph. Furthermore, we propose the algorithm that establishes the node disjoint parallel path which addresses a non-overlap path from node u to v. The outcome of this study proposes a novel interconnection network structure that is applicable in the routing algorithm optimization by limiting the communication links to three while the number of nodes These results implicate the viable operation among the high-performance edge computing system in a cost-efficient and effective manner.

Keywords: Optimal Routing Algorithm, Three-Degree Graph, Parallel route algorithm

DOI: 10.54941/ahfe1001466

Cite this paper:

​