Digital communication networks employing speed independent switches

• US 4,307,446 A
• Filed: 05/02/1979
• Issued: 12/22/1981
• Est. Priority Date: 05/02/1979
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Burroughs Incorporated (Terreno Realty Corp.)
• Inventors: Clark, Becky J., Barton, Robert S.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Heckler, Thomas M.
• Application Number:
  US06/035,314
• Time in Patent Office: 965 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 307/11, 307/18, 307/29, 307/38, 307/42, 307/43, 307/85, 307/112, 307/113, 307/239, 307/241, 340/147 T
• US Class Current: 710/316
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane

Abstract

An assemblage of digital devices, each having serial asynchronous input and output channels, can be connected via networks of speed independent arbiter and selector switches. Certain classes of networks have desirable properties: distributed control of routing, conflict resolution, automatic identification of source network address with respect to destination, and exploitation of permissable concurrent operations.

Claims

1. An assemblage of digital devices, each device having at least a serial asynchronous input channel and a serial asynchronous output channel for the serial transmission and reception of information in the form of a series of binary bits, said devices being interconnected via a network of a plurality of switching elements each having one or two input paths and one or two output paths where each output path is only connected to an input channel or an input path and each input path is only connected to an output channel or an output path, said plurality of elements comprising:

a first element having an input path and two output paths including means to route a message from said input path to one of its two output paths selected according to the first bit of a message on said input path, that bit then being removed; and

a second element having two input paths and an output path including means to route a message from one of said two input paths to its output path and appending a bit to the end of the message indicating the input path from which the message was received.

2. An assemblage according to claim 1 wherein:

said second element includes means to choose randomly between the two input paths in the event of conflicting requests and to continue to alternate between the two paths when requests are present on both.

3. An assemblage according to claim 1 wherein:

said first element and said second element each include means to store one bit of information so as to permit pipelining of messages and concurrent establishments of paths.

4. An assemblage according to claim 1 further including:

a sufficient number of said first and second elements such that each device can send messages to and receive messages from every other such device.

5. An assemblage according to claim 1 further including:

a second first element, said a first element and second first element being coupled together to form a tree network having at least one root node and a plurality of leaf nodes such that a message with a prefixed binary address will be routed from the root node of the tree to the addressed leaf node of the tree.

6. An assemblage according to claim 5 further including:

a second second element wherein said a second element and said second second element are coupled together to form a tree network having at least one root node and a plurality of leaf nodes such that a message will be routed from a leaf node of the tree network to the root node, generating a suffixed binary address which identifies the sending leaf node.

7. An assemblage according to claim 6 wherein:

said tree network of first elements and said tree network of second elements have identical forms with the respective root nodes of each tree network being connected to a device to be shared by a plurality of devices and the corresponding leaf nodes, of the respective tree networks, are coupled together.

8. An assemblage of digital devices, each device having at least a serial asynchronous input channel and a serial asynchronous output channel for the serial transmission and reception of information in the form of a series of binary bits, said devices being interconnected via a tree network of a plurality of switching elements each having an input path and two output paths whereby each input path is only connected to an output channel or an output path and each output path is only connected to an input channel or input path, said tree network having at least one root node and a plurality of leaf nodes, said plurality of switching elements comprising:

a plurality of elements each including means to route a message from its input path to one of its two output paths selected according to the first bit of a message on said input path, that bit then being removed such that a message with a prefixed binary address will be routed from a root node to the addressed leaf node.

9. An assemblage according to claim 8 further including:

a root node of said tree network not being connected to a digital device so as to be available for external connection.

10. An assemblage of digital devices, each device having at least a serial asynchronous input channel and a serial asynchronous output channel for the serial transmission and reception of information in the form of a series of binary bits, said devices being interconnected via a tree network of a plurality of switching elements each having two input paths and an output path whereby each input path is only connected to an output channel or an output path and each output path is only connected to an input channel or an input path, said tree network having at least one root node and a plurality of leaf nodes, said plurality of switching elements comprising:

a plurality of elements each including means to route a message from one of its two input paths to its output path and appending a bit to the end of that message indicating the input path from which the message was received such that a message will be routed from one of the leaf nodes to a root node with the resulting suffixed binary address identifying the sending leaf node.

11. An assemblage according to claim 10 further including:

a root node of said tree network not being connected to a digital device so as to be available for external connection.