Method and apparatus for finding latency floor in packet networks
A latency floor between two nodes of a packet-switched network is estimated using transit times of a group of packets traversing the two nodes. In particular, a periodically generated histogram of packet transit times is used to estimate the latency floor. In some packet-switched networks, the behavior of some network elements changes drastically when the network is congested. Because latency floor cannot be accurately estimated under such conditions, packet transit times collected during a congested state of the network are discarded.
1. A method of estimating a latency floor between two nodes of a packet-switched network, comprising the steps of:
collecting transit times of multiple packets traversing the two nodes;
determining a probability density function based on the collected transit times; and
estimating the latency floor using a floor bias correction determined based on a minimum delay cluster width associated with the collected transit times and a width of the probability density function between a fastest N1 percent of the packets and a slowest N2 percent of the packets.
2. The method according to claim 1 , wherein N1 is less than 10 and N2 is less than 10.
3. The method according to claim 2 , wherein N1 is about 5 and N2 is about 5.
4. The method according to claim 1 , wherein the floor bias correction is determined using equation:
floor_bias
=
m
·
[
mdcw
log
10
(
mw
)
]
+
b
nanoseconds
,
mdcw being the minimum delay cluster width, mw being the width of the probability density function between the fastest N1 percent of the packets and the slowest N2 percent of the packets, and m and b being constants.
5. The method according to claim 1 , further comprising transmitting packet pairs each including a high priority packet and a low priority packet, wherein the transit time of the high priority packet is collected if the corresponding low priority packet is received and the transit time of the high priority packet is not collected if the corresponding low priority packet is not received.
6. A method of correcting a frequency of a slave clock with respect to a frequency of a master clock, wherein the master clock and the slave clock are located at first and second nodes of a packet-switched network, respectively, said method comprising the steps of:
(a) transmitting packets from the first node to the second node;
(b) collecting transit times of multiple of the transmitted packets;
(c) determining a probability density function based on the collected transit times;
(d) estimating a latency floor
using a floor bias correction determined based on a minimum delay cluster width associated with the collected transit times and a width of the probability density function between a fastest N1 percent of the packets and a slowest N2 percent of the packets; and
(e) adjusting the frequency of the slave clock based on the estimated latency floor.
7. The method according to claim 6 , wherein steps (a) through (d) are repeated after the frequency of the slave clock has been adjusted according to step (e).
8. The method according to claim 6 , wherein the transmitted packets include packet pairs each including a high priority packet and a low priority packet, wherein the group of the transmitted packets includes high priority packets whose corresponding low priority packets are received at the second node and does not include high priority packets whose corresponding low priority packets are not received at the second node.
9. The method according to claim 6 , wherein the step (d) of estimating includes performing a curve fit to experimental data.
10. The method according to claim 9 , wherein the correction is determined using equation:
floor_bias
=
m
·
[
mdcw
log
10
(
mw
)
]
+
b
nanoseconds
,
mdcw being the minimum delay cluster width, mw being the width of the probability density function between the fastest N1 percent of the packets and the slowest N2 percent of the packets, and m and b being constants determined based on the curve fit.
11. The method according to claim 10 , wherein N1 is less than 10 and N2 is less than 10.
12. The method according to claim 11 , wherein N1 is about 5 and N2 is about 5.
13. A system comprising:
a packet interface for receiving packets from a master clock system through a packet-switched network;
a processor programmed to: (i) collect transit times of multiple received packets, (ii) determine a probability density function based on the collected transit times, (iii) estimate a latency floor using a floor bias correction determined based on a minimum delay cluster width associated with the collected transit times and a width of the probability density function between a fastest N1 percent of the packets and a slowest N2 percent of the packets, and (iv) compute frequency adjustment parameters based on the estimated latency floor; and
an oscillator for generating a clock signal using the frequency adjustment parameters.
14. The system according to claim 13 , wherein the packet interface includes hardware time stamp units.
15. The system according to claim 14 , wherein the hardware time stamp units include a transmit hardware time stamp unit that compensates for delays through a transmitter media access control unit and a transmit hardware time stamp unit that compensates for delays through a receiver media access control unit.
16. The system according to claim 13 , wherein the received packets comprise packet pairs each including a high priority packet and a low priority packet, wherein the group of the received packets includes high priority packets whose corresponding low priority packet is received and does not include high priority packets whose corresponding low priority packet is not received.
17. The system according to claim 13 , wherein the processor is further programmed to perform a curve fit to experimental data.
18. The system according to claim 17 , wherein the floor bias correction is determined by the processor using equation:
floor_bias
=
m
·
[
mdcw
log
10
(
mw
)
]
+
b
nanoseconds
,
mdcw being the minimum delay cluster width, mw being the width of the probability density function between the fastest N1 percent of the plurality of the packets and the slowest N2 percent of the plurality of the packets, and m and b being constants determined based on the curve fit.
19. The system according to claim 18 , wherein N1 is less than 10 and N2 is less than 10.
20. The system according to claim 19 , wherein N1 is about 5 and N2 is about 5.