Apparatus and method for matching offers and requests for sharing of resources

Patent metadata

Field	Value
Publication number	US-9535748-B2
Application number	US-201213370443-A
Country	US
Kind code	B2
Filing date	Feb 10, 2012
Priority date	Feb 10, 2012
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

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.

First claim

What is claimed is:

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

Assignees

• Viswanathan Ramesh
• Hari Adiseshu
• Chang Yuh-Jye
• Lakshman T V
• Alcatel Lucent

Inventors

• Viswanathan Ramesh
• Hari Adiseshu
• Chang Yuh-Jye
• Lakshman T V

Classifications

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F9/5005 Primary

  to service a request · CPC title