JP5238048B2 - Application connection number peak value estimation apparatus, method, and program - Google Patents

Description

  The present invention relates to an application connection number peak value estimation apparatus, method, and program, and in particular, by modeling the number of connections based on periodic observation of the number of application connections on an IP (Internet Protocol) network, the peak value of the number of application connections is determined. The present invention relates to an application connection number peak value estimating apparatus, method, and program.

  In general, in the capacity design and bandwidth design of an IP network, the capacity ratio and the upper limit of the required bandwidth are calculated based on the peak value of the target flow. For example, an efficient accommodation design method based on the number of simultaneous connections of packet flows has been proposed. However, the peak value of the number of simultaneously connected packet flows, which is one of the input values necessary for realizing these techniques, is not always directly obtained as the observed value. In the operation of commercial networks, there are cases where only the average value by periodic observation is observed instead of constant observation of instantaneous values. In this case, it is necessary to estimate the peak value from the observation values obtained by periodic observation. is there.

  In addition, regarding the estimation method of the average and variance of the link usage band, based on a plurality of average values obtained by periodic observation, a technology for estimating the variance of the link usage bandwidth in a finer time width is proposed (for example, (See Patent Document 1).

  The variance obtained with this technique depends on two parameters (number of samples) (m; n), but for a fixed n, the variance estimate obtained is O (m) and n = m In this case, if the time granularity is made fine, the required number of samples diverges infinitely, so it is considered unsuitable for peak value estimation with a fine time granularity. There have been many studies in the past regarding the calculation method of the distribution of peak values in the stochastic process (for example, Non-Patent Document 1).

Japanese Patent No. 3542030

IAN F. Blake and William C. Lindsey, "Level-Crossing Problems for Random Processes", IEEE Transactions on Information Theory, 19 (1973), 295-315.

  However, based on periodic observation of the number of application connections on the IP network, it is possible to calculate an approximate value of the α probability point (0 <α <1) of the peak value distribution from the average value for each observation period, There is a problem that the approximate value of the peak value cannot be estimated based on the plurality of average values obtained.

  The present invention has been made in view of the above points, and based on periodic observation of the number of application connections on an IP network, from the average value for each observation period to the probability point (0 <α <1) of the distribution of peak values. To provide an application connection number peak value estimation device, method and program capable of calculating an approximate value and estimating an approximate value of a peak value based on a plurality of average values obtained by periodic observation Objective.

In order to solve the above-described problems, the present invention provides an application connection number peak value estimation apparatus that estimates the peak value of the number of application connections within a certain observation period based on a plurality of observation values in periodic observation on an IP network. There,
An input means for inputting an average connection interval of application connections, an average service time, an observation period, and accuracy of an estimated value to be requested (hereinafter referred to as “estimation accuracy”) α (0 <α <1, α is a real number); ,
Based on the average arrival interval of the connection of the application input by the input means, the average service time, the observation period, and the required estimation accuracy, the number of application connections is modeled as a steady state queuing model. Modeling means for performing simulation and storing, as a simulation result, a peak value and an average value of the number of application connections in the system for each observation period in a modeling result storage means;
Obtaining the peak value and the average value from the modeling result storage means, and for the model modeled by the modeling means, the (peak value) / (average value) of the number of application connections in the observation period ) And a probability point calculating means for calculating a value of the random variable at the α probability point;
Obtain the number of application connections actually observed, and multiply the average value of the number of application connections by the probability variable value of the α probability point of (peak value) / (average value) to obtain the α probability point of the estimated peak value. An estimated peak value calculating means for calculating;
Have

  As described above, according to the present invention, based on the periodic observation of the number of application connections on the IP network, by modeling the number of application connections with the queue M / G / ∞, the peak value from the average value for each observation period is obtained. Allows estimation of values. In addition, based on periodic observations, it is possible to estimate peak values based on the M / G / ∞ model composed of M / G / ∞ parameters that model the number of application connections.

It is an image of the peak value and average value of the number of connections. It is a block diagram of the estimation apparatus in the 1st Embodiment of this invention. It is a flowchart of the estimation apparatus in the 1st Embodiment of this invention. It is each observation period peak value and average value in the 1st Embodiment of this invention. It is an empirical cumulative distribution of (peak value / average value) in the first embodiment of the present invention. It is a block diagram of the estimation apparatus in the 2nd Embodiment of this invention. It is a flowchart of the estimation apparatus in the 2nd Embodiment of this invention. It is an example of the observation value time series in the 2nd Embodiment of this invention. It is an example of the frequency distribution of the observed value in the 2nd Embodiment of this invention. It is an example of the peak value on all the observation time in the 2nd Embodiment of this invention. It is an example of empirical cumulative distribution of the peak value on all observation times in the second embodiment of the present invention.

  Embodiments of the present invention will be described below with reference to the drawings.

(1) <Definition>
First, definitions used in the present invention are shown.

・ H: Observation period;
Xt: the number of simultaneous connections at time t. Where M / G / ∞ is the steady state value;
1 / λ: average arrival interval;
1 / μ: average service time;
Α: Probability point value indicating estimation accuracy (0 <α <1, α is a real number)
FIG. 1 is an image of the peak value and average value of the number of connections. The number of connections itself is a natural number, but the average value is the average of the number of simultaneous connections within the observation period and takes a real value.

(2) <Modeling the number of application connections>
Next, modeling of the number of application connections will be described.

  In the present invention, on the assumption that connection arrivals of applications arrive independently of each other, modeling is performed according to a Poisson distribution with an average arrival interval of 1 / λ. Service time is an arbitrary random variable with an average of 1 / μ, and the number of target application connections is modeled as a steady-state queue (M / G / ∞).

  Hereinafter, the number of connections at time t is represented as Xt. For M / G / ∞ in the steady state, it takes the value n (∈N) at time t.

For the steady state probability P (X _t = n)
P (X _t = n) = ρ ⁿ exp (−ρ) / n (ρ = λ / μ)
It is known that This process is used in the modeling unit 10 in the first embodiment to be described later.

(3) <Modeling the ratio of peak value to average value>
Next, modeling of the ratio between the peak value and the average value will be described.

Based on the above-mentioned model of the number of application connections, the ratio A _h between the peak value and the average value of the number of application connections is modeled by the following known formula:

分母となる平均値は観測周期内におけるアプリケーション接続数の平均値（時間平均）である。Xt は定常過程であるため、A_h はt₀ には依存しない。

The average value as the denominator is the average value (time average) of the number of application connections within the observation period. Since Xt is a stationary process, A _h does not depend on t ₀ .

  This process is used in the modeling unit 10 of the second embodiment described later.

(4) <A _h :Apurikeshonsetsuzokusunopikuchitoheikinchinohiritsunobunpunosanshutsu_>
Next, calculation of the distribution of the ratio between the peak value and the average value of the number of application connections will be described.

The calculation method of the distribution of A _h proposed by the invention, based on simulation by the above M / G / ∞ model to calculate the cumulative distribution Pa ≡P of A _h (A _h ≦ a). Specifically, it follows the Poisson distribution based on the given parameter value, virtually generates the arrival of the application connection in the system, and adds the waiting time according to the given distribution to the departure time from the system, Generate a time series of numbers in the system.

Based on the cumulative distribution Pa of the A _h, it calculates the peak value of the application connections from the value of A _h in α probability point.

  The specific operation is as follows.

  Based on a given ρ = λ / μ, simulate the M / G / ∞ model for a sufficiently long time, calculate the number of M / G / ∞ models in the system, and (peak value) at each observation period Calculate the experience cumulative distribution Pa of / (average value).

Furthermore, A _h at the α probability point is calculated from the empirical cumulative distribution Pa of (peak value) / (average value) in the observation period.

When calculating A _{h at} the α probability point, it may be directly calculated from the experience cumulative distribution as described above, or calculated from the cumulative distribution obtained by applying some kind of smoothing to the experience distribution. It doesn't matter.

  This process is used in the probability point calculation unit 20 of the first embodiment described later.

(5) <Parameter identification>
Next, parameter identification will be described.

In steady state M / G / ∞, the distribution of the number of application connections X _t in the system does not depend on time and becomes a Poisson distribution with an average ρ.

は漸近的に正規分布Ｎ(ρ,σ)、ただし

Is asymptotically normal distribution N (ρ, σ), where

である。そこで、周期観測により複数観測値が得られた場合には、これに基づきパラメータρを同定し、上記の（１）の定義及び（４）のパラメータ同定に従い、ピーク値のα 確率点の推定を行う。

It is. Therefore, when multiple observation values are obtained by periodic observation, the parameter ρ is identified based on this, and the α probability point of the peak value is estimated according to the definition of (1) and the parameter identification of (4) above. Do.

  N observations by periodic observation

が得られたとして、

As obtained

を得られた値の標本平均とすると、ρ の推定値

Is the estimated mean of ρ

は

Is

により得られる。

Is obtained.

  A goodness-of-fit test is performed on the estimated value, and if the null hypothesis is not rejected, the process proceeds to the next procedure. If rejected, it is determined that more observation values need to be acquired. Specifically, a test (t-test) is performed on the null hypothesis that the observed value follows a normal distribution having parameters estimated by the Kolmogorov-Smirnov test or the like. If the hypothesis is rejected, it is determined that a larger number of samples are necessary for proper parameter estimation.

  This process is used in the parameter identification unit 40 of the second embodiment described later.

  next

をもつM/G/∞モデルを構成し、全観測時間にわたるシミュレーションをm 回実施してピーク値の経験分布η₁，η₂，…，η_m を得る。これにより、累積分布P(max Τ∈｛0，Nh｝ X_Τ≦x)（Nhは観測時間）を算出し、そのα 確率点を算出する。

Configure the M / G / ∞ model with, empirical distribution eta ₁ peak value simulation over the entire observation time was performed m times, eta _2, ..., get eta _m. Thus, the cumulative distribution P (max Τ∈ {0, Nh } X Τ ≦ x) (Nh observation time), and calculates the α probability point.

  This process is used in the peak value calculation unit 30 of the first and second embodiments described later.

  In the following, embodiments of the present invention will be described based on the above.

[First Embodiment]
In the present embodiment, a mode in which the transition of the number of application connections is modeled by a steady state of M / G / ∞ with a given average arrival interval 1 / λ and average service rate μ will be described.

  FIG. 2 shows the configuration of the estimation apparatus according to the first embodiment of the present invention.

  The estimation apparatus shown in FIG. 1 includes an input unit 1 such as a keyboard, a modeling unit 10, a probability point calculation unit 20, a peak value calculation unit 30, an output unit 2 such as a file (storage unit) or a display device, and a modeling unit 10. The modeled result storage unit 3 and the observation value storage unit 4 are stored.

  The operation in the above configuration is shown below.

  FIG. 3 is a flowchart of the transition device according to the first embodiment of the present invention.

  Step 101) The average arrival interval (1 / λ) and the average service rate (μ) are input from the input unit 1 to the modeling unit 10.

  Step 102) The modeling unit 10 constructs an M / G / ∞ model with an average number of connections ρ = λ / μ, and executes a simulation for a long simulation time that allows the system to be in a steady state and obtain a sufficiently large number of samples. Then, the transition of the number of systems and the peak value and average value of the number of systems in each simulation period are stored in a memory (not shown). In this simulation, (peak value) / (average value) in each observation period is calculated and stored in the modeling result storage unit 3. Specifically, the modeling in this step is executed by the process described in “(2) <Modeling of number of application connections>” described above.

  Step 103) The probability point calculation unit 20 obtains an output result of (peak value) / (average value) of each observation period in the simulation from the modeling result storage unit 3, and calculates the experience cumulative distribution. The probability point calculation unit 20 further calculates an observed value of (peak value) / (average value) at a probability point of α = 99% and outputs it to the peak value calculation unit 30. Specifically, the processing in this step is executed by the processing described in “(3) <Modeling of ratio between peak value and average value>” described above.

  The value of α is given as 99% in advance. Here, the value of α depends on how much margin is required.

  As an estimate of the peak value, when it is required that it is almost equal to or greater than the actual value (safe design), 99% is considered appropriate. On the other hand, when it is required to be close to the actual value, It is also possible to apply a value.

  Step 104) The peak value calculation unit 30 adds the 99% probability point (peak value / average value) of the empirical cumulative distribution calculated by the probability point calculation unit 20 to the observation value of the number of connected applications acquired from the observation value storage unit 4. ) To obtain an estimated value of the peak value in the observation period, and outputs it to the output means 2.

  Below, it demonstrates concretely using a numerical example.

  In the following example, an application connection follows an average arrival interval of 1 minute (1 / λ = 1), an average service time of 60 minutes (1 / μ = 60), and thus an average number of connections of 60 (ρ = 60). Assume that the average number of connections is observed at an observation period of 60 minutes (h = 60). Further, it is assumed that 61.5 is obtained from the observation value storage unit 4 as an observation value of the average number of connections in a certain observation section.

  When the average arrival interval and the average service rate are input to the modeling unit 10, the modeling unit 10 configures an M / G / ∞ model with an average number of connections ρ = λ / μ = 60 and executes the simulation in the modeling unit 10. To do. In this simulation, the modeling unit 10 stores (peak value) / (average value) in each observation period every 60 minutes in the modeling result storage unit 3.

  FIG. 4 shows a plot of the peak value and the average value in each observation section at this time.

  Next, the probability point calculation unit 20 calculates the cumulative experience distribution from the output result of (peak value) / (average value) in the simulation of the modeling result storage unit 3 described above. FIG. 5 shows an empirical cumulative distribution of (peak value) / (average value) obtained from the calculation result of the simulation time of 350 hours in the numerical example. As a result, the value 1.29 of (peak value / average value) at a 99% probability point given in advance is output to the peak value calculation unit 30.

  The peak value calculation unit 30 multiplies the observation value 61.5 obtained from the observation value storage unit 4 by the output value 1.29 of the probability point calculation unit 20 and outputs an estimated value 86.43 of the peak value to the output means 2 (note that The peak value of the actual number of connections in the observation section is 78, which falls within the above estimated range). This is the final output of the estimation device in the operation of the present embodiment.

[Second Embodiment]
In the first embodiment, the probability point calculation unit 20 is included. However, in this embodiment, the probability point calculation unit 20 is not provided, and a plurality of average connection numbers obtained by periodic observation are used. A mode for performing a process of identifying a ratio between the average arrival interval and the average service time in the queue model will be described.

  FIG. 6 shows the configuration of the estimation apparatus according to the second embodiment of the present invention.

  The estimation apparatus shown in the figure includes an input unit 1, a parameter identification unit 40, a modeling unit 10, a peak value calculation unit 30, an output unit 2, an estimated value storage unit 5, and a peak value storage unit 6.

  The operation in the above configuration will be described below.

  FIG. 7 is a flowchart of the estimation apparatus according to the second embodiment of the present invention.

  In the present embodiment, N observation values are obtained by periodic observation.

が得られている（観測時間がN × h である）ことを前提とする。

Is obtained (the observation time is N × h).

Step 201) A plurality of original time series observation data {ξ ₁ , ξ ₂ ,..., Ξ _N } are input to the parameter identification unit 40 from the input unit 1. Note that the observation data may be read from the observation storage unit 4 in the first embodiment.

  Step 202) The parameter identification unit 40 generates a frequency distribution of observation values from the input original observation data time series, and performs maximum likelihood estimation. The parameter identification unit 40 further calculates an estimated value of the average number of connections ρ in the steady state M / G / ∞ based on the multiple observation values by maximum likelihood estimation.

として算出する。また推定値の適合度検定（例えば、Kolmogorov-Smirnov検定）を実施し、観測値が推定したパラメータを持つ正規分布に従うとの帰無仮説が棄却されない場合には、求められた推定値を推定値記憶部５に格納し、ステップ２０３に進み、棄却された場合にはより多くの観測値を要するものと判断し、ステップ２０１に移行する。

Calculate as In addition, if a goodness-of-fit test of the estimated value (for example, Kolmogorov-Smirnov test) is performed and the null hypothesis that the observed value follows a normal distribution with the estimated parameter is not rejected, the estimated value obtained is estimated. The data is stored in the storage unit 5, and the process proceeds to step 203, and if rejected, it is determined that more observation values are required, and the process proceeds to step 201.

  Step 203) The modeling unit 10 estimates the average number of connections that is the output of the parameter identification unit 40 from the estimated value storage unit 5.

を取得し、当該推定値をもつM/G/∞モデルの定常状態を構成する。このモデルにより、シミュレーション時間N × hにわたるシミュレーションをm回実行し、それぞれのピーク値

And construct the steady state of the M / G / ∞ model with the estimated value. With this model, the simulation is performed m times over the simulation time N × h, and each peak value is

をピーク値記憶部６に蓄積する。

Are stored in the peak value storage unit 6.

Step 204) peak value calculation unit 30, from the peak value storage unit 6, and acquires the m-number of peak values, empirical cumulative distribution eta ₁ of the peak value, eta _2, ..., and calculates the eta _m. The cumulative distribution is calculated by P (max Τ∈ {0, Nh } X Τ ≦ x) (Nh observation time). Based on the value of the 99% probability point, it is calculated as an estimated value of the peak value in the entire observation time N × h and is output to the output unit 2.

  Below, it demonstrates concretely using a numerical example.

  In the following example, as a numerical example, the number of connections of the target application is the same as in the first embodiment described above: average arrival interval 1 minute (1 / λ = 1), average service time 60 minutes (1 / It is assumed that the average number of connections is 60 (ρ = 60), and observations are made at an observation period of 60 minutes (h = 60). Further, it is assumed that 350 observation values are obtained as shown in FIG. 8 (observation time 350 hours).

  The parameter identification unit 40 estimates the average number of connections from these 350 pieces of data.

として59.8 を算出する。

As a result, 59.8 is calculated.

  The frequency distribution of observed values generated by the parameter identification unit 40 is shown in FIG.

Further, it is confirmed that the ρ value by t-test is less than 10 ⁻¹⁰ and the null hypothesis is not rejected, and is stored in the estimated value storage unit 5, and the process proceeds to the next step.

  The modeling unit 10 constitutes a steady state M / G / ∞ model having an average number of connections of 59.8 based on the output of the parameter identification unit 40 of the estimated value storage unit 5. A simulation over 350 hours is performed 200 times (m = 200) using this model, and the peak value of each time is stored in the peak value storage unit 6. The result is shown in FIG.

  In the numerical example, the peak value calculation unit 30 acquires 200 peak values that are the output of the modeling unit 10 from the peak value storage unit 6, calculates the empirical cumulative distribution, and sets the probability point α to 99%. The peak value 89 is output as the value. The result is shown in FIG. 11 (note that the actual peak value over 350 hours is 87, which falls within the above estimated value range). This value is output to the output unit 2 as an estimated value of the peak value. This is the final output of the estimation device in the operation of the second embodiment.

  The operation of the constituent elements of the estimation device in the first and second embodiments described above is constructed as a program, installed in a computer used as an application connection number peak value estimation device, and executed. It is also possible to circulate through the network.

  The present invention is not limited to the above-described embodiments, and various modifications and applications can be made within the scope of the claims.

DESCRIPTION OF SYMBOLS 1 Input part 2 Output part 3 Modeling result storage part 4 Observation value storage part 5 Estimated value storage part 6 Peak value storage part 10 Modeling part 20 Probability point calculation part 30 Peak value calculation part 40 Parameter identification part

Claims (5)

On an IP (Internet Protocol) network, an application connection number peak value estimation device that estimates the peak value of the number of application connections within a certain observation period based on one observation value in periodic observation,
An input means for inputting an average connection interval of application connections, an average service time, an observation period, and accuracy of an estimated value to be requested (hereinafter referred to as “estimation accuracy”) α (0 <α <1, α is a real number); ,
Based on the average arrival interval of the connection of the application input by the input means, the average service time, the observation period, and the required estimation accuracy, the number of application connections is modeled as a steady state queuing model. Modeling means for performing simulation and storing, as a simulation result, a peak value and an average value of the number of application connections in the system for each observation period in a modeling result storage means;
Obtaining the peak value and the average value from the modeling result storage means, and for the model modeled by the modeling means, the (peak value) / (average value) of the number of application connections in the observation period ) And a probability point calculating means for calculating a value of the random variable at the α probability point;
Estimating the number of application connections actually observed, and multiplying the number of application connections by the probability variable value of the (probable value) / (average value) α probability point to calculate the α probability point of the estimated peak value A peak value calculating means;
An application connection number peak value estimation device characterized by comprising: On an IP (Internet Protocol) network, an application connection number peak value estimation device that estimates the peak value of the number of application connections within a certain observation period based on a plurality of observation values in periodic observation,
An input means for inputting a plurality of average connections obtained by periodic observation;
From the value of the plurality of average number of connections, the parameter identification means for identifying the ratio of the average arrival interval and the average service time in wait queue model,
Based on prior Symbol parameter identification means average arrival interval and the average service ratio of time identification result of, and modeled as a queuing model, a simulation, as a simulation result, the peak value of the total observation time in modeling result storage means Modeling means to store;
The peak value over the entire observation time stored in the modeling result storage means is obtained, the distribution function of the peak value over the entire observation time is calculated, and the α probability point (0 <α <1) is estimated. A peak value calculating means to perform;
An application connection number peak value estimation device characterized by comprising: On an IP (Internet Protocol) network, an application connection number peak value estimation method for estimating the peak value of the number of application connections within a certain observation period based on one observation value in periodic observation,
The modeling means inputs the average arrival interval, average service time, observation period, and required accuracy of the estimated value (hereinafter referred to as “estimation accuracy”) α (0 <α <1, α is Based on the real number), the number of application connections is modeled as a steady-state queuing model, a simulation is performed, and the peak value and average value of the number of application connections in the system for each observation period are stored as model results. Modeling steps stored in the means;
Probability point calculating means obtains the peak value and the average value from the modeling result storage means, and for the model modeled by the modeling means, (peak) of the number of application connections in the observation period A random variable representing (value) / (average value), and a probability point calculating step of calculating a value of the random variable in the estimated accuracy α probability point;
The estimated peak value calculation means obtains the actually observed number of application connections and multiplies the number of application connections by the probability variable value of the (accuracy value) probability point of the (peak value) / (average value). An estimated peak value calculating step for calculating an α probability point of the value;
An application connection number peak value estimation method characterized by: On an IP (Internet Protocol) network, an application connection number peak value estimation method for estimating a peak value of the number of application connections within a certain observation period based on a plurality of observation values in periodic observation,
Parameter identification means, from a plurality of values of the average number of connections with the input parameter identification step and modeling means for identifying the ratio of the average arrival interval in the wait queue model average service time is the average arrival by the parameter identification step Based on the identification result of the ratio of the interval and the average service time, modeling as a queuing model, performing a simulation, and as a simulation result, storing a peak value over the entire observation time in the modeling result storage means,
The peak value calculation means obtains the peak value over the entire observation time stored in the modeling result storage means, calculates the distribution function of the peak value over the entire observation time, and the α probability point (0 <α A peak value calculating step for estimating <1);
An application connection number peak value estimation method characterized by:   An application connection number peak value estimation program for causing a computer to function as each means constituting the application connection number peak value estimation apparatus according to claim 1.

Images