Resource Allocation Mechanism

• US 20130212279A1
• Filed: 02/15/2012
• Published: 08/15/2013
• Est. Priority Date: 02/15/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dutta, Debojyoti, Banerjee, Subrata, Spiegel, Ethan, Shinde, Rajendra
• Granted Patent: US 9,535,764 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5061 Partitioning or combining of resources
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

A first network device determines capabilities of resources in a section of a network that is accessible using the first network device. The first network device groups the resources into a resource cluster. The first network device advertises the resource cluster in the network, wherein each of a plurality of network devices advertise a resource cluster associated with sections of the network. A second network device receives a request for providing a service. The second network device groups the request into a plurality of request clusters. The second network device selects at least one resource cluster for providing the service based on information associated with the request clusters and the advertised resource clusters. The second network device allocates resources included in the at least one resource cluster for providing the service based on selecting the at least one resource cluster.

Claims

1. A method comprising:

determining, using a first network device, capabilities of resources in a section of a network that is accessible using the first network device, wherein the first network device is one of a plurality of network devices providing access to resources in different sections of the network;

based on determining the capabilities of the resources, grouping, using the first network device, the resources into a resource cluster, wherein a resource cluster is a grouping of resources with similar features; and

advertising, using the first network device, the resource cluster in the network, wherein each of the plurality of network devices advertise a resource cluster associated with sections of the network that are accessible using each of the plurality of network devices.

2. The method of claim 1, wherein a resource is selected from a group including a computer, a server, a virtual machine (VM) running on a server, a switch and a router.

3. The method of claim 1, the method further comprising grouping the resources into a plurality of resource clusters using clustering, based on

determining within a pre-determined time interval, a similarity metric for each pair of resources associated with the section of the network that is accessible using the first network device,

selecting resources with values of the similarity metric that are higher than a pre-determined threshold,

including the selected resources in a resource cluster, and

for remaining resources that are not selected, determining the similarity metric for each pair of resources, selecting resources with values of the similarity metric that are higher than a pre-determined threshold, and including the selected resources in the resource cluster until the pre-determined time interval is expired.

4. The method of claim 3, wherein the similarity metric is associated with a weighted Euclidean distance, wherein the Euclidean distance is based on at least one feature selected from a group including bandwidth, central processing unit (CPU) speed and memory, and wherein weights used in determining the Euclidean distance are based on a policy of resource allocation.

5. The method of claim 3, wherein the similarity metric is associated with an expression based on at least one feature selected from a group including bandwidth, CPU speed and memory, wherein an evaluation of the expression results in a binary value.

6. The method of claim 1, further comprising:

receiving, at a second network device, advertisements from the plurality of network devices, wherein an advertisement includes information on a resource cluster;

receiving, at the second network device, a request for providing a service, the request including information related to a resource requirement for providing the service;

grouping, using the second network device and based on the information related to the resource requirement for providing the service, the request into a plurality of request clusters;

selecting, using the second network device and based on information associated with the request clusters and the advertised resource clusters, at least one resource cluster for providing the service; and

based on selecting at least one resource cluster for providing the service, allocating, using the second network device, resources included in the at least one resource cluster for providing the service.

7. The method of claim 6, wherein a request cluster includes a grouping of one or more components of the service.

8. The method of claim 6, wherein a request cluster includes a virtual machine (VM).

9. The method of claim 6, wherein the service includes a data center (DC) service.

10. The method of claim 6, wherein a number of the resource clusters selected for providing the service is at most same as a number of request clusters.

11. The method of claim 6, wherein selecting, using the second network device and based on information associated with the request clusters and the advertised resource clusters, at least one resource cluster for providing the service further includes:

determining, using the second network device and based on grouping the request into a plurality of request clusters, requirements of a plurality of parameters for the request clusters;

analyzing, using the second network device, capabilities of the resource clusters associated with the plurality of parameters;

based on analyzing the capabilities of the resource clusters, identifying, using the second network device, at least one resource cluster that has capabilities associated with the plurality of parameters similar to the determined requirements of the plurality of parameters for the request clusters; and

selecting, using the second network device, the at least one identified resource cluster for providing the service.

12. The method of claim 11, wherein analyzing, using the second network device, capabilities associated with plurality of parameters of the resource clusters further comprises:

removing from consideration for providing the service resource clusters with capabilities associated with the plurality of parameters that are not similar to the requirements of the plurality of parameters for the request clusters.

13. The method of claim 11, wherein the plurality of parameters are selected from a group including virtual machine (VM) features and available bandwidth of a resource cluster.

14. The method of claim 13, wherein the available bandwidth of a resource cluster is based on a committed information rate (CIR) associated with the resource cluster.

15. The method of claim 11, wherein identifying, using the second network device, at least one resource cluster that has capabilities associated with the plurality of parameters similar to the determined requirements of the plurality of parameters for the request clusters further comprises:

computing, using the second network device, a similarity metric between each request cluster and each resource cluster; and

for each request cluster, identifying a resource cluster that has a highest value of the similarity metric amongst all resource clusters.

16. The method of claim 15, wherein for a given request cluster, a resource cluster that has the highest value of the similarity metric is the resource cluster that has capabilities associated with the plurality of parameters most similar to the determined requirements of the plurality of parameters for the given request cluster.

17. A method comprising:

determining, using a first network device, capabilities of resources in a network;

based on determining the capabilities of the resources, grouping, using the first network device, the resources into a resource cluster, wherein a resource cluster is a grouping of a plurality of resources with similar features;

receiving, using the first network device, a request for providing a service, the request including information related to a resource requirement for providing the service;

grouping, using the first network device and based on the information related to the resource requirement for providing the service, the request into one or more request clusters, wherein a request cluster is a grouping of a plurality of components of the service with similar resource requirements;

selecting, using the first network device and based on information associated with the resource clusters and the request clusters, at least one resource cluster for providing the service; and

based on selecting at least one resource cluster for providing the service, allocating, using the first network device, resources included in the at least one resource cluster for providing the service.

18. A method for allocating resources using clustering, the method comprising:

determining, using a first network device, capabilities of resources in a network;

receiving, using the first network device, a request for providing a service, the request including information related to a resource requirement for providing the service;

grouping, using the first network device, the resources into a plurality of resource clusters based on the determined capabilities of the resources and the information related to a resource requirement for providing the service, wherein a resource cluster is a grouping of a plurality of resources with similar features;

selecting, using the first network device and based on information associated with the plurality of resource clusters and information associated with the request, at least one resource cluster for providing the service; and

based on selecting at least one resource cluster for providing the service, allocating, using the first network device, resources included in the at least one resource cluster for providing the service.

19. A non-transitory computer-readable medium storing software comprising instructions executable by one or more processors, which, upon such execution, cause the one or more processors to perform operations comprising:

determining, using a first network device, capabilities of resources in a section of a network that is accessible using the first network device, wherein the first network device is one of a plurality of network devices providing access to resources in different sections of the network;

based on determining the capabilities of the resources, grouping, using the first network device, the resources into a resource cluster, wherein a resource cluster is a grouping of resources with similar features; and

advertising, using the first network device, the resource cluster in the network, wherein each of the plurality of network devices advertise a resource cluster associated with sections of the network that are accessible using each of the plurality of network devices.

20. The computer-readable medium of claim 19, wherein the instructions cause the one or more processors to perform operations comprising grouping the resources into a plurality of resource clusters using clustering, based on

determining within a pre-determined time interval, a similarity metric for each pair of resources associated with the section of the network that is accessible using the first network device,

selecting resources with values of the similarity metric that are higher than a pre-determined threshold,

including the selected resources in a resource cluster, and

for remaining resources that are not selected, determining the similarity metric for each pair of resources, selecting resources with values of the similarity metric that are higher than a pre-determined threshold, and including the selected resources in the resource cluster until the pre-determined time interval is expired.

21. The computer-readable medium of claim 19, wherein the instructions cause the one or more processors to perform operations comprising:

receiving, at a second network device, advertisements from the plurality of network devices, wherein an advertisement includes information on a resource cluster;

receiving, at the second network device, a request for providing a service, the request including information related to a resource requirement for providing the service;

grouping, using the second network device and based on the information related to the resource requirement for providing the service, the request into a plurality of request clusters;

selecting, using the second network device and based on information associated with the request clusters and the advertised resource clusters, at least one resource cluster for providing the service; and

based on selecting at least one resource cluster for providing the service, allocating, using the second network device, resources included in the at least one resource cluster for providing the service.

22. The computer-readable medium of claim 21, wherein selecting, using the second network device and based on information associated with the request clusters and the advertised resource clusters, at least one resource cluster for providing the service comprises:

determining, using the second network device and based on grouping the request into a plurality of request clusters, requirements of a plurality of parameters for the request clusters;

analyzing, using the second network device, capabilities of the resource clusters associated with the plurality of parameters;

based on analyzing the capabilities of the resource clusters, identifying, using the second network device, at least one resource cluster that has capabilities associated with the plurality of parameters similar to the determined requirements of the plurality of parameters for the request clusters; and

selecting, using the second network device, the at least one identified resource cluster for providing the service.