Measurement of packet loss ratio in a network using end-point data
View Patent ↗The packet loss ratio for a network is measured using only end-point packet counter or byte counter data received from ingress and egress network elements, or all edge routers attached to edge network elements in a virtual private network (VPN). After preprocessing the packet count data from the end-points, the data signal is put through a low pass filter of one or more tap sizes to remove high frequency variations in the ingress and egress packet count data due to the inability to sample selected data sets simultaneously. After filtering the data may be integrated in order to increase detection of small amounts of data packet loss. In order to determine if measurable loss has been detected the standard deviation of the signal is calculated over a selected set of data points prior to the window in which the packet loss ratio is calculated. If the detected packet loss is greater than a predetermined detectability threshold based on the computed standard deviation for a target threshold rate for a certain filter size then the loss rate is reported.
1. A method for measuring data loss rate in a network having an ingress network element and an egress network element comprising the steps of:
inputting counter data measuring the data count into the network at the ingress network element;
inputting counter data measuring the data count out of the network at the egress network element;
calculating the difference between the data count into the network and the data count out of the network for each of a plurality of predetermined intervals to generate a data difference signal;
applying a low pass filter to the data difference signal to generate a filtered data difference signal;
calculating the standard deviation of the filtered data difference signal using data immediately prior to a predetermined window;
calculating the data loss rate based on the filtered data difference signal in the predetermined window; and,
reporting the data loss rate if the data loss rate exceeds a predetermined detectability threshold based on the computed standard deviation of the filtered difference signal.
2. The method of claim 1 further comprising the step of integrating the filtered data signal prior to calculating the standard deviation of the filtered signal.
3. The method of claim 1 further comprising the recreation of missing data counts through interpolation prior to calculating the difference between the data count into the network and the data count out of the network.
4. The method of claim 1 further comprising, prior to applying the filter, the step of correcting the data count due to routing header size differences at the ingress network element and the egress network element due to the use of byte count data.
5. The method of claim 1 further comprising, prior to applying the filter, the step of removing variations in the data counts due to larger than usual sampling times at the ingress or egress network elements.
6. The method of claim 1 further comprising, prior to the applying the filter, the step of adjusting the data counts if the network elements failed to properly update its internal counters.
7. The method of claim 1 wherein the predetermined detectability threshold is approximately six times the computed standard deviation of the filtered difference data signal.
8. The method of claim 2 wherein the predetermined detect ability threshold is approximately three times the computed standard deviation of the filtered and integrated difference data signal.
9. The method of claim 1 further comprising the steps of:
reporting that the data loss is less than the predetermined detectability threshold;
calculating a new computed standard deviation for the filtered data difference signal based on the moving average of the last two computed standard deviations;
shifting the predetermined window forward in time by one interval; and,
repeating the above steps until the predetermined detectability threshold is exceeded.
10. The method of claim 1 further comprising applying an additional plurality of low pass filters having different tap sizes and performing each of the subsequent steps on the respective filtered difference signals in parallel.
11. The method of claim 1 wherein the size of the predetermined window is based on the desired target loss rate and the computed standard deviation of the filtered data difference signal.
12. A method for measuring data loss in a virtual private network having a plurality of edge network elements comprising the steps of:
inputting counter data from each edge network element;
computing the amount of data into the network at each edge network element and the amount of data out of the network at each edge network element from the counter data for a plurality of predetermined intervals;
calculating the difference between the total amount of data into the network and the total amount of data count out of the network for each of the predetermined intervals to generate a data difference signal;
applying a low pass filter to the data difference signal to generate a filtered data difference signal;
calculating the standard deviation of the filtered data difference signal using data immediately prior to a predetermined window;
calculating the data loss rate based on the filtered data difference signal in the predetermined window; and,
reporting the data loss rate if the data loss rate exceeds a predetermined detectability threshold based on the computed standard deviation of the filtered difference signal.
13. The method of claim 12 further comprising the step of integrating the filtered data signal prior to calculating the computed standard deviation of the filtered data signal.
14. The method of claim 12 further comprising the recreation of missing data counts through interpolation prior to calculating the difference between the total amount of data into the network and the total amount of data out of the network.
15. The method of claim 12 further comprising, prior to applying the filter, the step of removing variations in the data counts due to larger than usual sampling times at one or more edge network elements.
16. The method of claim 12 further comprising, prior to the applying the filter, the step of adjusting the data counts if one or more edge network elements failed to properly update an internal counters.
17. The method of claim 12 wherein the predetermined detectability threshold is approximately six times the computed standard deviation of the filtered data difference signal.
18. The method of claim 13 wherein the predetermined detectability threshold is approximately three times the computed standard deviation of the filtered and integrated data difference signal.
19. The method of claim 12 further comprising the steps of:
reporting that the data loss is less than the predetermined threshold;
calculating a new computed standard deviation for the filtered data difference signal based on and average of the last two computed standard deviations;
shifting the predetermined window forward in time by one interval; and,
repeating the above steps until the predetermined detectability threshold is exceeded.
20. The method of claim 12 further comprising applying an additional plurality of low pass filters having different tap sizes and performing each of the subsequent steps on the respective filtered difference signals in parallel.
21. A system for measuring the data loss rate in a network having an ingress network element and an egress network element comprising:
means for inputting counter data measuring the data count into the network at the ingress network element and the data count out of the network at the egress network element;
means for calculating the difference between the data count into the network and the data count out of the network for each of a plurality of predetermined intervals to generate a data difference signal;
means for applying a low pass filter to the data difference signal to generate a filtered data difference signal;
means for calculating the standard deviation of the filtered data difference signal over a set of data point immediately prior to a predetermined window;
means for calculating the data loss rate based on the data difference signal in the predetermined window; and,
means for reporting the data loss rate if the data loss exceeds a predetermined detectability threshold based on the computed standard deviation of the filtered difference signal.
22. The system of claim 21 further comprising means for integrating the filtered data signal prior to calculating the standard deviation of the data difference signal.
23. The system of claim 21 further comprising means for the recreation of missing data counts through interpolation prior to calculating the difference between the data count into the network and the data count out of the network.
24. The system of claim 21 further comprising means for correcting the data count due to routing header size differences at the ingress network element and the egress network element due to the use of byte count data.
25. The system of claim 21 further comprising means for removing variations in the data counts due to larger than usual sampling times at the ingress or egress network elements.
26. The system of claim 21 further comprising means for adjusting the data counts if the network elements failed to properly update its internal counters.
27. The system of claim 21 wherein the predetermined detectability threshold is approximately six times the computed standard deviation of the filtered data difference signal.
28. The system of claim 22 wherein the predetermined detectability threshold is approximately three times the computed standard deviation of the filtered and integrated data difference signal.
29. The system of claim 21 further comprising:
means for reporting that the data loss is less than the predetermined threshold;
means for computing a new standard deviation for the filtered data difference signal based on the moving average of the last two computed standard deviations; and,
means for shifting the predetermined window forward in time by one interval.