JP6969261B2 - Node management device, node management method and program - Google Patents

Description

The present invention relates to a node management device, a node management method, and a program for managing a plurality of nodes that process requests in cooperation with each other.

A distributed processing system is known as an example of a system consisting of a plurality of nodes that process requests in cooperation with each other. In this distributed processing system, load balancing is performed in order to prevent the load bias of each node and maintain the overall processing efficiency. Load balancing includes static load balancing and dynamic load balancing. The former is a method of allocating a process to a node by a predetermined allocation. The latter is a method of monitoring the load of a node and allocating processing to a node having a light load. In general, dynamic load balancing is expected to be more load-balanced according to the actual situation than static load balancing.

As an example of a distributed processing system, Patent Document 1 describes a production control system that manages the entire process of a production line. In this production control system, inventories or work-in-process completion schedules are sequentially allocated from product inventory for each process toward the source process, and inventory or allocation, surplus, and shortage of each process are determined. The shortage is converted into charges, and the required preparation date and the required number of preparations are obtained. Then, the reserved portion and the required preparation portion are piled up from the headwater process to the downstream process, and the scheduled preparation date and the scheduled completion date of each process are obtained.

Japanese Unexamined Patent Publication No. 11-48102

In the distributed processing system described above, processing is assigned to nodes by a predetermined allocation, but it is not possible to predict the processing load of each node when actually processing a request. For this reason, it may not be possible to deal with the node in time, resulting in an overload. In addition, the load may be reduced more than necessary.
Even in the production control system described in Patent Document 1, since the processing load cannot be predicted, the same problem as the above-mentioned distributed processing system arises.

An object of the present invention is to provide a node management device, a node management method and a program capable of solving the above problems.

In order to achieve the above object, the first node management device of the present invention has a plurality of nodes that process requests in cooperation with each other, between the processing load when each node processes the request and the node of the request. It has an analysis unit that analyzes the transition, and a prediction unit that predicts the processing load of each node for a desired number of requests based on the processing load and the analysis result of the transition.

The first node management method of the present invention analyzes the processing load when each node processes the request and the transition between the nodes of the request for a plurality of nodes that process the request in cooperation with each other.
It includes predicting the processing load of each node for a desired number of requests based on the processing load and transition analysis results.

The first program of the present invention is a process of analyzing the processing load when each node processes the request and the transition between the nodes of the request for a plurality of nodes that process the request in cooperation with each other, and the process. A computer is made to perform a process of predicting the processing load of each node for a desired number of requests based on the load and transition analysis results.

It is possible to estimate overloaded and underloaded nodes and take appropriate measures such as load balancing and congestion control at an early stage.

It is a block diagram which shows the structure of the node management apparatus by 1st Embodiment of this invention. It is a block diagram which shows the structure of the node management apparatus by the 2nd Embodiment of this invention. It is a flowchart which shows one procedure of the node management processing performed by the node management apparatus shown in FIG. It is a figure for demonstrating an example of the aggregation result of the processing load and the transition destination node information. It is a figure for demonstrating an example of the count value of the number of requests which transitioned between each node. It is a figure for demonstrating an example of the calculation process of the transition probability that a request transitions between nodes. It is a figure for demonstrating an example of prediction using a transition probability matrix. It is a figure for demonstrating an example of the transition probability adjustment table.

Next, an embodiment of the present invention will be described with reference to the drawings.
(First Embodiment)
FIG. 1 is a block diagram showing a configuration of a node management device according to the first embodiment of the present invention. In addition, in FIG. 1, the unidirectional arrow simply indicates the direction of the flow of a certain signal (data or information), and does not exclude bidirectionality.
Referring to FIG. 1, the node management device 11 has an analysis unit 12 and a prediction unit 13. The analysis unit 12 analyzes the processing load when each node processes a request and the transition between the request _{nodes for a plurality of nodes 15 1} to 15 _n that process the request in cooperation with each other. The prediction unit 13 predicts the processing load of each node for the desired number of requests w based on the analysis result of the processing load and the transition from the analysis unit 12.

According to the node management device 11 described above, since the processing load of each node can be quantitatively predicted for a desired number of requests w, an overloaded node or a low-loaded node can be estimated, and load balancing and congestion control can be performed. Appropriate measures such as can be taken at an early stage.

The node management device 11 may be provided with one control unit having the functions of the analysis unit 12 and the prediction unit 13. Further, the control unit may be realized by a computer equipped with a CPU (Central Processing Unit) or the like. In this case, the functions of the analysis unit 12 and the prediction unit 13 may be realized by the computer executing the program.

The program may be for the computer to execute the processing corresponding to each function of the analysis unit 12 and the prediction unit 13. For example, the program analyzes the processing load when a node processes a request and the transition between the request _{nodes for a plurality of nodes 15 1} to 15 _n that process the request in cooperation with each other, and the processing load. And the process of predicting the processing load of each node for a desired number of requests based on the analysis result of the transition may be performed by the computer. The program may be provided on a computer-enabled or computer-readable medium, or may be provided via a network such as the Internet.

Computer-enabled or computer-readable media include media on which information can be recorded or read using magnetism, light, electrons, electromagnetics, infrared rays, and the like. Such media include, for example, semiconductor memories, semiconductor or solid storage devices, magnetic tapes, removable computer diskettes, random access memory (RAM), read-only memory (ROM), magnetic disks, optical disks, optomagnetic disks, etc. There is.

Further, in the node management device 11, the analysis unit 12 indicates, for the nodes 15 ₁ to 15 _n , the processing load when the node processes the request and the transition destination node information indicating the transition destination of the request processed by the node. And may be aggregated, and the processing load and the tendency of the transition destination may be analyzed based on the aggregated result.
Further, the analysis unit 12 may calculate the transition probability of the request between the nodes, and the prediction unit 13 may predict the processing load of each node based on the transition probability of the request.
Further, the analysis unit 12 _{counts the number of requests transitioned between each node for the nodes 15 1} to 15 _n for each unit processing load, calculates a transition probability matrix based on the count value, and the prediction unit 13 determines. The processing load of each node may be predicted based on the transition probability matrix.

Further, in the node management device 11, for each node, the predicted value of the processing load predicted by the prediction unit 13 and the permissible value are compared, and when the predicted value exceeds the permissible value, a predetermined message is output. The unit may be further provided. The predetermined message may be, for example, a message indicating a warning.
Further, the countermeasure unit may output a countermeasure message for reducing the processing load of the node whose predicted value exceeds the allowable value. In this case, the countermeasure may be any one of improvement of the processing load, relaxation of the allowable value, relaxation of the number of requests, and reduction of the transition probability, or a combination of two or more.

(Second embodiment)
FIG. 2 is a block diagram showing a configuration of a node management device according to a second embodiment of the present invention. In FIG. 2, the unidirectional arrow simply indicates the direction of the flow of a certain signal (data or information), and does not exclude bidirectionality.
Referring to FIG. 2, the node management device 21 is a device that predicts and monitors the processing load of the distributed processing system 10, and is a transition detection unit 22, a transition aggregation analysis unit 23, a processing load prediction unit 24, and a request number acquisition. It has a unit 25, a countermeasure calculation unit 26, and an allowable load acquisition unit 27. The transition aggregation analysis unit 23, or the portion including the transition detection unit 22 and the transition aggregation analysis unit 23 can be referred to as an analysis unit. The processing load prediction unit 24 and the request number acquisition unit 25 can be referred to as a prediction unit. The countermeasure calculation unit 26 and the allowable load acquisition unit 27 can be referred to as a countermeasure unit.

The distributed processing system 10 has a plurality of nodes 1 to 5 that process requests (number of requests = w) in cooperation with each other. Here, specific processing is assigned to each of the nodes 1 to 5. The request consists of a series of processes and is processed by the node corresponding to the process. When the processing at a certain node is completed, the request determines the processing to be performed next and transitions to the corresponding next node. The request repeats processing and transition, and all processing is completed within a finite time. The processing load of the node when processing the request shall be measurable or estimateable.

The transition detection unit 22 detects the transition between the requesting nodes. The transition detection result is supplied from the transition detection unit 22 to the transition aggregation analysis unit 23.
The transition aggregation analysis unit 23 aggregates the processing load when the node processes the request and the transition destination node information indicating the transition destination of the request processed by the node for the nodes 1 to 5. For example, the transition aggregation analysis unit 23 may aggregate information indicating on which node each request was processed discretely for each unit amount of the processing load. The transition aggregation analysis unit 23 analyzes the processing load and the tendency of the transition destination based on the aggregation result of the processing load and the transition destination node information. The transition aggregation analysis unit 23 supplies the analysis result to the processing load prediction unit 24.

The transition detection unit 22 may inquire each node about the processing load and the transition destination node information. Alternatively, each node may voluntarily report the processing load of its own node and the transition destination node information to the transition detection unit 22. Alternatively, the transition detection unit 22 may monitor the communication of each node and detect the timing of starting the processing of the request and the passing of the request, thereby totaling the processing load and the transition destination node information.

The request number acquisition unit 25 acquires the number of requests to be processed by the nodes 1 to 5. For example, the request number acquisition unit 25 may accept input of the expected number of requests to each node. The request number acquisition unit 25 supplies the acquired request number to the processing load prediction unit 24.
The processing load prediction unit 24 predicts the processing load of each node for a desired number of requests based on the analysis result from the transition aggregation analysis unit 23. The desired number of requests is supplied from the request number acquisition unit 25. The processing load prediction unit 24 supplies the predicted value of the processing load of each node to the countermeasure calculation unit 26.

The allowable load acquisition unit 27 acquires the allowable value of the processing load of the nodes 1 to 5. For example, the allowable load acquisition unit 27 may accept the input of the allowable value of the processing load. The allowable load acquisition unit 27 supplies the acquired allowable value to the countermeasure calculation unit 26.
The countermeasure calculation unit 26 compares the predicted value and the allowable value of the processing load for each node. When the predicted value exceeds the permissible value, the countermeasure calculation unit 26 outputs a warning message, calculates a countermeasure for the node, and outputs a message indicating the countermeasure. The countermeasure calculation unit 26 can be called a notification unit.

Next, the operation of the node management device 21 of the present embodiment will be specifically described.
FIG. 3 is a flowchart showing one procedure of the node management process performed by the node management device 21.

First, the transition detection unit 22 detects the transition between the requested nodes. Then, the transition aggregation analysis unit 23 aggregates the processing load of each node and the transition destination node information (step S10).
Next, the transition aggregation analysis unit 23 analyzes the processing load of each node and the tendency of the transition destination based on the aggregation result obtained in step S10 (step S11). Next, the processing load prediction unit 24 predicts the processing load of each node with respect to the number of requests acquired by the request number acquisition unit 25 based on the processing load obtained in step S11 and the tendency analysis result of the transition destination (step). S12).

Next, the countermeasure calculation unit 26 determines whether or not the predicted value of the processing load obtained in step S12 is larger than the allowable value acquired by the allowable load acquisition unit 27 for each node (step S13). When the predicted value is larger than the permissible value, the countermeasure calculation unit 26 outputs a warning message, calculates a countermeasure for the node, and outputs a message indicating the countermeasure.

Below, the processing load and transition destination node information aggregation processing (step S10), processing load and transition destination trend analysis processing (step S11), processing load prediction processing (step S12), and warning / countermeasure calculation processing (step S14). ) Will be explained in detail.
In the following, the processing time is used as a measure of the processing load of the node. That is, the unit processing time is used as the unit processing load when analyzing the request transitioning between the nodes. As a case different from this, when the processing load is evaluated by, for example, the communication amount, the unit communication amount may be used as the unit processing load.

Aggregation processing of processing load and transition destination node information (step S10)
FIG. 4 shows an example of the aggregation result of the processing load and the transition destination node information. In FIG. 4, "a", "b", and "c" indicate requirements, respectively. The aggregation result of FIG. 4 is the aggregation of the information indicating which of the nodes 1 to 5 the requests a to c were processed for each unit processing time in the processing order. In this example, assuming that the processing load is evaluated by the processing time, the transition aggregation analysis unit 23 aggregates the information about the request transition for each unit processing time in each node.

Node 1 processes the request a from the cumulative processing time (hereinafter, time) 0, processes the request b at the time 3, and processes the request c at the times 4 and 5. The node 2 processes the request a at time 1 and the request c at time 6. The node 3 processes the request a at time 2, the request b at time 4, and the request c at times 7 and 9. Node 4 processes the request a at time 3 and the request c at times 8 and 10. The node 5 processes the request a at time 4, processes the request b at time 5, and processes the request c at time 11.

When the time changes from t to t + 1, a request that moves from one node to another indicates that the processing at one node has finished within that unit processing time and has transitioned to the next node. For example, at time 0, node 1 processes request a, and at time 1, node 2 processes request a. In this case, the request a is a request in which the nodes are moved over the unit processing time.
Also, even if the time changes from t to t + 1, a request that stays at a certain node indicates that the processing at a certain node did not end within the unit processing time and the node did not transition. For example, node 1 is processing request c at times 4 and 5. In this case, the request c is a request that stays at the same node over a unit processing time.

The above processing load and transition destination node information aggregation processing (step S10) may be performed up to the processing for analyzing the processing load and transition destination tendency described below (step S11). That is, it may be performed periodically for each unit processing time, sequentially for each transition, or collectively immediately before step 11.

Processing load and transition destination tendency analysis processing (step S11)
The transition aggregation analysis unit 23 calculates a transition probability matrix as an analysis result. That is, the transition aggregation analysis unit 23 calculates a transition probability matrix in which a request is processed by a unit processing load at a certain node and then transitions to the next node.
For example, the transition aggregation analysis unit 23 counts the number of requests that have transitioned between each node for each unit processing load, and calculates a transition probability matrix based on the count value. The calculation process of this transition probability matrix will be specifically described with the following example.
In the following example, the aggregated result of the processing load (processing time) and the transition destination node information shown in the above example is used. Therefore, the processing load shall be evaluated by the processing time.

[Calculation of the number of times a request has transitioned from node i to node j]
FIG. 5 shows an example of the count value of the number of requests transitioned between each node. The result of counting the number of requests based on the aggregation result shown in FIG. 4 is shown by using the transition counter Cij which accumulates the number of times the request has transitioned from the node i to the node j for each unit processing time. Here, i and j are given within the range of the number of nodes constituting the distributed processing system 10.

In FIG. 5, the transition counter Cii counts the number of times the request has transitioned from node i to node i, that is, the number of times the request has stayed at node i. In the aggregation result of FIG. 4, since the request c stays at the node 1 at the cumulative processing times (hereinafter, time) 4 and 5, the count value of the transition counter C11 becomes “1” at the time 4. After that, the transition counter C11 maintains the count value "1" until time 11.

The transition counter Cij counts the number of times a request has transitioned from node i to node j. In the aggregation result of FIG. 4, since the request a transitions from the node 1 to the node 2 from the time 0 to 1, the count value of the transition counter C12 at the time 0 is set to “1”. After that, the transition counter C12 maintains the count value "1" until time 4. Further, since the request c is transitioning from the node 1 to the node 2 from the time 5 to 6, the count value of the transition counter C12 at the time 5 is set to “2”. After that, the transition counter C12 maintains the count value "2" until time 11.

The other transition counters C13 to C15, C21 to C25, C31 to C35, C41 to C45, and C51 to C55 of FIG. 5 are also requested based on the aggregation result of FIG. 4 by the same principle as the transition counter C11 or the transition counter C12. Count the transitions between the nodes of.

[Calculation of transition probability that a request transitions from node i to node j]
FIG. 6 shows an example of a transition probability calculation process in which a request transitions between nodes. In this example, the result of calculating the transition probability Pij in which the request transitions from the node i to the node j is shown based on the count result shown in FIG.

The transition probability Pij in which a request transitions from the transition source node to the transition destination node is the value obtained by dividing the number of requests transitioned from the transition source node i to the transition destination node j by the total number of requests transitioned from the transition source node i (probability). Value).
In FIG. 6, P11 indicates the probability that the request transitions from node 1 to node 1, that is, the probability that the request stays at node 1. The transition probability P11 is given by dividing the number of requests staying at node 1 by the total number of requests transitioned from node 1. That is, the transition probability P11 is a value (= 1/4) obtained by dividing the count result “1” of the transition counter C11 by the total value “4” (= C11 + C12 + C13 + C14 + C15 = 1 + 2 + 1 + 0 + 0) of the count results of the transition counters C11 to C15.

P12 indicates the probability that the request will transition from node 1 to node 2. The transition probability P12 is given by dividing the number of requests transitioned from node 1 to node 2 by the total number of requests transitioned from node 1. That is, the transition probability P12 is a value (= 1/2) obtained by dividing the count result “2” of the transition counter C12 by the total value (= C11 + C12 + C13 + C14 + C15 = 1 + 2 + 1 + 0 + 0) of the count results of the transition counters C11 to C15.
The other transition probabilities P13 to P15, P21 to P25, P31 to P35, P41 to P45, and P51 to P55 in FIG. 6 are also based on the same principle as the transition probabilities P11 or the transition probabilities P12, based on the count results in FIG. It is calculated.

を得る。 [Transition probability matrix]
Based on the above-mentioned transition probabilities P11 to P15, P21 to P25, P31 to P35, P41 to P45, and P51 to P55, the following transition probability matrix

To get.

この遷移確率行列

では、遷移元ノードが同じ遷移確率どうしを同じ列に配置し、遷移先ノードが同じ遷移確率どうしを同じ行に配置している。

This transition probability matrix

Then, the transition source nodes arrange the same transition probabilities in the same column, and the transition destination nodes arrange the same transition probabilities in the same row.

を用いて、所望の要求数に対する各ノードの処理負荷を予測する。例えば、処理負荷予測部２４は、ノードの処理負荷、すなわち各ノードに遷移する要求の総数を、遷移確率行列

を用いて期待値として予測する。以下の例では、前述の例で求めた遷移確率行列を用いて、この予測を行なう処理を具体的に説明する。 Processing load prediction processing (step S12)
The processing load prediction unit 24 is a transition probability matrix calculated by the transition aggregation analysis unit 23.

Is used to predict the processing load of each node for the desired number of requests. For example, the processing load prediction unit 24 sets the processing load of the node, that is, the total number of requests transitioning to each node, as a transition probability matrix.

Is used to predict the expected value. In the following example, the process of making this prediction will be specifically described using the transition probability matrix obtained in the above example.

を用いた予測の一例を示す。この例では、ノード１〜５にそれぞれ、

個の要求が投入されると要求数取得部25によって想定されたとする。各ノードが、それぞれの要求を単位処理負荷（前述の例と同様に、以下、単位処理時間）分だけ処理すると、要求の一部は他のノードに遷移する。ノードiからノードjへ遷移する要求の数は、遷移確率Ｐｉｊを用いると、期待値（Ｐｉｊ×ｗｉ）と予測される。よって、最初の単位処理時間後（１回目）に、各ノードに遷移した要求数は、遷移確率行列

と各ノードに投入された要求数

の行列積

となると期待される。
行列積

の値は、以下の式で算出される。 Figure 7 shows the transition probability matrix.

An example of prediction using is shown. In this example, nodes 1 to 5 respectively

It is assumed that the request number acquisition unit 25 assumes that individual requests are input. When each node processes each request by the unit processing load (hereinafter, unit processing time as in the above example), a part of the request transitions to another node. The number of requests transitioning from node i to node j is predicted to be an expected value (Pij × wi) using the transition probability Pij. Therefore, the number of requests that have transitioned to each node after the first unit processing time (first time) is a transition probability matrix.

And the number of requests submitted to each node

Matrix product of

Is expected to be.
Matrix product

The value of is calculated by the following formula.

となると期待される。また、３回目，．．．，１３回目についても、それぞれ行列積

となると期待される。このような処理を繰り返す結果、各ノードの要求の延べ数、すなわち、各ノードの処理負荷は、

となると期待される。 Similarly, after the next unit processing time (second time), the number of requests transitioned to each node is a matrix product.

Is expected to be. Also, the third time ,. .. .. ， For the 13th time, matrix multiplication

Is expected to be. As a result of repeating such processing, the total number of requests of each node, that is, the processing load of each node is

Is expected to be.

とすると、

で与えられる。図７の例において、ノード１〜５それぞれの処理時間の累計値

は、

で求めることができる。この結果、ノード１の処理時間の累計値Ｔは１．３、ノード２の処理時間の累計値Ｔは０．７、ノード３の処理時間の累計値Ｔは１．３、ノード４、５の処理時間の累計値Ｔはそれぞれ１．０である。(下式では、小数点2桁以下を四捨五入)

[Prediction of processing time (Solution 1)]
The cumulative value T of the processing time is the sum of the number of requests (unit processing time required to process the request).

Then

Given in. In the example of FIG. 7, the cumulative value of the processing time of each of the nodes 1 to 5

teeth,

Can be obtained at. As a result, the cumulative value T of the processing time of the node 1 is 1.3, the cumulative value T of the processing time of the node 2 is 0.7, the cumulative value T of the processing time of the node 3 is 1.3, and the cumulative value T of the nodes 4 and 5 is 1. The cumulative value T of the processing time is 1.0, respectively. (In the formula below, round off to two decimal places)

となる。このため、各ノードの処理負荷は、

で求めることができる。ここで、

は単位行列を示す。 [Prediction of processing time (Solution 2)]
Also, since there is a precondition that all processing of the request is completed within a finite time,

Will be. Therefore, the processing load of each node is

Can be obtained at. here,

Indicates the identity matrix.

である。両辺に

をかけると、

となる。式１の

から式２の

を引くと、

となる。ゆえに、

を得る。 Specifically,

Is. On both sides

When you apply

Will be. Equation 1

From formula 2

When you pull,

Will be. therefore,

To get.

の値は以下のように求められる。 In the example of FIG. 7,

The value of is calculated as follows.

よって、

Therefore,

を得る。これは、上記の解１の結果と同じである。

To get. This is the same as the result of Solution 1 above.

と予測され、ノード１、3の処理時間が許容値を越えている。つまり、これは、ノード１、3に遷移してくる要求が過多であることを示す。 Warning / Countermeasure calculation process (step S14)
Here, it is assumed that the allowable value of the processing time is T _limit = 1.0. As mentioned above, processing time

It is predicted that the processing time of nodes 1 and 3 exceeds the permissible value. That is, this indicates that there are too many requests to transition to the nodes 1 and 3.

The countermeasure calculation unit 26 compares the predicted value of the processing time with the permissible value. The predicted value of the processing time of the node 1 and the node 3 is both "1.3", which is larger than the allowable value "1.0". In this case, the countermeasure calculation unit 26 outputs a warning message (for example, a message such as "the predicted processing time exceeds the allowable processing time"), and the countermeasure calculation unit 26 is as follows. Can present various countermeasures.

[Improvement of processing load]
The countermeasure calculation unit 26 outputs a message prompting the improvement of the processing load, such as "Is it faster to 1.0 or parallelization?" For the node 1 and the node 3 whose predicted values exceed the permissible values.

[Relaxation of tolerance]
The countermeasure calculation unit 26 outputs a message prompting the relaxation of the allowable value, such as "Can the _{T limit be relaxed from 1.0 to 1.3?".}

の要求量を緩和できますか？」
といった要求の緩和を促すメッセージを出力する。 [Relaxation of demand]
The countermeasure calculation unit 26 is described as "

Can you relax your demands? "
A message prompting the relaxation of such a request is output.

[Adjustment of transition probability]
FIG. 8 shows a transition probability adjustment table. The transition destination node is shown in the column direction of the transition probability adjustment table, and the transition source mode is shown in the row direction. In the table, the nodes and numerical values shown in bold indicate the transition source node that is transitioning the request to the node whose processing time has been exceeded and the transition probability thereof.
The countermeasure calculation unit 26 outputs the transition probability adjustment table shown in FIG. 8, and prompts the node of the transition source that transitions the request to the node whose processing time has exceeded to lower the transition probability. Is output. For example, the countermeasure calculation unit 26 sends a message urging the probability of transition to the node 3, that is, the transition probability of "P13 = 1/4", "P23 = 1/1", and "P43 = 1/3". Output.

According to the node management device 21 of the present embodiment described above, the processing load of each node for an arbitrary number of requests is quantified based on the actual processing result for any distributed processing system that processes requests within a finite time. Can be predicted. In this prediction, not only the overloaded node and its load but also the cause of the overload and the low load node can be estimated, so that measures such as load balancing and congestion control can be set up faster and in more detail.

In the node management device 21, one control unit having the functions of the transition detection unit 22, the transition aggregation analysis unit 23, the processing load prediction unit 24, the request number acquisition unit 25, the countermeasure calculation unit 26, and the allowable load acquisition unit 27 is It may be provided. Further, the control unit may be realized by a computer equipped with a CPU or the like. In this case, by executing the program by the computer, each function of the transition detection unit 22, the transition aggregation analysis unit 23, the processing load prediction unit 24, the request number acquisition unit 25, the countermeasure calculation unit 26, and the allowable load acquisition unit 27 can be performed. It may be realized.

In the program, the computer executes the processes corresponding to the functions of the transition detection unit 22, the transition aggregation analysis unit 23, the processing load prediction unit 24, the request number acquisition unit 25, the countermeasure calculation unit 26, and the allowable load acquisition unit 27. It may be one. The program may be provided on the computer-enabled or computer-readable medium described above, or may be provided via a network such as the Internet.

Further, in the node management device 21, the following modifications can be applied.
The transition detection unit 22 aggregates the processing load generated when the node processes the request and the information of the request transition destination node. Here, each node may voluntarily report the processing load and the information of the transition destination node, but the transition detection unit 22 may inquire the node about the processing state and the transition result. Further, the transition detection unit 22 may monitor the communication of the node to detect the timing of starting the processing of the request and the passing of the request.

Further, if there is a queue in the node until the request is processed, the processing load may be obtained from the node itself, the start / end timing of processing, and the like. On the other hand, when there is no queue in the node, that is, when each request receives a constant load of processing in the node, a third party other than the node who can know the transition time etc. infers the processing load. You may.
For example, if the distributed processing system is a production line system, each node may have a queue. In this case, the load (time when the inspection was started / ended) when the request (work in process) was processed (inspected) by the node (inspection process) and the transition destination node (next process determined as a result of the inspection) are determined. , The node itself may ask for it. The transition aggregation analysis unit 23 aggregates information based on the report from the node.

Further, the node may be a base station for mobile communication. In this case, the transition aggregation analysis unit 23 monitors the communication of the control information of the handover transmitted by the node, and the time when the request (user) transitions (handover) between the nodes (base stations) and the transition destination node (handover). The target base station) may be detected. Further, assuming that each user applies a constant processing load to the node, the transition aggregation analysis unit 23 may estimate the processing load from the transition (handover) time.
The completeness of the aggregation of the processing load and the information of the transition destination node may be related to all transitions, or may be a sample randomly selected. Here, the sample may be all transitions of randomly sampled requests, or randomly sampled transitions of randomly sampled requests.

The processing load prediction unit 24 may use the actual number of requests input to the distributed processing system 10 as the number of requests that are the premise of prediction. Here, the number of requests may be not only the number of requests in the past but also the number of requests currently input. Even in the latter case, the processing load can be predicted immediately before the actual processing. Alternatively, the processing load prediction unit 24 may predict the number of requests that will occur in the future based on some simulation. Alternatively, the number of requests input to the distributed processing system 10 may be the sum of the actual number of requests and the number of partial simulation requests.

が、連続的に発生する場合、その発生周期を処理時間の許容値とする）。
処理負荷が許容値を超えた場合の通知先は、例えば、分散処理システムの管理者または状態監視装置、ノードの負荷分散の担当者または負荷分散装置、要求の受付システム、または輻輳制御装置である。ここで、負荷分散装置は、処理負荷の予測値が許容値を超えていないノードの処理能力の一部を、処理負荷が許容値を超えているノードの処理に割り当てても良い。 The allowable value of the processing load may be input interactively from the user interface, for example (for example, when the number of requests w occurs sporadically). Alternatively, the frequency of occurrence of the number of requests based on the above prediction may be used as the allowable value of the processing load (for example, the number of requests).

However, if it occurs continuously, the generation cycle is taken as the allowable value of the processing time).
When the processing load exceeds the allowable value, the notification destination is, for example, the administrator or status monitoring device of the distributed processing system, the person in charge of load balancing or the load balancing device of the node, the request receiving system, or the congestion control device. .. Here, the load balancer may allocate a part of the processing capacity of the node whose predicted processing load does not exceed the allowable value to the processing of the node whose processing load exceeds the allowable value.

When reporting a node whose predicted value exceeds the allowable value and a processing load, the processing load prediction unit 24 may also notify a node whose predicted value of the processing load is equal to or less than the allowable value and its processing load. .. By this notification, distributed processing (for example, processing that relocates processing resources from a node whose predicted value is less than the allowable value to a node whose predicted value is more than the allowable value) or congestion control (for example, in a node with a high load). It is possible to perform a process of transitioning a part of the request to a node with a low load.

The node management device of each embodiment described above is an example of the present invention, and changes that can be understood by those skilled in the art can be applied to the configuration and operation thereof without departing from the spirit of the invention.

The present invention can be applied to a system consisting of a plurality of nodes that process requests in cooperation with each other. For example, the present invention can be applied to load balancing of a distributed processing system, traffic control / congestion control of mobile communication, production management and progress management of a production line.

11 Node management device 12 Analysis department 13 Forecasting department 15 ₁ to 15 _n nodes

Claims (8)

For a plurality of nodes that process requests in cooperation with each other, an analysis unit that analyzes the processing load when each node processes the request and the transition between the nodes of the request,
A node management device including a prediction unit that predicts the processing load of each node for a desired number of requests based on the analysis result of the processing load and the transition. The analyzing unit, on the basis of the result of node aggregates the processing load at the time of processing the request, and a transition destination node information indicating a transition destination of requests processed by said node, and aggregated, the processing The node management device according to claim 1, which analyzes the tendency of the load and the transition destination. The analysis unit calculates the transition probability for each unit processing load of the request between the nodes.
The node management device according to claim 1 or 2, wherein the prediction unit predicts the processing load of each node based on the transition probability of the request. The analyzing unit, for said plurality of nodes, the number of requests that transitions between the nodes counted for each unit processing load to calculate the transition probability matrix based on the value obtained by counting,
The node management device according to claim 3, wherein the prediction unit predicts the processing load of each node based on the transition probability matrix. A claim that further has a countermeasure unit for each node, which compares the predicted value of the processing load predicted by the prediction unit with the permissible value and outputs a predetermined message when the predicted value exceeds the permissible value. The node management device according to any one of 1 to 4. The node management device according to claim 5, wherein the countermeasure unit outputs a message indicating measures for reducing the processing load of the node whose predicted value exceeds the permissible value. For a plurality of nodes that process requests in cooperation with each other, the processing load when each node processes the request and the transition between the nodes of the request are analyzed.
A node management method comprising predicting the processing load of each node for a desired number of requests based on the processing load and transition analysis results. For a plurality of nodes that process requests in cooperation with each other, a process of analyzing the processing load when each node processes the request and a transition between the nodes of the request, and a process of analyzing the transition between the nodes of the request.
A program for causing a computer to execute a process of predicting the processing load of each node for a desired number of requests based on the analysis result of the processing load and the transition.

Images