CN104375897A - Cloud computing resource scheduling method based on minimum relative load imbalance degree - Google Patents

Abstract

The invention discloses a cloud computing resource scheduling method based on the minimum relative load unbalanced degree. A load balancer is used to evaluate the load level of each physical machine in the cluster to judge whether there is an overload phenomenon on the physical machine. If overloaded, calculate all normal Run the relative load imbalance of the physical machine relative to the overloaded physical machine, select the physical machine with the smallest relative load imbalance value as the candidate physical host, and judge whether the computing resource capacity of the candidate host meets the virtual machine resources to be migrated If the resource capacity is satisfied, the physical machine will be used as an alternative physical machine to migrate the virtual machine; if the resource capacity is not met, the physical machine will be excluded and an alternative physical host will be selected. The invention can effectively improve the utilization rate of system resources, ensure system load balance and improve system stability.

Description

A cloud computing resource scheduling method based on the minimum relative load imbalance

technical field

The invention belongs to the field of virtualization and cloud computing, and in particular relates to a method for scheduling cloud computing resources based on the minimum relative load imbalance.

Background technique

Cloud computing emerged in response to the social trend that enterprises and individual consumers have increasingly demanding data center processing capabilities, and has become one of the hottest issues in IT research. The virtual cluster built by the cloud computing platform using virtualization technology can dynamically organize heterogeneous computing resources, and can isolate specific hardware architecture and diversified software system platforms. It can flexibly build computing environments that meet different application requirements. Improve the efficient use of computing resources. In the cloud computing environment, the application system will no longer be limited to its own system performance, but can obtain powerful computing power, massive data resources, and various applications from cloud resources, and can use more ways to meet various requirements. Diversified and high-level service needs of users. Users will also get a more complete service experience and be able to enjoy various services of the application system in a timely, efficient and barrier-free manner.

As the most critical and core technical driving force in the cloud computing IaaS layer, virtualization technology can abstract the underlying architecture such as physical resources, making the differences and compatibility of devices transparent to upper-layer applications, thus allowing the cloud to unify the vastly different underlying resources manage. It is precisely because of the maturity and wide application of virtualization technology that computing, storage, applications and services in cloud computing have all become resources, which can be dynamically expanded and configured, and cloud computing can finally be logically integrated in the form of a single whole presented. In a cloud environment, a virtual machine is used as a computing resource, and users usually require its operation to be stable, and they do not want frequent migration of virtual machines.

In the cloud computing application platform, its resources are widely distributed and various in variety. To enable users to use the resources in the cloud environment like water and electricity, the key issue is to properly handle the resource allocation. At the same time, the real-time dynamics of user needs are difficult to be accurately predicted, and issues such as system performance and cost must also be considered. Therefore, efficient cloud computing data center allocation and scheduling strategy algorithms have become a research hotspot. In a cloud computing system, when a user requests to create a new virtual machine, or a virtual machine needs to be migrated, cloud computing resource scheduling is required to keep the entire system running efficiently and reliably. Existing cloud computing resource scheduling methods, such as the paper "ADynamic And Integrated Load-Balancing Scheduling Algorithm For Cloud Data Centers" (IEEE International Conference on CloudComputing and Intelligence System, 311-315, Wenhong Tian, YongZhao, Yuanliang Zhong, Minxian Xu, Chen Jing, 2011-09-15) Chinese invention patent application "a large-scale virtual machine rapid migration decision-making method for cloud data centers" (application number: 201310186581.8 publication date: 2013-08-14), these methods mainly consider the system Performance and load balancing, without considering whether the host capacity meets the requirements and the impact on resource utilization.

Contents of the invention

The purpose of the present invention is to provide a cloud computing resource scheduling method based on the minimum relative load imbalance, to solve the problem that the existing technology cannot obtain high resource utilization and maintain a low level under the premise of ensuring high system performance The problem of load imbalance.

The technical solution adopted in the present invention is a cloud computing resource scheduling method based on the minimum relative load imbalance, and the load balancer is used to evaluate the load level of each physical machine in the cluster to determine whether there is an overload phenomenon on the physical machine. Calculate the relative load imbalance of all normal running physical machines relative to the overloaded physical machine, select the physical machine with the smallest relative load imbalance value as the candidate physical host, and judge whether the computing resource capacity of the candidate host meets the requirements for migration. Virtual machine resource requirements, if the resource capacity is satisfied, the physical machine will be used as an alternative physical machine to migrate the virtual machine; if the resource capacity is not met, the physical machine will be excluded, and an alternative physical host will be reselected to migrate the virtual machine .

The specific steps to evaluate the load level of the physical machine are as follows:

Step 1. The monitor tracks the load information of each physical machine based on a certain period of time;

Step 2, the load information memory records all the load information tracked in step 1 in the unit of the same time period as the monitor;

Step 3. The load information storage feeds back the load information recorded in step 2 within a certain time interval to the load balancer, and the load balancer calculates the average resource load:

${\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; ,</span>$

Among them, δ _i is the average resource load, U _i is the average utilization rate of resources in the physical machine, and T _i is the total amount of resources in the physical machine;

Step 4. Calculate the load value of the physical machine according to the value obtained in step 3:

γ _i =E+δ _i ,

Among them, is the load value of the physical machine, and E is a relatively small constant;

Step 5. Compare the value obtained in step 4 with the alarm value set in the system. If the obtained value exceeds the load alarm value, a judgment is made: the physical machine is overloaded;

The relative load imbalance refers to the ratio of the resource load value of the normal operating physical machine to the load value of the overloaded physical machine at a certain moment, calculated according to the formula:

${\mathrm{<span\; class="notranslate">\; B</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; I</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; the\; ri</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; the\; ri</span>}}}{{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; mi</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; mi</span>}}}<span\; class="notranslate">\; ,</span>$

Among them, B _r is the relative load imbalance of the overloaded physical machine, U _ri is the average utilization rate of the physical machine resources in normal operation, U _mi is the average utilization rate of the overloaded physical machine resources, _Tri is the resource capacity of the physical machine in normal operation, T _mi is the resource capacity of the overloaded physical machine, and a _i is the weight factor of computing resource i.

The load information includes the average utilization rate U _i and the total amount T _i of resources such as CPU, memory, storage space, and network bandwidth, and i represents the dimension of cloud computing resources.

The beneficial effects of the present invention are:

1. The utilization rate of system resources is high: Based on the comparison of the load information of the normal operating physical machine and the load information of the overloaded physical machine, the relative imbalance is obtained, and the physical machine with the minimum relative imbalance is selected. After calculating the resource requirements and meeting the conditions, virtual Machine dynamic migration;

2. System load balancing: Guide the virtual machine scheduling according to the load level of each computing node to balance the system load of the nodes, which improves the stability of the system.

Description of drawings

Fig. 1 is a schematic diagram of a cloud computing system model;

Fig. 2 is a flow chart of the cloud computing resource scheduling method based on the minimum relative load imbalance degree of the present invention.

Detailed ways

The present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments.

Fig. 1 is a schematic diagram of the cloud computing system model of the present invention: the customer sends a request through a computer terminal, and the cloud system stores it in the central task buffer queue located in the task buffer, and builds a virtual machine in the physical machine in turn according to the request; the monitor Track the load information of the physical machine in real time and store the result in the load information storage. The load information storage feeds back the received load information of the physical machine to the load balancer. The load balancer evaluates the load level of the physical machine and makes a judgment Whether the physical machine is overloaded, if it is overloaded, calculate the relative load unbalance of all normal running physical machines relative to the overloaded physical machine, select the physical machine with the smallest relative load unbalanced value as the candidate physical host, and judge Whether the computing resource capacity of the candidate host meets the resource requirements of the virtual machine that needs to be migrated. If the resource capacity is sufficient, the physical machine will be used as the candidate physical machine to migrate the virtual machine; if the resource capacity is not satisfied, the physical machine will be excluded and re-selected. Select an alternative physical host to migrate the virtual machine.

In this embodiment, the cloud computing resource scheduling method based on the minimum relative load imbalance is specifically implemented according to the following steps, see FIG. 2:

Step 1. The cloud system receives the customer request information, stores it in turn and creates a corresponding virtual machine in the physical machine;

Step 2. The monitor tracks the load information of each physical machine in units of T=20s, and the load information memory records the tracked load information in units of the same period T as the monitor;

Step 3. At time S, the load information memory feeds back all the physical machine load information received at this time to the load balancer;

Step 4. The load balancer uses the physical information received in step 3 to obtain the resource load average:

${\mathrm{<span\; class="notranslate">\; \&delta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}$

Among them, δ _i is the average resource load, U _i is the average utilization rate of resources in the physical machine, and T _i is the total amount of resources in the physical machine;

Step 5. Calculate the load value of the physical machine according to the value obtained in step 4:

γ _i =E+δ _i

Among them, γ _i is the load value of the physical machine, and E is a relatively small constant;

Step 6. Compare the value obtained in step 5 with the alarm value set in the system. If the obtained value exceeds the load alarm value, the load determiner will make a judgment: at time S, the load of the physical machine is overloaded, and the physical machine running on the physical machine needs to be checked. virtual machines for migration;

Step 7. The load information memory feeds back the load information of each normal operating physical host and the load information of the overloaded physical machine at time S-1, and calculates the relative load unbalance degree of the overloaded physical machine:

${\mathrm{<span\; class="notranslate">\; B</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; I</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; the\; ri</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; the\; ri</span>}}}{{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; mi</span>}}{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; mi</span>}}}$

Among them, B _r is the relative load unbalance degree of the overloaded physical machine, U _ri is the average utilization rate of the physical machine resources in normal operation at the time S-1, U _mi is the average utilization rate of the overloaded physical machine resources at the time S-1, _Tri is The resource capacity of the physical machine running normally at time S-1, T _mi is the resource capacity of the overloaded physical machine at time S-1, and a _i represents the weight factor of computing resource i;

Step 8. The task scheduler combines the judgment issued by the load balancer, and selects the physical machine corresponding to the minimum relative imbalance as the candidate host for virtual migration;

Step 9. Check the resource constraints on the candidate host, obtain the task request assigned to the physical machine at time S-1 from the task cache, and judge whether the task request will cause the candidate host to be overloaded: if the virtual machine needs to be migrated The resource demand is an I-dimensional vector, and each dimension represents the demand for a certain computing resource, then: H=(h ₁ ,h ₂ ...h _i ...h _I ),i=1,2 , 3...I; Obtain the load information of the candidate mainframe at the moment S from the load information memory, and still write it into vector form: =(n ₁ ,n ₂ ...n _i ...n _I ), i=1,2,3...I; compare h _i and n _i in turn, if the condition h _i ≤n _i is satisfied, i=1, 2, 3...I; then dynamically migrate the virtual machine in the overloaded physical machine to this alternative host; if h _i >n _i , i=1, 2, 3...I, then exclude this alternative host, Re-select the candidate host until the candidate host that meets the requirements is selected;

Step 10, migrate the virtual machine to an alternative host.

Claims (4)

1. The cloud computing resource scheduling method based on the minimum relative load imbalance degree is characterized in that a load balancer is used for evaluating the load level of each physical machine in a cluster, judging whether an overload phenomenon occurs on the physical machine or not, if the physical machine is overloaded, calculating the relative load imbalance degree of all normally-operated physical machines relative to the physical machine with the overloaded load, selecting the physical machine with the minimum relative load imbalance degree as an alternative physical host, judging whether the computing resource capacity of the alternative host meets the resource requirement of a virtual machine needing to be migrated or not, and if the resource capacity meets the requirement, taking the physical machine as the alternative physical machine to migrate the virtual machine; and if the resource capacity is not satisfied, excluding the physical machine from reselecting the alternative physical host.

2. The method for scheduling cloud computing resources based on minimum relative load imbalance according to claim 1, wherein the specific steps of evaluating the load level of the physical machine are as follows:

step 1, a monitor tracks load information in each physical machine by taking a certain time interval as a unit;

step 2, the load information memory takes the same time interval as the monitor as a unit to record all the load information tracked in the step 1;

step 3, the load information memory feeds back the load information recorded in the step 2 in a certain time interval to the load balancer, and the load balancer calculates the average value of the resource load:

<math> <mrow> <msub> <mi>&delta;</mi> <mi>i</mi> </msub> <mo>=</mo> <mfrac> <mrow> <mi>&Sigma;</mi> <msub> <mi>T</mi> <mi>i</mi> </msub> <mo>*</mo> <msub> <mi>U</mi> <mi>i</mi> </msub> </mrow> <mrow> <mi>&Sigma;</mi> <msub> <mi>U</mi> <mi>i</mi> </msub> </mrow> </mfrac> <mo>,</mo> </mrow> </math>

wherein,_iis the resource load average, U_iIs the average utilization of resources in the physical machine, T_iThe total amount of resources in the physical machine;

and 4, calculating the load value of the physical machine according to the value obtained in the step 3:

γ_i＝E+_i，

wherein, γ_iE is a relatively small constant, and is the load value of the physical machine;

and 5, comparing the value obtained in the step 4 with an alarm value set in the system, and if the obtained value exceeds the load alarm value, judging: the physical machine is overloaded.

3. The method for scheduling cloud computing resources based on minimum relative load imbalance according to claim 1, wherein the relative load imbalance is a ratio of a resource load value of a normally operating physical machine to a load value of an overloaded physical machine at a certain time, and is calculated according to a formula:

<math> <mrow> <msub> <mi>B</mi> <mi>r</mi> </msub> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>I</mi> </munderover> <mfrac> <mrow> <msub> <mi>a</mi> <mi>i</mi> </msub> <msub> <mi>U</mi> <mi>ri</mi> </msub> <msub> <mi>T</mi> <mi>ri</mi> </msub> </mrow> <mrow> <msub> <mi>U</mi> <mi>mi</mi> </msub> <msub> <mi>T</mi> <mi>mi</mi> </msub> </mrow> </mfrac> <mo>,</mo> </mrow> </math>

wherein, B_rFor the degree of imbalance of the relative loads of the overloaded physical machine, U_riFor average utilization of resources of normally operating physical machines, U_miFor average utilization of overloaded physical machine resources, T_riFor the resource capacity of a normally operating physical machine, T_miTo overload the resource capacity of a physical machine, a_iRepresenting the weight factor of the computing resource i.

4. The method as claimed in claim 2, wherein the load information includes an average utilization rate U of resources such as CPU, memory, storage space, and network bandwidth_iAnd the total amount T_iAnd i represents a cloud computing resource dimension.