Multi-threaded, multi-cast switch

• US 6,473,428 B1
• Filed: 12/31/1998
• Issued: 10/29/2002
• Est. Priority Date: 12/31/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Nichols, Stacy, Brown, David A.
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/223,836
• Time in Patent Office: 1,398 Days
• Field of Search: 370/474, 370/469, 370/395-410, 370/413, 370/399-398, 370/244, 370/416, 370/427, 370/360, 370/466, 370/401, 370/394, 370/396-397, 370/232, 370/252, 370/417, 370/412, 370/468, 370/498, 370/388-389, 370/455
• US Class Current: 370/395.1
• CPC Class Codes: H04L 2012/5678 Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
• CPC Class Codes: H04L 49/1515 Non-blocking multistage, e.g. Clos
• CPC Class Codes: H04L 49/1569 Clos switching fabrics
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3027 Output queuing

Abstract

A multi-stage switch includes a plurality of switching elements for routing cells from input components to output components. Internal switch logic routes incoming cells to the output components in the same temporal order as they are received from the input components, and sequentially activates the switching elements to distribute the cells evenly within the switch.

Claims

1. A multi-stage switch comprising:

a plurality of output circuits;

a plurality of input circuits containing cells, each of the cells being destined for at least one of the output circuits;

a plurality of pending signals, each one of the plurality of pending signals associated with one of the plurality of input circuits, for indicating a presence of a new cell at the corresponding input circuit;

a plurality of switches for receiving the cells from the input circuits and transmitting he cells to the destined ones of the output circuits; and

a scheduler circuit for causing the switches to the cells to the output circuits in essentially the same temporal order as the cells are received from the input circuits to the switches in response to plurality of pending signals.

2. The multi-stage switch of claim 1 wherein the scheduler circuit further includes

a circuit for transmitting cells from the input circuits to the switches in the same temporal order as the cells were received at the input circuit.

3. The multi-stage switch of claim 1 wherein the input circuits include

a multiplexer having a plurality of inputs for receiving data and having an output coupled to each of the switches.

4. The multi-stage switch of claim 1 wherein the output circuits each include

a demultiplexer having an input coupled to each of the switches and having a plurality of outputs.

5. The multi-stage switch of claim 4, further including

an encoder coupled to the queue selector circuit for translating an output of the queue selector circuit into a number.

6. The multi-stage switch of claim 4, further including

an encoder for receiving an eight-bit signal from a queue selector circuit and encoding the signal.

8. The multi-stage switch of claim 1 wherein the scheduler circuit includes

a queue status circuit for indicating a status associated with the input circuits;

a queue selector circuit, coupled to the queue status circuit, for selecting a particular one of the input circuits based upon the status; and

a controller circuit, coupled to the queue selector circuit, for selecting the switches in a pre-defined sequence.

10. The multi-stage switch of claim 8 wherein the queue status circuit further includes

means for determining a status of arriving cells;

and

means for broadcasting the status.

11. The multi-stage switch of claim 10 wherein the means for determining the status of arriving cells further includes means for determining

a source;

a destination; and

a priority for each of the cells.

7. A multi-stage switch, comprising:

a plurality of output circuits;

a plurality of input circuits containing cells, each of the cells being destined for at least one of the output circuits;

a plurality of switches for receiving the cells from the input circuits and transmitting the cells to the destined ones of the output circuits;

a scheduler circuit for causing the switches to transmit the cells to the output circuits in essentially the same temporal order as the cells are received from the input circuits to the switches, wherein the scheduler circuit includes;

means for determining whether a cell is pending after a cell has been transmitted; and

means for transferring a pending cell to the next stage.

9. A multi-stage switch, comprising:

a plurality of output circuits;

a plurality of input circuits containing cells, each of the cells being destined for at least one of the output circuits;

a plurality of switches for receiving the cells from the input circuits and transmitting the cells to the destined ones of the output circuits;

a scheduler circuit for causing the switches to transmit the cells to the output circuits in essentially the same temporal order as the cells are received from the input circuits to the switches, wherein the scheduler circuit includes

a queue status circuit for indicating a status associated with the input circuits;

a queue selector circuit, coupled to the queue status circuit, for selecting a particular one of the input circuits based upon the status wherein the queue selector circuit includes

an input signal indicating an output port selected by a previous stage;

an input signal indicating which second-stage switch should be traversed for a given output; and

an input signaling indicating that an output queue has a cell to be transmitted to the second-stage, but that the second-stage is not active; and

a controller circuit, coupled to the queue selector circuit, for selecting the switches in a pre-defined sequence.

12. A multi-stage switch, comprising:

a plurality of output circuits;

a plurality of input circuits containing cells, each of the cells destined for at least one of the output circuits;

a plurality of switches for transmitting the cells from the input circuits to the destined ones of the output circuits; and

a scheduler circuit for transmitting the cells from the input circuits to the switches based upon a “

pending status” and

a “

previous status”

of cells within the input circuits.

13. The multi-stage switch of claim 12 wherein the input circuits each include

a multiplexer having a plurality of inputs for receiving data and having an output coupled to each of the switches.

14. The multi-stage switch of claim 12 wherein the output circuits each include

a demultiplexer having an input coupled to each of the switches and having a plurality of outputs.

15. The multi-stage switch of claim 12 wherein the scheduler circuit includes:

a queue status circuit for indicating the pending status and the previous status;

a queue selector circuit coupled to the queue status circuit for selecting a particular one of the input circuits based upon the pending status and the previous status; and

a circuit coupled to the queue selector circuit for sequentially selecting the switches.

16. The multi-stage switch of claim 15, further including

an encoder coupled to the queue selector circuit for translating an output of the queue selector circuit into a number.

17. A method of transmitting cells through a multi-stage switch, comprising:

queuing a plurality of cells in a plurality of input circuits, each of the cells being destined for at least one of a plurality of output circuits; and

transmitting each of the cells, through a plurality of switches, from the one of the input circuits containing that cell to the ones of the output circuits for which the cell is destined by routing the cells in essentially the same temporal order as the cells are transmitted from the input circuits to the switches.

18. The method of claim 17 wherein queuing includes

receiving data in a multiplexer having a plurality of inputs and having an output coupled to each of the switches.

19. The method of claim 17, wherein transmitting includes

receiving data in a demultiplexer having an input coupled to each of the switches and having a plurality of outputs.

20. The method of claim 17 wherein transmitting includes

indicating a status associated with the input circuits;

selecting a particular one of the input circuits based upon the status; and

sequentially selecting the switches.

21. The method of claim 20, further including

assigning a number to the selection of the input circuit.

22. A method of transmitting cells through a multi-stage switch, comprising:

queuing a plurality of cells in a plurality of input circuits, each of the cells being destined for at least one of a plurality of output circuits; and

transmitting the cells through a plurality of switches from a particular one of the input circuits containing that cell to the ones of the output circuits for which the cell is destined, by routing the cells based upon a pending status and a previous status of cells within the queues of the input circuits.

23. The method of claim 22 wherein queuing includes

receiving data in a multiplexer having a plurality of inputs and having an output coupled to each of the switches.

24. The method of claim 22, wherein transmitting includes

receiving data in a demultiplexer having an input coupled to each of the switches and having a plurality of outputs.

25. The method of claim 22 wherein transmitting includes

sequentially selecting the switches.

26. The method of claim 25, further including

assigning a number to the selection of the input circuit.