Dokument: Beating the Clock - An Offline Clock Synchronization Method Inspired by Maximum Likelihood Techniques

Titel:	Beating the Clock - An Offline Clock Synchronization Method Inspired by Maximum Likelihood Techniques
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=33005
URN (NBN):	urn:nbn:de:hbz:061-20141218-144630-9
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Dipl.-Math. Luo, Li [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 701,5 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 18.12.2014 / geändert 18.12.2014
Beitragende:	Prof. Dr. Jarre, Florian [Gutachter] Dr. Scheuermann, Björn [Gutachter]
Stichwörter:	Clock Synchronization Maximum Likelihood
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibungen:	Die Analyse von Übertragungslogdateien eines Netzwerkes ist ein wichtiges Werkzeug in der Entwicklung von neuen Netzwerkprotokollen und vernetzten Geräten. Logdateien speichern unter anderem zu welchen Zeitpunkten Übertragungen statt finden. Aber Logdateien von unterschiedlichen Geräten sind schlecht vergleichbar, da die gespeicherten Zeitstempeln durch zufällige Verzögerungen, unvollständigen Übertragungen, und ungenaue Uhren verfälscht werden. Online Synchronisierungsprotokollen sind nicht immer anwendbar, bereiten zusätzlichen Implementierungsaufwand, und können gewisse zufällige Verzögerungen nicht korrigieren. Aus diesen Gründen kann ein Offline Synchronisierungsverfahren, welches die Zeitstempeln im Nachhinein korrigiert, viel ansprechender sein. In vielen Netzwerkkarten erfolgt eine Übertragungen an alle benachbarten Geräten. Die vorliegende Arbeit nutzt diese Eigenschaft aus, um die Erzeugung der Zeitstempeln als das Ziehen einer Zufallsstichprobe einer unbekannten Verteilung zu interpretieren. Wenn die Uhren als Funktionen modelliert werden, dann können die Inverse dieser Funktionen auf natürlicher Weise als Parameter dieser unbekannten Verteilung interpretiert werden. Dies erlaubt uns die inversen Uhren mit Hilfe von Schätzverfahren zu schätzen. Die vorliegende Arbeit verwendet hierfür einen Maximum-Likelihood Ansatz, um ein effizientes offline Synchronisierungsverfahren herzuleiten. Es zeigt sich, dass die Schätzungen die Lösungen von dünnbesetzten linearen Programmen sind, die sich mit Hilfe eines speziell angepassten Innere-Punkte-Verfahrens unter Ausnutzung dieser Nullstruktur effizient berechnen lassen, sogar für große Stichproben. Unter schwachen Regularitätsannahmen, zeigt die vorliegende Arbeit, dass das Schätzverfahren stark konsistent ist; das heißt, die Schätzungen konvergieren fast sicher gegen die inversen Uhren. Die Simulationen zeigen genau das vorhergesagte asymptotische Verhalten. Tatsächlich, gibt sie Anlass zu vermuten, dass das Schätzverfahren unter allgemeineren Annahmen ebenfalls konsistent ist. The analysis of network transmission log files is an important tool in the design process of network protocols and devices. As the logs record when which device sent or received a transmission. The very character of network communication makes log files of multiple devices hard to compare, as they suffer from random delays, incomplete transmissions, and inaccurate or non-synchronized clocks. Online clock synchronization protocols are not always applicable, require additional implementation effort, and can not eliminate certain random delays. Thus, offline clock synchronization, a post processing method which corrects the timestamps in log files, is very appealing. In a local broadcast network a transmission is received by multiple devices. Exploiting this fact, this thesis models the timestamps generation as sampling of an unknown distribution which is parameterized by the inverse of clock functions. This allows us to apply maximum likelihood estimation techniques to create an offline clock synchronization method. It is shown that the presented estimates are optimizers of linear programs with well-known sparsity structure. Thus, they can be computed efficiently with a tailored interior point method even for a large amount of samples. Further, under some weak regularity assumptions, the thesis establishes the strong consistency of the presented estimator. That is, the estimates converges almost surely to the inverse clock functions. The simulation displays the predicted asymptotic as expected. Even more, it indicates that consistency might remain valid under more general assumptions.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Mathematische Optimierung
Dokument erstellt am:	18.12.2014
Dateien geändert am:	18.12.2014
Promotionsantrag am:	16.09.2014
Datum der Promotion:	21.10.2014