Pipelined packet processor

• US 7,649,879 B2
• Filed: 04/28/2004
• Issued: 01/19/2010
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Parker, David K.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Hom, Shick
• Application Number:
  US10/835,598
• Publication Number:
  US 20050226242A1
• Time in Patent Office: 2,092 Days
• Field of Search: 370/423, 370/489
• US Class Current: 370/389
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

A pipelined packet processor is described having at least one pipeline, the at least one pipeline having one or more processing slots. Packets are assigned to available ones of the slots, and each of one or more of the assigned packets are processed during one or more cycles of processing. Upon or after a packet has undergone one or more cycles of processing, a packet classification or filtering decision is derived for the packet.

Claims

1. A pipelined packet processing system comprising:

a pipelined processor configured to

     1) provide at least one pipeline having one or more slots,

     2) assign packets to each of one or more available ones of the slots,

     3) process one or more of the assigned packets during one or more processing cycles, and

     4) derive a packet classification or forwarding decision for each of the one or more assigned packets, upon or after the one or more assigned packets have undergone one or more cycles of processing;

wherein the pipelined processor is further configured to process a packet, assigned to a slot, during a processing cycle by

     1) accessing one or more resources responsive to packet processing state data relating to the packet,

     2) retrieving data from the one or more resources, and

     3) selectively updating the packet processing state data relating to the packet responsive to the data retrieved from the one or more resources; and

the packet processing state data relating to the packet is stored in or assigned to the same slot of the pipeline as the packet, updated packet processing state data is formed from the packet processing state data after a predetermined number of processing cycles of the packet on the pipeline, where the predetermined number of processing cycles is programmable, and the processor derives the classification or forwarding decision for the packet from the updated packet processing state data for the packet after the predetermined number of processing cycles of the packet is completed.

2. The system of claim 1 wherein the one or more as signed packets are processed in sequence during a processing cycle.

3. The system of claim 1 wherein each of the one or more assigned packets undergoes a common, predetermined number of processing cycles.

4. The system of claim 1 wherein the processor is configured to fill one or more available ones of the slots with packet processing state data during a loading mode of operation, and process the packets assigned to the available slots during a subsequent processing mode of operation that commences after the loading mode of operation.

5. The system of claim 1 wherein the processor is configured to assign packets to available ones of the slots as obtained from a queue.

6. The system of claim 4 wherein the processor is configured to bypass available ones of the slots if and while the queue is empty.

7. The system of claim 5 wherein packet identifiers, identifying packets as stored in a buffer, are stored in the queue.

8. The system of claim 1 wherein packet processing state data relating to the packet is stored in the slot of the pipeline assigned to the packet.

9. The system of claim 8 wherein the packet processing state data as stored in the slot of the pipeline is an identifier of packet processing state data as stored in a buffer.

10. The system of claim 1 wherein the packet processing state data comprises control data.

11. The system of claim 10 wherein the packet processing state data comprises pipeline management information.

12. The system of claim 10 wherein the packet processing state data comprises static packet information.

13. The system of claim 1 wherein the packet processing state data comprises packet classification or forwarding data.

14. The system of claim 13 wherein the packet processing state data comprises priority-based packet classification or forwarding data.

15. The system of claim 12 wherein the packet processing state data comprises non-priority-based packet or forwarding data.

16. The system of claim 15 wherein the non-priority-based packet or forwarding data comprises one or more sticky flags.

17. The system of claim 1 wherein the packet processing state data comprises statistical information relating to the packet.

18. The system of claim 17 wherein the statistical information relates to each of the predetermined number of processing cycles performed on corresponding packet data for the packet.

19. The system of claim 1 wherein the packet processor is further configured to release the assigned slot after processing of the corresponding packet has been completed.

20. The system of claim 1 wherein the packet processor is configured to release the slot by unloading packet processing state data relating to the packet from the slot.

42. The system of claim 1 wherein the pipelined processor is configured to process a packet, assigned to a slot, during a processing cycle by 1) accessing a sequence control table responsive to packet processing state data relating to the packet to obtained a command, 2) deriving a key from either or both the packet processing state data or corresponding packet data responsive to the command, 3) accessing a content addressable memory (CAM) using the key to locate a matching entry having an index portion, 4) using the index portion to identify an entry in an associated RAM, 5) retrieving data from the entry of the associated RAM, and 3) selectively updating the packet processing state data relating to the packet responsive to the either or both the command and the data from the entry in the associated RAM.

21. A method, performed in, by or for a pipelined packet processor, of performing pipelined processing of one or more packets comprising the steps of:

providing at least one pipeline having one or more slots;

assigning one or more packets to one or more available ones of the slots;

processing each of the one or more assigned packets during one or more processing cycle;

processing a packet, assigned to a slot, during a processing cycle by

     1) accessing one or more resources responsive to packet processing state data relating to the packet,

     2) retrieving data from the one or more resources, and

     3) selectively updating the packet processing state data relating to the packet responsive to the data retrieved from the one or more resources;

storing or assigning the packet processing state data relating to the packet in or to the same slot of the pipeline as the packet;

deriving updated packet processing state data from the packet processing state data during a predetermined number of processing cycles of the packet on the pipeline, where the predetermined number of processing cycles is programmable;

deriving a classification or forwarding decision for the packet after the packet has undergone the predetermined number of processing cycles.

22. The method of claim 21 wherein the first processing step comprises processing each of the one or more assigned packets in sequence during a each of the one or more processing cycles.

23. The method of claim 21 wherein the first processing step comprises processing each of the one or more assigned packets for a common, predetermined number of processing cycles.

24. The method of claim 21 wherein the number of slots in the pipeline is programmable.

25. The method of claim 21 wherein the packet is assigned to the slot by storing packet processing state data relating to the packet in the one or more slots.

26. The method of claim 21 further comprising releasing the assigned slot upon or after processing of the corresponding packet has been completed.

27. The method of claim 26 wherein the step of releasing the slot comprises unloading packet processing state data from the slot.

28. The method of claim 21 further comprising assigning packets to available slots as obtained from a queue.

29. The method of claim 28 further comprising bypassing available ones of the slots if and while the queue is empty.

30. The method of claim 21 further comprising assigning the packet to the slot by storing an identifier of the packet as stored in a buffer in the slot.

31. The method of claim 25 wherein the packet processing state data stored in the slot comprises an identifier of the packet as stored in a buffer.

32. The method of claim 25 wherein the packet processing state data stored in the slot comprises control data.

33. The method of claim 32 wherein the control data comprises pipeline management data.

34. The method of claim 32 wherein the control data comprises static packet information.

35. The method of claim 21 wherein the packet processing state data comprises packet classification or forwarding data.

36. The method of claim 21 wherein the packet processing state data comprises priority-based packet classification or forwarding data.

37. The method of claim 21 wherein the packet processing state data comprises non-priority-based packet classification or forwarding data.

38. The method of claim 37 wherein the packet processing state data comprises one or more sticky flags relating to the packet.

39. The method of claim 21 wherein the packet processing state data comprises statistical data relating to the packet.

40. The method of claim 39 wherein the statistical data relates to each of the predetermined number of processing cycles performed on the corresponding packet data.

41. A system for performing pipelined processing of one or more packets comprising:

first means for providing at least one pipeline having one or more slots;

second means for assigning packets to one or more available ones of the slots, processing each of one or more of the assigned packets during one or more cycles of processing; and

third means for processing a packet, assigned to a slot, during a processing cycle by

     1) accessing one or more resources responsive to packet processing state data relating to the packet,

     2) retrieving data from the one or more resources, and

     3) selectively updating the packet processing state data relating to the packet responsive to the data retrieved from the one or more resources;

wherein the packet processing state data relating to the packet is stored in or assigned to the same slot of the pipeline as the packet, and updated packet processing state data is formed from the packet processing state data after a predetermined number of processing cycles of the packet on the pipeline, where the predetermined number of processing cycles is programmable; and

fourth means for deriving a classification or forwarding decision for the packet upon or after the same has undergone the predetermined number of processing cycles.