Multi-slice network processor

• US 7,486,678 B1
• Filed: 07/03/2003
• Issued: 02/03/2009
• Est. Priority Date: 07/03/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Greenfield Networks LLC (Cisco Systems, Inc.)
• Inventors: Torabi, Majid, Heaton, Richard J., Petersen, Brian A., Belur, Harish P., Devanagondi, Harish R.
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Wu; Jianye
• Application Number:
  US10/612,889
• Time in Patent Office: 2,042 Days
• Field of Search: 370/230, 370/389, 370/229, 370/429, 370/394, 370/395.1, 370/396
• US Class Current: 370/394
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/252 Store and forward routing
• 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/3072 Packet splitting
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets

Abstract

A multi-slice network processor processes a packet in packet slices for transfer over a multi-port network interface such as a switch fabric. The network processor segments a packet into cells having a target size. A group of cells of a common packet form a packet slice which is independently processed by one of a number of parallel processing and storage slices. Load balancing may be used in the selection of processing slices. Furthermore, the network processor may load balance slices across the multi-port network interface to one or more destination slices of another network processor. The multi-slice processor uses post header storage delivery on ingress processing to the multi-port interface thereby reducing temporary storage requirements. The multi-slice network processor may also utilize sequence numbers associated with each packet to ensure that prior to transmission onto a destination network, the packet is in the correct order for a communication flow.

Claims

1. In a multi-slice network processor system comprising a plurality of processing slice modules, each module processing and storing a slice of packet data, a method for processing a packet in packet slices for transfer over a network interface comprising:

prepending a system header to the packet, the system header providing information for use by the multi-slice system, the information comprising a sequence number;

assigning a packet identifier to the packet;

segmenting data of the packet into cells, the data including both header and body data for the packet;

generating cell descriptive information for each cell, the cell descriptive information including the packet identifier, and a packet position indicator indicating an order position of data of the cell with respect to the packet;

delivering one or more cells of the packet to one or more processing slice modules based upon load balancing criteria;

storing one or more cells in a buffer in the packet slice;

generating a buffer correlation data structure correlating the buffer of the packet slice to the packet, wherein the buffer correlation data structure is a linked list of buffer identifiers;

maintaining an independent set of upper bits of a sequence number for each communication flow; and

incrementing the independent set of upper bits for the respective communication flow, concatenating the set of upper bits with a set of bits of a sequence number in the system header into an index, indexing into a re-sequencing buffer space of sufficient depth to cover a slice-to-slice skew case based on the index, and resequencing the packet into its sequence order position responsive to one of the processing slices delivering a packet having a sequence number that is smaller in value than a sequence number for an immediately preceding packet for the same slice.

2. The method of claim 1 wherein load balancing criteria includes that no load balancing is in effect.

3. The method of claim 1 wherein the packet identifier is a sequence number representing an order of the packet in a communications flow and further comprising assigning a communications flow indicator to the cell descriptive information of each cell of the packet.

4. The method of claim 1 wherein the cell descriptive information further comprises a slice position indicator indicating an order position of the data of the cell with respect to a slice of data of the packet.

5. The method of claim 4 further comprising delivering body data of the packet to one or more of the processing slices ahead of the header data of the packet.

6. The method of claim 5 further comprising:

performing lookup functions for each slice of data;

determining a size of data change in header data; and

communicating the size of data change to a queue manager via an indicator in the system header.

7. The method of claim 1 further comprising generating a slice correlation data structure for the packet including a packet reference pointing to the buffer of the packet slice including the first cell of the packet, and a respective buffer indicator for the buffer in each packet slice storing the first cell in the slice for the packet.

8. The method of claim 7 further comprising entering the slice correlation data structure as a single queue entry into a queue.

9. A multi-slice network processor system comprising:

a plurality of parallel processing slices, each processing slice comprising a lookup processing module and access to a storage sub-system, the storage sub-system including a memory, the memory storing at least one group of cells of a packet in a buffer; and

a buffer manager, the buffer manager maintaining a buffer correlation data structure for correlating one or more buffers to the packet, wherein the buffer correlation data structure is a linked list of buffer identifiers, the buffer correlation data structure being stored in the memory;

a network data distribution and aggregation module for segmenting a packet received from a network into one or more packet slices, the network data distribution and aggregation module having a communication interface to each of the processing slices for communicating each packet slice;

each of the plurality of slices having a channel communication interface with the network interface over which each packet slice is directed to a destination processing slice across the network interface; and

a queuing module having an enqueuing communication interface and a de-queuing communication interface with each of the processing slices, the queuing module controlling the enqueuing and dequeuing of each of the packet slices, and determining the destination processing slice based on load balancing criteria;

wherein the queuing module is configured to maintain an independent set of upper bits of a sequence number for each communication flow;

wherein the queuing module is configured to acquire a sequence number for a packet delivered from a slice; and

wherein the queuing module is configured to increment the independent set of upper bits for a communication flow, concatenate the set of upper bits with a set of bits of the sequence number of the packet into an index, index into a re-sequencing buffer space of sufficient depth to cover a slice-to-slew case based on the index, and re-sequence the packet into its sequence order position responsive to detecting one of the processing slices delivering a packet with a sequence number that is smaller in value than sequence number for a packet immediately preceding the packet for the same slice.

10. The system of claim 9 wherein load balancing criteria includes no load balancing.

11. The system of claim 9 wherein the network interface is a switch fabric, and wherein each channel communication interface comprises a port connection with the switch fabric.

12. The system of claim 9 wherein the queuing module includes a queuing memory space, the queuing module maintaining a slice correlation data structure for correlating one or more slices of the same packet slice in a single queue entry, the slice correlation data structure being stored in the queuing memory space.

13. The system of claim 9 wherein the buffer manager comprises an ingress buffer manager including an ingress buffer memory space for each processing slice, the ingress buffer memory space for storing cells received from the respective processing slice, and an egress buffer memory space for each processing slice, the egress buffer memory space for storing cells received from the switch fabric for each respective processing