 |
Description  |
|
|
BACKGROUND OF THE INVENTION
The present invention relates to the field of computing networks, and
methods and apparatus for routing and transferring computer information in
networks. More specifically, the present invention relates to computing
networks of recursively interconnected computing node arrangements,
methods for accomplishing routing and transfer of computer information in
the inventive networks and assemblies of apparatus for the purpose.
In the prior art it has been recognized that digital computers can be
connected together into a network configuration so as to accomplish
transfers of data therebetween. Parallel processing has been suggested so
that a large computing problem is split into multiple tasks which can be
executed at the same time. Some prior art networks involve a grid-like
lattice of computers or a branching tree interconnection of computers.
Depending on application, the structure of a network should provide
advantageous properties from both the hardware and software points of
view, compatibility with efficient addressing and routing methods, and
short path lengths between computers in the system.
It is of significant interest to the art to find new forms of computer
networks having advantageous features superior to those of the prior art
and to elaborate the art by discovering alternative network apparatus,
methods, and systems. In addition, the advent of large scale integrated
circuit technology (LSI) and very large scale integrated circuit
technology (VLSI) has spurred interest in computer methods, apparatus
building blocks, and systems conveniently compatible to such technologies.
SUMMARY OF THE INVENTION
In the present invention new kinds of recursive computer networks, methods
for operating them, and apparatus for routing and transferring information
in computing networks have been discovered.
In the invention a network of computing nodes is interconnected by a
plurality of communication channels so as to be organized into units, each
unit having at least three computing nodes. Each computing node in each
unit is directly connected to every other computing node in the same unit
by communication channels. Also, the network is organized into at least
one group of units. In each group, each unit has only one direct
connection to each other unit by way of the communication channels. Each
group has at least three units, and any one computing node in any unit in
the network has a direct connection to at most one other unit in the
network. The nodes may be the same or different from one another,
depending on application. The nodes can also be computing networks
themselves.
Each computing node is provided with a whole number P (at least 3) of
two-way communication ports. Only one less than P of the ports on each
computing node are required to accomplish full interconnection of
computing nodes within the unit. Consequently, the unit is left with
exactly P two-way communication ports, one per computing node, useful for
communications external to the unit. Now the unit is able to be regarded
as a larger computing node having its own set of ports, just as do its
component computing nodes. The units can be and are interconnected into
groups in the same manner as computing nodes are interconnected to form
each unit. Groups, in turn, are suitably interconnected to each other to
form a higher order cluster in the same manner also as computing nodes are
interconnected to form each unit, because at each step, or level of
recursion, exactly P two-way communication ports remain for
ever-higher-order external communications. This capacity for
interconnection at any order of complexity in the same manner is the
recursive quality of the network.
The recursive networks of the invention lend themselves to a simple
addressing approach in that each computing node is given an identification
in each unit (cluster of nodes), each unit is given an identification in
each group (cluster of units), and each group is given an identification
any or each next higher-order cluster of groups, and so on. The
identifications are concatenated to form the address byte, or word, for
each computing node in the network as a whole. Relatively uncomplicated
routing operations are then capable of sending computer information to the
destination indicated by the contents of a destination address word.
The inventive methods of routing computer information in the networks of
the invention involve the steps of storing in each of the computing nodes
a distinct address having address portions. The address portions include
in decreasing order an address portion identifying for each computing node
its unit and an address portion identifying each computing node in its
unit. Also, an identification of each port of each computing node is
respectively stored in each computing node. The identification of each
port is identical with the computing node address portion of the address
of the computing node in the same unit to which the port is connected.
However, when the port is connected to a computing node in a distinct unit
in the same group of units, then the identification of the port is
identical with the unit address portion of the address of the computing
node in the distinct unit to which the port is connected. If the port is
connected to a computing node in a distinct group, then the port
identification is identical with the group address portion of the
computing node in the distinct group to which the port is connected, and
so on for levels of recursion higher and higher in the network.
In such methods, the computer information to be transferred is provided
with an associated destination address identical to an address of one of
the computing nodes in the network. Then the computer information is
transferred from its location in any sending one of the computing nodes
having an address distinct from the destination address, by selecting the
port of the sending computing node which has a port identification
identical to the highest order address portion in the destination address
which is different from the corresponding address portion of the sending
computing node. The computer information is sent out from the port so
selected into an adjacent computing node to which the port is connected by
a communication channel.
Because of the remarkable recursive properties of the inventive networks,
and the nodal addressing and port identification approach, the procedure
for selecting the correct port for transmission from any node along the
journey to the destination is found with highly advantageous economy of
method.
Addressable access to the adjacent node is available in some embodiments of
the routing and transfer apparatus of the invention. Where such access is
utilized, an adjacent port identification aspect of the inventive methods
is accomplished merely by obtaining as the adjacent port identification
the lowest-order address portion in the sending node address which is
different from the port identification of the port selected for sending
the computer information from the sending node.
In the routing and transfer apparatus feature of the invention, inventive
networks are prepared by interconnecting building blocks of the inventive
apparatus. Each apparatus includes at least one processing assembly having
a digital processor, first and second memories, partitioning circuitry,
and assembly control circuitry, communicating with first and second buses.
Each digital processor is able to communicate with its respective first
memory locally so as to be able to generate digital information to be
routed in the network. Also, each digital processor is able to communicate
through its respective partitioning circuitry with its respective second
memory. Each digital processor is able to communicate the information it
generates through the partitioning circuitry to the second bus
simultaneously with the partitioning circuitry also permitting access to
the second memory along the first bus to permit digital information also
to be communicated along the first bus to the second memory. The
partitioning circuitry is operated by grant inputs at least from the
assembly control circuitry in response to requests assertable from the
first bus and each digital processor.
Unlike a prior art approach wherein each digital processor communicates
with other processors exclusively through one or more terminal units, the
inventive routing and transfer apparatus permits adjacent processors to
reach and transfer directly into local shared memory, the second memory,
while the local digital processor is transferring directly into the shared
memory associated with another digital processor in another identical
processing assembly apparatus. The arrangement of each processor,
memories, partitioning circuitry, and assembly control circuitry which
permits this, is highly flexible in that the grant inputs to the
partitioning circuitry dynamically rearrange the configuration as
operations proceed. In this way transfers to first bus and second bus, and
direct operations on the second memory by the local digital processor are
made possible. By using more than one bus, highly advantageous flexibility
is obtained in interconnecting many of the processing assemblies together.
When three or more such processing assembly apparatus building blocks are
connected together with accompanying bus control circuitry, computing
nodes are formed. Each node has the first bus of each assembly apparatus
being a distinct nodal external bus for communications externally, and the
second bus of each assembly apparatus being joined and utilized as one
common intranodal bus. When two such processing assembly apparatus
building blocks are connected together with accompanying bus control
circuitry, assembly-pairs are formed. Each assembly-pair has the first bus
of each assembly apparatus joined and utilized so as to join the
processing assemblies. The second buses are respectively available.
Interestingly, the networks of the invention can in most cases be viewed
as interconnected nodes or as configurations of assembly-pairs.
The networks of the invention are useful by way of example in a computing
system of the multiple-instruction stream, multiple data stream (MIMD)
type. It is contemplated that the processing assemblies, and even
computing nodes be provided on LSI (and even networks on VLSI chips) and
interconnected in the recursive architecture of the inventive networks. As
such, the chips are suitably combined together at a single location to
form a computer of small size but huge computing capacity. The resulting
relatively inexpensive computational facility is applicable in solving
data processing problems in distributed or single data bases and complex
mathematical problems such as differential equations in multiple
dimensions. Fields of application include seismology, cosmology,
aerodynamics, meteorology, nuclear physics, signal processing, tomography,
pattern analysis, artificial intelligence, visual processing, speech
analysis, speech generation, and complex system control and simulation.
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 depicts an inventive second-order network (group) of computing
nodes.
FIG. 2 is a node addressing diagram of the inventive network of FIG. 1.
FIG. 3 depicts a third-order network according to the invention including
four groups having four units of four nodes each. Two examples of routing
of blocks of data in the network are shown using path arrows.
FIG. 4 depicts a second-order network according to the invention including
three units having three nodes apiece.
FIG. 5 depicts a second-order network according to the invention including
five units having five nodes apiece.
FIG. 6A is a flowchart illustrating an inventive method of operation of the
network of FIG. 3.
FIG. 6B illustrates address bits in a source address and a destination
address to facilitate description of the FIG. 6A operations.
FIG. 7 depicts a port identification scheme for each of four nodes in a
unit in the network of FIG. 3.
FIG. 8 is an electrical block diagram of the circuits and buses in a
typical one of the identical nodes in the inventive network of FIG. 3,
each node being an inventive combination.
FIG. 9 is a more detailed electrical circuit diagram of an inventive
circuit implemented a multiplicity of times to form the node of FIG. 8.
DETAILED DESCRIPTION OF THE DRAWING
FIG. 1 shows inventive network 1 having four computing units 10, 20, 30,
and 40. Each of the units has four computing nodes. Unit 10 includes
computing nodes 11, 12, 13, and 14. Unit 20 has computing nodes 21, 22,
23, and 24. Unit 30 includes computing nodes 31, 32, 33, and 34. Unit 40
has computing nodes 41, 42, 43, and 44.
Each node includes at least one digital processing unit for executing
instructions according to a program and using space in at least one
storage device or memory. Each node has interfaces called ports for
suitably two-way communication from node to node. In the network of FIG. 1
each node is provided with ports equal in number to the number of nodes in
each unit, being four in this case. Each node, for instance, is suitably a
PDP-11 or other minicomputer communicating to the other nodes from its
ports along communication links in accordance with the EIA RS-232
standard, where serial data transfer is contemplated, or along buses for
parallel data transfer as the skilled worker elects.
Each node is also suitably implemented as a microcomputer with the
appropriate number of two-way communication ports, using technique
analogous to the minicomputer approach. A discussion of such known nodes
is not undertaken since they are familiar to the skilled worker in the
field of computer network design. However, an inventive node providing
interesting features is described in connection with FIGS. 8 and 9. In any
event, the detail of each node is omitted in FIGS. 1-5 to clarify the
principles and manner of operation of the inventive networks without
sacrificing completeness in the disclosure thereof.
In unit 10 six two-way coxmunication channels interconnect nodes 11, 12,
13, and 14 as intraunit connections, represented by the six lines
respectively joining node pairs 11,12; 11,13; 11,14; 12,13; 12,14; and
13,14. Each of the units 20, 30, and 40 also each has six two-way
communication channels correspondingly interconnecting the nodes within as
intraunit connections.
Network 1 organizes the units 10, 20, 30, and 40 in a manner of
interconnection between units analogous to the manner of interconnection
of computing nodes within each unit. Thus, each of the units is
interconnected with every other unit by means of six two-way communication
channels 51, 52, 53, 54, 55 and 56, called interunit connections. Unit
pair 10,20 is connected by channel 51; 10,30 by channel 55; 10,40 by
channel 54; 20,30 by channel 52; 20,40 by channel 56; and 30,40 by channel
53.
Each node in network 1 has a two-way communication port for each two-way
communication channel connecting to it. For instance, node 12 has four
two-way communication ports (bidirectional ports) for the four two-way
communication channels connecting to it from nodes 11,13,14, and 34. As
another example node 44 has four two-way communication ports for the four
two-way communication channels connecting to it from nodes 41, 42, 43, and
13. By contrast, node 43 has four two-way communication ports and has
three two-way communication channels connecting to it from nodes 41, 42,
and 44, one of the ports being free for connection to an additional
two-way communication channel 45.
In an interesting feature of network 1, each unit 10, 20, 30, and 40
regarded as a whole has four ports available for communication outside
itself, just as does each four-port node. For instance, unit 10 has four
ports available for communication along channels 15, 51, 55, and 54. Unit
20 has four ports available for communication along channels 51, 25, 52,
and 56. Unit 30 has four ports available for communication along channels
52, 35, 53, and 55. Unit 40 has four ports available for communication
along channels 56, 53, 45, and 54. Thus, each unit 10, 20, 30, and 40 can
be regarded as a four-port computing device analogous to each four-port
computing node within it.
Further regarding network 1 itself as a whole, it is additionally observed
that network 1 also has precisely four ports available for communication
outside itself along two-way communication channels 15, 25, 35, and 45.
Accordingly, network 1 is itself a four-port computing device analogous to
each four-port computing unit and each four-port computing node within it.
This characteristic of network 1 is called recursion. Each unit 10, 20,
30, 40 has the same whole number being four of computing nodes in itself.
The network 1 has the same whole number being four of units in itself as
there are computing nodes in each unit. Each unit has each node therein
being directly connected to every other node in the same unit by
respective two-way communication channels from each node to every other
node in the same unit. At the same time, each unit has one and only one
direct connection (two-way communication channel with no intervening node)
to each other unit by way of the two-way communication channels, with any
one computer in each unit having at most one interunit direct connection
like 51,52,53,54,55,56 of FIG. 1. Each node is constructed identically.
Moreover, network 1 can be, and in embodiments of the invention is,
connected into more complex networks having the same recursive
organization as network 1 in the same manner of connection as any one or
each four-port node or four-port unit in network 1 is connected into
network 1 itself. When network 1 is connected together with other networks
identical to itself in the manner that units 10,20,30, and 40 are
connected together to form network 1, then a network of the next higher
level of recursion, or next higher order, is formed as shown in FIG. 3,
discussed later herein.
An addressing scheme made possible by network 1 is particularly
interesting. As shown in FIG. 2, each node within a unit can be identified
by as few as two bits 00, 01, 10, and 11 for four nodes. In turn, each
unit for addressing purposes is identified by as few as two higher-order
bits 00, 01, 10, and 11 for the four units. All sixteen nodes in network 1
are accordingly identified by four bits, the two higher-order unit bits
and the two lower-order node bits. By virtue of the particular
organization of the network as shown in FIG. 1, the four bits not only
merely distinctly identify each of sixteen nodes regardless of network
organization but also identify which unit the node is in, and where the
node is in its unit. The inventive organization of network not only
permits the four bits to distinctly "name" each node but also to provide
the location information on each node for data routing purposes between
nodes in the network.
For example, node 34 of FIG. 1 has address 0110 as shown in FIG. 2. The
address 0110 is a concatenation of the address 01 of unit 30 and the
address 10 of node 0110 in unit 01. In other words, computing node 0110 is
in the upper-right 01 unit and at the nodal intraunit position at
lower-left 10. Corresponding examples can be described for each of the
sixteen nodes in network 1. In each case 00 is an upper-left position, 01
is an upper-right position, 10 is lower-left, and 11 is lower-right.
Because of the regularity of the network due to its geometrically
recursive topology, the address word for each node not only identifies
each node distinctly but also contains the information cues needed to
locate the node in the network. Accordingly, an advantageously simple, and
consequently fast, routing program is made possible, described
hereinafter.
In FIG. 3, four groups, or networks, of the same type as network 1 and
numbered 110, 120, 130, and 140 are interconnected into network 100 in the
precisely analogous manner to the way units 10, 20, 30, and 40 are
interconnected into network 1 of FIG. 1. The resulting network 100 of FIG.
3 has 4 groups of 4 units of 4 nodes apiece for a total of 64 nodes in
all.
The third-order inventive network of FIG. 3, network 100, is composed of
four groups 110,120,130, and 140 which are said to be topologically
equivalent in that their wiring, or interconnection, diagrams are
identical in FIG. 3. Each group has one and only one direct connection by
a two-way communication channel to each other group by means of channels
151,152,153,154,155, and 156. Group 110 has units 111,112,113,114; group
120 has units 121,122,123,124; group 130 has units 131,132,133,134; and
group 140 has units 141,142,143, 144. In each group the units are all
topologically equivalent to one another in that their wiring diagrams are
identical.
In network 100 there are exactly four two-way communication ports available
for communication outside network 100 along communication channels 115,
125, 135, and 145. Network 100 can accordingly be interconnected into
networks of even higher order, or used in substitution for one of its own
nodes, units or groups. The addressing scheme is such that group 120 is
given binary address 00 (upper-left); group 130 is given binary address 01
(upper-right); group 110 is given binary address 10 (lower-left); and
group 140 has address 11 (lower-right). The group address is concatenated
as high-order bits to the address which each node has in each group as
described in connection with FIG. 1, so that a six-bit address is formed
for each of the 64 nodes in the network of FIG. 3.
For example the computing node having address 110100 in FIG. 3 has group
address 11 (lower-right), unit address 01 (upper-right in group 11), and
node address 00 (upper-left in unit 01). Two other nodes 101001 and 010010
are indicated on FIG. 3 as examples showing how the address also signifies
location in the network. It is observed that in general where the number P
is 4 of groups in the network, and the order of recursion of the network
is R, then the number of bits in the address word is 2R. For instance in
FIG. 3 the order of recursion R is 3 (third-order network) and the number
of bits in the address word is 6. In FIG. 1 the order of recursion is 2
and the number of bits in the address word is 4.
In FIG. 3 each unit has one and only one direct connection to each other
unit in the same group, i.e. the same second-order portion of the network.
Any one node in each unit of the network has at most one interunit direct
connection, at most one intergroup direct connection, and in general at
most one direct connection connecting portions of the network at the same
level of recursion. Any one computing node in any one unit in the whole
network 100 has a direct connection to at most one other unit in the
network.
The inventive computer networks take many forms. For example when the
number P of nodes per unit in a second-order network is three, network 60
of FIG. 4 is the result. In FIG. 4 three units 70, 80, and 90 each include
three nodes fully interconnected in triangular wiring diagrams by the
two-way communication channels. Three ports per node suffice to provide
each node with sufficient two-way communication ports for interconnection
in network 60. In unit 70 computing nodes 71, 72, 73 are interconnected by
channels 76,77,74. In unit 80 nodes 81, 82, 83 are interconnected by
channels 84,86,87. In unit 90 nodes 91, 92, 93 are interconnected by
channels 94,96,97. Interunit communication channels 79, 78, and 88 are
provided so that each unit is directly connected to every other unit but
that each node in each unit has at most one interunit direct connection.
In the recursive aspect of the network 60, when all nodes are provided
with exactly the same number P being 3 of two-way communication ports,
there are three ports 75, 85, and 95 left over for interconnection of
network 60 into higher-order networks. No two-way communication links
cross over one another in the diagram of FIG. 4 providing a potentially
advantageous feature when deposition on a planar substrate in
very-large-scale-integration (VLSI) technology is undertaken. The number
of bits per address word remains at twice the network level of recursion
R.
FIG. 5 shows a second-order network 200 of the invention in which the whole
number P of nodes per unit is five, and there are five fully
interconnected pentagon units 210,220,230,240,250. There are ten interunit
communication channels (P.times.(P-1)/2). Units 210,220 have interunit
communication channel 211; 210,230 have 212; 220,230 have 221; 220,240
have 222; 230,240 have 231; 230,250 have 232; 240,250 have 241; 240,210
have 242; 250,210 have 251; and 250,220 have 252. Each node (P.times.P=25
nodes) is provided with five two-way communication ports and each unit has
a free port for connection to optional two-way communication channels
213,223,233,243,253 thereby permitting higher orders of recursion. The
number of bits per address word now is three times the recursion number R,
since three bits are needed to identify each of five nodes per unit, and
five units in network 200. Since three bits can identify up to eight nodes
per unit (P=8), the same address word length can be used when the number
of nodes per unit is eight and the nodes are connected in fully
interconnected octagons with 8.times.7/2 or 28 interunit communication
channels, not shown. At all numbers P of nodes per unit and levels of
recursion R, the networks of the invention can be laid out in a manner
compatible with printed circuit board construction and even VLSI technique
due to the substantially planar arrangement.
In the present disclosure, a recursive network of the type being disclosed
is called "symmetrical" if every group is topologically equivalent to
every other group in the network, every subgroup is topologically
equivalent to every other subgroup in the network, and in general when
every portion of the network at the same level of recursion is
topologically equivalent to every other portion of the network at that
level of recursion. The networks of FIGS. 1, 3, 4, and 5 are all
symmetrical.
A recursive network of the type being disclosed is called "assymetrical" if
it is not symmetrical. An example of an assymetrical network (not shown)
is a network as shown in FIG. 3 having all but one node being identical,
the last node being the network of FIG. 1 substituted at one nodal
location in FIG. 3. A second example of an assymetrical network (not
shown) is a network as shown in FIG. 1 having identical nodes except for
units of the type of unit 111 of FIG. 3 being substituted for FIG. 1 nodes
23,34,41, and 12. In this second example, "symmetry" is absent as the term
is used herein notwithstanding that it can be said from a geometric point
of view that the assymetrical network can be divided into halves which are
mirror-images of each other. Assymetrical networks have contemplated
usefulness in situations including those in which it is desired to
concentrate computing power at some location to an additional degree
because of the nature of the computational problem to be solved.
A symmetrical network having P nodes per unit and level of recursion R is
denominated a PSR network. The FIG. 1 network 1 is 4S2 because it has four
nodes per unit and is second order. FIG. 3 shows a 4S3 network; FIG. 4 a
3S2; and FIG. 5 a 5S2. Each unit of a PSR network is a PS1 network
relative to its nodes, and each node may be a network itself. Each group
is a PS2 network. If the nodes are networks, they are described after a
colon (:). For example, a PS2 network is equivalent to a PS1:PS1 network,
which is a unit of nodes which are units of nodes themselves. In general,
PSR.sub.1 :PSR.sub.2 is equivalent to PS(R.sub.1 +R.sub.2). A P-port node
is a PSO (zero-order) network relative to itself. A "cluster" of PSR
networks is defined to be a PS(R+1) network.
The number of nodes N in a PSR network is P.sup.R. The number of
communications channels L internal to a PSR network is 1/2(P.sup.R+1 -P).
The largest minimum distance M required for a data block to traverse in
travelling between any two nodes in the network, expressed as the number
of communication channels to travel along, is 2.sup.R -1. The total number
of communications channels T is the internal channels L plus the external
channels being P in number.
It is to be understood that the hereinabove notation is not meant to
suggest that only symmetric networks are within the inventive scope, but
instead the notation assists in referring to some of the embodiments of
the inventive networks.
The average distance between nodes in a recursive architecture is of
considerable importance if random traversals are frequently attempted.
This can be the case, for instance, in a multiple computer system which
uses communication channels for interprocessor synchronization and for
access to a distributed data base.
The average path length in several symmetrical recursive (PSR) networks of
the invention has been computed. The results of the computations, as well
as of the equations for number of nodes N, total number of communications
channels T, and largest minimum distance M, are summarized in Table I. Two
values are given for the average path length. AVE1 includes a zero-length
traversal from each node in a structure to itself. AVE2 does not include
such zero-length traversals.
Average path length computations including zero-length traversals have been
performed for a tree-like computer network of the prior art known as
X-TREE. Therefore, the table column AVE1 is used to compare the selected
PSR networks with X-TREE. The comparison is shown in Table II.
In Table II, the N column has entries for the numbers of nodes in the
computer network. The 3SR, 4SR, 5SR, and 8SR columns have entries for the
average path length AVE1 of Table I rounded to the first decimal place
corresponding to the number of nodes N. The X-TREE column also has average
path length entries for the so-called fully-ringed X-TREE which utilizes
nodes having five ports each.
TABLE I
______________________________________
P R N T M AVE1 AVE2
______________________________________
3 2 9 15 3 1.78 2.00
3 3 27 42 7 3.93 4.08
3 4 81 123 15 8.20 8.30
4 2 16 34 3 2.06 2.20
4 3 64 130 7 4.64 4.71
4 4 256 514 15 9.78 9.82
5 2 25 65 3 2.24 2.33
5 3 125 315 7 5.09 5.13
5 4 625 1565 15 10.78 10.80
8 2 64 260 3 2.52 2.56
8 3 512 2052 7 5.78 5.79
______________________________________
TABLE II
______________________________________
N 3SR X-TREE 4SR 5SR 8SR
______________________________________
3 1.0 1.0
4 1.0
5 1.0
7 1.5
8 1.0
9 1.8
15 2.1
16 2.1
25 2.2
27 3.9
31 3.1
63 4.3
64 4.6 2.6
81 8.2
125 5.1
127 5.8
255 7.5
256 9.8
511 unav'b'l
512 5.8
625 10.8
______________________________________
The recursive and geometrical properties of the inventive networks allow
arbitrarily complex multiple-computer structures to be traversed from node
to node, using a very simple routing technique presented hereinafter. In a
PSR network, or in a symmetrical portion of a network, four parameters are
required for network traversal. These are
1. Source address
2. Destination address
3. Number of ports per node (P)
4. Level of recursion (R)
The first two parameters--the addresses of the source and destination
nodes, use a recursively-ordered addressing scheme over the full network.
The position of a node can be determined from its address, and the node
can use this address to determine the addresses of other nodes connected
to its communications ports. Thus, the addressing scheme of the preferred
embodiment is fixed and global, providing each node and its communications
ports with unique identifications, which are known to the node and its
neighbors.
The network addressing scheme in one approach uses base P numbers to
identify the nodes, and to enumerate the communications ports. A node
address has R digits, one digit for each level of recursion. A digit
describes the position of a node in a unit, the position of the unit in a
group, the position of each group in the next higher-order level, and so
forth.
The ports of each node are identified by conceptually labelling them in a
consistent fashion, so that all nodes have ports identified by the
identical scheme. Thus, it is to be emphasized that the network addressing
scheme not only involves providing addresses with location meanings to
every node but also identifying each port of each node according to the
scheme. The port addressing scheme is provided as information in each node
so that a routing operation identical for all the nodes can be executed at
each node.
Address word portions are binary-coded to represent base-P numbers, so that
when P=4, for example, the ports of each node are identified by the coded
representations 00, 01, 10, and 11. P nodes in a unit are arranged to form
a fully interconnected network, e.g. 4S1. Each position in the pattern of
the unit is numbered in a manner corresponding to the port
identifications. Thus, there are P nodes arranged in a geometric
structure, as the vertices of a polygon or polyhedron. When P is 4, for
instance, the geometric structure is a tetrahedron and when laid out on a
plane is the topologically equivalent circuit of a square with four
vertices fully interconnected. Each unit resembles topologically the
outline of a tetrahedron with a node at each vertex and a communication
channel for each edge. Each group is also topologically tetrahedral, with
a unit at each vertex and a communication channel for each edge.
Accordingly, the network of FIG. 3 is, like that of FIG. 1, recursively
topologically tetrahedral.
FIG. 7 shows a unit 142 of four nodes 110100, 110101, 110110, and 110111
from FIG. 3 having the ports of each node identified by the coded
representations 00, 01, 10, and 11 just next to the external communication
channels connected to each node. For example, port 00 of node 110100 is
the port to which unit 141 of FIG. 3 is connected; port 01 is the port to
which node 110101 is connected; port 10 is the port to which node 110110
is connected; and port 11 is the port to which node 110111 is connected.
Similar port designations are provided for illustration purposes next to
each of the other nodes in corresponding locations. The four nodes in unit
142 are arranged to form a fully interconnected configuration of the 4Sl
type within a larger 4S3 network.
In unit 142, node 110100 is in the 00 (upper-left) position as indicated in
the rightmost 00 bit-pair in the node address 110100 itself. Similarly,
node 110101 is in the 01 position, node 110110 is in the 10 position, and
node 110111 is in the 11 position in unit 142.
In the connection strategy of the preferred embodiment, as illustrated in
FIG. 7, the 01 port of the node in the 00 position (i.e. node 110100) is
connected to the 00 port of the node in the 01 position (i.e. node
110101). The 10 port of the 00 node is connected to the 00 port of the 10
node. The 11 port of the 00 node is connected to the 00 port of the 11
node. The 10 port of the 01 node is connected to the 01 port of the 10
node. The 11 port of the 01 node is connected t | | |
