Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
2000-02-29
2002-08-06
Chin, Wellington (Department: 2664)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S231000, C370S236000, C370S410000, C709S224000, C709S233000
Reexamination Certificate
active
06430160
ABSTRACT:
FIELD OF THE INVENTION
This application relates to the field of computer network performance and more particularly to estimating data delays that packets encounter as they are routed through a network.
BACKGROUND OF THE INVENTION
As IP networks move toward improving quality of service, Internet service providers (ISP) have been including quality of service into their service level agreements with customers. The quality of service in service level agreements may include network availability and reachability. ISPs may also include end-to-end delay benchmarks within their network into service level agreements. Such benchmarks may allow ISPs to provide better services to existing applications, such as Web browsing, as well as to new emerging services such as IP telephony and e-commerce, by providing guarantees of achieving such benchmarks.
The ability to measure quality of service may be critical to ensure that the network delivers the performance that the service level agreement promises. Measurement tools may monitor the network for compliance with the service level agreement, and identify where the provider needs to allocate more network resources.
The ability to measure quality of service may be critical to ensure that the network delivers the performance that the service level agreement promises. Measurement tools may monitor the network for compliance with the service level agreement, and identify where the provider needs to allocate more network resources.
Probe packets may be used to measure delays. Probe packets are packets that an experimenter injects into the network with the intention of measuring some aspect of their behavior, such as delay. Although probe packets could be actual user data packets, typically they are not because the experimenter wants to control the probes behavior more fully than the user's application would permit. For example, the experimenter might wish to prescribe exactly when probes are transmitted or to set the packets sizes. The experimenter might want to make the packets as small as possible to minimize their usage of network resources. Injecting probe packets into a network involves the routine use of standard networking utilities available on any PC or workstation.
One technique for estimating benchmarks related to end-to-end data traffic delay is to send small probe packets and measure their delays. For example, the Internet utility “Ping” measures the delays that the probe packets experience as they travel from one network location to another. One-way delay measurements require the clocks at the two endpoints to be synchronized, but round trip delay measurements require only that the router at the destination reflect probe packets back to the source. Many ISPs use probes to measure delay performance within their networks. Some commercial companies use probes to measure and compare different ISP network performance.
To determine what probes really measure, account may have to be made for the fact that probes and data may “see” different delay distributions because they arrive differently to a queuing system. Data traffic might be bursty, causing a later arrival to “see,” and be delayed by, an earlier data packet. Probes may see the effects of data traffic burstiness differently.
To determine how well probes measure delays, account may have to be made for sampling error, which arises since only finitely many probes in a given time interval are obtained.
By sampling from various distributions, ensemble averages of various quantities of interest such as average delay time, may be obtained. As is common in ergodic theory, conditions may be examined under which these ensemble averages are approximated by time averages. For example, Ping samples periodically (one probe every x seconds). But it may be difficult to estimate how accurately periodic sampling approximates the time average.
Even if these time averages could be accurately estimated by ensemble averaging, there remains the question of how to relate these averages obtained by using probe packets to averages involving data packets. In the prior art, practitioners may erroneously assume that the delays obtained by using probe packets are the same delays that would be experienced by data packets once sampling error is accounted for. Because obtaining probe information may be easier than obtaining data information, there is motivation to invent a method and system to convert information about probe packet delays into data delays.
SUMMARY OF THE INVENTION
The aforementioned problems may be addressed by correctly translating probe delays into data packet delays. For this purpose, a time average may be used as an intermediate quantity to pass from probe delays to data delays. Two parts may be considered. 1) Probe packets are transmitted according to the departure statistics governing a Poisson process; as described in more detail in the Detailed Description below, the user is able to estimate the time average from the probe delays with a prescribed accuracy. 2) The time average may then be related to the data packet delays. The second part is independent of the method used to obtain the time average. Thus, part 1) provides an improved estimate if the time average of the latter is of interest in another application and part 2) translates between time averages and data delays if techniques other than those in part 1) are used to estimate the time average. As an example of part 1), a better estimate of a time average, such as the fraction of time a resource is busy, may be obtained using Poisson sampling instead of periodic sampling. On the other hand, if periodic sampling were used to estimate a time average delay, the methods under 2) could still translate the time average estimate into data delay estimates.
More specifically, a method of estimating data delays in transmitting data packets from a first location to a second location on a computer network is presented including identifying a bottleneck link in a path connecting the first location to the second location; determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location; and estimating a queuing delay of data from the queuing delay of probes at the bottleneck limit.
The method of estimating data delays may further include adding a sum of data service times and a propagation delay to the queuing delay to obtain an estimate of the data delays. Determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include subtracting a sum of probe service times and a propagation delay from first location to second location probe delays.
Determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include injecting probe packets according to a probability distribution, which may include a Poisson distribution.
The method may further include determining a data packet length distribution served by the bottleneck link.
A method of estimating data delays in transmitting data packets from a first location to a second location on a computer network is also provided. The method includes transmitting probe packets on the computer network; determining probe delays for the probe packets to travel from the first location to the second location; estimating a time average from the probe delays with a prescribed accuracy; and relating the time average to the data delays.
Transmitting probe packets on the computer network may include transmitting probe packets on the computer network from the first location to the second location. Transmitting probe packets on the computer network from the first location to the second location may include transmitting probe packets on the computer network from the first location to the second location according to departure statistics consistent with a stochastic process.
Transmitting probe packets on the computer network from the first location to the second location includes transmitting probe packets on the computer network from the first location to the second location
Li Man
Smith Donald E.
Chin Wellington
Phan M.
Suchyta Leonard Charles
Verizon Laboratories Inc.
Weixel James K.
LandOfFree
Estimating data delays from poisson probe delays does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Estimating data delays from poisson probe delays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimating data delays from poisson probe delays will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2890690