Gradient clock synchronization

We introduce the distributed gradientclock synchronization problem. As in traditional distributed clock synchronization, we consider a network of nodes equipped with hardware clocks with bounded drift. Nodes compute logical clock values based on their hardware clocks and message exchanges, and the goal is to synchronize the nodes' logical clocks as closely as possible, while satisfying certain validity conditions. The new feature of gradient clock synchronization GCS for short) is to require that the skew between any two nodesy' logical clocks be bounded by a nondecreasing function of the uncertainty in message delay (call this the distance) between the two nodes, and other network parameters. That is, we require nearby nodes to be closely synchronized, and allow faraway nodes to be more loosely synchronized. We contrast GCS with traditional clock synchronization, and discuss several practical motivations for GCS, mostly arising in sensor and ad-hoc networks. Our main result is that the worst case clock skew between two nodes at distance d or less from each other is Ω(d + , where D is the diameter of the network. This means that clock synchronization is not a localproperty, in the sense that the clock skew between two nodes depends not only on the distance between the nodes, but also on the size of the network. Our lower bound implies, for example, that the TDMA protocol with a fixed slot granularity will fail as the network grows, even if the maximum degree of each node stays constant.     

Interval-based Clock Synchronization

In this paper, we develop and analyze a simple interval-based algorithm suitable for fault-tolerant external clock synchronization. Unlike usual internal synchronization approaches, our convergence function-based algorithm provides approximately synchronized clocks maintaining both precision and accuracy w.r.t. external time. This is accomplished by means of a time representation relying on intervals that capture external time, providing accuracy information encoded in interval lengths. The algorithm, which is generic w.r.t. the convergence function and relies on either instantaneous correction or continuous amortization for clock adjustment, is analyzed by utilizing a novel, interval-based framework for establishing worst-case precision and accuracy bounds subject to a fairly detailed system model. Apart from individual clock rate and transmission delay bounds, our system model incorporates non-standard features like clock granularity and broadcast latencies as well. Relying on a suitable notion of internal global time, our analysis unifies treatment of precision and accuracy, ending up in striking conceptual beauty and expressive power.     

Model Checking Weighted Integer Reset Timed Automata

Weighted timed automata (WTA), introduced in Alur et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 49–62, Springer, Berlin, 2001), Behrmann et al. (Proceedings of HSCC’01, LNCS, vol. 2034, pp. 147–161, Springer, Berlin, 2001) are an extension of Alur and Dill (Theor. Comput. Sci. 126(2):183–235, 1994) timed automata, a widely accepted formalism for the modelling and verification of real time systems. Weighted timed automata extend timed automata by allowing costs on the locations and edges. There has been a lot of interest Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006), Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008), Brihaye et al. (Proceedings of FORMATS/FTRTFT’04, LNCS, vol. 3253, pp. 277–292, Springer, Berlin, 2004), Brihaye et al. (Inf. Comput. 204(3):408–433, 2006) in studying the model checking problem of weighted timed automata. The properties of interest are written using logic weighted CTL (WCTL), an extension of CTL with costs. It has been shown Bouyer et al. (Log. Methods Comput. Sci. 4(2):9, 2008) that the problem of model checking WTAs with a single clock using WCTL with no external cost variables is decidable, while 3 clocks render the problem undecidable Bouyer et al. (Inf. Process. Lett. 98(5):188–194, 2006). The question of 2 clocks is open. In this paper, we introduce a subclass of weighted timed automata called weighted integer reset timed automata (WIRTA) and study the model checking problem. We give a clock reduction technique for WIRTA. Given a WIRTA A\mathcal{A} with n≥1 clocks, we show that a single clock WIRTA A￠\mathcal{A}' preserving the paths and costs of A\mathcal{A} can be obtained. This gives us the decidability of model checking WIRTA with n≥1 clocks and m≥1 costs using WCTL with no external cost variables. We then show that for a restricted version of WCTL with external cost variables, the model checking problem is undecidable for WIRTA with 3 stopwatch costs and 1 clock. Finally, we show that model checking WTA with 2 clocks and 1 stopwatch cost against WCTL with no external cost variables is undecidable, thereby answering a question that has remained long open.     

Secure and self-stabilizing clock synchronization in sensor networks

In sensor networks, correct clocks have arbitrary starting offsets and nondeterministic fluctuating skews. We consider an adversary that aims at tampering with the clock synchronization by intercepting messages, replaying intercepted messages (after the adversary’s choice of delay), and capturing nodes (i.e., revealing their secret keys and impersonating them). We present an efficient clock sampling algorithm which tolerates attacks by this adversary, collisions, a bounded amount of losses due to ambient noise, and a bounded number of captured nodes that can jam, intercept, and send fake messages. The algorithm is self-stabilizing, so if these bounds are temporarily violated, the system can efficiently stabilize back to a correct state. Using this clock sampling algorithm, we construct the first self-stabilizing algorithm for secure clock synchronization in sensor networks that is resilient to the aforementioned adversarial attacks.     

Adversarial Queueing Model for Continuous Network Dynamics

In this paper we initiate the generalization of the Adversarial Queueing Theory (aqt) model to capture the dynamics of continuous scenarios in which the usually assumed synchronicity of the evolution is not required anymore. We propose an asynchronous model, named continuous aqt (caqt), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. With respect to the standard aqt model, these new features turn out to be significant for the stability of packet scheduling policies that take them into account, but not so much for the stability of networks. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i.e., stable independently of the scheduling policies and traffic patterns used in it. Interestingly enough, this even holds for traffic patterns that make links to be fully loaded. Finally, it turns out that the set of universally stable networks remains the same as in the aqt model and, therefore, the property of universal stability of networks is decidable in polynomial time. Concerning packet scheduling policies, we show that the well-known lis, sis, ftgand nfsscheduling policies remain universally stable in the caqt model. We introduce other scheduling policies that, although being universally stable in the aqt model, they are unstable under the caqt model. This work was partially supported by eu IST-2004-15964 (aeolus), by the Spanish Ministry of Education and Science under cicyt tin2005-09198 (asce) and cicyt tin2005-25859-E, by the Regional Government of Madrid under contract No. 07T/0022/2003, and by the Universidad Rey Juan Carlos under project No. PPR-2004-42. Also partially supported by the Universidad de Chile (Mecesup fellowship and Anillo en Redes). A preliminary version of this work was presented in the 30th International Symposium on Mathematical Foundations of Computer Science (mfcs), Gdansk, Poland, LNCS, vol. 3618, pp. 144–155, Springer.     

Improved Competitive Guarantees for QoS Buffering

We consider a network providing Differentiated Services (DiffServ), which allow Internet Service Providers (ISPs) to offer different levels of Quality of Service (QoS) to different traffic streams. We study two types of buffering policies that are used in network switches supporting QoS. In the FIFO type, packets must be transmitted in the order they arrive. In the uniform bounded delay type, there is a maximal delay time associated with the switch and each packet must be transmitted within this time, or otherwise it is dropped. In both models the buffer space is limited, and packets are lost when the buffer overflows. Each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets. Our main contribution is an algorithm for the FIFO model with arbitrary packet values that for the first time achieves a competitive ratio better than 2, namely 2-ε for a constant ε gt; 0. We also describe an algorithm for the uniform bounded delay model which simulates our algorithm for the FIFO model, and show that it achieves the same competitive ratio.     

A synchronization algorithm for distributed multimedia environments

Network synchronization plays a significant role in transmitting multimedia objects over computer networks. Even packets from a single channel must be synchronized due to the problems in a packet switching environment, such as network jitter, frequency, and time offsets. We present an algorithm that determines the set of packets generated periodically by various participants arriving at a node. The basic advantage of the proposed algorithm is that the receiver estimates the reference times (expected arrival times of the packets) and achieves synchronization, without knowledge of the packet delays. The accuracy is improved and the complexity is reduced by predicting the time/frequency offsets between the clocks at the source and the mixer. The error is calculated by the Chernoff bound, demonstrated by simulation, and shown to be acceptable in practical applications.     

The accuracy of the clock synchronization achieved by TEMPO inBerkeley UNIX 4.3BSD

The authors discuss the upper and lower bounds on the accuracy of the time synchronization achieved by the algorithm implemented in TEMPO, the distributed service that synchronizes the clocks of the University of California, Berkeley, UNIX 4.3BSD systems. The accuracy is shown to be a function of the network transmission latency; it depends linearly upon the drift rate of the clocks and the interval between synchronizations. TEMPO keeps the clocks of the VAX computers in a local area network synchronized with an accuracy comparable to the resolution of single-machine clocks. Comparison with other clock synchronization algorithms shows that TEMPO, in an environment with no Byzantine faults, can achieve better synchronization at a lower cost     

Efficient distributed selection with bounded messages

We consider the problem of selecting the Kth smallest element of a set distributed among the sites of a communication network when the size of messages is bounded; that is, each message is a packet which contains at most c bits, where c⩾1 is a constant. A general selection algorithm using packets is presented and its packet complexity is analyzed. Its complexity is shown to be a significant improvement for a large range of packet sizes over the existing bounds. The proposed technique is then instanciated for specific classes of network topologies; the resulting bounds either match or improve the ones of existing solutions for a large range of values of the packet size. Furthermore, it is bit optimal in star networks     

Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graphs

We study digital clock synchronization for multiprocessor systems, where processors are triggered by a common clock pulse and communicate with others via shared memory.A self-stabilizing digital clock synchronization protocol for systems with a general communication graph is presented. The protocol can commence in an arbitrary non-consistent system state and converges to a legitimate state in which the clocks are synchronized and incremented by one in every subsequent pulse.To enhance the fault-tolerance of our protocol, we allow that during and following convergence processors may stop operating. Crash failures may partition the communication graph into several connected components. Our protocol synchronizes the clocks of the processors in every such connected component. For the case in which faulty processors can exhibit Byzantine behavior, we prove that there is no digital clock synchronization protocol that tolerates even one single faulty processor.     

Using integer clocks to verify clock-synchronization protocols

We use the Uppaal model checker for timed automata to verify the Timing-Sync time-synchronization protocol for sensor networks (TPSN), the clock-synchronization algorithm of Lenzen, Locher and Wattenhofer (LLW) for general distributed systems, and the clock-thread technique of the software monitoring with controllable overhead algorithm (SMCO). Clock-synchronization algorithms such as TPSN, LLW, and SMCO must be able to perform arithmetic on clock values to calculate clock drift and network propagation delays. They must also be able to read the value of a local clock and assign it to another local clock. Such operations are not directly supported by the theory of timed automata. To overcome this formal-modeling obstacle, we augment the Uppaal specification language with the integer clock-derived type. Integer clocks, which are essentially integer variables that are periodically incremented by a global pulse generator, greatly facilitate the encoding of the operations required to synchronize clocks as in the TPSN, LLW, and SMCO protocols. With these integer-clock-based models in hand, we use Uppaal to verify a number of key correctness properties, including network-wide time synchronization, bounded clock skew, bounded overhead skew, and absence of deadlock. We also use the Uppaal Tracer tool to illustrate how integer clocks can be used to capture clock drift and resynchronization during protocol execution.     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

Time-Constrained Scheduling of Weighted Packets on Trees and Meshes

Abstract. The time-constrained packet routing problem is to schedule a set of packets to be transmitted through a multinode network, where every packet has a source and a destination (as in traditional packet routing problems) as well as a release time and a deadline. The objective is to schedule the maximum number of packets subject to deadline constraints. This problem is studied in [1], where it is shown that the problem is NP-Complete even when the underlying topology is a linear array. Approximation algorithms are also provided in [1] for the linear array and the unidirectional ring for both the case where packets may be buffered in transit and the case where they may not be. In this paper we extend the results of [1] in two directions. First, we consider the more general network topologies of trees and two-dimensional meshes. Second, we associate with each packet a measure of utility, called a weight, and study the problem of maximizing the total weight of the packets that are scheduled subject to their timing constraints. For the bufferless case, we provide constant factor approximation algorithms for the time-constrained scheduling problem with weighted packets on trees and meshes. We also provide logarithmic approximations for the same problems in the buffered case. These results are complemented by new lower bounds, which demonstrate that we cannot hope to achieve the same results for general network topologies. For example, we show that if k packets are required to follow prescribed paths in an arbitrary graph, then unless NP = ZPP, there is no polynomial-time k ^1-ε -approximation, for any ε > 0 , to the optimal set of packets that can be scheduled.     

Effective Routing and Scheduling in Adversarial Queueing Networks

In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r)^-1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r)^-2); moreover, our result matches the traditional queueing-theoretic number-in-system bound.     

Testing distributed real-time systems in the presence of inaccurate clock synchronizations

This article deals with testing distributed real-time systems. More precisely, we propose: (1) a model for describing the specification of the implementation under test, (2) a distributed architecture of the test system (TS), (3) an approach for coordinating the testers which constitute the TS, and (4) a procedure for deriving automatically the test sequence of each tester from a global test sequence. In comparison with a very recent work, the proposed test method has the following important advantage: the clocks used by the different testers are not assumed perfectly synchronized. Rather, we assume more realistically that each clock is synchronized with a reference clock with a given (nonnull) inaccuracy. This advantage is very relevant if, for example, the testers communicate through the Internet.     

Bounds on maximum delay in networks with deflection routing

We consider the problem of finding the worst case packet transit delay in networks using deflection routing. Several classes of networks are studied, including many topologies for which deflection routing has been proposed or implemented (e.g., hypercube, Manhattan Street Network, shuffle-exchange network). We derive new upper bounds on the evacuation time of batch admissions, and present simple proofs for several existing bounds. Also derived are bounds on worst case transit delay for certain networks admitting packets continuously. To demonstrate the practical utility of our results, we compare a new delay bound to the maximum delay observed in simulations. The results have application in both protocol design and the determination of the required capacity of packet resequencing buffers     

Non-preemptive buffer management for latency sensitive packets

The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of \(\phi ^3 - {\varepsilon }\approx 4.236\), almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).     

Discrete-control correction A technique for the synchronization of digital communication networks

Discrete-control correction is a method of synchronizing the clocks of a digital communication network by means of periodic corrections to their frequencies, the correction to each clock being derived from the change in the buffer level at that node.

This paper presents a comprehensive treatment of this method and extends the results of earlier papers to more general situations. It is shown that there is a set of conditions, one for each node, which is sufficient to establish network synchronism. Explicit formulae are derived for the frequency of synchronism and the steady-state buffer levels.

It is shown also that the master—slave scheme of synchronization, in which the clocks of the network are synchronized to a designated master clock, is obtained as the special case of discrete-control correction in which corrections are made to all the clocks except the master clock.

It is pointed out that in the event of disruption of a part of the network, the surviving part or parts of the network are assured of regaining synchronism.     

Performance and stability bounds for dynamic networks

In this work, we study the impact of dynamically changing link capacities on the delay bounds of LIS (Longest-In-System) and SIS (Shortest-In-System) protocols on specific networks (that can be modelled as Directed Acyclic Graphs (DAGs)) and stability bounds of greedy contention–resolution protocols running on arbitrary networks under the Adversarial Queueing Theory. Especially, we consider the model of dynamic capacities  , where each link capacity may take on integer values from [1,C]$[1,C]$ with C>1$C>1$, under a (w,ρ)$(w,\rho )$-adversary. We show that the packet delay on DAGs for LIS is upper bounded by O(iwρC)$O(\mathit{iw}\rho C)$ and lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$ where i   is the level of a node in a DAG (the length of the longest path leading to node v$v$ when nodes are ordered by the topological order induced by the graph). In a similar way, we show that the performance of SIS on DAGs is lower bounded by Ω(iwρC)$\Omega (\mathit{iw}\rho C)$, while the existence of a polynomial upper bound for packet delay on DAGs when SIS is used for contention–resolution remains an open problem. We prove that every queueing network running a greedy contention–resolution protocol is stable for a rate not exceeding a particular stability threshold, depending on C and the length of the longest path in the network.