OPTIMIZING TRAFFIC LOAD IN A COMMUNICATIONS NETWORK

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

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Allan, David Ian, Garg, Vipin
• Granted Patent: US 8,862,744 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45591 Monitoring or debugging support
• CPC Class Codes: G06F 2009/45595 Network integration; Enabling network access in virtual machine instances
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04N 21/4437 Implementing a Virtual Machine [VM] virtual machines in general G06F9/45533

Abstract

A system and method that facilitates the migration of one or more Virtual Machines (VMs) throughout a communications network, such as a cloud network, is disclosed. A management system monitors a current traffic matrix to determine if the network is congested. If the network is congested, the management system determines a minimum number of VMs that must be migrated to unused VM sites to ease the congestion and optimize the distribution of traffic in the network. Additionally, the management system also identifies which VMs should be migrated to which unused VM sites, and a sequence in which the migration should be performed to return the bandwidth distribution in the network to an acceptable level. In addition, the management system may determine which unused VM site or sites is best for the addition of one or more new VMs or groups of VMs.

Claims

1. A method of optimizing traffic in a communications network, the method comprising:

monitoring traffic communicated by a plurality of Virtual Machines (VMs) over one or more paths through the network, each path comprised of one or more constituent links;

generating a set of candidate VM sites, each candidate VM site comprising an unused VM site in the network;

generating a set of congested VMs from the plurality of VMs in the network, wherein each congested VM is determined to be communicating with at least one other VM over a path having at least one congested link;

ranking the congested VMs based on one or more predefined criteria; and

modeling the migration of one or more congested VMs to one or more candidate VM sites to;

determine a minimum number of congested VMs to migrate to corresponding candidate VM sites to optimize the traffic through the network; and

identify which congested VMs to migrate to which candidate VM sites.

2. The method of claim 1 wherein monitoring traffic in a communications network comprises analyzing a bandwidth utilization for one or more links comprising a path communicatively connecting a given pair of VMs.

3. The method of claim 1 wherein generating the set of congested VMs comprises adding a VM to the set of congested VMs if a bandwidth utilization for a link in a path connecting the VM to a peer VM equals or exceeds a first predetermined threshold.

4. The method of claim 1 further comprising calculating, for each congested VM:

a congestion index by counting the number of congested links in the one or more paths communicatively connecting a congested VM to its peer VMs in the network;

a correction index by computing the number of congested links that would no longer be congested if the traffic being communicated from the congested VM was removed from the network; and

a consumption index as a function of cumulative bandwidth utilization summed over all of the links in the paths connecting the congested VM to each of its peer VMs.

5. The method of claim 4 wherein ranking the congested VMs based on one or more predetermined criteria comprises ordering the set of congested VMs based on one or more of the correction index, the consumption index, and the congestion index.

6. The method of claim 1 wherein modeling the migration of one or more congested VMs comprises recursively searching the set of potential VM migrations by modeling the migration of one or more of the congested VMs to selected candidate VM sites based on the ranking of the congested VMs.

7. The method of claim 6 wherein modeling the migration of one or more of the congested VMs based on the ranking of the congested VMs comprises modeling the migration of those congested VMs that have a ranking exceeding a predetermined value.

8. The method of claim 1 wherein modeling the migration of one or more congested VMs to one or more candidate VM sites further comprises determining a sequence in which to migrate the identified congested VMs to the identified candidate VM sites.

9. The method of claim 1 wherein determine a minimum number of congested VMs to migrate to corresponding candidate VM sites comprises:

selecting a range of correction index values; and

for each congested VM having a correction index within the selected range of correction index values, determining a set of possible candidate VM sites to which to migrate the congested VM.

10. The method of claim 9 wherein determining the set of possible candidate VM sites to which to migrate the congested VM comprises modeling the migration of the congested VM to a first candidate VM site.

11. The method of claim 10 further comprising modeling the migration of the congested VM to a second candidate VM site if migrating the congested VM to the first candidate VM site would:

cause one or more other links in the network to become congested;

increase the congestion on one or more of the links connecting the congested VM to one or more of its peer VMs;

or

cause the congested VM to have a consumption index that exceeds either its current consumption index, or exceed a predefined minimum consumption index.

12. The method of claim 10 further comprising:

determining whether migrating the congested VM to the first candidate VM site would ease congestion on one or more other links in the network; and

if the migration would ease congestion on the one or more other links;

updating values for each of the remaining congested VMs in the set of congested VMs to indicate the eased congestion; and

removing a remaining congested VM from the set of congested VMs if the updated values for the remaining congested VM meets or exceeds a predetermined threshold.

13. The method of claim 12 wherein modeling the migration of one or more congested VMs to one or more candidate VM sites comprises:

re-ranking the remaining congested VMs based on the predetermined criteria; and

based on the re-ranking sequence and on a predefined exit criteria, recursively processing the remaining congested VMs with respect to the candidate VM sites to;

determine the minimum number of congested VMs to migrate to the corresponding candidate VM sites to optimize the traffic through the network;

identify which of the remaining congested VMs to migrate to which of the candidate VM sites; and

identify a sequence in which to migrate the identified congested VMs to the identified candidate VM sites.

14. The method of claim 1 further comprising displaying the identification of the congested VMs and the candidate VM sites to the user on a display.

15. A network element configured to optimize traffic in a communications network, the network element comprising:

a communications interface configured to send data to and receive data from a plurality of Virtual Machines (VMs) communicating over one or more paths through the network, each path comprised of one or more constituent links; and

a programmable controller configured to;

monitor traffic communicated by the plurality of VMs over the network paths;

generate a set of candidate VM sites, each candidate VM site comprising an unused VM site in the network;

generate a set of congested VMs from the plurality of VMs in the network, wherein each congested VM is determined to be communicating with at least one other VM over a path having at least one congested link;

rank the congested VMs based on one or more predefined criteria; and

model the migration of one or more congested VMs to one or more candidate VM sites to;

determine a minimum number of congested VMs to migrate to corresponding candidate VM sites to optimize the traffic through the network; and

identify which congested VMs to migrate to which candidate VM sites.

16. The network element of claim 15 wherein the controller is further programmed to analyze bandwidth utilization for one or more links comprising a path communicatively connecting a given pair of VMs.

17. The network element of claim 15 wherein to generate the set of congested VMs, the controller is further configured to add a VM to the congested set of VMs if a bandwidth utilization for a link in a path connecting the VM to a peer VM equals or exceeds a first predetermined threshold.

18. The network element of claim 15 wherein the controller is further configured to calculate, for each congested VM:

a congestion index indicating the number of congested links in the one or more paths communicatively connecting a congested VM to its peer VMs in the network;

a correction index indicating the number of congested links that would no longer be congested if the traffic being communicated from the congested VM was removed from the network; and

a consumption index indicating a cumulative bandwidth utilization summed for the congested VM over all the links in the paths connecting the congested VM to each of its peer VMs.

19. The network element of claim 18 wherein the controller is further configured to rank the congested VMs based on one or more of the correction index, the consumption index, and the congestion index.

20. The network element of claim 15 wherein the controller is further configured to recursively search the set of potential VM migrations by modeling the migration of one or more of the congested VMs to selected candidate VM sites based on the ranking of the congested VMs.

21. The network element of claim 20 wherein the controller is further configured to model the migration of the congested VMs that have a ranking exceeding a predetermined value.

22. The network element of claim 15 wherein the controller is further configured to determine a sequence in which to migrate the identified congested VMs to the identified candidate VM sites.

23. The network element of claim 15 wherein to determine the minimum number of congested VMs to migrate to corresponding candidate VM sites, the controller is further configured to:

select a range of correction index values; and

for each congested VM having a correction index within the selected range of correction index values, determine a set of possible candidate VM sites to which to migrate the congested VM.

24. The network element of claim 23 wherein the controller is further configured to model the migration of the congested VM to a first candidate VM site.

25. The network element of claim 24 wherein the controller is further configured to model the migration of the congested VM to a second candidate VM site if migrating the congested VM to the first candidate VM site would:

cause one or more other links in the network to become congested;

increase the congestion on one or more of the links connecting the congested VM to one or more of its peer VMs;

or

cause the congested VM to have a consumption index that exceeds either its current consumption index, or exceed a predefined minimum consumption index.

26. The network element of claim 24 wherein the controller is further configured to:

determine whether migrating the congested VM to the first candidate VM site would ease congestion on one or more other links in the network; and

if the migration would ease congestion on the one or more other links;

update values for each of the remaining congested VMs in the set of congested VMs to indicate the eased congestion; and

remove a remaining congested VM from the set of congested VMs if the updated values for the remaining congested VM equals or exceeds a predetermined threshold.

27. The network element of claim 26 wherein the controller is further configured to:

re-rank the remaining congested VMs based on the predetermined criteria; and

based on the re-ranking sequence and on a predefined exit criteria, recursively process the remaining congested VMs with respect to the candidate VM sites to;

determine the minimum number of congested VMs to migrate to the corresponding candidate VM sites to optimize the traffic through the network;

identify which of the remaining congested VMs to migrate to which of the candidate VM sites; and

identify a sequence in which to migrate the identified congested VMs to the identified candidate VM sites.

28. The network element of claim 15 further comprising a display, and wherein the controller is further configured to output the identification of the congested VMs and the candidate VM sites to the display for the user.

29. A method of optimizing traffic in a communications network having a plurality of Virtual Machines (VMs) communicating over paths comprised of one or more constituent links, the method comprising:

generating a set of candidate VM sites, each candidate VM site comprising an unused VM site in the network;

modeling a traffic matrix for the network as if a new VM to be added to the network were instantiated at a selected candidate VM site; and

instantiating the new VM at the selected candidate site if the modeled traffic matrix indicates that one or more links connecting the new VM to its peer VMs would not be congested.

30. The method of claim 29 wherein modeling the traffic matrix for the network comprises determining resource requirements for the new VM at the candidate site.

31. The method of claim 30 wherein instantiating the new VM at the selected candidate site comprises instantiating the new VM if the resource requirements do not equal or exceed a minimum threshold.

32. The method of claim 29 further comprising:

counting a number of links that would exceed a predefined bandwidth threshold if the new VM were instantiated at the candidate site; and

determining that one or more of the links in the network will become congested if the number of links counted equals or exceeds a predetermined threshold.

33. The method of claim 32 further comprising selecting another candidate site for the new VM if it is determined that one or more of the links in the network will become congested.

34. The method of claim 29 further comprising computing an estimated consumption index for the new VM as if the new VM were operating at the selected candidate site, the estimated consumption index indicating an estimated cumulative bandwidth utilization for the new VM over all the links in the paths that would connect the new VM to each of one or more peer VMs.

35. The method of claim 34 wherein instantiating the new VM at the selected candidate site further comprises instantiating the new VM if the estimated consumption index is less than a predetermined value.

36. A network element configured to optimize traffic in a communications network, the network element comprising:

a communications interface configured to send data to, and receive data from, a plurality of Virtual Machines (VMs) communicating over one or more paths through the network, each path comprised of one or more constituent links; and

a programmable controller configured to;

generate a set of candidate VM sites, each candidate VM site comprising an unused VM site;

model a traffic matrix for the network as if a new VM to be added to the network were instantiated at a selected candidate VM site; and

indicate that the new VM should be instantiated at the selected candidate site if the modeled traffic matrix indicates that one or more of the links connecting the new VM to its peer VMs would not be congested.

37. The network element of claim 36 wherein to model the traffic matrix for the network, the controller is further configured to determine resource requirements for the new VM at the candidate site.

38. The network element of claim 37 wherein the controller is configured to indicate that the new VM should be instantiated at the selected candidate VM site if the resource requirements do not equal or exceed a minimum threshold.

39. The network element of claim 36 wherein the controller is further configured to:

compute a number of links that would exceed a predefined bandwidth threshold if the new VM were instantiated at the candidate site; and

determine that one or more of the links in the network will become congested if the number of links counted equals or exceeds a predetermined threshold.

40. The network element of claim 39 wherein the controller is further configured to select another candidate site for the new VM if the controller determines that one or more of the links in the network will become congested.

41. The network element of claim 36 wherein the controller is further configured to calculate an estimated consumption index for the new VM as if the new VM were operating at the selected candidate site to estimate a cumulative bandwidth utilization for the new VM over all the links in the paths that would connect the new VM to each of one or more peer VMs.

42. The network element of claim 41 wherein the controller is configured to indicate that the new VM should be instantiated if the estimated consumption index is less than a predetermined value.

43. A method of optimizing traffic in a communications network having a plurality of Virtual Machines (VMs) communicating over paths comprised of one or more constituent links, the method comprising:

generating a set of candidate VM site pairs, each candidate VM site pair communicatively connected by a path comprised of one or more constituent links, each link having an available link bandwidth;

identifying one or more pairs of new VMs to be instantiated in the network, each new VM pair having a bandwidth requirement;

selecting the new VM pair having the highest bandwidth requirement;

ranking each candidate VM site pair based on the number of links in the path connecting each candidate VM site pair; and

selecting a candidate VM site pair for the selected VM pair based on the ranking.

44. The method of claim 43 wherein ranking each candidate VM site pair further comprises ranking each candidate VM site pair based on the available link bandwidth.

45. The method of claim 44 further comprising removing each candidate VM site pair from the set of candidate VM site pairs having an available link bandwidth that is less than bandwidth requirement of the selected VM pair.

46. The method of claim 43 wherein, for the remaining candidate VM site pairs, the method further comprises modeling a traffic matrix as if the selected VM site pair were instantiated at the selected candidate VM site pair.

47. The method of claim 46 further comprising adjusting the link bandwidth between the selected candidate VM site pairs based on the bandwidth requirement of the selected VM pair.

48. The method of claim 43 further comprising:

calculating an estimated consumption index for each new VM to be added to the network; and

summing the estimated consumption index to compute an estimated cumulative bandwidth utilization for the new VM over all the links in the paths that would connect the new VM to each of one or more peer VMs.

49. The method of claim 48 further comprising:

comparing the estimated cumulative bandwidth utilization to a predefined threshold value; and

identifying the selected candidate VM site pairs to receive the selected VM pair based on the comparison.

50. A network element configured to optimize traffic in a communications network, the network element comprising:

a communications interface configured to send data to, and receive data from, a plurality of Virtual Machines (VMs) communicating over one or more paths through the network, each path comprised of one or more constituent links, each link having an available link bandwidth; and

a programmable controller configured to;

identify one or more pairs of new VMs to be instantiated in the network, each new VM pair having a bandwidth requirement;

select the new VM pair having the highest bandwidth requirement;

rank each candidate VM site pair based on the number of links in the path connecting each candidate VM site pair; and

select a candidate VM site pair for the selected VM pair based on the ranking.

51. The network element of claim 50 wherein the controller is further configured to rank each candidate VM site pair based on the available link bandwidth for the candidate VM site pair.

52. The network element of claim 51 wherein the controller is further configured to remove each candidate VM site pair having an available link bandwidth that is less than the bandwidth requirement of the selected VM pair.

53. The network element of claim 50 wherein, for the remaining candidate VM site pairs, the controller is further configured to model a traffic matrix as if the selected VM site pair were instantiated at the selected candidate VM site pair.

54. The network element of claim 53 wherein the controller is further configured to adjust the link bandwidth between the selected candidate VM site pairs based on the bandwidth requirement of the selected VM pair.

55. The network element of claim 50 wherein the controller is further configured to:

calculate an estimated consumption index for each new VM to be added to the network; and

sum the estimated consumption index to compute an estimated cumulative bandwidth utilization for the new VM over all the links in the paths that would connect the new VM to each of one or more peer VMs.

56. The network element of claim 55 wherein the controller is further configured to:

compare the estimated cumulative bandwidth utilization to a predefined threshold value; and

identify the selected candidate VM site pairs to receive the selected VM pair based on the comparison.