(Joint work with A. Agrawala and S. Hawkins at the University of Maryland,
College Park)
A Cyclone network is a class of connection oriented synchronous communication
network that utilizes a cyclic approach to node resource management. Resources
are reserved for the duration of a cycle, a fixed length period
during which fixed size chunks of data are transmitted. Because
reservations specify both time (i.e. cycle number) and link (i.e. the
link from node i to node j), there is no run-time contention for resources
between different scheduled communication tasks. This allows the system
to provide deterministic (predictable) service levels, and results in
zero delay jitter, lossless data transmission, and efficient processing
of datagrams on every node of the transmission path. Nodes in a Cyclone
network (called cyclonodes) are controlled by clocks local to the
individual nodes. Because discrepancies among the local clocks can be
expected, and because Cyclone network protocols require tight temporal
coordination, clock synchronization is essential. For this purpose, each
cycle is divided into a transmission period of fixed (and global) duration
and an idle period of variable duration. The variability of the length
of the idle period is used to adjust the lengths of the cycles on individual
nodes, ensuring both relatively uniform cycle lengths and very low phase
discrepancies. It should also be noted that the algorithm presented here
does not technically achieve ``clock'' synchronization, but instead achieves
the necessary ``cycle'' synchronization. That is, the local clocks can,
over time, have widely varying time readings---the times they provide
are not in any way synchronized with ``global time'', and local clocks
do not adjust their time readings in any way. Rather, it is the cycle
start and end times, that remain synchronized. We have developed a lightweight
cycle synchronization algorithm for such networks, and have verified its
performance both via simulation and analysis. Initial analysis focuses
on an idealized model of the network, in which clock rates, link latencies,
discretization errors, and errors due to noisy transmission links are
ignore. Using this model, system behavior is described by a system of
difference equations which can be analyzed using Markov chain techniques,
since the key variable in the matrix equations turns out to be the transition
matrix for an ergodic Markov chain. I showed that cycle synchronization
properties are related to the convergence properties and rate of this
transition matrix. Our second stage model includes the error and noise
factors omitted in the base case, and thus provides a more realistic barometer
of system performance. Relying on methods from transform theory and function
theoretic operator theory, I showed that even in this case, cycles remain
synchronized within tolerable levels. Though theoretically satisfying,
the major impact of the algorithm is the potential for dramatically lowering
the synchronization costs of synchronous optical networks, both in terms
of the bandwidth required for synchronization protocols, and in terms
of hardware, as our algorithm eliminates the need for cesium clocks (or
near cesium accuracy clocks).
Douglas
C. Szajda, PhD
