JP2015019159A - Queue delay calculation device, queue delay calculation method and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To calculate a probability distribution of queue delay by inputting an arrival process and the average and dispersion of service time distribution.SOLUTION: The queue delay calculation device for calculating queue delay comprises: number in-system estimation means for calculating number in-system distribution by inputting a moment observation value up to the second-order of an arrival time to a queue to calculate a positive solution of diffusion approximation; and queue delay distribution calculation means for inputting the calculated number in-system distribution and a moment observation value up to the Nth-order (N≥2) of a queue service time to calculate queue delay distribution.

Description

  The present invention relates to a queue simulation technique, and relates to a queue delay calculation device, a queue delay calculation method, and a program that perform a queue delay simulation using a queue model.

  A general queuing model is represented by an arrival process representing arrival at a queue, a service time required for the service, and the number of services.

  If neither the arrival process nor the service time is Markovian, it is called a non-Markov model. There are a plurality of approximation methods for non-Markov models. Among these approximation methods, the diffusion approximation method is known as having universality and easily obtaining a system performance measure as a result. Diffusion approximation is a formulation that describes the number of customers in a system or the provisional waiting time process using a diffusion equation in order to obtain a system performance evaluation scale in a non-Markov queuing system. Thereby, the approximate value of the queue delay can be easily calculated.

E. Gelenbe, "Probabilistic models of computer systems, Part II, Diffusion approximations, waiting times and batch arrivals," Acta Informatica, vol. 12, pp.285-303, 1979. Takataka Takahashi: "Diffusion approximation (non-Markov model approximation)", IEICE Knowledge Base, 2010.http: //www.ieice-hbkb.org/files/05/05gun_01hen_03.pdf

  In a queuing model in which one or both of the arrival process and service time follow a predetermined well-known distribution, such as the M / D / 1 model, the theoretical value of the in-system distribution can be calculated recursively but explicitly. It is. However, in the GI / GI / 1 model that follows the general probability distribution for both the arrival process and the service time distribution, it is difficult to calculate the number distribution in the system. The diffusion approximation is a well-known technique, and an approximate solution can be configured numerically by applying the diffusion approximation. However, in the case of the GI / GI / 1 model, since the explicit solution of the diffusion approximation is not known, the validity of the diffusion approximation model, the error in the numerical calculation, the convergence to the stationary solution, and the model are imposed. The conditions to be determined are unknown.

  Further, even if the distribution of the numbers in the system is obtained, the queue delay cannot be directly calculated based on the distribution.

  In view of the above problems, an object of the present invention is to calculate an approximate value of a queue delay distribution in the queue model GI / GI / 1. Specifically, an object of the present invention is to calculate a probability distribution of queue delays by using, as input, readily available arrival processes and service time distribution averages and variances in the queuing model GI / GI / 1. .

A queue delay calculation apparatus according to an aspect of the present invention provides:
A queue delay calculation device for calculating a queue delay,
An in-system number estimation means for calculating an in-system number distribution by calculating an explicit solution of diffusion approximation by using moment observation values up to the second order of arrival time to the queue;
Queue delay distribution calculating means for calculating the queue delay distribution by using the calculated intra-system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time,
It is characterized by having.

A queue delay calculation method according to an aspect of the present invention includes:
A queue delay calculation method in a queue delay calculation device for calculating a queue delay,
A step of calculating an in-system number distribution by calculating an explicit solution of diffusion approximation by using the moment observation value up to the second order of the arrival time to the queue as an input by the in-system number estimating means of the queue delay calculating device; When,
The queue delay distribution calculating means of the queue delay calculating device calculates the queue delay distribution by using the calculated intra-system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time as inputs. Steps,
It is characterized by having.

A program according to one aspect of the present invention is:
A program for operating a computer as a cue delay calculation device that calculates cue delay, and using this computer as input for moment observation values up to the second order of arrival time to the cue, an explicit solution of diffusion approximation is calculated System input number estimation means for calculating the system number distribution, and the calculated system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time as input. A queue delay distribution calculating means for calculating a delay distribution;
It is made to function as.

  According to the present invention, it is possible to calculate the probability distribution of the queue delay with the arrival process and the average and variance of the service time distribution as inputs.

1 is a configuration diagram of a queue delay calculation apparatus according to an embodiment of the present invention. The figure which shows the example of the input information identification means of the queue delay calculation apparatus which concerns on the Example of this invention. Flowchart of queue delay calculation method according to an embodiment of the present invention The figure which shows the comparison with the estimation result in the queue delay calculation apparatus which concerns on the queue delay calculation apparatus which concerns on the Example of M / D / 1 system internal number

  Examples of the present invention will be described in detail below.

  In the embodiment of the present invention, an approximate value of the probability distribution of the queue delay at the bottleneck link of the network is output as an input of moment observation values up to the second order for the arrival interval and the Nth order (N ≧ 2) for the service time. A queue delay calculation apparatus will be described.

  The queue delay calculation apparatus according to the embodiment of the present invention calculates and uses an explicit solution of the diffusion approximation, and in the queuing model GI / GI / 1, the arrival process and the average of the waiting time distribution that are easily available And the variance as inputs, the system number distribution at each time or steady state is output. Next, a queue delay distribution is calculated based on the calculated intra-system number distribution. Here, moment distributions up to the Nth order (N ≧ 2) of the service time are used, and asymptotic expansion is used to calculate the waiting time distribution of arrival packets at that time.

  FIG. 1 is a configuration diagram of a queue delay calculation apparatus according to an embodiment of the present invention. The queue delay calculation apparatus includes an in-system number estimation unit 101 and a queue delay distribution calculation unit 102. Further, as will be described below, the queue delay calculation device is configured to input information for identifying the average and variance of the arrival intervals and the observed moment values up to the Nth order of the service time from the measured values of the arrival intervals and the measured service times. You may further have the identification means 103. FIG.

  First, the input information identifying unit 103 identifies the average and variance of arrival intervals and the observed moment values up to the Nth order of service time from the observed network information, and uses it as input information to the in-system number estimating unit 101. . For example, as shown in FIG. 2, the input information identification unit 103 extracts the time interval of arrival packets from the packet capture data before and after the bottleneck link router, and calculates the average value and standard deviation. The service time is captured by a packet capture device synchronized in time before and after the router, and the router transit time is measured. If the packet transit time of each packet p_i (i = 1, 2, ..., M) is t_i (i = 1, 2, ..., M), the k-th moment observed value μ_k (k = 1 , 2, ..., N) can be obtained as follows.

μ_k = E [t_i ^k ]
However, the input information to the in-system number estimation means 101 may be measured by another device. For example, in the case of batch processing in a server, it is also possible to acquire these values by utilizing a log in a server terminal.

  The input to the intra-system number distribution calculating means 101 is moment observation values up to the second order of the arrival interval and service time. The in-system number distribution calculating means 101 calculates and outputs an in-system number distribution at a desired time t or in a steady state based on the explicit diffusion solution (2) shown below and the input. The output of the in-system number estimation unit 101 is input to the queue delay distribution calculation unit 102.

  The diffusion approximation of GI / GI / 1 that employs the basic reflecting wall boundary condition that the intra-system number distribution calculation means 101 uses to calculate the intra-system number distribution is expressed as follows.

ここで方程式の係数は
(α,β)=(λK_a+μK_s,λ-μ)
により与えられ（非特許文献１参照）、前記入力された到着間隔及びサービス時間の2次までのモーメント観測値から算出するものとする。(λ,K_a,μ,K_s)はそれぞれ平均到着率、到着間隔の変動係数（標準偏差を平均で除した値）、平均サービス率、サービス時間の変動係数である。独立変数(x,t)はそれぞれ系内数の近似値と時刻、未知変数f(x,t)は時刻tにおける系内数の確率密度関数、Λ^-1は系内数が0となる時間間隔の平均、R(t)は時刻tにおける系内数0の確率を示す。

Where the coefficient of the equation is
(α, β) = (λK_a + μK_s, λ-μ)
(See Non-Patent Document 1), and is calculated from the moment observation values up to the second order of the input arrival interval and service time. (λ, K_a, μ, K_s) are an average arrival rate, a variation coefficient of arrival intervals (a value obtained by dividing the standard deviation by an average), an average service rate, and a variation coefficient of service time, respectively. The independent variable (x, t) is the approximate value and time of the system number, the unknown variable f (x, t) is the probability density function of the system number at time t, and Λ ^-1 is the time when the system number is 0 The average of the intervals, R (t), indicates the probability of 0 in the system at time t.

  Although the above (1) is given as a model, its explicit solution has not been known until now (see Non-Patent Document 2). Therefore, the in-system number distribution calculation means 101 first gives the above-mentioned explicit solution and uses this to realize simple calculation of the in-system number distribution and the queue delay distribution. Specifically, the explicit solution can be obtained as follows.

*、*xはそれぞれ(x,t)及びxに関する畳み込み、δ(・)、H(・),はそれぞれDiracのデルタ関数、Heavisideのステップ関数である。解の表現（2）を得る具体的な証明は省略する。

* And * x are convolutions about (x, t) and x, respectively, and δ (·) and H (·) are a Dirac delta function and a Heaviside step function, respectively. The concrete proof for obtaining the solution expression (2) is omitted.

  In order to calculate the system number distribution in the steady state, the following function obtained as t → ∞ in (2) above is applied.

次に再度図1を使用して、キュー遅延分布算出手段１０２につき記載する。キュー遅延分布算出手段１０２は、系内数推定手段１０１で算出された系内数分布とサービス時間分布のN次（N≧2）までのモーメントを入力として、キュー遅延分布を算出し、出力する。ここでNは、後述するように所望の推定精度要件に応じて設定する。ここでは、観測されているサービス時間分布のモーメント次数に応じ、分布関数に対する標本数に関する漸近展開の適用により、近似的にキュー遅延W_tの分布を算出・出力する。

Next, the queue delay distribution calculating means 102 will be described again using FIG. The queue delay distribution calculating unit 102 calculates and outputs the queue delay distribution by using the system number distribution calculated by the system number estimating unit 101 and the moment up to the Nth order (N ≧ 2) of the service time distribution as inputs. . Here, N is set according to a desired estimation accuracy requirement as described later. Here, the distribution of the queue delay W _t is approximately calculated and output by applying asymptotic expansion regarding the number of samples to the distribution function according to the observed moment order of the service time distribution.

ここでP(W_t≦y)はキュー遅延yの分布関数、P(k,t)は時刻tにおける系内数kの確率密度であり、前記（２）により得たf(x,t)を用いて以下の通り算出する.

Here, P (W _t ≦ y) is the distribution function of the queue delay y, P (k, t) is the probability density of the number k in the system at time t, and f (x, t) obtained by the above (2) Is calculated as follows.

また、

Also,

は当該系内kパケットの全処理時間がy以下である確率を表す。当該確率は未知であるが、系内数kに関して漸近的に正規分布に従うことから、系内数kに関する漸近展開により近似的に陽な表現を求めることができる。以上により、式（３）を用いてキュー遅延分布算出手段１０２の出力が算出される。これがキュー遅延算出装置の最終出力である。

Represents the probability that the total processing time of the in-system k packet is y or less. Although the probability is unknown, since it follows the normal distribution asymptotically with respect to the system number k, an approximately explicit expression can be obtained by asymptotic expansion with respect to the system number k. As described above, the output of the queue delay distribution calculating unit 102 is calculated using the equation (3). This is the final output of the queue delay calculation device.

  Next, a flowchart of a queue delay calculation method according to an embodiment of the present invention will be described with reference to FIG.

  First, in step S101, the input information identification unit 103 identifies input information. The input information identification unit 103 identifies, as input information, the average and variance of arrival intervals from the observed network information and the observed moment values up to the Nth order of the service time distribution. The average and variance of arrival intervals can be identified, for example, by observing the number of packets that arrive at a predetermined time interval. The service time distribution is obtained by observing the transit time of each packet by measurement before and after the router. As described above, the input information identification unit 103 itself may exist in another apparatus and is not defined here. In model (1), R (t) and Λ need to be given. These are given in advance.

  Next, in step S102, the in-system number distribution calculating unit 101 estimates the in-system number distribution. The in-system number distribution calculating unit 101 calculates and outputs the in-system number distribution at a desired time by substituting the input information from the input information identifying unit 103 into the model (1).

  In step S103, the queue delay distribution calculation unit 102 calculates a queue delay distribution based on the calculated intra-system number distribution and outputs the queue delay distribution. Here, the waiting time that the packet arriving at the system enjoys after the processing of the packet arriving before it follows the same service time distribution. For this reason, the waiting time experienced by a packet arriving at the system at a certain time is the sum of random variables that follow the independent and uniform distribution of packets in the system at that time. The queue delay distribution calculating means 102 first calculates a probability P (k, t) that is an in-system number k (k = 0, 1, 2,...) As an output of the in-system number distribution calculating means 101. Using f (x, t), the following calculation is performed (Equation (3) again).

次に式（３）を用いて、時刻tにおける待ち時間W_tがx以下である確率P(W_t≦y)を以下の様に算出する。

Next, using equation (3), the probability P (W _t ≦ y) that the waiting time W _{t at} time _t is less than or equal to x is calculated as follows.

ここで

here

は、当該系内の全処理時間がy以下である確率を表す。この確率について、系内数kが大きい場合には、中心極限定理により当該分布は系内数に関し漸近的に平均、標準偏差がそれぞれ(k/μ,kσ_s)の正規分布のそれに従うことが知られている。ここでσ_sはサービス時間の標準偏差である。また更に精度を高める手段としてEdgeworth展開が知られている。Edgeworth展開では、サービス時間分布のモーメントを高次まで入力するほど、推定誤差を標本数の負冪のオーダで抑制することができる。例として、ここでは２次のEdgeWorth展開により

Represents the probability that the total processing time in the system is y or less. With regard to this probability, when the system number k is large, the central limit theorem indicates that the distribution asymptotically follows the normal distribution with an average and standard deviation of (k / μ, kσ_s). It has been. Here, σ_s is a standard deviation of service time. Further, Edgeworth expansion is known as a means for further improving accuracy. In Edgeworth expansion, the estimation error can be suppressed on the order of negative number of samples as the moment of service time distribution is input to higher order. As an example, here is a secondary EdgeWorth expansion

の表現を陽に与える手法を記載する。この場合、推定誤差はo(k^-1.5)である。

Describes a method for explicitly giving the expression. In this case, the estimation error is o (k ^−1.5 ).

First, consider a random variable Z with normalized service time distribution and its k sample values {Zi} _{i = 1} ^k .

Z = (X-μ) σ _s ^-1
Applying the second-order EdgeWorth expansion to this, the probability distribution of the k sums is given as follows.

ここでΦ(・)、φ(・)はそれぞれ標準正規分布の分布関数及び確率密度関数、H_i(・)(i=2,3,5)はi次Hermite多項式、(μ₃,μ₄)はサービス時間分布の3次及び4次のモーメントである。従って前記所望の確率は、近似的に以下の様に表現することができる。

Where Φ (•) and φ (•) are the distribution function and probability density function of the standard normal distribution, H _i (•) (i = 2,3,5) is the i-th order Hermite polynomial, (μ ₃ , μ ₄ ) Is the third and fourth moment of the service time distribution. Therefore, the desired probability can be approximately expressed as follows.

これが本装置の最終出力である。

This is the final output of this device.

  The Hermite polynomial is given as follows in the case of up to the fifth order, for example.

＜本発明の実施例の効果＞
上記のように、一般的なGI/GI/1モデルを対象とする場合、従来技術では、確率密度関数を陽に表現する手段が存在しなかった。このため、コンピュータ上に待ち行列システムを実装して、シミュレーションを膨大な回数反復し、近似する手段しか存在しなかった。本発明の実施例では、各時刻における確率密度関数の近似値を陽に求めて用いることにより、各時刻における確率密度を、陽な表現で極めて容易に出力することが可能である。

<Effect of the embodiment of the present invention>
As described above, when a general GI / GI / 1 model is targeted, the prior art has no means for explicitly expressing the probability density function. For this reason, there is only a means for implementing a queuing system on a computer, repeating the simulation numerous times, and approximating it. In the embodiment of the present invention, by using the approximate value of the probability density function at each time explicitly obtained and used, the probability density at each time can be output very easily in an explicit expression.

  According to the embodiment of the present invention, in the queuing simulation according to the GI / GI / 1 model according to the general probability distribution for both the arrival process and the service time distribution, the average arrival rate, the variation coefficient of the arrival interval, and the moment of the service time are input. The intra-system number distribution and the queue delay distribution at each time can be calculated. Therefore, the present invention can be applied to a network quality control technique for estimating / predicting a queue delay in a bottleneck link of the network by simple measurement on the network.

  Since the method according to the embodiment of the present invention can also calculate the number of systems and the distribution of delay at an arbitrary time, it can be used for predictive estimation of distribution distribution in the future and distribution in a steady state.

  In the following, an example of a queue delay distribution when the apparatus according to the embodiment of the present invention is used when the arrival process is a Poisson process and the waiting time is fixed (M / D / 1) will be shown. The average value 1 / λ of arrival intervals, the variation coefficient K_a, the average value 1 / μ of service time, and the variation coefficient K_s are as follows.

(1 / λ, K_a, 1 / μ, K_s, μ ₃ , μ ₄ ) = (2,1,1,0,0,0)
The time for which the distribution is to be estimated is given as t = 10, Λ = 0.5, and R (t) = 1 + exp (−t). In this case, ρ = 0.5.

  With this as an input, the service time distribution estimated by the embodiment of the present invention is as shown in FIG. 4, which is almost equal to the theoretical value of the probability density function of the steady state queue delay of M / D / 1 when ρ = 0.5. It can be confirmed that the results are obtained.

  The embodiment of the present invention is applicable to a queuing model (GI / GI / 1 model) having a single server and an infinitely long queue including an M / M / 1 model and the like.

  For convenience of explanation, the queue delay calculation device according to the embodiment of the present invention has been described using a functional block diagram. However, the queue delay calculation device according to the embodiment of the present invention may be hardware, software, or their It may be realized in combination. In addition, the functional units may be used in combination as necessary. Further, although the method according to the embodiment of the present invention has been described using the flowchart showing the flow of processing, the method according to the embodiment of the present invention may be performed in an order different from the order shown in the embodiment. .

  As described above, the method for calculating the probability distribution of the queue delay using the arrival process and the average and variance of the service time distribution as input has been described, but the present invention is not limited to the above-described embodiments, and Various modifications and applications can be made within.

101 In-system number estimation means 102 Queue delay distribution calculation means 103 Input information identification means

Claims (7)

A queue delay calculation device for calculating a queue delay,
An in-system number estimation means for calculating an in-system number distribution by calculating an explicit solution of diffusion approximation by using moment observation values up to the second order of arrival time to the queue;
Queue delay distribution calculating means for calculating the queue delay distribution by using the calculated intra-system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time,
A queue delay calculating device.   The queue delay calculation apparatus according to claim 1, wherein the in-system number estimation unit further calculates an in-system number distribution in a steady state. The intra-system number estimation means is a probability density function f (x, t) of an approximate value x of the intra-system number at time t:

Where (α, β) = (λK_a + μK_s, λ-μ),
(λ, K_a, μ, K_s) is the average arrival rate, arrival interval variation coefficient, average service rate, service time variation coefficient,
Λ ^-1 is the average of the time intervals when the in-system number is 0, R (t) is the probability of in-system number 0 at time t,
*, * X are convolutions about (x, t) and x, respectively, δ (・), H (・), are Dirac delta functions, Heaviside step functions,
The queue delay calculation apparatus according to claim 1, wherein the intra-system number distribution is calculated by using. The queue delay distribution calculating means is a probability density P (k, t) of the number k in the system at time t:

And the probability that the processing time in the system is y or less:

Is approximated by an asymptotic expansion for the number k in the system, and the probability density function P (W _t ≤ y) of the queue delay W _t :

The queue delay calculation apparatus according to claim 3, wherein   By observing packets that arrive at a communication device, the average and variance of moment observation values up to the second order of the arrival time are identified, and by observing the transit time of the communication device, up to the Nth order of the service time The queue delay calculation device according to claim 1, further comprising input information identification means for identifying a moment observation value. A queue delay calculation method in a queue delay calculation device for calculating a queue delay,
A step of calculating an in-system number distribution by calculating an explicit solution of diffusion approximation by using the moment observation value up to the second order of the arrival time to the queue as an input by the in-system number estimating means of the queue delay calculating device; When,
The queue delay distribution calculating means of the queue delay calculating device calculates the queue delay distribution by using the calculated intra-system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time as inputs. Steps,
A queue delay calculation method. A program for operating a computer as a cue delay calculation device that calculates cue delay, and using this computer as input for moment observation values up to the second order of arrival time to the cue, an explicit solution of diffusion approximation is calculated System input number estimation means for calculating the system number distribution, and the calculated system number distribution and the observed moment values up to the Nth order (N ≧ 2) of the queue service time as input. A queue delay distribution calculating means for calculating a delay distribution;
Program to function as.

Images