MetaRing: Rings with Spatial Reuse & Fairness

Y. Ofek, "Overview of the MetaRing Architecture," Computer Networks and ISDN Systems, Volume: 26, Number: 6-8, Pages: 817-830, March 1994.

ABSTRACT

The basic MetaRing architecture is a full-duplex ring providing fairness and spatial bandwidth reuse. Concurrent access and spatial bandwidth reuse enable simultaneous transmission over disjoint segments of the bi-directional ring. It therefore increases the potential throughput in each direction, by a factor of four or more. In this work, we overview the MetaRing principles: (1) Distributed global fairness algorithm, a simple and robust mechanism based on a single control signal (i.e., one bit of information) that regulates the access to the ring. (2) Protocol for service integration of: (i) synchronous or real-time traffic which is periodic and requires a connection set-up and which will have guaranteed bandwidth as well as bounded delay, and (ii) connectionless or asynchronous traffic with no real-time constraints that can use the remainder of the bandwidth. Integration is an important function for multi-media applications. (3) Protocol and requirements for multi-ring and dual-bus MetaRing networks. (4) Principles and requirements for interconnecting MetaRing with wide-area networks (WANs). We show that (i) the WAN-to-ring interconnection requires a separate queue for asynchronous traffic and relies on the use of the fairness mechanism for internal flow control, whereas (ii) the WAN-to-dual-bus configuration of the MetaRing network is simpler, since it does not require any buffering and does not rely on a fairness mechanism for internal flow control, furthermore; it is fault tolerant and has better synchronous traffic performance.

Yoram Ofek, Khosrow Sohraby, Ho-Ting Wu, "Integration of Synchronous and Asynchronous Traffic on the MetaRing Architecture and Its Analysis," IEEE/ACM T. on Networking, Volume: 5, Number: 1, Pages: 111-121, 1997 - Also published in: ICC'92, Pages: 147-153, 1992. Also IBM Research Report: RC 17718, February 1992.

ABSTRACT

In this paper, we describe and evaluate a protocol for integrating two types of traffic on the MetaRing Architecture. Synchronous (reserved or real-time) traffic which is periodic and requires a connection set-up and will have guaranteed bandwidth and bounded delay, and asynchronous or bursty traffic with no real-time constraints that can use the remainder of the bandwidth in a fair manner. The integration mechanism is functionally equivalent to the Timed-Token Function in FDDI, which is a shared media ring protocol. The MetaRing is a slotted or buffer insertion ring with fairness and spatial bandwidth reuse. Concurrent access and spatial bandwidth reuse enable the simultaneous transmissions over disjoint segments of a bi-directional ring and therefore, can increase the effective throughput in each direction. The fairness mechanism for this architecture is simple and robust, and it is based on a 1-bit control signal that regulates the access to the ring. A Markovian state space formulation of the integration protocol is given. This compact and efficient formulation which uses only a few state equations is used for the simulation of the network with arbitrary number of nodes. An upper bound on the delay of the synchronous traffic is provided to demonstrate the importance of the integration algorithm. Simulation results are also presented to show the effects of the fairness and flow control signals on the performance of the network.

Israel Cidon, Yoram Ofek, "MetaRing - A Full-Duplex Ring with Fairness and Spatial Reuse," IEEE Trans. on Comm., Volume: COM-41, Number: 1, Pages: 110-120, January 1993. Also published in: IEEE INFOCOM'90, Pages: 969-981. Also IBM Research Report: RC 14961, September 1989.

ABSTRACT

We describe the design principles of a ring network with spatial bandwidth reuse. Our goal is to provide the same functions in existing LAN/MAN designs that do not permit spatial reuse and concurrent transmission. A distributed fairness mechanism for this architecture, which uses low latency hardware control signals, is presented. The basic fairness mechanism can be extended for implementing multiple priority levels and integration of asynchronous with synchronous traffic. The ring is full-duplex and has two basic modes of operation: buffer insertion mode for variable size packets and slotted mode for fixed size packets or cells. As a result, this architecture is suitable for a wide range of applications and environments. Concurrent access and spatial reuse enable the simultaneous transmissions over disjoint segments of a bi-directional ring, and therefore, can increase the effective throughput, by a factor of four or more. The efficiency of this architecture does not degrade as the bandwidth and physical size of the system increases. The combination of a full-duplex ring, spatial reuse, reliable fairness mechanism, and the exploitation of the recent advent in fiber-optic technology are the basis for the MetaRing network architecture. This network has been prototyped at the IBM T. J. Watson Research Center, and will also be deployed within the AURORA Testbed that is part of the NSF/DARPA Gigabit Networking program.

Alain Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung, " Self-Stabilizing Symmetry Breaking in Constant-Space," ACM-STOC, Pages: 667-678, May 1992.

ABSTRACT

We investigate the problem of self-stabilizing round-robin token management scheme on an anonymous bi-directional ring of identical processors, where each processor is an asynchronous probabilistic (coin-flipping) finite state machine which sends and receives messages. We show that the solution to this problem is equivalent to symmetry breaking (i.e., leader election). Requiring only constant-size messages and message-passing model has practical implications: our solution can be implemented in high-speed networks using a universal fast hardware switches (i.e., finite state machines) of size independent of the size of the network. Our automata-based message-passing model has inherent deadlock possibility (i.e., when all processors are waiting for a message) which we assume is detected by an external time-out mechanism. Provided that there is no deadlock to begin with, we show how starting from an arbitrary configuration, the system never enters a deadlock state and further stabilizes in polynomial time. We note that Dijkstra showed that the last problem does not have a deterministic solution (even when the identical processors possess an arbitrary power): starting from a ring with a multitude of tokens, any deterministic system will either not stabilize or will enter a deadlock state.

Jeane Chen, Israel Cidon, Yoram Ofek, "A Local Fairness Algorithm for Gigabit LANs/MANs," IEEE J. on Selected Areas in Comm., Volume: 11, Number: 8, Pages: 1183-1192, October 1992. Also published in: GLOBECOM'92, Pages: 1635-1641, 1992.

ABSTRACT

In this paper we present an algorithm to provide local fairness for ring and bus networks with spatial bandwidth reuse. Spatial bandwidth reuse can significantly increase the effective throughput delivered by the network and is, therefore, desirable to be implemented in high-speed LAN/MAN environments. Our algorithm can be applied to any dual ring or bus architecture such as MetaRing. In the performance study section of our paper, we will show that this local fairness algorithm can exploit the throughput advantage offered by spatial bandwidth reuse better than a global fairness algorithm. This is accomplished because it ensures fair use of network resources among nodes, which are competing for the same subset of links, while permitting free access to non-congested parts of the network. We will demonstrate the performance advantage of out local fairness scheme by simulating the system under various traffic scenarios and compare the results to that of the MetaRing SAT-based global fairness algorithm. Furthermore, we will show that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition.

Alain Mayer, Yoram Ofek, Moti Yung, "Approximating Max-Min Fair Rates via Distributed Local Scheduling with Partial Information," IEEE INFOCOM'96, March 1996. Also IBM Research Report: RC 19931, September 1995.

ABSTRACT

Max-Min fairness has been recognized as an optimal throughput-fairness definition. However, its realization in packet switching networks and its computational requirements have not yet been understood. In this work we attempt to take a step in this direction. The Max-Min definition is given in terms of transmission rates of sources sending to their destinations (sessions). In order to realize Max-Min rates in a packet switching environment, transmission schedules of packets need to be realized. We first show that finding Max-Min fair schedules (with given rates) requires global state and timing information of all the nodes in the network.

Rahul Simha, Yoram Ofek, "A Starvation-free Access Protocol for a Full-duplex Buffer Insertion Ring Local Area Network," Computer Networks and ISDN Systems, Volume: 21, Number: 2, Pages: 109-120, 1991. Also IBM Research Report: RC 15052, October 1989.

ABSTRACT

Of several existing designs for local area networks, the buffer insertion ring has been shown to provide higher throughputs, lower mean delays, and greater spatial reuse than competing designs such as the token ring and slotted ring networks. However, one disadvantage is that the normally unregulated access scheme of the Insertion Ring allows for the phenomenon of starvation, when a network node has to wait too long before it can access the ring. In our work we demonstrate that starvation is a serious problem and we present a protocol to prevent it. It is shown that the new protocol is correct, stable, and does not substantially degrade the otherwise efficient operation of the ring.

Rahul Simha, Yoram Ofek, "Reducing Global Address Recognition Delay in Local Area Networks with Spatial Reuse," Computer Networks and ISDN Systems, Volume: 26, Pages: 1375-1384, 1994.

ABSTRACT

A special class of local area networks has recently received much attention in which destination nodes remove packets from the network, allowing spatial bandwidth reuse or concurrent transmission of packets without collision. Destination removal requires that each node delays packets long enough so it can decode the destination address. If the address is a short label (say, 8-bit) the decoding time is short, but if we want to use global or MAC addresses of 48 or 64 bits, the sum of decoding times encountered by packets may result in unacceptably long delays, even at light traffic loads. In this paper, we propose protocols for reducing global address recognition delays, which are designed to supplement existing protocols for local area networks with spatial bandwidth reuse. They are also designed to coexist with other addressing modes used for individual LANs, which are based on the use of very short, locally administered labels. Of particular interest is a completely decentralized protocol, which achieves the low global address recognition delays of multi-access protocols and yet seamlessly reverts to efficient spatial bandwidth reuse at high loads. We focus on the MetaRing and MetaNet architectures and apply our methods to these local area networks. A simple probabilistic model is presented which demonstrates significant improvement in delay when our protocols are used.

Jeane Chen, Hamid Ahmadi, Yoram Ofek, "Performance Study of a Gb/s MetaRing," 16th Conference on Local Computer Networks, 1991.

ABSTRACT

MetaRing is a Gigabit/second Local Area Network architecture based on a dual (bi-directional) optical fiber ring with spatial bandwidth reuse mechanism. Concurrent access and spatial bandwidth reuse enable simultaneous transmissions over disjoint segments of a bi-directional ring, and therefore, can potentially increase the effective throughput by a factor of four. The architecture has two basic modes of operation: buffer insertion mode for variable size packets and slotted mode for fixed size packets. As a result, this architecture is suitable for a wide range of applications and environments. The heart of the architecture is a distributed global fairness mechanism that ensures fair access to the ring by all stations with little degradation in performance. The efficiency of this architecture does not degrade as the bandwidth and physical size of the system increases. In this paper we use simulation to study the performance of MetaRing in the buffer insertion mode with variable length packets. We show through various delay-throughput curves, the major performance aspects of the MetaRing architecture. Our results indicate that the combination of a full-duplex ring, spatial bandwidth reuse, and a simple and reliable fairness mechanism of MetaRing architecture exhibit excellent delay-throughput performance.

Yoram Ofek, "Integration of Multi-ring on the MetaRing Architecture," 2nd IEEE Workshop on Future Trends of Distributed Computing Systems, Pages: 190-196, Egypt, 1990. Also IBM Research Report: RC 16058, 1990.

ABSTRACT

The MetaRing architecture is a full-duplex ring with fairness and spatial bandwidth reuse. Concurrent access and spatial reuse enable the simultaneous transmissions over disjoint segments of a bi-directional ring, and therefore, can increase the effective throughput, in each direction, by a factor of four or more. The fairness mechanism for this architecture is distributed; based on a control signal that regulates the access to the ring, and is extremely simple and robust. The efficiency of this architecture does not degrade as the bandwidth and physical size of the system increases. In this work we describe the principles for constructing a single MetaRing system that is composed of multiple rings. The motivation for such a structure is to increase the spatial reuse and to enhance the fault tolerance of the system. Each ring in this structure can be viewed as a cluster of users with relatively higher internal interaction than external interaction with users in other clusters.

Israel Cidon, Yoram Ofek, "Distributed Fairness Algorithm for Local Area Networks with Concurrent Transmissions," Springer Verlag Lecture Notes in Computer Science 392 (The 3rd International Workshop on Distributed Algorithms), Pages: 57-69, September 1989. Also IBM Research Report: RC 15051, October 1989.

ABSTRACT

In this work, it is shown how multiple nodes can access a ring network concurrently in a fair manner. Traditionally, most ring and bus networks allow only a single user to transmit at any given time (e.g., token ring, Ethernet, DQDB). Concurrent access or spatial bandwidth reuse enables the simultaneous transmissions over disjoint segments of a bi-directional ring, and therefore, can significantly increase the effective throughput, by a factor of four or more. Spatial bandwidth reuse can be easily implemented using a full-duplex buffer insertion or slotted techniques. However, these techniques may also cause starvation and thus has an inherent fairness problem. Two types of fairness algorithms are presented, global and local; both are shown to be stable and fault tolerant. The global fairness mechanism provides a complete fairness and is immune to control messages loss or duplication. This global algorithm views the whole ring as a single resource, while the local fairness algorithm views the ring as multiple disjoint resources. The local fairness mechanism is triggered only if potential starvation exists and is usually restricted only to segments of interfering nodes. If the segment of the interfering nodes covers the whole ring, we show that the local mechanism is equivalent to the global one. The combination of a full-duplex buffer insertion ring, spatial reuse, reliable fairness mechanism, and the exploitation of the recent advent in fiber-optic technology are the basis for the MetaRing network architecture. This network is currently being prototyped at the IBM T.J. Watson Research Center.

Felix Closs, Yoram Ofek, "Media Access Protocols for Gb/s LANs with Spatial Reuse, Fairness, and Isochronous Service," 37th Annual IEEE International Computer Conference - COMPCON SPRING '92, Pages: 239-246, 1992.

ABSTRACT

The authors describe the design principles of a ring-based LAN (local area network) with spatial bandwidth reuse and support of isochronous channels. The network uses buffer insertion which, in contrast to token passing principles, allows concurrent media access. Spatial bandwidth reuse and concurrent access allow simultaneous packet transmissions over disjoint segments of the ring. As a result, the potential aggregate throughput of a dual ring can be 8 times the data rate of a single link. Buffer insertion coupled with spatial bandwidth reuse can cause unfairness. The author describes two algorithms to eliminate this deficiency: (i) a flow-based fairness algorithm and (ii) a reservation-based fairness algorithm. Conventional buffer insertion introduces variable amounts of delay and is therefore not directly suitable for isochronous traffic. A novel method to combine asynchronous (packet-oriented) and isochronous traffic on the same buffer insertion ring is outlined.

G. Anastasi, L. Lenzini, M. La Porta, Y. Ofek, "Dynamic Max-Min Fairness in Ring Networks", Cluster Computing, Vol. 3, No. 3 , pp. 215-230, 2000.

ABSTRACT

Ring networks are enjoying renewed interest as Storage Area Networks (SANs), i.e., networks for interconnecting storage devices (e.g., disk, disk arrays and tape drives) and storage data clients. This paper addresses the problem of fairness in ring networks with spatial reuse operating under dynamic traffic scenarios. To this end, in the first part of the paper the Max-Min fairness definition is extended to dynamic traffic scenarios and an algorithm for computing Max-Min fair rates in a dynamic environment is introduced. In the second part of the paper the extended Max-Min fairness definition is used as a measure to compare the performance in dynamic conditions of three fairness algorithms proposed for ring-based SANs. These algorithms are characterized by different fairness cycle sizes (number of links involved in each instance of the fairness algorithm), i.e., different complexity. The results show that the performance increases as the fairness cycle size decreases. In particular, the Global-cycle algorithm (implemented in the Serial Storage Architecture – SSA), whose cycle size is equal to the number N of links in the ring, exhibits the lowest performance, while the One-cycle algorithm, so called because of its cycle size equal to 1, has the best performance. The Variable-cycle algorithm, whose cycle size changes between 1 and N links, performs in between and provides the best tradeoff between performance and complexity.

G. Anastasi, L. Lenzini, Y. Ofek, "Tradeoff between the Cycle Complexity and the Fairness of Ring Networks", Microprocessors and Microsystems, Vol. 25, No. 1, pp. 41-59, 2001.

ABSTRACT

In this paper we study performance tradeoffs of fairness algorithms for ring networks with spatial bandwidth reuse, by using two measures: (i) the fairness cycle size as a complexity measure, and (ii) the Max-Min optimal fairness criterion as a throughput measure. The fairness cycle size is determined by the number of communication links involved in every instance of the fairness algorithm (several identical fairness algorithms can be executed concurrently on the same ring). The study compares three fairness algorithms with different cycle sizes: the Globalcycle algorithm (implemented in the Serial Storage Architecture - SSA) in which the cycle size is equal to the number N of links in the ring; the Variable-cycle algorithm in which its cycle size changes between 1 and N links; the Onecycle, where there is a fairness cycle on every link. It is shown how varying the cycle size affects the network performance with respect to the Max-Min optimal fairness criterion. The results show that for non-homogeneous traffic patterns, decreasing the fairness cycle size, while increasing the complexity, can significantly improve the performance with respect to the Max-Min optimal fairness criterion.