Cell-based switch fabric with inter-cell control for regulating packet flow

• US 6,990,097 B2
• Filed: 06/01/2001
• Issued: 01/24/2006
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Callahan Cellular LLC (Intellectual Ventures LLC)
• Original Assignee: 4536631 Canada Incorporated (Lowe's Cos., Inc.)
• Inventors: Norman, Richard S., Haughey, John, De Maria, Marcelo, Langlois, Carl, Boudreault, Yves, Côté, Sébastien
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US09/870,767
• Publication Number:
  US 20020181455A1
• Time in Patent Office: 1,698 Days
• Field of Search: 370/386, 370/387, 370/388, 370/389, 370/359, 370/360, 370/401, 710/100, 710/317, 340/2.28, 340/2.29
• US Class Current: 370/386
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/1553 Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/503 Policing

Abstract

A switch fabric implemented on a chip includes an array of cells and an I/O interface in communication with the array of cells for permitting exchange of data packets between the array of cells and components external to the array of cells. Each cell communicates with at least one other cell of the array, permitting an exchange of data packets between the cells of the array and an exchange of control information between the cells of the array. Each cell is operative to control transmission of data packets to other cells of the array at least in part on a basis of the control information. The control information is thus used to regulate the flow of data packets between cells.

Claims

1. A switch fabric implemented on a chip, comprising:

a) an array of cells, each cell communicating with at least one other cell of said array,

b) an I/O interface in communication with said array of cells for permitting exchange of data packets between said array of cells and components external to said array of cells;

wherein said array of cells includes;

a) a plurality of data channels for transporting data packets between the cells of said array; and

b) for each individual cell of said array, a respective plurality of control channels distinct from said data channels for conveying control information to said individual cell of said array, the respective plurality of control channels conveying control information from respective cells of said array;

c) each cell operative to control transmission of data packets to other cells of said array at least in part on a basis of the control information conveyed thereto.

2. A switch fabric as defined in claim 1, wherein each of the channels of the plurality of control channels interconnects two cells of said array.

3. A switch fabric as defined in claim 2, wherein each cell of said array includes:

a) a transmitter in communication with said I/O interface and in communication with every other cell of said array, said transmitter operative to process a data packet received from said I/O interface to determine a destination of the data packet and forward the data packet to at least one cell of said array selected on a basis of the determined destination;

b) a plurality of receivers associated with respective cells of said array, each receiver being in communication with a respective cell allowing the respective cell to forward data packets to the receiver;

c) said receivers in communication with said I/O interface for releasing data packets to said I/O interface.

4. A switch fabric as defined in claim 3, wherein each data channel of said plurality of data channels is associated with a given cell of said array, the data channel associated with said given cell connecting the transmitter of said given cell to receivers in cells other than said given cell and associated with said given cell.

5. A switch fabric as defined in claim 3, wherein each data channel of said plurality of data channels is associated with a given cell of said array, the data channel associated with said given cell connecting the transmitter of said given cell to a receiver in every cell of said array of cells and associated with said given cell.

6. A switch fabric as defined in claim 5, wherein the plurality of data channels are independent from one another, wherein transmission of a data packet over one data channel is made independently of transmission of a data packet over another data channel.

7. A switch fabric as defined in claim 6, wherein each data channel performs a parallel data transfer.

8. A switch fabric as defined in claim 7, wherein the transmitter of said given cell includes a memory for storing data packets received from said I/O interface.

9. A switch fabric as defined in claim 8, wherein said memory includes a plurality of segments, each segment being associated with a receiver in a cell of said array to which the transmitter of said given cell is capable of forwarding a data packet via a data channel from said plurality of data channels.

10. A switch fabric as defined in claim 9, wherein the transmitter of said given cell includes a control entity, said control entity being operative to process a data packet forwarded from said I/O interface to determine a cell of said array to which the data packet is destined and identify on a basis of the determined cell a segment of said memory in which the packet is to be loaded.

11. A switch fabric as defined in claim 10, wherein said control entity includes a plurality of queue controllers associated with respective segments of said memory.

12. A switch fabric as defined in claim 11, wherein said memory implements a plurality of registers, each register being associated with a queue controller and being suitable for holding data representative of a degree of occupancy of a segment of said memory associated with the queue controller.

13. A switch fabric as defined in claim 12, wherein a data packet received by said transmitter from said I/O interface is characterized by a priority level selected in a group of priority levels, each segment of said memory being partitioned into slots, each slot capable of storing at least one data packet, each slot being associated with a given priority level of said group of priority levels.

14. A switch fabric as defined in claim 13, wherein the registers of said memory associated with each queue controller store data indicative of a degree of occupancy of the slots of said segment associated with the queue controller, for each priority level of the group of priority levels.

15. A switch fabric as defined in claim 14, wherein said memory is a first memory;

wherein each cell includes a second memory, said second memory being divided into a plurality of sectors corresponding to respective ones of the receivers associated with the cell, said sectors capable of storing data packets forwarded to the receivers; and

wherein the control information is passed between said control entity and each receiver associated with said given cell and is indicative of a degree of occupancy of the sector corresponding to each receiver associated with said given cell.

16. A switch fabric as defined in claim 15, wherein said control entity communicates with each receiver associated with said given cell via a channel from said plurality of control channels to receive the control information.

17. A switch fabric as defined in claim 16, wherein said plurality of control channels are back channels, there being a dedicated back channel between said control entity and respective receivers associated with said given cell.

18. A switch fabric as defined in claim 17, wherein each back channel transfers data serially.

19. A switch fabric as defined in claim 18, wherein said first memory includes an area for storing data derived from the control information, indicative of the degree of occupancy of the sectors of receivers associated with said given cell.

20. A switch fabric as defined in claim 19, wherein said control entity is operative to process the data derived from the control information to determine which data packet stored in said first memory is suitable for transmission to a receiver.

21. A switch fabric as defined in claim 20, wherein when said control entity determines that a data packet is suitable for transmission, said control entity generates a control signal to request transmission of the data packet.

22. A switch fabric as defined in claim 21, wherein when said control entity determines that a plurality of data packets are suitable for transmission, said control entity generates a plurality of control signals to request transmission of the data packets, each control signal being associated with a data packet.

23. A switch fabric as defined in claim 22, wherein said control entity includes an arbiter for processing said control signals to select a data packet to transmit among the plurality of data packets suitable for transmission.

24. A switch fabric as defined in claim 23, wherein a data packet is characterized by a priority level, wherein each control signal conveys the priority level of the data packet associated with the control signal.

25. A switch fabric as defined in claim 24, wherein said arbiter selects a data packet to transmit among the plurality of data packets suitable for transmission at least in part on a basis of the priority levels of the plurality of data packets suitable for transmission.

26. A switch fabric as defined in claim 25 wherein said arbiter processes control signals to request transmission of data packets in a round robin manner.

27. A switch fabric as defined in claim 26, wherein said arbiter selects a data packet to transmit among the plurality of data packets suitable for transmission on a basis of the priority levels of the plurality of data packets suitable for transmission and on the basis of whether or not a data packet was previously submitted for transmission.

28. A switch fabric as defined in claim 15, wherein each receiver of said plurality of receivers communicates with said I/O interface.

29. A switch fabric as defined in claim 28, wherein said control entity is a first control entity, the plurality of receivers of each cell include a second control entity to regulate a release of data packets from the sectors of the receivers to said I/O interface.

30. A switch fabric as defined in claim 3, wherein each data packet comprises a plurality of words including a first word of said data packet and a last word of said data packet, wherein each word comprises a field indicative of whether said word is a pre-determined number of words away from said last word of said data packet.

31. A switch fabric as defined in claim 30, wherein the transmitter is operative to monitor said field in each word of each data packet forwarded to at least one cell of said array, the transmitter further being operative to begin forwarding a next data packet upon detecting that said field of a word in a packet currently being forwarded is indicative of said word being a pre-determined number of words away from the last word of said data packet currently being forwarded.

32. A switch fabric as defined in claim 3, each cell further including a central processing unit (CPU) connected to the transmitter, said transmitter being further operative to process a data packet received from said CPU to determine a destination of the data packet and forward the data packet to at least one cell of said array selected on the basis of the determined destination.

33. A switch fabric as defined in claim 4, each cell further including a central processing unit (CPU) connected to the transmitter, said transmitter being further operative to process a data packet received from said CPU to determine a destination of the data packet and forward the data packet to at least one cell of said array selected on the basis of the determined destination, wherein data packets received by the transmitter in a given cell from the I/O interface and from the CPU in said given cell share the data channel associated with said given cell.

34. A switch fabric as defined in claim 3, each cell further including a central processing unit (CPU) connected to the plurality of receivers, said receivers being further operative to determine whether data packets are to be released to the I/O interface or to the CPU and release said data packets accordingly.

35. A switch fabric as claimed in claim 34, wherein each data packet comprises a field indicative of whether the data packet is destined for a CPU and wherein said receivers are operative to determine whether data packets are to be released to the I/O interface or to the CPU on the basis of said field.

36. A switch fabric as defined in claim 22, each cell further including a central processing unit (CPU) connected to the plurality of receivers, wherein said control entity includes a first arbiter for processing said control signals to select a data packet to transmit to the I/O interface among the plurality of data packets suitable for transmission to the I/O interface, wherein said control entity includes a second arbiter for processing said control signals to select a data packet to transmit to the CPU among the plurality of data packets suitable for transmission to the CPU.