A New Unicast Routing Algorithm for Hyper Hexa-Cell Interconnection Networks

A New Unicast Routing Algorithm for Hyper Hexa-Cell Interconnection Networks

Jehad Ahmed Al-Sadi (Arab Open University, ITC Department, Amman, Jordan)
Copyright: © 2017 |Pages: 13
DOI: 10.4018/IJISSC.2017070104

Abstract

The Hyper Hexa-Cell topology; HHC for short; is a new interconnection network topology that has many attractive topological properties compared to other traditional topologies. There have been a number of studies in the literature on the HHC to explore the promising topological properties of this topology. Furthermore, other studies extend this topology by combining it with OTIS technology to produce a new version called OHHC. We have found that there is a lake of presenting any point to point routing algorithm for the HHC, although there were some efforts on building routing algorithms for the OHHC. To cover this shortage, this paper introduces a new unicast routing algorithm for the HHC. The new routing algorithm for the HHC uses store-and-forward technique which allows a message to be transmitted through a path from the source node to the destination node. In addition to presenting the routing algorithm, we present an example to explore the algorithm steps and also an enhancement on the routing algorithm to apply adaptively on the routing based on parameterized criteria. Finally, we present a theoretical theorem to prove that the algorithm routes any message from any source to any destination via an optimal path.
Article Preview

Introduction

Recently, there is a huge research effort in the field of parallel computing to solve different real life problems due to the massive use of computing power in all areas of our life. Parallel computing utilizes the power of multiple processing to solve a problem by distributing the problem into independent processors, so each processor executes a specific unit of the problem simultaneously with other processors. Interconnection network is the backbone topology in which the processors are structured. There are many interconnection network topologies, such as Hypercube, Star, Ring, Mesh, etc (Grama, Gupta, Karypis, & Kumar, 2003; Patterson & Hennessy, 2009; Wang & Taher & Heuvel, 2015; Benrais & Baha, 2016).

The binary Hypercube (or the n-cube for short) is considered as one of the most well-known interconnection networks for multi-processors due to its attractive topological properties; e.g. low diameter regular structure, and its capability to exploit communication locality that is required for many parallel mathematical problems’ solving and applications. Many experimental and commercial systems have been use the n-cube interconnection topology including the NCUBE-2, iPSC/2, Cosmic Cube, and SGI Origin 2000 multiprocessor (Grama, et al., 2003).

Hypercube is a well-known interconnection topology that is widely used in parallel computations, routing algorithms, and as a basic structure in many hybrid interconnection networks. A d-dimensional hypercube; n-cube; consists of 2𝑑 nodes (Saad & Schultz, 1988), where each node can be addressed using d bits label. Each node is connected to its neighbors’ nodes if and only if their labels are differing from it in only one bit position. A d-dimensional hypercube consists of two hypercubes of dimension (d-1). The one-dimensional hypercube has two only connected nodes. The two-dimensional hypercube can be constructed by connecting two one-dimensional hypercubes.

The continuous improvements and advancements of the technology motivate researchers to produce new interconnection topologies. Researches started to utilize such technology by structuring new interconnection networks based on clustering and combining a set on interconnection topologies (Zhao, Xiao, & Parhami, 2009; Al-Sadi, 2015).

Mahafzah, Sleit, Hamad, & Abu-Khabeer (2012) introduced a new structured interconnection network under the name of HHC (Hyper Hexa-Cell) based on the topology of hypercube topology structure; HHC has attractive properties such as low diameter, minimum degree, and good scalability in the topology size. HHC is structured by initializing a hexa-cell graph, within the hexa-cell graph three additional edges are added in a way that two edges are used to construct two opposite triangles and the third edge is used to connect the top nodes of the two opposite triangles, A d-dimensional HHC construction based on a hypercube topology, where each node of a hypercube of dimension d-1 replaced by one dimensional HHC graph. Therefore, each one dimensional HHC represents a subgroup in a d-dimensional HHC graph.

The main purpose of a routing algorithm is to rout a message from one node to another within a specific interconnection network topology. A routing algorithm selects the best path to rout from source to destination, and has great impact on network performance.

A More flexible routing algorithm will lead to a better performance. To be more specific, it will lead to an increasing in the network throughput and also a decreasing in the message latency for routing a message from any source node to any destination node via an optimal selected bath (Al-Sadi, 2015).

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018): 3 Released, 1 Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing