JP6325348B2 - Virtual machine placement device - Google Patents

Description

  The present invention relates to a technology of a virtual machine arrangement device, a virtual machine arrangement method, and a virtual machine arrangement program.

  In recent years, server aggregation by server virtualization has been studied in data centers and the like. By constructing a plurality of logical servers (virtual machines) on one physical server, the number of physical servers can be aggregated. Even if the load amount of the virtual machine is the same, the performance of the entire virtualization system varies greatly depending on the physical server on which each virtual machine is placed. If the arrangement state is not good, only one computer resource is excessively used, but another computer resource is not used, resulting in an inefficient state.

Therefore, Patent Document 1 describes a method for improving resource usage efficiency by extracting as virtual machine candidates to be moved in order from a virtual machine with a large amount of used resources.
Patent Document 2 discloses a method of arranging two virtual machines having a large amount of communication so that they are executed on the same physical machine in order to arrange virtual machines in consideration of the dependency between virtual machines. Is described.

JP 2013-239095 A JP 2010-140134 A

  Here, in order to guarantee the end-to-end communication quality (QoS: Quality of Service) between virtual machines, pay attention only to the relationship between the physical server and the virtual machine, and the relationship between the virtual machines. It is not enough to determine the placement destination.

  As components of the virtualization system, there are not only physical servers on which virtual machines are mounted, but also communication devices (switches) that transfer traffic between those physical servers. Therefore, no matter how much processing capacity can be afforded by a single physical server, if multiple traffic concentrates on one switch, the switch becomes a bottleneck and communication delay between virtual machines occurs. .

  Therefore, the main object of the present invention is to arrange each virtual machine on a physical server so as to guarantee the communication quality between the virtual machines.

In order to solve the above problems, the virtual machine placement apparatus of the present invention is a predetermined process performed between the first virtual machine in the first physical server and the second virtual machine in the second physical server. The communication volume used in the predetermined communication is within the free capacity of the switch that relays the predetermined communication between the first physical server and the second physical server. A placement processing unit that selects the placement destination of the first virtual machine as the first physical server and selects the placement destination of the second virtual machine as the second physical server. The placement processing unit is characterized in that, among the switches that transfer the predetermined communication between the first and second virtual machines that have already been arranged, the amount of communication used in the predetermined communication at the present time is Exceeding the communication capacity of the switch If there is such a switch, it was in charge so that another switch is responsible for at least a part of the traffic used in the predetermined communication that the excess switch was in charge of At least one virtual machine of the first and second virtual machines is currently relocated to a physical server different from the first and second physical servers.
As a result, the physical server that is a candidate for the placement destination of the virtual machine is selected in advance so as to avoid exceeding the communication capacity of the switch, so that each virtual machine is configured so as to guarantee the communication quality between the virtual machines. It can be placed on a physical server, and the excess of the communication capacity of the switch that has occurred at the present time can be quickly resolved.

In addition, the present invention relates to predetermined communication performed between the first virtual machine in the first physical server and the second virtual machine in the second physical server. When the amount of communication used is within the available capacity of the switch that relays the predetermined communication between the first physical server and the second physical server, the first virtual machine An arrangement processing unit that selects an arrangement destination as the first physical server and an arrangement destination of the second virtual machine as the second physical server is provided, and the arrangement processing unit is arranged Among the switches that transfer the predetermined communication between the first and second virtual machines, it is predicted that the amount of communication used in the predetermined communication at a future time will exceed the communication capacity of the switch When the switch exists Of the first and second virtual machines in charge, another switch is responsible for at least part of the traffic used in the predetermined communication for which the switch is expected to exceed The at least one virtual machine is relocated to a physical server different from the first and second physical servers at a future time.
  As a result, it is possible to prevent an excess of the communication capacity of the switch that is predicted to occur at a future time.

According to the present invention, the arrangement processing unit is configured such that the communication amount used in the predetermined communication between the first virtual machine and the second virtual machine, the first virtual machine, and the second virtual machine the product of the number of hops between the virtual machine and the communication evaluation values between virtual machines, so that the sum of the previous SL communications evaluation value is minimum, determine each physical server as the placement destination of the virtual machine It is characterized by doing.

As a result, the amount of communication of the virtual machines in the entire network is minimized, so that the utilization efficiency of the entire network can be improved.

The present invention, the arrangement processing unit, when selecting the first and second virtual machines to determine the placement destination of a set of virtual machines unplaced, the first virtual machine and the second As the amount of communication used in the predetermined communication with the virtual machine increases , the placement destination of the first and second virtual machines is determined in an earlier order, and the physical that becomes the placement destination candidate of the virtual machine When the first and second physical servers to be arranged are selected from a set of servers, the more the communication capacity of the switch connected in the vicinity of the first and second physical servers is larger, The placement destinations of the first and second physical servers are determined in an early order.

  As a result, a virtual machine having a large communication volume can be arranged around a switch having a large communication capacity, and appropriate network resource distribution can be performed in the entire network.

  According to the present invention, each virtual machine can be arranged on a physical server so as to guarantee the communication quality between the virtual machines.

It is a block diagram which shows the virtualization system regarding one Embodiment of this invention. It is explanatory drawing which shows the graph (FIG.2 (a)), such as a predicted value by the VM usage amount estimation part regarding one Embodiment of this invention, and a NW information management part (FIG.2 (b)). FIG. 3A shows an example of VM usage (FIG. 3A), an example of NW information (FIG. 3B), and the NW information of FIG. FIG. 3C is an explanatory diagram illustrating an initial placement process (FIG. 3C) of the VM placement unit based on the VM usage amount of FIG. FIG. 4A shows an example of VM usage (FIG. 4A), an example of NW information (FIG. 4B), and the NW information of FIG. FIG. 4C is an explanatory diagram illustrating an initial placement process (FIG. 4C) of the VM placement unit based on the VM usage amount of FIG. It is a flowchart explanatory drawing which shows the initial arrangement process of the VM arrangement | positioning part regarding one Embodiment of this invention. It is explanatory drawing which shows the condition (FIG.6 (a)) which requires the rearrangement regarding one Embodiment of this invention, and the condition (FIG.6 (b)) after performing rearrangement from the situation. The graph (FIG. 7A) indicating that the situation requiring the rearrangement of FIG. 6A relating to an embodiment of the present invention has occurred at the present time, and the fact that the rearrangement of FIG. It is a graph (FIG.7 (b)) which shows. The graph (FIG. 8A) indicating that the situation requiring the rearrangement of FIG. 6A relating to an embodiment of the present invention has occurred at a future time, and the rearrangement of FIG. 6B performed at the future time. It is a graph (FIG.8 (b)) which shows that it carried out. It is flow explanatory drawing which shows the rearrangement process of the VM arrangement | positioning part regarding one Embodiment of this invention.

  Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a configuration diagram illustrating a virtualization system. The virtualization system includes a VM placement device 1, a physical server 4, and a switch 3. Each device constituting these virtualization systems is configured as a computer having a CPU (Central Processing Unit), a memory, a hard disk (storage means), and a network interface, and this computer is a program read by the CPU onto the memory. By executing the above, each processing unit is operated.
The VM placement apparatus 1 determines a physical server 4 as a placement destination for each virtual machine 2.
The virtual machine 2 is a computer environment that uses the computer resources of the physical server 4 to emulate the operation of a computer. Hereinafter, the physical server 4 may be abbreviated as PS (Physical Server), the virtual machine 2 may be abbreviated as VM (Virtual Machine), and the switch 3 may be abbreviated as SW (SWitch).

The VM placement device 1 includes a VM usage amount prediction unit 11, a SW usage amount prediction unit 12, a SW capacity management unit 13, an NW information management unit 14, a VM score calculation unit 15, a placement destination calculation unit 16, The VM arrangement unit 17, the VM information receiving unit 18, the SW information receiving unit 19, a PS score calculating unit 10a, and a PS usage amount collecting unit 10b are included.
The virtual machine 2 includes a VM usage collection unit 21 and a VM information transfer unit 22.
The switch 3 includes a SW usage amount collection unit 31 and a SW information transfer unit 32.
The physical server 4 includes a PS usage amount collection unit 41 and a PS information transfer unit 42.
Hereinafter, the details of each component in FIG. 1 will be described.

The VM usage amount collection unit 21 collects the VM usage amount (actual value) for each pair of its own VM and the communication destination VM for each predetermined period. The VM usage is the amount of communication resources used for transferring communication (traffic) of a VM pair.
The VM information transfer unit 22 transmits information on its own VM such as the VM usage collected by the VM usage collection unit 21 to the VM information reception unit 18.
The VM information receiving unit 18 receives information on each VM from the VM information transfer unit 22.

The VM usage amount prediction unit 11 calculates a predicted value of the VM usage amount in a predetermined period in the future from the measured value of the VM usage amount received by the VM information receiving unit 18. The VM usage amount prediction unit 11 recalculates the predicted value of the VM usage amount based on the actual measurement value every time the actual measurement value of the VM usage amount in the predetermined VM pair is updated.
FIG. 2A is a graph showing a predicted value by the VM usage amount prediction unit 11 and the like. The horizontal axis of the graph indicates time, and the vertical axis indicates the VM usage between predetermined VM pairs.
For example, the current time is set to 14:00 on October 11 (indicated as 10/11).
The solid line in the graph is the measured value of the VM usage indicating the past traffic trend. On the previous day (10/10), the actual measurements from the morning to the night are measured, and today (10/11) the actual measurements from the morning to 14:00 are measured.
A broken line in the graph is a predicted value of the VM usage based on the actual measurement value. Today, predictions from 14:00 to night are calculated.
For example, if the horizontal axis (definition area) of the graph in FIG. 2 (a) is 1 day, the amount used in the morning (left side of the graph) is low and the amount used in the daytime (center side of the graph) from the actual measurement value of the previous day. You can see past traffic trends in which the usage decreases in the evening (slightly to the right of the graph) and increases in the evening (to the right of the graph).
The measured values from today's morning to 14:00 are similar in overall trend, although the VM usage is slightly higher than the measured values at the same time of the previous day.
Therefore, since the forecast value from 14:00 today to the night is expected to be similar to the past (previous day) traffic trend, the forecast value for today is slightly higher than the actual value measured at the same time on the previous day. It is calculated by tracing. For example, since the actual measurement value in the evening of the previous day (16:00) is low, the predicted value of today's evening (16:00) is also lowered. In addition, since the actual measurement value of the previous night (19:00) is high, the prediction value of today's night (19:00) is also increased.

  Returning to FIG. 1, the VM score calculation unit 15 calculates a “VM score” for each virtual machine 2 indicating that the virtual machine 2 is easily selected as the next key VM (details are FIG. 3). The higher the VM score is, the easier it is to be selected as the placement destination of the next VM, and the higher the VM score is, the easier it is to be selected as the reset target for the already placed VM. Hereinafter, a VM score calculation method will be exemplified.

  As a first VM score calculation method, for a VM pair between a predetermined VM and a communication destination VM, the VM usage (average value in a predetermined period) for each VM pair is large (for example, the VM usage is There is a method of increasing the VM score for a predetermined VM as the number of communication destination VMs having a large VM usage amount increases.

  As a second VM score calculation method, the VM usage (average value in a predetermined period) for a predetermined VM is calculated for each VM of the communication destination viewed from the predetermined VM, and the VM usage for the predetermined VM is calculated. There is a method of increasing the VM score for a predetermined VM as the total value increases.

  The VM score calculation unit 15 receives a predicted value from the VM usage amount prediction unit 11 and an actual measurement value from the VM information reception unit 18 as the VM usage amount used for calculation of the VM score. The VM score calculation unit 15 recalculates the VM score every time the received VM usage is updated.

The SW usage amount collecting unit 31 collects the SW usage amount (actually measured value) for its own SW every predetermined period. The SW usage is the amount of communication resources used by the SW to transfer the communication of the VM pair. Specifically, the usage of a certain SW is the VM usage of the route passing through the SW. It is the sum.
The SW information transfer unit 32 transmits information related to its own SW such as the SW usage collected by the SW usage collection unit 31 to the SW information reception unit 19.
The SW information receiving unit 19 receives information regarding each SW from the SW information transfer unit 32.
The SW capacity management unit 13 uses, as information about each SW, the SW usage received by the SW information receiving unit 19 and the SW capacity registered for each SW in advance (the SW communication capacity obtained from the SW communication capacity). to manage.

  The SW usage amount prediction unit 12 calculates the usage amount of each SW per unit time based on the VM usage amount predicted by the VM usage amount prediction unit 11 and the arrangement relationship of the VMs determined by the arrangement destination calculation unit 16. Predict. The SW usage amount prediction unit 12 recalculates the predicted value of the usage amount of each SW every time the input parameter (VM usage amount, VM arrangement relationship) is updated.

The PS usage amount collection unit 41 collects the PS usage amount (actually measured value) and the number of installed VMs for its physical server 4 every predetermined period. The PS usage is the amount of communication resources used by the physical server 4. The number of installed VMs is the number of VMs arranged (mounted) on the own physical server 4.
The PS information transfer unit 42 transmits information on the physical server 4 collected by the PS usage amount collection unit 41 to the PS score calculation unit 10a and the NW information management unit 14, respectively.
The PS usage amount collection unit 10 b collects the PS usage amount and the number of installed VMs transmitted from the PS information transfer unit 42 of each physical server 4.

The NW information management unit 14 receives and manages topology information of a network system that is a VM placement target from an administrator or the like in advance. The topology information is, for example, the following information.
-Route information between each physical server-Route hop count information for each route between each physical server-SW information existing in each route FIG. 2 (b) is an explanatory diagram showing topology information managed by the NW information management unit 14 It is. The switch 3 (SW1 to SW5) and the physical server 4 (PS1 to PS4) are connected as illustrated.

  Returning to FIG. 1, the PS score calculation unit 10 a calculates a “PS score” for each physical server 4 that indicates the ease with which the physical server 4 can be selected as the placement destination of the next VM. The higher the PS score, the easier it is to be selected as the next VM placement destination. Hereinafter, a PS score calculation method will be exemplified.

  The first PS score calculation method focuses on the switches 3 within N hops (for example, N = 1) when viewed from its own physical server 4, and the free communication capacity continues for a predetermined period of these switches 3. This is a method of increasing the PS score as the number of switches 3 having a predetermined value or more (in other words, having a margin) increases.

  The second PS score calculation method focuses on the switches 3 within N hops (for example, N = 1) when viewed from its own physical server 4, and the total value of the free communication capacities during the predetermined period of each focused switch 3 This is a method of increasing the PS score as the value of is larger.

  The free communication capacity for each switch 3 is obtained by subtracting the usage amount of the switch 3 from the capacity (communication capability) of the switch 3. The PS score calculation unit 10 a receives the predicted value from the SW usage amount prediction unit 12 and the actual measurement value from the SW capacity management unit 13 as the usage amount of the switch 3. The PS score calculation unit 10a recalculates the PS score each time the received usage amount of the switch 3 is updated.

The placement destination calculation unit 16 determines, for each virtual machine 2, the physical server 4 that is the placement destination based on the placement policy. The placement policy is to determine the placement destination of each VM so as to satisfy all of the following (Rule 1) to (Rule 5). Alternatively, the placement destination of each VM is determined so as to satisfy at least one condition of (Rule 1) to (Rule 5).
(Rule 1) The target VM is selected in descending order of the VM score (the VM that is used is large and crowded), and the key VM that is used with the target VM is selected.
(Rule 2) The physical servers 4 that are the placement destinations are selected in descending order of PS score (low PS usage and free PS).
(Rule 3) The target VM and the key VM selected in (Rule 1) are arranged on the physical server 4 selected in (Rule 2) so as to minimize the amount of communication relayed by the switch 3 of the entire network.
(Rule 4) The physical constraints (SW usage amount ≦ SW capacity) of each SW are satisfied.
(Rule 5) The physical constraints of PS (PS usage amount ≦ PS capacity, number of mounted VMs ≦ mounted VM upper limit number) are satisfied.

The placement destination calculation unit 16 acquires the following information from other processing units at the time of initial placement of the VM in order to determine whether or not the above placement policy is satisfied. In FIG. 1, among the arrows indicating the flow of information, some of the arrows flowing to the arrangement destination calculation unit 16 are omitted.
-Predicted value of VM usage (from VM usage prediction unit 11)
SW capacity (from SW capacity management unit 13)
Topology information (from NW information management unit 14)
VM score (from the VM score calculation unit 15)
PS score (from PS score calculation unit 10a)
-PS usage and number of installed VMs (from PS usage collection unit 10b)

Furthermore, in order to determine whether or not the placement policy is satisfied, the placement destination calculation unit 16 receives the following information from each of the other processing units in addition to the information acquired at the time of the initial placement at the time of VM relocation. get.
・ Measured value of SW usage (from SW information receiver 19)
・ Actual value of VM usage (from VM information receiver 18)

  The VM placement unit 17 actually places each virtual machine 2 on each physical server 4 in accordance with the VM initial placement instruction and relocation instruction from the placement destination calculation unit 16. Note that the placement destination calculation unit 16 and the VM placement unit 17 may be configured as one placement processing unit.

FIG. 3A is an explanatory diagram illustrating an example of the VM usage in each VM pair received by the VM information receiving unit 18. Of the six virtual machines 2 (VM1 to VM6), the directly connected VM pair (such as VM1 and VM2) generates communication between the VM pairs, and links its communication volume (VM usage). (For example, the VM usage between VM1 and VM2 is “40”).
In order to simplify the description, each VM usage amount is set to a constant value regardless of the passage of time, but actually, each VM usage amount is sequentially updated.

In addition, among the connection lines of the VM pair, connection lines that generate a VM usage amount equal to or greater than the threshold “30” are indicated by bold lines. This bold connection line indicates the relationship between the “target VM” and the “key VM”. When selecting a certain target VM (for example, VM1), the VM placement unit 17 selects another VM (VM2, VM3, VM4 with respect to VM1) connected to the target VM with a thick connection line as a key VM. To do.
Note that the key VM is a VM that performs communication with the target VM such that the VM usage amount (such as an average value in a predetermined period) exceeds a predetermined amount (threshold value “30”).

FIG. 3B is an explanatory diagram illustrating an example of NW information managed by the NW information management unit 14. In order to simplify the description, a simpler topology than that in FIG.
Here, for each physical server 4 (PS1 to PS3), the upper limit number of accommodation VMs is assumed to be “2”. For example, the PS1 can accommodate the target VM (VM1) and its key VM (VM2), but cannot accommodate the third key VM (VM3).

FIG. 3C is an explanatory diagram illustrating an initial placement process of the VM placement unit 17 based on the VM usage amount of FIG. 3A with respect to the NW information of FIG. 3B.
Hereinafter, a state in which the virtual machines 2 are gradually arranged in each stage (first stage to fifth stage) indicated by the column elements in the table will be described. The row elements in the table indicate each virtual machine 2 in FIG. 3A and each switch 3 in FIG.
Regarding the contents of each cell in the table, in the cell of the virtual machine 2, the current selection status such as “target VM” and “key VM”, and the physical server 4 of the current placement destination such as “(PS2)” are described. Is done. In the cell of switch 3, a fractional format such as “110/150” is described, the denominator indicates its own capacity, and the numerator indicates the current allocated usage.

In the first stage, the VM placement unit 17 selects the VM 1 with the highest VM score as the target VM according to (Rule 1). Since VM1 has many communication partners (key VMs) connected by bold lines (three), and the total value of VM usage (30 + 40 + 50 = 120) is also larger than other VM2-6, The VM score is the highest.
Then, the VM placement unit 17 determines PS2 having a high PS score as the placement destination of the target VM (VM1) according to (Rule 2). Note that PS2 has a free communication capacity larger than a predetermined threshold (50) for both SW1 and SW2 existing within one hop, and the total value (80 + 150) of the two free communication capacities is Since it is the maximum, the PS score is higher than the other PS1 and PS3.
Further, as described with reference to FIG. 3A, the VM placement unit 17 selects communication partners (VM2, VM3, VM4) connected by a thick line from the target VM (VM1) as the key VMs.

In the second stage, the VM placement unit 17 determines only the VM 3 that is the highest VM usage (50) of the key VMs according to (Rule 5) and (Rule 3), which are the accommodation VM upper limit number “2”. Placed in the same PS2 (0 hops) as VM1.
In the third stage, the VM placement unit 17 places the remaining keys VM (VM2, 4) in the PS3 that is as close as possible (one hop) to the target VM (VM1) according to (Rule 3). Here, in the VM placement unit 17, the sum of the VM usage amounts between PS2 (VM1, VM3) and PS3 (VM2, VM4) is “40 + 30 + 40 = 110”, and between PS2 and PS3 Since it is within the capacity (150) of SW2 to be relayed, PS3 is selected to satisfy (Rule 4). Further, the VM placement unit 17 selects PS3 so as to satisfy (rule 5), which is the upper limit number of accommodation VMs “2”.

In the fourth stage, the VM placement unit 17 has already placed the first target VM (VM1) and its key VM (VM2, VM3, VM4), so the second target VM (VM5) and its key VM ( VM6) is selected as in the first stage. In this selection process, each VM (VM1 to VM4) that has been placed is excluded from the selection target.
In the fifth stage, the VM placement unit 17 places the VMs 5 and 6 selected in the fourth stage on PS1 so as to satisfy each placement policy, as in the first to third stages.

FIG. 4A is an explanatory diagram illustrating an example of the VM usage amount, and has a configuration different from that in FIG.
FIG. 4B is an explanatory diagram showing an example of NW information, and has a configuration different from that shown in FIG.
FIG. 4C is an explanatory diagram illustrating an initial placement process of the VM placement unit 17 based on the VM usage amount of FIG. 4A with respect to the NW information of FIG. 4B. FIG. 4C illustrates a case where the arrangement of the virtual machine 2 once arranged is reset (released), unlike FIG. 3C.

  In the first stage of FIG. 4C, as described in the first to third stages of FIG. 3C, the VM placement unit 17 targets the VM 1 having the highest VM score according to (Rule 1). Select as a VM, and according to (Rule 2), determine PS2 with a high PS score as the placement destination of the target VM (VM1). Then, the VM placement unit 17 places the remaining key VMs (VM2, VM4) in PS1 that is as close as possible (one hop) to the target VM (VM1) according to (Rule 3).

  In the second stage of FIG. 4C, the VM placement unit 17 selects VM5 as the next target VM according to (Rule 1), and selects VM5 as its key VM. However, according to (Rule 5), regardless of which VM5 placement destination candidate (PS3, PS4) has a surplus in the upper limit number of installed VMs (PS3, PS4), VM4 that forms a VM pair with that VM5 has already been placed in PS1. When the communication amount “50” of the VM pair passes through SW1, the communication amount excess of SW1 (130/90) occurs.

In the third stage of FIG. 4C, the VM placement unit 17 resets the placed VM 4 that has been problematic in the second stage. As a result, the unallocated VMs become VM4, VM5, and VM6.
In the fourth stage of FIG. 4C, the VM placement unit 17 gives priority to the VM4 reset in the third stage over the VM5 having a higher VM score, as an exception process to (Rule 1). And Therefore, VM5 connected to VM4 by a thick line is the current key VM. According to (Rule 2), the VM placement unit 17 determines PS3 having a high PS score as the placement destination of the target VM (VM4), and according to (Rule 3), the key VM (VM5) is made up of the target VM (VM1) as much as possible. Place it in PS3 that will be near (0 hops).
In the fifth stage of FIG. 4C, the VM placement unit 17 places the remaining VMs 6 on the PS 4 that satisfies the placement policy.

FIG. 5 is a flowchart for explaining the initial placement process of the VM placement unit 17.
In S101, the VM placement unit 17 determines whether there is a VM that has not been placed. If Yes in S101, the process proceeds to S102, and if No, the process ends. For this reason, the VM placement unit 17 manages information indicating whether or not the placement is currently performed for each VM and information indicating the placement destination physical server 4 in the storage unit when the placement is performed.
In S102, the VM placement unit 17 selects a target VM from the unplaced VMs according to (Rule 1). For example, in the first stage of FIG. 3C, VM1 is selected as the target VM. In (Rule 1), a plurality of VMs may be selected in descending order of the VM score.

In S103, the VM placement unit 17 selects a key VM from the selected target VM as described with reference to FIG. For example, in the first stage of FIG. 3C, VM2, VM3 and VM4 are selected as the key VMs of the target VM (VM1).
In S104, the VM placement unit 17 selects a placement destination PS according to (Rule 2) and (Rule 5). For example, in the first stage of FIG. 3C, PS2 having a high PS score and no other installed VM is selected as the placement destination PS. In (Rule 2), a plurality of PSs may be selected in descending order of PS score.

As S105, the VM placement unit 17 places the target VM selected in S102 and the key VM selected in S103 in the placement destination PS (or other PS) selected in S104 according to (Rule 3).
For example, in the first stage of FIG. 3C, the target VM1 selected in S102 is arranged in PS2 selected in S104. Further, in the second stage of FIG. 3C, the key VM3 selected in S103 is arranged in PS2 selected in S104. Further, in the third stage of FIG. 3C, the keys VM2, 4 selected in S103 are arranged in PS3.

  Whether or not (Rule 3) is satisfied is determined based on an evaluation formula for the traffic of the entire network. First, the VM placement unit 17 forms a VM pair set for each combination of the target VM selected in S102 and the key VM selected in S103, and the VM usage amount (total value in a predetermined period) of these VM pairs. The total is the total traffic. Note that the VM usage of the VM pair may be weighted (multiplied) by the number of hops between the VM pairs. When both of the VM pairs are arranged on the same physical server 4, the number of hops is 0, so the VM usage of the VM pair is also 0. That is, if the number of hops between the selected VMs is arranged to be as small as possible, the total communication amount is also reduced.

Then, the VM placement unit 17 tries various combinations of placement destinations so that the target VM selected in S102 and the key VM selected in S103 are placed in any of the placement destination PSs in S104 (temporary placement). ) To find a combination that minimizes the total traffic.
When the key VM selected in S103 is already arranged, if the total traffic of (Rule 3) is improved (becomes smaller) while satisfying the arrangement policy, the arranged key VM is reset. , S105 may be rearranged.

In S106, the VM placement unit 17 determines whether or not each switch 3 satisfies (Rule 4) by the placement process in S105. If Yes in S106, the process returns to S101, and if No, the process proceeds to S107.
For example, in the third stage of FIG. 3C, the communication amount of SW2 is “110/150” and is within the capacity, so (Rule 4) is satisfied.
On the other hand, in the second stage of FIG. 4C, since the traffic volume of SW1 is “130/90” and exceeds the capacity, (Rule 4) is not satisfied.
Here, the higher the VM score of the arranged target VM, the lower the threshold indicating the SW capacity (such as 110/150 denominator “150”) may be set.

In S107, the VM placement unit 17 resets the key VM placed in S105 this time, selects the reset VM as the next target VM, and returns to S103.
For example, in the third stage of FIG. 4C, the VM4 arranged as the key VM in the second stage is reset, and the VM4 is selected as the target VM in the fourth stage.
In order to prevent an infinite loop, the VM placement unit 17 holds a history of placement destinations that have already been tried for each VM, and places the physical server 4 of the placement destination that has previously failed as a placement destination for the next and subsequent times. It is desirable to exclude from candidates.

FIG. 6A is an explanatory diagram illustrating a situation where rearrangement is required. VM1 and VM2 are arranged in PS1, VM3 and VM4 are arranged in PS2, and VM5 is arranged in PS3. Here, since the VM usage between the VM1-VM3 pairs is large, the SW usage of the SW1 located on the path between the VM pairs is increased, and the SW1 is congested.
FIG. 6B is an explanatory diagram showing a situation after the rearrangement is executed from FIG. The VM placement unit 17 resets (removes) VM1 from PS1, and then rearranges VM1 to PS3. As a result, although the VM usage amount between the VM1-VM3 pair continues to be large, there is a margin in the SW capacity of SW2 located on the path, so that it is not necessary to cause congestion of SW1 and SW2.

FIG. 7A is a graph showing that the situation requiring the rearrangement of FIG. 6A has occurred at the present time. First, the SW usage amount (actually measured value) of the current SW1 exceeds the SW capacity indicated by the threshold when combined with not only the VM usage amount between the VM1-VM3 pair but also other VM usage amounts. On the other hand, the SW usage amount of the current SW2 still has a margin, and even if the VM usage amount between the VM1-VM3 pair is added, from the present time to a predetermined period ahead (including not only the actual measurement value but also the predicted value) , SW capacity of SW2 is not exceeded.
Therefore, the VM placement unit 17 changes the VM usage amount between the VM1 and VM3 pairs from SW1 to SW2 so that both SW1 and SW2 satisfy the physical constraints of SW according to (Rule 4) and (Rule 5). To relocate (to relocate VM1 to PS3).

  FIG. 7B is a graph showing that the rearrangement of FIG. 6B has been executed at the present time. Both SW1 and SW2 can satisfy (Rule 4) when the SW usage amount falls within the threshold (SW capacity). Note that the VM placement unit 17 excludes PS2 in which two upper limit VMs are already mounted from the relocation destination candidates in order to satisfy the restriction on the upper limit number of installed VMs in (Rule 5).

FIG. 8A is a graph showing that the situation requiring the rearrangement of FIG. 6A has occurred at a future time (time t). FIG. 8B is a graph showing that the rearrangement of FIG. 6B has been executed at a future time (time t).
Comparing FIG. 8 and FIG. 7, the SW 1 excess capacity point of SW1 is replaced from the present time to the future time (time t). That is, in FIG. 8, the SW capacity of SW1 does not exceed at present.

  In FIG. 8A, the VM usage amount (predicted value) of SW1 at the future time point (time t) is not only the VM usage amount between the VM1-VM3 pairs but also the other VM usage amounts, the threshold value is The indicated SW capacity has been exceeded. On the other hand, the VM usage (predicted value) of SW2 at the future time (time t) is still sufficient, and even if the VM usage between the VM1-VM3 pairs is added, it is predetermined from the future time (time t). It is predicted that the SW capacity of SW2 will not be exceeded until the period ahead.

Therefore, as illustrated in FIG. 8B, the VM placement unit 17 determines the VM usage amount between the VM1-VM3 pair so that both SW1 and SW2 satisfy the physical constraints of the SW according to (Rule 4). , SW1 is determined to be rearranged. Note that unlike FIG. 7B, the VM placement unit 17 determines the relocation destination (in the figure, SW2) of the VM usage that satisfies the placement policy, not just at the current time but immediately before the future time (time t). May be. That is, the reset process of VM1 and the rearrangement process of VM1 may be performed immediately before a future time (time t) instead of the current time.
As a result, an actual measurement value with higher accuracy than the predicted value can be used as the SW usage amount of each SW, so that an available SW can be reliably selected as a relocation destination of the VM usage amount.

FIG. 9 is a flowchart illustrating the rearrangement process of the VM placement unit 17.
As S201, the VM placement unit 17 acquires the VM usage and the SW usage as materials for determining whether or not the VM placement status satisfies the placement policy (details are described in FIG. 1).
In S202, the VM placement unit 17 determines whether or not each switch 3 satisfies the physical constraint condition (SW usage amount ≦ SW capacity) of (Rule 4). If Yes in S202, the process ends. If No, the process proceeds to S203. For example, SW1 in FIG. 6A is an example in which congestion occurs because (rule 4) is not satisfied.

As S203, the VM placement unit 17 sets a VM pair that has a large ratio of the VM usage amount accommodated by the switch 3 to the switch 3 that does not satisfy (rule 4) at S202 (in FIGS. Select VM1-VM3 pair ").
In S204, the VM placement unit 17 searches for a VM placement amount rearrangement destination according to (Rule 4) and (Rule 5). For example, in FIG. 7 (a) and FIG. 8 (a), a search is made for SW2 having an unused SW usage.
In S205, the VM placement unit 17 determines whether a relocation destination has been found in S204. If Yes in S205, the process proceeds to S206, and if No, the process proceeds to S208. In FIGS. 6 to 8, PS3 is found as a relocation destination of VM1 (Yes in S205).

In S206, the VM placement unit 17 resets one of the VM pairs ("VM1" in FIGS. 6 to 8) so that the VM usage of the VM pair passes through the switch 3 searched in S204. The VM is relocated to another physical server 4 (“PS3” in FIGS. 6 to 8). This rearrangement process is realized by calling an initial arrangement process of FIG. 5 with an instruction not to execute the arrangement reset of the arranged VM.
In S207, the VM placement unit 17 determines whether the rearrangement in S206 has succeeded. If Yes in S207, the process returns to S202, and if No, the process proceeds to S208.

  As S208, the VM placement unit 17 resets both of the VM pairs ("VM1 and VM3" in FIGS. 6 to 8), and calls the initial placement process of FIG. 5 to relocate the reset VM. . Then, after S208, the process returns to S202.

Regarding the execution times of the processes in FIG. 9 described above, when a situation requiring relocation occurs at the current time as shown in FIG. 7, the processes of S201 to S208 are executed at the current time.
On the other hand, as shown in FIG. 8, when it is predicted that a situation requiring rearrangement will occur at a future time (time t), S202 to S203 are executed at this time, and the subsequent processing (S204 to S208) is performed. The process is executed after waiting immediately before the future time (time t).

In the present embodiment described above, as shown in FIGS. 3 and 4, according to (Rule 4), the target VM and the key VM are initially arranged so that the capacity of each switch 3 does not exceed. Each virtual machine can be arranged on a physical server so as to guarantee the communication quality between the virtual machines.
Furthermore, as shown in FIGS. 6 to 8, even if (Rule 4) is satisfied at the time of the initial initial arrangement in the past, the event (Rule 4) is not satisfied at the present time or in the future due to traffic fluctuation or the like. On the other hand, by rearranging the virtual machines 2 that have already been arranged, it can be improved to satisfy (Rule 4) afterwards.

1 VM placement device (virtual machine placement device)
2 VM (virtual machine)
3 SW (switch)
4 Physical Server 11 VM Usage Prediction Unit 12 SW Usage Prediction Unit 13 SW Capacity Management Unit 14 NW Information Management Unit 15 VM Score Calculation Unit 16 Placement Destination Calculation Unit (Placement Processing Unit)
17 VM placement unit (placement processing unit)
18 VM information receiving unit 19 SW information receiving unit 10a PS score calculating unit 10b PS usage collecting unit 21 VM usage collecting unit 22 VM information transfer unit 31 SW usage collecting unit 32 SW information transferring unit 41 PS usage collecting unit 42 PS information transfer unit

Claims (4)

For the predetermined communication performed between the first virtual machine in the first physical server and the second virtual machine in the second physical server, the amount of communication used in the predetermined communication is When the first virtual machine is within the free capacity of the switch that relays the predetermined communication between the first physical server and the second physical server, the placement destination of the first virtual machine is the first virtual server. of selecting a physical server, the placement destination of the second virtual machine to have the arrangement processing unit that selects as said second physical server,
The placement processing unit is configured so that a communication amount used in the predetermined communication at the present time is a communication amount of the switch among the switches that transfer the predetermined communication between the first and second virtual machines that have been arranged. When there is a switch that exceeds the capacity, another switch is responsible for at least a part of the traffic used in the predetermined communication that the excess switch is in charge of. Relocating at least one virtual machine of the first and second virtual machines in charge to a physical server different from the first and second physical servers at the present time, virtual machine placement device to. For the predetermined communication performed between the first virtual machine in the first physical server and the second virtual machine in the second physical server, the amount of communication used in the predetermined communication is When the first virtual machine is within the free capacity of the switch that relays the predetermined communication between the first physical server and the second physical server, the placement destination of the first virtual machine is the first virtual server. And a placement processing unit that selects the second virtual machine placement destination as the second physical server.
The placement processing unit is configured such that, of the switches that transfer the predetermined communication between the first and second virtual machines that have already been arranged, a communication amount used in the predetermined communication at a future time point When there is the switch that is predicted to exceed the communication capacity, another switch is responsible for at least a part of the communication amount used in the predetermined communication that the switch that is predicted to exceed the capacity is in charge. And at least one virtual machine of the first and second virtual machines in charge is relocated to a physical server different from the first and second physical servers at a future time. virtual machine placement device to. The arrangement processing unit includes a communication amount used in the predetermined communication between the first virtual machine and the second virtual machine, and between the first virtual machine and the second virtual machine. The product of the number of hops between them is used as a communication evaluation value between virtual machines, and each physical server as a placement destination of each virtual machine is determined so that the sum of the communication evaluation values is minimized. Item 3. The virtual machine arrangement device according to item 1 or 2 . The arrangement processing unit
When selecting the first and second virtual machines for determining the placement destination from a set of unplaced virtual machines, the predetermined communication between the first virtual machine and the second virtual machine is performed. As the amount of communication used increases, the placement destination of the first and second virtual machines is determined in an earlier order,
When selecting the first and second physical servers as placement destinations from a set of physical servers that are candidates for placement destinations of virtual machines, they are connected in the vicinity as seen from the first and second physical servers The placement destination of the first and second physical servers is determined earlier in order as the communication capacity of the switch increases.
The virtual machine placement device according to claim 1 .

Images