Delay tomography is an inference technique for link delays in a network, where end-to-end route measurement is a promising method to reduce measurement overhead. Furthermore, by incorporating compressed sensing, delay tomography can efficiently detect sparse anomaly. In delay tomography, however, there is an inevitable issue that is clock synchronization for the route measurements. In this paper, based on route referencing, we study synchronization-free delay tomography with compressed sensing. From theoretical analysis, optimal route referencing and ordering methods for synchronization-free delay tomography are derived as “subtractive and differential schemes,” which cancel or minimize the error factors caused by clock asynchronism, clock skew, and normal link delays with single or multiple references, respectively. Simulation experiments confirm that the proposed methods can identify abnormal links more accurately with robustness against the error factors than a conventional scheme, where the newly proposed differential scheme always shows the best performance thanks to its better error factors cancelation.