臺灣博碩士論文加值系統

摘要　　　　　　
隨著網際網路的蓬勃發展，分散式系統的使用要求也日益增加，對於分散式系統而言，保持彼此間的時間同步是非常重要的議題，本論文引用高精度時間同步協定(Precision Time Protocol, PTP) IEEE 1588 主從式(Master-Slave)架構及時間戳(Time stamp)收發技術來做為系統之模型。
由於現行的網路採用封包交換網路系統，在資料傳輸過程中，有可能參雜大量的封包延時偏差，再加上原先主從式時鐘頻率及時間偏差，使得端點時間戳所記載之時間無法表示實際之封包傳輸時間，進而無法計算出主從式系統間的頻率及時間偏差。
本論文之目的，為發展出一套時間同步演算法，並且在高網路負載及大量封包延時偏差之情況下，仍能有效地估算出精準的頻率及時間偏差，使其能達到PTP系統預期之次微秒(<10-6秒)時間同步性能。

ABSTRACT
As the rapid development of the Internet, the requirement of synchronization between distributed devices increases. This thesis addresses this issue with high-precision time synchronization protocol (Precision Time Protocol, PTP which is also called IEEE 1588), the hierarchical master-slave structure and time stamp transceiver technology as the system model.
Since the current Internet uses the packet-switching technology, there could be a large packet delay variation (PDV) at the receiver. Moreover, the receiver clock is likely to have frequency skew and time offset with respect to the transmitter clock.
In this thesis, we design and implement an effective clock synchronization algorithm. Under heavy traffic load and large packet delay variation situations, our proposed algorithm can provide good estimates of frequency skew and time offset. The precision achieved by our proposed algorithm is sub-microsecond (&lt;10-6 sec).

中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
圖目錄 vii
表目錄 viii

一、Introduction 1
1.1 Introduction 1
1.2 Related works 5
1.3 Structure of the Dissertation 7

二、Background and Problem Formulation 8
2.1 Introduction of Time and Frequency 8
2.2 Network Delay 10
2.3 IEEE 1588 13
2.4 Relative Clock model 15
2.5 Clock Terminology 17

三、Proposed Algorithm 19
3.1 Idea behind the Proposed Algorithm 19
3.1.1 Simple Skew Calculation method and Average
Technique 19
3.1.2 Data fitting technology 21
3.1.3 Linear Programming Method 23
3.2 Proposed Algorithm 25
3.2.1 Two-Way Delay Pre-Detector 25
3.2.2 Modify Linear Least Square Method 28
3.3 Clock Synchronization Algorithm 30

四、Simulation 32
4.1 Algorithm Property and Comparison with Linear
Programming Algorithm 33
4.1.1 Computational complexity 33
4.1.2 Accuracy 34
4.1.3 Distinguish the Delay and Offset 41
4.1.4 Robustness 42
4.2 Long-Term Continuous Time Tracking 44

五、Conclusion 47

參考文獻 48

[1] IEEE Std 1588-2002, IEEE Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems, 8 November 2002.
[2] Vern Paxson, “On calibrating measurements of packet transit times“ , in Measurement and Modeling of Computer Systems, 1998, pp. 11-21.
[3] Sue B. Moon, Paul Skelly, and Don Towsley, “Estimation and removal of clock skew from network delay measurements” , in INFOCOM, March 1999.
[4] Li Zhang, Zhen Liu, and Cathy Honghui Xia, “Clock synchronization algorithms for network measurements” , in INFOCOM, June 2002.
[5] Orion Hodson, Colin Perkins, and Vicky Hardman, “Skew detection and compensation for internet audio applications” , in IEEE International Conference on Multimedia and Expo, July 2000.
[6] H.Khlifi, J.C.Gregoire, “Estimation and removal of clock skew from delay measures” , Proceedings of IEEE LCNcom 2004.
[7] Luca De Vito, Sergio Rapuano, Member, IEEE, and Laura Tomaciello, “One-Way Delay Measurement: State of the Art” , IEEE Transactions on instrumentation and Measurement, Vol.57, NO. 12, December 2008.
[8] Patrick O’Farrell, David Rosselot, “IEEE 1588 Synchronization Over Standard Networks Using the DP83640” , National Semiconductor Application Note 1963, May 14, 2009.
[9] Renaud Sirdey, Francois Maurice, “A linear programming approach to highly precise clock synchronization over a packet network” , Springer-Verlage 2007, 30 October 2007.
[10] Cheng Guang, Gong Jian, Ding Wei, “A Relative Time Model in a Distributed Network using Exchanged Time Information” , Consumer Communications and Networking Conference, 2004.
[11] H. Weibel, “High Precision Clock Synchronization according to IEEE 1588: Implementation and Performance Issues,” in Proc. Embedded World 2005.
[12] Hans Weibel and Dominic Béchaz, “IEEE1588 – Implementation and Performance of Time Stamping Techniques”, Proceedings of NIST Conference on IEEE1588, Gaithersburg, Maryland, 27-29 Sept, 2004
[13] J. C. Eidson, “IEEE-1588 Standard for a Precision Clock Synchronization Protocol for Networked Measurement and Control Systems: Test and Measurement Applications,” Proceedings of the 2005 Conference on IEEE-1588 Standard, Zurich, Oct. 2005.