A local fairness algorithm for the metaring, and its performance study

Abstract

In this paper we present an algorithm to provide local fairness for ring and bus networks with spatial reuse. Spatial reuse can significantly increase the effective throughput delivered by the network and is therefore desirable to be implemented in high speed LAN/MAN environments. However, spatial reuse can result in unfair access among nodes in the network, and thus, a fairness algorithm is needed to regulate the access to the network. A local fairness algorithm views the network as multiplicity of communication resources, as opposed to a global fairness algorithm, which views the network as a single communication resource. Our algorithm can be applied to any dual ring or bus architecture such as MetaRing [1, 4]. In the dual-bus configuration, when transporting ATM cells, the local fairness algorithm can be implemented using two generic flow control (GFC) bits in the ATM cell header. In the performance study section of our paper, we show that this local fairness algorithm can exploit the throughput advantage offered by spatial reuse better than a global fairness algorithm. This is 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 demonstrate the performance advantage of our 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 show that under certain traffic patterns, the performance of this algorithm achieves the optimal throughput result predicted by the known Max-Min fairness definition [5].