OUTPUT QUEUED SWITCH WITH A PARALLEL SHARED MEMORY, AND METHOD OF OPERATING SAME

• US 20110085553A1
• Filed: 11/15/2010
• Published: 04/14/2011
• Est. Priority Date: 11/29/2000
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: YANG, Brian Hang Wai, SIU, Kai-Yeung (Sunny), RAHMAN, Mizanur M.
• Granted Patent: US 8,711,849 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5627 Fault tolerance and recovery
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/153 ATM switching fabrics having parallel switch planes
• CPC Class Codes: H04L 49/60 Software-defined switches
• CPC Class Codes: H04L 49/606 Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

Abstract

A network switch includes an input layer to receive a data stream with a set of cells. Each cell includes data and a header to designate a destination device. The input layer includes a set of input layer circuits. A selected input layer circuit of the set of input layer circuits receives the data stream. The selected input layer circuit includes a set of queues corresponding to a set of destination devices. The selected input layer circuit is configured to assign a selected cell from the data stream to a selected queue of the set of queues. The selected queue corresponds to a selected destination device specified by the header of the selected cell. An intermediate layer includes a set of intermediate layer circuits, each intermediate layer circuit has a set of buffers corresponding to the set of destination devices. A selected intermediate layer circuit of the set of intermediate layer circuits receives the selected cell and assigns the selected cell to a selected buffer corresponding to the selected destination device. An output layer includes a set of output layer circuits corresponding to the set of destination devices. A selected output layer circuit of the set of output layer circuits stores the selected cell prior to routing the selected cell to a selected output layer circuit output node.

Claims

1-4. -4. (canceled)

5. A method of routing data packets, comprising:

receiving a serial data stream with a set of cells, each cell including data and a header designating a respective destination port that the data is intended for, at a first input layer port of a first input layer circuit, said first input layer circuit being a part of an input layer comprising a plurality of input layer circuits, each input layer circuit comprising a sorting circuit and a plurality of queues, each queue corresponding to a destination port in a one to one correspondence;

routing a first cell of said set of cells, said first cell having a header designating a first destination port, to a first queue of said first input layer circuit corresponding to said first destination port;

routing said first cell from said first queue to a first intermediate layer circuit of an intermediate layer comprising a plurality of intermediate layer circuits, each intermediate layer circuit comprising a sorting circuit and a plurality of buffers, each buffer corresponding to a destination port in a one to one correspondence,

assigning said first cell to a first buffer of said first intermediate layer circuit, said first buffer corresponding to said first destination port; and

routing said first cell from said first buffer to a first output layer circuit of an output layer, said first output layer comprising said first destination port, said output layer comprising a plurality of output layer circuits, each output layer circuit comprising a destination port in a one to one correspondence.

6. The method of claim 5, wherein said step of routing said first cell from said first queue to a first intermediate layer circuit is initiated when said first queue is filled with a predetermined number of cells.

7. The method of claim 5, wherein said step of routing said first cell from said first queue to a first intermediate layer circuit of an intermediate layer comprising a plurality of intermediate layer circuits comprises transposing a queue of a plurality of serially received cells in said first queue, including said first cell, into a parallel format and routing each of said plurality of serially received cells in parallel to a different one of said plurality of intermediate layer circuits, each intermediate layer circuit assigning the respective cell routed to it to a buffer corresponding to the respective destination port of the respective cell.

8. The method of claim 7, wherein said step of routing said first cell from said first buffer to a first output layer circuit further comprises routing each of the plurality of cells in the respective buffers to a respective output layer circuit of said output layer without reading said header designating the respective destination port of each cell, the respective output layer circuit comprising the respective destination port for each respective cell routed to it.

9. The method of claim 8, further comprising the step of:

transposing, at said respective output layer circuits, said cells routed to said respective output layer circuits, from a parallel format to a serial format, prior to delivering said cells to the respective destination port.

10. The method of claim 5, wherein said step of routing said first cell from said first buffer to a first output layer circuit of an output layer is performed without referencing said header designating said first destination port.

11. The method of claim 5, further comprising the step of:

duplicating said first cell when said header of said first cell specifies that said first cell is a multicast cell.

12. The method of claim 5, further comprising the step of:

routing said first cell to a dedicated high priority traffic intermediate layer circuit if said header of said first cell specifies that said first cell has a high priority.

13. The method of claim 6, wherein said predetermined number is based upon criteria selected from the group consisting of:

a fixed number, input queue size, whether any cell in a queue is older than a predetermined threshold, cell header information, priority of a cell, status of a queue of the output layer, and quality of service data.

14. The method of claim 5, wherein said input layer, said intermediate layer, and said output layer are formed on a single semiconductor substrate.

15. A switch for routing data, comprising:

an input layer including a plurality of input layer circuits, each input layer circuit including an input layer circuit input port and a plurality of queues corresponding to a plurality of destination ports in a one to one correspondence, wherein each input layer circuit is configured to;

receive a serial data stream with a set of cells, each cell including data and a header designating a respective destination port for said data

route each cell to a respective queue corresponding to the respective destination port for each cell; and

route each cell from its respective queue to a buffer in an intermediate layer circuit corresponding the respective destination port for each cell;

an intermediate layer including a plurality of intermediate layer circuits, each intermediate layer circuit including a plurality of buffers, each buffer corresponding to one of said destination ports in a one to one correspondence, each intermediate layer circuit operably coupled to each said input layer circuit and a plurality of output layer circuits, wherein each intermediate layer circuit is configured to

assign each cell received from a queue to a respective buffer of said plurality of buffers corresponding to the respective destination port of each cell; and

route each cell from its respective buffer to a respective output layer circuit corresponding to the respective destination port of each cell; and

an output layer including a plurality of output layer circuits, each output layer circuit including a single destination port.

16. The switch of claim 15, wherein each input layer circuit further comprises:

a sorting circuit for routing incoming cells to a respective queue corresponding to the respective destination port for each cell; and

a transposer circuit configured to transpose a queue of a plurality of serially received cells in one of said queues into a parallel format and routing each of said plurality of serially received cells in parallel to a different one of said plurality of intermediate layer circuits.

17. The switch of claim 15 wherein each output layer circuit further comprises:

a transposer configured to transpose said cells routed to said respective output layer circuits, from a parallel format to a serial format, prior to delivering said cells to the respective destination port; and

an output layer circuit queue coupled to the transposer circuit and the destination port.

18. The switch of claim 15 wherein each said intermediate layer circuit is configured to assign each cell received from a queue to a respective buffer of said plurality of buffers corresponding to the respective destination port of each cell without referencing said header designating said first destination port.

19. The switch of claim 15, wherein the switch is configured such that the stop of routing each cell from its respective queue to a buffer in an intermediate layer circuit corresponding to the respective destination port for each cell is initiated when the respective queue reaches a specified volume level.

20. The switch of claim 15, wherein the switch is configured to duplicate a cell when the header of such cell specifies that the cells is a multicast cell.

21. The switch of claim 15, wherein said input layer, said intermediate layer, and said output layer are formed on a single semiconductor substrate.

22. The switch of claim 15, wherein the switch is configured to route a cell from its respective queue to a buffer of an intermediate layer circuit, wherein the intermediate layer circuit is an intermediate layer circuit that remains operative after one or more of intermediate layer circuits becomes inoperative.

23. The switch of claim 19, wherein said specified volume is based upon criteria selected from the group consisting of:

a fixed number, input queue size, whether any cell in a queue is older than a predetermined threshold, cell header information, priority of a cell, status of a queue of the output layer, and quality of service data.

24. The switch of claim 16 wherein each output layer circuit further comprises:

a transposer configured to transpose said cells routed to said respective output layer circuits, from a parallel format to a serial format, prior to delivering said cells to the respective destination port; and

an output layer circuit queue coupled to the transposer circuit and the destination port.