Resource allocation protocol for a virtualized infrastructure with reliability guarantees

• US 10,057,339 B2
• Filed: 08/22/2014
• Issued: 08/21/2018
• Est. Priority Date: 07/31/2009
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Yeow, Wai-Leong, Westphal, Cedric, Kozat, Ulas
• Primary Examiner(s): Meky, Moustafa M
• Assistant Examiner(s): Rubin, Blake
• Application Number:
  US14/466,856
• Publication Number:
  US 20140365664A1
• Time in Patent Office: 1,460 Days
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions

Abstract

A method and apparatus is disclosed herein for a resource allocation protocol. In one embodiment, the apparatus comprises a resource allocation engine to allocate physical resources to primary and redundant virtual infrastructures, wherein, when the resource allocation engine allocates virtual infrastructures, physical resources of redundant virtual infrastructures are shared across multiple primary virtual infrastructures.

Claims

1. A resource allocation method for allocating physical resources to primary and redundant virtual infrastructures, the method comprising:

receiving a first request for a set of resources, links connecting the resources, and a requested reliability requirement; and

computing a number of redundant nodes to provide the requested reliability based on a probability of joint failure of at least two resources from the set of resources, including provisioning k redundant virtual resources with links to each of the set of resources, wherein the k redundant virtual resources are back up resources for any of n number of primary resources to achieve n;

k replication that satisfies the requested reliability requirement, where n is the number of primary resources, k is the number of redundant virtual resources, and k is less than n.

2. The method defined in claim 1 wherein each of the resources comprises a node.

3. The method defined in claim 1 wherein the physical resources comprise compute capacity and bandwidth.

4. The method defined in claim 1 further comprising determining redundant links to insert between nodes.

5. The method defined in claim 1 further comprising:

computing respective reliabilities of the first request and that of an existing, allocated request when redundant resources of the existing, allocated request are shared with the first request;

determining whether to combine redundant resources of the first request with that of the existing, allocated request based on the computed reliabilities and available physical resources; and

combining the redundant resources of the first request with that of the existing, allocated request based on results of determining whether to combine redundant resources of the first request with that of the existing, allocated request.

6. The method defined in claim 1 wherein the resources comprises server resources and links connecting these resources.

7. The method defined in claim 1 wherein the reliability requirement relates to at least one application.

8. The method defined in claim 1 further comprising modeling bandwidth reservations between virtual nodes as flows.

9. The method defined in claim 1 further comprising modeling bi-directional mappings between a physical node and a virtual or redundant node with a binary variable.

10. The method defined in claim 1 wherein each virtual node is only mapped on a single physical node, and no more than one virtual node is mapped onto one physical mode.

11. An article of manufacture having one or more recordable storage media storing instruction thereon which when executed by a system cause the system to perform a method for allocating physical resources to primary and redundant virtual infrastructures, the method comprising:

receiving a first request for a set of resources, links connecting the resources, and a requested reliability requirement; and

computing a number of redundant nodes to provide the requested reliability based on a probability of joint failure of at least two resources from the set of resources, including provisioning k redundant virtual resources with links to each of the set of resources, wherein the k redundant virtual resources are back up resources for any of n number of primary resources to achieve n;

k replication that satisfies the requested reliability requirement, where n is the number of primary resources, k is the number of redundant virtual resources, and k is less than n.

12. The article of manufacture defined in claim 11 wherein each of the resources comprises a node.

13. The article of manufacture defined in claim 11 wherein the physical resources comprise compute capacity and bandwidth.

14. The article of manufacture defined in claim 11 wherein the method further comprises determining redundant links to insert between nodes.

15. The article of manufacture defined in claim 11 wherein the method further comprises:

computing respective reliabilities of the first request and that of an existing, allocated request when redundant resources of the existing, allocated request are shared with the first request;

determining whether to combine redundant resources of the first request with that of the existing, allocated request based on the computed reliabilities and available physical resources; and

combining the redundant resources of the first request with that of the existing, allocated request based on results of determining whether to combine redundant resources of the first request with that of the existing, allocated request.

16. The article of manufacture defined in claim 11 wherein the resources comprises server resources and links connecting these resources.

17. The article of manufacture defined in claim 11 wherein the reliability requirement relates to at least one application.

18. The article of manufacture defined in claim 11 wherein the method further comprises modeling bandwidth reservations between virtual nodes as flows.