Method of extending default fixed number of processing cycles in pipelined packet processor architecture

• US 7,889,750 B1
• Filed: 12/30/2005
• Issued: 02/15/2011
• Est. Priority Date: 04/28/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Parker, David K.
• Primary Examiner(s): Patel, Jayanti K
• Assistant Examiner(s): Wyllie, Christopher T
• Application Number:
  US11/324,205
• Time in Patent Office: 1,873 Days
• Field of Search: 370/229, 370/230, 370/395.31, 370/389, 370/396, 370/440, 370/402, 712/241, 712/244, 712/205, 712/234, 712/213, 712/225
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 49/1546 using pipelined operation

Abstract

In a packet processing system, where a packet processor normally performs a fixed number of processing cycles on a packet as it progresses through a processing pipeline, a method of extending the fixed number of processing cycles for a particular packet is provided. During the processing of a packet, an extension bit associated with the packet is set to an “on” state if extended processing of the packet is needed. While the extension bit is set to that state, updating of a count, indicating the number of processing cycles that has been undertaken for the packet, is inhibited. When the extended processing of the packet has been completed, the extension bit for the packet is set to an “off” state, and the updating of the count resumed. When that count indicates the number of processing cycles the packet has undergone equals or exceeds the fixed number, the packet is exited from the pipeline.

Claims

1. In a packet processing system, a method comprising:

implementing a processing pipeline having a fixed number of processing cycles, the fixed number of processing cycles to be applied to each packet through the pipeline as a default fixed number of processing cycles;

maintaining a count of a number of processing cycles performed or remaining for each packet relative to the default fixed number of processing cycles, wherein the count of the number of processing cycles performed or remaining for each packet is maintained within a FIFO (First In First Out) buffer of the packet processing system as state data within a pointer to the corresponding packet maintained in a separate and distinct FIFO buffer having the corresponding packet buffered therein;

prior to completion of the default fixed number of processing cycles for each packet;

determining whether processing is complete for the packet or whether extended processing is required for the packet,

setting a DONE bit for the packet when processing is complete for the packet prior to completion of the default fixed number of processing cycles, and

setting an extension bit when extended processing is required for the packet in excess of the default fixed number of processing cycles for the packet;

exiting each packet from the processing pipeline having its respective DONE bit is set;

allocating excess cycles in the processing pipeline for each packet exited from the processing pipeline due to having its respective DONE bit set, to one or more packets having their respective extension bit set indicating extended processing is required for the one or more packets, wherein a quantity of excess cycles allocated corresponds to the difference between the count of the number of processing cycles performed or remaining for each packet exited from the processing pipeline due to having its respective DONE bit relative to the default fixed number of processing cycles; and

applying the excess cycles in the processing pipeline to the extended processing required for each packet having its respective extension bit set, wherein the excess cycles are applied to each packet having its respective extension bit set through a subsequent cycle of the same processing pipeline.

2. The method of claim 1 wherein the default state of the extension bit is off and wherein the default state of the DONE bit is “

off.”

3. The method of claim 1, further comprising incrementing the count if the extension bit is set to the “

off”

state, and having each packet exited from the processing pipeline once the count equals or exceeds the default fixed number of processing cycles.

4. The method of claim 1, further comprising updating the count of the number of processing cycles performed or remaining for each packet by decrementing the count, when the count indicates a number of processing cycles remaining for each packet, and having the packet exited from the pipeline once the count is less than or equal to zero and the extension bit is off.

5. The method of claim 1, further comprising:

having each packet exited from the pipeline once the done bit is set to the “

on”

state, even if the count of the number of processing cycles performed or remaining indicates the number of processing cycles the packet has undergone is less than the default fixed number of processing cycles for the processing pipeline.

6. The method of claim 5 wherein the default “

off”

state of the done bit is a logical “

0” and

the “

on”

state of that bit is a logical “

1.”

7. The method of claim 5 wherein the default “

off”

state of the done bit is a logical “

1” and

the “

on”

state of that bit is a logical “

0.”

8. The method of claim 1 wherein the packet processing system is in a router, switch, or combination router/switch.

9. The method of claim 8 wherein the packet processing system is for making a classification and forwarding decision for a packet.

10. The method of claim 8 wherein the packet processing system is implemented through ASIC technology on one or more integrated circuit chips.

11. A packet processing system comprising:

a processor;

a plurality of commands, instructions, and/or state transitions;

wherein the processor of the packet processing system to execute the plurality of commands, instructions, and/or state transitions causing the packet processing system to perform a method comprising;

implementing a processing pipeline having a fixed number of processing cycles, the fixed number of processing cycles to be applied to each packet through the pipeline as a default fixed number of processing cycles;

maintaining a count of a number of processing cycles performed or remaining for each packet relative to the default fixed number of processing cycles, wherein the count of the number of processing cycles performed or remaining for each packet is maintained within a FIFO (First In First Out) buffer of the packet processing system as state data within a pointer to the corresponding packet maintained in a separate and distinct FIFO buffer having the corresponding packet buffered therein;

prior to completion of the default fixed number of processing cycles for each packet;

determining whether processing is complete for the packet or whether extended processing is required for the packet,

setting a DONE bit for the packet when processing is complete for the packet prior to completion of the default fixed number of processing cycles, and

setting an extension bit when extended processing is required for the packet in excess of the default fixed number of processing cycles for the packet;

exiting each packet from the processing pipeline having its respective DONE bit is set;

allocating excess cycles in the processing pipeline for each packet exited from the processing pipeline due to having its respective DONE bit set, to one or more packets having their respective extension bit set indicating extended processing is required for the one or more packets; and

applying the excess cycles in the processing pipeline to the extended processing required for each packet having its respective extension bit set, wherein the excess cycles are applied to each packet having its respective extension bit set through a subsequent cycle of the same processing pipeline.

12. The packet processing system of claim 11, wherein the method performed further comprises:

updating the count of the number of processing cycles performed or remaining for each packet by decrementing the count, when the count indicates a number of processing cycles remaining for each packet; and

exiting the packet from the pipeline once the count is less than or equal to zero and the extension bit is off.

13. The packet processing system of claim 11, wherein the method performed further comprises:

exiting each packet from the pipeline once the done bit is set to the “

on”

state, even if the count of the number of processing cycles performed or remaining indicates the number of processing cycles the packet has undergone is less than the default fixed number of processing cycles for the processing pipeline.

14. A packet processing system comprising:

a packet processor to implement a processing pipeline having a fixed number of processing cycles, the fixed number of processing cycles to be applied to each packet through the pipeline as a default fixed number of processing cycles wherein the packet processor is to;

maintain a count of a number of processing cycles performed or remaining for each packet relative to the default fixed number of processing cycles, wherein the count of the number of processing cycles performed or remaining for each packet is maintained within a FIFO (First In First Out) buffer of the packet processing system as state data within a pointer to the corresponding packet maintained in a separate and distinct FIFO buffer having the corresponding packet buffered therein;

determine, prior to completion of the default fixed number of processing cycles for each packet;

whether processing is complete for the packet or whether extended processing is required for the packet,

set a DONE bit for the packet when processing is complete for the packet prior to completion of the default fixed number of processing cycles, and

set an extension bit when extended processing is required for the packet in excess of the default fixed number of processing cycles for the packet;

wherein the packet processor is to further;

exit each packet from the processing pipeline having its respective DONE bit is set;

allocate excess cycles in the processing pipeline for each packet exited from the processing pipeline due to having its respective DONE bit set, to one or more packets having their respective extension bit set indicating extended processing is required for the one or more packets; and

apply the excess cycles in the processing pipeline to the extended processing required for each packet having its respective extension bit set, wherein the excess cycles are applied to each packet having its respective extension bit set through a subsequent cycle of the same processing pipeline.

15. The packet processing system of claim 14, wherein the packet processor is to further increment the count if the extension bit is set to the “

off”

state, and having each packet exited from the processing pipeline once the count equals or exceeds the default fixed number of processing cycles.

16. The packet processing system of claim 14, wherein the packet processor is to further:

update the count of the number of processing cycles performed or remaining for each packet by decrementing the count, when the count indicates a number of processing cycles remaining for each packet, and

exit the packet from the pipeline once the count is less than or equal to zero and the extension bit is off.

17. The packet processing system of claim 14, wherein the packet processor is to further:

exit each packet from the pipeline once the done bit is set to the “

on”

state, even if the count of the number of processing cycles performed or remaining indicates the number of processing cycles the packet has undergone is less than the default fixed number of processing cycles for the processing pipeline.