Search

Clock synchronization over networks is a nontrivial problem that has long been an important topic in the fields of computer science and engineering as it pertains to digital networks and distributed systems. Recently, clock synchronization has received much attention in the study of networked control theory due to the importance of consensus on time in distributed control and estimation settings.This dissertation addresses the need for new clock synchronization schemes with the presentation of several hybrid based approach to clock synchronization problem. To motivate this work, the problem of a hybrid observer, with a clock synchronization scheme, that receives information sporadically over a network is presented. Through an attractivity result on the convergence properties of the observer system, sufficient conditions on the convergence properties of the accompanying clock synchronization scheme demonstrate the need for clock synchronization algorithms with performance guarantees. In one of the solutions to the problem, a distributed hybrid algorithm that synchronizes the time and rate of a set of clocks connected over a network is presented. Clock measurements of the nodes are given at aperiodic time instants and the controller at each node uses these measurements to achieve synchronization. Due to the continuous and impulsive nature of the clocks and the network, a hybrid system model to effectively capture the dynamics of the system and proposed hybrid algorithm is introduced. Moreover, the hybrid algorithm allows each agent to estimate the skew of its internal clock in order to allow for synchronization to a common timer rate. Sufficient conditions guaranteeing synchronization of the timers, exponentially fast are provided. Numerical results illustrate the synchronization property induced by the proposed algorithm as well as robustness to communication noise.Next, an innovative hybrid systems approach to the sender-receiver synchronization of timers is presented. Via the hybrid systems framework, the traditional sender-receiver algorithm for clock synchronization is united with an online, adaptive strategy to achieve synchronization of the clock rates to exponentially synchronize a pair of clocks connected over a network. Following the conventions of the algorithm, clock measurements of the nodes are given at periodic time instants, and each node uses these measurements to achieve synchronization. For this purpose, a hybrid system model of a network with continuous and impulsive dynamics that captures the sender-receiver algorithm as a state-feedback controller to synchronize the network clocks is introduced. Moreover, sufficient design conditions that ensure attractivity of the synchronization set are provided with numerical examples to validate the theoretical results.Finally, a general approach and framework to modeling clock synchronization protocols using hybrid systems is presented. Using the general framework, several existing algorithms from the literature are modeled. The models are then simulated numerically to demonstrate the feasibility of the proposed modeling framework.

Unprecedented Cyber-Physical Systems (CPS) and Internet of Things (IoT) applications such as health care, connected vehicles, and augmented/virtual reality are revolutionizing smart spaces and change how we build and manage our systems. These applications span the cloud and the edge devices and give birth to new system designs with critical dependence on temporal use cases. As such, cloud services are expected to provide timely responses and schedulable demands, while edge devices are required to synchronize observations and choreograph actions across distributed entities. Both cloud and edge demand time awareness in general, and time-indexed queries, precise timestamping, and dynamic clock synchronization in particular. However, contemporary distributed system designs are inherently “clockless” and becoming increasingly complex. They fail to meet consistency, causality, and scheduling demands of underlying applications yet enabling time awareness for various applications running on commodity platforms and operating systems (OS) is a challenge in itself.In this dissertation, we devise a new way of acquiring time information by introducing the notion of Quality of Time (QoT) that collectively captures various time metrics such as resolution, accuracy, stability, and integrity. Analogous to Quality of Service (QoS) in networking, QoT treats time as a controllable OS primitive with observable performance. To provide QoT to applications, we proposed the first OS abstraction – timeline – that reacts to application timing demands and exposes QoT to applications in an easy-to-use, secure, and scalable way. This degree of richness of information had never been available to coordinated applications whose activities are choreographed across time and space. This flow of information was immediately relevant to the broader field of IoT addressing the emerging temporal use cases for applications at the cloud and the edge in a secure fashion. As such, QoT expanded distributed applications to a global scale with no significant overhead and no performance compromise.This dissertation focuses on covering various aspects of QoT. In the first part of this thesis, we design extensible abstractions to characterize timing uncertainty in the presence of timing variations. In an effort to reduce complexity and overhead of current distributed database designs, our abstractions and systems enable globally replicated lockless transactions with simplified design, low overhead and no loss in performance. The second part exposes timing vulnerabilities in trusted execution technologies and network security mechanisms and provides timing integrity by designing secure time architectures in the presence of vulnerabilities. Thus enabling trusted timestamping in commodity systems to preserve one’s digital rights and digital signals. The third part focuses on redesigning the hardware, OS and network interfaces that help time information flow between applications and systems, and enable timing precision. This precision boosts high-speed measurements at large-scale distributed entities. The final section addresses the inefficacy of testing mechanisms for time synchronization protocols deployed in safety-critical environments. We then propose a customized testbed for testing timing robustness under failures and adversarial attacks.Current designs in distributed systems rely on message-passing based protocols and come at a huge energy and bandwidth cost along with high system complexity. In contrast, our designed systems based on QoT support new temporal use cases of globally distributed applications with low computation and communication overhead. We released our system designs to support various time management and clock synchronization use cases in emerging distributed applications.

This dissertation investigates the question: How do we precisely access and control time in a network of computer systems? Time is fundamental for network measurements. It is fundamental in measuring one-way delay and round trip times, which are important for network research, monitoring, and applications. Further, measuring such metrics requires precise timestamps, control of time gaps between messages and synchronized clocks. However, as the speed of computer networks increase and processing delays of network devices decrease, it is challenging to perform network measurements precisely. The key approach that this dissertation explores to controlling time and achieving precise network measurements is to use the physical layer of the network stack. It allows the exploitation of two observations: First, when two physical layers are connected via a cable, each physical layer always generates either data or special characters to maintain the link connectivity. Second, such continuous generation allows two physical layers to be synchronized for clock and bit recovery. As a result, the precision of timestamping can be improved by counting the number of special characters between messages in the physical layer. Further, the precision of pacing can be improved by controlling the number of special characters between messages in the physical layer. Moreover, the precision of synchronized clocks can be improved by running a protocol inside the physical layer by extending bit-level synchronization. Subsequently, we make three contributions embodied in the design, implementation and evaluation of our approaches. First, we present how to improve the precision of timestamping and pacing via access to the physical layer at sub-nanosecond scale. SoNIC implements the physical layer in software and allows users to control and access every bit in the physical layer. Second, we demonstrate that precise timestamping and pacing can improve the performance of network applications with two examples: Covert timing channels and available bandwidth estimation. A covert timing channel, Chupja, is high-bandwidth and robust and can deliver hidden messages while avoiding detection. An available bandwidth estimation algorithm, MinProbe, can accurately estimate the available bandwidth in a high-speed network. Finally, we present how to improve the precision of synchronized clocks via access to the physical layer. DTP, Datacenter Time Protocol, extends the physical layer's link-level synchronization and implements a peer-to-peer clock synchronization protocol with bounded nanosecond precision. Together, these systems and approaches represent important steps towards precise network measurements.

Abstract: A wireless sensor network (WSN) consists of spatially distributed sensor nodes which are deployed to monitor some process of interest. Although WSNs are very promising, the distributed nature, attributes of wireless networks, and availability of limited resources in WSNs introduce significant theoretical and practical challenges. First, the cooperative control of sensor nodes requires to consider subsystems instead of a single system. Second, the communication capabilities and connectivity of the sensor nodes are limited. Third, the information exchange in the wireless sensor network may be unreliable and suffer transmission delays. Fourth, the availability of limited resources imposes constraints on the sampling rates and time synchronization of sensor nodes. Motivated by these challenges, this thesis studies the design of distributing filtering and sampling techniques in resource constrained WSNs. For distributed filtering, one of the most promising techniques are the linear consensus protocols. A motivating example for studying the application of consensus protocols is to investigate the distributed time synchronization problem in WSNs. In this thesis, we study and propose distributed time synchronization protocols which consider an asynchronous framework where the sensor nodes can have different time-periods, starting times and input update times. The clocks in a WSN are modeled by a time-varying system with time-delay terms. By employing tools from nonnegative matrix and graph theories, the convergence analysis is presented. Most of the standard control and monitoring techniques rely on uniform and synchronized sampling. A sensor node has limited battery resources and their efficient utilization imposes constraints on the time synchronization of the sensor nodes which introduces sampling jitters. In this thesis, we model WSNs employing distributed sampling using filter banks and present the design of synthesis filters to minimize the effects of sampling jitters. We consider two cases for the design of synthesis filters. In the first case, we consider a hybrid filter bank and assume that the sampling jitter is known for each sensor. We employ tools from sampled-data control theory and present a procedure to design optimal H2 synthesis filter bank to handle sampling jitters and reconstruct uniformly sampled measurements. In the second case, we consider a discrete-time filter bank and allow the sampling jitters to be time-varying. Using polytopic matrices to encompass all possible representations of the system matrices, the problem is reduced to an Hinfty optimization problem and the design of pre-processing filters is presented. All the theoretical development and the proposed techniques in this thesis are validated using simulation examples.

Ad Hoc wireless networks have been gaining importance in the communication world for the past decade. Wireless network extends the access to the network by removing the restriction of physical wires. Ad hoc network further improves the network coverage and availability to places without infrastructure support. Clock synchronization and dominating set are two of the fundamental issues in the wireless ad hoc networks. They are important for the correctness and/or performance of many protocols and applications. We focus on IEEE 802.11 wireless ad hoc networks in this dissertation due to the wide deployments of 802.11 networks. The theories and practices are definitely extensible to other types of ad hoc networks. IEEE 802.11 wireless network depends heavily on the distribution of timing information to all the stations in the network. Clock synchronization is important for frequency hopping, power saving and wireless medium reservation. We review the Timing Synchronization Function (TSF) of Ad Hoc mode defined in the 802.11 standard. It is well-known that the 802.11 TSF is not scalable. We carefully analyze the root causes of the scalability problem and design new schemes to overcome the problem. Our new schemes show great improvement over the 802.11 TSF and other solutions in the fields. Our solutions have nice characteristics: scalable, accurate, bounded and adaptive to station mobility. We are able to control the maximum clock differences under 25 micro seconds and 50 micro seconds in single hop and multihop networks respectively. The performance improvement is at least 200% or more compared with the current solutions. Dominating set has been widely used in multihop ad hoc networks (MANET) by numerous routing, broadcast and collision avoidance protocols. The problem to construct a minimum sized dominating set is known to be NP-hard. We propose a protocol that is simple, distributed, inexpensive, and adaptive to station mobility. We show that our protocol can construct dominating set using 35% to 60% less nodes than other distributed dominating set protocols. We study and address two of the fundamental and difficult problems in ad hoc wireless networks. Our solutions show significant improvements over the current solutions. Our work provides solid foundations to other important problems: routing, power saving, frequency hopping, media access scheduling, and broadcast storm mitigation.

We investigate a framework for assessing the readiness of a network to support Voice over IP (VoIP) at the pre-deployment stage. In this framework, VoIP traffic is synthesized on the network, while simultaneously monitoring the health of network devices and links using the Simple Network Management Protocol(SNMP). Using this framework, we try to understand whether SNMP can be used to detect which network links or devices, if any, cause poor VoIP quality. First, we investigate the limitations of the end-to-end VoIP quality measurement, and SNMP measurement framework used in lab experiments. We quantify the errors in end-to-end VoIP quality measurements, and in SNMP measurements, so that these errors can be taken into account depending on the application at hand. Next, we use our lab experiments to understand how VoIP performance metrics like delay and loss are affected by offered load on a link. From our initial experiments with faulty synthetic traffic generators, we find that even at low utilization, bursty network traffic can significantly degrade VoIP quality, and small timescale measurements, which are impractical with SNMP, are required to detect the problems. However, using realistic emulation of network traffic in the lab, we find that when network problems are severe and last for long periods of time, they can be easily detected using SNMP. We also present a case study of VoIP assessment data collected from a real network, where we again successfully used SNMP to detect the network links that caused poor quality