Queueing system for processors in packet routing operations

• US 7,715,410 B2
• Filed: 03/23/2006
• Issued: 05/11/2010
• Est. Priority Date: 02/08/2000
• Status: Expired due to Fees

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Nemirovsky, Mario, Melvin, Stephen, Nemirovsky, Adolfo, Musoll, Enric, Sankar, Narendra, Sampath, Nandakumar
• Primary Examiner(s): Sefcheck, Gregory B
• Application Number:
  US11/277,293
• Publication Number:
  US 20060159104A1
• Time in Patent Office: 1,510 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 queuing 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 requeuing 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 packet identifier queues arranged in one or more clusters;

an identification mechanism for creating unique packet identifiers for arriving packets, wherein each created packet identifier includes two or more fields and exists independently of the plurality of packet identifier queues;

insertion logic for inserting said created packet identifiers into the plurality of packet identifier queues and for determining into which packet identifier queue to insert a given packet identifier, wherein the insertion logic is configured to independently sort inserted packet identifiers within each packet identifier queue; and

selection logic, for selecting said packet identifiers from the plurality of packet identifier queues to initiate processing of identified packets, downloading of completed packets, or for requeuing of the selected packet identifiers,

wherein the system is configured to receive commands generated in response to packet instructions corresponding to said packet identifiers.

2. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise an insert instruction configured to direct the queuing system to insert one of said packet identifiers into one of said plurality of packet identifier queues.

3. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a move instruction configured to direct the queuing system to move at least one of said packet identifiers from a first one of said plurality of packet identifier queues to a second one of said plurality of packet identifier queues.

4. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a complete instruction configured to direct the queuing system to indicate that processing of one of said packet identifiers is complete.

5. The data-packet processor as recited in claim 4, wherein said packet instructions comprise a complete instruction configured to direct the queuing system to indicate that a size of a corresponding packet has changed during processing.

6. The configurable queuing system as recited in claim 5, wherein said complete instruction indicates that said size has increased.

7. The configurable queuing system as recited in claim 5, wherein said complete instruction indicates that said size has decreased.

8. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a replace instruction configured to direct the queuing system to replace a first one of said packet identifiers with a second one of said packet identifiers.

9. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a probe packet number instruction configured to direct the queuing system to return an indication of whether one of said packet identifiers exists in said plurality of packet identifier queues.

10. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a probe and set instruction configured to direct the queuing system to return an indication of whether one of said packet identifiers exists in said plurality of queues, and to indicate that said one of said packet identifiers has been probed.

11. The configurable queuing system as recited in claim 1, wherein said packet instructions comprise a probe queue instruction configured to direct the queuing system to return a number of said packet identifiers that exist in one of said plurality of packet identifier queues.

12. A method for accounting for packets in a data-packet processor, comprising:

providing in the processor a plurality of packet identifier queues in one or more clusters;

creating unique packet identifiers for arriving packets, wherein each created packet identifier includes two or more fields and exists independently of the plurality of packet identifier queues, and wherein said creating comprises;

identifying a device from which each of the arriving packets was received;

inserting each of the created packet identifiers into a corresponding one of the plurality of packet identifier queues;

sorting inserted packet identifiers independently within each one of the plurality of packet identifier queues; and

processing commands received from a stream processing unit that processes contexts corresponding to the packet identifiers.

13. The method as recited in claim 12, wherein said processing comprises executing an insert instruction that directs the queuing system to insert one of the packet identifiers into one of the plurality of packet identifier queues.

14. The method as recited in claim 12, wherein said processing comprises executing a move instruction configured to direct the queuing system to move at least one of the packet identifiers from a first one of the plurality of packet identifier queues to a second one of the plurality of packet identifier queues.

15. The method as recited in claim 12, wherein said processing comprises executing a complete instruction configured to direct the queuing system to indicate that processing of one of the packet identifiers is complete and that a size of a corresponding packet has changed during processing.

16. The method as recited in claim 15, wherein said executing comprises directing the queuing system to indicate that the size has increased.

17. The method as recited in claim 15, wherein said executing comprises directing the queuing system to indicate that the size has decreased.

18. The method as recited in claim 12, wherein said processing comprises executing a replace instruction configured to direct the queuing system to replace a first one of the packet identifiers with a second one of the packet identifiers.

19. The method as recited in claim 12, wherein said processing comprises executing a probe packet number instruction configured to direct the queuing system to return an indication of whether one of the packet identifiers exists in the plurality of packet identifier queues.

20. The method as recited in claim 12, wherein said processing comprises executing a probe and set instruction configured to direct the queuing system to return an indication of whether one of the packet identifiers exists in the plurality of packet identifier queues, and to indicate that the one of the packet identifiers has been probed.

21. The method as recited in claim 12, wherein said processing comprises executing a probe queue instruction configured to direct the queuing system to return a number of the packet identifiers that exist in one of the plurality of packet identifier queues.