Paper Info
Title
Oblivious routing for LC permutations on hypercubes
Abstract
We propose an oblivious algorithm to route linear-complement (LC) permutations on hypercubes in circuit switched and wormhole routing. The algorithm guarantees that N independent paths can be set up simultaneously for any LC permutation with only a comparison of two bits in one routing step for any path. An LC permutation is determined by a transformation matrix T and a constant modifier C. For all the LC permutations with the same transformation matrix T (we call them a type of permutations), an algorithm is executed to find an ordered sequence of dimensions without knowing a particular permutation. When the sequence of dimensions is used in the routing process for all the packets of a permutation of this type, a comparison of two bits is carried out in each routing step in the packet transmission process. It is guaranteed that no contention will occur between any two paths on the use of the dimensional links, thus N independent paths can be set up simultaneously for the N packets of an LC permutation. Time complexity of the algorithm for finding an ordered sequence for the use of the n dimensions is O(n(3)) for any type of LC permutations (rather than one particular LC permutation), and it can be carried out off-line. The routing process itself is distributed, and oblivious. (C) 1999 Elsevier Science B.V. All rights reserved.
Year
DOI
Venue
1999
10.1016/S0167-8191(99)00008-3
Parallel Computing
Keywords
Field
DocType
lc permutation,oblivious routing,routing algorithms,parallel processing,time complexity,circuit switched,hypercube
Discrete mathematics,Equal-cost multi-path routing,Combinatorics,Link-state routing protocol,Dynamic Source Routing,Computer science,Permutation,Destination-Sequenced Distance Vector routing,Time complexity,Transformation matrix,Hypercube
Journal
Volume
Issue
ISSN
25
4
0167-8191
Citations 
PageRank 
References 
1
0.39
11
Authors
2
Name
Order
Citations
PageRank
Zhiyong Liu145.55
David W. Cheung21511156.71