The Synthesized MetaNet Architecture for Communication and Distributed Computing.

        In this paper we present a synthetic approach for improving the bounds and average of the routing length in the MetaNet architecture. By doing so the delay and jitter are decreased, and the total system throughput is increased. More specifically, given N nodes with fixed degree d, we show in this work two methods for constructing d global virtual rings. Each ring traverses all nodes in the network once, and thus induces a Hamiltonian cycle. It is shown, analytically and experimentally, that this construction provides an upper bound of N/d on the length of routing. The routing on the MetaNet is a variant of deflection routing, combining the actual routing decision with the internal flow control state. As a result, there is no packet loss due to congestion inside the network. Furthermore, unlike other deflection techniques the MetaNet routing uses the global virtual rings as global sense of direction, which guarantees that packets will reach their destinations. Note that previous deflection algorithms did not guarantee deterministic routing convergence, i.e., no upper bound on the routing length. The approach presented in this paper is synthetic, in the sense that first a set of global virtual rings are constructed, and then a target network is obtained from a union of these rings. For the synthetic approach it is assumed that there are no pre-existing infrastructure constraints, and therefore, the network links and switches can be laid out in an arbitrary fashion. This is usually the case when constructing distributed and parallel computing machines.

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

Published in: RC19226 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 .