Apparatus and method for matching offers and requests for sharing of resources
A resource assignment capability is presented. A resource specification associated with a plurality of elements is received. The resource specification includes, for each of the elements, a resource request including an indication of a quantity of resources requested by the element and a resource offer including an indication of a quantity of resources offered by the element for use by one or more other elements. A resource assignment, including an indication of an association between the resources requests and the resource offers, is determined using a resource assignment process. The resource assignment process may be a greedy assignment process or a maximum flow resource assignment process. The maximum flow resource assignment process includes constructing a maximum flow resource graph based on the one or more resource specifications and applying a maximum flow process to the maximum flow resource graph to determine thereby the resource assignment.
1. An apparatus, comprising:
a processor and a memory communicatively coupled to the processor, the processor configured to:
receive one or more resource specifications associated with a plurality of elements, wherein the one or more resource specifications comprise, for each of the elements, a resource request comprising an indication of a quantity of resources requested by the element and a resource offer comprising an indication of a quantity of resources offered by the element for use by one or more other elements;
construct a maximum flow resource graph based on the one or more resource specifications; and
apply a maximum flow process to the maximum flow resource graph to determine thereby a resource assignment, the resource assignment comprising an indication of an association between the resource requests and the resource offers.
2. The apparatus of claim 1 , wherein the one or more resource specifications further comprises, for each of the elements, upper-bound constraint information indicating one or more upper-bound constraints on an amount of resources to be hosted for the element at one or more other elements.
3. The apparatus of claim 1 , wherein the one or more resource specifications further comprises, for each of the elements, cost information indicating a cost charged by the element for hosting resources of one or more other elements.
4. The apparatus of claim 1 , wherein, for constructing the maximum flow resource graph, the processor is configured to:
provide a source node and a sink node;
provide a plurality of request nodes associated with the respective plurality of resource requests of the one or more resource specifications;
provide a plurality of offer nodes associated with the respective plurality of resource offers of the one or more resource specifications;
provide a plurality of request edges between the source node and the respective request nodes, wherein the request edges are configured to represent the respective resources amounts associated with the resource requests;
provide a plurality of offer edges between the respective offer nodes and the sink node, wherein the offer edges are configured to represent the respective resources amounts associated with the resource offers; and
provide a plurality of sets of cross-edges between the request nodes and the offer nodes, wherein the cross-edge between one of the request nodes and one of the offer nodes is configured to represent an upper-bound constraint on an amount of resources that can be hosted at an offering element of the offer node on behalf of a requesting element of the requesting node.
5. A method, comprising:
using a processor and a memory for:
receiving one or more resource specifications associated with a plurality of elements, wherein the one or more resource specifications comprise, for each of the elements, a resource request comprising an indication of a quantity of resources requested by the element and a resource offer comprising an indication of a quantity of resources offered by the element for use by one or more other elements;
constructing a maximum flow resource graph based on the one or more resource specifications; and
applying a maximum flow process to the maximum flow resource graph to determine thereby a resource assignment, the resource assignment comprising an indication of an association between the resource requests and the resource offers.
6. The method of claim 5 , wherein the one or more resource specifications further comprises, for each of the elements, upper-bound constraint information indicating one or more upper-bound constraints on an amount of resources to be hosted for the element at one or more other elements.
7. The method of claim 5 , wherein the one or more resource specifications further comprises, for each of the elements, cost information indicating a cost charged by the element for hosting resources of one or more other elements.
8. The method of claim 5 , wherein constructing the maximum flow resource graph comprises:
providing a source node and a sink node;
providing a plurality of request nodes associated with the respective plurality of resource requests of the one or more resource specifications;
providing a plurality of offer nodes associated with the respective plurality of resource offers of the one or more resource specifications;
providing a plurality of request edges between the source node and the respective request nodes, wherein the request edges are configured to represent the respective resources amounts associated with the resource requests;
providing a plurality of offer edges between the respective offer nodes and the sink node, wherein the offer edges are configured to represent the respective resources amounts associated with the resource offers; and
providing a plurality of sets of cross-edges between the request nodes and the offer nodes, wherein the cross-edge between one of the request nodes and one of the offer nodes is configured to represent an upper-bound constraint on an amount of resources that can be hosted at an offering element of the offer node on behalf of a requesting element of the requesting node.
9. An apparatus, comprising:
a processor and a memory communicatively coupled to the processor, the processor configured to:
receive one or more resource specifications associated with a plurality of elements, wherein the one or more resource specifications comprise, for each of the elements, a resource request comprising an indication of a quantity of resources requested by the element, a resource offer comprising an indication of a quantity of resources offered by the element for use by one or more other elements, and upper-bound constraint information indicating one or more upper-bound constraints on an amount of resources to be hosted for the element at one or more other elements; and
determine, using a resource assignment process, a resource assignment comprising an indication of an association between the resource requests and the resource offers.
10. The apparatus of claim 9 , wherein the one or more resource specifications further comprises, for each of the elements, cost information indicating a cost charged by the element for hosting resources of one or more other elements.
11. The apparatus of claim 9 , wherein the resource assignment process comprises a greedy resource assignment process.
12. The apparatus of claim 9 , wherein the resource assignment process comprises a maximum flow resource assignment process.
13. The apparatus of claim 9 , wherein, when executing the maximum flow resource assignment process, the processor is configured to:
construct a maximum flow resource graph based on the one or more resource specifications; and
apply a maximum flow process to the maximum flow resource graph to determine thereby the resource assignment.
14. The apparatus of claim 13 , wherein, for constructing the maximum flow resource graph, the processor is configured to:
provide a source node and a sink node;
provide a plurality of request nodes associated with the respective plurality of resource requests of the one or more resource specifications;
provide a plurality of offer nodes associated with the respective plurality of resource offers of the one or more resource specifications;
provide a plurality of request edges between the source node and the respective request nodes, wherein the request edges are configured to represent the respective resources amounts associated with the resource requests;
provide a plurality of offer edges between the respective offer nodes and the sink node, wherein the offer edges are configured to represent the respective resources amounts associated with the resource offers; and
provide a plurality of sets of cross-edges between the request nodes and the offer nodes, wherein the cross-edge between one of the request nodes and one of the offer nodes is configured to represent an upper-bound constraint on an amount of resources that can be hosted at an offering element of the offer node on behalf of a requesting element of the requesting node.
15. A method, comprising:
using a processor and a memory for:
receiving one or more resource specifications associated with a plurality of elements, wherein the one or more resource specifications comprise, for each of the elements, a resource request comprising an indication of a quantity of resources requested by the element, a resource offer comprising an indication of a quantity of resources offered by the element for use by one or more other elements, and upper-hound constraint information indicating one or more upper-bound constraints on an amount of resources to be hosted for the element at one or more other elements; and
determining, using a resource assignment process, a resource assignment comprising an indication of an association between the resource requests and the resource offers.
16. The method of claim 15 , wherein the one or more resource specifications further comprises, for each of the elements, cost information indicating a cost charged by the element for hosting resources of one or more other elements.
17. The method of claim 15 , wherein the resource assignment process comprises a greedy resource assignment process.
18. The method of claim 15 , wherein the resource assignment process comprises a maximum flow resource assignment process.
19. The method of claim 15 , wherein executing the maximum flow resource assignment process comprises:
constructing a maximum flow resource graph based on the one or more resource specifications; and
applying a maximum flow process to the maximum flow resource graph to determine thereby the resource assignment.
20. The method of claim 19 , wherein constructing the maximum flow resource graph comprises:
providing a source node and a sink node;
providing a plurality of request nodes associated with the respective plurality of resource requests of the one or more resource specifications;
providing a plurality of offer nodes associated with the respective plurality of resource offers of the one or more resource specifications;
providing a plurality of request edges between the source node and the respective request nodes, wherein the request edges are configured to represent the respective resources amounts associated with the resource requests;
providing a plurality of offer edges between the respective offer nodes and the sink node, wherein the offer edges are configured to represent the respective resources amounts associated with the resource offers; and
providing a plurality of sets of cross-edges between the request nodes and the offer nodes, wherein the cross-edge between one of the request nodes and one of the offer nodes is configured to represent an upper-bound constraint on an amount of resources that can be hosted at an offering element of the offer node on behalf of a requesting element of the requesting node.