JP2009044474A - Time error correction method and apparatus in packet transfer delay fluctuation measurement - Google Patents

Abstract

An object of the present invention is to enable accurate measurement by removing an error mixed due to the accuracy of a measuring instrument when measuring packet transfer delay fluctuation, which is one of the performance measures of transfer quality in IPNW.
An accurate packet transfer delay fluctuation value can be estimated by using a characteristic of a measured value and an error, and removing an error by analyzing the measured value using a probability point regression technique. .
[Selection] Figure 4

Description

  The present invention relates to a time error correction method and apparatus in packet transfer delay fluctuation measurement used for measuring the performance of a packet network or its constituent devices, and can particularly improve accuracy particularly compared to a conventionally used method. The present invention also relates to a time error correction method and apparatus in packet transfer delay fluctuation measurement.

One of the performance evaluation measures of transfer quality in an IP network is packet delay fluctuation (see Non-Patent Document 1 and Non-Patent Document 2). When measuring this packet delay fluctuation, an error is mixed depending on the accuracy of the measuring instrument.
The present invention provides a technique for removing an error by analyzing a measured value using characteristics of a measured value and an error when measuring the packet delay fluctuation described above.

The packet delay fluctuation is usually measured and calculated by the following method.
FIG. 1 shows a process for measuring packet delay fluctuation.
In FIG. 1, MP1 indicates a point where a packet enters the network (NW) to be measured, and MP2 indicates a point where the packet leaves the network.

  Step A: The transfer delay time of a plurality of packets is measured according to the method disclosed in Non-Patent Document 1 and Non-Patent Document 3. For that purpose, the transit time is measured (11, 12) at the point where the packet enters the measurement target network (MP1) and the point where it exits (MP2), and the difference is obtained.

Step B: Consider the distribution of measured packet transfer delay times,
(99.9% value)-(minimum value)
Is the desired “packet delay fluctuation”.
This will be described in more detail later using measurement examples shown in FIGS.

That is, if the exact time at which the i-th packet passed MP _j is t _{j, i} , the transfer delay time of the i-th packet without error is
d _i = t _{2, i} −t _{1, i} (1)
And a, is represented by _{{d i}} of the alpha percentage _{P α ({d i})} , accurate delay _{fluctuations, P 99.9 ({d i}} ) - P 0 and _{({d i})} Become.

By the way, when measuring the delay time, a measurement error occurs due to the following factors.
-(1) Error of the internal clock of the measuring instrument-(2) Internal processing time until the time of the internal clock of the measuring instrument is read after the packet passes the measurement point

The error of the internal clock of (1) is accumulated as time passes, and is expressed as a function of elapsed time. Here, the error of the internal clock when the i-th packet is observed by MP _j is used as an elapsed time T _{j, i} −T from the time T at the measurement start time, and f _j (t _{j, i} −T). It expresses.

Further, an error due to the internal processing time when the i-th packet of (2) is observed by MP _j is represented as e _{j, i} . Here, since the internal processing time occurs probabilistically without depending on the passage of time, e _{j, i} is a random variable.

When the time stamp t ′ _{j, i} of the i-th packet in MP _j is expressed using the above symbols, t ′ _{j, i} = t _{j, i} + f _j (t _{j, i} −T) + e _{j, i} . 2)
The delay time d ′ _i of the i-th packet obtained as a measurement result is
d ′ _i = t ′ _{2, i} −t ′ _{1, i
= T 2, i -t 1,} i + f j (t 2, i -T) -f j (t 1, i -T) + e 2, i -e 1, i
= D _i + f ₂ (t _{2, i} −T) −f ₁ (t _{1, i} −T) + e _{2, i} −e _{1, i}
... (3)
It becomes.

And the measurement error of packet delay time is
d ′ _i −d _i = f ₂ (t _{2, i} −T) −f ₁ (t _{1, i} −T) + e _{2, i} −e _{1, i}
(4)
It becomes. When d _i = t _{2, i} −t _{1, i} is sufficiently small with respect to the elapsed time t _{1, i} −T,
f ₂ (t _{2, i} −T) −f ₁ (t _{1, i} −T)
_{= F 2 (t 1, i} -T) -f 1 (t 1, i -T) + o (t 2, i -t 1, i)
= G (t1 _{, i-} T) + o (t2 _{, i-} t1 _{, i} )
... (5)
If a minute amount is ignored, the measurement error is an error related to the elapsed time g (t _{1, i} −T) and an error e _{2, i} −e _{1, i that is} not related to the elapsed time. Expressed as the sum of

ITU-T Recommendation Y.1540, "Internet protocol data communication service-IP packet transfer and availability performance parameters", Dec., 2002 C. Demichelis and P. Chimento, "IP packet delay variation metric for IP performance metrics (IPPM)", RFC, 2002 G. Almes, S. Kalidindi, and M. Zekauskas, "A one-way delay metriv for IPPM", RFC, 1999 Bruce A Mah, "pchar: A tool for measuring internet path characteristics", WWW pages, http://www.enployees.org/bmah/Software/pchar/. J. Fan and I Gijbels, Local Polynomial Modeling and Its Applications, Chapman & Hall, 1996

FIG. 2 and FIG. 3 show time-series graphs when the transfer delay fluctuation in a certain network is measured with an accurate measuring instrument and when measured with a measuring instrument having an error, respectively.
It is known that if the measurement is performed for a long time to some extent, the minimum value of the delay time is substantially constant regardless of the time (see Non-Patent Document 4).

  In FIG. 2, the minimum value of the delay time is certainly almost constant regardless of the time, but in FIG. 3, there is a tendency corresponding to the time, that is, the elapsed time. In addition, although it is a small number, large and small values can be seen regardless of the time.

These are considered to be errors due to the internal clock of the measuring instrument and the internal processing time of the measuring instrument. In the conventional calculation method of delay fluctuation as defined, the delay fluctuation is overestimated due to these errors.
An object of the present invention is to eliminate the problems based on the conventional technique and to estimate the accurate packet transfer delay fluctuation shown in FIG. 2 from the measurement result using an error measuring instrument as shown in FIG. There is in making it possible.

  More specifically, the object of the present invention is to estimate the time of the packet delay fluctuation measurement that can significantly improve accuracy when estimating the accurate packet transfer delay fluctuation from the measurement result using a measuring instrument having an error. An object of the present invention is to provide an error correction method and apparatus.

In order to achieve the above object, the time error correction method in the packet delay fluctuation measurement according to the present invention measures and records the packet transit time at both ends of a specific section on the network, and takes the difference to obtain the packet transfer delay. When measuring time, packet transfer estimates the relative time error of the measuring instrument as the sum of the measuring error inside the measuring instrument related to the elapsed time and the error due to the internal processing time of the measuring instrument regardless of the elapsed time. An error correction method for time in delay fluctuation measurement, in which the measurement error inside the measuring device related to the elapsed time is measured using the measuring device including the error, and the observation time at the originating time input unit of the i-th packet child correction by predicting the percentage of the transfer delay time of the set _{{(t '1, i,} d' i)} by applying the probability point regression analysis, varies depending on the time of day The features.

Here, when applying the probability point regression analysis, the likelihood L _α (g _tmp (t)) as the probability point regression is defined by the following equation to obtain a function with the minimum likelihood. preferable.

In addition, the packet delay fluctuation estimation method according to the present invention is an accurate packet transfer delay that eliminates the relative time error of the measuring device estimated by the time error correction method as described above and the measurement error inside the measuring device. Based on the time, for each sample, d ″ _i = d ′ _i −g ′ (t ′ _{1, i} ) is calculated, and P _99.9 ({d ″ _i }) is calculated as the delay fluctuation estimate. It is characterized by doing.

Further, the present invention can be embodied as an apparatus for estimating packet delay fluctuation.
In other words, the packet delay fluctuation estimation apparatus according to the present invention measures and records the packet transit time at both ends of a specific section on the network, measures the packet transfer delay time by taking the difference, and based on this measurement result A packet transfer delay fluctuation estimating device for estimating packet transfer delay fluctuation, a call origination time input section for receiving a call origination time, a call arrival time input section for receiving a call arrival time, and these call origination time inputs A delay time calculation unit that calculates a delay time in which a time error is corrected in a predetermined packet delay fluctuation measurement based on information from the reception side and the arrival side time input unit, and derives g (t) by probability point regression g (t) Deriving unit, deriving error-corrected delay fluctuation for deriving error-corrected delay fluctuation by correcting error based on g (t) deriving result by g (t) deriving unit Estimation processing unit, and characterized in that it comprises a result display unit for outputting the result of data processing by the processing unit.

According to the present invention, a set {(t ′ _{1, i} , d ′ _i )} of the observation time and the transfer delay time of the i-th packet measured by using a measuring instrument including an error at the source time input unit. By applying the probability point regression analysis, the measurement error is corrected for the part related to the elapsed time and the part not related to the elapsed time, so it is possible to accurately correct the time error in the packet delay fluctuation measurement. In addition, since the packet transfer delay fluctuation is estimated based on the correction result, it is possible to estimate the packet transfer delay fluctuation with high accuracy.

  DESCRIPTION OF EMBODIMENTS Hereinafter, the present invention will be described in detail based on preferred embodiments shown in the accompanying drawings.

FIG. 4 is a diagram illustrating a configuration of an apparatus that estimates packet transfer delay fluctuation according to an embodiment of the present invention.
In FIG. 4, MP1 indicates a point where a measurement target packet (test packet) enters the measurement target network, and MP2 indicates a point where the packet exits the network.
The arrows passing through MP1 and MP2 represent the transfer path of the measurement target packet (test packet) to be transferred.

  Reference numeral 20 denotes a packet transfer delay fluctuation estimation device (hereinafter abbreviated as an estimation device) having a time error correction processing unit (hereinafter abbreviated as a correction processing unit) 26 in packet delay fluctuation measurement. The estimation device 20 is configured to receive start / stop and other instructions from a central control device having a function of monitoring and controlling the entire network.

  In the estimator 20, it is notified from the originating side time input unit 22 and MP2 that receives the time (this is called the originating side time) when the measurement object packet (test packet) is input to the MP1, which is notified from the MP1. From the arrival-side time input unit 24 that receives the time at which the measurement target packet (test packet) arrives at MP2 (this is called the arrival-side time), the above-mentioned originating-side time input unit 22 and the arrival-side time input unit 24 A correction processing unit 26 that performs time error correction in a predetermined packet delay fluctuation measurement, and an estimation processing unit 28 that estimates packet transfer delay fluctuations using an error correction result by the correction processing unit 26, In addition, a result display unit 30 for outputting the estimation result of the packet transfer delay fluctuation by the estimation processing unit 28 is provided.

Based on information from the packet verification unit 26a having a packet verification function for recognizing the measurement target packet (test packet), the originating time input unit 22, and the arrival time input unit 24, the correction processing unit 26 calculates the difference. A delay time calculation unit 26b that calculates a delay time by calculation and a g (t) derivation / error correction unit 26c that derives g (t) by probability point regression described later are provided.
The estimation processing unit 28 has a function of deriving error-corrected delay fluctuations based on the error correction result by the g (t) deriving / error correcting unit 26c.

  In the following description, the operation of the time error correction apparatus in the packet delay fluctuation measurement in the correction apparatus 20 according to the present embodiment will be described based on some reasonable assumptions.

A method for estimating the delay fluctuation is shown under the following assumptions.
Assumption 1: It is assumed that the error g (t _{1, i} −T) related to the elapsed time can be approximated by a polynomial, and the higher order terms can be ignored.
Assumption 2: The probability that the error e _{2, i} −e _{1, i} regardless of the elapsed time is so large that it cannot be ignored is a known value β (%).

Assumption 3: The frequency with which the accurate delay time takes a value near the minimum value is sufficiently high.
Assumption 4: β (%) is sufficiently smaller than 0.1%.
Based on this assumption, from the set {(t ′ _{1, i} , d ′ _i )} of the observation time and the transfer delay time of the i-th packet at MP1 measured using a measuring instrument including an error, the following Estimate exact delay fluctuations in the procedure.

Step 1: For {(t ′ _{1, i} , d ′ _i )}, a minimum value excluding an error is estimated. At that time, the minimum value excluding the error is modeled by an nth order polynomial, and probability point regression using β as a percentage value (quantile regression: see Non-Patent Document 5) is applied.
Step 1-1 Select n + 1 from the measured values {(t ′ _{1, i} , d ′ _i )}. The measurement value at that _time, i _0, i _1, and ... _{i n.}

Step 1-2 measurements _{i 0, i 1,} ... obtains the polynomial of degree n candidate _{g tmp} (t) through the _{i n.}
Against Step 1-3 obtained _{g tmp} (t), obtaining the following likelihood _{L α (g tmp (t)} ).

Step 1-4 all of the measured values _{i 0, i 1,} ... _i do steps 1-3 for the combination of _n, the most likelihood decreases the _{g tmp} (t) at the time of, the probability point regression curve g '(t ).
Step 2 Calculate d ″ _i = d ′ _i −g ′ (t ′ _{1, i} ) for each sample.
Step 3 Let P _99.9 ({d ” _i }) be an estimate of the delay fluctuation.

Assumption 3 makes it possible to apply regression analysis because there are many samples with an accurate delay time near the minimum value. Premise 1 is necessary to model the regression equation with a polynomial. Since the estimation target by regression analysis is not the average value but the minimum value, probability point regression is used. If there is no error e _{2, i} −e _{1, i that} is not related to the elapsed time, 0 measurement value as β (%) includes an error that is not related to the elapsed time. Regress the removed minimum value. Therefore, as assumption 2, β (%) needs to be known.

In the probability point regression, the minimum value excluding the error is estimated, but in d ″ _i calculated in Step 2, an error that is not related to the elapsed time is mixed again. %) Is sufficiently small compared to 0.1%, the influence on P _99.9 ({d " _i }) is sufficiently small.

Further, in Non-Patent Document 2, the constant term of g (t _{1, i} −T) approximated by a polynomial is the relative difference in time of MP1 and MP2, the relative term of time is relative skew, and the secondary term is time. This is called a relative draft, and at most, polynomials within the second order are practical.

  With respect to the apparatus for estimating the packet transfer delay fluctuation shown in FIG. 4, when the above-described assumptions occur in a situation that falls outside the predetermined range, this is detected quickly, and the packet transfer delay fluctuation is erroneously detected. In order to avoid the estimation, for example, the measurement value that is the basis of the delay time calculation is displayed in the subsequent stage of the delay time calculation unit 26b in the correction processing unit 26 in FIG. 4 (see the example in FIG. 3). It is also preferable to have the operator check this.

  In the case where the measured value deviates significantly from the example of FIG. 3, for example, changes in a curved shape, the definition of the likelihood used here may not be used, so the measurement is temporarily interrupted, Since it may be necessary to search for the cause of the abnormality, it is also important to make it easier to cope with it.

  The above embodiment shows an example of the present invention, and the present invention is not limited to this. It is possible to make appropriate changes and improvements within the scope not changing the gist of the present invention. Needless to say.

It is a figure which shows the process of a packet delay fluctuation measurement. It is a figure which shows the example of the delay time measured with the exact measuring device. It is a figure which shows the example of the delay time measured with the measuring device with an error. It is a figure explaining the structure of the error correction apparatus of the time in the packet delay fluctuation measurement which concerns on one Embodiment.

Explanation of symbols

MP1 point where test packet enters NW MP2 point where test packet leaves NW 20 packet transfer delay fluctuation estimation device 22 source side time input unit 24 destination side time input unit 26 correction processing unit 26a packet verification unit 26b delay time calculation Part 26c g (t) deriving part 28 estimation processing part 30 result display part

Claims (4)

When measuring the packet transit time at both ends of a specific section on the network and measuring the packet transfer delay time by taking the difference,
Time error in packet transfer delay fluctuation measurement that estimates the relative time error of the instrument as the sum of the measurement error inside the instrument related to the elapsed time and the error due to the internal processing time of the instrument not related to the elapsed time A correction method,
The measuring device inside the measurement error related to the elapsed time, i th observation time at the originating time input unit of the packet transfer delay time set {(t _'1 was measured using a measuring instrument including an _{error, i} , D ′ _i )}, and applying a probabilistic point regression analysis to predict a percentage value that varies according to the time, thereby correcting the time error in the packet transfer delay fluctuation measurement. In applying the probability point regression analysis, the likelihood L _alpha as a probability point regression _{(g tmp (t)),} defined by the following formula, according to claim 1 for determining a function that likelihood is minimized Error correction method for measuring packet transfer delay fluctuations.

Based on the accurate packet transfer delay time obtained by removing the relative time error of the measuring device estimated by the time error correction method according to claim 1 and the measuring error inside the measuring device,
For each sample, d ″ _i = d ′ _i −g ′ (t ′ _{1, i} ) is calculated, and P _99.9 ({d ″ _i }) is an estimated value of delay fluctuation, To estimate packet transfer delay fluctuation. Measure and record the packet transit time at both ends of a specific section on the network, measure the packet transfer delay time by taking the difference, and estimate the packet transfer delay fluctuation based on this measurement result. An estimation device,
A predetermined packet delay fluctuation measurement based on information from the calling side time input unit that receives the calling side time, the called side time input unit that receives the called side time, and information from the calling side time input unit and the called side time input unit A delay time calculation unit that calculates a delay time in which the time error is corrected, a g (t) derivation unit that derives g (t) by probability point regression, and a g (t) derivation result by the g (t) derivation unit And an estimation processing unit for deriving error-corrected delay fluctuations, and a result display unit for outputting a result of data processing by each processing unit. Device for estimating packet transfer delay fluctuation.

Images