1994 Reports
Hamiltonian Decompositions of Regular Topology Networks with Convergence Routing
This paper introduces new methods to construct multiple virtual rings for loss-free routing of non-reserved bursty data in high-speed environments such as ATM LANs. The routing algorithm on multiple virtual rings is convergence routing which combines the actual routing decision with the internal flow control state. Multiple virtual rings are obtained on the hypercube and the circulant networks such that each virtual ring is hamiltonian, and are mutually edge-disjoint. It is shown that multiple virtual rings improve (i) the bound on the length of routing, and (ii) the fault tolerance. On the circulant graphs, necessary and sufficient conditions for hamiltonian decomposition is established. On the hypercube, three algorithms are designed for an N-node hypercube with even dimension: (i) an O(N) time algorithm to find two edge-disjoint hamiltonian circuits, (ii) an O(N log N) time algorithm to find I01N hamiltonian circuits with only E ~ 0.1 common edges, and (iii) a recursive algorithm for the hamiltonian decomposition of the hypercube with dimension power of two. It is shown analytically, and verified by simulations on the circulants that with the d virtual ring embeddings, a bound of O( N / d) is established on the maximum length of routing.
Subjects
Files
-
CUCS-0110940001.pdf application/pdf 12 MB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-011-094
- Published Here
- August 7, 2013