Network switch with a parallel shared memory

• US 20020064170A1
• Filed: 08/24/2001
• Published: 05/30/2002
• Est. Priority Date: 11/29/2000
• Status: Active Grant

• 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
• Granted Patent: US 7,420,969 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• 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, said N output layer circuit input terminals corresponding to individual intermediate layer circuit output terminals of said N intermediate layer circuits.

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

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

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.

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

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.

5. The network switch of claim 1, wherein:

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.

6. The network switch of claim 1, wherein:

said intermediate layer is configured to identify a multicast demand signal in a cell and thereafter replicate said cell to produce a multicast signal.

7. A network switch, comprising:

an input layer to receive a data stream including a set of cells, each cell including data and a header to designate a destination device, said input layer including a set of input layer circuits, a selected input layer circuit of said set of input layer circuits receiving said data stream, said selected input layer circuit including a set of queues corresponding to a set of destination devices, said selected input layer circuit being configured to assign a selected cell from said data stream to a selected queue of said set of queues, said selected queue corresponding to a selected destination device specified by said header of said selected cell;

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

an output layer including a set of output layer circuits corresponding to said set of destination devices, a selected output layer circuit of said set of output layer circuits storing said selected cell prior to routing said selected cell to a selected output layer circuit output node.

8. The network switch of claim 7 wherein said selected output layer circuit includes circuitry to generate a flow control warning signal for application to said selected input layer circuit.

9. The network switch of claim 7 further comprising a line card connected to said selected input layer circuit, wherein said selected output layer circuit includes circuitry to generate a flow control warning signal for application to said line card.

10. The network switch of claim 9 wherein said line card delivers only high priority cells to said input layer circuit in response to said flow control warning signal.

11. The network switch of claim 7 wherein said selected output layer circuit includes circuitry to produce a flow control warning signal in response to output layer congestion, said flow control warning signal being applied to said input layer, which produces a flow halt signal within a cell header, said intermediate layer including circuitry to identify said flow halt signal and alter the delivery of cells to said output layer.

12. The network switch of claim 7 wherein said input layer includes circuitry to identify cell priority values within cell headers.

13. The network switch of claim 12 wherein said input layer alters delivery of cells in response to said cell priority values.

14. The network switch of claim 7 wherein said input layer is operative in a normal mode to deliver data cells to each of said intermediate layer circuits and is alternately operative in a fault mode to deliver cells to a subset of said intermediate layer circuits that remain operative.

15. The network switch of claim 7 wherein said intermediate layer is operative in a normal mode to deliver data cells to each of said output layer circuits and is alternately operative in a fault mode to deliver cells to a subset of said set of output layer circuits that remain operative.

16. The network switch of claim 7 wherein said intermediate layer includes multicast circuitry to identify a multicast command signal within a multicast cell and replicate said multicast cell in response to said multicast command signal.

17. The network switch of claim 7 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.

18. The network switch of claim 17 wherein 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.

19. The network switch of claim 7 wherein said intermediate layer processes cells without communicating between said intermediate layer circuits.

20. The network switch of claim 7 wherein said set of intermediate layer circuits process cells in accordance with a link skew value and synchronization skew value.

21. The network switch of claim 7 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.

22. A network switch, comprising:

an input layer including N input circuits each coupled to an input port and having N buffers therein corresponding to N output terminals;

an intermediate layer including N intermediate circuits each having N input terminals and N output terminals, where the first output terminal of each input circuit is coupled to the first intermediate circuit and the Nth output terminal of each input circuit is coupled to the Kth intermediate circuit, where K={1, 2, . . . N}; and

an output layer including N output circuits each having N input terminals and an output port, where the first output terminal of each intermediate circuit is coupled to the first output circuit and the Nth output terminal of each intermediate circuit is coupled to the Lth output circuit, where L={1, 2, . . . N}.

23. The network switch of claim 22, wherein each input circuit includes:

a sorting circuit coupled to the input port and configured to sort incoming data cells by destination;

N queues coupled to the sorting circuit and configured to store a plurality of data cells; and

a transposer circuit coupled to the N queues and the N output terminals and configured to transpose the cells stored in a selected queue and to selectively communicate the cells to the N output terminals.

24. The network switch of claim 22, wherein each intermediate circuit includes:

a sorting circuit coupled to the input terminals and configured to sort incoming data cells by destination;

N buffers coupled to the sorting circuit and configured to store a plurality of data cells; and

Wherein the N buffers are respectively coupled to the N output terminals and configured to selectively communicate the cells to the N output terminals.

25. The network switch of claim 22, wherein each output circuit includes:

a transposer circuit coupled to the N input terminals and configured to transpose data cells received on the N input terminals; and

a queue coupled to the transposer and the output port and configured to selectively communicate the cells to the output port.

27. The network switch of claim 26, wherein each input layer circuit includes:

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.

28. The network switch of claim 26, wherein each intermediate layer circuit includes:

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.

29. The network switch of claim 26, wherein each output layer circuit includes:

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.

26. 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, said N output layer circuit input terminals corresponding to individual intermediate layer circuit output terminals of said N intermediate layer circuits;

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.

30. 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.

31. The network switch of claim 30, wherein said transposer circuit transposes said cells stored in said N queues for parallel delivery to said N output terminals.

32. The network switch of claim 30 further comprising 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.

33. The network switch of claim 32 further comprising 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, said N output layer circuit input terminals corresponding to individual intermediate layer circuit output terminals of said N intermediate layer circuits.

35. The network switch of claim 34 wherein each intermediate layer circuit includes 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.

37. The network switch of claim 36 wherein each output layer circuit includes:

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, said output layer circuit queue producing said serial cell stream.

39. The method of claim 38 further comprising duplicating said selected packet when said header specifies that said selected packet is a multicast packet.

40. The method of claim 39 wherein duplicating is performed at said selected intermediate layer circuit.

41. The method of claim 38 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.

34. A network switch, comprising:

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, said N intermediate layer circuits asynchronously receiving cells at said intermediate layer circuit input terminals and asynchronously delivering cells to said intermediate layer circuit output terminals.

36. A network switch, comprising:

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, each output layer circuit asynchronously receiving cells at said N output layer circuit input terminals and producing a serial cell stream at said output layer circuit output port.

38. A method of routing network traffic, comprising:

receiving a data stream of cells 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 from said input layer to a selected intermediate layer circuit within a set of intermediate layer circuits, said routing including routing said selected cell to a specified buffer within said selected intermediate layer circuit that corresponds to said destination device of said selected cell; and

delivering said selected cell from said selected intermediate layer circuit 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.

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

receiving a data stream with a set of cells, 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;

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

sending said selected cell 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 prior to delivering said selected cell to an output node.

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

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

45. The method of claim 44 wherein said duplicating is performed at said selected intermediate layer circuit.

46. The method of claim 42 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.

47. The method of claim 42 further comprising:

generating a flow control signal 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 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.

48. The method of claim 42 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 an original set of intermediate layer circuits become inoperative.

49. The method of claim 42 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 an original set of output layer circuits become inoperative.

50. The method of claim 42 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.