Advanced
Application of the Hamiltonian circuit Latin square to a Par allel Routing Algorithm on Gener alized Recur sive Cir culant Networks
Application of the Hamiltonian circuit Latin square to a Par allel Routing Algorithm on Gener alized Recur sive Cir culant Networks
Journal of Korea Multimedia Society. 2015. Sep, 18(9): 1083-1090
Copyright © 2015, Korea Multimedia Society
  • Received : April 30, 2015
  • Accepted : July 28, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Dongmin Choi
Division of Undeclared Majors, Chosun University
Ilyong Chung
Dept. of Computer Engineering, Chosun University
iyc@chosun.ac.kr

Abstract
A generalized recursive circulant network(GR) is widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on this network, that is a key to the performance of this network. We would like to transmit maximum number of packets from a source node to a destination node simultaneously along paths on this network, where the ith packet traverses along the ith path. In order for all packets to arrive at the destination node securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian Circuit Latin Square(HCLS), a special class of (n x n) matrices, we present O(n 2 ) parallel routing algorithm on generalized recursive circulant networks.
Keywords
1. INTRODUCTION
A generalized recursive circulant network(GR) [1] is widely used in the design and implementation of local area networks and parallel processing architectures.
This network denoted by GR ( mh , m h-1 ,..., m 1 ) has
PPT Slide
Lager Image
vertices where mi ≥ 2 for 1 ≤ i h . Index I is a dimension of the labeling system while mi is the base of dimension i . Each vertex in the network can be expressed as an h -tuple ( xh , x h-1 ,..., x 1 ) with 0 ≤ xi mi - 1 for i = 1,2,..., h . The number of edges at a node is
PPT Slide
Lager Image
, if mi > 2, then ki = 2, else ki = 1.
The routing of message is thus a key to performance of networks. We look for algorithms that are capable of handling, multiple data items simultaneously transmitted from a starting node to a destination node. There are a few algorithms on the hypercube-like network that allow us to locate n disjoint paths such as the Hamiltonian path Algorithm [2] , the Rotation Algorithm using Tree Structure [3] , the Disjoint Path Algorithm [3] , and the Routing Algorithms [4] . Node-disjoint paths can be categorized into three classes-one-to-one, one-to- many, and many-to-many. The first class considers the disjoint paths from a source node to a destination node, the second from a source node to k destination nodes and the third from k source nodes to k destination nodes. One-to-one disjoint paths were constructed on several networks such as hypercubes [5] , k-ary n-cubes [6] and star graphs [7] . One-to-many disjoint paths were designed on hypercubes [8 , 9] and star graphs [8] . For the generation of many-to-many disjoint paths some work has been done [10 , 11] .
In this paper, we propose an algebraic approach to routing of messages on GR ( mh , m h-1 ,..., m 1 ). As described above, maximum number of packets are simultaneously transmitted from a starting node to a destination node, where the ith packet is sent along the ith path. In order for all packets to arrive at a destination node quickly and securely, the ith path must be node-disjoint from all other paths. To accomplish this, we employ the operations of nodes presented in Cayley Graph [12] and the special matrix called as Hamiltonian Circuit Latin Square(HCLS) [5] , which was used to find a set of node-disjoint paths on hypercube network [5] , circulant networks [13] and recursive cube of rings networks [14] .
2. DESIGN OF THE SHORTEST PATH
Let A and B be any two nodes on GR ( mh , m h-1 ,..., m 1 ). The paper’s objective is to find algorithms that will facilitate the transmission of data from a source node to a desired node on generalized recursive circulant networks. In order for the data to traverse to a desired node, it must cross, successively, intermediate nodes along a path.
Definition 1. GR ( mh , m h-1 ,..., m 1 ) is defined as follows:
Each vertex in the network can be expressed as an h -tuple ( xh , x h-1 ,..., x 1 ) with 0 ≤ xi mi - 1 for i = 1,2,..., h and the edge set E is {( v , w )| w = ( xh ,..., xi ,..., x 1 ), + i ± = ( xh ,..., xi ± 1,..., x 1 ), where v = ( xh ,..., xi ,..., x 1 ), if xi + 1 = m , then xi = 0, x i+1 = xi + 1 and if xi - 1 = -1, then xi = mi - 1, x i+1 = x i+1 - 1.
The number of edges at a node is
PPT Slide
Lager Image
, if mi > 2, then ki = 2, else ki = 1. It means that if mi > 2, then ( mh ,..., mi ,..., m 1 ) has two edges at dimension i - ( mh ,..., m i+1 ,..., m 1 ) and ( mh ,..., mi - 1,..., m 1 ), else it has one edge - ( mh ,..., m i+1 ,..., m 1 ). When the operations occur at the leftmost dimension mh , since m h+1 is invisible, addition and subtraction to m h+1 are neglected. This means that vertices (0, x h-1 ,..., x 1 ) and mh - 1, x h-1 ,..., x 1 ) are adjacent (see Fig. 1 ).
PPT Slide
Lager Image
GR (2,4,3).
Researches on generalized recursive circulant networks(GR) are actively performed in graphic-theoretical areas such as embedding and faulttolerance. As mentioned earlier, a node on Cayley Graph can traverse to another node by performing a certain operation. We now employ these operations to GR.
Definition 2. The Routing function R for i ± is as follows:
R i± ( A ) = A + i ± (mod n ), where A is an address of a node
Node A is physically connected to k neighboring nodes and these paths are node-disjoint. Data is transmitted from a source node along the ith path. The path above is selected by the routing function described in Definition 2. To do this, the relative address of two nodes can be obtained below.
Definition 3. Let A and B be ( ah , a h-1 ,..., ai ,..., a 1 ) and ( bh , b h-1 ,..., ai ,..., b 1 ), respectively. The relative address r of nodes A and B is computed as the difference between each dimension of two nodes.
  • r= (bh-ah,bh-1-ah-1,...,bi- ,ai,...,b1-a1)
Let A and B be (1,2,1) and (3,2,2) on GR(4, 5, 3). The relative address r is (2,0,1), which can be described as a sequence S of operations <3 + ,3 + ,1 + > since r 3 = 2 and r 1 = 1. Also, x + is interchangeable to x and S is <3,3,1>.
Definition 4. Let T(A,S) be a logical transmission path starting form node A to a destination node, where r is a multiset and a sequence of operations, via which data can reach at a destination node. T(A,S) is determined by the order of elements in S .
Given node A and multiset S on GR(4,5,3) , we would like to transmit to a destination node via intermediate nodes. Let node A and set S be (1,2,1) and <3,3,1>, respectively. Operations in S are applied to the routing function sequentially and then the traversal of data is (1, 2, 1) → (2, 2, 1) → (3, 2, 1) → (3, 2, 2).
Since the paper’s objective is to find an algorithm that will facilitate the secure transmission of data from a starting node to a destination node, those operations should be appropriate for this objective. Given S, a size of this sequence must be minimized since a routing distance is equal to a size of a sequence.
For example, supposed that S = < 1 - ,1,1,1,3,3,1 - > on GR(4,5,3) . then S can be minimized to < 1 - ,2,3,3,1 - >since x 1 + 1 + 1 + 1 (mod 3) = x 1 and a carry 1 is added to x 2 .
PPT Slide
Lager Image
The operations applied at the first step and the last step.
3. Application of the Hamiltonian Circuit Latin Square to the Parallel Routing Algorithm on Generalized Recursive Circulant Networks
The k packets are transmitted from a source node to a destination node on GR ( mh , m h-1 ,..., m 1 ). In this section, we would like to construct a set of k node-disjoint paths in order to transmit these packets safely. First, k packets residing at a node are sent to its neighboring nodes along a set of disjoint paths. These paths are generated by employing k different operations at the beginning step and by performing k different operations at the last step in order to arrive at a destination node. The figure below illustrates the operations applied to generate k paths from a source node to a destination node.
The ith packet is transmitted along the ith path, the first intermediate node of which is obtained from applying operation si at a starting node and the last intermediate node transmits this packet to a destination node by applying operation pi . In some cases, si and pi can be the same.
Definition 5. Let Os be a set of operations occurring at a starting node when k packets are transmitted simultaneously and Let Od be a set of operations occurring at the last k intermediate nodes in order for k packets to arrive at a destination node. These sets are defined as follows:
  • Os= {s1,s2,...,sk-1,sk}
  • Od= {p1,p2,...,pk-1,pk}
  • Os=Od
We now apply the HCLS(Hamiltonian Circuit Latin Square) to find a set of m shortest and node-disjoint paths. A latin square is a square ma-trix with m 2 entries of m different elements, none of the elements occurring twice within any row or column of the matrix. The integer m is called the order of latin square. The next definition describes the HCLS.
Definition 6. The HCLS M 1 is constructed as follows: Given distinct m points a 0 , a 1 ,..., a m-2 , a m-1 , a , a Hamiltonian circuit , ai ,→ aj →…→ ak →, ai , is randomly selected. On the circuit each row of M 1 can be obtained from the Hamiltonian path. starting at any position ak (0 ≤ k m - 1), under the condition that no two rows begin at the same position. If a Hamiltonian path is , ai ,→ aj →…→ ak , then the row obtained from it is [, ai , aj ,... ak ].
From the HCLS given in Definition 6, the MHCM(Modified Hamiltonian Circuit Matrix) is constructed below.
Definition 7. Given the HCLS M 1 = ( aij ), the MHCM M 2 is constructed as follows: M 2 = ( Aij ), Aij = ( a i,0 , a i,1 ,..., a i,j-1 , ai,j ), aij Zm ,0 ≤ i m - 1,0 ≤ j m - 2.
The following example will provide a better understanding of Definition 6 & 7.
Example 1. If the Hamiltonian path is 2 → 3 → 1 → 4, then the HCLS M 1 and the MHCM M 2 are constructed as follows.
PPT Slide
Lager Image
Definition 8. Call M 3 the MGNDP(Matrix for Generating Node-Disjoint Paths). No two entries of this matrix are the same. It satisfies the following conditions.
  • M3= (Ai,j),Ai,j⊂ {Zm∪ {s}},
0 ≤ i m - 1,0 ≤ j m - 2 s means “stay at the current node”.
  • (1) |Ai,j| =j+ 1
  • (2)Ai,j≠Ak,l,ifi≠k
  • (3)Ai,j⊂Ai,j+1
  • (4)Ai,j+1=Ai,j∪{s}, ifs∈Ai,j
Referring to [5] , the MHCM satisfies the conditions of the MGNDP(Matrix for Generating Node-Disjoint Paths), which constructs a set of node-disjoint paths on the hypercube network. Since The HCLS belongs to the latin square, a set of elements in the first column is the same as that of the last column. On generalized recursive circulant networks, an element in the HCLS is represented as an operation. Also, Os and Od in Definition 5 are described as all the elements in the first column and all the elements in the last column, respectively. We, intuitively, realize that a set of m node-disjoint paths is generated if the number of distinct sequences of operations for arriving at an arbitrary node in a short time is m ( m k ). The remaining operations excluding these distinct operations from Os and Od , should be performed.
Example 2. Let A and B be (1,2,1) and (3,2,2) on GR (4,5,3). According to Definition 4, sequence S is computed as < 3, 3, 1 > and a set of node-disjoint paths is generated as follows. A set of distinct operations in S is < 1, 3 >. Using these operations, (2 × 2) HCLS can be obtained from Definition 6.
PPT Slide
Lager Image
Operations in the ith row of the HCLS generated above are performed for traversal of the ith packet and the remaining operation is also executed at the point except the first and the last points. In order to assure that these paths are node-disjoint, the remaining operation should be executed at the same time. In this example, the running point of the remaining operation is the second. Physical transmission paths from node A to node B are described below.
  • Path 1 : T(A,< 1, 3, 3 >) : A → (1, 2, 2) → (2, 2, 2) → B
  • Path 2 : T(A,< 3, 3, 1 >) : A → (2, 2, 1) → (3, 2, 1) → B
From Definitions 1 and 6, Os and Od are obtained, that is, Os = Od = {1,1 - ,2,2 - ,3,3 - }. Excluding the operations 1 and 3, which are performed in the first and the last steps, from Os and Od , Os and Od become {1 - ,2,2 - ,3}. Recall that we deal with design of six node-disjoint paths, out of which two node-disjoint paths are now constructed. Examining Definition 2, when a packet traverses in a positive direction on the ith dimension and then traverses in a reverse direction on the same dimension, a packet comes back to its original position. This idea is applied to generation of disjoint paths. If { i , i - } exists as a subset of Os and Od , these operations are executed at the first and the last steps and the operations obtained from design of the shortest distance at the middle steps. Path 3 and Path 4 are constructed below.
  • Path 3 :T(A< 2,1,3,3,2->) : A → (1, 3, 1) → (1, 3, 2) → (2, 3, 2) → (3, 3, 2) → B
  • Path 4 :T(A< 2-,1,3,3,2->) : A → (1, 1, 1) → (1, 1, 2) → (2, 1, 2) → (3, 1, 2) → B
Excluding { 2,2 - } from Os and Od , Os and Od become { 1 - ,3 - }. While operations working at the first and the last steps are not the same, operations performing at the remaining steps are the same. As described earlier for Path 3 and Path 4, a packet traverses in a positive direction on the ith dimension and then traverses in a reverse direction on the same dimension. Likewise a packet traverses twice in the same direction on the ith dimension and then traverses twice in the reverse direction on the same dimension, and then this packet comes back to its original position. A sequence of operations for a path is now obtained. Firstly, two operations traversed in the same direction are chosen for the first and the last steps. Secondly, two operations in reverse direction and the operations for the shortest distance would be executed at the middle steps. However, these operations must be minimized in order to be a shortest path and then the minimal operations are executed. Paths 5 and 6 are generated by handling cases of {1 - } and {3 - }, respectively.
  • Path 5 :
  • T(A,< 1-,1,1,1,3,3,1->) =T(A,< 1-,2,3,3,1->): A → (1, 2, 0) → (1, 3, 0) → (2, 3, 0) → (3, 3, 0) → B
  • Path 6 :
  • T(A,< 3-,3,3,3,3,1,3->) =T(A,< 3-,1,3,- >): : A → (0, 2, 1) → (0, 2, 2) → B
The process to find a set of node-disjoint paths is described above. We now propose a parallel routing algorithm that generates a set of node-disjoint paths on generalized recursive circulant networks. In this paper, we will use the term “distance” between two nodes to refer to the number of routing steps(also called hopcounts) needed to send a message from one node to another.
  • GR_Routing_Algorithm
  • A ← an address of a starting node A
  • B ← an address of a destination node B
  • Os← a set of operations occurring at a starting node A
  • Od← a set of operations requisite for reaching to a destination node B
begin
(1) Compute the relative address r of nodes A and B
(2) Using the relative address r, a sequence S of operations to arrive at node B in a short time are produced.
(3) In order to design a set of node-disjoint paths, find a sequence S 1 of distinct elements in S. A set of | S 1 | shortest and node-disjoint paths are generated. Each path of length is | S |,
(3-1) Using S 1 , (n × n) HCLS is constructed, where n = | S 1 |.
(3-2) Operations in the ith row of the HCLS are performed for traversal of the ith packet and the remaining operations in S should be executed at the point except the first and the last points.
(3-3) Os Os S 1 and Od Od S 1
(4) Construct two node-disjoint paths, each path has length | S | + 2.
(4-1) If Os = ϕ , the process is finished.
(4-2) If a set of { i , i - } is found in Os , then these operations are performed at the first and the last steps, and the operations in S at the middle steps, otherwise go to (5).
(4-3) Os Os - { i , i - }, Od Od - { i , i - } and go to (4-1).
(5) Generate the remaining paths.
(5-1) If Os = ϕ , the process is finished.
(5-2) For i Os ( mi > 2), produce S 2 of mini-mum number of operations by reducing the size of S ∪ { i - , i - }, S 2 = {i, min(S ∪ { i - , i - }), i}
(5-3) Operation i is performed at the first and the last steps and the remaining operations of S 2 are executed at the middle steps.
(5-4) Os Os - { i }, Od Od - { i } and go to (5-1).
end.
GR_Routing_Algorithm is thus fairly straightforward. The time involved in performing Steps (1), (2) and (4) is small compared to the remaining steps. The first, second and fourth steps of this algorithm does not, therefore, contribute to an objectionable overhead.
Theorem 1. The construction of a set of k node-disjoint paths can be performed in O(n2) time.
Proof: Applying the Algorithm above to generate k node-disjoint paths. Important steps for determining time complexity requisite for the Algorithm are two things. One is to design the HCLS, which requires O(n) . The other is to run Step (5) of GR_Routing_Algorithm . In Step (5), in order to run i in Os at the first and the last steps in transmission, a sequence of operations is de-termined to S ∪{ i - , i - }, and is reduced. Since the reduction process requires O(n) time and the number of elements in Os is less than n, Step (5) can be computed in O(n2) . Therefore, a set of k node-disjoint paths can be created in O(n2) time.
The paper’s objective is to find a set of k node-disjoint paths between two nodes. The major topological characteristics of the generalized recursive circulant network is considered and the property of k paths obtained from the Algorithm is proven below.
Theorem 2. The k transmission paths produced by GR_Routing_Algorithm are node-disjoint.
Proof: The k packets residing at node A are now transmitted at time t 0 . These packets reach to its k neighboring nodes at time t 1 . Then, each packet traverses to a neighboring node along a shortest path. Suppose that two packets arrive at the same node except a destination node during transmission. In order for this case to occur, the following condition should be satisfied. Let Si and Sj be two sequences of operations for sending two packets from a starting node to two arbitrary nodes at time tij , where tij means that one packet arrives at time ti and the other arrives at time tj . Then, Si and Sj should be the same. In other words, if these sequences do not appear, a set of node-disjoint paths can be constructed. According to the Algorithm described above, three classes of paths are generated on this network. We now consider three cases.
Case 1: Let S 1i and S 1j be two sequences of operations obtained from design of the shortest distance. Then S 1i and S 1j must not be the same due to the properties of the MGNDP.
Case 2: Let S 2i and S 2j be two sequences of operations acquired by running Algorithm-(4). Then S 2i and S 2j must not be the same because the first elements of S 2i and S 2j are Sk and
PPT Slide
Lager Image
, respectively and the rests of them are the same. In order for paths generated through case 1 and case 2 to be node-disjoint, we prove that S 1i and S 2j must not be the same. Considering the first element Sk of S 2j , it is not an element of S 1j . Therefore, these sequences are different all the times.
Case 3: Let S 3i and S 3j be two sequences of operations generated by performing Algorithm-(5), and T be a sequence of operations, which creates a shortest path from a source node to a desired node. Then, the first elements of S 3i and S 3j do not belong to T, S 3i does not contain the first element of S 3j , and S 3j does not contain the first element of S 3i . So, S 3i and S 3j should not be the same.
To prove that the paths created by all the cases are node-disjoint, S 3i and S 2j must not be the same. The method of proof is the same as the case 2. Looking into the first element of S 2j , the element is not a part of S 3i . Therefore, these sequences are different all the time.
4. CONCLUSION
In this paper, we present the algorithm that generates a set of k node-disjoint paths on GR ( mh , m h-1 ,..., m 1 ) employing the Hamiltonian Circuit Latin Square(HCLS). Important steps for determining time complexity requisite for the algorithm are two things. One is to design the HCLS, which needs O(n) . The other is to execute Step (5) of GR_Routing_Algorithm , which requires O(n2) . Therefore, we can create O(n2) parallel routing algorithm for constructing a set of k node-disjoint paths.
BIO
Dongmin Choi
He received his B.E. degree from the Kyunghee University in 2003 and M.S. and Ph.D. degrees in computer Science from Chosun University in 2007 and 2011, respectively. He is working as a researcher in Computer Science at Chosun University. His research interests are in information security, sensor network systems, mobile ad-hoc systems, smart grid home network systems and internet ethics.
Ilyong Chung
He received the B.E. degree from Hanyang University, Seoul, Korea, in 1983 and the M.S. and Ph.D. degrees in Computer Science from City University of New York, in 1987 and 1991, respectively. From 1991 to 1994, he was a senior technical staff of Electronic and Telecommunication Research Institute (ETRI), Dajeon, Korea. Since 1994, he has been a Professor in Department of Computer Science, Gwangju, Korea. His research interests are in computer networking, security systems and coding theory.
References
Tang S. , Wang Y. , Li C. 2012 “Generalized Recursive Circulant Graphs,” IEEE Transactions on Parallel Distributed Systems 23 (1) 87 - 93    DOI : 10.1109/TPDS.2011.109
Chung I. 2013 “Design of a Set of One-to-Many Node-Disjoint and Nearly Shortest Paths on Recursive Circulant Networks,” Journal of Korea Multimedia Society 16 (7) 897 - 904    DOI : 10.9717/kmms.2013.16.7.897
Johnson S.L. , Ho C. 1989 “Optimum Broadcasting and Personalized Communication in Hypercube,” IEEE Transactions on Computer 38 (9) 1249 - 1268    DOI : 10.1109/12.29465
Rabin M.O. 1989 “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance,” Journal of Association for Computing Machinery 36 (2) 335 - 348    DOI : 10.1145/62044.62050
Chung I. 1992 “Application of the Special Latin Squares to the Parallel Routing Algorithm on Hypercube,” Journal of Korea Information Science Society 19 (5) 569 - 578
Shih Y. , Kao S. 2011 “One-to-one Disjoint Path Covers on K-ary N-cubes,” Theoretical Computer Science 412 (35) 4513 - 4530    DOI : 10.1016/j.tcs.2011.04.035
Day K. , Tripathi A. 1994 “Comparative Study of Topological Properties of Hypercubes and Star Graphs,” IEEE Transactions on Parallel Distributed Systems 8 (1) 1196 - 1202
Gao S. , Novick B. , Qiu K. 1998 “From Hall Matching Theorem to Optimal Routing on Hypercubes,” Journal of Combinatorial Theory, Series B 74 (2) 291 - 301    DOI : 10.1006/jctb.1998.1850
Lai C. 2012 “Two Conditions for Reducing the Maximal Length of Node-Disjoint Paths in Hypercubes,” Theoretical Computer Science 418 82 - 91    DOI : 10.1016/j.tcs.2011.11.009
Gu Q. , Peng S. 2000 Theoretical Computer Science Networks 35 (1) 83 - 90    DOI : 10.1002/(SICI)1097-0037(200001)35:1<83::AID-NET7>3.0.CO;2-D
Madhavapeddy S. , Sudborough I. H. “A Topogical Property of Hypercubes: Node Disjoint Paths,” Proceedings of the Second IEEE Symposium on Parallel Distributed Processing 1990 532 - 539
Zhou J. , Wu Z. , Yang S. , Yuan K. 2015 ”Symmetric Property and Reliability of Balanced Hypercube,” IEEE Transactions on Computers 64 (3) 876 - 881    DOI : 10.1109/TC.2014.2304391
Cho Y. , Chung I. 2006 “A Parallel Routing Algorithm on Circulant Networks Employing the Hamiltonian Circuit Latin Square,” Information Sciences 176 (21) 3132 - 3142    DOI : 10.1016/j.ins.2005.12.014
Choi D. , Lee O. , Chung I. 2008 “A Parallel Routing Algorithm on Recursive Cube of Rings Networks Employing Hamiltonian Circuit Latin Square,” Information Sciences 178 (6) 1533 - 1541    DOI : 10.1016/j.ins.2007.10.028