Ph.D Thesis

Ph.D StudentGurewitz Omer
SubjectClassless Network Time Synchronization and
One-Way Delay Estimation
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROFESSOR EMERITUS Moshe Sidi


Time synchronization is critical in distributed environments. A variety of network protocols, middleware and business applications rely on proper time synchronization across the computational infrastructure and depend on clock accuracy. We suggest a novel non-hierarchical peer-to-peer approach for time synchronization termed Classless Time Protocol (CTP) which exploits convex optimization theory. We develop a distributed protocol that can be implemented over a communication network and prove its convergence to the optimal clock offsets. We show that CTP substantially outperforms hierarchical schemes such as NTP without increasing complexity. We also introduce a new way to synchronize the frequency among all clocks in the network with respect to a single frequency. Our schemes offer network-wide approaches that take into account all clocks in the network and estimate the frequency difference of each clock with respect to the reference time node. The frequency synchronization schemes are easy to implement and do not trigger an excessive amount of traffic. Another part of our work investigates several approaches for the estimation of one-way delays between neighboring nodes without requiring any time synchronization. This is based on conducting one-way measurements among pairs of nodes, and estimating the one-way delays by maximizing the value of the global objective function that is affected by the overall network topology and not just by individual measurements. Finally we show that the two problems of synchronizing clocks and estimating one way link delays are tightly related. We explain how to alternate between the two problems and discuss the tradeoff in terms of complexity when solving the two problems jointly.