Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation

We propose and analyze a new proportional share allocation algorithm for time shared resources. We assume that the resource is allocated in time quanta of size q. To each client, we associate a weight which determines the relative share from the resource that the client should receive. We define the notion of fairness in the context of an idealized system in which the resource is assumed to be granted in arbitrarily small intervals of time. Mainly, we show that in steady conditions our algorithm guarantees that the difference between the service time that a client should receive in the idealized system and the service time it actually receives in the real system is bounded by the size q of a time quantum. The algorithm provides support for dynamic operations, such as a client joining or leaving the competition (for the resource), and changing a client's weight. By using an efficient augmented binary search tree data structure we implement these operations in O(log n), where n represe...