Distributed and Parallel Systems

THE WANDERING TOKEN: CONGESTION AVOIDANCE OF A SHARED RESOURCE (p. 3-4)

Augusto Ciuffoletti
CoreGRID Institute of Grid Information, Resource and Workflow Monitoring Services
INFN/CNAF – Via Berti Pichat – 40127 Bologna

Abstract

In a distributed system where scalability is an issue, the problem of enforcing mutual exclusion often arises in a soft form: the infrequent failure of the mutual exclusion predicate is tolerated, without compromising the consistent operation of the overall system. For instance this occurs when the operation subject to mutual exclusion requires massive use of a shared resource.

We introduce a scalable soft mutual exclusion algorithm, based on token passing: one distinguished feature of our algorithm is that instead of introducing an overlay topology we adopt a random walk approach. The consistency of our proposal is evaluated by simulation, and we bone based network.

This algorithm is studied in the frame of the CoreGRID Institute of Grid Information, Resource and Workflow Monitoring Services, in cooperation with the FORTH Institute, in Greece.

Keywords: congestion avoidance, random walk, token circulation, self-stabilization, soft mutual exclusion.

1. Introduction

In an ideal distributed system all resources are equivalently able to play any role. However, in practical applications, it is often the case that the introduction of a centralized resource may be appropriate, in order to reduce the cost, or to improve the performance. The loss of scalability and fault tolerance, which is inherent to the introduction of a centralized resource, is accepted as a tradeoff.

In order to avoid congestion, an appropriate access control mechanism must be provided. It is a well known fact that locating such mechanism at resource-side exhibits several drawbacks: the resource must be designed to negotiate services, using an appropriate protocol which consumes a share of available resources, and clients should make appropriate use of such negotiation. Here we propose a client-side mechanism especially suited for environments where resource and networking infrastructure are legacy.

A congestion avoidance mechanism coordinates the access to the centralized resource. The basic requirement is that resource performance, as observed by the client, must be nominal as long as the overall load does not exceed resource capacity. When requests overtake the capacity of the resource, it should reproduce at client side the effect of an overload, but without stress for the resource. The mechanism must not introduce bounds on system size, other than those enforced by resource capacity: this excludes the adoption of centralized algorithms, that are not scalable, as well as distributed algorithms based on deterministic consensus, that have an heavy footprint.

As a case study, we consider a "Video on Demand" environment where video streams at 650Kbps (appropriate for low resolution movies) are delivered to a group of subscribers. The shared resource in a 200Mbps backbone, which saturates with 300 subscribers. We want that subscribers coordinate their access to the infrastructure in order to limit their access to the stream source, thus keeping the overall used bandwidth below 200Mbps. Only exceptionally such limit can be exceeded:

the Service Agreement states that bursts up to 400Mbps are delivered with an additional cost, and that packet delivery is not guaranteed over that further limit. This might justify a flexible control over the number of subscribers, that might go over the theoretical maximum of 300 subscribers.

Summarizing, unlike traditional mutual exclusion modeled by a concurrent write on a shared register, our problem statement includes the occasional occurrence of simultaneous access to the resource. This is due to the nature of the resource whose performance may degrade (in the case study, degradation is initially only financial) when many are executed simultaneously, but without damage for the consistency of the system. This is formally translated in the following definition: