Output queued switch with a parallel shared memory, and method of operating same

• US 7,835,334 B2
• Filed: 08/26/2008
• Issued: 11/16/2010
• Est. Priority Date: 11/29/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Yang, Brain Hang Wai, Rahman, Mizanur M., Siu, Kai-Yeung (Sunny)
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): NGUYEN, PHUONGCHAU BA
• Application Number:
  US12/198,776
• Publication Number:
  US 20080310418A1
• Time in Patent Office: 812 Days
• Field of Search: 370/228, 370/231, 370/236.1, 370/388, 370/390, 370/395.1, 370/395.32, 370/395.42, 370/396, 370/398, 370428-429
• US Class Current: 370/338
• 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. A network switch, comprising:

an input layer including N input layer circuits, each input layer circuit including an input layer circuit input port and N queues corresponding to N output terminals;

an intermediate layer including N intermediate layer circuits, each intermediate layer circuit including N buffers positioned between N intermediate layer circuit input terminals and N intermediate layer circuit output terminals; and

an output layer including N output layer circuits, each output layer circuit having N output layer circuit input terminals and an output layer circuit output port, the N output layer circuit input terminals corresponding to individual intermediate layer circuit output terminals of the N intermediate layer circuits;

wherein the input layer, the intermediate layer, and the output layer are formed on a single semiconductor substrate, the network switch being configurable to enable a first region of the single semiconductor substrate selected from the input layer, the intermediate layer and the output layer, while disabling two regions of the single semiconductor substrate selected from the input layer, the intermediate layer and the output layer.

2. The network switch of claim 1, wherein each input layer circuit includes:

a sorting circuit to route incoming cells to one of N destinations, each destination of the N destinations having a corresponding queue within the input layer circuit; and

a transposer circuit coupled to the N queues and the N output terminals, the transposer circuit being configured to transpose cells stored in the N queues for delivery to the N output terminals.

3. The network switch of claim 1, wherein each intermediate layer circuit includes:

a sorting circuit to route incoming cells to the N buffers, the N buffers thereafter delivering the incoming cells to the N intermediate layer circuit output terminals.

4. The network switch of claim 1, wherein each output layer circuit includes:

a transposer circuit coupled to the N output layer circuit input terminals, the transposer circuit being configured to transpose data cells received at the N output layer circuit input terminals; and

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

5. A network switch comprising:

an input layer circuit configured to receive a serial data stream with a set of cells or data packets, each cell including data and a header to designate a destination device, and configured to assign a selected cell of the set of cells to a selected queue of a set of queues within the input layer circuit, the selected cell specifying a selected destination device, the selected queue corresponding to the selected destination device;

an input layer sorting circuit configured to fill the queue with a predetermined number of cells, forming a queue of serially received cells;

an input layer transposer circuit configured to transpose the serially received cells into an alternative parallel format in which all of the serially received cells in the queue may be accessed on an equal basis regardless of the original order in which the serially received cells were first serially received, when the predetermined number of cells is reached;

a set of intermediate layer circuits within the set of intermediate layer circuits, the selected intermediate layer circuit including;

a set of buffers corresponding to a set of destination devices, the selected intermediate layer circuit assigning the selected cell to a selected buffer of the set of buffers, the selected buffer corresponding to the selected destination device; and

an intermediate layer sorting circuit for sorting or not sorting or modifying or duplicating parallel format cells based upon predetermined cell header criteria and/or predetermined order of cell serial arrival criteria; and

a set of output layer circuits, the selected cell being sent as the selected cell arrives at the selected intermediate layer circuit to a selected output layer circuit within the set of output layer circuits, the selected output layer circuit corresponding the selected destination device, the selected output layer circuit storing the selected cell, and selected output layer circuit including an output layer transposer circuit for transposing the sorted or not sorted or modified or duplicated parallel format cells back into a serial format, prior to delivering the selected cell to an output node;

wherein an input layer, an intermediate layer, and an output layer are formed on a single semiconductor substrate, the network switch being configurable to enable a first region of the single semiconductor substrate selected from the input layer, the intermediate layer and the output layer, while disabling two regions of the single semiconductor substrate selected from the input layer, the intermediate layer and the output layer.

6. The network switch of claim 5, wherein the routing of the selected cell to the selected intermediate layer circuit is initiated when the selected queue reaches a specified cell volume level.

7. The network switch of claim 5, wherein the selected cell is duplicated when the header specifies that the selected cell is a multicast cell.

8. The network switch of claim 7, wherein the duplicating is performed at the selected intermediate layer circuit.

9. The network switch of claim 5, wherein the routing of the selected cell to the selected intermediate layer circuit includes routing the selected cell to a dedicated high priority traffic intermediate layer circuit when the header specifies that the selected cell has a high priority.

10. The network switch of claim 5, wherein the selected cell is routed to a selected intermediate layer circuit within a subset of intermediate layer circuits that remain operative after one or more intermediate layer circuits within a previously presented set of intermediate layer circuits become inoperative.

11. The network switch of claim 5, wherein the selected cell is sent to a selected output layer circuit within a subset of output layer circuits that remain operative after one or more output layer circuits within a previously presented set of output layer circuits become inoperative.

12. The network switch of claim 5, wherein the selected data cell is sent from the selected intermediate layer circuit without communicating timing information with other intermediate layer circuits within the set of intermediate layer circuits.

13. The network switch of claim 5, wherein the cell header criteria comprises cell header criteria selected from the group consisting of packet identification, error correction coding, protocol type, Quality of Service (QoS), unicast service, broadcast service, and error conditions.

14. The network switch of claim 5, wherein the predetermined number is varied according to criteria comprising criteria selected from the group consisting of a fixed number, input queue size, how old the cells are, cell header information, priority of the cells, status of the output queues, and quality of service data.

15. The network switch of claim 5, wherein if a given destination device is blocked or partially blocked, resulting in an output queue to this device becoming overly full, then back pressure information is used to control the predetermined number, or the criteria by which cells are transposed or sorted or modified or duplicated, in order to compensate for this blockage.

16. The network switch of claim 15, wherein cells with headers indicating that the cell is high priority are transposed or sorted or modified or duplicated preferentially relative to cells with lower priority headers in response to the back pressure information.