 |
Claims  |
|
|
What is claimed is:
1. A communications system, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network, the means for connecting comprising forward channel
and back channel signal paths coupled to each of the input and output
ports in the switch nodes, wherein the back channel signal paths have a
narrower bandwidth relative to the forward channel signal paths to
simplify packaging.
2. The system of claim 1, further comprising:
(c) multicast means, operative within the network, for transmitting forward
channel messages from a source to one or more destinations; and
(d) back channel merge means, within each switch node, for combining back
channel replies received from the destinations into a single result,
wherein the result is transmitted on the back channel to the source.
3. The system of claim 1, wherein the means for connecting comprises
cabling means for wiring between switch nodes in different stages so that
the forward channels and back channel signal paths are laid out in one or
more copies of a universal wiring pattern.
4. The system of claim 3, wherein the universal wiring pattern comprises a
permutation of connections between switch node input and output ports that
swaps the least significant two base b digits of a port's level number
representation, where b is the switch node size.
5. The system of claim 3, wherein the means for wiring comprises means for
wiring every stage in a network of size N=x.sup.n, n>1, with x.sup.n-2
copies of the universal wiring pattern, wherein x is a total number of
output ports on a switch node.
6. The system of claim 1, wherein the means for connecting comprises means
for interconnecting the switch nodes together to simplify the cabling,
wherein a pattern of interconnections between switch nodes in each stage
of the network is completely specified by permuting the digits of a level
number representing a port of a switch node.
7. The system of claim 6, wherein the means for interconnecting comprises
means for connecting switch node output ports identified by (S: x.sub.n-1
. . . x.sub.1 x.sub.0) to switch node input ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network, and x is a level number of a switch node port
represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in a base b
corresponding to a size of the switch nodes, wherein 0.ltoreq.x.sub.i =b,
0.ltoreq.i<n.
8. The network of claim 7, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.2.sub.0 {x.sub.1 x.sub.0
}=x.sub.0 x.sub.1 for a network wherein n=2.
9. The network of claim 7, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.1 x.sub.0 x.sub.2 for a network wherein n=3.
10. The network of claim 7, wherein PERMUTE.sup.n.sub.S }x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 }x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 }x.sub.2 x.sub.1
x.sub.0 }=x.sub.0 x.sub.1 x.sub.2 for a network wherein n=3.
11. The network of claim 7, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.4.sub.0 {x.sub.3 x.sub.2
x.sub.1 x.sub.0 }=x.sub.3 x.sub.2 x.sub.0 x.sub.1, PERMUTE.sup.4.sub.1
{x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.1 x.sub.0 x.sub.3 x.sub.2, and
PERMUTE.sup.4.sub.2 {x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.3 x.sub.2
x.sub.0 x.sub.1 for a network wherein n=4.
12. The network of claim 11, wherein PERMUTE.sup.4.sub.0 and
PERMUTE.sup.4.sub.2 leave the most significant two digits undisturbed, so
that an interconnection length in stages 0 and 2 are minimized.
13. The system of claim 6, wherein the means for interconnecting comprises
means for connecting switch node output ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }) to switch node
input ports identified by (S: x.sub.n-1 . . . x.sub.1 x.sub.0), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network, and x is a level number of a switch node port
represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in a base b
corresponding to a size of the switch nodes, wherein 0.ltoreq.x.sub.i <b
and 0.ltoreq.i<n.
14. The network of claim 13, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.2.sub.0 {x.sub.1 x.sub.0
}=x.sub.0 x.sub.1 for a network wherein n=2.
15. The network of claim 13, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.1 x.sub.0 x.sub.2 for a network wherein n=3.
16. The network of claim 13, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.0 x.sub.1 x.sub.2 for a network wherein n=3.
17. The network of claim 13, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.4.sub.0 {x.sub.3 x.sub.2
x.sub.1 x.sub.0 }=x.sub.3 x.sub.2 x.sub.0 x.sub.1, PERMUTE.sup.4.sub.1
{x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.1 x.sub.0 x.sub.3 x.sub.2, and
PERMUTE.sup.4.sub.2 {x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.3 x.sub.2
x.sub.0 x.sub.1 for a network wherein n=4.
18. The network of claim 17, wherein PERMUTE.sup.4.sub.0 and
PERMUTE.sup.4.sub.2 leave the most significant two digits undisturbed, so
that an interconnection length in stages 0 and 2 are minimized.
19. The system of claim 1, wherein the means for connecting comprises means
for arranging the switch nodes in more than log.sub.b N stages, wherein
b is a total number of switch node input/output ports, N is a total number
of network I/O ports, and log.sub.b N indicates a ceiling function
providing the smallest integer not less than log.sub.b N, thereby
providing additional communication paths between any network input port
and network output port to enhance fault tolerance and lessen contention.
20. The system of claim 19, wherein the switch nodes are arranged in 2
log.sub.b N stages.
21. A method of communicating among a plurality of switch nodes connected
together in a multistage interconnect network, each switch node comprising
a first plurality of input ports, a second plurality of output ports, and
means for selectively connecting said input ports to said output ports,
the method comprising:
(a) transmitting messages between switch nodes using a forward channel
coupled to each of the input and output ports in the switch nodes; and
(b) transmitting between switch nodes using a back channel coupled to each
of the input and output ports in the switch nodes, wherein the back
channels have a narrower bandwidth relative to the forward channels to
simplify packaging.
22. The method of claim 21, further comprising:
(c) transmitting forward channel messages from a source to one or more
destinations; and
(d) combining back channel replies received from the destinations into a
single result, wherein the result is transmitted on the back channel to
the source.
23. A communication system having a plurality of ports for concurrently
transferring messages between different ones of the ports, comprising:
(a) a plurality of agents connected to the system, each including means
providing interconnect request messages containing routing tags for
communicating with other agents, means for transmitting variable length
data messages, and means for transmitting response messages of different
types having values in accordance with a predetermined protocol; and
(b) network means for intercoupling the agents, the network means
comprising a plurality of switch nodes arranged in a multistage
interconnect network and each having a plurality of forward channel and
back channel signal paths with selectable interconnections between
different terminals of the switch nodes, the back channel signal paths
having a narrower bandwidth relative to the forward channel signal paths,
the switch nodes also including means responsive to the routing tags in
the messages for selecting signal paths between switch nodes in order to
establish a complete path through the network, and the switch nodes
further comprising means for reserving the complete path during the
transmission of variable length data messages, once request messages and
response messages thereto have been successfully interchanged.
24. A communications system, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for interconnecting the switch nodes together in a multistage
interconnect network to simplify the cabling therebetween, wherein a
pattern of interconnections between different stages of switch nodes is
specified by permuting the digits of a level number representing a port of
a switch node.
25. The system of claim 24, wherein the means for interconnecting comprises
means for connecting switch node ports identified by (S: x.sub.n-1 . . .
x.sub.1 x.sub.0) to switch node ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network, and x is a level number of a switch node port
represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in a base b
corresponding to a size of the switch nodes, wherein 0.ltoreq.x.sub.i <b
and 0.ltoreq.i<n.
26. The network of claim 25, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.2.sub.0 {x.sub.1 x.sub.0
}=x.sub.0 x.sub.1 for a network wherein n=2.
27. The network of claim 25, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.1 x.sub.0 x.sub.2 for a network wherein n=3.
28. The network of claim 25, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.0 x.sub.1 x.sub.2 for a network wherein n=3.
29. The network of claim 25, wherein PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.4.sub.0 {x.sub.3 x.sub.2
x.sub.1 x.sub.0 }=x.sub.3 x.sub.2 x.sub.0 x.sub.1, PERMUTE.sup.4.sub.1
{x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.1 x.sub.0 x.sub.3 x.sub.2, and
PERMUTE.sup.4.sub.2 {x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.3 x.sub.2
x.sub.0 x.sub.1 for a network wherein n=4.
30. The network of claim 29, wherein PERMUTE.sup.4.sub.0 and
PERMUTE.sup.4.sub.2 leave the most significant two digits undisturbed, so
that an interconnection length in stages 0 and 2 are minimized.
31. A communications apparatus, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network by connecting switch node ports identified by (S:
x.sub.n-1 . . . x.sub.1 x.sub.0) to switch node ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network and hence its size, and x is a level number of a
switch node port represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in
a base b corresponding to the size of the switch nodes, wherein
0.ltoreq.x.sub.i <b, 0.ltoreq.i<n and PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.2.sub.0 {x.sub.1 x.sub.0
}=x.sub.0 x.sub.1 for a network wherein n=2.
32. A communications apparatus, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network by connecting switch node ports identified by (S:
x.sub.n-1 . . . x.sub.1 x.sub.0) to switch node ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network and hence its size, and x is a level number of a
switch node port represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in
a base b corresponding to the size of the switch nodes, wherein
0.ltoreq.x.sub.i <b, 0.ltoreq.i<n and PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.1 x.sub.0.sub.x.sub.2 for a network wherein n=3.
33. A communications apparatus, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network by connecting switch node ports identified by (S:
x.sub.n-1 . . . x.sub.1 x.sub.0) to switch node ports identified by (S+1:
PERMUTE.sup.n.sub.S }x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network and hence its size, and x is a level number of a
switch node port represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in
a base b corresponding to the size of the switch nodes, wherein
0.ltoreq.x.sub.i <b, 0.ltoreq.i<n and PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.3.sub.0 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.2 x.sub.0 x.sub.1 and PERMUTE.sup.3.sub.1 {x.sub.2 x.sub.1
x.sub.0 }=x.sub.0 x.sub.1 x.sub.2 for a network wherein n=3.
34. A communications apparatus, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network by connecting switch node ports identified by (S:
x.sub.n-1 . . . x.sub.1 x.sub.0) to switch node ports identified by (S+1:
PERMUTE.sup.n.sub.S {x.sub.n-1 . . . x.sub.1 x.sub.0 }), wherein S
indicates a switch node in a specific stage, n refers to a total number of
stages in the network and hence its size, and x is a level number of a
switch node port represented as (x.sub.n-1 . . . x.sub.1 x.sub.0).sub.b in
a base b corresponding to the size of the switch nodes, wherein
0.ltoreq.x.sub.i <b, 0.ltoreq.i<n and PERMUTE.sup.n.sub.S {x.sub.n-1 . . .
x.sub.1 x.sub.0 } is equivalent to PERMUTE.sup.4.sub.0 {x.sub.3 x.sub.2
x.sub.1 x.sub.0 }=x.sub.3 x.sub.2 x.sub.0 x.sub.1, PERMUTE.sup.4.sub.1
{x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub. 1 x.sub.0 x.sub.3 x.sub.2, and
PERMUTE.sup.4.sub.2 {x.sub.3 x.sub.2 x.sub.1 x.sub.0 }=x.sub.3 x.sub.2
x.sub.0 x .sub.1 for a network wherein n=4.
35. A communications network, comprising:
(a) a plurality of switch nodes arranged into a multistage interconnect
network having a plurality of input and output ports, each port being
coupled to an agent to effect communication between agents through the
network;
(b) the network having a multiple of log.sub.b N stages of interconnected
switch nodes, wherein b is a total number of switch node input/output
ports, N is the number of network I/O ports, and log.sub.b N indicates a
ceiling function providing the smallest integer not less than log.sub.b N,
thereby providing additional paths between any network input port and
network output port to enhance fault tolerance and lessen contention; and
(c) the network having a loop-back point indicating where the stages of the
network are physically folded together so that corresponding switch nodes
in similarly numbered stages on either side of the loop-back point are
located adjacent to each other, thereby simplifying packaging and
minimizing signal path lengths.
36. An apparatus for concurrently transferring messages between different
ports, comprising:
(a) multistage interconnect network means for interconnecting a plurality
of switch nodes for communication therebetween, each switch node
comprising a first plurality of input ports, a second plurality of output
ports, and means for selectively connecting said input ports to said
output ports; and
(b) dynamic configuration means for determining how the switch nodes are
interconnected and hence a topology of the multistage interconnect network
means, so that messages can be routed correctly between the switch nodes.
37. The apparatus of claim 36, wherein the dynamic configuration means
further comprises:
(1) means for communicating addresses between switch nodes, wherein one
switch node communicates its location to another switch node connected
thereto; and
(2) tag mapping table means, in each switch node, for storing routing
information derived from the addresses of the switch nodes, so that
messages can be routed correctly between the switch nodes.
38. The apparatus of claim 37, further comprising initializing means for
querying the switch nodes at startup to determine how they are
interconnected and for generating the tag mapping table means in response
thereto.
39. A network, comprising:
(a) a plurality of switch nodes, each having a first plurality of input
ports, a second plurality of output ports, and path selector means for
selectively connecting the switch node input ports to the switch node
output ports;
(b) means for interconnecting the switch nodes in a relatively arbitrary
manner to effect a multistage interconnect network, the network having a
first plurality of input ports, a second plurality of output ports, and
means for routing messages through the network by transmitting a message
from one switch node to another switch node; and
(c) means for determining how the switch nodes have been interconnected and
for constructing routing tables for each switch node in response thereto,
so that the path selector means can connect an input port receiving a
message to an output port for transferring the message in order to
correctly transmit the message.
40. The network of claim 39, wherein the means for determining comprises:
(1) topology determination means for communicating addresses between the
switch nodes, so that a topology for the network can be determined; and
(2) message routing means for storing routing information derived from the
addresses of the switch nodes, so that messages can be routed correctly
through the network.
41. A communications apparatus, comprising:
(a) network means for providing bidirectional data transmission between
agents, the network means comprising switch nodes connected together in a
multistage interconnect network, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) tag mapping table means, in each switch node, for storing routing
information derived from the addresses of the switch nodes, so that the
data transmission can be routed correctly through the network means.
42. A method for communicating in a network comprising a plurality of
switch nodes, each switch node having a first plurality of input ports, a
second plurality of output ports, and path selector means for selectively
connecting the switch node input ports to the switch node output ports,
the method comprising:
(a) interconnecting the switch nodes in a relatively arbitrary manner to
effect a multistage interconnect network;
(b) determining how the switch nodes have been interconnected;
(c) constructing routing tables for each switch node according to how the
switch nodes have been interconnected; and
(d) transferring messages through the network according to the routing
tables, wherein each switch node that receives the messages uses a routing
table to determine which output port should receive the message.
43. The method of claim 42, wherein the determining step comprises:
(1) communicating addresses between the switch nodes, so that a topology
for the network can be determined; and
(2) storing routing information derived from the addresses of the switch
nodes, so that messages can be routed correctly through the network.
44. A communications system, comprising:
(a) network means for providing bidirectional data transmission between
agents connected thereto, the network means comprising switch nodes
connected together in a multistage interconnect network, each switch node
comprising a first plurality of input ports, a second plurality of output
ports, and means for selectively connecting said input ports to said
output ports; and
(b) self-diagnosing means, integrated with the network, for detecting and
reporting any errors that occur within the network.
45. The system of claim 44, wherein the self-diagnosing means comprises
diagnostic processor means for monitoring the state of the network means,
for performing self-tests on the components of the network means, and for
initializing the network means.
46. The system of claim 45, wherein the diagnostic processor means
comprises means for configuring routing tables and input and output enable
vectors for the network means so that fault conditions in the network
means can be bypassed.
47. A communications system, comprising:
(a) a multistage interconnect network comprising a plurality of
interconnected active logic switch nodes;
(b) diagnostic means for detecting and reporting any errors that occur
within the network, and for isolating the errors without propagating them,
thereby improving diagnosability and serviceability;
(c) reconfiguration means for reconfiguring the network when an error is
detected, without interrupting communications in the system, so that any
degradation in performance is minimized.
48. The system of claim 47, wherein the reconfiguration means further
comprises means for reconfiguring routing tables and input and output
enable vectors in the network, so that all communications are routed
around a faulty section of the network.
49. The system of claim 47, wherein the network further comprises redundant
networks for providing added bandwidth and fault tolerance to the system.
50. The system of claim 49, further comprising control means for load
leveling message transmission through the redundant networks.
51. The system of claim 49, further comprising control means for switching
between the redundant networks when a failure occurs, so that if one or
more of the redundant networks is not available, the others can take over,
thereby providing for graceful degradation in the presence of
malfunctions.
52. A method for communicating in a multistage interconnect network
comprising a plurality of interconnected active logic switch nodes, the
method comprising the steps of:
(a) detecting and reporting any errors that occur within the network, and
isolating the errors without propagating them, thereby improving
serviceability; and
(b) reconfiguring the network when an error is detected, without
interrupting communications in the system, so that any degradation in
performance in the reconfigured network is minimized.
53. The method of claim 52, wherein the reconfiguring step further
comprises reconfiguring routing tables and input and output enable vectors
in the network, so that all communications are routed around a faulty
section of the network.
54. The method of claim 52, further comprising load leveling message
transmission through redundant networks.
55. The method of claim 52, further comprising switching between redundant
networks when a failure occurs, so that if one or more of the redundant
networks is not available, the others can take over, thereby providing for
graceful degradation in the presence of malfunctions.
56. A communications system, comprising:
(a) a multistage interconnect network comprising a plurality of
interconnected active logic switch nodes;
(b) each switch node comprising a first plurality of input ports, a second
plurality of output ports, and means for selectively connecting said input
ports to said output ports;
(c) the multistage interconnect network comprising more than log.sub.b N
stages of switch nodes, wherein b is a total number of switch node
input/output ports, N is a total number of network input/output ports, and
log.sub.b N indicates a ceiling function providing the smallest integer
not less than log.sub.b N, the stages thereby providing a plurality of
paths between any network input port and network output port to enhance
fault tolerance and lessen contention;
(d) diagnostic means for detecting and reporting any errors that occur
within the network, thereby improving serviceability; and
(e) reconfiguration means for reconfiguring the network, without
interrupting the communications in the system, when an error is detected,
and for isolating the error without propagating it, so that any
degradation in performance in the reconfigured network is minimized.
57. The system of claim 56, wherein the switch nodes further comprise tag
mapping table means, associated with each input port of a switch node, for
interpreting a routing tag to determine which output port of the switch
node to select in order to route correctly a connect request through the
network.
58. The system of claim 57, wherein the tag mapping table means comprises a
memory array with a plurality of entries for translating the routing tag
to an output port selection, wherein the array provides a one-to-one
mapping between a logical port selection provided by the routing tag and a
physical port selection.
59. The system of claim 58, wherein each entry in the array is derived from
an appropriate field of the routing tag according to a stage of the switch
node within the network.
60. The system of claim 56, wherein the switch nodes further comprise input
enable vectors for indicating which input ports of the switch node are
operational.
61. The system of claim 56, wherein the switch nodes further comprise
output enable vectors for indicating which output ports of the switch node
are operational.
62. The system of claim 59, wherein the tag mapping table means comprises a
lookup table for mapping the routing tag to a physical output port based
on the way in which the network is cabled.
63. The system of claim 59, wherein the tag mapping table means further
comprises means for initializing each entry in the tag mapping table means
to be numerically equivalent to its address offset, such that a physical
port selection is equal to a logical port selection, thereby providing
default values that are appropriate for fully configured networks.
64. The system of claim 63, wherein the tag mapping table means further
comprises means for overlaying the default values when a configuring agent
has determined an actual topology for the network.
65. A communications system, comprising:
(a) a network comprising at least two input ports and two output ports, and
capable of simultaneous communications between a different pair of input
and output ports;
(b) message routing means, within the network, for accepting a connect
request containing a routing tag identifying an output port destination
for the message, and for steering the connect request to the output port
destination;
(c) back-off means, within the network, for cancelling the connect request
when the output port destination is unavailable; and
(d) retry means, triggered by the back-off means, for delaying a retry of
the connect request, and for trying a different connect request between
the input port and a different output port destination, thereby reducing
contention in the network.
66. The system of claim 65, wherein the network further comprises:
(1) a plurality of switch nodes, each comprising a first plurality of input
ports, a second plurality of output ports, and means for selectively
connecting said input ports to said output ports;
(2) tag mapping table means, associated with each input port of a switch
node, for interpreting the routing tag to determine which output port of
the switch node to select in order to route correctly the connect request
through the network.
67. The system of claim 65, wherein the message routing means further
comprises monocast blocking means for disabling the back-off means and for
waiting until a desired path through the network becomes available.
68. The system of claim 65, wherein the message routing means further
comprises monocast pipelining means for sending messages from sending
agents to receiving agents without waiting for acknowledgments to connect
requests from the receiving agents.
69. A communications method for a network comprising at least two input
ports and two output ports, and capable of simultaneous communications
between a different pair of input and output ports, the method comprising
the steps of:
(a) accepting a connect request containing a routing tag identifying an
output port destination for the message, and steering the connect request
to the output port destination;
(b) cancelling the connect request when the output port destination is
unavailable; and
(c) delaying a retry of the connect request, and for trying a different
connect request from the input port, thereby reducing contention in the
network.
70. The method of claim 69, further comprising interpreting the routing tag
to determine which output port of the switch node to select in order to
route correctly the connect request through the network.
71. The method of claim 69, wherein the accepting step further comprises
preventing cancellation of connect requests and waiting until a desired
path through the network becomes available.
72. The method of claim 69, wherein the accepting step further comprises
transmitting messages from sending agents to receiving agents without
waiting for acknowledgments to connect requests from the receiving agents.
73. A communications apparatus, comprising:
(a) a multistage interconnect network comprising a plurality of
interconnected active logic switch nodes;
(b) each switch node comprising a first plurality of input ports, a second
plurality of output ports, and means for selectively connecting said input
ports to said output ports;
(c) the multistage interconnect network comprising more than log.sub.b N
stages of switch nodes, wherein b is a total number of switch node
input/output ports, N is a total number of network input/output ports, and
log.sub.b N indicates a ceiling function providing the smallest integer
not less than log.sub.b N, thereby providing a plurality of paths between
any network input port and network output port to enhance fault tolerance
and lessen contention; and
(d) load balancing means, in each switch node, for distributing messages
among the plurality of output ports so that messages are evenly
distributed throughout the network.
74. The apparatus of claim 73, wherein the load balancing means comprises:
(1) means, within each switch node, for choosing a switch node output port
similarly numbered as a requesting switch node input port when the
similarly numbered switch node output port is available; and
(2) means, within each switch node, for choosing a next available switch
node output port when the similarly numbered switch node output port is
not available.
75. The apparatus of claim 74, wherein the load balancing means further
comprises means for selecting a second output port of a switch node having
a next higher port number than the input port of the switch node that
received the connect request when the first output port is unavailable.
76. A system for concurrently transferring messages between different
ports, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting the input ports to the output ports; and
(b) means for interconnecting the switch nodes in a multistage interconnect
network having a first plurality of network input ports and a second
plurality of network output ports;
(c) partitioning means for grouping the network ports into logically
independent subsets, wherein each subset is a supercluster; and
(d) multicast means, operative within the network, for transmitting a
message from a network input port to one or more network output ports
grouped in a supercluster, wherein messages transmitted within any one
supercluster are prevented from interfering with messages transmitted
within any other supercluster.
77. The system of claim 76, wherein the partitioning means further
comprises:
(1) means for grouping network ports into a supercluster of size 2.sup.m-p,
wherein binary addresses for the grouped network ports are identical in p
highest order bits thereof, thereby providing 2.sup.P superclusters of
size 2.sup.m-p in the system, wherein m= log.sub.2 N , N is a total number
of network input/output ports, and log.sub.2 N indicates a ceiling
function providing the smallest integer not less than log.sub.2 N; and
(2) means for addressing each supercluster as {y.sub.m-1,y.sub.m-2, . . .
,y.sub.m-p }, wherein y.sub.i .epsilon. }0,1} and m-1.ltoreq.i.ltoreq.m-p.
78. The system of claim 77, further comprising means for recursively
subdividing superclusters into smaller superclusters, so that the system
can contain a plurality of superclusters of different sizes, wherein each
size is a power of two.
79. The system of claim 77, further comprising means for allocating network
ports to address blocks that are a power of two when each supercluster
size is not a power of two and/or N is not a power of two.
80. The system of claim 76, wherein the partitioning means further
comprises:
(1) means for generating a list of supercluster sizes; and
(2) means for calculating a smallest power of two not less than each
supercluster size;
(3) means for adding up the calculated powers of two to determine a size of
a network needed;
(4) means for calculating the smallest power of two not less than the size
of the network;
(5) means for dividing the network in half recursively as needed until
there is a section which is the size of each power of two that was
calculated for each supercluster; and
(6) means for assigning the network ports in each supercluster to addresses
in the corresponding range.
81. A method for concurrently transferring messages between different ports
of a multistage interconnect network having a plurality of interconnected
switch nodes, the method comprising the steps of:
(a) grouping the network ports into logically independent subsets, wherein
each subset is a supercluster; and
(b) transmitting a message from a network input port to one or more network
output ports grouped in a supercluster, wherein messages transmitted
within any one supercluster are prevented from interfering with messages
transmitted within any other supercluster.
82. The method of claim 81, wherein the grouping step further comprises:
(1) grouping network ports into a supercluster of size 2.sup.m-p, wherein
binary addresses for the grouped network ports are identical in p highest
order bits thereof, thereby providing 2.sup.P superclusters of size
2.sup.m-p in the system, wherein m= log.sub.2 N , N is a total number of
network input/output ports, and log.sub.b N indicates a ceiling function
providing the smallest integer not less than log.sub.2 N; and
(2) addressing each supercluster as {y.sub.m-1,y.sub.m-2, . . . ,y.sub.m-p
}, wherein y.sub.i .epsilon. {0,1}and m-1.ltoreq.i.ltoreq.m-p.
83. The method of claim 82, further comprising recursively subdividing
superclusters into smaller superclusters, so that the network can contain
a plurality of superclusters of different sizes, wherein each size is a
power of two.
84. The method of claim 82, further comprising allocating network ports to
address blocks that are a power of two when N is not a power of two.
85. The method of claim 81, wherein the grouping step further comprises:
(1) generating a list of supercluster sizes; and
(2) calculating a smallest power of two not less than each supercluster
size;
(3) adding up the calculated powers of two to determine a size of a network
needed;
(4) calculating the smallest power of two not less than the size of the
network;
(5) dividing the network in half recursively as needed until there is a
section which is the size of each power of two that was calculated for
each supercluster; and
(6) assigning the network ports in each supercluster to addresses in the
corresponding range.
86. A system for concurrently transferring messages between different
ports, comprising:
(a) a plurality of switch nodes, each switch node comprising a first
plurality of input ports, a second plurality of output ports, and means
for selectively connecting said input ports to said output ports; and
(b) means for connecting the switch nodes together in a multistage
interconnect network, the means for connecting comprising forward channel
and back channel signal paths; and
(c) multicast means, operative within the network, for transmitting forward
channel messages from a source to one or more destinations; and
(d) back channel merge means, within each switch node, for combining back
channel replies received from the destinations into a single result,
wherein the result is transmitted on the back channel to the source.
87. The system of claim 86, wherein the multicast means comprises means for
steering a multicast request for a supercluster to a bounce back point
within the network means, wherein all multicast requests to the
supercluster use the same bounce back point.
88. The system of claim 87, wherein the means for steering comprises means
for steering a multicast request from one supercluster to a destination
supercluster through a bounce back point for the destination supercluster.
89. The system of claim 86, wherein the multicast means comprises means for
permitting only one multicast message at a time within a supercluster
thereby preventing deadlock between competing multicast requests.
90. A method for concurrently transferring messages between different ports
of multistage interconnect network, the network comprising a plurality of
switch nodes, each switch node comprising a first plurality of input
ports, a second plurality of output ports, and means for selectively
connecting said input ports to said output ports, the switch nodes
connected together via forward channel and back channel signal paths
connected to every input and output port, the method comprising the steps
of:
(a) transmitting forward channel messages from a source to one or more
destinations; and
(b) combining back channel replies received from the destinations into a
single result, wherein the result is transmitted on the back channel to
the source.
91. The method of claim 90, wherein the transmitting step comprises
steering a multicast request for a supercluster to a bounce back point
within the network means, wherein all multicast requests to the
supercluster use the same bounce back point.
92. The method of claim 91, wherein the steering step comprises steering a
multicast request from one supercluster to a destination supercluster
through a bounce back point for the destination supercluster.
93. The method of claim 90, wherein the transmitting step comprises
permitting only one multicast message at a time within a supercluster,
thereby preventing deadlock between competing multicast requests.
94. A system for concurrently transferring messages, comprising:
(a) a multistage interconnect network comprising a plurality of
interconnected active logic switch nodes;
(b) each switch node comprising a first plurality of input ports, a second
plurality of output ports, and means for selectively connecting said input
ports to said output ports;
(c) the multistage interconnect network comprising more than log.sub.b N
stages of switch nodes, wherein b is a total number of switch node
input/output ports, N is a total number of network input/output ports, and
log.sub.b N indicates a ceiling function providing the smallest integer
not less than log.sub.b N, the multistage interconnect network providing a
plurality of paths between any network input port and network output port
to enhance fault tolerance and lessen contention; and
(d) multicast steering means, within each switch node, for routing
multicast requests to a specific input port of a specific switch node
within the network, so that only one multicast request can occur at a
time, thereby preventing deadlock between competing multicast requests.
95. The system of claim 94, further comprising:
(1) means for storing a reply from each network output port in the back
channel; and
(2) means for collecting replies from the network output ports and for
applying the replies to merge means for synchronously combining all of the
replies, wherein the replies are sorted as they propagate through the
merge means, so that only the reply having the highest priority is
transmitted through the system.
96. The system of claim 95, wherein the merge means comprises low sort
means for outputting a reply with a lowest key followed by an accompanying
data word.
97. The system of claim 95, wherein the merge means further comprises add
means for summing data words of all replies in a bit serial manner so that
the result has the same number of bits as the operands.
98. An apparatus for concurrently transferring messages between different
ports, comprising:
(a) a multistage interconnect network comprising a plurality of
interconnected active logic switch nodes;
(b) each switch node comprising a first plurality of input ports, a second
plurality of output ports, and means for selectively connecting said input
ports to said output ports,
(c) the multistage interconnect network comprising more than log.sub.b N
stages of switch nodes, wherein b is a total number of switch node
input/output ports, N is a total number of network input ports and network
output ports, and log.sub.b N indicates a ceiling function providing the
smallest integer not less than log.sub.b N, the multistage interconnect
network providing a plurality of paths between any network input port and
network output port to enhance fault tolerance and lessen contention; and
(d) deadlock avoidance means, within each switch node, for allowing only
one routing multicast request at a time, thereby preventing deadlock
between requests.
99. The system of claim 98, wherein the deadlock avoidance means further
comprises means for allowing only one multicast request within a
supercluster at a time and for allowing a plurality of multicast requests
within different superclusters to occur at the same time.
100. A communications system, comprising:
(a) a plurality of switch nodes arranged into a multistage interconnect
network having a plurality of input and output ports, each port being
coupled to an agent to effect communication between agents through the
network;
(b) the network having more than log.sub.b N stages of interconnected
switch nodes, wherein b is a total number of switch node input/output
ports, N is the number of network input/output ports, and log.sub.b N
indicates a ceiling function providing the smallest integer not less than
log.sub.b N; and
(c) the network having a plurality of turnaround points at the highest
stage of switch nodes, the turnaround points logically differentiating
between switch nodes that load balance messages through the network from
switch nodes that direct messages to receiving agents;
(d) means for depopulating switch nodes from the highest stage to reduce
the number of turnaround points in the network, as long as at least one
path exists between every network input port and every network output
port; and
(e) the input and output ports of the switch nodes in stages adjacent the
highest stage sensing when the switch nodes in the highest stage ar
removed and disabling the input and output ports in response thereto,
thereby lowering the bandwidth of the network and lowering the cost of the
network without a loss of functionality.
101. A communications apparatus, comprising:
(a) multistage interconnect network means for intercon | | |
