M. QATAWNEH707

node, and Yd is the location of destination node in the

line number. One of the previous cases will be called

recursively until the destination has been reached.

Discussions via Example s

The following examples explain the above routing cases.

For this purposed, we consider a network of a MLH(2,2)

as shown in Figure 7.

Example 1: If (Ks < Kd).

Let (1.1.4) and (2.2.5) be the address of the source and

destination nodes respectively. CASE 3 of the routing

algorithm (i.e. source layer + 1) and moveDown will use

the following path: (2.1.4) → (2.1.5) → (2.2.5) as shown

in Figure 6. From Example 1, it can be easily seen that,

in order to forward a message to the next node, the rout-

ing algorithm performs only one operation (subtraction)

to the source layer (Ks – 1) and so on until the message

reaches its destination layer. When the source and desti-

nation layers are equal, the routing algorithm forwards

the message by applying the moveDown procedure as

shown in the Figure 7.

Example 2: If (Ks > Kd).

Let (2.3.7) and (1.1.4) be the address of the source and

destination nodes respectively. CASE 2 of the routing

algorithm (i.e. source layer –1) and moveUp will use the

following path: (1.3.7) → (1.2.7) → (1.2.6) → (1.1.5) →

(1.1.4) as shown in Figure 6. From Example 2, it can be

easily seen that, in order to forward a message to the next

node, the routing algorithm performs only one operation

(addition operation) to the source layer (Ks + 1) and so on

until the message reaches its destination layer. When the

source and destination layers are equal, the routing algo-

rithm forwards the message by applying the moveUp

procedure as shown in the Figure 7.

Example 3: If (Ks = Kd).

Let (1.4.5) and (1.4.1) be the address of the source and

destination nodes respectively.

CASE 1 of the routing algorithm (i.e. Ks = Kd). From

the address of the source and destination nodes, it is clear

that they are located at the same level (level 4). Applying

the routing algorithm the moveHorizontal will be used.

Figure 7. MLH(2,2).

The move Horizontal procedure will use the following

path: (1.4.4) → (1.4.3) → (1.4.2) → (1.4.1).

5. Conclusions

This paper introduced a new interconnection topology

called Multilayer Hex-Cells. Additionally, the paper

proposed an efficient routing algorithm for MLH which

requires no detailed knowledge of the network. The new

addressing node scheme makes the proposed routing

algorithm simple and efficient in terms of that it needs a

minimum number of calculations to reach the destination

node. The proposed MLH maintains a constant network

degree regardless of the increase in the network size de-

gree which facilitates modularity in building blocks of

scalable systems. Moreover, the diameter of the proposed

MLH is less than Hex-Cell.

While the proposed topology has been analyzed ma-

thematically and discussed through examples, it can be

tested as an underlining network for many applications in

distributed systems area.

6. References

[1] A. Mokhtar, “Multi-Level Hypercube Network,” Pro-

ceedings of the 5th International Conference in Parallel

Processing Symposium, Anaheim, 30 April - 2 May 1991,

pp. 475-480.

[2] S. Huyn, O. Jae-Chul and L. Hyeong-Ok, “Multiple Re-

duced Hypercube (MRH): A New Interconnection Net-

work Reducing Both Diameter and Edge of Hypercube,”

International Journal of Grid and Distributed Computing,

Vol. 3, No. 1, 2010, pp. 19-30.

[3] Y. Y. Liu and J. G. Han, “Double-Loop Hypercube: A

New Scalable Interconnection Network for Massively

Parallel Computing. Computing,” Proceedings of the

ISECS International Colloquium on Computing, Commu-

nication, Control, and Management, Guangzhou, 3-4 Au-

gust 2008, pp. 170-174. doi:10.1109/CCCM.2008.45

[4] T. Chan and Y. Saad, “Multigrid Algorithms on the Mul-

tiprocessor,” IEEE Transactions on Computers, Vol. C-35,

No. 11, 2002, pp. 969-977.

doi:10.1109/TC.1986.1676698

[5] S. Syed, K. Rizvi, M. Elleithy and A. Riasat, “An Effi-

cient Routing Algorithm for Mesh-Hypercube (M-H)

Networks,” Proceedings of the International Conference

on Parallel and Distributed Processing Techniques and

Applications, Las Vegas, 14-17 July 2008, pp. 69-75.

[6] C. Decayeux and D. Seme, “3D Hexagonal Network:

Modeling, Topological Properties, Addressing Scheme,

and Optimal Routing Algorithm,” IEEE Transaction on

Parallel and Distributed Systems, Vol. 16, No. 9, 2005,

pp. 875-884. doi:10.1109/TPDS.2005.100

[7] K. Day and A. Al-Ayyoub, “Topological Properties of

OTIS-Networks,” IEEE Transactions on Parallel and

Copyright © 2011 SciRes. IJCNS