Network switch with a parallel shared memory

• US 7,420,969 B2
• Filed: 08/24/2001
• Issued: 09/02/2008
• Est. Priority Date: 11/29/2000
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: RMI Corporation (Broadcom, Inc.)
• Inventors: Rahman, Mizanur M., Siu, Kai-Yeung (Sunny), Yang, Brain Hang Wai
• Primary Examiner(s): Backer; Firmin
• Assistant Examiner(s): NGUYEN, PHUONGCHAU BA
• Application Number:
  US09/939,454
• Publication Number:
  US 20020064170A1
• Time in Patent Office: 2,566 Days
• Field of Search: 370/388, 370/390, 370/228, 370/231, 370/236.1, 370/396, 370/398, 370/395.1, 370428-429, 370/395.32, 370/395.42
• US Class Current: 370/388
• 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 method of routing network traffic, comprising;

receiving a serial data stream of cells or data packets at an input layer, each cell of said data stream of cells including data and a header to designate a destination device;

routing a selected cell to a specified queue that corresponds to said destination device of said selected cell,

and filling said queue with a predetermined number of cells, forming a queue of serially received cells; and

when said predetermined number of cells is reached, transposing said serially received cells into an alternative parallel format in which all of said serially received cells in said queue may be accessed on an equal basis regardless of the original order in which said serially received cells were first serially received;

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

transposing said sorted or not sorted or modified or duplicated parallel format cells back into a serial format; and

delivering said selected cell to a selected output layer circuit within a set of output layer circuits, said selected output layer circuit corresponding to said destination device of said selected cell;

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

2. The method of claim 1 further comprising duplicating said selected cell or data packet when said header specifies that said selected cell or data packet is a multicast packet.

3. The method of claim 1 wherein said routing includes routing said selected cell or data packet to a dedicated high priority traffic intermediate layer circuit when said header specifies that said selected cell or data packet has a high priority.

4. The method of claim 1, in which the cell header criteria comprise 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.

5. The method of claim 1, wherein said 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.

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

7. The method of claim 6, 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 said back pressure information.

8. A method of routing network traffic, said method comprising:

receiving a serial data stream with a set of cells or data packets, each cell including data and a header to designate a destination device;

assigning a selected cell of said set of cells to a selected queue of a set of queues within an input layer circuit, said selected cell specifying a selected destination device, said selected queue corresponding to said selected destination device;

and filling said queue with a predetermined number of cells, forming a queue of serially received cells; and

when said predetermined number of cells is reached, transposing said serially received cells into an alternative parallel format in which all of said serially received cells in said queue may be accessed on an equal basis regardless of the original order in which said serially received cells were first serially received;

routing said selected cell to a selected intermediate layer circuit within a set of intermediate layer circuits, said selected intermediate layer circuit including a set of buffers corresponding to a set of destination devices, said selected intermediate layer circuit assigning said selected cell to a selected buffer of said set of buffers, said selected buffer corresponding to said selected destination device; and

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

sending said selected cell as said selected cell arrives at said selected intermediate layer circuit to a selected output layer circuit within a set of output layer circuits, said selected output layer circuit corresponding said selected destination device, said selected output layer circuit storing said selected cell; and

transposing said sorted or not sorted or modified or duplicated parallel format cells back into a serial format;

prior to delivering said selected cell to an output node;

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

9. The method of claim 8 wherein said routing is initiated when said selected queue reaches a specified cell volume level.

10. The method of claim 8 further comprising duplicating said selected cell when said header specifies that said selected cell is a multicast cell.

11. The method of claim 10 wherein said duplicating is performed at said selected intermediate layer circuit.

12. The method of claim 8 wherein said routing includes routing said selected cell to a dedicated high priority traffic intermediate layer circuit when said header specifies that said selected cell has a high priority.

13. The method of claim 8 further comprising:

generating a flow control warning signal in response to output layer congestion at said selected output layer circuit;

forming a flow control header signal within a header of an incoming data cell in response to said flow control warning signal; and

processing said incoming data cell through said selected intermediate layer circuit and said selected output layer circuit in accordance with said flow control header signal.

14. The method of claim 8 wherein said routing includes routing said selected cell 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.

15. The method of claim 8 wherein said sending includes sending said selected cell 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.

16. The method of claim 8 wherein said sending includes sending said selected data cell from said selected intermediate layer circuit without communicating timing information with other intermediate layer circuits within said set of intermediate layer circuits.

17. 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;

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

a transposer circuit coupled to said N queues and said N output terminals, said transposer circuit being configured to transpose cells stored in said N queues for delivery to said 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;

each intermediate layer additionally including a sorting circuit to route incoming cells to said N buffers, said N buffers thereafter delivering said incoming cells to said N intermediate layer circuit output terminals; and

an output layer including N output layer circuits, each output layer circuit having a transposer circuit coupled to said N output layer circuit input terminals, said transposer circuit being configured to transpose data cells received at said N output layer circuit input terminals; and

an output layer circuit queue coupled to said transposer circuit and said output layer circuit output port;

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

18. The network switch of claim 17, in which said output layer includes an output layer circuit configured to generate a back-pressure signal representative of the status of said output layer circuit;

and said input layer includes an input layer circuit configured to be responsive to said back-pressure signal by selectively inserting flow control information into a data cell.

19. The network switch of claim 17, in which said intermediate layer is configured to identify a multicast demand signal in a cell and thereafter replicate said cell to produce a multicast signal.

20. The network switch of claim 17 wherein said input layer includes circuitry to identify cell priority values within cell headers, or in which said input layer alters delivery of cells in response to said cell priority values.

21. The network switch of claim 17 wherein said intermediate layer circuit includes a first set of buffers to process high priority traffic and a second set of buffers to process best effort traffic, or in which said output layer includes a first set of output layer circuits to process said high priority traffic and a second set of output layer circuits to process said best effort traffic.