One-way delay computations for real time clock synchronization.

Abstract

Global time agreement and clock synchronization in a network of nodes are important issues which cannot be easily measured due to unstable delays and asymmetric paths. An important metric used to obtain an estimation of the network delays is round-trip time. Round-trip time is often for approximating one-way delay. Specifically, under a common, assumption that the path is symmetric, one-way delay is estimated as half the round-trip time. However, very often this estimation is not very accurate. For example, the path that the packet follows to reach its destination is not always the same as reaching its source. Even if the reverse path is symmetric, unstable delays due to operating system intervention, such as interrupts while the packet is waiting at the socket buffer, and/or asymmetries in the processing time of messages make this estimate inaccurate. The aim of this thesis is to review and implement more accurate one-way delay estimation methods. We implement Yoo and Choi’s technique that focuses on measuring round-trip time on both sides with a ping pong procedure to estimate one-way delay using network calculus. We compare divergence of this method to the common practice of using “half the round-trip time”. We also implement Aoki, Oki, and Cessa’s model to measure one-way delay variation by relating it to inter-packet delay, providing linear regression to remove the clock skew. Experiments were performed on CAN Bus with two AVR microprocessors, and on Ethernet with two Odroid XU4 connected to a fast Ethernet router. Results show that one-way delay can, be computed much more accurately than earlier approximations. Moreover, CAN network offers a much smaller one-way delay variation than Ethernet. Notice that further more complex experiments related to computing one-way delay (and especially round trip time) in the presence of other CAN bus traffic in a 6-node configuration have been reported independently at the APPLEPIES conference “Applications in Electronics Pervading Industry, Environment” in Pisa, Italy (September 26-27, 2018). Proceedings are to appear in Lecture Notes in Electrical Engineering.

Η συμφωνία ενός κοινού χρόνου σε ένα δίκτυο με κόμβους είναι ένα σοβαρό πρόβλημα το οποίο δημιουργείται λόγω των ασταθών καθυστερήσεων των κόμβων και ασύμμετρων διαδρομών στο δίκτυο. Μια σημαντική μέτρηση που χρησιμοποιείται για την εκτίμηση καθυστερήσεων δικτύου είναι ο χρόνος απόκρισης μιας κατεύθυνσης ή one way delay. Αν υποτεθεί ότι η διαδρομή του δικτύου είναι συμμετρική, το one way delay εκτιμάται ως το μισό του χρόνου εξυπηρέτησης (turnaround time). Παρόλα αυτά η εκτίμηση συχνά δεν είναι πολύ ακριβής, συνήθως επειδή η διαδρομή ενός δικτυακού πακέτου που ακολουθεί για να φτάσει σε έναν κόμβο δεν είναι ίδια με την διαδρομή που θα κάνει για να επιστρέψει στον αρχικό αποστολέα. Ακόμα και αν η διαδρομή ήταν συμμετρική, καθυστερήσεις λόγω της διαμεσολάβησης του λειτουργικού συστήματος για να διαβιβαστεί το πακέτο από τις δομές δικτύου (π.χ. socket buffer) σε υψηλότερα πρωτόκολλα (user space) και αντίστροφα καθιστούν την εκτίμηση ανακριβή. Σκοπός αυτής της εργασίας είναι να υλοποιηθούν πιο ακριβείς μέθοδοι εκτίμησης του one way delay. Υλοποιήθηκε η τεχνική των Yoo και Choi η οποία επικεντρώνεται στην μέτρηση του χρόνου εξυπηρέτησης μεταξύ δύο κόμβων για την εκτίμηση του one way delay μέσω εξισώσεων network calculus. Στην παρούσα πτυχιακή συγκρίναμε αποτελέσματα της τεχνικής των Yoo και Choi σε διάφορα δίκτυα (Ethernet και CAN Bus) σε σχέση με πιο απλές μεθόδους (μισό του χρόνου εξυπηρέτησης). Επίσης υλοποιήθηκε η μέθοδος των Aoki, Oki, και Cessa για τη μέτρηση της διακύμανσης του one way delay αναλύοντας τις καθυστερήσεις μεταξύ πακέτων σε μονόδρομη client-server επικοινωνία και εφαρμόζοντας γραμμική παλινδρόμηση για να γίνει απαλοιφή του clock skew. Τα πειράματα έγιναν σε δίκτυο CAN Bus με δύο AVR microprocessors και σε δίκτυο Ethernet με δύο Odroid XU4 συνδεδεμένα σε έναν γρήγορο δρομολογητή. Τα αποτελέσματα των πειραμάτων δείχνουν πως το one way delay μπορεί να διαφοροποιείται σημαντικά σε σχέση με απλές προσεγγίσεις. Επιπλέον η διακύμανση του one way delay είναι μικρότερη σε δίκτυα CAN bus είναι μικρότερη από την αντίστοιχη διακύμανση του one way delay σε Ethernet δίκτυα. Πιο περίπλοκα πειράματα που σχετίζονται με στατιστικές μετρήσεις μονόδρομης καθυστέρησης σε ένα δίκτυο CAN συνδεδεμένο σε 6 AVR microprocessors παρουσιάστηκαν στο συνέδριο APPLEPIES “Applications in Electronics Pervading Industry, Environment” στην Πίζα της Ιταλίας ( 26-27 Σεπτεμβρίου 2018).