Method and system for allocating limited resources to entities that reveal their stochastic demands on arrival over a finite horizon in a proportionally fair manner

1 . A method executed by at least one processor, the method comprising:

receiving, by the at least one processor from a first entity, a first request for an allocation of a first amount of a cloud computing resource for the first entity, wherein the cloud computing resource has a predetermined maximum amount of the cloud computing resource available for allocation during a predetermined time interval, and wherein the allocation is an irrevocable allocation;

fulfilling, by the first entity responsive to an actual allocation of the first amount of the cloud computing resource to the first entity, the first request, wherein:

utility of the first entity is increased and the first amount of the cloud computing resource is removed from the predetermined maximum amount of the cloud computing resource responsive to the actual allocation of the first amount of the cloud computing resource to the first entity,

the first amount is less than the predetermined maximum amount of the cloud computing resource,

the first amount of the cloud computing resource is based on a first adjustment to a standard deviation of an uncertainty of an estimated number of a first plurality of future requests to be received by the at least one processor and amounts of the cloud computing resource estimated to be requested within the predetermined time interval prior to receiving the estimated number of first plurality of future requests, and

the first plurality of future requests are to be received by the at least one processor sequentially and subsequent to the first request,

when the actual allocation of the cloud computing resource has been made to the first entity, the predetermined time interval has not elapsed, and there is at least one unfulfilled future request of the plurality of future requests:

the maximum amount of the cloud computing resource that remains available for allocation based on the actual allocation of the cloud computing resource that has been made to the first entity is updated, and

a second amount of the cloud computing resource to be sequentially allocated to a second entity is based on a second adjustment to a standard deviation of an uncertainty of an estimated number of a second plurality of future requests to be received by the at least one processor and amounts of the cloud computing resource of the updated maximum amount of the cloud computing resource that remains available for allocation estimated to be requested within the predetermined time interval prior to receiving the estimated number of second plurality of future requests, wherein the second plurality of future requests are to be received by the at least one processor sequentially and subsequent to the first plurality of future requests; and

fulfilling, by the second entity, a sequential allocation of the second amount of the cloud computing resource to the second entity, wherein:

the sequential allocation occurs subsequent to the actual allocation of the first amount of the cloud computing resource to the first entity,

the second amount is different from the first amount, and

the second entity is different from the first entity.

2 . The method of claim 1 , wherein the actual allocation of the first amount of the cloud computing resource to the first entity is further based on a first algorithm associated with the predetermined maximum amount of the cloud computing resource and the first adjustment.

3 . The method of claim 2 , wherein the first algorithm optimizes a Nash Social Welfare (NSW) objective that is generalized for sequential settings.

4 . The method of claim 1 , further comprising: when the predetermined time interval has elapsed, an optimal hindsight allocation of the cloud computing resource with respect to the first entity is based on actual numbers of requests and the amounts of the cloud computing resource estimated to be requested during the predetermined time interval.

5 . The method of claim 4 , wherein a fairness metric that corresponds to the first entity is based on the optimal hindsight allocation with respect to at least one from among the first amount and the second amount.

6 . A computing apparatus comprising:

a processor;

a memory; and

a communication interface coupled to each of the processor and the memory, wherein the processor is configured to:

receive, via the communication interface from a first entity, a first request for an allocation of a first amount of a cloud computing resource for the first entity, wherein the cloud computing resource has a predetermined maximum amount of the cloud computing resource available for allocation during a predetermined time interval, and wherein the allocation is an irrevocable allocation;

fulfill, by the first entity responsive to an actual allocation of the first amount of the cloud computing resource to the first entity, the first request, wherein:

utility of the first entity is increased and the first amount of the cloud computing resource is removed from the predetermined maximum amount of the cloud computing resource responsive to the actual the allocation of the first amount of the cloud computing resource to the first entity,

the first amount is less than the predetermined maximum amount of the cloud computing resource,

the first amount of the cloud computing resource is based on a first adjustment to a standard deviation of an uncertainty of an estimated number of a first plurality of future requests to be received by the at least one processor and amounts of the cloud computing resource estimated to be requested within the predetermined time interval prior to receiving the estimated number of first plurality of future requests, and

the first plurality of future requests are to be received by the communication interface sequentially and subsequent to the first request,

when the actual allocation of the cloud computing resource has been made to the first entity, the predetermined time interval has not elapsed, and there is at least one unfulfilled future request of the plurality of future requests:

the maximum amount of the cloud computing resource that remains available for allocation based on the allocation of the cloud computing resource that has been made to the first entity is updated, and

a second amount of the cloud computing resource to be sequentially allocated to a second entity is based on a second adjustment to a standard deviation of an uncertainty of an estimated number of a second plurality of future requests to be received by the communication interface and amounts of the cloud computing resource of the updated maximum amount of the cloud computing resource that remains available for allocation estimated to be requested within the predetermined time interval prior to receiving the estimated number of second plurality of future requests, wherein the second plurality of future requests are to be received by the communication interface sequentially and subsequent to the first plurality of future requests; and

fulfill, by the second entity, a sequential allocation of the second amount of the cloud computing resource to the second entity, wherein:

the sequential allocation occurs subsequent to the actual allocation of the first amount of the cloud computing resource to the first entity,

the second amount is different from the first amount, and

the second entity is different from the first entity.

7 . The computing apparatus of claim 6 , wherein the actual allocation of the first amount of the cloud computing resource to the first entity is further based on a first algorithm associated with the predetermined maximum amount of the cloud computing resource and the first adjustment.

8 . The computing apparatus of claim 7 , wherein the first algorithm optimizes a Nash Social Welfare (NSW) objective that is generalized for sequential settings.

9 . The computing apparatus of claim 6 , wherein when the predetermined time interval has elapsed, an optimal hindsight allocation of the cloud computing resource with respect to the first entity is based on actual numbers of requests and the amounts of the cloud computing resource estimated to be requested during the predetermined time interval.

10 . The computing apparatus of claim 9 , wherein a fairness metric that corresponds to the first entity is based on the optimal hindsight allocation with respect to at least one from among the first amount and the second amount.

11 . A non-transitory computer readable storage medium storing instructions which, when executed by a processor, causes the processor to:

receive, by the processor from a first entity, a first request for an allocation of a first amount of a cloud computing resource for the first entity, wherein the cloud computing resource has a predetermined maximum amount of the cloud computing resource available for allocation during a predetermined time interval, and wherein the allocation is an irrevocable allocation;

fulfill, by the first entity responsive to an actual allocation of the first amount of the cloud computing resource to the first entity, the first request, wherein:

utility of the first entity is increased and the first amount of the cloud computing resource is removed from the predetermined maximum amount of the cloud computing resource responsive to the actual the allocation of the first amount of the cloud computing resource to the first entity,

the first amount is less than the predetermined maximum amount of the cloud computing resource,

the first amount of the cloud computing resource is based on a first adjustment to a standard deviation of an uncertainty of an estimated number of a first plurality of future requests to be received by the at least one processor and amounts of the cloud computing resource estimated to be requested within the predetermined time interval prior to receiving the estimated number of first plurality of future requests, and

the first plurality of future requests are to be received by the processor sequentially and subsequent to the first request,

when the actual allocation of the cloud computing resource has been made to the first entity, the predetermined time interval has not elapsed, and there is at least one unfulfilled future request of the plurality of future requests:

the maximum amount of the cloud computing resource that remains available for allocation based on the allocation of the cloud computing resource that has been made to the first entity is updated, and

a second amount of the cloud computing resource to be sequentially allocated to a second entity is based on a second adjustment to a standard deviation of an uncertainty of an estimated number of a second plurality of future requests to be received by the processor and amounts of the cloud computing resource of the updated maximum amount of the cloud computing resource that remains available for allocation estimated to be requested within the predetermined time interval prior to receiving the estimated number of second plurality of future requests, wherein the second plurality of future requests are to be received by the processor sequentially and subsequent to the first plurality of future requests; and

fulfill, by the second entity, a sequential allocation of the second amount of the cloud computing resource to the second entity, wherein:

the sequential allocation occurs subsequent to the actual allocation of the first amount of the cloud computing resource to the first entity,

the second amount is different from the first amount, and

the second entity is different from the first entity.

12 . The storage medium of claim 11 , wherein the actual allocation of the first amount of the cloud computing resource to the first entity is further based on a first algorithm associated with the predetermined maximum amount of the cloud computing resource and the first adjustment.

13 . The storage medium of claim 12 , wherein the first algorithm optimizes a Nash Social Welfare (NSW) objective that is generalized for sequential settings.

14 . The storage medium of claim 11 , wherein when the predetermined time interval has elapsed, an optimal hindsight allocation of the cloud computing resource with respect to the first entity is based on actual numbers of requests and the amounts of the cloud computing resource estimated to be requested during the predetermined time interval.

15 . Storage medium of claim 14 , wherein a fairness metric that corresponds to the first entity is based on the optimal hindsight allocation with respect to at least one from among the first amount and the second amount.