MetaNet: Embedding of Virtual Rings

Yoram Ofek, Moti Yung, "METANET: Principles of an Arbitrary Topology LAN," IEEE/ACM T. on Networking, Volume: 3, Number: 2, Pages: 169-180, April 1995. (Abstract)

Y. Ofek, A. Mayer, M. Yung, "Local and congestion-driven fairness algorithm in arbitrary topology networks," IEEE/ACM Transactions on Networking, vol. 8, no. 3, Jun. 2000. (Abstract)

Yoram Ofek, Moti Yung, "Routing and Flow Control on the MetaNet: an Overview," Computer Networks and ISDN Systems, Volume: 26, Number: 6-8, Pages: 859-872, March 1994. (Abstarct)

Yoram Ofek, Moti Yung, "Asynchronous Lossless Broadcast-with-Feedback on the MetaNet Architecture," IEEE INFOCOM'91, Pages: 1050-1063, April 1991. (Abstarct)

Yoram Ofek, Moti Yung, "Principles for High Speed Network Control: lossless-ness and deadlock-freeness, self-routing and a single buffer per link," 9-th Annual ACM Symposium on Principles of Distributed Computing (PODC), Pages: 161-175, August 1990.
Also published in IBM Research Report: RC 16874, May 1990.

Yoram Ofek, Bulent Yener, Moti Yung, "Concurrent Asynchronous Broadcast on the MetaNet," IEEE Trans. on Computers, Volume: 46, Number: 7, Pages: 737-748, July 1997. (Abstarct)

Bulent Yener, Yoram Ofek, Moti Yung, "Combinatorial design of congestion-free networks," IEEE/ACM T. on Networking, Volume: 5 Issue: 6, Dec 1997, Pages: 989-1000.

Early version published in: IEEE INFOCOM'95, Pages: 88-96, 1995.
also published in: IBM Research Report: RC 19649, July 1994. (Abstarct)

Bulent Yener, Yoram Ofek, Moti Yung, "Configuration and Performance Issues in the MetaNet Design," 18th Conference on Local Computer Networks, Pages: 291-299, 1993. (Abstract)

Bulent Yener, Terry Boult, Yoram Ofek, Moti Yung, "Multiple Global Virtual Ring Embeddings on the MetaNet," IBM Research Report: RC 19209, October 1993. (Astract)

Bulent Yener, Yoram Ofek, Moti Yung, "The Synthesized MetaNet Architecture for Communication and Distributed Computing," IBM Research Report: RC 19226, October 1993. (Abstract)

Bulent Yener, Terry Boult, Yoram Ofek, "Hamiltonian Decompositions of Regular Topology Networks with Convergence Routing," IBM Research Report: RC 19810, November 1994. (Abstract)

Yoram Ofek, Moti Yung, "Local and congestion-driven fairness algorithm in arbitrary topology networks," IEEE/ACM Transactions on Networking, vol. 8, no. 3, pp. 362--372, Jun. 2000.

Yoram Ofek, Moti Yung, "Local Fairness in General-Topology Networks with Convergence Routing," IEEE/ACM Transactions on Networking, Vol. 5, No. 6, pp. 989-1000, December 1997.

Yoram Ofek, Moti Yung, "Access Regulation Mechanism for Switch-based LAN," Computer Networks, 31, 1999, pages: 505–518.

Yoram Ofek, Moti Yung, "Efficient Mechanism for Fairness and Deadlock-Avoidance in High-Speed Networks," Spriger-Verlag, Lecture Notes in Computer Science, No. 486 (The 4th International Workshop on Distributed Algorithms).
Also publiched in: IBM Research Report, RC 16851, May 1990. (Abstract)

Alain Mayer, Yoram Ofek, Moti Yung, "Local Fairness in General Topology Networks with Convergence Routing," IEEE INFOCOM'95, Pages: 891-899, 1995.
Also published in: IBM Research Report: RC 19686, August 1994. (Abstract)

Bulent Yener, Yoram Ofek, Moti Yung, "Convergence routing on disjoint spanning trees," Computer Networks, Pages: 169-175, 1994. (Abstract)

Bulent Yener, Yoram Ofek, Moti Yung, "Design and Performance of Convergence Routing on Spanning Trees," IEEE Globecom'94, Vol. 31, 1999. (Abstract)

Bulent Yener, S. Matsoukas, Yoram Ofek, "Iterative Approach to Optimize Convergence Routing Priorities," IEEE/ACM Transactions on Networking,,Vol. 5, No. 4, pp. 530-542, August 1997.
Also published in: IBM Research Report: RC 20178, September 1995. (Abstract)

Reuven Cohen, Yoram Ofek, "Reliable Transmission of Data Over a Semi-FIFO Routing Layer," Computer Networks and ISDN Systems, Volume: 27, Number: 12, Pages: 1633 - 1649, 1995.

Early version published in: IEEE INFOCOM'94, 984-991, 1994.
Also published in: IBM Research Report: RC 19052, July 1994. (Abstract)

Bulent Yener, Inderpal Bhandari, Yoram Ofek, Moti Yung, "Fault-Tolerant Convergence Routing," Journal of Parallel and Distributed Computing - JPDC, 42, pp. 173-183, 1997.

Early version published in : International Conference on Network Protocols (ICNP'94), Pages: 229-237, 1994. (Abstract)

Yoram Ofek, Moti Yung, "MetaNet: an Arbitrary Topology LAN for Data Acquisition and Processing," 2nd Conference on Electronics for Future Colliders, 1992. (Abstract)

Yoram Ofek, Steve Hicks, "High Speed Network for Real-time Data Acquisition and Control with Lossless and Balanced Self-routing," Symposium on Research and Development for the SSC, Dallas, October 1990. Also published in: IBM Research Report: RC 16852, October 1990. (Abstract)

Yoram Ofek, Moti Yung, "METANET: Principles of an Arbitrary Topology LAN," IEEE/ACM T. on Networking, Volume: 3, Number: 2, Pages: 169-180, April 1995.

ABSTRACT

The MetaNet is a scalable local area network (LAN) architecture with an arbitrary topology and a switch at each node (i.e., a switch based LAN). Its design provides on one hand a service in which any node can try to transmit asynchronously in a bursty manner without reservation as much as it can (as in traditional LAN), and on the other hand the network access and flow control ensure the following properties:
(1) no packet loss due to congestion, (2) fair access to the network, (3) no deadlocks, and (4) self-routing with broadcast. The switching over this network requires only a (5) single buffer per input link. The MetaNet is asynchronous, distributed, and designed for transmission of fixed size cells or variable size packets. It can be viewed as a general-topology buffer-insertion architecture with fairness, thus as generalizing the MetaRing architecture.

Yoram Ofek, Moti Yung, "Routing and Flow Control on the MetaNet: an Overview," Computer Networks and ISDN Systems, Volume: 26, Number: 6-8, Pages: 859-872, March 1994.

ABSTRACT

We review the underlying principles and design of the MetaNet, a LAN/MAN architecture with an "arbitrary topology" (i.e., a switch-based LAN). Its design provides on one hand a service in which every node can try to transmit asynchronously, in a bursty manner without reservation (as much as it can) as in shared-media LANs. On the other hand, the network access and flow control ensure the following properties: (1) no cell/packet loss due to congestion, (2) fair access to the network, (3) no deadlocks, (4) dynamic self-routing, and (5) broadcast-with-feedback. The switching over this network requires only a single buffer per link - as in buffer insertion rings.
The dynamic self-routing on the MetaNet is a variant of deflection routing. It makes on-line routing decisions based on the local flow of traffic (load conditions). Unlike other deflection techniques the MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. Thus, we call this method convergence routing (previous deflection algorithms did not guarantee deterministic routing convergence, i.e., a cell/packet can be deflected indefinitely inside the network). A natural implementation of a global sense of direction is an embedding a virtual ring along a tree that spans the network. The links of the virtual ring are numbered sequentially, such that, the numbering establishes a linear measure of the distance to the destination.

Yoram Ofek, Moti Yung, "Asynchronous Lossless Broadcast-with-Feedback on the MetaNet Architecture," IEEE INFOCOM'91, Pages: 1050-1063, April 1991.

ABSTRACT >

In this work we present broadcast and broadcast-with-feedback on the recently suggested MetaNet. The MetaNet is a novel network architecture which can be viewed as a local area network with an arbitrary topology and spatial bandwidth reuse (i.e., packets are removed by their destinations). On this architecture it is possible that on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure (1) no loss, (2) fair access to the network, (3) no deadlocks and (4) self-routing. The switching over this network requires only a (5) single buffer on the receiving sides of the full-duplex links.

Yoram Ofek, Moti Yung, "Principles for High Speed Network Control: lossless-ness and deadlock-freeness, self-routing and a single buffer per link," 9-th Annual ACM Symposium on Principles of Distributed Computing (PODC), Pages: 161-175, August 1990. Also published in IBM Research Report: RC 16874, May 1990.

ABSTRACT

A high-speed network is a new environment motivated by recent advances in transmission technology. The high-speed environment requires that the network node operate (fast) based solely on local information (at least most of the time). This fact implies properties that are much different than those existing in current architectures and algorithms for traditional large-area networks. The new environment poses new challenges for the network architect and the algorithm designer.
In this paper we present principles of operation for the basic control functions of a high-speed network with an arbitrary topology, we then suggest a design of such a network. In the architecture we design, on one hand a node can try to transmit asynchronously, without reservation, as much as it can, and on the other hand the network access and flow control will ensure no loss, fair access to the network, no deadlocks and self-routing.
The switching over this network requires only a single buffer on each side of the full-duplex links. The transmission via the receiving buffer can be cut through, i.e., the incoming packet can be sent to the next link before the entire packet has arrived (unlike store-and-forward). A dynamic self-routing technique is implemented, in which the packet header contains only the destination identification when it leaves the source. This information is sufficient for reaching the destination, not necessarily on the same route each time, and to overcome congestion and failures. All these properties are implemented in a distributed manner. The system is asynchronous and designed for transmission of variable size packets.

Yoram Ofek, Bulent Yener, Moti Yung, "Concurrent Asynchronous Broadcast on the MetaNet," IEEE Trans. on Computers, Volume: 46, Number: 7, Pages: 737-748, July 1997.

ABSTRACT

The problem solved in this work is how multiple nodes in a network with an arbitrary topology can broadcast concurrently, in an asynchronous manner, to all other nodes. Asynchronous means that the nodes do not coordinate their broadcast, and therefore, it is possible that all nodes will start to broadcast at the same time. Simultaneous broadcast by many nodes can cause traffic congestion, which can result in a traffic loss.
The main property of the broadcast algorithms presented in this work is that under any arbitrary broadcast pattern there will be no packet or cell loss due to internal traffic congestion. The routing mechanism used by the broadcast algorithm is a variant of deflection routing, which means that a node makes on-line routing decisions based on the local flow of traffic (i.e., internal load conditions). Unlike other deflection techniques, the MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. Thus, we call this method convergence routing (previous deflection algorithms did not guarantee deterministic routing convergence, i.e., a cell/packet can be deflected indefinitely inside the network). As a result of the convergence property, the deflection routing used in this work is the only one with broadcast capability.

Yoram Ofek, Moti Yung, "Efficient Mechanism for Fairness and Deadlock-Avoidance in High-Speed Networks," Spriger-Verlag, Lecture Notes in Computer Science, No. 486 (The 4th International Workshop on Distributed Algorithms). Also publiched in: IBM Research Report, RC 16851, May 1990.

ABSTRACT

This paper describes a mechanism that regulates access of burst traffic sources to a switch-based LAN. This regulation mechanism ensures global fairness, such that, within a well-defined global control cycle each node can transmit a predefined number of data units over its adjacent links. The global control cycle is created over a tree that spans a network with an arbitrary topology. As oppose to previous works, in which a global control cycle was created over a ring (e.g., token-ring, MetaRing). As a result, in this work the global control cycle can be shorter and the access mechanism to the network is more efficient.
The regulation mechanism is based on exchanging control signals between neighboring nodes. The proposed mechanism has the following properties: (i) time-driven automatic stabilization, (ii) it can tolerate automatically one control signal loss in every global control cycle, and (iii) it requires only two bits of information for the control signals. This last property is of significance for ATM LANs, since it will be possible to implement this mechanism using two bits in the generic flow control (GFC) field of the ATM cell header.

Alain Mayer, Yoram Ofek, Moti Yung, "Local Fairness in General Topology Networks with Convergence Routing," IEEE INFOCOM'95, Pages: 891-899, 1995. Also published in: IBM Research Report: RC 19686, August 1994.

ABSTRACT

Convergence routing is a unique variant of deflection routing which ensures that packets (or cells) will converge to their destinations along a global sense of direction. In this work we show how a global sense of direction can be used in an arbitrary network for the design of a control algorithm which (a) ensures fair access in switch-based local area networks, (b) is efficient with respect to performance measures we have developed, and (c) is easily interfaced to the convergence routing mechanism.
We present performance measures which assess the new access- and flow-control algorithm: (i) Locality - only the sub-network containing conflicting traffic streams gets involved in the fairness regulation. (ii) Scalability - the data-structure sizes used in the algorithm are a function of the switching node degree, and uses constant space control signals of only 2-bit (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). (iii) Linear access-time measured by the maximal clique in the conflict-graph to which a node belongs, and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).

Reuven Cohen, Yoram Ofek, "Reliable Transmission of Data Over a Semi-FIFO Routing Layer," Computer Networks and ISDN Systems, Volume: 27, Number: 12, Pages: 1633 - 1649, 1995. Also published in: IEEE INFOCOM'94, 984-991, 1994. Also published in: IBM Research Report: RC 19052, July 1994.

ABSTRACT

In computer networks there is usually a trade-off between the performance and implementation complexity of the routing protocol, and those of the protocol for reliable transmission of data. Often, the routing protocol can perform better if it is not required to retain the FIFO order of the routed data units. However, in such a case the protocol for reliable transmission of data has to maintain many logical timers and to have accurate estimate of the round trip delay. The paper introduces a new notion: semi-FIFO service, which means that the routing layer retains the FIFO order in part.
The paper shows that sometimes a non-FIFO routing layer may provide for semi-FIFO service, without substantial changes in the routing concept. Then, the paper proposes a new protocol for reliable transmission of data over an unreliable semi-FIFO routing layer. The protocol uses only one logical timer and does not require an estimate of the round trip delay in order to operate with full capacity. Therefore, the contribution of the paper is eliminating the deficiencies associated with non-FIFO routing schemes that may offer semi-FIFO service.

Bulent Yener, Inderpal Bhandari, Yoram Ofek, Moti Yung, "Fault-Tolerant Convergence Routing," JPDC, .... Also published in : International Conference on Network Protocols (ICNP'94), Pages: 229-237, 1994.

ABSTRACT

This paper presents fault-tolerant protocols for fast packet switch networks with convergence routing. The objective is to provide, after a link or a node (switch) failure, fast reconfiguration and continuous host-to-host communication. Convergence routing is a variant of deflection routing, which combines, in a dynamic fashion, the on-line routing decision with the traffic load inside network. Unlike other deflection techniques, convergence routing guarantees that packets will reach or converge to their destinations.
This fault-tolerant solution is designed for a switch-based (i.e., arbitrary topology) LAN architecture called MetaNet. In this work, the original MetaNet's convergence routing scheme has been modified in order to facilitate the property that the packet header need not be recomputed after a failure and/or a reconfiguration. This is achieved by having, at the network interface, a translator that maps the unique destination address to a virtual address. The virtual addresses are stored at the packet header, and used for convergence routing, with global sense of direction over (i) a single spanning tree, and (ii) over two edge-disjoint spanning trees - for redundancy (fault tolerance) and greater efficiency.

Bulent Yener, Yoram Ofek, Moti Yung, "Topological Design of Loss-Free Switch-Based LANs," IEEE/ACM T. on Networking. Also published in: IEEE INFOCOM'95, Pages: 88-96, 1995. also published in: IBM Research Report: RC 19649, July 1994.

ABSTRACT

This paper presents a new design methodology and tools to construct a switch-based LAN with (i) scalable throughput, (ii) no loss due to congestion, and (iii) two routing modes: FIFO or non-FIFO. More specifically, given a bounded degree (number of switch ports) at each node, the design is based on the construction of multiple virtual rings under the following constraints: (i) the virtual rings are pairwise edge-disjoint, and (ii) there is at least one virtual ring between any pair of nodes. The target topology is obtained from the edge union of the multiple virtual rings. The objectives of the above two constraints are (i) to ensure no loss due to congestion inside the network of bursty traffic sources, and (ii) to ensure convergence of packets/cells to their destinations. The virtual rings are constructed by a new methodology that employs Combinatorial Block Designs together with a new algorithm for realizing any size networks. It is shown that the bound on the maximum route length, under the two constraints, is O(\sqrt N) for an N-node network.

Bulent Yener, Yoram Ofek, Moti Yung, "Configuration and Performance Issues in the MetaNet Design," 18th Conference on Local Computer Networks, Pages: 291-299, 1993.

ABSTRACT

This paper examines various virtual embedding configurations for the MetaNet architecture. It compares and contrast the suggested embedding structures, and identifies design parameters and their trade-off. This study is based on the combination of convergence routing with the fairness mechanism, which controls the internal traffic load. More specifically, the fairness is used as a mechanism to ensure that the network internally will not be over-loaded. Therefore, packets can be sent from source to destination on a route which is close to the shortest path.
The routing on the MetaNet is a variant of deflection routing}. It makes on-line routing decisions based on the local flow of traffic (load conditions). Unlike other deflection techniques the MetaNet routing is along a global sense of direction, which guarantees that packets will reach their destinations. Therefore, we call this method convergence routing (previous deflection algorithms did not guarantee deterministic routing convergence, i.e., a cell/packet can be deflected indefinitely inside the network).
The MetaNet is a LAN/MAN architecture with an "arbitrary topology" (i.e., a switch-based LAN). Its design provides on one hand a service in which every node can try to transmit asynchronously, in a bursty manner without reservation, as much as it can, as in shared-media LANs. On the other hand, the network access and flow control ensure the following properties: (1) no cell/packet loss due to congestion, (2) fair access to the network and (3) broadcast-with-feedback. The switching over this network requires only a single buffer per link - as in buffer insertion rings.

Bulent Yener, Terry Boult, Yoram Ofek, Moti Yung, "Multiple Global Virtual Ring Embeddings on the MetaNet," IBM Research Report: RC 19209, October 1993.

ABSTRACT

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.

Bulent Yener, Yoram Ofek, Moti Yung, "The Synthesized MetaNet Architecture for Communication and Distributed Computing," IBM Research Report: RC 19226, October 1993.

ABSTRACT

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.

Bulent Yener, Terry Boult, Yoram Ofek, "Hamiltonian Decompositions of Regular Topology Networks with Convergence Routing," IBM Research Report: RC 19810, November 1994.

ABSTRACT

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 log N over 2 hamiltonian circuits with only Epsilon less than equal to 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.

Bulent Yener, Yoram Ofek, Moti Yung, "Design and Performance of Convergence Routing on Spanning Trees," IEEE Globecom'94, Pages: 169-175, 1994.

ABSTRACT

This paper presents a new design, and a performance study for convergence routing in a general network with multiple spanning trees suggested as a switch-based LAN. In particular, a new algorithm for constructing two edge-disjoint spanning trees of a given network is presented, and the resulting trees are used for convergence routing (a variant of deflection routing with destination convergence guaranteed). It is shown empirically that convergence routing on two edge-disjoint spanning trees yields a better bound than a single spanning tree, on the maximum route length. The construction of the two edge-disjoint spanning trees is done with specific strategies for achieving certain tree properties that improve the system's performance.

Bulent Yener, S. Matsoukas, Yoram Ofek, "Iterative Approach to Optimize Convergence Routing Priorities," IEEE/ACM, ...???????? Also published in: IBM Research Report: RC 20178, September 1995.

ABSTRACT

In convergence routing successive packets of the same session are routed towards their destinations, but not necessarily on the same path (i.e., it is a dynamic routing technique). More specifically, at every intermediate switching node a packet can be forwarded towards its destination over one or more out-going links. The routing decision, over which link to forward the packet, is based on a simple metric, which ensures that each packet will converge to or reach its destination. When there are multiple routing choices the simplest routing strategy is local-greedy, namely, to minimize the distance to the destination as much as possible at every intermediate node.
In this work we show that the local-greedy strategy is not necessarily the best one. We develop an iterative optimization technique which sets routing priorities and takes into account the potential gain on other switching nodes along the route. The optimization objective is to maximize throughput by minimizing the maximum total flow on a link in the network under uniform traffic model. The flow values are computed by formulating the convergence routing as a multicommodity flow problem, and solving it as an instance of linear programming by Simplex algorithm. Flow assignments over the links are input to a new analytical model to update the routing probabilities for the next iteration of the optimization algorithm. The stability of the routing tables are studied computationally on various networks and traffic matrices. Five heuristics are examined to find an efficient bias factor to prevent the oscillation problem.

Yoram Ofek, Moti Yung, "MetaNet: an Arbitrary Topology LAN for Data Acquisition and Processing," 2nd Conference on Electronics for Future Colliders, 1992.

ABSTRACT

In this paper we present gigabit network architecture, called MetaNet, for interconnecting both the on-line and the off-line data acquisition and processing. In our solution we concentrate on how to interconnect the front-end (ADCs and level 1 and 2 triggers) with the on-line (real-time) event processing. We propose that the on-line solution will be extended into the off-line data processing and mass-storage. As a result, this solution provides a single uniform structure which will simplify the overall system.
The MetaNet is a local area network (LAN) architecture with an "arbitrary topology" and switch at each node (a switch based LAN). Its design provides on one hand a service in which any node can try to transmit asynchronously, in a bursty manner without reservation, as much as it can, and on the other hand the network access and flow control will ensure the following properties: (1) no packet loss due to congestion, (2) fair access to the network, (3) no deadlocks, (4) dynamic self-routing, and (5) broadcast-with-feedback. The switching over this network requires only a (6) single buffer per link for the transmission of variable size frames or fix size cells.

Yoram Ofek, Steve Hicks, "High Speed Network for Real-time Data Acquisition and Control with Lossless and Balanced Self-routing," Symposium on Research and Development for the SSC, Dallas, October 1990. Also published in: IBM Research Report: RC 16852, October 1990.

ABSTRACT

We present a gigabit network architecture for interconnecting the on-line and off-line data acquisition and processing farms for future detector facilities at the SSC (Superconducting Super Collider). In our solution we concentrate on how to interconnect the front-end (ADCs and level 1&2 triggers) with the on-line (real-time) computer farm. We propose that the solution be extended into the off-line data processing and mass-storage. As a result, this solution provides a single uniform structure which will simplify the overall system.

Y. Ofek, A. Mayer, M. Yung, "Local and congestion-driven fairness algorithm in arbitrary topology networks," IEEE/ACM Transactions on Networking, vol. 8, no. 3, Jun. 2000.

ABSTRACT

Typically, bandwidth reservation is not made for data applications. Therefore, the only way to provide minimum bandwidth guarantees to such an application is by using a fairness mechanism to regulate the access to the network and by controlling the packet loss (i.e., congestion) inside the network. There are numerous works treating fairness in ring networks, however, there are almost no such works on fairness in arbitrary topology networks. The context of this work is fairness in an arbitrary topology network, the MetaNet, which employs convergence routing, a loss-free routing technique which is a variant on deflection routing. We note that minimum bandwidth guarantee combined with loss-free routing are the desired quality-of-service (QoS) attributes for most data applications.
While developing the mechanisms, we also present performance measures to assess the new access- and flow-control algorithm:

1. Locality and congestion-driven -- only the subnetwork containing conflicting traffic streams becomes involved in the fairness regulation. Furthermore, the fairness regulation is activated only when congestion occurs. This implies that when there is no congestion, nodes can access the network immediately and freely, which is a key requirement for distributed computing.
2. Scalability -- the data-structure sizes used in the algorithm are a function of the switching node degree, and use constant space control signals of two bits only (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control).
3. Linear access time in the congested subnetwork -- measured by “the maximal clique in what we call the conflict graph to which a node belongs,” and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).