 |
Description  |
|
|
FIELD OF THE INVENTION
This invention relates to data processing systems and more particularly to
means for interconnecting a plurality of computers into a network wherein
each computer shares certain of its data sets in common with other
computers in the network and each node in the network can initiate or
receive the updating of shared data and resolve conflicts among nodes
competing to update the same data.
DESCRIPTION OF THE PRIOR ART
Networks of computers interconnected by a communication link are known. So,
too, is it known for a computer in a network to share data in common with
other computers in the network so that each computer may have rapid access
to frequently used data. In these prior art systems, a central
housekeeping facility was given the task of insuring that all the shared
data was current and supervising the updating of the data in the satellite
units.
The instant invention relies on the same principles of shared data, or
distributed multiple copies, to give efficient access to frequently used
data. It differs from prior art systems in that the control of updating is
distributed among the several computer nodes sharing the data. Therefore,
each node in the network can act as either a master or a slave in the
updating of a shared data set. Each unit, as to each respective shared
data set, has local stored information defining the priority of each node
so that it can resolve conflicts between itself and any other node, or
conflicts between two other nodes both competing to be the master of this
slave unit.
SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide means in a data
communication network, comprising a plurality of nodes, each of which has
associated therewith a computer storing sets of data in common with
predetermined ones of the computers associated with other nodes in the
network, for controlling the updating of the data sets shared by the
computers, and for resolving conflicts among a plurality of nodes
competing to update the same shared data set.
A further object of the invention is to provide means at each of the nodes
in a data communication network for storing the node location of each set
of data shared in common by a plurality of nodes, for manifesting the
priority each node has for updating each respective shared data set, and
for resolving conflicts between nodes seeking to update the same data set
in accordance with the stored priorities.
The foregoing and other objects, features, and advantages of the present
invention will be apparent from the following more particular description
of a preferred embodiment of the invention as illustrated in the
accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram illustrating the bulk deployment of the nodal
units.
FIG. 2 is a timing chart showing the progression of a message through the
update module.
FIG. 3 shows the relative positions of FIGS. 3A through 3Z when joined.
FIGS. 3A through 3Z show the detailed circuit diagram of the invention.
DESCRIPTION OF A PREFERRED EMBODIMENT
Overall Arrangement and Message Format
FIG. 1 shows the overall arrangement of the nodes in the data communication
network. In the illustrative embodiment, six nodes have been arbitrarily
chosen as representative of a system that can be expanded at will.
Each of the nodes includes an interface unit 1A through 1F, an update unit
2A through 2F, and a computer 3A through 3F. A separate communication link
4A through 4F connects the interface unit at each node to the interface
unit in the next succeeding node to form a closed loop network. Each
communication link in the preferred embodiment consists of four wires, as
messages are transmitted parallel by bit serially by character. The
communication link could also be a radio link, optical link, and could
employ any one of the conventional communication expedients for
discriminating between bits and characters.
Any node has the capability of inserting a message into the line leading
from the node or absorbing a message from the line leading into the node.
Actually, all messages coming into a node enter the interface unit and are
either absorbed from there into the update unit or pass out of the
interface unit to the outgoing line. Thus, a message can conceivably
circulate through several trips around the loop until a node is prepared
to receive it.
All messages are initiated within the update unit and are inserted into the
interface unit and the outgoing line when a blank message slot is found on
the line. Therefore, before going into any further details of the node
structure, it is expedient to pause and explain the message format.
Each message consists of eight four-bit characters transmitted parallel by
bit, serially by character. Each message is structured as follows:
______________________________________
Character Description
______________________________________
C1 Beginning of Message = 1111
C2 Destination (0000 = blank message)
C3 Command
C4 Address of Sender (1 to 6 in Binary)
C5 Data Set No.
C6 Data Address (Address of Byte)
C7 First 4 bits of data)
C8 Second 4 bits of data) .sup..sup.= 1 byte
______________________________________
A complete data set consists of 16 bytes of eight bits each. Updating of a
complete data set thus requires sixteen messages plus four for each node
to be addressed. Thus, for example, if node A were to command nodes B and
C to update a complete data set, node A would transmit eighteen messages
to node B and node B would return two messages to node A for a total of
twenty messages. A like number of messages would be interchanged between
nodes A and C for a total of forty for the whole transaction between the
nodes.
Returning now to the message format, the beginning of message character
(1111) is detected by a node and starts an operation synchronized with the
eight character message so that only the first character can be detected
as having all ones. This allows the character 1111 to be used in
subsequent character, or data, positions in the message.
The destination code is merely the number (1 to 6 in the illustrative
embodiment) of the node to which the message is addressed. If the
destination code 0000 follows the beginning of the message character, the
message slot is delineated as a blank message. Any characters following a
0000 are in effect "garbage" characters, in that they have no message
significance. It is expedient to leave them in and use the 0000 as a
signal that they should be ignored. When a message is absorbed by a node,
it inserts 0000 in the destination position. Even though it absorbs a
message (enters it into its own registers), it leaves the characters C3
through C8 in the message.
The destination code signals a node whether the message is "mine" or "not
mine," or, if 0000, that it can insert a message on line if it has one
waiting. Thus, the message is so structured that it first alerts a node
that a message is beginning, followed by the destination code which
manifests an empty message slot, or whether the message should be absorbed
or passed on by the node. If the destination code is compatible with the
node, the next following command code instructs the node as to wishes of
the initiating node.
There are five commands:
a. SP = send prepare. This is sent by the master node and instructs the
addressed slave node to prepare for an update.
b. AP = acknowledge prepare. This is returned by a slave node to the master
node in response to an "SP" command addressed to it.
c. SU = send update. This is sent by the master node to each data-sharing
slave node after it has received AP acknowledgements from all prior
addressed nodes.
d. AU = acknowledge update. This is sent by each slave node to the master
node in response to an SU command addressed to it.
e. SX = send execute. This is sent to each slave node along with the data
byte to be corrected. There is no acknowledgement for this command.
Following the command character in the message is the address of the
sender. This is a four-bit number from one to six (in the illustrative
embodiment) signifying the number of the node initiating the command or
returning the acknowledgement. It is used in testing for relative
priorities to resolve conflicts and to check off the returns of
acknowledgements in the master node.
The next following character, the data set number, is the number which
identifies the 16 bytes of data, constituting the data set, which is to be
updated, either in whole or in part. The data set number and the next
following data address identify the specific byte of data to be updated.
If a whole data set is to be updated, the first data address transmitted
is 16 (1111) followed separately by 15 (1110), etc. These data addresses
are only sequentially decremented for successive SX commands. The prior
commands and acknowledgements thereto use the set number to determine
priorities.
The last two characters are actually the 8 bits of data (a byte)
corresponding to the data address immediately preceding. If, for example,
byte 5 of a given data set required updating, bytes 5, 4, 3, 2, and 1
would be transmitted even though no change in the bytes 4, 3, 2, and 1
would be effected. This is the result of the machine structure and the
decrementing of the byte addresses.
Returning now to FIG. 1 and the broad system arrangement, cursory
examination reveals that each node has an incoming and an outgoing
communication line. Thus, every message on the line passes through the
interface module of each node. The interface unit consists of seven 4-bit
registers through which the successive characters are shifted in the
manner of a shift register. A local timing pulse generator in the
interface unit synchronizes the shift of the message and provides control
signals to the update unit to identify the location of each character as
it progresses through the successive shift registers. While the message is
in the interface unit, the destination is analyzed by the update machine
for "blank message," "my address," or "not my address." The update machine
can then, (a) insert a message if the destination is 0000, or (b) absorb
the message and insert 0000 in the destination if it is "my address," or
(c) do nothing if it is "not my address." The absorption or insertion of
messages is synchronized with the shift of characters through the
interface unit.
The update machine will not now be described in detail. It consists
essentially of registers for receiving the message from the interface
unit, registers to store update information from its computer, registers
to store a message intended for insertion on the line, a control word
memory, logic for analyzing and selecting the sub-routines applicable to
the detected situation, sub-routine timing means, and controls for
processing the incoming and outgoing messages.
In the update machine, there are three basic routines and ten sub-routines.
These will be described in detail in the detailed explanation of FIGS. 3A
through 3Z.
The basic routines are:
a. OA = overall routine. This routine controls the update machine during
its dormant or waiting period. It is operative to condition the machine to
listen for a message or to listen for zeros.
b. RM = receive message. This is operative to control the update machine to
absorb a message from the line.
c. TM = transmit message. This routine is operative to control the
insertion of a message into the line when a blank message is detected.
The ten sub-routines employed by the update machine are:
a. SP = send prepare. This sub-routine controls the master update machine
in the preparation of all of the SP commands to the slave nodes.
b. SP1 = send prepare after conflict. This subroutine is initiated at a
node if it has received an SP command and has an update of its own with a
higher priority.
c. P0 = prepare. This sub-routine is activated in a slave unit upon receipt
of the first received SP command for a given data set to prepare an AP
acknowledgement.
d. P1 = prepare upon conflict. This sub-routine is activated in a slave
unit upon receipt of a second SP command for a given set of data to
determine the relative priorities and return an AP acknowledgement only if
the second command has a higher priority than the first.
e. AP1 = acknowledge prepare. This sub-routine is active at a master node
to check off the AP acknowledgement received from the slave nodes.
f. SU = request to update. This sub-routine is active at a master node to
prepare SU commands for transmission to all data-sharing slave nodes only
if all nodes have responded with an AP acknowledgement.
g. U1 = receive update. This sub-routine is employed by a slave node in
response to an SU command to prepare the AU acknowledgement for
transmission.
h. AU2 = acknowledge update. This sub-routine is used by the master node in
response to the receipt of an AU acknowledgement to check off the
responses and to initiate an SX routine.
i. SX = send execute change. This sub-routine is used by the master node to
prepare updates for each successive byte and each slave node.
j. X2 = receive execute. This sub-routine is used by each slave node to
receive the SX command and associated data and enter it into the computer
at the slave node.
The selection of eight of the sub-routines by the update module is effected
by a so-called AND matrix. This matrix AND's the various combinations of
node states with the commands. Each node has three states; 0, 1, and 2. A
dormant node resides in the 0 state. The 1 and 2 states are set as
follows:
1 state -- Set in a master node as part of the send prepare sub-routine.
Set in a slave unit in response to reception of the first received SP
command.
2 State -- Set in a master node as part of the request to update (SU)
sub-routine. Set in a slave node in response to a received SU command as
part of the U1 sub-routine.
The eight sub-routines which are called into action by the AND matrix as
follows:
State 0 and SP Command at Master Node = SP sub-routine
State 1 and SP Command at Master Node = SP1 sub-routine
State 2 and SP Command at Master Node = No operation
State 0 and Received SP Command at Slave Node = P0 sub-routine
State 1 and Received SP Command at Slave Node = P1 sub-routine
State 2 and Received SP Command at Slave Node = No operation
State 0 and Received AP Acknowledgement at Master Node = No operation
State 1 and Received AP Acknowledgement at Master Node = AP1 sub-routine
State 2 and Received AP Acknowledgement at Master Node = No operation
State 0 and Received SU Command at Slave Node = No operation
State 1 and Received SU Command at Slave Node = U1 sub-routine
State 2 and Received SU Command at Slave Node = No operation
State 0 and Received AU acknowledgement at Master Node = No operation
State 1 and Received AU Acknowledgement at Master Node = No operation
State 2 and Received AU Acknowledgement at Master Node = AU2 sub-routine
State 0 and Received SX Command at Slave Node = No operation
State 1 and Received SX Command at Slave Node = No operation
State 2 and Received SX Command at Slave Node = X2 sub-routine
The two remaining sub-routines SU (send update) and SX (send execute) are
initiated upon completion of the checkoff of the acknowledgements returned
to the master node.
A node in the 0 state is susceptible to any type of operation.
Message Progression Through the Interface
Every incoming message starts with a beginning of message character
consisting of four ones, immediately followed by a destination code
consisting of four zeros if it be a blank message, or one of the remaining
fifteen combinations of four bits, including all ones if it is addressed
to a node. Since in this illustrative embodiment there are only six nodes,
the destination code will not exceed 0110.
The message is clocked through the interface by a clock pulse generator and
the position of each of the eight characters which constitute the message
is tracked through the interface by a counter which is stepped by the
clock pulse generator.
The progression and tracking of the message characters through the
transmission line interface is invariable even though in some instances
the incoming message from the line is put back on the line without
alteration and in other cases the incoming message is absorbed and a blank
message substituted therefor. In both cases, the all ones "beginning of
message" character proceeds without change. Also, in both cases all of the
following characters retain their relative positions in the message,
whether or not the coded representation thereof is unchanged or changed.
Thus, some destination character (including all zeros) will invariably
follow the beginning of message character. The remaining six characters
will also follow, either unchanged or changed.
Turning now to FIG. 3A, any message appearing on lines 100 is applied to
gates 102 and 116. If a beginning of message character C1 (all ones) is
present, AND gate 102 is activated to produce a P0 timing pulse on line
104. In fact, any all ones character will produce an output on line 104.
However, AND gate 782 is only activated once for each message cycle
because flip-flop 780 is set to the one state at the end of the preceding
message and reset immediately upon recognition of the next following
beginning of message character.
With flip-flop 780 set, AND gate 782 will pass the P0 pulse generated by
character C1 to OR gate 106 and line 108 which leads to three sets of four
gates each connecting the outputs of registers 1A, 2A, and 3A,
respectively, to the inputs of registers 2, 3 and 4 to effect the
respective shift of the characters therebetween. The P0 pulse is generated
only once during each message cycle. However, another pulse P1 having the
same timing will be repeated for each subsequent character. For ease of
reference, the P0 pulse can be considered as the pulse on line 126, and P1
as the pulse appearing on lines 132, 134, and 108. The P1 pulse will
effect the inter-register shift of characters.
The P0 pulse, appearing on line 126 also resets the character counter 124
to all zeros. Thus, upon the initial recognition of the beginning of
message character, the time reference P0, T0 starts, wherein P0 is the
pulse time and T0 is the character count. At this time, none of the new
message has been entered into the system.
The P0 pulse on line 126 enters OR gate 110 and delay 112, the delayed
output of which constitutes pulse time P2. The sole function of P2 is to
gate the characters from line 100 by means of the P2 pulse on line 114
which opens gate 116 to pass the line bits to the four OR gates connected
to the one or set side of the four flip-flops constituting register 1. It
is to be noted that there are only four incoming lines. Therefore, zeros
and ones are manifested by no potential or some potential on the lines.
Pulse P1 also resets register 1 to zeros through the OR gates connected to
zero inputs of the flip-flops.
Other inputs, as for example from cables 207 or 169, consist of four pairs
of signals. No resets are required for these entries, nor for any other
entries into the other registers. All registers except register 4 have
true and complementary outputs.
The P2 pulse appearing on line 114 operates delay 118 to produce a P3 pulse
on line 120. This P3 pulse operates to shift characters from register 1 to
register 1A, from register 2 to register 2A, from register 3 to register
3A, and from register 4 back to the lines. Pulse P3 on line 120 opens the
four gates preceding registers 1A, 2A, and 3A and the gate preceding the
line drivers to effect the character shift.
Pulse P3 also feeds logic circuitry in the update section to gate
characters into and out of registers 1, 2, 3, and 4 (in only) at this
time. This permits the extraction and insertion of characters from and
into the shift register system at the appropriate time, working in
conjunction with the character counter 124.
Before proceeding with the incrementing of the character counter 124, it is
expedient to explain the generation of the P1, P2, and P3 pulses following
the initial P0 pulse.
The P0 pulse, since it appears only once for each message cycle, must
initiate a chain of timing pulses. The P0 pulse on line 126 activates
delay 128 to produce a P2.sub.o pulse which through OR 130 fires single
shot 122. This single shot provides the subsequent P1 pulses, being
repetitively fired by the regenerative circuit through delay 150, AND 148,
and OR 130. The AND gate 148 remains open for all counts of counter less
than the maximum count, as manifested by a potential on line 144. Inverter
146 provides a constant potential on all counts except the final count.
Single shot 122 produces its repetitive P1 pulse, which, through OR 106,
resets register 1 and gates the contents of the A registers into the
respective next sequential registers as hereinabove described with respect
to the P0 pulse. The P1 pulse on line 132 also through OR 110 activates
delay 112 to provide the P2 pulse. The same P1 pulse on line 134 resets
flip-flop 780 to deactivate AND 782 to nullify the effect of any
characters after the first, also consisting of all ones. This permits use
of the full spectrum of the four bits in all subsequent characters.
Finally, the P1 pulse on line 134 increments the counter 124 upon each
occurrence thereof, the counter having been reset as above described by
the P0 pulse.
Counter 124 and its decoder 136 (binary to one-out-of-sixteen) keeps track
of the progress of the message characters through the sequential shift
registers. Initially, as described, this counter is reset by the P0 pulse
upon detection of the all ones beginning of message character C1 in AND
102. If this reset is referred to as T0 time, the C1 character is entered
into register 1 at T0, P2 time. Subsequent entries of message characters
occur in accordance with the chart shown in FIG. 2, wherein C1 through C8
are the eight message characters, T0 through T12 are the times delineated
by counter 124, and P1 through P3 are the timing pulses produced by the
single shot 122 and associated delay circuitry.
Examination of FIG. 2 will reveal that C1 progresses through the shift
registers and is read out to the line at T3-P3 time. Each succeeding
character follows sequentially until C8 is entered into the line at T10-P3
time. Thus, the count in counter 124 must include at least ten counts to
shift a complete message through the transmission line interface shift
registers. However, to provide an intermessage blank space on the line,
the count on line 144 is arbitrarily chosen as thirteen.
When the count in counter 124 achieves thirteen, decoder 136 energizes line
144, which, through inverter 146, deactivates AND 148 to stop the
regeneration of the "P" pulses. Potentialization of line 144 also sets
flip-flop 780 to energize AND 782 making it susceptible to passing the
potential produced by the next following all ones beginning of message
character. Since the line is initially filled with messages, the interface
unit will always be active to receive and reinsert messages from and to
the line, whether or not they be blank messages or valid messages.
It is to be noted that the counter 124 keeps track of each character as it
progresses through the shift registers. Thus, if a character is to be
extracted or inserted, it must be gated out of or into the appropriate
register at the proper time. The chart in FIG. 2 will be of assistance in
understanding this gating.
Except for the detection of the destination character (C2) and the
insertion of a blank message character by inserting all zeros in the
destination slot, all characters are entered or extracted at either T4 or
T7 times.
At T4 the following registers contain the following characters:
______________________________________
Register 1
C5 (Set Number)
Register 2
C4 (Sender)
Register 3
C3 (Command)
Register 4
C2 (Destination)
At T7 the characters are disposed as follows:
Register 1
C8 (Byte Data)
Register 2
C7 (Byte Data)
Register 3
C6 (Data Address)
Register 4
C5 (Not Gated - See T4 supra)
______________________________________
The destination address is detected in register 1 at T1 time. A blank
message character (C2) is inserted into register 2 at T2 time. A new valid
destination number is inserted in register 4 at T4 time.
Operation Upon Characters in Interface
The first operation upon any incoming message is to test the destination
character to determine if the message is (a) blank (binary zero), (b)
destined for another node, or (c) destined for this node. If the message
slot is blank (all zeros in C2), then two operations are possible, (a)
pass it on, or (b) insert a locally generated message in its place. If the
message is addressed to another node, it must be passed on without change.
If the message is addressed to this node, it will be absorbed if the node
is not otherwise occupied. If so, the message will be left in the line for
another time.
The first order of business, therefore, is to test C2 at the earliest
opportunity following detection of a C1 character. As explained, C2 is in
register 1 at T1 time. Therefore, when line 138 (FIG. 3B) manifests a T1
time, AND 152 receives a P3 pulse from line 120 to open gate 156 to
introduce the C2 character into cable 158 which joins cable 220 and exits
as cable 158 on FIG. 3E. There it enters register 396 and decoder 398 to
produce one of three outputs, all zeros, "not my address," or "my
address." If register 396 is a four-bit register, then decoder 398 would
include a four input AND gate with zero inputs from the register. The "my
address" line would be the output of a second 4-input AND gate having zero
and one inputs corresponding to the node number. Node five, for example,
would have hard-wired inputs of 0101 to the AND gate. The "not my address"
would be the inverse thereof.
Thus, at T1 and P3 time of the interface, the nature of the message will be
partially determined. However, the update machine has its own timing
controls which must be coordinated with the message progression timing.
Therefore, the update machine has a series of sets of timing pulse
generators which are selectively activated upon the determination of need.
These are analogous to the micro-programs in general purpose computers.
In the first example, it will be assumed that the local update machine has
no reason to generate and transmit any message. Therefore, it has no
reason to look for a blank message slot. Its sole function is to look for
a destination address intended for it. Derivatively, if it finds a message
"not for me," it must avoid interfering with it and allow it to proceed
through the interface.
When gate 156 is opened at T1 and P3 time to gate C2 to the destination
address register 396 for test, it also gates the P3 pulse on wire 120 to
wire 160 and, via cable 400, to FIG. 3S where, if the "listen for message"
latch 370 is set (as in fact is is), AND 394 will be active to pass the P3
pulse on wire 160 to fire single shot 402 to produce an RM-1 pulse in
cable 358.
The RM-1 pulse reappears on FIG. 3E to open gate 404 to gate the "not my
address" or "my address" signals to lines 242 and 244, respectively. The
"not my address" signal on line 242 proceeds via cable 362 to FIG. 3S and
OR 406 to reset the "listen for message" latch 370. It also is connected
to OR 408 (FIG. 3U) to fire single shot 354 to produce the OA-1 pulse.
The OA-1 pulse feeds through cable 358 to FIG. 3E and gate 360 to test
computer latch 342. Since, in the example chosen, the computer requires no
service, latch 342 will be reset, thus gating a potential to line 252 and
thence to FIG. 3V and OR 368, the output of which fires single shot 366 to
produce an OA-5 pulse, which pulse sets the "listen for message" latch 370
on FIG. 3U. The destination register 396 will retain the destination until
a new entry is made. However, the valid message signal on line 160 appears
only at T1-P3. The TM-1 pulse will not be produced a second time. Even if
it were, it would only produce several operations of the circuitry just
traced.
The update machine, in the absence of a computer request, will dwell
awaiting the next occurring entry of a new destination address into
register 396 to start another test sub-cycle. This allows the "not my
address" message to shift through the interface under control of the P1,
P2, and P3 shift pulses produced therein. No extraction or introduction of
characters will be effected. The C2 character read out of register 1 at
T1-P3 time will be shifted into register 1A at the same time and proceed
absorb"be shifted in synchronism with the other characters in accordance
with the timing shown in FIG. 2.
Returning now to the second possibility of a message intended for this
node, with no local request for service, the destination address in
register 396 (FIG. 3E), through decoder 398, will yield a "my address"
signal. The T1-P3 pulse on line 160 will be passed by AND 394 (FIG. 3S) to
fire single shot 402 to produce the RM-1 pulse as heretofore explained,
the "listen for message" latch having been set at OA-5. The RM-1 pulse
will now produce a "my address" signal on line 244. This will initiate a
"message absorb" operation.
The "my address" signal on line 344 exits from the cable 362 on FIG. 3T to
fire single shot 410 (FIG. 3S) to produce the RM-2 pulse, which, via cable
358, sets the "message absorb" latch 412 adjacent to the single shot. The
one state of latch 412 potentializes line 162 in cable 358, which line
exits from the extension cable 426 on FIG. 3E in three places. The first
exit potentializes AND 172 (FIG. 3B) which has further inputs of character
count T4 and timing pulse P3. At this time, as shown in FIG. 2, the
disposition of the characters in the registers is as follows:
C5 (data set number) is in register 1
C4 (sender number) is in register 2
C3 (command) is in register 3
These are now entered into the update machine. The output of AND 172 at T4,
P3 and the duration of latch 412 opens gates 176 (for register 1), 178
(for register 2) and 180 (for register 3) to gate the outputs of these
registers as follows:
Register 1 to cable 182
Re | | |
