Queueing system for processors in packet routing operations

• US 7,551,626 B2
• Filed: 02/23/2006
• Issued: 06/23/2009
• Est. Priority Date: 02/08/2000
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Nemirovsky, Adolfo, Nemirovsky, Mario, Melvin, Stephen, Sampath, Nandakumar, Musoll, Enric, Sankar, Narendra
• Primary Examiner(s): Sefcheck, Gregory B
• Application Number:
  US11/360,338
• Publication Number:
  US 20060153197A1
• Time in Patent Office: 1,216 Days
• Field of Search: None
• US Class Current: 370/395.7
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet

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.

Claims

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.