Sage Journals: Discover world-class research

Abstract

In this paper, we propose a new product network using a Cartesian product of hypercube and Kautz network, named as hyper-Kautz network. The proposed network possesses the properties of both hypercube and the Kautz network including logarithmic diameter, optimal connectivity, and simple routing algorithms.

Keywords

Hypercube-Kautz Product network

1. Introduction

Recently there has been an increasing interest in a class of interconnection networks called product networks. Product networks are obtained by applying the Cartesian product operation on basic topologies.

In this paper, we propose a new scalable product network by applying the Cartesian product operation on hypercube and Kautz network, named as hyper-Kautz network. In hyper-Kautz network, we can observe a trade-off between cost and performance.

2. Topological Structure of Hyper-Kautz

Definition 1

The hyper-Kautz network HK(n, k) is the product network H(n) ⊕ UK(k).

Each node in HK(n, k) is assigned a label (u_n−1…u₀, v_k-1…v₀) where each u_i is a binary bit and each v_j∊{0, 1, 2} and v_i ≠ v_i+1, for 0 ≤ i ≤ k−2. We refer to u_n−1 …u₀ as the hypercube-part-label and v_k−1…v₀ to as the Kautz-part-label of any node in HK(n, k).

It is easy to see that a node (u_n−1…u₀, v_k−1…v₀) has an edge incident on the following nodes referred to as Kautz-part-neighbors

\begin{aligned} (u_{n - 1} u_{n - 2} \dots u_{1} u_{0}, v_{k - 2} v_{k - 3} \dots v_{0} x) for all x \in {0, 1, 2} and x \neq v_{0} . \\ (u_{n - 1} u_{n - 2} \dots u_{1} u_{0}, x v_{k - 1} v_{k - 3} \dots v_{1}) for all x \in {0, 1, 2} and x \neq v_{k - 1} . \end{aligned}

and to the following nodes referred to as hypercube-part-neighbors

(u_{n - 1} u_{n - 2} \dots {\bar{u}}_{1} \dots u_{1} u_{0}, v_{k - 1} v_{k - 2} \dots v_{1} v_{0}) for all i, 0 \leq i \leq n - 1.

Hyper-Kautz network has properties of Hamiltonian cycle, low mean internodal distance, and maximally fault tolerant, etc.

3. Conclusion

In this paper, we proposed the hyper-Kautz interconnection topology, which is the Cartesian product of hypercube and Kautz network. The hyper-Kautz network is an improvement over the hypercube and the Kautz network because hyper-Kautz network inherits properties of both the hypercube and the Kautz network.