Clock synchronization algorithms for network measurements

Packet delay traces are important measurements for analyzing end-to-end performance and for designing traffic control algorithms in computer networks. Due to the fact that the clocks at the end systems are usually not synchronized and running at different speeds, these measurements can be quite inaccurate. We propose several algorithms to estimate and remove the relative clock skews from delay measurements based on the computation of convex hulls. Compared with existing techniques, such as linear regression and linear programming, the convex-hull approach provides better insight and allows us to handle more error metrics. We obtain algorithms which are linear in the number of measurement points for the case with no clock resets. For the more challenging case with clock resets, i.e., the clocks are reset to some reference times during the measurement period, we develop linear algorithms to identity the clock resets, and derive the best clock skew lines. We extend this analysis to environments in which at least one of the clocks is controlled by NTP (network time protocol). These algorithms can greatly improve the accuracy of the measurements, and can be used both online and offline. They can also be extended for active clock synchronization, to replace or further improve NTP. Numerical experiments are presented to demonstrate the robustness of the algorithms.