 |
Description  |
|
|
Introduction
This invention relates to a network system for providing communication
among a plurality of separate units and, more particularly, to a network
in which control of such communication resides in a central control unit,
the network being capable of reconfiguration on a periodic basis and
adaptable to maintain effective communication in the face of faults which
may occur therein.
Background of the Invention
In the design of systems which provide communicating interconnections
between one or more central control units and a plurality of remote units,
it is desirable to provide a high degree of reliability at a reasonable
cost. Reliability is a particular problem where such interconnections are
subject to partial physical damage as, for example, by the collapse of
support structures therefor due to fire, battle damage in combat
situations, or any other common physical phenomena. Such system may
include, for example, a central data processing complex and a plurality of
remote units which may be other computer units or input/output peripheral
units.
While a central processing complex often can be protected against massive
physical damage by placing such a unit in a well structured, or well
armored, location, the protection of the remote units of an overall system
cannot be readily protected in many practical situations, particularly
where the system is spread over a relatively large area. Further, the
remote units may be in locations which are easily subject to damage, such
as in aircraft systems where portions of the system must be located, for
example, in the wings of the aircraft.
While the dispersion of units over a larger area offers some protection in
itself, inasmuch as physical damage is unlikely to destroy the entire
system all at once, the system may often be subjected to more limited, but
nevertheless severe, forms of damage wherein certain units of the system
either are destroyed themselves or become effectively isolated from the
rest of the system by the destruction of the communications links with
other portions thereof.
It is desirable, therefore, that the installation of an overall system,
which may include a large number of remote units requiring communication
both with a central processing unit and with each other, should be
arranged so that the protection of the overall system can be as closely
comparable as possible to the protection that can be provided for the
central processing unit thereof, taking into account the cost, the weight
and the size of the system and the units which are utilized therein.
Description of the Prior Art
Two approaches have generally been used in arranging an overall
communication system to provide interconnections between a central
processor complex and a plurality of remote devices. One such approach
involves the use of dedicated, or fixed, wiring from the central unit to
each of the remote devices. In systems where a large number of remote
units are involved an enormous amount of the total weight and bulk of the
system must be devoted to the wire itself and, moreover, the central
processor complex must contain relatively complicated interface circuitry
for the many wires which terminate there. The material and installation
costs of such a system can become extremely large and in many cases the
large number of remote devices that are used requires so much wiring that
insufficient physical space is available therefor. Further, if the
communicating link furnished by the dedicated wiring between a particular
remote unit and the central processing complex is damaged, the remote unit
becomes completely isolated even though it may remain undamaged in itself.
In order to overcome the cost and space problems associated with dedicated
wiring systems, most modern computer control systems have resorted to the
use of appropriate bus structures. Thus, for example, a single processor
interface can be arranged to handle a time-multiplexed data bus to which
all of the remote devices of the system are connected. The cost of wiring
and the cost of the interface circuitry is effectively reduced to the cost
of the single data bus and its central interface circuitry together with
appropriate and relatively standardized interface circuitry at each of the
remote devices. A bus system provides greater flexibility and
expandibility than a dedicated wiring system in that the number of remote
units can be readily increased by attaching the additional units on to the
main bus at convenient points. No changes to the main frame wiring or to
the interface at the central complex are thereby required and minimal
adjustments to the bus routing are needed, particularly if the bus already
passes near the newly added remote device.
Unfortunately, however, bus systems give rise to disadvantages in
applications where damage to the system might occur. Thus, damage to the
bus anywhere along its length generally disables the entire system and
even the most minor of mishaps can reduce the system to inoperability.
Such extreme vulnerability makes the use of bus systems undesirable if any
reasonable degree of fault-tolerance is required.
Summary of the Invention
In order to overcome the problems associated with dedicated wire and bus
systems, the invention utilizes a network configuration in which
substantially all control of the communications between a central
processing complex and a plurality of remote units, as well as
communications among the remote units themselves, resides in the central
processing unit. The network comprises a plurality of nodes and
appropriate linking paths, i.e., communication links, between the nodes,
and a central control unit connected to a selected number of the nodes.
Each node can be used to service a single remote device or a small group
of remote devices. Each of the nodes has at least two terminals, each
connected to a linking path, with a selected number of nodes having at
least three terminals, each connected to a linking path, so that an
appropriate network configuration can be provided. Each node terminal is
capable of being placed in a selected status for use as an input terminal,
an output terminal, or an inactive terminal. For the purposes of this
description the inboard side of an active linking path is defined as the
end of the linking path which is nearest to the central control unit while
an outboard side thereof is defined as the end thereof which is furthest
from the central control unit.
The system includes means for appropriately activating a selected number of
the linking paths which are provided between the nodes and between certain
of the nodes and the central control unit, and for selectively assigning a
suitable status to the terminal of each node so as to provide a network
configuration in which each node unit is in communication with the central
control unit through a unique route which includes one, or more, of the
activated linking paths. The system can be further arranged to permit a
change in the active network configuration by revising the assignment of
activated linking paths and by appropriately reassigning the status of
each node terminal. The system may be so arranged to reconfigure the
network many times over a predetermined time period so that each linking
path is activated at least once over such time period.
In accordance therewith, the overall network system thereby provides a
reliable means for interconnecting the remote units with each other and
with a central processor complex. Further, all of the decision-making is
arranged to be performed at the central control unit with no
decision-making required at any of the individual node units themselves.
The information which is being sent from the central processor unit to the
remote units, from a particular remote unit to the central unit, or from
one remote unit to another, can be sent in serial form so that there is no
need for any buffer storage capability at the node units. The node unit
construction is thereby made relatively simple and inexpensive. Further,
the system is readily adaptable to the incorporation of appropriate
redundancy techniques in order to increase the reliability and to provide
for error detection. Replicated redundancy is particularly suitable for
use in the system of the invention due to its high degree of modularity
and the potential economy which is possible in matching large scale
integrated circuit technology thereto.
Description of the Invention
The invention can be described with more particularity with the assistance
of the accompanying drawings wherein
FIG. 1 depicts in diagrammatic form a network in accordance with the
invention;
FIG. 2 depicts diagrammatically the relationship among the redundant
circuits of a node unit of the network of FIG. 1;
FIG. 3 depicts in more detailed form a portion of an exemplary node unit of
the network of FIG. 1;
FIG. 4 depicts a more detailed block diagram of the control logic of an
exemplary node unit of the network of FIG. 1;
FIG. 5 depicts the logic circuitry of the receiver control logic of FIG. 4;
FIG. 6 depicts the logic circuitry of the discriminator control logic of
FIG. 4;
FIG. 7 depicts the logic circuitry of the conductivity control logic of
FIG. 4;
FIG. 8 depicts the logic circuitry of the transmit control logic of FIG. 4;
FIG. 9 depicts the logic circuitry of the monitor unit of FIG. 3;
FIG. 10 depicts exemplary interface connections at the input/output (I/O)
bus of the central processor complex of the network of FIG. 1;
FIG. 11 depicts a flow chart of a basic GROW routine for organizing an
uninitialized network into a functioning network system in accordance with
the invention;
FIG. 12 depicts a flow chart of a basic VERIFY routine for determining the
status of active links of a network system in accordance with the
invention; and
FIGS. 13-18 depict a flow chart of a basic MODIFY routine for reconfiguring
a network system in accordance with the invention.
FIG. 1 depicts in relatively simplified form an exemplary network in
accordance with the principles of the invention. As can be seen therein
the network includes a central processor complex 10 and a plurality of
remote units 11 which may be computer units or appropriate input/output
devices, for example. Each of the remote units is appropriately connected
to a single node unit 12, the purpose of which is described in more detail
below.
A plurality of linking paths 13 interconnect the node units 12 and,
further, interconnect a selected number of node units with the central
unit 10. In the particular network configuration of FIG. 1, a selected
number of such links, designated as links 13A, are placed in an active
status, as shown by the solid lines, as explained more fully below, and a
selected number thereof, designated as 13B, are placed in an inactive
status, as shown by the dashed lines. Each active linking path 13 can be
thought of as having an inboard side and an outboard side. Identification
of the inboard and outboard sides of a particular active link can be made
as follows. If a return path of active links is traced from the link in
question to the central processor complex, the side of the link in
question which is nearest the central processor complex along such return
path is defined as the inboard side and the side of the link in question
which is furthest therefrom is defined as the outboard side. In the figure
an outboard side of a link is indicated by an arrowhead in order to
distinguish it from the inboard side thereof. Inactive links are not
provided with any specific orientation and the orientation of the inboard
and outboard sides of a link are determined by the overall network
assignment which is controlled by the central processing complex unit.
Each node 12 can be defined as having an inboard terminal which, for the
purposes of this description, is defined as a terminal connected to the
outboard side of an active link, and a variable number of outboard
terminals which are defined as terminals connected to the inboard side of
an active link. Terminals of each node unit 12 which are assigned neither
an inboard nor an outboard status are said to be inactive (or null)
terminals and are connected to inactive links. The assignment of the
status of any particular terminal is controlled by the central processing
unit 10 via control logic and such assignments may change if the overall
network is reconfigured.
In the network as shown, a specific configuration has been selected by the
central processor control unit 10 so that active and inactive links are
appropriately defined as shown as well as the inboard and outboard sides
thereof. Data communication is achieved exclusively from the central
processor complex 10 to each of the remote nodes 12 and from the remote
nodes to the central processor. There is no direct data communication path
from one remote unit to another since all data communication therebetween
must pass through the central processor control complex unit 10.
Information from the processor is effectively broadcast on all active
links leaving the processor and travels through the active links of the
overall network to all nodes thereof. Thus, the direction of data
information flow from the central unit 10 can be traced along the active
links in the direction of the arrowhead so that all nodes 12 are
ultimately reached thereby.
Messages from a remote unit are routed back to the processor from the node
associated therewith along a single unique path which can be traced from a
specific remote node 12 along one linking path in a direction against the
arrowheads until the processor is reached. For example, a unique path is
shown from the lowermost node unit of FIG. 1, designated as node 12',
along a first linking path 13' to a second node unit 12" and thence along
a linking path 13" to node 12'" and thence along linking path 13'" to the
central unit 10.
Data from the central processor unit is transmitted serially, on a
bit-by-bit basis, and need not be buffered or stored in any way at any
intermediate point of the network, such as at any of the node units 12. As
mentioned above, each of the linking paths 13 is assigned an active or
inactive status and each of the terminals of nodes 12 has an inboard or an
outboard status depending on which end of an active link it is connected
to. Terminals which are connected to inactive links are likewise inactive.
The assignments may be changed under the control of the central processor
unit 10 to reconfigure the active network. In any one configuration a node
unit 12 has only a single inboard terminal which is the terminal from
which data information from the central unit 10 is received. Such data
information is relayed on a bit-by-bit basis to all of the outboard
terminals of the node for re-transmission on the active links connected
thereto. No data information is relayed on any of the inactive links from
the inactive terminals of the node units.
In the operation of the network in a reverse direction, i.e., where data
information from a remote unit is to be relayed to the central unit 10 for
use thereby or from re-transmission to another remote unit, such
information from the outboard terminals of the node unit are ORed together
and re-transmitted out the inboard terminal of the node unit. Since only
one remote unit is transmitting at any one time, the ORing of such data
information from incoming data paths can be accomplished without problem.
Inactive terminals of a node unit normally do not receive or transmit any
data information. All of the nodes and all of the linking paths of the
network are fully duplexed, that is, each may handle data transmitted in
both directions simultaneously.
The central processor complex unit 10 directly controls the conductivity of
a particular node unit by sending control commands thereto over the
network. Most of the node unit control command, such as a command to
change the status of a node terminal from an inactive status, for example,
to an outboard status are received by a node unit at its inboard terminal
and processed by the node control portion of each node unit as described
in more detail below. An exception to such a control command path is
provided in the case of a command which is required to establish a new
inboard terminal for a node unit. Such latter command does not normally
arrive at the then current inboard terminal but rather arrives at the
designated future inboard terminal, as described in more detail below.
An appropriate circuit at the node unit monitors the incoming command
information and performs the appropriate function for each node control
unit upon the detection of the command which is so received. Unlike the
normal node unit commands, the specialized command discussed above for
setting up a new inboard terminal is appropriately encoded so as to
minimize the possibility of an erroneous triggering of the command
decoding circuitry which circuitry might be exposed to random data from
failed portions of the overall network.
The network provides fault tolerance effectively at two levels, which can
be defined as the "macro" level and the "micro" level. The macro level
fault tolerance is achieved by the basic ability to re-configure the
overall network so as to bypass failed links or nodes. Accordingly, the
macro level of fault tolerance is used as a means for overcoming massive
damage which might completely destroy certain links, nodes, or entire
regions of the overall network. By re-configuring the network it is
possible to reroute the data information so as to avoid the damaged
regions. The micro level of fault tolerance is achieved by providing basic
redundancy at each single node unit or linking path. Such redundancy is
provided because each remote unit is connected to the network at a single
node unit and, therefore, each node unit must be designed to have
sufficient redundancy to achieve the specified reliability requirements.
The redundancy of each node unit raises the basic reliability of the
building blocks of the network and guards against most normal component
failures.
FIGS. 2-8 describe in more detail the node units 12 of FIG. 1. Each node
unit is designed to be capable of verifying the correctness of any
transmission which passes through the node. Further, each node unit must
be able to record any errors which it recognizes and on command report
such errors to the central processor complex. The node unit further is
arranged to isolate itself from the effects of a faulty link despite the
necessity for monitoring all incoming terminal assignment commands. It is
further arranged to generate coordinated test conditions for all error
modes so as to test the error detection circuitry of the surrounding
nodes. Moreover, it is designed to maintain flexibility in the assignment
of the conductivity of the node.
Each node, in a preferred embodiment, can be fabricated so as to provide
redundant operation in order to increase the overall reliability thereof.
In the specific embodiment of a typical node unit, as discussed herein,
the node unit is connected to three other node units through appropriate
linking paths, although the concepts described herein can be expanded to
provide connections from one node unit to more than three other node
units, as desired. Further, while the node unit specifically described is
shown as having a redundancy level of three, such redundancy level can be
reduced to two or increased to more than three without significantly
altering the concepts involved. The use of replicated redundancy is
helpful in order to avoid using coded redundancy techniques which may be
more difficult to implement for purposes of providing the primary means of
error detection. When using replicated redundancy a minimum redundancy
level of at least two is required. Increased redundancy can be utilized to
increase the node and link reliabilities.
As can be seen in FIG. 2, for triple redundancy each node utilizes three
circuit sections which for convenience are depicted as separate integrated
circuit packages, or plates, 20. Such plates may all be on the same
integrated circuit module in a production system, for example. The data
paths 21 are connected together among the plates 20 as shown and the
redundant links 22 providing the connections to and from adjoining nodes
are a natural result of the redundant nature of the node itself. Such
duplication allows for easy determination of the sources of any errors. A
plurality of interconnections 23 to a remote device 24 are present between
each of the redundant node plates 20 and the associated remote device.
FIG. 3 illustrates a block diagram of a single node plate 20, the primary
task thereof being to route any data coming from the inboard side of the
node unit to the outboard side thereof or to the associated remote device
and to route any data from the remote device to the inboard side. Such
operation is done by selectively enabling the conductivity controls, as
described in more detail below.
In FIG. 3 when a node terminal comprising input lines 32 and output line 35
is connected to the inboard side of a node it can transmit information to
another node or receive information therefrom. Information arriving from
another node for transmittal through the node to the central control unit
arrives on such input lines 32 and is thereupon placed on the "IN" bus 34
within the node unit. Because of the triple redundancy technique used in
the particular embodiment shown, three input lines are used, as discussed
in more detail later. Such information which is destined for the central
control unit is thereupon directly transmitted to the output line 35 of a
node terminal which is converted to the outboard side of a link which
conveys the information to the central control unit either directly or via
intermediate nodes and links as required.
Information from the central processor control unit can be transmitted
directly through a node, if such information is not intended for any of
the remote devices associated with such node, via the inboard terminal of
the node which is connected to the outboard side of a link carrying such
information. Thus, such information arrives on input lines 32 thereof and
is placed on the OUT bus 33 whence it is transferred directly to the
outgoing line 35 of all outboard terminals connected to the inboard sides
of other links which are in turn connected to the other nodes.
Information from the central control unit which is intended for a
particular remote device arrives at the outboard side of a link to the
input lines 32 of the inboard terminal of a node which services such
remote device and is thereupon placed on the "OUT" bus 34 for appropriate
transmittal to the remote unit. Information from a remote device is
transmitted therefrom to the "IN" bus 34 of the node unit which services
the remote device and thence to the output line 35 of an inboard terminal
which is connected to the outboard side of a link which conveys the
information to the central control unit directly or via intermediate nodes
and links as required.
The input and output lines of the terminals of the node are organized so
that the output from one plate 20 of the node unit drives a single data
line 35 and the total number of redundant data output data lines from one
side of the node unit is equal to the number of plates 20 in that node
unit. All of the redundant input lines 32 into a side of the node unit are
processed by the discriminators 36 of each node plate and are used to
formulate a single correct data stream for use as the input signal to that
plate. The disriminators are, in effect, voter devices of the type well
known to those in the art and can include error detection circuitry also
well known to those in the art. For example, the voter circuit may be of
the form identified as majority logic gate unit MC14530 made and sold by
Motorola, Inc., while the error detection circuitry may be of the form
identified as exclusive-OR unit SN74136 made and sold by Texas
Instruments, Inc. which can be used to provide a set of outputs for
identifying which of the inputs agree and which one or more of the inputs
disagree with the majority, or of the form identified as comparator unit
DM8131 made and sold by National Semiconductor, Inc. to provide a simple
disagreement or error signal showing that at least one of the inputs
disagrees with the majority. Thus, the outputs from the discriminators 36
are made available to a node control unit 37 a part of which appropriately
controls the operation of the discriminators over suitable control lines.
When only three inputs are supplied to the discriminators 36,
substantially no control need to be provided by the node control unit 37
since the discriminator operates in an appropriate manner for providing
its output as is well known with respect to such voter discriminator
operation. If, however, more than three input lines are required for
certain types of redundancy techniques, some control over the selection of
which redundant lines are to be examined by the discriminator may be
necessary and such control is exercise | | |
