Browse Prior Art Database

Clock Distribution Algorithm for Network

IP.com Disclosure Number: IPCOM000099131D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 4 page(s) / 169K

Publishing Venue

IBM

Related People

Grover, GA: AUTHOR [+3]

Abstract

Disclosed is an algorithm to assign K alternate sources to each node in a network to synchronize all signals. The algorithm provides a loop-free network and finds a near optimal number of for synchronization.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 36% of the total text.

Clock Distribution Algorithm for Network

       Disclosed is an algorithm to assign K alternate sources to
each node in a network to synchronize all signals.  The algorithm
provides a loop-free network and finds a near optimal number of for
synchronization.

      One of the major problems in the design of a network of digital
switches and digital access cross switches (DACS) is synchronization.
 Digital signals be locked to a common clock to allow for their
identification.  Because the sources of these signals are often
separated by large distances, synchronization is a complex problem.
One of the most methods of synchronizing a network of digital and
facilities is the use of master clock(s) for the entire networks by
the use of a hierarchical network.  In this scheme one (or more, see
below) of the network is equipped with a master clock and information
is distributed hierarchically to other  The master clock passes
information to small number locations (or receivers).  These
receivers, in turn, act the source for one or more nodes lower in the
timing hierarchy. a sense, this hierarchy ensures that there is a
single source for a node.  This, in turn, ensures that there no loop
in the timing path.  This timing hierarchy is by establishing a tree
over the network which is at the node with master clock.

      The deficiency with a network with a single master clock its
vulnerability to failure.  A single failure will the timing network.
Therefore, one requirement is design a network which withstands K
failures (node and/or  To this end, network should have multiple
clock and each node should have one primary and, possibly secondary
sources of clock.  In assigning clocks nodes and providing primary
and secondary source of one should be careful not to create loop.

      The problem of synchronization (clock) network design is as
follows:

      Find the minimum number of clocks and their locations design
the synchronization network (hereinafter referred as the clock tree)
to withstand K nodes and/or failures. we will refer to K as the
'connectivity  (It is assumed by this algorithm that if a master
itself fails, the node with which it is associated may a backup
master clock, but only if this access occurs the network being
synchronized.) Placement Algorithm

      The basic idea behind the following algorithm is to nodes with
consecutive numbers such that nodes with numbers provide signal to
higher numbered neighbors. implicitly assigns direction to links and
prevents  It is also an objective to minimize the number of clocks
which are required to synchronize the network, in general, the
provision of a master clock source at node entails significant
expense.  This algorithm is in its requirement for clocks, although
not optimal.  With respect to these objectives, we the following
observations:
   1.   Nodes which have degree (number of links incident
        to them) k less then K (the connect...