JP5587166B2 - Line capacity estimation apparatus, program and method for estimating future line capacity in consideration of dispersion of short-term fluctuations in traffic volume - Google Patents

Description

  The present invention relates to a technique for designing an optimum line capacity based on a traffic volume.

  Conventionally, when designing the line capacity of a communication network, there is a technique for probabilistically evaluating the quality of the communication service based on statistical traffic fluctuations. For example, in the case of the public telephone network, it is a well-known fact that the arrival process of calls generated from a large number of independent subscribers follows a Poisson process having random characteristics. The Poisson process is a stochastic process that represents a situation in which call arrival occurs randomly, and the number of call arrivals in non-overlapping time intervals is independent of each other. In the Poisson process, future traffic prediction can be determined by a single parameter of the average number of calls per time interval, so it is very easy to design a communication model from measured traffic data.

  On the other hand, in the case of an IP (Internet Protocol) network, the use of real-time applications such as VoIP (Voice over IP) and moving image distribution with a large data amount and a short allowable delay time is increasing. In this case, there is a characteristic that a large amount of traffic is generated in a burst manner. Therefore, in order to design the line capacity with high accuracy, information on the traffic amount with high time resolution is required. Instantaneous traffic fluctuation affects the determination of line capacity based on the packet loss rate.

  The traffic volume generally monitored is, for example, an average traffic volume of about 5 minutes. For this reason, it is impossible to grasp the instantaneous burstiness of packets actually flowing. When the line capacity is designed based on such low time resolution traffic volume information, it is determined as if the narrow band line capacity is sufficient without considering the instantaneous burstiness of the packet. End up. In this case, the packet to be transferred has a longer residence time in the reception buffer in the relay apparatus on the line, and the delay increases. A packet overflowing from the reception buffer is discarded. As described above, when the channel capacity is designed based on the information of the traffic amount with low time resolution, it causes a reduction in service quality for a real-time application having bursty traffic characteristics.

  There is the fact that the number of packets arriving per time interval in an IP network has self-similarity or long-term dependence and has a positive correlation over time. Self-similarity means that the time fluctuation of traffic does not depend on the time interval. For example, even if the traffic having burstiness is coarse in time granularity, the burstiness is not lost. For this reason, the queue length of the reception buffer is likely to diverge compared to traffic simplified based on the Poisson distribution. Therefore, it is considered that the Poisson model cannot be used for the quality evaluation of the communication service of the IP network.

  Further, the IP network has a problem that the packet loss rate cannot be improved even if the capacity of the reception buffer that accommodates traffic is increased to a certain extent. This was a problem in the circuit capacity design. In addition, in the backbone line of the IP network, a certain number of randomness is inherent in the arrival process of the IP packet because many independent users access, and the characteristics are very close to the Poisson process. .

  The temporal correlation in the IP network is caused by various factors (for example, transfer file capacity, TCP window size, etc.) based on different time intervals. The strength of the correlation varies depending on the size of the time interval. For example, when the time interval is reduced to the order of 1 μs or less, the obtained time series of the number of packets shows little correlation, and looks like random traffic. On the other hand, if the time interval is on the order of more than that, a strong correlation over a long period is shown. In other words, it can be said that IP traffic includes a mixture of time intervals that exhibit relatively random characteristics and time intervals that exhibit strong correlation such as long-term dependence.

  On the other hand, by utilizing the self-similarity of the bursty traffic characteristic, an arbitrary fine time interval (for example, 10 millisecond interval) can be obtained from the traffic amount of a rough time interval (for example, 5 minute interval (300 seconds)). There is a technique for estimating fluctuations in traffic volume at the time (see, for example, Patent Document 1). In the case of an IP network, when traffic fluctuations are observed at the packet level, such as at intervals of 10 milliseconds, the dispersion is greater than in the case of minutes. Therefore, an appropriate line bandwidth is to be estimated in consideration of traffic fluctuations in a short time interval (for example, in milliseconds).

  There is also a technique for modeling traffic information with low temporal resolution (in seconds) by applying MWM (Multi-fractal Wavelet Model) and generating pseudo traffic information with high temporal resolution (in milliseconds) (for example, patents). Reference 2).

JP-A-2005-151111 JP 2009-253882 A

HF Zhang, “Estimation of Hurst Parameter by Variance-Time Plots”, IEEE PACRIM, 1997, [online], [December 12, 2010 search], Internet <URL: http://ieeexplore.ieee.org/xpl/ freeabs_all.jsp? arnumber = 620401>

  According to the above-described conventional technology, the line capacity can be designed by analyzing the current traffic volume. However, it is impossible to design the line capacity in consideration of the self-similarity that may occur in the future target period. The line capacity of the network resource should be designed to ensure an allowable packet error rate over a long period, for example, 5 years or more. On the other hand, securing a line capacity with an unnecessarily wide bandwidth in the future leads to waste of network resources.

  Therefore, in consideration of the dispersion of short-term fluctuations in traffic volume, the present invention can accommodate less than the allowable packet loss rate based on the latest short-term traffic volume and any self-similarity that may occur in the future. It is an object of the present invention to provide a line capacity estimation apparatus, program, and method for estimating a possible line capacity.

According to the present invention, a line capacity estimation apparatus for estimating a line capacity,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history accumulating means for storing arrival times and sizes of a large number of measured packets;
Short-term packet extraction means for extracting a plurality of predetermined time unit packet groups (i = 1 to n) that occurred in the most recent short period from the traffic history storage means;
For each packet group i, and the average traffic amount calculating means for calculating the average amount of traffic m _i,
For each packet group i, the packet loss rate is calculated from the arrival times and sizes of a plurality of packets based on the reception buffer size B, and the minimum on the buffer output side so that the packet loss rate is equal to or less than the allowable packet loss rate p. Minimum line capacity calculating means for calculating the line capacity C _i ;
For each packet group i, to calculate the stress-free load factor _{ρ i (= m i / C} i) which represents the ratio of the average traffic volume m _i for each minimum channel capacity C _i, the combination of each packet group i (C _i, stress free load factor calculating means for outputting ρ _i ),
A reference value extracting means for determining a stress-free load factor ρ ₀ that is the minimum value among a plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ _{0, the} minimum line capacity C _0, and the Hurst parameter Htarget, the stress-free load ratio ρ for the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. Plot and
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A capacity-to-load factor relationship calculating means for calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
It has a line capacity determining means for determining the line capacity so that the average traffic amount m is equal to or less than the ratio of the stress-free load factor ρ to the line capacity C.

According to another embodiment of the line capacity estimation apparatus of the present invention,
The target average traffic volume Vtarget is defined in advance,
Long-term packet extraction means for extracting a plurality of predetermined time unit packet groups that have occurred in the past long-term from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted against the passage of time, and is extended toward the future long-term passage of time to correspond to the target average traffic amount Vtarget. A target time specifying means for predicting a future target time Ttarget;
Based on the packet group extracted by the long-term packet extraction means, calculate a variance value according to different time resolution, plot each variance value for different time resolution, and based on the slope β obtained by extending a plurality of plots, A Hurst parameter calculation means for calculating a Hurst parameter H (= 1−β / 2);
Plotting the Hurst parameter H for each predetermined time unit with respect to time, and having a target Hurst parameter specifying means for calculating the future target Hurst parameter H with respect to the target time Ttarget by extending the longest time in the future. Is also preferable.

  According to another embodiment of the channel capacity estimation apparatus of the present invention, the target time specifying means, the Hurst parameter calculating means, and the target Hurst parameter specifying means include a least square method, a regression analysis, an autoregressive sum to extend linearly. It is also preferable to use a fractional moving average model or an autoregressive moving average model.

  According to another embodiment of the line capacity estimation apparatus of the present invention, the minimum line capacity calculating means inputs the arrival time and size of a plurality of packets in a simulation to the queue based on the reception buffer size B. It is also preferable to calculate the packet loss rate by ingest simulation.

According to the present invention, there is provided a channel capacity estimation program for causing a computer to function,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history accumulating means for storing arrival times and sizes of a large number of measured packets;
Short-term packet extraction means for extracting a plurality of predetermined time unit packet groups (i = 1 to n) that occurred in the most recent short period from the traffic history storage means;
For each packet group i, and the average traffic amount calculating means for calculating the average amount of traffic m _i,
For each packet group i, the packet loss rate is calculated from the arrival times and sizes of a plurality of packets based on the reception buffer size B, and the minimum on the buffer output side so that the packet loss rate is equal to or less than the allowable packet loss rate p. Minimum line capacity calculating means for calculating the line capacity C _i ;
Every packet group i, to calculate the stress-free load factor _{ρ i (= m i / C} i) which represents the ratio of the average traffic volume m _i for each minimum channel capacity C _i, the combination of each packet group i (C _i, stress free load factor calculating means for outputting ρ _i ),
A reference value extracting means for determining a stress-free load factor ρ ₀ that is the minimum value among a plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ _{0, the} minimum line capacity C _0, and the Hurst parameter Htarget, the stress-free load ratio ρ for the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. Plot and
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A capacity-to-load factor relationship calculating means for calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
The computer is caused to function as line capacity determining means for determining the line capacity so that the average traffic amount m is equal to or less than the ratio of the stress-free load factor ρ to the line capacity C.

According to another embodiment of the channel capacity estimation program of the present invention,
The target average traffic volume Vtarget is defined in advance,
Long-term packet extraction means for extracting a plurality of predetermined time unit packet groups that have occurred in the past long-term from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted against the passage of time, and is extended toward the future long-term passage of time to correspond to the target average traffic amount Vtarget. A target time specifying means for predicting a future target time Ttarget;
Based on the packet group extracted by the long-term packet extraction means, calculate a variance value according to different time resolution, plot each variance value for different time resolution, and based on the slope β obtained by extending a plurality of plots, A Hurst parameter calculation means for calculating a Hurst parameter H (= 1−β / 2);
A computer is further provided as a target Hurst parameter specifying means for plotting the Hurst parameter H for each predetermined time unit with respect to the passage of time and extending it toward the future long-term passage to calculate the future target Hurst parameter H with respect to the target time Ttarget. It is also preferable to make it function.

According to the present invention, there is provided a line capacity estimation method for estimating a capacity of a line configured in a network using an apparatus,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history storage unit that stores the arrival times and sizes of a large number of measured packets;
A first step of extracting a plurality of predetermined time unit packet groups (i = 1 to n) generated in the short term from the traffic history storage unit;
Every packet group i, and a second step of calculating the average amount of traffic m _i,
For each packet group i, the packet loss rate is calculated from the arrival times and sizes of a plurality of packets based on the reception buffer size B, and the minimum on the buffer output side so that the packet loss rate is equal to or less than the allowable packet loss rate p. A third step of calculating the line capacity C _i ;
For each packet group i, to calculate the stress-free load factor _{ρ i (= m i / C} i) which represents the ratio of the average traffic volume m _i for each minimum channel capacity C _i, the combination of each packet group i (C _i, a fourth step of outputting ρ _i );
A fifth step of determining a stress-free load factor ρ ₀ that is a minimum value among the plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ _{0, the} minimum line capacity C _0, and the Hurst parameter Htarget, the stress-free load ratio ρ for the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. Plot and
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A sixth step of calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
And a seventh step of determining the line capacity so that the average traffic amount m is equal to or less than the ratio of the stress-free load factor ρ to the line capacity C.

According to another embodiment of the channel capacity estimation method of the present invention,
The following steps are executed before the first step.
The target average traffic volume Vtarget is defined in advance,
Extracting a plurality of predetermined time unit packet groups that have occurred in the past long-term from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted against the passage of time, and is extended toward the future long-term passage of time to correspond to the target average traffic amount Vtarget. Predicting a future target time Ttarget;
Based on the packet group extracted by the long-term packet extraction means, calculate a variance value according to different time resolution, plot each variance value for different time resolution, and based on the slope β obtained by extending a plurality of plots, Plotting the Hurst parameter H for each predetermined time unit against the step of calculating the Hurst parameter H (= 1−β / 2) and the passage of time, and extending it for the long-term future in the future. It is also preferable to further include a step of calculating the target Hurst parameter H.

  According to the line capacity estimation apparatus, program, and method of the present invention, the line capacity that can be accommodated at an allowable packet loss rate or less based on the most recent short-term traffic volume and any self-similarity that may occur in the future. Is estimated.

It is a model figure showing line capacity. It is a graph showing the stress free load factor with respect to time passage. It is a function block diagram of the channel capacity estimation apparatus in this invention. It is a graph showing the stress free load factor ρ ₀ that is the minimum value. It is a graph showing the relational expression of the capacity | capacitance versus load factor in this invention. It is a functional block diagram of the line capacity estimation apparatus which can estimate future line capacity. It is a graph showing the amount of average traffic with respect to the passage of time in the future. It is a graph showing the dispersion | distribution with respect to different time resolution. It is a graph showing the Hurst parameter H with respect to the time passage over the future.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

  FIG. 1 is a model diagram showing the line capacity.

According to FIG. 1, the relay apparatus 2 arranged on the IP network relays and forwards IP packets. The relay apparatus 2 receives an IP packet from one line and outputs it to the other line via a reception buffer. The reception buffer is generally a FIFO (First-In First-Out) queue, and a buffer size B (for example, about 10 Mbit per 10 milliseconds) is defined in advance. Further, as a communication carrier, an allowable packet loss rate p (for example, about 10 ⁻⁵ ) in the reception buffer is also defined in advance.

  When the line capacity on the output side is small (when the bandwidth on the output side is narrow), the residence time in the reception buffer becomes long and the delay increases. In addition, the overflow packet when the reception buffer is full is discarded. The communication carrier needs to design the line capacity on the output side so that the packet loss rate is equal to or less than the allowable packet loss rate p even when the packet is discarded.

  The line capacity estimation device 1 receives a set of measurement traffic information measured by the relay device 2. Here, the measurement traffic information includes at least the arrival time and the size (packet length). It is also preferable to include a source IP address, a source port number, a destination IP address, a destination port number, and a protocol.

  FIG. 2 is a graph showing the amount of traffic over time.

  FIG. 2A is a graph obtained by measuring the average traffic volume every 5 minutes over 60 minutes. According to MRTG (Multi Router Traffic Grapher), it seems that the fluctuation of the traffic amount is stable.

  FIG. 2B is a graph in which the amount of traffic every 10 milliseconds is measured over 60 minutes. According to FIG. 2B, it can be understood that the traffic volume fluctuates rapidly and instantaneously. Therefore, in the case of a line to which IP packets are transferred, it is necessary to analyze the traffic volume with high time resolution (for example, 10 milliseconds).

FIG. 2C is a graph showing the average traffic amount over 5 minutes. According to FIG. 2C, the stress-free load factor ρ is represented by the average traffic amount m in units of 5 minutes and the line capacity C. “Stress-free load factor ρ” refers to the ratio of the average traffic amount m to the minimum line capacity C that satisfies the allowable packet loss rate.
ρ = m / C
Here, according to FIG. 2 (c), it represents the traffic fluctuation when the allowable packet loss rate is 0 and there is no buffer. However, since there is actually a buffer, some fluctuations can be absorbed. When the buffer is provided to absorb the fluctuation, the line capacity C is slightly lower than the maximum fluctuation amount of the traffic amount in units of 10 milliseconds shown in FIG.

  The stress-free load factor is used to calculate the capacity that can be accommodated at an allowable packet loss rate p or less in consideration of traffic fluctuations in a short time interval, that is, in consideration of the strength of traffic self-similarity. Used for. That is, it represents a load factor at which the line does not become a substantial bottleneck in traffic. For example, when the stress-free load factor is 0.7 for a line capacity of 1 Gbps, if the average traffic amount m for 5 minutes is 700 Mbps (= 1G × 0.7) or less, the line is a substantial bottleneck in traffic. Means not.

  FIG. 3 is a functional configuration diagram of the channel capacity estimation apparatus according to the present invention.

  As shown in FIG. 3, the line capacity estimation apparatus 1 includes a traffic history accumulation unit 100, a measurement traffic information reception unit 101, and a line capacity estimation function unit 11. The line capacity estimation function unit 11 is realized by executing a line capacity estimation program that causes a computer installed in the apparatus to function. It should be noted that the processing flow of the functional components described in FIG. 3 can also be understood as a channel capacity estimation method.

  The traffic history accumulating unit 100 stores the arrival times and sizes of a large number of measured packets. The measurement traffic information receiving unit 101 receives measurement traffic information (arrival time and size) from a relay device on the network, and outputs the measurement traffic information to the traffic storage unit 100.

  The channel capacity estimation apparatus 1 is preliminarily defined with a target Hurst parameter Htarget that represents the degree of self-similarity at a future target time. The target Hurst parameter Htarget may be set by the user, or may be determined by FIG.

  The line capacity estimation function unit 11 includes a short-term packet extraction unit 111, an average traffic calculation unit 112, a minimum line capacity calculation unit 113, a stress-free load factor calculation unit 114, a reference value extraction unit 115, and a capacity-to-load factor. A relationship calculation unit 116 and a line capacity determination unit 117 are included.

  The short-term packet extraction unit 111 extracts, from the traffic history accumulation unit 100, a plurality of packet groups (i = 1 to n) that have occurred in the most recent short period. The predetermined unit time may be, for example, 5 minutes (300 seconds). Further, it is assumed that the packet group is, for example, measurement packets for one hour every day in the most recent week. In this case, a packet group of 60 minutes ÷ 5 minutes × 7 days = 84 points (i = 1 to 84) is extracted.

The average traffic calculation unit 112, for each packet group of a predetermined time unit i, and calculates an average amount of traffic m _i. The average traffic amount _mi is calculated by “the sum of the data amount of all packets / time”. The average traffic amount _mi is output to the minimum line capacity calculation unit 113 and the stress-free load factor calculation unit 114.

The minimum line capacity calculation unit 113 calculates the packet loss rate from the arrival times and sizes of a plurality of packets based on the reception buffer size B for each packet group i. Then, the minimum line capacity C _i on the buffer output side is calculated so that the packet loss rate is equal to or less than the allowable packet loss rate p.

The packet loss rate is calculated by queuing simulation for a queue based on the reception buffer size B, using the arrival time of the packet and its packet size as input parameters for each packet group i. As shown in the model diagram of FIG. 1, the queuing simulation assumes a reception buffer, and inputs packets included in the packet group i to the buffer according to the arrival time and size of the history, Calculate the packet loss rate. Here, while adjusting the line capacity C _i on the buffer output side, the minimum line capacity C _i that is equal to or less than the allowable packet loss rate p is calculated.

Stress-free load factor calculation section 114, for each packet group i, to calculate the stress-free load factor represents the percentage of average traffic amount m _i for each minimum channel capacity _{C i ρ i (= m i} / C i). Then, the combination (C _i , ρ _i ) for each packet group i is output to the reference value extraction unit 115.

The reference value extraction unit 115 determines the stress-free load factor ρ ₀ that is the minimum value among the plurality of stress-free load factors ρ _i , and outputs one reference value combination (C ₀ , ρ ₀ ). The reference value is output to the capacity-to-load factor relationship calculation unit 116.

FIG. 4 is a graph showing the stress-free load factor ρ ₀ that is the minimum value.

According to FIG. 4, the combinations (C _i , ρ _i ) for each packet group i are plotted. Among them, the combination (C ₀ , ρ ₀ ) of the stress-free load factor ρ ₀ that is the minimum value is determined.

The capacity-to-load factor relationship calculation unit 116 calculates an allowable ratio of the average traffic amount with respect to an arbitrary channel capacity based on the stress-free load factor ρ _{0, the} minimum channel capacity C _0, and the target Hurst parameter Htarget. . Here, the capacity-to-load factor relationship calculating unit 116 changes the variable K by a predetermined unit value step (for example, K = 0.0 to 00.00 to 0.01 step) according to the following formula, and the stress-free load factor with respect to the line capacity C. Plot ρ.
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
The curve calculated by the plot is derived as a relational expression ρ = f (C) of the stress-free load factor ρ with respect to the line capacity C.

  FIG. 5 is a graph showing a relational expression of capacity versus load factor in the present invention.

According to FIG. 5, the curve ρ = f (C) is drawn so as to pass through the combination of the minimum reference values (C ₀ , ρ ₀ ) in FIG. This curve is drawn by changing the variable K in increments of a predetermined unit value.

The line capacity determining unit 117 determines the line capacity so that the average traffic amount m is equal to or less than the ratio of the stress-free load factor ρ to the line capacity. That is, in consideration of the stress-free load factor ρ, the average traffic amount m is designed to satisfy the following expression.
m <ρ · C

  The relational expression in FIG. 5 is created based on the future target Hurst parameter Htarget, and the communication carrier can recognize the stress-free load factor ρ according to the line capacity C, and the average corresponding to the ρ. The amount of traffic m can be recognized. That is, even if the communication carrier increases the line capacity in the future, it is possible to predict the stress-free line capacity.

  FIG. 6 is a functional configuration diagram of a channel capacity estimation apparatus that can estimate the future channel capacity.

  The line capacity estimation apparatus in FIG. 6 further includes a traffic configuration prediction unit 12 in addition to the line capacity estimation function unit 11 as compared with FIG. According to the present invention based on FIG. 6, the traffic configuration prediction unit 12 that predicts the Hurst parameter based on the future demand by paying attention to the self-similarity from the traffic measurement result, and the traffic fluctuation for a short period of time from the prediction result. A line capacity estimation function unit 11 that calculates an optimum line communication capacity in consideration of dispersion.

  The traffic configuration prediction unit 12 includes a long-term packet extraction unit 121, a target time specifying unit 122, a Hurst parameter calculation unit 123, and a target Hurst parameter specifying unit 124.

  The traffic configuration prediction unit 12 predefines the target average traffic amount Vtarget.

The long-term packet extraction unit 121 extracts, from the traffic history accumulation unit 100, a plurality of predetermined time unit packet groups that have occurred in the past long period. The predetermined unit time may be, for example, 5 minutes (300 seconds). Here, the predetermined unit time of the packet group in the long-term packet extraction unit 121 needs to be the same as the predetermined unit time in the short-term packet extraction unit 111. The packet group is, for example, a measurement packet of one hour every day for one year in the past long term. The one hour is preferably, for example, a time zone in which the average traffic volume is the highest in one day (for example, 20: 00-21: 00 every day).
Xt (t = 0,1,2 ...): Time series data of packet size (t: equivalent to time stamp)
Xk (n) = 1 / n. (Xk (n-n + 1) + Xk (n-n + 2) +... + Xk (n)) (k = 1, 2... N)
: Time series data that averages Xt together for every n

  Based on the packet group extracted by the long-term packet extraction unit 121, the target time specifying unit 122 plots the average traffic amount for each predetermined time unit with respect to the passage of time.

  FIG. 7 is a graph showing the average traffic volume with respect to the passage of time in the future.

  According to FIG. 7, the future target time Ttarget corresponding to the target average traffic volume Vtarget (predicted value of demand traffic volume) is further extended toward the future long-term time using a general prediction method. Predict.

  As a general prediction method, a least square method, a regression analysis, an autoregressive integrated moving average model, or an autoregressive moving average model may be used in order to extend linearly. “Least-squares” is an approximation that the assumed function is a good approximation to the measurement plot when approximating a specific function (linear function, logarithmic curve, etc.) assumed from an appropriate model from a plurality of plots. This is a method (linear fitting) for determining a coefficient that minimizes the sum of squares of the residuals. “Regression analysis” is a method of quantitatively analyzing how much a dependent variable (objective variable) can be explained by an independent variable (explanatory variable) of a continuous scale. An example of the autoregressive integrated moving average model is ARIMA (Auto Regressive Integrated Moving Average). As an autoregressive moving average model, for example, there is ARMA (Auto Regressive Moving Average).

  The Hurst parameter calculation unit 123 calculates a variance value corresponding to different time resolutions (time scale, time interval) based on the packet group extracted by the long-term packet extraction unit 121, and plots each variance value for different time resolutions (Variance-Time Plots).

The “dispersion value” is an average value of values obtained by squaring the error of how far each data is centered on the average value, and means a dispersion characteristic. By considering the dispersion value, that is, the burst characteristic, the optimum line capacity on the buffer output side can be derived.
Var X (n): Variance of time series Xk (n)

  FIG. 8 is a graph showing the variance for different temporal resolutions.

  The Hurst parameter H (= 1−β / 2) is calculated based on the inclination β of the extension direction of the plot (see, for example, Non-Patent Document 1). The Hearst parameter H (H = 1−slope) indicating the self-similarity by looking at the decrease of the dispersion value with respect to the horizontal axis changed from the high time resolution (short time interval) to the low time resolution (long time interval). / 2) is obtained. For the variance value, the slope β is calculated by the above-described general prediction method (for example, linear fitting by the least square method).

  The nature of traffic with low temporal resolution (packet level time scale) is represented by the Hurst parameter H, which represents self-similarity. For example, even if the average amount of traffic for a long time (for example, 5 minutes) is the same, if the self-similarity is weak (close to H = 0.5), the time resolution (time scale) is increased (for example, From 10 milliseconds to 1 second), the variance value of the traffic fluctuation becomes small. On the other hand, when the self-similarity is strong (close to H = 1), even if the time resolution (time scale) is increased, the dispersion value does not decrease. That is, in traffic with strong self-similarity (close to H = 1), it can be recognized that there are very large short-term fluctuations for long-term traffic fluctuations.

  The target Hurst parameter specifying unit 124 plots the Hurst parameter H for each predetermined time unit with respect to the passage of time.

  FIG. 9 is a graph showing the Hurst parameter H over time in the future.

  According to FIG. 9, the future target Hurst parameter Htarget with respect to the target time Ttarget is calculated by linearly extending toward a long time in the future. Also here, the plot of the Hurst parameter H is extended in the linear direction by the above-described general prediction method (for example, linear fitting by the least square method).

  Then, the target Hurst parameter specifying unit 124 outputs the calculated target Hurst parameter Htarget to the channel capacity estimation function unit 11. Thus, the channel capacity estimation function unit 11 can estimate the channel capacity based on the future target Hurst parameter Htarget calculated by the traffic configuration prediction unit 12.

  As described above in detail, according to the channel capacity estimation apparatus, program, and method of the present invention, the allowable packet loss rate based on the most recent short-term traffic volume and any self-similarity that may occur in the future. The line capacity that can be accommodated is estimated below. As a result, it is possible for the communication carrier to predict a stress-free line capacity when the line capacity is increased in the future.

  According to the present invention, the demand is predicted in consideration of the multiplicity of flows, the variance of the traffic amount in the order of several milliseconds is estimated from the measured traffic amount in the order of several minutes, and the allowable packet loss rate is satisfied. The estimation accuracy of the line capacity can be improved. A flow refers to a sequence of packets having the same five items of the source IP address, source port number, destination IP address, destination port number, and protocol. This is because the traffic observed on the backbone line of the IP network can be viewed as a superposition of packet flows generated by a very large number of users.

  Various changes, modifications, and omissions of the above-described various embodiments of the present invention can be easily made by those skilled in the art. The above description is merely an example, and is not intended to be restrictive. The invention is limited only as defined in the following claims and the equivalents thereto.

DESCRIPTION OF SYMBOLS 1 Line capacity estimation apparatus 100 Traffic history storage part 101 Measurement traffic information receiving part 11 Line capacity estimation function part 111 Latest short-term data extraction part 112 Average traffic calculation part 113 Minimum line capacity calculation part 114 Stress free load factor calculation part 115 Reference value extraction Unit 116 Capacity-to-load ratio relationship calculation unit 117 Line capacity determination unit 12 Traffic configuration prediction unit 121 Long-term packet extraction unit 122 Target time specification unit 123 Hurst parameter calculation unit 124 Target Hurst parameter specification unit 2 Relay device

Claims (8)

A line capacity estimation device for estimating a line capacity,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history accumulating means for storing arrival times and sizes of a large number of measured packets;
Short-term packet extraction means for extracting a plurality of predetermined time unit packet groups (i = 1 to n) that have occurred in the short term from the traffic history storage means;
For each of the packets i, an average traffic amount calculating means for calculating the average amount of traffic m _i,
For each packet group i, a packet loss rate is calculated from arrival times and sizes of a plurality of packets based on the reception buffer size B, and the buffer output is set so that the packet loss rate is equal to or less than the allowable packet loss rate p. Minimum line capacity calculating means for calculating the minimum line capacity C _i on the side,
For each of the packets i, to calculate the stress-free load factor represents the percentage of average traffic amount m _i for each minimum channel capacity _{C i ρ i (= m i} / C i), the combination of each of the packet group i (C _i , ρ _i ) for outputting stress-free load factor;
A reference value extracting means for determining a stress-free load factor ρ ₀ that is a minimum value among the plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ ₀ and the minimum line capacity C ₀ and the Hurst parameter Htarget, the stress-free load ratio with respect to the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. plot ρ,
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A capacity-to-load factor relationship calculating means for calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
A line capacity estimation device comprising: a line capacity determining means for determining a line capacity so that an average traffic amount m is equal to or less than a ratio of the stress-free load factor ρ to the line capacity C. The target average traffic volume Vtarget is defined in advance,
Long-term packet extraction means for extracting a plurality of predetermined time unit packet groups that have occurred in the past long-term from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted with respect to the time passage, and is expanded toward the long-term time passage in the future, and the target average traffic amount Vtarget is obtained. A target time specifying means for predicting a corresponding future target time Ttarget;
Based on the group of packets extracted by the long-term packet extraction means, calculate dispersion values corresponding to different time resolutions, plot each dispersion value for different time resolutions, and based on the slope β obtained by extending a plurality of plots Hurst parameter calculation means for calculating the Hurst parameter H (= 1-β / 2),
A target Hurst parameter specifying means for plotting the Hurst parameter H for each predetermined time unit with respect to time and extending the time to a long time in the future to calculate the target Hurst parameter H in the future with respect to the target time Ttarget; The line capacity estimation apparatus according to claim 1, comprising: The target time specifying means, the Hurst parameter calculating means, and the target Hurst parameter specifying means use a least square method, regression analysis, an autoregressive integrated moving average model or an autoregressive moving average model for linear extension. The line capacity estimation apparatus according to claim 2 . The minimum line capacity calculating means calculates a packet loss rate by queuing simulation, in which arrival times and sizes of a plurality of packets are inputted in a simulation to a queue based on the reception buffer size B. The line capacity estimation apparatus according to any one of claims 1 to 3 . A line capacity estimation program for causing a computer to function,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history accumulating means for storing arrival times and sizes of a large number of measured packets;
Short-term packet extraction means for extracting a plurality of predetermined time unit packet groups (i = 1 to n) that have occurred in the short term from the traffic history storage means;
For each of the packets i, an average traffic amount calculating means for calculating the average amount of traffic m _i,
For each packet group i, a packet loss rate is calculated from arrival times and sizes of a plurality of packets based on the reception buffer size B, and the buffer output is set so that the packet loss rate is equal to or less than the allowable packet loss rate p. Minimum line capacity calculating means for calculating the minimum line capacity C _i on the side,
For each of the packets i, to calculate the stress-free load factor represents the percentage of average traffic amount m _i for each minimum channel capacity _{C i ρ i (= m i} / C i), the combination of each of the packet group i (C _i , ρ _i ) for outputting stress-free load factor;
A reference value extracting means for determining a stress-free load factor ρ ₀ that is a minimum value among the plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ ₀ and the minimum line capacity C ₀ and the Hurst parameter Htarget, the stress-free load ratio with respect to the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. plot ρ,
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A capacity-to-load factor relationship calculating means for calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
A line capacity estimation program for causing a computer to function as line capacity determining means for determining a line capacity so that an average traffic volume m is equal to or less than a ratio of the stress-free load factor ρ to the line capacity C. The target average traffic volume Vtarget is defined in advance,
Long-term packet extraction means for extracting a plurality of predetermined time unit packet groups that have occurred in the past long-term from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted with respect to the time passage, and is expanded toward the long-term time passage in the future, and the target average traffic amount Vtarget is obtained. A target time specifying means for predicting a corresponding future target time Ttarget;
Based on the group of packets extracted by the long-term packet extraction means, calculate dispersion values corresponding to different time resolutions, plot each dispersion value for different time resolutions, and based on the slope β obtained by extending a plurality of plots Hurst parameter calculation means for calculating the Hurst parameter H (= 1-β / 2),
As a target Hurst parameter specifying means for plotting the Hurst parameter H for each predetermined time unit with respect to time, and extending the time to a long time in the future to calculate the target Hurst parameter H in the future with respect to the target time Ttarget The line capacity estimation program according to claim 5 , further causing a computer to function. A line capacity estimation method for estimating the capacity of a line configured in a network using a device,
An allowable packet loss rate p, a reception buffer size B, and a target Hurst parameter Htarget representing self-similarity at a future target time are defined in advance.
A traffic history storage unit that stores the arrival times and sizes of a large number of measured packets;
A first step of extracting a plurality of predetermined time unit packet groups (i = 1 to n) generated in the short term from the traffic history storage unit;
For each of the packet group i, and a second step of calculating the average amount of traffic m _i,
For each packet group i, a packet loss rate is calculated from arrival times and sizes of a plurality of packets based on the reception buffer size B, and the buffer output is set so that the packet loss rate is equal to or less than the allowable packet loss rate p. A third step of calculating the minimum line capacity C _i on the side;
For each of the packets i, to calculate the stress-free load factor represents the percentage of average traffic amount m _i for each minimum channel capacity _{C i ρ i (= m i} / C i), the combination of each of the packet group i (C _i , ρ _i ) in a fourth step,
A fifth step of determining a stress-free load factor ρ ₀ that is a minimum value among the plurality of stress-free load factors ρ _i and outputting one reference value combination (C ₀ , ρ ₀ );
Based on the stress-free load factor ρ ₀ and the minimum line capacity C ₀ and the Hurst parameter Htarget, the stress-free load ratio with respect to the line capacity C is changed every time the variable K is changed by a predetermined unit value according to the following equation. plot ρ,
ρ = 1 / {1 + S · K ^{(−1 / 2 · Htarget)} }
S = 1 / ρ ₀ −1
C = ρ ₀ · C ₀ · K / ρ
A sixth step of calculating a relational expression of the stress-free load factor ρ calculated by the plot as a ratio of an average traffic amount allowable for an arbitrary line capacity C ;
And a seventh step of determining the line capacity so that the average traffic amount m is equal to or less than the ratio of the stress-free load factor ρ to the line capacity C. The following steps are executed before the first step,
The target average traffic volume Vtarget is defined in advance,
Extracting a plurality of predetermined time unit packet groups that have occurred in the past from the traffic history storage means;
Based on the packet group extracted by the long-term packet extracting means, the average traffic amount for each predetermined time unit is plotted with respect to the time passage, and is expanded toward the long-term time passage in the future, and the target average traffic amount Vtarget is obtained. Predicting a corresponding future target time Ttarget;
Based on the group of packets extracted by the long-term packet extraction means, calculate dispersion values corresponding to different time resolutions, plot each dispersion value for different time resolutions, and based on the slope β obtained by extending a plurality of plots , Calculating the Hurst parameter H (= 1−β / 2) and plotting the Hurst parameter H for each predetermined time unit with respect to the elapsed time, and extending the target time Ttarget The method of claim 7 , further comprising: calculating the future target Hurst parameter H for

Images