A New Approach to Implement Proportional Share Resource Allocation

We describe a new approach to implement proportional share resource allocation and to provide different levels of service quality. We consider multiple clients that compete for a time-shared resource, and we associate to each client a certain amount of funds. At the beginning of every timeslice a client is selected and it is granted to use the resource during that time-slice. For selecting a client, we use a new deterministic scheme that allocates time-slices to every client in proportion to its funds. More precisely, we prove that our scheme ensures that out of m consecutive time-slices that are allocated to all clients, the difference between the actual number of time-slices allocated to a client and the expected one is at most proportional to log m. The algorithm is extended in order to support different levels of service quality; at the highest level it guarantees that a client receives a share of the resource that is both superior and inferior bounded. 1 Introduction One of the m...