Wire-speed packet management in a multi-pipeline network processor

1. A network processor for maintaining processing order of data packets in a process flow, the network processor comprising:

a packet input queue, each packet in said queue having a unique flow-identification;

a plurality of pipeline units having respective inputs and outputs disposed within the network processor, each pipeline unit (PU) capable of accepting a received packet from the packet input queue and comprising a predetermined number of pipeline stages for processing the received packet by the network processor, wherein the number of pipeline stages is at least two;

multiple flow-identification content addressable memories (FICAM), each said FICAM associated with a respective PU and comprising a number of locations, equal to the number of pipeline stages in said respective PU, for accepting respective flow-identifications of packets being processed by the pipeline stages of said respective PU; each said FICAM including:

a row of content addressable memory (CAM) cells operative to store a first flow-identification, the first flow-identification corresponding to a first packet dispatched for processing by a PU; and

a comparison unit operative:

to compare a second flow-identification corresponding to a second packet with contents of said row of CAM cells;

to make a determination if the second flow-identification is same as the first flow-identification;

to generate a hit message if said second flow-identification is the same as the first flow-identification; and

to generate a miss message when none of said multiple FICAM comparison units generate a hit message; and

a controller, responsive to said hit message, operative to reschedule said second packet such that said second packet is not placed in a PU until said miss message is generated, to maintain processing order of said first and said second packets.

2. The network processor of claim 1 , wherein at least one of said pipeline units is capable of transferring the received packet upon completion of processing by the at least one PU to a second PU of said network processor along with the received packet'flow-identification.

3. The network processor of claim 1 , wherein said comparison unit is capable of comparing a range of flow-identification values.

4. The network processor of claim 1 , wherein upon generating said hit message said FICAM further provides information on a stage of said PU to which said hit message corresponds.

5. The network processor of claim 4 , wherein said stage indication is used to reschedule the processing of the second packet.

6. The network processor of claim 1 , wherein said FICAM is integrated into an integrated circuit (IC).

7. The network processor of claim 1 , wherein at least one of said pipeline units is capable of processing at least one of: layer seven pay-per-click, layer three and layer four counting, layer five metering.

8. The network processor of claim 1 , said controller being capable of dispatching a packet upon receiving a miss indication from all of said flow-identification content addressable memories and rescheduling said packet upon receiving a hit indication from at least one of said flow-identification content addressable memories.

9. The network processor of claim 8 , wherein said rescheduling comprises comparing the flow-identification of the received packet and the contents of said FICAM in a later cycle.

10. The network processor of claim 1 , wherein said FICAM is configured to remove said flow-identification of said packet from said FICAM upon completion of processing of the packet by said respective PU.

11. The network processor of claim 4 , wherein each time the processing of the received packet moves to a next pipeline stage, the flow-identification of the packet moves to a next location in said FICAM.

12. A method for maintaining processing order of data packets in a process flow, the method comprising:

receiving packets in a packet input queue, each packet in said queue having a unique flow-identification and a packet order;

providing a network processor having a plurality of pipeline units therein, each pipeline unit (PU) having an input and an output disposed within the network processor, and being capable of accepting a newly-received packet from the packet input queue and comprising a predetermined number of pipeline stages for processing the newly-received packet by the network processor, wherein the number of pipeline stages is at least two;

associating flow-identification content addressable memories (FICAM) with the pipeline units, such that each said FICAM is associated with a respective PU and comprises a number of locations equal to the number of pipeline stages in said respective PU, for accepting respective flow-identifications of packets being processed by the pipeline stages of said respective PU; and

dispatching said newly-received packet for processing in the network processor by one or more of said pipeline units responsively to a comparison between the flow-identification of the received packet and contents of said FICAM,

said dispatching said newly-received packet including:

storing a previously-received flow-identification in one of the locations in said FICAM, the previously-received flow-identification corresponding to a previously-received packet dispatched for processing by a pipeline unit (PU); and

comparing a newly-received flow-identification corresponding to said newly-received packet with said contents of said FICAM;

determining whether said newly-received flow-identification is same as said previously-received flow-identification;

generating a hit message upon said determining that said newly-received flow-identification is the same as said previously-received flow-identification; and

generating a miss message if no comparison of any FICAM generates a hit message; and

upon generating a hit message, rescheduling said newly-received packet such that said newly-received packet is not placed in a PU until said miss message is generated, to maintain processing order of said newly-received and said previously-received packets.

13. The method of claim 12 , and comprising transferring the newly-received packet upon completion of processing by at least one of said pipeline units to a second PU with the newly-received packet's flow-identification.

14. The method of claim 12 , wherein generating said hit message comprises providing information on a stage of said PU to which said hit message corresponds.

15. The method of claim 14 , wherein dispatching said newly-received packet comprises rescheduling the processing of the newly-received packet responsively to said stage indication.

16. The method of claim 14 , wherein each time the processing of the newly-received packet moves to a next pipeline stage, the flow-identification of the newly-received packet moves to a next location in said FICAM.

17. The method of claim 12 , wherein comparing said newly-received flow-identification comprises comparing a range of flow-identification values.

18. The method of claim 12 , wherein dispatching said newly-received packet comprises processing said newly-received packet in at least one of said pipeline units so as to perform at least one of: layer seven pay-per-click, layer three and layer four counting, layer five metering.

19. The method of claim 12 , wherein rescheduling said newly-received packet comprises comparing the flow-identification of the newly-received packet and the contents of said FICAM in a later cycle.

20. The method of claim 12 , further comprising removing a flow-identification of a packet from a FICAM upon completion of processing of the packet by a PU.