Queueing system for processors in packet routing operations

Abstract

In a data-packet processor, a configurable queueing system for packet accounting during processing has a plurality of queues arranged in one or more clusters, an identification mechanism for creating a packet identifier for arriving packets, insertion logic for inserting packet identifiers into queues and for determining into which queue to insert a packet identifier, and selection logic for selecting packet identifiers from queues to initiate processing of identified packets, downloading of completed packets, or for requeueing of the selected packet identifiers.

What is claimed is: 
     
       1. In a data-packet processor, a configurable queuing system for packet accounting during processing, the system comprising:
 a plurality of queues arranged in one or more clusters; 
 an identification mechanism for creating packet identifiers for arriving packets, wherein each of said packet identifiers comprises:
 one or more of an identifier of a device from which an associated arriving packet was received; and 
 an indication of whether said associated arriving packet has increased or decreased in total size during processing; and 
 
 insertion logic for inserting said packet identifiers into said plurality of queues and for determining into which of said plurality of queues to insert a particular one of said packet identifiers. 
 
     
     
       2. The queuing system as recited in  claim 1 , wherein said insertion logic determines a priority for said associated arriving packet, and inserts said associated arriving packet into a particular one of said plurality of queues depending on said priority. 
     
     
       3. The queuing system as recited in  claim 2 , wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number. 
     
     
       4. The queuing system as recited in  claim 1 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for requeueing based on a value of a next queue number set in a corresponding packet identifier. 
 
     
     
       5. The queuing system as recited in  claim 1 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for downloading based on a value of an indication of whether processing on said given packet is completed. 
 
     
     
       6. The queuing system as recited in  claim 1 , wherein the data-packet processor comprises a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein selection logic therein causes header information from a given packet associated with a selected one of said packet identifiers to be loaded into an available one of said contexts. 
     
     
       7. The queuing system as recited in  claim 6 , wherein there are more of said contexts than said individual streams, and wherein loading of header information into said available one of said contexts is accomplished in background, that is, in parallel with processing of packets. 
     
     
       8. A method for accounting for packets in a data-packet processor, comprising:
 providing in the processor a plurality of queues in one or more clusters; 
 creating a packet identifier for an arriving packet, wherein said creating comprises:
 identifying a device from which the arriving packet was received; and 
 indicating whether or not the arriving packet has increased or decreased in total size during processing; and 
 
 inserting the packet identifier into one of the plurality of queues. 
 
     
     
       9. The method as recited in  claim 8 , wherein said inserting comprises:
 determining a priority for the arriving packet, and placing the arriving packet into a particular queue depending on the priority. 
 
     
     
       10. The method as recited in  claim 8 , further comprising:
 selecting packet identifiers from the plurality of queues, for initiating processing of identified packets, downloading of completed packets, or for requeueing of selected packet identifiers, wherein said requeuing is based on a value of a next queue number set in the packet identifier. 
 
     
     
       11. The method as recited in  claim 8 , further comprising:
 selecting packet identifiers from the plurality of queues, for initiating processing of identified packets, downloading of completed packets, or for requeueing of selected packet identifiers, wherein said downloading is based on a value of an indication of whether processing on the arriving packet is completed. 
 
     
     
       12. The method as recited in  claim 8 , wherein the data-packet processor is a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein the method further comprises:
 selecting packet identifiers from the plurality of queues, for initiating processing of identified packets, downloading of completed packets, or for requeueing of selected packet identifiers, wherein said selecting comprises:
 causing header information from a packet associated with a selected identifier to be loaded into an available one of the contexts. 
 
 
     
     
       13. A data packet processor, for performing accounting during packet processing, the data packet processor comprising:
 a plurality of queues arranged in one or more clusters; 
 an identification mechanism for creating packet identifiers for arriving packets, wherein each of said packet identifiers comprises:
 one or more of an identifier of a device from which an associated arriving packet was received; and 
 an indication of whether or not processing on said associated arriving packet was completed; and 
 
 insertion logic for inserting said packet identifiers into said plurality of queues and for determining into which of said plurality of queues to insert a particular one of said packet identifiers. 
 
     
     
       14. The data packet processor as recited in  claim 13 , wherein said insertion logic determines a priority for said associated arriving packet, and inserts said associated arriving packet into a particular one or said plurality of queues depending on said priority. 
     
     
       15. The data packet processor as recited in  claim 14 , wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number. 
     
     
       16. The data packet processor as recited in  claim 13 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for requeueing based on a value of a next queue number set in a corresponding packet identifier. 
 
     
     
       17. The data packet processor as recited in  claim 13 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for downloading based on said indication. 
 
     
     
       18. The data packet processor as recited in  claim 13 , wherein the data-packet processor comprises a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein selection logic therein causes header information from a given packet associated with a selected one of said packet identifiers to be loaded into an available one of said contexts. 
     
     
       19. The data packet processor as recited in  claim 18 , wherein there are more of said contexts than said individual streams, and wherein loading of header information into said available one of said contexts is accomplished in background, that is, in parallel with processing of packets. 
     
     
       20. A queuing apparatus, for performing packet accounting in a packet processor, the queuing apparatus comprising:
 a plurality of queues arranged in one or more clusters; 
 an identification mechanism for creating packet identifiers for arriving packets, wherein each of said packet identifiers comprises:
 one or more of an identifier of a device from which an associated arriving packet was received; and 
 a next queue into which said each of said packet identifiers should be inserted; and 
 
 insertion logic for inserting said packet identifiers into said plurality of queues and for determining into which of said plurality of queues to insert a particular one of said packet identifiers. 
 
     
     
       21. The queuing apparatus as recited in  claim 20 , wherein said insertion logic determines a priority for said associated arriving packet, and inserts said associated arriving packet into a particular one of said plurality of queues depending on said priority. 
     
     
       22. The queuing apparatus as recited in  claim 21 , wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number. 
     
     
       23. The queuing apparatus as recited in  claim 20 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for requeueing based on said next queue. 
 
     
     
       24. The queuing apparatus as recited in  claim 20 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for downloading based on a value of an indication of whether processing on said given packet is completed. 
 
     
     
       25. The queuing apparatus as recited in  claim 20 , wherein the packet processor comprises a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein selection logic therein causes header information from a given packet associated with a selected one of said packet identifiers to be loaded into an available one of said contexts. 
     
     
       26. The queuing apparatus as recited in  claim 25 , wherein there are more of said contexts than said individual streams, and wherein loading of header information into said available one of said contexts is accomplished in background, that is, in parallel with processing of packets. 
     
     
       27. An apparatus in a data packet processor, for performing packet accounting during packet processing, the apparatus comprising:
 a plurality of queues arranged in one or more clusters; 
 an identification mechanism for creating packet identifiers for arriving packets, wherein each of said packet identifiers comprises:
 one or more of an identifier of a device from which an associated arriving packet was received; and 
 a next queue into which said each of said packet identifiers should be inserted; and 
 
 insertion logic for inserting said packet identifiers into said plurality of queues and for determining into which of said plurality of queues to insert a particular one of said packet identifiers. 
 
     
     
       28. The apparatus as recited in  claim 27 , wherein said insertion logic determines a priority for said associated arriving packet, and inserts said associated arriving packet into a particular one of said plurality of queues depending on said priority. 
     
     
       29. The apparatus as recited in  claim 28 , wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number. 
     
     
       30. The apparatus as recited in  claim 27 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for requeueing based on said next queue. 
 
     
     
       31. The apparatus as recited in  claim 27 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for downloading based on a value of an indication of whether processing on said given packet is completed. 
 
     
     
       32. The apparatus as recited in  claim 27 , wherein the data packet processor comprises a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein selection logic therein causes header information from a given packet associated with a selected one of said packet identifiers to be loaded into an available one of said contexts. 
     
     
       33. The apparatus as recited in  claim 32 , wherein there are more of said contexts than said individual streams, and wherein loading of header information into said available one or said contexts is accomplished in background, that is, in parallel with processing of packets. 
     
     
       34. An apparatus in a packet processor, for performing packet accounting during packet processing, the apparatus comprising:
 a plurality of queues arranged in one or more clusters; 
 an identification mechanism for creating packet identifiers for arriving packets, wherein each of said packet identifiers comprises:
 one or more of an identifier of a device from which an associated arriving packet was received; and 
 an identifier of whether said associated arriving packet is currently being processed; and 
 
 insertion logic for inserting said packet identifiers into said plurality of queues and for determining into which of said plurality of queues to insert a particular one of said packet identifiers. 
 
     
     
       35. The apparatus as recited in  claim 34 , wherein said insertion logic determines a priority for said associated arriving packet, and inserts said associated arriving packet into a particular one of said plurality of queues depending on said priority. 
     
     
       36. The apparatus as recited in  claim 35 , wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number. 
     
     
       37. The apparatus as recited in  claim 34 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for requeueing based on a value of a next queue number set in a corresponding packet identifier. 
 
     
     
       38. The apparatus as recited in  claim 34 , further comprising:
 selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of selected packet identifiers, wherein said selection logic selects a given packet for downloading based on a value of an indication of whether processing on said given packet is completed. 
 
     
     
       39. The apparatus as recited in  claim 34 , wherein the packet processor comprises a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and wherein selection logic therein causes header information from a given packet associated with a selected one of said packet identifiers to be loaded into an available one of said contexts. 
     
     
       40. The apparatus as recited in  claim 39 , wherein there are more of said contexts than said individual streams, and wherein loading of header information into said available one of said contexts is accomplished in background, that is, in parallel with processing of packets.