In many applications, multiple entities have demands for a service or resource where the aggregate demand exceeds the total resources available. In such a situation, the goal is to allocate the available resources in a fair manner among the entities. Some systems, such as an ABR capable ATM adapter, require this allocation to be performed quickly and repeatedly due to the dynamic nature of the demands on the shared resource.
In the past, this task has been done in one of two basic ways; using implicit allocation or explicit allocation. Implicit allocation services each entity according to a policy, such as round-robin or weighted round-robin, and the shared resources are "allocated" as the entities use them during their turn to be serviced. Explicit allocation attempts to calculate using some criterion, such as proportional allocation or max-min fairness, the amount of resources to be provided to each entity which can then be used to determine when to service each entity.
The different methods of performing allocation vary in complexity of implementation, fairness, accuracy, and failure modes. Explicit allocation using the max-min fairness criterion is considered to be one of the best methods for performing this task, but it has been considered impractical to use due to the time to perform and complexity of the calculations required especially when the number of entities is "large". The algorithm presented provides a simple, quick method of performing an explicit max-min fair allocation and can be customized for a variety of applications.