Multiple Global Virtual Ring Embeddings on the MetaNet

        This paper introduces embeddings of multiple virtual rings into the MetaNet, a switch based LAN architecture, for improving the bound on the average length of routing and increasing the throughput. The virtual rings are directed, edge-disjoint, and each ring traverses every node at least once. Two structures for multiple virtual embeddings are suggested based on (i) two edge-disjoint spanning trees, and (ii) edge-disjoint Hamiltonian circuits. The tree embedded virtual rings are suggested for arbitrary topology networks. Necessary and sufficient conditions for finding two edge-disjoint spanning trees are established and a new O (N/3/) time algorithm is presented, where N is the number of nodes. The Hamiltonian based virtual rings are studied on the hypercube and 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 log N over 2 Hamiltonian circuits with only epsilon less than equal to 0.1 common edges, and (iii) a simple algorithm for the Hamiltonian decomposition of the hypercube with dimension power of two. It is shown that the multiple virtual ring embeddings yields to a bound N/d for the average length of routing.

By: Bulent Yener (Dept. of CS, Columbia U.), Terry Boult, Yoram Ofek and Moti Yung

Published in: RC19209 in 1993

This Research Report is not available electronically. Please request a copy from the contact listed below. IBM employees should contact ITIRC for a copy.

Questions about this service can be mailed to reports@us.ibm.com .