System and method for fair resource allocation

Patent metadata

Field	Value
Publication number	US-10831553-B2
Application number	US-201715589175-A
Country	US
Kind code	B2
Filing date	May 8, 2017
Priority date	Jan 23, 2017
Publication date	Nov 10, 2020
Grant date	Nov 10, 2020

Abstract

A system and method for fair resource allocation includes a method. The method includes determining demand for a plurality of communications features of a network. The method further includes determining resource allocations for virtual computing instances hosted by a plurality of servers. The virtual computing instances serve the communications features. The method further includes adjusting the resource allocations for the virtual computing instances according to the demand for the communications features and a fairness algorithm.

First claim

What is claimed is:

1. A method comprising:
determining demand for a plurality of communications features of a network, the plurality of communications features comprising a plurality of slices for end-to-end partitions of the network, each slice of the plurality of slices carrying traffic for a different network service of a plurality of network services;
determining resource allocations for virtual computing instances hosted on a plurality of servers, the virtual computing instances serving the communications features; and
adjusting the resource allocations for the virtual computing instances hosted on the plurality of servers according to the demand for the communications features and according to a fairness algorithm that is fair to the plurality of network services corresponding to the plurality of slices of the plurality of communications features, wherein the plurality of slices comprise a first slice and a second slice, and wherein the virtual computing instances comprise a first subset of virtual computing instances serving the first slice and a second subset of virtual computing instances serving the second slice, the adjusting comprising:
after a weight of the first slice increases:
increasing resources allocated for the first subset of virtual computing instances serving the first slice, and
decreasing resources allocated for the second subset of virtual computing instances serving the second slice,

wherein a first sum of the resources allocated for the first subset of virtual computing instances and the resources allocated for the second subset of virtual computing instances before the adjusting equals a second sum of the resources allocated for the first subset of virtual computing instances and the resources allocated for the second subset of virtual computing instances after the adjusting.

2. The method of claim 1 , wherein the fairness algorithm is a max-min fairness algorithm.

3. The method of claim 1 , wherein the fairness algorithm is an alpha fairness algorithm.

4. The method of claim 1 , wherein the fairness algorithm is a proportional fairness algorithm.

5. The method of claim 1 , wherein each slice of the plurality of slices having a corresponding weight.

6. The method of claim 5 , wherein the virtual computing instances virtualize networking functionality for the network.

7. The method of claim 5 , wherein the resource allocations for each of the virtual computing instances are determined for the each slice of the plurality of slices according to:
max Σ s w s log(X s ), and

Σ s∈j X s ≤C j ,

wherein X s indicates the resource allocations for the each slice of the plurality of slices, w s is the corresponding weight of the each slice of the plurality of slices, and C j is the capacity of the server hosting the computing instance.

8. The method of claim 1 , further comprising:
determining weights for the plurality of slices, wherein the resource allocations for the virtual computing instances are further adjusted according to the weights of the plurality of slices.

9. The method of claim 8 , further comprising:
adjusting the weights of the plurality of slices according to placement of the plurality of slices on the servers.

10. The method of claim 9 , wherein the adjusting the resource allocations for the virtual computing instances further comprises:
optimizing the resource allocations for each of the servers.

11. A device comprising:
a processor; and
a non-transitory computer readable storage medium storing programming for execution by the processor, the programming including instructions for:
determining demand for a plurality of communications features of a network, the plurality of communications features comprising a plurality of slices for end-to-end partitions of the network, and each slice of the plurality of slices carrying traffic for a different network service of a plurality of network services;
determining resource allocations for virtual computing instances hosted on a plurality of servers, the virtual computing instances serving the communications features; and
adjusting the resource allocations for the virtual computing instances hosted on the plurality of servers according to the demand for the communications features and according to a fairness algorithm that is fair to the plurality of network services corresponding to the plurality of slices of the plurality of communications features, wherein the plurality of slices comprise a first slice and a second slice, and wherein the virtual computing instances comprise a first subset of virtual computing instances serving the first slice and a second subset of virtual computing instances serving the second slice, the adjusting comprising:
after a weight of the first slice increases:
increasing resources allocated for the first subset of virtual computing instances serving the first slice, and
decreasing resources allocated for the second subset of virtual computing instances serving the second slice,

wherein a first sum of the resources allocated for the first subset of virtual computing instances and the resources allocated for the second subset of virtual computing instances before the adjusting equals a second sum of the resources allocated for the first subset of virtual computing instances and the resources allocated for the second subset of virtual computing instances after the adjusting.

12. The device of claim 11 , wherein the fairness algorithm is a max-min fairness algorithm.

13. The device of claim 11 , wherein the fairness algorithm is an alpha fairness algorithm.

14. The device of claim 11 , wherein the fairness algorithm is a proportional fairness algorithm.

15. The device of claim 11 , wherein each slice of the plurality of slices having a corresponding weight.

16. The device of claim 15 , wherein the virtual computing instances virtualize networking functionality for the network.

17. The device of claim 15 , wherein the resource allocations for each of the virtual computing instances are determined for the each slice of the plurality of slices according to:
max Σ s w s log(X s ), and

Σ s∈j X s ≤C j ,

wherein X s indicates the resource allocations for the each slice of the plurality of slices, w s is the corresponding weight of the each slice of the plurality of slices, and C j is the capacity of the server hosting the computing instance.

18. The device of claim 11 , wherein the programming includes further instructions for:
determining weights for the plurality of slices, wherein the resource allocations for the virtual computing instances are further adjusted according to the weights of the plurality of slices.

19. The device of claim 18 , wherein the programming includes further instructions for:
adjusting the weights of the plurality of slices according to placement of the plurality of slices on the servers.

20. The device of claim 19 , wherein the adjusting the resource allocations for the virtual computing instances further comprises:
optimizing the resource allocations for each of the servers.

21. A method comprising:
determining parameters for a plurality of slices of a network, the plurality of slices being logical end-to-end partitions of the network, each slice of the plurality of slices carrying traffic for a different network service of a plurality of network services;
placing the plurality of slices on a plurality of servers, each of the servers having a plurality of virtual computing instances, each of the pl

Assignees

• Huawei Tech Co Ltd

Inventors

• Mccormick William Carson
• Kelly Francis Patrick

Classifications

• G06F9/5077 Primary

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F9/45504

  Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators · CPC title