Resource plan preparation program

The present invention relates to a resource planning program for creating an allocation plan for a plurality of services operated by a computer cluster system composed of a plurality of computer clusters composed of a plurality of computers connected to the plurality of computer clusters. , It is related to a resource planning creation program that can prevent each computer cluster from becoming overloaded and can efficiently use the computer resources of the computer cluster.

In recent years, data centers have come to operate a plurality of network services entrusted by a plurality of service providers at the same time in one data center, and at the same time, a plurality of services to be operated at the same time. Dynamically increase the allocation of computational resources in the data center for services with increasing load, and move the allocation of computational resources in the data center for services with reduced load. Resource allocation control is performed based on a utility method that reduces the number of data (see, for example, Patent Document 1).

However, when some services operating in the data center are temporarily overloaded and it becomes necessary to significantly increase the resource allocation for this service, new idle resources to be allocated are newly allocated in the data center. In some cases, there may be a shortage and resources cannot be added.

In order to prevent such a situation from occurring, the amount of resources required when the total load of all operational services in the data center peaks is predicted, and the amount of resources required during peak hours is constantly prepared in the data center. However, in this case, most of the resources will remain unused as idle resources during periods other than peak hours, and the cost performance and computing resource utilization efficiency of the data center as a whole will decline.

Therefore, in the international patent application JP03 / 03273, a method using a logistical support data center is proposed. In this method, each service is usually constantly operated in a specific data center (hereinafter referred to as "original center") designated by the service provider operator who requested the operation of the service (hereinafter, such a service). Is called "primitive service").

Then, when the primitive service is temporarily overloaded due to the time fluctuation of the load, and the original center itself is also overloaded as a whole, one of the overloaded primitive services on the original center. In order to process the department in another data center called the logistical support center, an auxiliary service (hereinafter referred to as "derivative service") corresponding to the primitive service is generated on the logistical support center and on the logistical support center. Start operation.

As a result, the derivative service on the logistical support center can take over a part of the load borne by the overloaded primitive service, and the overload state of the original center as a whole can be eliminated.

Here, the distribution ratio of the amount of user requests arriving at each service to the primitive service and the derived service is set in the load distribution device or redirector in the network, and the load distribution device or the like is serviced based on the set ratio. The amount of user requests arriving at is distributed between the primitive service and the derived service.

In such a conventional data center operation mode, there are generally a plurality of original centers and often one logistical support center. In addition, the division of roles between the original center and the logistical support center was clear, and the logistical support center was used exclusively for the operation of derivative services.

<patcit num="1"><text>Japanese Patent Application Laid-Open No. 2002-24192</text></patcit>

<p> However, in the conventional technology of defining a specific data center as a logistical support center and operating all derived services exclusively in that data center, there is one logistical support center from many primitive services on multiple original centers at the same time. There is a problem that the logistical support center becomes overloaded as a whole when the generation requests of the derived service are concentrated on the above.</p><p> In addition, if the logistical support center predicts the amount of resources required at the logistical support center when the concentration of requests for generation of derivative services peaks, and the logistical support center constantly prepares the required resource amount at the peak time, it is backward except during peak hours. Most of the computational resources of the support center will not be used, and the resource utilization efficiency will decrease.</p><p> The present invention has been made to solve the above-mentioned problems caused by the prior art, and prevents each computer cluster, which is an aggregate of computer resources such as a data center as a typical example, from being overloaded. At the same time, the purpose is to provide a resource planning program that can efficiently use the computational resources of a computer cluster.</p>

<p> In order to solve the above-mentioned problems and achieve the object, the present invention transfers a plurality of services operated by a computer cluster system composed of a plurality of computer clusters composed of a plurality of computers to the plurality of computer clusters. A resource plan creation program that creates a resource plan to be deployed, and operates from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service, which is a service in which the computer cluster to be operated is defined. Create a derived service generation procedure that generates a derived service to which a part is transferred, and a resource plan that optimally allocates the derived service group generated by the derived service generation procedure to the plurality of computer clusters based on a predetermined evaluation index. It is characterized by having a computer execute the planning procedure to be performed.</p><p> According to the present invention, a derived service is generated in which a part of the operation is transferred from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service which is a service in which the computer cluster to be operated is defined. , Since the resource plan for allocating the generated derived services to multiple computer clusters is created based on a predetermined evaluation index, some of the services operated by the overloaded computer cluster will be replaced by the entire computer cluster system. be able to.</p>

<p> According to the present invention, a part of the services operated by the overloaded computer cluster is taken over by the entire computer cluster system, so that each computer cluster can be prevented from being overloaded and the computing resources of the computer cluster can be efficiently used. It has the effect of being able to be used.</p>

A preferred embodiment of the resource planning program according to the present invention will be described in detail below with reference to the accompanying drawings. Here, the case where the present invention is applied to the creation of a resource plan for allocating the computational resources of a plurality of data centers to a plurality of services will be mainly described.

First, the concept of the resource plan according to this embodiment will be described. FIG. 1 is an explanatory diagram for explaining the concept of the resource plan according to the present embodiment. The graph on the left side of Fig. 1 plots the annual load fluctuation forecast for the WEB service provided by the XX ticket sales company.

The height shown by the horizontal dotted line in this graph represents the amount of load that can be processed by the amount of resources held by the company's own center of the XX ticket sales company. The load fluctuation in this graph has two peaks, and both peaks exceed the load amount (dotted line height) that can be processed by the company's center resources. Therefore, in the resource plan according to this embodiment, a derived service is generated in a data center other than the company's own center at the peak time, and the load exceeding the dotted line is taken over.

Here, during the peak occurrence period on the left side, the data center X consumes almost no resources, while the data center Y consumes most of the resources by other services. Therefore, the derived service is placed in the data center X at the peak on the left side.

On the other hand, during the peak occurrence period on the right side, most of the resources in data center X are consumed by other services, etc., and resources are hardly consumed in data center Y, so derived services are placed in data center Y. To do.

That is, in the resource plan according to this embodiment, the original center having a large amount of idle resources temporarily surplus due to the low load of the primitive service in operation is selected from among the plurality of original centers. Treat as a temporary logistical support center and operate derivative services at the temporary logistical support center.

Based on this mode of operation, the division of roles between the original center and the back support center is not unique to each data center, data center X constantly operates primitive service A, and data center Y. Data center X may always serve as the original center for primitive service A and as a back-up support center for primitive service B if .. Hereafter, here, the division of roles between the original center and the logistical support center will be determined by the relative relationship with the service as described above.

Here, when trying to operate a large number of primitive services in an environment where many data centers are connected by a network, when a certain primitive service becomes overloaded in the future, which data center is used for derivative service operation. The question is whether to select it as a back support center. In other words, the question is when and when each derived service that is expected to occur in the future should be placed in which data center.

However, it is necessary to consider the amount of calculation and the calculation time when searching for the optimum solution for how to arrange each derived service occurring at a certain future point in each computer cluster. For example, if you have three data centers and 30 derived services are occurring at the same time at some point in time, then one derived service is two data centers other than the original center of the original service from which it originated. Since it can be placed in either of the two, there are two ways to place 30 derived services in three data centers (2 to the 30th power (1 billion or more)).

Therefore, it is a huge waste of time to evaluate all of these by simple search, and when finding the optimum solution for the placement of the derived service set in the data center set, the optimum solution that can keep the number of search steps as small as possible can be suppressed. A search method is required.

Specifically, given a group of data centers and a set of primitive services, and an original center that operates each primitive service is specified, the future occurrence time of derived services is predicted in advance, and the computational resources of all data centers. In order to improve utilization efficiency, it is necessary to optimize the data center for each derived service that occurs at various points in time (center placement of the derived service) (Fig. 2).

In addition, the configuration of the derived service set, the load processed by each derived service, the resource consumption status of each data center, etc. change from moment to moment, so it is optimal to arrange the derived service set in the data center group over time. It is necessary to redo the conversion regularly. When re-optimizing the above arrangement on a regular basis, the time axis is divided into cycles called time slots, and the optimum derived service arrangement is obtained for each time slot (Fig. 3).

Therefore, in the end, the optimum candidate for the arrangement pattern of the derived service set in the data center group is obtained for each fixed time cycle (for each time slot), and the information is arranged in chronological order in the time slot time order. Need to output. This output information is hereinafter referred to as a data center group resource plan.

In addition, when searching for the time series of the optimum derived service arrangement, the search space becomes huge depending on the number of derived services that occur at the same time, and a simple search takes an enormous amount of time. In the relevant resource plan, the following measures will be taken.

The solution to be searched is generally evaluated by a plurality of indexes, and the solution that optimizes all the indexes as much as possible must be finally selected, but at least one index from the search space seems to be optimal. A set consisting of various solutions (Pareto solution set) is narrowed down, an arbitrary solution is selected from the Pareto solution set according to a specific criterion, and the solution is used as a provisional solution.

Then, the provisional solution is asymptotically brought closer to the true optimum solution by the NDC replacement operation described later, and when the evaluation value of the provisional solution reaches a certain radius of convergence, the provisional solution is output as the final optimum solution.

The services operated by the data center include transaction-type services such as WEB services, which require real-time response so that a response must be returned within a few seconds after receiving a user request, and daily and monthly services. There is a batch type service that needs to complete all processing of a plurality of job groups submitted at a predetermined time in a fixed cycle such as by a predetermined deadline time.

A batch-type service is composed of a plurality of jobs, and is generally divided into a plurality of times, and a plurality of jobs are collectively submitted to a data center at a predetermined time. This job submission schedule is repeated at regular intervals such as a daily cycle or a monthly cycle. The job submission schedule is specified in advance by the outsourcer that outsources the operation of the batch service.

Regarding the batch type service, as long as all the submitted job groups are processed by the specified deadline time, each job may be processed at any time, so to speak, real-time performance is not required.

Therefore, if the primitive service set operated in the data center group consists of two types of services, a transaction type service and a batch type service, consider that the transaction type service is a service that requires real-time performance. However, the computing resources of the data center group are preferentially allocated to the transaction type service.

Thereafter, tiger it is necessary to perform generation of the resource planning that allocates the spare computing resources not assigned to Nzakushon service to process the batch services. Therefore, in order to generate the resource plan of the data center group, first, the resource plan is generated assuming that only the transaction type primitive service is operated in the data center group, and the resource plan is assigned to the transaction type service in the resource plan. Generate a resource plan for batch-type services for surplus transaction resources that have not been created.

In addition, regarding the load fluctuation prediction of the batch type primitive service, since the job submission schedule of the batch type service is known in advance, it may be possible to predict the future load fluctuation of the service by a mathematical prediction algorithm such as the ARIMA model method. Instead, future load fluctuations can be planned by a specific job scheduling algorithm.

Therefore, in the generation of the resource plan for the set of batch-type primitive services, the future load fluctuation of the batch-type primitive services is not predicted, but the one planned in advance by the job scheduling algorithm is used.

The specific job scheduling algorithm will be described later, but the feature of the scheduling algorithm is that each job constituting the batch type primitive service is scheduled in the order of the latest input time, and the job to be scheduled is selected. , The job is scheduled at the time when the surplus computational resources of the data center group are the largest in the time zone between the input time of the job and the deadline time.

The reason for adopting such a job scheduling algorithm is that the load processing of the batch type service is performed by selecting the time when the load of the transaction type service is free as much as possible.

Next, the configuration of the resource planning apparatus according to this embodiment will be described. FIG. 4 is a functional block diagram showing the configuration of the resource planning apparatus according to this embodiment. As shown in the figure, the resource planning apparatus 100 includes a transaction planning unit 110, a batch planning unit 120, and a resource planning transmission unit 130.

The transaction planning unit 110 is a processing unit that creates a resource plan for a transaction type service, and is a prediction unit 111, a derived service generation unit 112, a DC generation unit 113, an NDC generation unit 114, and an optimum solution search unit. Has 115 and.

In the following description of the transaction planning unit 110, the service, the primitive service, and the derived service mean a transaction type service unless otherwise specified. Further, in the generation of the resource plan of the transaction type service, the length of the time slot shall be manually determined by the operator of the data center group as a unique value for the entire data center group.

The prediction unit 111 is a processing unit that predicts the future of load fluctuations of all primitive services to be operated. Here, the period to be predicted is hereinafter referred to as a prediction period, and its length is one day, one month, one year, or the like.

The derived service generation unit 112 obtains the occurrence time of the derived service, the number of occurrences, and the load distribution ratio between each derived service and the primitive service based on the load fluctuation prediction by the prediction unit 111 and the amount of resources owned by the original center. It is a processing unit.

The following are examples of conditions for generating derived services. Figures 5-1 and 5-2 are explanatory diagrams (1) and (2) for explaining the conditions under which the derived service occurs. Figure 5-1 shows the case where the derived service is generated when the resource utilization of the primitive service located in the data center exceeds 90%.

In addition, Figure 5-2 calculates the average of the resource utilization of the three data centers X, Y, and Z, and generates the derived service when the resource utilization of each data center becomes 1.2 times or more of the average. Shows the case.

In reality, the derived service generation unit 112 calculates the standard deviation of the resource usage rate by the primitive service for each data center, and adopts the generation condition that the derived service is generated when the value exceeds a certain threshold value. ing.

The DC generation unit 113 divides the prediction period into time slots with a fixed cycle, and generates all candidates for the placement combination pattern that determines in which data center the derived services generated in the time slot are placed in each time slot. It is a processing unit.

Here, each candidate of the generated placement combination pattern is called a DC (Deployment Candidate), and the DC belonging to the set of DCs generated for the time slot (t) is referred to as the DC belonging to the time slot (t). Call.

The NDC generation unit 114 is a processing unit that creates an NDC (Normal DC) excluding VDC (Violating DC) from the DCs belonging to each time slot. Here, VDC is a plurality of evaluation indexes m.₁, ..., m_kEvaluation result by₁, ..., e_kIs a DC that violates certain conditions, and NDC is any other DC.

The evaluation index is such that the resource utilization efficiency of the entire data center group is improved by optimizing the arrangement combination of the derived service group in the data center group by using the evaluation index. For example, the load Equality (Fig. 6-1), NDC similarity (Fig. 6-2), etc. Here, it is assumed that the smaller the evaluation value is, the better the evaluation is.

Figure 6-1 shows that the load placement is not even and bad and the load placement is even and good in the three data centers X, Y and Z. The better the placement, the better the load equality value. Shall be small.

Figure 6-2 shows the movement of derived services between the four data centers W, X, Y and Z when moving from time slot (K-1) to time slot (K) and from time slot (K). It shows the movement of derived services when moving to the time slot (K + 1). Here, the larger the number of service movements at the time of time slot transition with the passage of time, the larger the NDC similarity value. To do.

The optimal solution search unit 115 is a processing unit that creates an optimal NDC series based on the Pareto optimality theory. Here, the NDC series is a series in which NDCs are selected one by one from each time slot and arranged in chronological order in the order of time slots. In other words, creating the optimal NDC series will create the optimal resource plan.

Specifically, the optimum solution search unit 115 evaluates k evaluation values of each NDC constituting the NDC series for each NDC series.₁, ..., e_kThe series evaluation value E is the sum of each of the above over the entire NDC series.₁, ..., E_kAnd.

And k series evaluation values E₁, ..., E_kAmong the above, all the ones having the smallest one or more series evaluation values are selected and used as the initial series set. In this initial series set, the set of NDC series is used as the solution space, and k series evaluation values E₁, ..., E_kCorresponds to the Pareto solution set in a multi-objective optimization problem when each of the above is used as an objective function.

Then, the NDC series that minimizes the value of the series evaluation function ξ is selected from the obtained initial series set and used as the quasi-optimal NDC series. Then, for each time slot, each NDC constituting the semi-optimal NDC series is compared with all other NDCs belonging to the same time slot as the NDC, and if the following replacement conditions are satisfied, the former NDC Is replaced with the latter NDC.

Where e_i(T_p, c) is the time slot T in the suboptimal NDC series_pE about NDC belonging to_iIs the value of, e_i(T_p, O) is the time slot T_pE for NDCs that belong to NDC but are not included in the suboptimal NDC series_iDefined as the value of.

And time slot T_pFor all k evaluation values of NDC in the suboptimal NDC series belonging to, e_i(T_p, c) e_i(T_p, o) If (1 i k), replace the NDC. That is, as a result of NDC replacement, if the evaluation values are improved for all the evaluation values constituting the set of k evaluation values, the NDC is replaced.

Also, replace the NDC in the following cases. If some of the evaluation values that make up a set of k evaluation values are improved by replacement and the other evaluation values are deteriorated, the replacement control function is added to the improvement amount of the improved evaluation values. If the weighted average of the applied values exceeds the weighted average of the values to which the replacement control function is applied to the deterioration amount of the evaluation value to be deteriorated, the replacement is performed.

That is, the set of integers I = [i | 1 i k] can be divided into two subsets I1 and I2, and e if i I1._i(T_p, c) e_i(T_p, O) and e if i I2_i(T_p, c)&gt; e_i(T_p, O), the following equation (1)<maths num="1"><img file="JP2005293048A_D0001.tif" /></maths>If holds true, perform the NDC swap operation. Where φ_iIs the weighting factor, Δe_i(T_p) = e_i(T_p, c) -e_i(T_p, o), δe_i(T_p) = e_i(T_p, o) -e_i(T_p, c), Λ_iAnd λ_iIs the evaluation value e_iIt is a replacement control function for.

Then, the quasi-optimal NDC series corrected by NDC replacement is evaluated by the series evaluation function ξ, and compared with the value evaluated by ξ of the quasi-optimal NDC series before the NDC replacement operation, the improvement rate is set to a certain threshold. If it falls below the limit, the quasi-optimal NDC series is used as the resource plan for the data center group, and if not, the NDC series corrected by the NDC replacement is used as the new quasi-optimal NDC series, and the NDC replacement is repeated.

Here, a specific example of the processing of the optimum solution search unit 115 will be described with reference to FIGS. 7 to 12. FIG. 7 is an explanatory diagram for explaining the outline of the optimization procedure by the optimum solution search unit 115. Here, the equality of load and the similarity of NDC are used as evaluation indexes.

As shown in the figure, the optimum solution search unit 115 generates an initial candidate group of the provisional solution based on the similarity of NDC as the optimization step (1), and as the optimization step (2), the provisional solution. The initial candidate group of is evaluated using the equality of load and the similarity of NDC, and the one with the smallest evaluation value is used as a provisional solution.

Then, as the optimization step (3), a better provisional solution is generated by exchanging the NDC with respect to the provisional solution, and as the optimization step (4), it is determined whether or not the convergence condition is satisfied, and when the convergence condition is satisfied. Outputs the provisional solution as the final solution, and if the convergence condition is not satisfied, returns to the optimization step (3) and repeats the replacement of NDC until the convergence condition is satisfied.

FIG. 8 is an explanatory diagram for explaining the concept of the NDC table used for explaining the optimization procedure. As shown in the figure, the NDC table is a table in which NDCs belonging to each time slot are arranged in order of good load equality. Each optimization step will be described below using this NDC table.

FIG. 9 is an explanatory diagram for explaining the optimization step (1). As shown in the figure, in this optimization step, NDCs having "NDC similarity = 0" are connected between adjacent time slots to generate a similar NDC sequence. For example, in FIG. 9, a plurality of similar NDC sequences such as a similar NDC series starting with NDC (1) in time slot (0) and a similar NDC series starting with NDC (2) in time slot (0) are obtained. Be done.

When connecting NDCs to each other, if there is no NDC with "NDC similarity = 0", the NDC with the smallest NDC similarity is selected. As a result, the generated similar NDC series uses the similarity of NDC as an evaluation index, and is the NDC series having the smallest value of this evaluation index, and these are used as the initial candidate group of the provisional solution. In addition, the NDC series composed of NDCs having the minimum load equality in each time slot is the NDC series having the smallest total load equality as a whole series, and this is also included in the initial candidate group of the provisional solution.

FIG. 10 is an explanatory diagram for explaining the optimization step (2). As shown in the figure, in this optimization step, all similar NDC series are evaluated using the load equality and the similarity of NDC as evaluation indexes, and the best similar NDC series with the smallest series evaluation value Ec is used as the provisional solution. ..

FIG. 11-1 is an explanatory diagram for explaining the optimization step (3). As shown in the figure, in this optimization step, the NDCs are replaced when the NDCs other than the NDCs included in the provisional solution satisfy a predetermined condition in each time slot of the provisional solution.

Here, the predetermined condition is, as shown in Fig. 11-2, if there is an NDC that simultaneously improves the load equality and the similarity of the NDC, the evaluation value E in that time slot._iSelect the one with the smallest value of and replace it.

If only one of them is improved, do as follows. When only the load equality is improved, the load equality improvement amount ΔL is larger than the value BL (ΔS) obtained by evaluating the NDC analogy deterioration amount ΔS with a predetermined function. -When the one with the maximum BL (ΔS) value is selected and only the similarity is improved, the amount of deterioration of the load equality is greater than the value BL (ΔS) obtained by evaluating the improvement amount ΔS of the similarity with a predetermined function. Among the NDCs in which ΔL is larger, the one with the largest value of BL (ΔS) -ΔL is selected and replaced.

FIG. 12 is an explanatory diagram for explaining the optimization step (4). As shown in the figure, in this optimization step, the improvement rate of the series evaluation value Ec of the best similar NDC series that has undergone NDC replacement processing is investigated, and if the improvement rate is within 3%, for example, the convergence condition is satisfied. If the convergence condition is not satisfied, the process returns to the optimization step (3) and the replacement process is repeated.

In this way, the initial candidate group of the NDC series is generated based on the similarity of the NDC, the best similar NDC series with the smallest series evaluation value Ec is set as the provisional solution from the initial candidate group, and the provisional solution is improved by replacing the NDC. By doing so, the optimum NDC series can be obtained. Although two evaluation indexes of load equality and NDC similarity are used here, in general, any number of evaluation indexes can be used. In addition, the improvement rate used for the convergence condition can be a value other than 3%.

The batch planning unit 120 is a processing unit that generates a resource plan for a batch type primitive service set, and includes a load amount calculation unit 121, a batch type derived service generation unit 122, a batch type DC generation unit 123, and a batch type. It has an NDC generation unit 124 and a batch type optimum solution search unit 125.

In the following explanation of the batch planning unit 120, it is assumed that the job submission schedule is repeated in a one-day cycle and a resource plan for a transactional service with a forecast period of one day is obtained. To do.

In addition, the time required to process one job of a batch type service on one server with standard performance is called "turnaround time", and the length of this time is unique for each batch type service. It is decided.

In addition, the amount of load that can be handled by one server with standard performance is called "unit server performance". The deadline time and turnaround time are unique values for each batch-type primitive service. Further, the time difference between the input time of each job of the batch type service and the start time of the prediction period is an integral multiple of the turnaround time of the batch type service.

The load amount calculation unit 121 is a processing unit that calculates a future load amount. Specifically, the load amount calculation unit 121 calculates the future load amount by the following procedure. First, find the least common multiple of the turnaround time of all batch-type primitive services, and use this value as the new time slot length.

Then, for each data center and each measurement cycle, the load amount that can be handled by the surplus resources existing in the data center (not assigned to the transaction type service) in the measurement cycle is divided by the unit server performance. , Convert the amount of surplus resources into the expression of the number of standard performance servers (hereinafter this is referred to as the number of surplus servers).

Then, the future load fluctuation of each batch type primitive service within the forecast period is initialized to 0. After that, for each batch-type primitive service, the job submission schedule for each batch-type service is set to "Time t.₁To n₁Submit jobs, t₂To n₂Input the matter, ..., t_kTo n_kWhen "Enter", execute the following (S1) to (S5) for each integer i for which 1 i k. However, t₁&gt; t₂&gt; ...&gt; t_kAnd.

(S1) Time t_iThe period from to the deadline time of the batch-type primitive service (this is called a schedule period) is divided into a time quantum having the length of the turnaround time of the batch-type primitive service. (S2) For each time quantum in each data center, find the measurement cycle that minimizes the number of surplus servers, and use the number of surplus servers at that time as the number of surplus servers for that time quantum.

(S3) In each time quantum, the data center with the largest number of surplus servers is searched, the data center is set as the maximum center in that time quantum, and the total number of surplus servers is totaled over all data centers for each time quantum. Then, the total value is used as the R value of the time quantum.

(S4) Search for the time quantum with the maximum R value, subtract the value of the number of surplus servers of the maximum center in the time quantum by 1, and recalculate the maximum center and R value for the time quantum. The load amount equal to the unit server performance is added to the load amount of the portion corresponding to the time quantum of the future load fluctuation of the batch type primitive service. (S5) n_iSubtract 1 from n_iIf&gt; 0, it returns to (S3).

The batch-type derived service generation unit 122 is a processing unit that generates a batch-type derived service based on the load amount representing the future load fluctuation calculated by the load amount calculation unit 121. Specifically, the batch-type derived service generation unit 122 determines the time when the batch-type derived service is generated from the batch-type primitive service based on the load amount representing the future load fluctuation for each batch-type primitive service.

At that time, an appropriate number of batch-type derived services shall be generated from the batch-type primitive services, and the load of the batch-type primitive services shall be appropriately distributed among the batch-type derived services. Then, for each time slot, a set of batch-type derived services generated in that time slot is generated.

The batch type DC generation unit 123 is a processing unit that generates all candidates (DCs) of the arrangement combination pattern of the batch type derived service set generated in the time slot in the data center group for each time slot.

The batch type NDC generation unit 124 is a processing unit that creates an NDC obtained by removing VDC from DC. That is, the batch type NDC generator 124 has an evaluation index m for each time slot.₁, ..., m_kEvaluate each DC belonging to the time slot based on, and the evaluation value e for each DC₁, ..., e_kTo calculate.

Then, for each time slot, each DC belonging to that time slot is evaluated as an evaluation value e.₁, ..., e_kClassify into NDC and VDC based on, and exclude VDC from the set of DCs belonging to the relevant time slot.

The batch-type optimum solution search unit 125 is a processing unit that creates a batch-type resource plan. That is, this batch-type optimum solution search unit 125 generates a Pareto solution set (initial series set) from the NDC series set by the same method as in the case of the transaction type service, and the series evaluation function is generated from the initial series set. Select the NDC series with the smallest value and use it as the semi-optimal NDC series.

Then, the NDC corresponding to each time slot in the suboptimal NDC series is replaced by the NDC replacement operation (similar to the case of the transaction type service), and the values of the series evaluation functions of the suboptimal NDC series before and after the NDC replacement operation are compared. However, if the improvement rate is 3% or less, the semi-optimal NDC series is set as a batch type resource plan, and if not, the NDC replacement is repeated.

The resource plan transmitter 130 connects the created resource plan to the n data centers 10 via the Internet 20.₁~10_nIt is a processing unit that sends to. Each data center operates the service according to the resource plan transmitted by the resource plan transmission unit 130.

Next, the processing procedure of the transaction planning unit 110 shown in FIG. 3 will be described. In the following, an XML-based WEB service is assumed as an example of a transaction type service, and all primitive services are assumed to be WEB services.

Further, the time axis representing the prediction period for which the load fluctuation of the primitive service is predicted is divided into time slots having a fixed cycle, and each time slot is divided into a measurement cycle which is a cycle for measuring the load of the primitive service. Then, N is the total number of time slots included in the forecast period._t, T the i-th time slot in the forecast period (counting from the earliest time on the time axis)_iIt is expressed as.

The load of the service at time t is the number of user requests per second arriving at the service at time t. Here, the set of data centers is C = [c_i| 1 i N_c], Set of primitive services P = [p_i| 1 i N_p], Time slot T_iThe set of all derived services occurring within the period of D (T)_i) = [d (T)_i, j) | 1 j n (T)_i)], A set of k evaluation indexes for evaluating DC [m₁, m₂, ..., m_k], A set of k evaluation values that evaluated DC with k evaluation indexes [e₁, e₂, ..., e_k], E of each NDC that composes the NDC series_iIs the sum of the entire NDC series and the series evaluation value E_i, Time slot T_iThe set of NDCs belonging to Γ (T)_i) = [γ (T)_i, j) | 1 j ν (T_i)], Let S be the set of the entire NDC series.

Also, in the NDC that constitutes a certain NDC series s S, the time slot T_iNDC belonging to γ_s(T_iWrite, j) and NDCγ (T)_iEvaluation value e calculated for, j)_iThe value of e_i(γ (T)_i, j)). Therefore, one instance of the NDC series s S has s = &lt;γ._s(T₁, j₁), γ_s(T₂, j₂), γ_s(T₃, j₃), ..., γ_s(T_Nt-1, j_Nt-1), γ_s(T_Nt, j_Nt)&gt;.

Also, data center c_iIs a primitive service p_jBeing the original center of_j c_iEtc., c_iR (c) is the load amount (number of requests per second) that can be handled using the total amount of resources of_i).

In addition, here, three indexes m defined below as evaluation indexes for evaluating DC.₁, m₂, m₃It was adopted. Where m₁Represents the degree of load equality of the entire data center group when the derived services are arranged according to the DC to be evaluated. This is because in order to minimize the peak resource requirement that should be prepared in each data center of the data center group, the load amount should be evenly distributed among all the data centers over the entire prediction period.

Also, m₂Represents the traffic between derived services. When each primitive service is an XML-based WEB service, there may be a case where the primitive services communicate with each other by the SOAP protocol. In such a case, the derived services generated from those primitive services also perform SOAP communication.

Therefore, when each derived service is placed in the destination data center according to a certain DC, each of a plurality of derived services that frequently exchange a large amount of data with each other by SOAP communication is placed in a different data center. In that case, the amount of communication between data centers increases significantly.

If the communication delay of SOAP communication increases due to the lack of bandwidth of the communication path, an unnecessary load is applied to each data center as a result. Therefore, as an evaluation index for DC, the amount of communication between derived services m₂It was adopted.

Also, m₃Represents the similarity of NDC. Time slot T_iNDC γ (T) belonging to_i, j₁The definition of similarity in) is as follows. When a certain NDC series is defined, the NDC that constitutes the NDC series has a time slot T._i-1NDC corresponding to γ (T_i-1, j₀), Time slot T_iNDC corresponding to γ (T_i, j₁), Time slot T_{i + 1}NDC corresponding to γ (T_{i + 1}, j₂), The time slot becomes T as time passes._i-1From T_iWhen transitioning to, the placement of the derived service set in the data center group is γ (T)._i-1, j₀) To γ (T_i, j₁With the change to), the derived service set [D (T)_i-1) D (T_i)] Some derived services may be moved from one data center to another.

Also, the time slot is T_iFrom T_{i + 1}Similarly, when transitioning to, the derived service allocation is γ (T)._i, j₁) To γ (T_{i + 1}, j₂With the change to), [D (T)_i) D (T_{i + 1})] May be moved between data centers.

So time slot T_iNDC γ (T) in the NDC series corresponding to_i, j₁) Similarity, time slot is T_i-1From T_iThe number of derived services and the time slot that can be moved between data centers for the above reasons when transitioning to T_iFrom T_{i + 1}It is assumed that the number of derived services that can be moved between data centers when transitioning to is totaled.

In other words, the fact that the similarity of a certain NDC is large means that if the derived service is arranged according to the NDC, the number of movements of the derived service due to the transition of the time slot increases, and the service is moved to the data center group by that amount. Control load will be applied.

As a result, each data center bears a large amount of load that normally does not need to be processed, so it is necessary to adopt NDC similarity as one of the NDC evaluation indexes. In addition, m₃Is m₁, m₂Unlike NDC alone, it cannot be evaluated, and it can be evaluated only after the NDC series is specified.

FIG. 13 is a flowchart showing a processing procedure of the transaction planning unit 110 shown in FIG. As shown in the figure, in the transaction planning unit 110, first, the prediction unit 111 has 1 i N._pFor all integers i that_iPredict the load fluctuation prediction over the entire prediction period using existing prediction methods such as ARIMA model prediction (step S101). In addition, p_iLoad fluctuation prediction is p_iExpressed as a time function of the load of, p at time t_iThe load amount of is θ_iIt will be expressed as (t).

Then, the derived service generation unit 112 generates the derived service based on the load fluctuation prediction and the resource amount of the original center (step S102). The details of how to generate the derivative service based on the load fluctuation prediction will be described later. And 1 i N_tT for each integer i_iD (T), a set of derived services that are expected to occur during the period of_i) Is generated (step S103).

Then, the DC generator 113 has 1 i N._tFor each integer i that is_iAll possible placement combinations (DCs) for the data center group C of each derived service belonging to) are generated by the tree search algorithm, and the time slot T is generated._iThe set of placement combination candidates generated for is Γ (T)_i) (Step S104).

Then, the NDC generator 114 moves 1 i N._tEach integer i, 1 j ν (T)_iΓ (T) for all combinations of each integer j that is_i, j) Γ (T_i) Is the evaluation index m₁, m₂Evaluate with and evaluate value e₁, e₂(Step S105). In addition, γ (T_i, j) about e₁And e₂The details of the procedure for calculating the above will be described later.

And 1 i N_tEach integer i, 1 j ν (T)_iFor all combinations of each integer j that is), e₁(γ (T)_i, j))&gt; 0.7 or e₂(γ (T)_i, j))&gt; 0.8 then γ (T)_iLet, j) be VDC and set Γ (T)_i). Otherwise, γ (T_iSet Γ (T) with, j) as NDC_i) (Step S106).

Then, the optimal solution search unit 116 defines the NDC series set S (step S107), and k series evaluation values E in the NDC series included in the NDC series set S.₁(s), E₂(s), E₃Find all the NDC series s in which any one or more of (s) has the minimum value, and use them as the elements of the initial series set (step S108).

However,<maths num="2"><img file="JP2005293048A_D0002.tif" /></maths>And. The details of the procedure for extracting the initial series set (Pareto set) from the NDC series set S will be described later.

Then, the NDC series belonging to the initial series set is evaluated by the series evaluation function ξ (s), and the NDC series having the smallest evaluation value is defined as the quasi-optimal NDC series σ (step S109). However, with k = 3<maths num="3"><img file="JP2005293048A_D0003.tif" /></maths>And. Also, K₁= 1.0, K₂= 1.0, K₃= 0.1.

And 1 i N_tTime slot T corresponding to each integer i_iTherefore, the NDC replacement process is performed (step S110), and the quasi-optimal NDC series before the NDC replacement is σ'and the quasi-optimum NDC series after the NDC replacement is σ. ) | / ξ (σ') is calculated (step S111). The details of the NDC replacement process will be described later.

Then, it is determined whether or not the improvement rate is 0.03 or less (step S112), and if the improvement rate is 0.03 or less, σ is output as the resource plan of the data center group C, and all the processing is completed (step S112). Step S113). Otherwise, return to step S110 with σ as the new σ'.

In this way, the optimal solution search unit 115 creates the optimal resource plan for the data center group by generating the optimal NDC series based on the Pareto optimization theory for the derived service generated by the derived service generator 112. be able to.

Next, the details of the derived service generation by the derived service generation unit 112 will be described. The derived service generation unit 112 performs the following (S1) to (S3) for each measurement cycle for all measurement cycles.

(S1) Center time t of measurement cycle, 1 i N_cFor the integer i that is_j c_iFor all j<maths num="4"><img file="JP2005293048A_D0004.tif" /></maths>And set [Θ_i / R (c_i) | 1 i N_c ] Is regarded as the sample distribution, the standard deviation is calculated, and if the standard deviation is 0.1 or less, go to (S3), otherwise go to (S2).

(S2) 1 i N_cFor each integer i that becomes p_iPart of the load at time t is divided as a derived service. Here, the method of dividing the load amount to the derived service is as follows.

N derived services from each primitive service_c-Assuming that one occurred at a time, determine a temporary center placement for each derived service. The distribution ratio of the load of the assumed derivative service and the primitive service is calculated as follows.

Optimize the above distribution ratio using linear programming so that the following conditions are met: When each derived service is placed in the above temporary center layout, each data center c_i(1 i N_c), The total load of the primitive service and the derivative service operating there is g_iSample set [g_i/ R (c_i) | 1 i N_c] Standard deviation should be 0.1 or less.

If the integer programming does not provide a split ratio that satisfies the above conditions, the temporary center placement of each derived service should be randomly changed, and the split ratio should be optimized again by the integer programming. By repeating this, the division ratio of the load amount to be divided into the derivative services for each primitive service is obtained.

However, N_cEven if it is&gt; 5, the upper limit of the number of derived services that can be generated from one primitive service at the same time is 4. If the distribution ratio determined by the above method for a derived service is 0, the derived service is treated as nonexistent. (S3) Move to the next measurement cycle and start (S1) for a new measurement cycle.

Next, γ (T_i, j) about e₁The details of the procedure for calculating the above will be described. Time slot T_iSet the center time of the measurement cycle contained in [t]ⁱ_h| 1 h N_m]. That is, time slot T_iThe center time of the hth measurement cycle from the start ofⁱ_hAnd N in one time slot_mIt is assumed that the number of measurement cycles is included.

Data center c_r(1 r N_c) Is the total load at time t of all services._rIf (t), then γ (T)_ie for, j)_iThe value of is obtained as follows.

First, 1 r N_cTime series of total load for each center for each integer r [g_r(tⁱ_h) | 1 h N_m ], 1 r N_cFor each integer r that is a time series [g_r(tⁱ_h) / R (c_r) | 1 h N_m ] Average value on the time axis<maths num="5"><img file="JP2005293048A_D0005.tif" /></maths>To ask.

And the set [μ (0, i), μ (1, i), μ (2, i), ..., μ (N)_c, i)] is regarded as the sample distribution, the standard deviation is calculated, and this standard deviation is γ (T)._ie for, j)_iThe value of.

Next, γ (T_i, j) about e₂The details of the procedure for calculating the above will be described. First, for each measurement cycle in the time slot T to which the evaluation target NDC belongs, the amount of communication by SOAP communication between services is estimated in units of bps for each data center.

Then, for each data center, the estimated communication volume is divided by the bandwidth value (bps unit) of the communication path connecting the data center and the external network to obtain a value (hereinafter referred to as a communication path occupancy rate).

Then, the value obtained by averaging the communication path occupancy rate for each measurement cycle over the entire time slot T is calculated for each data center. E The average value in the data center where the average value is the maximum₂The value of.

When the relationship between the primitive services that communicate with each other is as shown in FIG. 14, the data center c_iAn example of the procedure for estimating the amount of SOAP communication between services when the measurement cycle in is t is shown below.

Where e₂The set of derived services for which the destination data center is specified in the NDC evaluated by D = [d_k| 1 k N_d], D_kData center is c_iThat d_k c_iEtc. The value of the load of service X expressed in the number of requests per second is expressed as L (X, t). Also, primitive service p_jIs d_kThat it is a primitive service from which_j d_kEtc.

First, in the estimation of the communication volume between the first and second stages in FIG. 14, the data center c at the measurement cycle t._iValue B in₁(c_i, t) is calculated. First, B₁(c_iInitialize, t) with 0, and consider the following four cases separately.

(1) p₁ c_iAnd p₂ c_iIn the case of B₁(c_i, t) = B₁(c_i, t) + | L (p)₁, t) × ω₁ --L (p)₂, t) |

(2) p₁ c_iAnd p₂ c_iIf not (p₂ d_h) (d_h c_i) Let H be the set of all subscripts h<maths num="6"><img file="JP2005293048A_D0006.tif" /></maths>

(3) p₂ c_iAnd p₁ c_iIf not (p₁ d_h) (d_h c_i) Let H be the set of all subscripts h<maths num="7"><img file="JP2005293048A_D0007.tif" /></maths>

(4) p₁ c_iNot p₂ c_iIf not (p₁ d_h) (d_h c_iLet H be the set of all subscripts h that are (), and (p.₂ d_k) (d_k c_i) Let K be the set of all subscripts k<maths num="8"><img file="JP2005293048A_D0008.tif" /></maths>

Next, in the estimation of the communication volume between the second and third stages in Fig. 14, the data center c at the measurement cycle t_iValue B in₂(c_i, t) is calculated. First, B₁(c_iInitialize, t) with 0, and consider the following four cases separately.

(1) p₂ c_iAnd p₃ c_iIn the case of B₂(c_i, t) = B₂(c_i, t) + | L (p)₂, t) × ω₂ --L (p)₃, t) |

(2) p₂ c_iAnd p₃ c_iIf not (p₃ d_h) (d_h c_i) Let H be the set of all subscripts h<maths num="9"><img file="JP2005293048A_D0009.tif" /></maths>

(3) p₃ c_iAnd p₂ c_iIf not (p₂ d_h) (d_h c_i) Let H be the set of all subscripts h<maths num="10"><img file="JP2005293048A_D0010.tif" /></maths>

(4) p₂ c_iNot p₃ c_iIf not (p₂ d_h) (d_h c_iLet H be the set of all subscripts h that are (), and (p.₃ d_k) (d_k c_i) Let K be the set of all subscripts k<maths num="11"><img file="JP2005293048A_D0011.tif" /></maths>

Where ω (c_i, t) = ω₁(c_i, t) + ω₂(c_iBy setting, t), the data center c at the measurement cycle t_iEstimated traffic ω (c)_i, T) is obtained.

Next, the details of the procedure for extracting the initial series set (Pareto set) from the NDC series set S will be described. First, the series evaluation value E₁Find s S that minimizes (s). Generally, there are a plurality of such s.

Specifically, 1 i N_tΓ (T) for each integer i_i) Stores all NDCs belonging to) in an array and e₁Sort the array using the value of Γ (T)_i) In e₁Set of NDCs with the smallest value of Γ^{b b}(T_i) Is generated. And the Cartesian product Γ^{b b}(T₀) × Γ^{b b}(T₁) × ... × Γ^{b b}(T_Nt) For each NDC series belonging to the series evaluation value E₁Let s S so that (s) is minimized.

Next, the series evaluation value E₂Find s S that minimizes (s). That is, 1 i N_tΓ (T) for each integer i_i) Stores all NDCs belonging to) in an array and e₂Sort the array using the value of Γ (T)_i) In e₂Set of NDCs with the smallest value of Γ^{b b}(T_i) Is generated. And the Cartesian product Γ^{b b}(T₀) × Γ^{b b}(T₁) × ... × Γ^{b b}(T_Nt) For each NDC series belonging to the series evaluation value E₂Let s S so that (s) is minimized.

Next, the series evaluation value E₃Find s S that minimizes (s). Here, the set Γ of NDC over the entire time axis is defined as follows.<maths num="12"><img file="JP2005293048A_D0012.tif" /></maths>

And 1 k N_AEach integer k and 1 i N_tThe following processing is performed for all combinations of each integer i that becomes. Set Γ (T_i), Search for NDC, and γ (T)_i, j) Γ (T_i), 1 j ν (T_i) And γ_kAnd γ (T_iSubscript j that minimizes relative similarity when comparing, j)^k_iFind the value of.

Here, the relative similarity is the arrangement specified by one NDC among the derived services that are commonly included in both the derived service arrangements specified by the two NDCs when comparing the two NDCs. Represents the number of derived services for which the destination data center and the destination data center specified in the other NDC are different.

And 1 k N_ANDC series s (k) = &lt;γ (T) expressed as follows for each integer k₀, j^k₀), Γ (T₁, j^k₁), ..., γ (T_Nt, j^k_Nt)&gt;.

Finally, the set [s (k) | 1 k N_A] Of the NDC series s (k) included in₂Select the one with the smallest value of (s (k)).

E as above₁(s), E₂(s), E₃All NDC series whose minimum value is one of (s) are selected from S and used as elements of the Pareto set (initial series set).

Next, the details of the NDC replacement process will be described. The following (S1) to (S3) are performed as the NDC replacement process. (S1) Set Γ (T)_i), Γσ (T_i, j₁) And γ (T_i, j₂) (However, j₁ j₂The following relationship holds between (and) j₂To ask. e₁(γσ (T_i, j₁))&gt; e₁(γ (T)_i, j₂)) e₂(γσ (T_i, j₁))&gt; e₂(γ (T)_i, j₂)) e₃(γσ (T_i, j₁))&gt; e₃(γ (T)_i, j₂))

J that meets the above conditions₂If is found, γσ (T_i, j₁) And γ (T_i, j₂) By replacing γ (T_i, j₂) Is the time slot T in the NDC series σ_iSet the NDC corresponding to (S3) and proceed to (S3). J that meets the above conditions₂If is not found, proceed to (S2).

(S2) Set Γ (T)_i), Γσ (T_i, j₁) And γ (T_i, j₂) (However, j₁ j₂The following relationship holds between (and) j₂To ask.<maths num="13"><img file="JP2005293048A_D0013.tif" /></maths>

Here, I1 and I2 are subsets of the integer set [h | 1 h 3] divided into two without an intersection, and e when h I1._h(γσ (T_i, j₁)) e_h(γ (T)_i, j₂)), And e when h I2_h(γσ (T_i, j₁))&gt; e_h(γ (T)_i, j₂)) And also Δe_h = e_h(γσ (T_i, j₁))-e_h(γ (T)_i, j₂)), δe_h= e_h(γ (T)_i, j₂))-e_h(γσ (T_i, j₁)).

J that meets the above conditions₂If is found, γσ (T_i, j₁) And γ (T_i, j₂) By replacing γ (T_i, j₂) Is the time slot T in the NDC series σ_iNDC corresponding to. J that meets the above conditions₂If not found, time slot T_iNDC will not be replaced. Where λ₁, λ₂, λ₃, Λ₁, Λ₂, Λ₃Definition and φ₁, φ₂, φ₃The value of is as follows.

λ₁(x) = x λ₂(x) = x λ₃(x) = 0.1 × exp (1.3x) Λ₁(x) = x Λ₂(x) = x Λ₃(x) = 0.1 × exp (1.3x) φ₁= 1.0 φ₂= 1.0 φ₃= 1.0 However, exp () is an exponential function based on the base of the natural logarithm.

(S3) Move to the next time slot with i = i + 1, and return to (S1).

Next, the processing procedure of the batch planning unit 120 shown in FIG. 3 will be described. As an example of the batch type service, a calculation service for aggregating the sales information of each store of the convenience store can be considered.

Below, here, the set of batch-type primitive services is P = [p._i| 1 i N_p], p_iTurnaround time for each job in τ_i, Data center c_iIn c_iR is the amount of resources required for ci when the total load of all services placed in is at its peak, expressed in terms of the number of requests per second._max(c_i), Of the resources of the data center ci, the amount of surplus computational resources remaining unallocated to the WEB service at time t is R (c)._i, T), the value of the unit server performance is f, and the definitions of other symbols are the same as those used in the explanation of the processing procedure of the transaction planning unit 110.

Also here, p_iThe time difference between the input time of each job and the start time of the forecast period is τ_iIs an integral multiple of τ_iIs an integral multiple of the transaction load measurement cycle.

In addition, in the generation of resource plans related to batch-type services, among the evaluation indexes adopted in the generation of resource plans for WEB services, m is used as an index to evaluate NDC.₁And m₃Adopt only. This is because it is usually impossible for batch services to perform SOAP communication with each other, so this is an evaluation index for the amount of SOAP communication between services.₂Is meaningless to consider.

FIG. 15 is a flowchart showing a processing procedure of the batch planning unit 120 shown in FIG. As shown in the figure, in the batch planning unit 120, first, the load amount calculation unit 121 is τ.₁, τ₂, ..., τ_NpFind the least common multiple of, and use that value as the length of the time slot (step S201).

Then, the time axis is divided into time slots, and 1 i N._cFor each integer i that is_i, t) = R (c_i, T) / f, and each batch type primitive service p by the job scheduling algorithm described later._i(1 i N_p), Plan future load fluctuations (step S202). In addition, p_iFuture load fluctuations related to are generated as time series data, and p at future time t_iThe load amount of is expressed as θ (i, t).

Then, the batch-type derived service generation unit 122 generates the batch-type derived service based on the load amount calculated by the load amount calculation unit 121 (step S203). The details of the batch-type derived service generation by the batch-type derived service generation unit 122 will be described later.

And 1 i N_tFor each integer i that is_iD (T), a set of derived services that are expected to occur during the period of_i) Is generated (step S204).

Then, the batch type DC generator 123 has 1 i N._tFor each integer i that is_i) Is generated by the tree search algorithm for all possible placement combinations (DCs) of each derived service in the data center group C (step S205), and the time slot T is generated._iThe set of placement combination candidates generated for is Γ (T)_i).

Then, the batch type NDC generator 124 determines 1 i N._tEach integer i, 1 j ν (T)_iΓ (T) for all combinations of each integer j that is_i, j) Γ (T_i) Is the evaluation index m₁Evaluate with and evaluate value e₁(Step S206).

And 1 i N_tEach integer i, 1 j ν (T)_iFor all combinations of each integer j that is), e₁(γ (T)_i, j))&gt; 0.7 then γ (T)_iLet, j) be VDC and set Γ (T)_i). Otherwise, γ (T_iSet Γ (T) with, j) as NDC_i) (Step S207).

Then, the batch-type optimum solution search unit 125 creates the NDC series set S (step S208), and k series evaluation values E in the NDC series included in the NDC series set S.₁(s), E₃Find all the NDC series s in which any one or more of (s) has the minimum value, and use them as the elements of the initial series set (step S209).

However,<maths num="14"><img file="JP2005293048A_D0014.tif" /></maths>And.

Then, the NDC series belonging to the initial series set is evaluated by the series evaluation function ξ (s), and the NDC series having the smallest evaluation value is defined as the quasi-optimal NDC series σ (step S210). However, ξ (s) = K₁E₁(s) + K₂E₂Let it be (s). Also, K₁= 1.0, K₃= 0.1.

And 1 i N_tTime slot T corresponding to each integer i_iThe NDC replacement process, which will be described later, is performed (step S211). Then, the improvement rate is calculated using the evaluation value of the quasi-optimal NDC series before the NDC replacement with ξ () and the evaluation value of the quasi-optimal NDC series after the NDC replacement with ξ () (step S212). ).

Then, it is determined whether or not the improvement rate is 3% or less (step S213), and if the improvement rate is 3% or less, the current semi-optimal NDC series is output as a resource plan (step S214), and all processing is completed. .. Otherwise, return to step S211.

Next, a job scheduling algorithm for planning future load fluctuations of batch-type primitive services will be described. Each batch type primitive service p_i(1 i N_p) Job submission schedule, turnaround time, deadline time are as shown in Fig. 16, each batch type primitive service p_i(1 i N_p) Executes the following (S1) to (S9).

However, the start time of the forecast period is t₀Then, for any i and j, t (i, j) -t₀= TA (i) × N, TD (i) -t0 = TA (i) × N'(where N and N'are integers), and TA (i) is an integral multiple of the length of the measurement cycle. Suppose there is. Also, let f be the unit server performance.

(S1) Let j = ρ (i). Also, θ at each time t within the forecast period._i(t) = 0. (S2) Data center c that is not assigned to any transactional or batch service at each time t within the forecast period._kThe amount of surplus resources in R (c_k, T) η (c)_k, t) = R (c_k, t) / f is calculated.

(S3) The time zone from time t (i, j) to time TD (i) is divided into time quantims of the length of TA (i), and the start time is in the order of earliest from time t (i, j). Let Q (i, j, h) be the hth time quantum. Also N_QLet (i, j) = (TD (i) -t (i, j)) / TA (i).

(S4) 1 h N_QEach integer h that is (i, j) and 1 k N_cThe following processing is performed for each combination of integers k that becomes. Among the multiple measurement cycles included in the time quantum Q (i, j, h), η (c) at the center time t of the measurement cycle_kFind the measurement cycle that minimizes the value of, t), and η (c) at the center time t of the measurement cycle._kThe value of, t) is the surplus resource amount η (Q (i, j, h), c) in Q (i, j, h)._k).

(S5) 1 h N_QThe following processing is performed for each integer h that becomes (i, j). η (Q (i, j, h), c_kFind the value of the subscript k that maximizes), and let this be k (i, j, h).<maths num="15"><img file="JP2005293048A_D0015.tif" /></maths>To calculate.

(S6) Find the value of the subscript h that maximizes the value of η (i, j, h), and find the value of η (c)._{k (i, j, h)}Subtract 1 from, t) and R (c)_{k (i, j, h)}Subtract f from, t). (S7) θ for each time t such that t (i, j) + TA (i) × h t t (i, j) + TA (i) × (h + 1)_i(t) = θ_iLet (t) + f.

(S8) Subtract 1 from n (i, j) and return to (S5) if n (i, j)&gt; 0. (S9) If j is 1, the process ends. Otherwise, return to (S2) with j = j-1. Θ obtained as a result of executing the above procedure_iThe value of (t) is the batch type primitive service p_iIt is the future load at the future time t of.

Next, the details of batch-type derived service generation by the batch-type derived service generation unit 122 will be described. The batch type derived service generator 122 has 1 i N._cFor each integer i that is, execute the following (S1) and (S2). Here, the data center c at time t_iThe total load of the WEB service is g (c)_i, t).

(S1) The following processing is executed in each measurement cycle within the prediction period. At the center time t of the measurement cycle, p_j c_iWhen the set of all subscripts j is J<maths num="16"><img file="JP2005293048A_D0016.tif" /></maths>Then p_h c_iBecomes p_hLoad amount θ'(h, t) at time t<maths num="17"><img file="JP2005293048A_D0017.tif" /></maths>And.

However,<maths num="18"><img file="JP2005293048A_D0018.tif" /></maths>Is.

(S2) The following processing is executed in each measurement cycle within the prediction period. When the central time of the measurement cycle is t, p_j c_iWhen the set of all subscripts j is J<maths num="19"><img file="JP2005293048A_D0019.tif" /></maths>Then p_h c_iEach batch type primitive service p_hFrom N at time t_c-Generate one batch-type derived service, and set the load amount of each batch-type derived service at time t as follows.<maths num="20"><img file="JP2005293048A_D0020.tif" /></maths>

Next, the details of the NDC replacement process will be described. The following (S1) to (S3) are performed as the NDC replacement process. (S1) Set Γ (T)_i), Γσ (T_i, j₁) And γ (T_i, j₂) (However, j₁ j₂The following relationship holds between (and) j₂To ask. e₁(γσ (T_i, j₁))&gt; e₁(γ (T)_i, j₂)) e₃(γσ (T_i, j₁))&gt; e₃(γ (T)_i, j₂))

J that meets the above conditions₂If is found, γσ (T_i, j₁) And γ (T_i, j₂) By replacing γ (T_i, j₂) Is the time slot T in the NDC series σ_iSet the NDC corresponding to (S3) and proceed to (S3). J that meets the above conditions₂If is not found, proceed to (S2).

(S2) Set Γ (T)_i), Γσ (T_i, j₁) And γ (T_i, j₂) (However, j₁ j₂The relationship between either of the following equations (S2) and (S3) holds between them.₂To ask.<maths num="21"><img file="JP2005293048A_D0021.tif" /></maths><maths num="22"><img file="JP2005293048A_D0022.tif" /></maths>

However, λ (x) = 0.1 × exp (1.3 × x). J that meets the above conditions₂If is found, γσ (T_i, j₁) And γ (T_i, j₂) By replacing γ (T_i, j₂) Is the time slot T in the NDC series σ_iNDC corresponding to. J that meets the above conditions₂If not found, time slot T_iNDC will not be replaced. (S3) Move to the next time slot with i = i + 1, and return to (S1).

Next, the simulation result of resource planning creation by the resource planning creation device 100 according to this embodiment will be described. FIG. 17 is a diagram showing a simulation result of resource planning creation by the resource planning creation device 100 according to this embodiment.

As shown in the figure, the Consumer traffic in Data Center X is divided into three parts during heavy load in the morning and night, and is also processed in Data Center Y and Data Center Z. In addition, the store traffic in data center Z is divided into three at the peak of morning and evening, and processing is also performed in data center X and data center Y.

As described above, in the present embodiment, the prediction unit 111 of the transaction planning unit 110 predicts the load of the primitive service for a plurality of transaction-type services operated by the plurality of data centers, and the derived service generation unit 112. Generates a derived service based on the load prediction by the prediction unit 111 and the amount of computational resources of the data center, and the optimal solution search unit 115 creates an optimal resource plan for the derived service generated by the derived service generation unit 112.

Further, for a plurality of batch-type services operated by a plurality of data centers, the load amount calculation unit 121 predicts the load of the primitive service, and the batch-type derivative service generation unit 122 of the batch planning unit 120 performs the load amount calculation unit. Derived services are generated based on the amount of computational resources not used for load prediction by 121 and processing of transactional services, and the batch-type optimal solution search unit 125 makes an optimal resource plan for the derived services generated by the derived service generator 122. create.

Therefore, the optimum load allocation according to the computational resources can be performed for each data center, so that the overload of the data center can be prevented and the computational resources of the data center can be used efficiently.

In addition, such resource plan generation processing determines the load distribution ratio between each derived service and the source service that originated it, the time when each derived service occurs, and the data center where it is located at that time. The time fluctuation transition of the total amount of the primitive service load and the derived service load within the forecast period can be obtained for each center.

Based on this, it is possible to estimate the peak load amount of the data center when the derived service is appropriately generated according to the load fluctuation for each data center, and this estimated load amount is derived. The value can be smaller than the peak load of each data center when no service is generated or when each derived service is improperly arranged.

Further, in the present embodiment, the case where the load prediction, the creation of the optimum resource plan, and the transmission of the resource plan to the data center are performed only by the resource plan creation device 100 has been described, but the present invention is not limited to this. For example, the same can be applied to the case where the load prediction unit 111 is performed by another device.

Further, in this embodiment, the resource planning creation device has been described, but by realizing the configuration of the resource planning creation device by software, a resource planning creation program having the same function can be obtained. Therefore, a computer system that executes this resource planning program will be described.

FIG. 18 is a diagram showing a computer system that executes the resource planning creation program according to this embodiment. As shown in the figure, the computer system 200 includes a main body 201, a display 202 that displays information on the display screen 202a according to an instruction from the main body 201, and a display 202 for inputting various information into the computer system 200. It has a keyboard 203, a mouse 204 that specifies an arbitrary position on the display screen 202a of the display 202, a LAN interface that connects to LAN 206 or a wide area network (WAN), and a modem that connects to public line 207. Here, the LAN 206 connects another computer system (PC) 211, a server 212, a printer 213, and the like to the computer system 200.

Further, FIG. 19 is a functional block diagram showing the configuration of the main body 201 shown in FIG. As shown in the figure, the main body 201 includes CPU221, RAM222, ROM223, hard disk drive (HDD) 224, CD-ROM drive 225, FD drive 226, I / O interface 227, and LAN. It has an interface 228 and a modem 229.

The resource planning program executed in the computer system 200 is stored in a portable storage medium such as a floppy disk (FD) 208, a CD-ROM209, a DVD disk, a magneto-optical disk, or an IC card, and these storage media. It is read from and installed on the computer system 200.

Alternatively, this resource planning program is stored in the database of the server 212 connected via the LAN interface 228, the database of another computer system (PC) 211, etc., and is read from these databases and stored in the computer system 200. It will be installed.

Then, the installed resource planning program is stored in HDD224 and executed by CPU221 using RAM222, ROM223, and the like.

Further, in the present embodiment, the case where the service is arranged in the data center has been described, but the present invention is not limited to this, and the same can be applied to the case where the service is arranged in another computer cluster. it can.

For example, there is a case where the set of computational resources constituting the inside of each data center is divided into a plurality of sections, and independent operation management is performed for each section. In this case, optimize which derived service is to be placed when and when for each partition, determine which primitive service is constantly operated in which partition, and select the derived service from the primitive service operated there for each partition. It is also possible to determine the future time point to generate.

(Appendix 1) A resource plan creation program that creates a resource plan for allocating multiple services operated by a computer cluster system consisting of multiple computer clusters composed of multiple computers connected to the multiple computer clusters. Then, a derived service generation that generates a derived service in which a part of the operation is transferred from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service which is a service in which the computer cluster to be operated is defined. It is characterized by having a computer execute a procedure and a planning procedure for creating a resource plan for arranging a group of derived services generated by the derived service generation procedure in the plurality of computer clusters based on a predetermined evaluation index. Resource planning program.

(Appendix 2) The derived service generation procedure generates a derived service for each time slot in which the prediction period of the load prediction is divided into a plurality of time slots at predetermined time intervals, and the planning creation procedure is for each time slot. The resource plan creation program according to Appendix 1, wherein the time slot allocation plan, which is the allocation plan of the derived service of the above, is arranged in the time slot time order to create an allocation plan series as the resource plan.

(Appendix 3) The resource planning creation program described in Appendix 2 is characterized in that the planning procedure creates a resource plan for optimally arranging derived service groups in the plurality of computer clusters based on the Pareto optimality theory. ..

(Appendix 4) The plan creation procedure is characterized in that the load equality between computer clusters and the similarity of the time slot arrangement plans between adjacent time slots on the time axis are used as evaluation indexes. Resource planning program described in.

(Appendix 5) In the plan creation procedure, the layout plan series having the best evaluation when the similarity and load equality are used as evaluation indexes is set as the initial series set, and the layout plan series included in the initial series set is set. The resource planning creation program according to Appendix 4, wherein the resource planning is created by making corrections so as to improve the evaluation of the load equality.

(Appendix 6) The resource plan described in any one of the appendices 1 to 5, characterized in that the computer further executes the resource plan transmission procedure for transmitting the resource plan created by the plan creation procedure to each computer cluster. Creation program.

(Appendix 7) The description in any one of Appendix 1 to 6, wherein the computer cluster is a data center, and the computer cluster system is a system in which a plurality of data centers are connected via a network. Resource planning program.

(Appendix 8) The derived service generation procedure is characterized in that individual jobs may be processed at any time as long as all the jobs constituting the service have been processed by the specified deadline time. When a non-real-time batch type service is operated as a set of computer clusters, the resources of the computer cluster are preferentially allocated to the transaction type service that requires real-time performance, and the remaining surplus. In order to allocate resources to the batch type service, a resource plan is generated for the transaction type service, and then a resource plan for the batch type service is generated for the surplus resources that were not allocated. The resource planning program described in 1.

(Appendix 9) In the above-mentioned planning procedure, all the jobs constituting each batch-type primitive service are targeted for execution planning in order from the one whose input time is closest to the deadline time, and the surplus is not used by any service. The resource planning creation program according to Appendix 1, which generates an execution plan of the job to be scheduled for the period in which the sum of the total amount of computational resources is maximized over the entire set of computer clusters.

(Appendix 10) Record a resource plan creation program that creates a resource plan for allocating multiple services operated by a computer cluster system consisting of multiple computer clusters composed of multiple computers connected to the multiple computer clusters. Derived service that is a computer-readable recording medium and whose operation is transferred from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service, which is a service in which the computer cluster to be operated is defined. The derived service generation procedure for generating the above and the planning creation procedure for creating the resource plan for arranging the derived services generated by the derived service generation procedure in the plurality of computer clusters based on a predetermined evaluation index are executed on the computer. A computer-readable recording medium characterized by recording a resource planning program.

(Appendix 11) This is a resource plan creation method for creating a resource plan in which multiple services operated by a computer cluster system composed of a plurality of computer clusters composed of a plurality of computers are connected to the plurality of computer clusters. Then, a derived service generation that generates a derived service in which a part of the operation is transferred from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service which is a service in which the computer cluster to be operated is defined. It is characterized by including a process and a plan creation process for creating a resource plan for optimally arranging the derived service group generated by the derived service generation process in the plurality of computer clusters based on a predetermined evaluation index. How to create a resource plan.

(Appendix 12) A resource plan creation device that creates a resource plan for allocating multiple services operated by a computer cluster system, which is composed of multiple computer clusters composed of multiple computers, to the multiple computer clusters. Then, a derived service generation that generates a derived service in which a part of the operation is transferred from each computer cluster to another computer cluster based on the load prediction of the primitive service from the primitive service which is a service in which the computer cluster to be operated is defined. It is characterized by being provided with means and a planning means for creating a resource plan for optimally arranging a group of derived services generated by the derived service generating means in the plurality of computer clusters based on a predetermined evaluation index. Resource planning device.

As described above, the resource planning program according to the present invention is useful for allocating services to a plurality of data centers, and is particularly suitable for data centers that need to eliminate overload and make effective use of computational resources. ..

<figref num="1">It is explanatory drawing for demonstrating the concept of resource planning which concerns on this Example.</figref><figref num="2">It is explanatory drawing for demonstrating derivation service occurrence and arrangement optimization.</figref><figref num="3">It is explanatory drawing for demonstrating the arrangement optimization of the derived service for every time slot.</figref><figref num="4">It is a functional block diagram which shows the structure of the resource planning apparatus which concerns on this Example.</figref><figref num="5-1">It is explanatory drawing (1) for demonstrating the occurrence condition of a derived service.</figref><figref num="5-2">It is explanatory drawing (2) for demonstrating the occurrence condition of a derived service.</figref><figref num="6-1">It is explanatory drawing for demonstrating the degree of equality of a load.</figref><figref num="6-2">It is explanatory drawing for demonstrating the similarity of NDC.</figref><figref num="7">It is explanatory drawing for demonstrating the outline of the optimization procedure.</figref><figref num="8">It is explanatory drawing for demonstrating the concept of an NDC table.</figref><figref num="9">It is explanatory drawing for demonstrating the optimization step (1).</figref><figref num="10">It is explanatory drawing for demonstrating the optimization step (2).</figref><figref num="11-1">It is explanatory drawing for demonstrating the optimization step (3).</figref><figref num="11-2">It is a figure which shows the replacement condition.</figref><figref num="12">It is explanatory drawing for demonstrating the optimization step (4).</figref><figref num="13">It is a flowchart which shows the processing procedure of the transaction planning part shown in FIG.</figref><figref num="14">It is a figure which shows the example of the service set which SOAP communicates with each other.</figref><figref num="15">It is a flowchart which shows the processing procedure of the batch planning part shown in FIG.</figref><figref num="16">It is a figure which shows the example of the job input schedule of a batch type primitive service.</figref><figref num="17">It is a figure which shows the simulation result of the resource plan creation by the resource plan creation apparatus 100 which concerns on this Example.</figref><figref num="18">It is a figure which shows the computer system which executes the resource planning creation program which concerns on this Example.</figref><figref num="19">It is a functional block diagram which shows the structure of the main body part shown in FIG.</figref>

Code description

10₁~10_n Data center 20 Internet 100 Resource planning device 110 Transaction planning unit 111 Prediction unit 112 Derived service generation unit 113 DC generation unit 114 NDC generation unit 115 Optimal solution search unit 120 Batch planning unit 121 Load calculation unit 122 Batch type derived service generation unit 123 Batch type DC generator 124 Batch type NDC generator 125 Batch type optimal solution search unit 130 Resource plan transmission unit 200,211 Computer system 201 Main unit 202 Display 202a Display screen 203 Keyboard 204 Mouse 206 LAN207 Public line 208 Floppy disk 209 CD-ROM212 Server 213 Printer 221 CPU222 RAM223 ROM224 Hard disk drive 225 CD-ROM drive 226 Floppy disk drive 227 I / O interface 228 LAN interface 229 modem