Multi-dimensional computing and communication resource allocation using bin-packing with per-branch combination tries
First Claim
1. A computer system comprising a processor for executing program instructions coupled to a memory for storing the program instructions, wherein the program instructions are program instructions for assigning a plurality of resource consumers to groups of computing or communications resources, and wherein the program instructions comprise:
- program instructions for first determining resource requirement vectors corresponding to the plurality of resource consumers, wherein the resource vectors contain values specifying resource amounts for multiple types of required resources for the corresponding resource consumer; and
program instructions for assigning the resource consumers to corresponding ones of the groups of computing or communication resources by executing program instructions implementing a bin-packing algorithm that recursively explores partial solutions for assigning the resource consumers to individual ones of the groups of computing or communication resources in order to satisfy the resource requirement vectors for the plurality of resource consumers, wherein the bin-packing algorithm extends the partial solutions via nested recursion that descends via repetitive invocations of the bin-packing algorithm from within the bin-packing algorithm, wherein the nested recursion descends until the requirements in the resource requirement vectors are met by assignment of individual groups of the resources that are sufficient to satisfy the resource amounts for the multiple types specified in a corresponding resource requirement vector, wherein the bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers.
1 Assignment
0 Petitions
Accused Products
Abstract
A recursive solution to a bin-packing algorithm provides efficient allocation of computing or communications resources to resource consumers in a computer or network system. The algorithm determines resource requirement vectors for the consumers that specify amounts of multiple resource types required for each consumer, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the resource consumers to corresponding groups of computing or communication resources by recursively exploring partial solutions that assign the consumers to the groups by extending the partial solutions via recursion until the requirements in the resource requirement vectors are met. The bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers.
-
Citations
13 Claims
-
1. A computer system comprising a processor for executing program instructions coupled to a memory for storing the program instructions, wherein the program instructions are program instructions for assigning a plurality of resource consumers to groups of computing or communications resources, and wherein the program instructions comprise:
-
program instructions for first determining resource requirement vectors corresponding to the plurality of resource consumers, wherein the resource vectors contain values specifying resource amounts for multiple types of required resources for the corresponding resource consumer; and program instructions for assigning the resource consumers to corresponding ones of the groups of computing or communication resources by executing program instructions implementing a bin-packing algorithm that recursively explores partial solutions for assigning the resource consumers to individual ones of the groups of computing or communication resources in order to satisfy the resource requirement vectors for the plurality of resource consumers, wherein the bin-packing algorithm extends the partial solutions via nested recursion that descends via repetitive invocations of the bin-packing algorithm from within the bin-packing algorithm, wherein the nested recursion descends until the requirements in the resource requirement vectors are met by assignment of individual groups of the resources that are sufficient to satisfy the resource amounts for the multiple types specified in a corresponding resource requirement vector, wherein the bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer program product comprising a computer-readable storage device that is not a signal or carrier wave storing program instructions for assigning a plurality of resource consumers to groups of computing or communications resources, wherein the program instructions are program instructions for:
-
first determining resource requirement vectors corresponding to the plurality of resource consumers, wherein the resource vectors contain values specifying resource amounts for multiple types of required resources for the corresponding resource consumer; and assigning the resource consumers to corresponding ones of the groups of computing or communication resources by executing program instructions implementing a bin-packing algorithm that recursively explores partial solutions for assigning the resource consumers to individual ones of the groups of computing or communication resources in order to satisfy the resource requirement vectors for the plurality of resource consumers, wherein the bin-packing algorithm extends the partial solutions via nested recursion that descends via repetitive invocations of the bin-packing algorithm from within the bin-packing algorithm, wherein the nested recursion descends until the requirements in the resource requirement vectors are met by assignment of individual groups of the resources that are sufficient to satisfy the resource amounts for the multiple types specified in a corresponding resource requirement vector, wherein the bin-packing algorithm tests resource requirements vectors for remaining unassigned ones of the resource consumers for both assignment and non-assignment to a current individual group of computing or communications resources in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of resource consumers. - View Dependent Claims (9, 10, 11, 12, 13)
-
Specification