Patent ID: 8694639

Claim:
A system, comprising: a memory of a server that, during operation, stores instructions; and one or more processors of the server that, during operation, execute the instructions to implement a capacity reservation system (CRS), wherein the CRS includes: a resource allocation module that, during operation, receives client requests from a plurality of clients for access to a server resource and allocates the server resource to the clients based, at least in part, on the client requests, wherein the server resource has a total capacity N, and wherein in response to any given client request, the resource allocation module allocates not more than a bounded amount of resource S k to any given client, where the sum of S k for all clients at any given time does not exceed N; a logical clock that, during operation, assigns a unique logical timestamp to each of the client requests; and a physical clock t that, during operation, changes at a consistent rate over time to measure elapsed time relative to the server; wherein to determine the bounded amount of resource S k corresponding to a particular one of the clients, during operation, the resource allocation module: stores an earliest logical timestamp corresponding to an oldest outstanding granted request for use of the server resource by the particular client, and stores a window logical timestamp that divides granted requests by the particular client into two regions of logical time; determines a maximum outstanding quantity B of the server resource granted to the particular client for a request having a logical timestamp prior to the window logical timestamp; determines a maximum outstanding quantity A of the server resource granted to the particular client for a request having a logical timestamp subsequent to the window logical timestamp; and selects a maximum of A or B as the bounded amount of resource S k corresponding to the particular client.