On the Time Synchronization of Distributed Log Files in Networks With Local Broadcast Media

Real-world experiments in computer networks typically result in a set of log files, one for each system involved in the experiment. Each log file contains event timestamps based on the local clock of the respective system. These clocks are not perfectly accurate, and deviate from each other. For a thorough analysis, however, a common time basis is necessary. In this paper, we tackle the fundamental problem of creating such a common time base for experiments in networks with local broadcast media, where transmissions can be received by more than one node. We show how clock deviations and event times can be estimated with very high accuracy, without introducing any additional traffic in the network. The proposed method is applied after the experiment is completed, using just the set of local log files as its input. It leads to a large linear program with a very specific structure. We exploit the structure to solve the synchronization problem quickly and efficiently, and present an implementation of a specialized solver. Furthermore, we give analytical and numerical evaluation results and present real-world experiments, all underlining the performance and accuracy of the method.

I. Introduction

A fundamental problem with interpreting results from real-world experiments in computer networks is that each system uses its own local clock to timestamp events. These clocks do not run perfectly synchronously; they can deviate. At the end of the experiment, the result is a set of log files where the timestamps are based on the clocks of the individual systems. This is generally insufficient for the investigation of timing issues, the correlation of events, and the visualization of the experiment. It is thus highly desirable to obtain an event log where all timestamps refer to a single reference clock instead of multiple local clocks.