JP4347333B2 - Flow statistics estimation method, apparatus and program thereof - Google Patents

Description

  The present invention relates to a technique for estimating original flow statistics from sample flow data obtained by applying packet sampling.

  In network operation management, it is important to understand what kind of flow the traffic flowing on the network is composed of. For example, in the case of an IP packet, the flow is defined by a combination of five records described in the IP header of “source IP address, destination IP address, source port number, destination port number, protocol type”. There are various flows by arbitrarily combining data (for example, AS number corresponding to the IP address) not directly recorded in the packet header related to the records on the packet header and the records recorded in the packet header. Can be defined. By examining the size of each flow and obtaining the distribution of the flow size, it is possible to quantitatively obtain information useful for control and management such as what kind of flow is flowing through the network. Further, by obtaining the flow size distribution, it is possible to detect an abnormality that has occurred in the network based on the change in the distribution.

  With the recent increase in the speed of network lines, a technique for constructing flow statistics from a part of packet data obtained by sampling has been put into practical use, instead of constructing flow statistics from all packet data flowing on the line. Yes. Here, the packet sampling is a technique for performing sampling according to a deterministic rule such as referring to one packet every N packets probabilistically or every N packets. By applying packet sampling when measuring a flow, resources such as processing speed and memory amount required for measurement and data accumulation can be greatly reduced.

  As described above, by applying packet sampling technology to flow measurement, scalability can be improved in terms of processing speed and retained data amount, but some packet data is not observed by sampling, so sampled flow statistics are Different from the original flow statistics. For this reason, it is necessary to statistically estimate the flow data before the sample from the sampled flow data.

  Non-Patent Literature 1 proposes a method of estimating an original flow distribution from sample flow statistics by a nonparametric method that does not assume a distribution model. However, since this method requires a large amount of calculation for estimation, there is a problem that it cannot be applied to the use of estimating the original flow statistics from the sample flow statistics in real time.

Nick Duffield, Carsten Lund, Mikkel Thorup, “Estimating Flow Distributions from Sampled Flow Statistics”, Proceedings the ACM SIGCOMM, pp.325-336, 2003

  The present invention has been made in view of the above problems, and when estimating the original flow size distribution from the sampled flow size data, it is possible to estimate the flow size distribution with high accuracy while greatly reducing the amount of calculation. Realizing this is the subject of the present invention.

  Of the inventions disclosed in this specification, the outline of typical ones will be briefly described as follows.

In order to achieve the above object, the present invention provides a flow statistics estimation method in a flow statistics estimation apparatus that statistically estimates a flow size distribution before a sample based on sample flow data, wherein the flow statistics estimation apparatus includes: A data acquisition step of acquiring flow data measured by applying a packet sampling to a measurement device on the network; a sampling rate value set in the flow measurement device; and sample flow data acquired in the data acquisition step. An estimation step for statistically estimating a flow size distribution before a sample using a distribution model having one or more parameters selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution and, that we have a. The flow size (flow size) is the number of packets for each flow.

Hereinafter, the distribution model will be described. Let X _j be the number of packets before a sample of a certain flow j. That is, X _j is the flow size before sample of flow j. At this time, the distribution model according to the discrete variable X _j is expressed by a probability function having Θ = {θ ₁ , θ ₂ ,... Θ _m } as parameters. That is,

とする。ここでΘは確率分布のパラメタの集合を表しており、ｍはパラメタの数であり、θ_１，θ_２，…θ_ｍはパラメタの集合Θを構成するパラメタである。（１）式は、あるフローｊのフローサイズＸ_ｊがある値ｘになる確率ｐが、Θをパラメタとする確率関数ｆ（ｘ；Θ）に等しいことを表した式である。

And Here Θ represents a set of parameters of the probability distribution, m is the number of _parameters, θ _1, θ _2, the ... theta _m is a parameter constituting the set Θ parameters. The expression (1) is an expression representing that the probability p that the flow size X _j of a certain flow _j becomes a certain value x is equal to the probability function f (x; Θ) having Θ as a parameter.

  Here, any model can be selected as the distribution model. However, since it is generally known that the flow distribution follows a long-tailed distribution, a distribution model having such characteristics is selected as a candidate for selection. . Further, the present invention estimates the original flow by a parametric method and uses a distribution model having one or more parameters, but from the viewpoint of reducing the amount of calculation, the number of parameters is better, It is desirable to select a simple distribution model having about 1 to 3 parameters as a selection candidate. For example, a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, a lognormal distribution, or the like can be selected as a distribution model that satisfies the above two characteristics, but the scope of application of the present invention is not limited to this.

The invention of claim 1, prior Symbol flow statistics estimation apparatus, wherein in the estimation step, 1 for observation data is sampled sample flow data over packet, flow size distribution before the sample by applying the EM algorithm It is a flow statistics estimation method characterized by estimating the parameter of.

Hereinafter, the parameter estimation method (referred to as “first estimation method”) will be described. When packets are sampled randomly at a sampling rate f (0 ≦ f ≦ 1), the number of packets sampled for the flow under the condition that the number of original packets of the flow is X _j = x is Y _j = y The probability that is

である。ここでＹ_ｊはフローｊのサンプル後のフローサイズである。Ｐｒ（Ｙ_ｊ＝ｙ｜Ｘ_ｊ＝ｘ）は、あるフローｊのフローサイズＸ_ｊがｘであった条件の元で、そのフローｊのサンプルフローサイズＹ_ｊがｙとなる確率（条件付確率）である。ｑ（ｙ｜ｘ）は、Ｐｒ（Ｙ_ｊ＝ｙ｜Ｘ_ｊ＝ｘ）を簡単に記述するために導入した関数である。

It is. Here, Y _j is the flow size after sample of flow j. Pr (Y _j = y | X _j = x) is a probability (conditional probability) that the sample flow size Y _{j of the} flow _j is y under the condition that the flow size X j of the flow _j is x. ). q (y | x) is a function introduced to simply describe Pr (Y _j = y | X _j = x).

At this time, the probability that the number of packets sampled for a certain flow j is Y _j = y is calculated using the equations (1) and (2).

となる。ここでｒ（ｙ；Θ）は、Ｐｒ（Ｙ_ｊ＝ｙ）を簡単に記述するために導入した関数である。Ｎは母集団に含まれるパケットの総数である。

It becomes. Here, r (y; Θ) is a function introduced to simply describe Pr (Y _j = y). N is the total number of packets included in the population.

When the number n _{i of} i-packet sampled flows is assumed, the complete log likelihood log L _C (Θ) including unobserved data n ₀ is expressed by using r (y) in the equation (3).

となる。ここでｉはサンプルされたパケット数であり、ｎ_ｉ（ｉ＝０，１，２，...）はｉ個のパケットがサンプルされたフローの数である。Ｌ_Ｃ（Θ）は完全尤度である（Ｌ＝likelihood、Ｃ＝complete）。対数をとったものが完全対数尤度である。

It becomes. Here, i is the number of sampled packets, and n _i (i = 0, 1, 2,...) Is the number of flows in which i packets are sampled. L _C (Θ) is a complete likelihood (L = likelihood, C = complete). The logarithm is the complete log likelihood.

Hereinafter, means for obtaining the parameter Θ by the EM algorithm will be described. Let Θ = Θ ⁽⁰⁾ be the initial estimate of the parameter. When this parameter is given, the conditional expected value under the observation data n _i (i ≧ 1) of the complete log likelihood defined by equation (4)

を計算する（Ｅ−ｓｔｅｐ）。つぎにＱ（Θ；Θ^（０））を最大化するようなΘを数値計算によって求め、その値をΘ＝Θ^（１）とする（Ｍ−ｓｔｅｐ）。以下同様にΘ^（ｉ）（ｉ＝１，２，...）を繰り返し計算する。Θ^{（ｉ−１）}とΘ^（ｉ）の差が十分に小さくなったら、Θ^（ｉ）をパラメタの推定値とする。

Is calculated (E-step). Next, Θ that maximizes Q (Θ; Θ ⁽⁰⁾ ) is obtained by numerical calculation, and the value is set as Θ = Θ ⁽¹⁾ (M-step). Thereafter, Θ ⁽ⁱ⁾ (i = 1, 2,...) Is repeatedly calculated in the same manner. When the difference between Θ ⁽ⁱ⁻¹⁾ and Θ ⁽ⁱ⁾ becomes sufficiently small, Θ ⁽ⁱ⁾ is set as an estimated value of the parameter.

In the equation (5), Q (Θ; Θ ⁽⁰⁾ ) is a function introduced to simply describe the equation on the right side. Hereinafter, E _{Θ (0)} {log L _C (Θ) | n ₁ , n ₂ ,..., N _m } on the right side of the equation (5) will be described. First, generally speaking, E {X} is an expected value of X, and E {X | Y} is an expected value of X when Y is given. _{Accordingly, E {log L C (Θ} ) | n 1, n 2, ..., n m} _{is, n 1, n 2, ...} , log in _{n m} (observed data) is given based on This is an expected value of the likelihood log L _C (Θ). By the way, E _{Θ (0)} {X (Θ)} is an expected value of X (Θ) when Θ is Θ = Θ ⁽⁰⁾ . After all, equation (5) of the right side of _{E Θ (0) {log L} C (Θ) | n 1, n 2, ..., n m} is, theta and theta = theta ⁽⁰⁾ and the time, n ₁ , n ₂ ,..., N _m (observed data) are expected values of the log likelihood log L _C (Θ) under given conditions.

Here, since (5) conditional expected value of the expression is a linear function with respect to non-observation data _{n 0,} conditional expected value _n ⁰ of ^{_{n 0 (0) = E Θ}} (0) (n 0 | n 1, n ₂ ,..., n _m ) can be obtained by substituting n ₀ in equation (4). n ₀ ⁽⁰⁾ is estimated by the odds ratio in the following equation.

請求項２の発明は、前記フロー統計推定装置が、前記推定ステップにおいて、未観測データであるサンプルされなかったフローの数である非サンプルフロー数の情報を前記計測装置より取得し、最尤法を適用することによってサンプル前のフローサイズ分布のパラメタを推定することを特徴とするフロー統計推定方法である。

According to a second aspect of the invention, before Symbol flow statistics estimating apparatus, in the estimation step, and acquires the non-sample number of flows of information that the number of samples that were not flow not yet observed data from the measuring device, the maximum likelihood This is a flow statistical estimation method characterized by estimating a parameter of a flow size distribution before a sample by applying a method.

Hereinafter, the parameter estimation method (referred to as “second estimation method”) will be described. In the second method, when the data n ₀ that has not been observed in the first method or its estimated value can be obtained by some other method, the estimation accuracy can be improved by estimating using the data. The aim is to plan. Specifically, the obtained n ₀ is substituted into the complete log likelihood of the equation (4), and Θ that maximizes the equation (4) is obtained by numerical calculation.

  According to the present invention, when estimating the original flow size distribution from sampled flow size data, it is possible to significantly reduce the amount of calculation.

  Embodiments of the present invention will be described below with reference to the drawings. The flow is defined by five keys (hereinafter referred to as flow key) of the source IP address, destination IP address, source port number, destination port number, and protocol type, but the scope of application of the present invention is not limited to this.

  FIG. 1 is a diagram showing an example of an application form of the present invention. 10 is a flow statistics estimation apparatus, 11 and 12 are flow measurement apparatuses that measure flows such as routers and switches, and 13 and 14 are sample flow data transmitted from the flow measurement apparatuses 11 and 12 to the flow statistics estimation apparatus 10, respectively. . The flow measurement apparatuses 11 and 12 sample flow packets that pass through the flow measurement apparatuses 11 and 12 to create flow data (sample flow data). The flow statistics estimation device 10 is a device that statistically estimates the distribution of the flow size before the sample based on the sample flow data. The flow size is the number of packets for each flow.

  The flow statistic estimation device 10 designates the flow data (sample flow data) measured by applying the packet sampling to the flow measurement devices 11 and 12 having a flow measurement function such as one or a plurality of routers / switches as an arbitrary value. Get at possible intervals. Here, it is assumed that the sample flow data includes at least the flow key and the cumulative number of packets in the measurement interval corresponding to each key. The flow statistic estimation apparatus 10 performs flow statistic estimation every time sampling flow data is acquired at the interval. The flow statistic estimation apparatus 10 has the above-described acquired sample flow data 13 and 14, the sampling rate value 15 set in the flow measurement apparatuses 11 and 12, and a feature that lengthens the base, and has one or more parameters. A distribution model, for example, a distribution model 16 selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution is input, and an estimation parameter 17 that is an estimated value of the parameter for the distribution model is returned as an output.

  In the second method to be described later, information 18 on the number of flows (number of non-sample flows) that has not been sampled by the flow measuring apparatuses 11 and 12 is used as an additional input item. As described above, in the second estimation method, the number of non-sample flows is estimated using the results measured by the flow measurement apparatuses 11 and 12, etc., but in the first estimation method described later, the number of non-sample flows is estimated.

  The flow statistic estimation apparatus 10 acquires sample flow data from a plurality of flow measurement apparatuses provided on the network and performs flow statistic estimation for the entire network. However, the flow statistic estimation is performed for each flow measurement apparatus. Also good.

  In FIG. 2, the example of the flowchart which shows the operation | movement of the flow statistics estimation apparatus 10 is shown. 21 is a data acquisition step, and 22 is an estimation step. In the data acquisition step 21, the flow statistic estimation apparatus 10 acquires flow data measured by the measurement apparatuses 11 and 12 on the network by applying packet sampling at intervals that can be arbitrarily specified. Next, in the estimation step 22, the flow statistic estimation apparatus 10 is based on the sampling rate value 15 set in the flow measurement apparatuses 11 and 12 and the sample flow data 13 and 14 acquired in the data acquisition step 21. The distribution of the flow size before the sample is statistically estimated using the distribution model 16 that has a characteristic that draws long and has one or more parameters.

  The distribution model only needs to have one or more parameters, but from the viewpoint of reducing the amount of calculation, the number of parameters is preferably small, and is preferably about 1 to 3. As the distribution model, for example, a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, a lognormal distribution, or the like can be used. In the example described later, a discrete Pareto distribution is used.

  In addition, the flow statistics estimation device 10 uses a distribution model having a characteristic that has a long base as described above and having one or more parameters in the data acquisition step 21. The first estimation method or the second estimation method shown is used.

  In the first estimation method, the flow statistics estimation apparatus 10 also samples one packet that cannot be observed by applying the EM algorithm to the observation data that is sample flow data sampled one or more packets at the estimation step 22. Estimate the flow size distribution parameters before the sample, including information about the flow that will not be performed.

  In the second estimation method, the flow statistic estimation apparatus 10 obtains information 18 of the number of unsampled flows that is the number of unsampled flows that are unobserved data from the measurement apparatuses 11 and 12 in the estimation step 22; Estimate the parameters of the flow size distribution before the sample by applying the maximum likelihood method.

  The explanation using the expressions for the distribution model, the first estimation method, and the second estimation method is as described in “Means for solving problems”.

  Hereinafter, an example of the flow size distribution before the sample and the flow data after the sample will be shown. The solid line (Original) in FIG. 3 shows the distribution of the flow size (before the sample) as a complementary distribution of the cumulative distribution using traffic data measured over a certain network for 5 minutes. The horizontal axis of FIG. 3 represents the flow size (Flow length), that is, the number of packets included per flow. The vertical axis represents a complementary cumulative distribution (CCD). Both the horizontal axis and the vertical axis are logarithmic displays.

Table 1 shown in FIG. 4 shows sample flow data (i, _ni ) when packet sampling with a sampling rate of f = 0.001 is applied to the traffic data. Where i is the number of packets sampled and n _i (i = 0, 1, 2,...) Is the number of flows sampled i packets (number of flows sampled i packets). It is. For the packet sampling, a commonly used random sampling was applied. In Table 1, the number of flows in which one packet is sampled is 1317, the number of flows in which two packets are sampled is 121, and the number of flows in which three packets are sampled. Is 36,... 408 packets are sampled and the number of flows is one. Since Table 1 is a table showing observation data, sample flow data is not described for i = 0, that is, the number of flows in which no packet is sampled. When the first estimation method is used, the flow statistic estimation apparatus 10 only needs to acquire the sample flow data shown in Table 1, but when the second estimation method is used, the number of flows in which one packet is not sampled separately. It is necessary to acquire information on the number of non-sample flows (information about the number of flows when i = 0).

  Hereinafter, an example in which a discrete Pareto distribution is selected in selecting a distribution model will be described, but the application form of the present invention is not limited to this example. The probability function of equation (1) is expressed by a discrete Pareto distribution

とモデル化する。パラメタは形状母数θ＞０である。ただしｘ＝１，２，...である。なお、（１）式はｍ個のパラメタを有するパラメタの集合Θ＝｛θ_１，θ_２，...θ_ｍ｝で一般的に表した式であるが、（６）式は１個のパラメタΘ＝｛θ_１｝の場合であり、これを簡単にθと記載している。

And model. The parameter is a shape parameter θ> 0. However, x = 1, 2,. The expression (1) is an expression generally expressed by a set of parameters having m parameters Θ = {θ ₁ , θ ₂ ,... Θ _m }, but the expression (6) This is the case of the parameter Θ = {θ ₁ }, which is simply described as θ.

  The broken line (fitting) in FIG. 3 shows the result of modeling the flow size distribution indicated by the solid line by the discrete Pareto distribution. At this time, the maximum likelihood estimated value of the parameter θ was θ = 1.243. It can be seen that the model distribution fits the actual distribution relatively well. Estimating the value of this parameter is the goal of the first and second estimation methods.

In the first estimation method, f (x; θ) in equation (6) is substituted into equation (5). Further, θ = θ ^{(i + 1)} which maximizes the conditional expectation value Q (θ; θ ⁽ⁱ⁾ ) of log likelihood is the partial derivative of Q (θ; θ ⁽ⁱ⁾ ) with respect to θ, q (θ) = ∂ Q (θ, θ ⁽ⁱ⁾ ) / ∂θ is set, and q (θ) = 0 is solved by the Newton method.

As a result, the estimated parameter value θ = 1.018 was obtained. The EM algorithm was repeated until the absolute value of the difference between θ ⁽ⁱ⁻¹⁾ and θ ⁽ⁱ⁾ was smaller than 0.0001.

In the second estimation method, as in the first estimation method, f (x; θ) in Equation (6) is substituted to obtain θ that maximizes the complete log likelihood log L _C (θ). It is obtained by solving θ by the Newton method such that the partial differential with respect to θ of the complete log likelihood becomes zero. Further, here, n ₀ was substituted by a true value, assuming that the measuring device observed. As a result, an estimated value of the parameter can be obtained as θ = 1.073.

  Using the parameter θ calculated by the above two methods, the result of drawing the estimated flow size distribution together with the original flow distribution shown in FIG. 1 is shown by the broken line in FIG. 3 (first method → method 1, second Method → Method 2) It can be seen that both methods estimate the distribution with relatively high accuracy. It can also be seen that the second method is closer to the original parameter value θ = 1.243.

  The flow statistic estimation apparatus 10 of this embodiment has means for realizing its operation, steps, and functions, and the means can be configured by a computer and a program. Moreover, you may comprise using hardware instead of a part or all of the program.

  As mentioned above, the invention made by the present inventor has been specifically described based on the above embodiments. However, the present invention is not limited to the above embodiments, and various modifications can be made without departing from the scope of the invention. Of course.

It is a figure which shows the example of the application form of this invention. The example of the flowchart which shows operation | movement of the flow statistics estimation apparatus of this invention is shown. It is a figure which shows the example of the flow distribution used as the object of the estimation in this invention, the approximation by the distribution model of the said flow distribution, and the flow distribution estimated by this invention. It is a table | surface (Table 1) which shows the example of the sample flow data in this invention.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 ... Flow statistics estimation apparatus, 11, 12 ... Flow measurement apparatus, 13, 14 ... Sample flow data, 15 ... Sampling rate, 16 ... Distribution model, 17 ... Estimation parameter, 18 ... Number of non-sample flows.

Claims (5)

A flow statistic estimation method in a flow statistic estimation device that statistically estimates a distribution of flow sizes before a sample based on sample flow data,
The flow statistic estimation device comprises:
A data acquisition step for acquiring flow data measured by a measurement device on the network by applying packet sampling;
One or more selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution based on the sampling rate value set in the flow measurement device and the sample flow data acquired in the data acquisition step An estimation step for statistically estimating a flow size distribution before the sample using a distribution model having parameters;
I have a,
The flow statistic estimation apparatus estimates a parameter of a flow size distribution before a sample by applying an EM algorithm to observation data which is sample flow data sampled one packet or more in the estimation step. The flow statistics estimation method. A flow statistic estimation method in a flow statistic estimation device that statistically estimates a distribution of a flow size before a sample based on sample flow data,
The flow statistic estimation device comprises:
A data acquisition step for acquiring flow data measured by a measurement device on the network by applying packet sampling;
One or more selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution based on the sampling rate value set in the flow measurement device and the sample flow data acquired in the data acquisition step An estimation step for statistically estimating a flow size distribution before the sample using a distribution model having parameters;
Have
In the estimation step, the flow statistic estimation device obtains information on the number of unsampled flows, which is the number of unsampled flows, which is unobserved data, from the measurement device, and applies the maximum likelihood method before sampling. A flow statistic estimation method characterized by estimating a flow size distribution parameter. A flow statistic estimation device that statistically estimates a flow size distribution before a sample based on sample flow data,
A data acquisition means for acquiring flow data measured by measuring equipment on the network by applying packet sampling;
One or more selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution based on the sampling rate value set in the flow measurement device and the sample flow data acquired by the data acquisition means An estimation means for statistically estimating the flow size distribution before the sample using a distribution model having parameters;
I have a,
A flow statistic estimation apparatus , wherein the estimation means estimates a parameter of a flow size distribution before a sample by applying an EM algorithm to observation data which is sample flow data sampled by one packet or more . A flow statistic estimation device that statistically estimates a flow size distribution before a sample based on sample flow data,
A data acquisition means for acquiring flow data measured by measuring equipment on the network by applying packet sampling;
One or more selected from a discrete Pareto distribution, a Yule-Simon distribution, a Weibull distribution, and a lognormal distribution based on the sampling rate value set in the flow measurement device and the sample flow data acquired by the data acquisition means An estimation means for statistically estimating the distribution of the flow size before the sample using a distribution model having parameters;
Have
The estimation means obtains information on the number of unsampled flows, which is the number of unsampled flows, which is unobserved data, from the measurement device, and applies a maximum likelihood method to obtain parameters of the flow size distribution before the sample. A flow statistic estimation device characterized by estimating. The program for making a computer perform the step of Claim 1 or 2 .

Images