Queueing system for processors in packet routing operations

• US 7,058,064 B2
• Filed: 12/14/2000
• Issued: 06/06/2006
• 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: Musoll, Enric, Melvin, Stephen, Sankar, Narendra, Sampath, Nandakumar, Nemirovsky, Adolfo, Nemirovsky, Mario
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Sefcheck, Gregory B
• Application Number:
  US09/737,375
• Publication Number:
  US 20010043610A1
• Time in Patent Office: 2,000 Days
• Field of Search: 370/360, 370/379, 370381-383, 370/392, 370/394, 370/395.7, 370/395.72, 370/412, 710/22, 710/52, 710/56, 710/310, 711/117, 711/128, 711/147, 711/154, 711/158, 711/170
• 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 queueing system for packet accounting during processing, the system comprising:

a plurality of queues arranged in one or more clusters;

an identification mechanism for creating a packet identifier for arriving packets, wherein the packet identifier created is associated to a memory location where the packet itself is stored during processing, and;

insertion logic for inserting packet identifiers into queues and for determining into which queue to insert a packet identifier, wherein the packet identifier created and queued comprises, in addition to the memory location, one or more of an identifier of a device from which the packet was received, an indication of whether the packet has increased or decreased in total size during processing, an indication of whether or not processing was completed on the associated packet, a next queue into which the packet identifier should be inserted, and an identifier of whether the packet is currently being processed; 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.

2. The queueing system of claim 1 wherein the insertion logic determines a priority for a packet, and inserts the packet into a particular queue depending on the priority determined.

3. The queueing system of claim 2 wherein clusters are numbered, and priority for processing identified packets is by cluster number.

4. The queueing system of claim 3 wherein the selection system selects packets for processing based upon priority by queue number.

5. The queueing system of claim 4 wherein a fairness algorithm is followed in selecting a queue within a priority cluster for selecting a packet for processing.

6. The queueing system of claim 1 wherein the selection system selects packets for requeueing based on the value of the next queue number set in the packet identifier.

7. The queueing system of claim 1 wherein the selection system selects packets for downloading based on the value of the indication of whether processing on the associated packet is completed.

8. The queueing system of claim 1 wherein the data-packet processor is a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and the selection system causes header information from a packet associated with a selected identifier to be loaded into an available context.

9. The queueing system of claim 8 wherein there are more contexts that streams, and loading of header information into available contexts is accomplished in background, that is, in parallel with processing of packets.

10. The queueing system of claim 1 wherein software executed by the processor is enabled to manipulate value of individual ones of fields in a packet identifier.

11. The queueing system of claim 1 wherein the insertion logic inserts packets into queues at least in part according to flow, and wherein insertion and selection logic cooperate to preserve order of packets in individual flows.

12. The queueing system of claim 1 wherein the insertion logic treats packets incoming from the network or switching fabric with highest priority for identifier insertion into a queue, packet identifiers to be requeued with a next highest priority, and identifiers for packets generated by software with a lowest priority.

13. A data-packet processor, comprising:

an input buffer for buffering incoming packets from one or more sources;

a local packet memory for storing packet data during processing;

a stream processor unit for processing packet data; and

a configurable queueing system for packet accounting during processing;

wherein the queueing system comprises 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; and

wherein the packet identifier created is associated to a memory location where the packet itself is stored during processing; and

wherein the packet identifier created and queued comprises, in addition to the memory location, one or more of an identifier of a device from which the packet was received, an indication of whether the packet has increased or decreased in total size during processing, an indication of whether or not processing was completed on the associated packet, a next queue into which the packet identifier should be inserted, and an identifier of whether the packet is currently being processed.

14. The processor of claim 13 wherein the insertion logic determines a priority for a packet, and inserts the packet into a particular queue depending on the priority determined.

15. The processor of claim 14 wherein clusters are numbered, and priority for processing identified packets is by cluster number.

16. The processor of claim 15 wherein the selection system selects packets for processing based upon priority by queue number.

17. The processor of claim 16 wherein a fairness algorithm is followed in selecting a queue within a priority cluster for selecting a packet for processing.

18. The processor of claim 13 wherein the selection system selects packets for requeueing based on the value of the next queue number set in the packet identifier.

19. The processor of claim 13 wherein the selection system selects packets for downloading based on the value of the indication of whether processing on the associated packet is completed.

20. The processor of claim 13 wherein the data-packet processor is a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and the selection system causes header information from a packet associated with a selected identifier to be loaded into an available context.

21. The processor of claim 20 wherein there are more contexts that streams, and loading of header information into available contexts is accomplished in background, that is, in parallel with processing of packets.

22. The processor of claim 13 wherein software executed by the processor is enabled to manipulate value of individual ones of fields in a packet identifier.

23. The processor of claim 13 wherein the insertion logic inserts packets into queues at least in part according to flow, and wherein insertion and selection logic cooperate to preserve order of packets in individual flows.

24. The processor of claim 13 wherein the insertion logic treats packets incoming from the network or switching fabric with highest priority for identifier insertion into a queue, packet identifiers to be requeued with a next highest priority, and identifiers for packets generated by software with a lowest priority.

25. 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 arriving packets, wherein the packet identifier created is associated to a memory location where the packet itself is stored during processing;

inserting packet identifiers into queues by an insertion mechanism having logic for determining into which queue to insert, wherein the packet identifier created and queued comprises, in addition to the memory location, one or more of an identifier of a device from which the packet was received, an indication of whether the packet has increased or decreased in total size during processing, an indication of whether or not processing was completed on the associated packet, a next queue into which the packet identifier should be inserted, and an identifier of whether the packet is currently being processed; and

selecting packet identifiers from the queues by selection logic, for initiating processing of identified packets, downloading of completed packets, or for requeueing of the selected packet identifiers.

26. The method of claim 25 wherein the insertion logic determines a priority for a packet, and inserts the packet into a particular queue depending on the priority determined.

27. The method of claim 26 wherein clusters are numbered, and priority for processing identified packets is by cluster number.

28. The method of claim 27 wherein the selection system selects packets for processing based upon priority by queue number.

29. The method of claim 28 wherein a fairness algorithm is followed in selecting a queue within a priority cluster for selecting a packet for processing.

30. The method of claim 25 wherein the selection system selects packets for requeueing based on the value of the next queue number set in the packet identifier.

31. The method of claim 25 wherein the selection system selects packets for downloading based on the value of the indication of whether processing on the associated packet is completed.

32. The method of claim 25 wherein the data-packet processor is a multi-streaming processor having separate contexts implemented by context registers and associated with individual streams, and the selection system causes header information from a packet associated with a selected identifier to be loaded into an available context.

33. The method of claim 32 wherein there are more contexts that streams, and loading of header information into available contexts is accomplished in background, that is, in parallel with processing of packets.

34. The method of claim 25 wherein software executed by the processor is enabled to manipulate value of individual ones of fields in a packet identifier.

35. The method of claim 25 wherein the insertion logic inserts packets into queues at least in part according to flow, and wherein insertion and selection logic cooperate to preserve order of packets in individual flows.

36. The method of claim 25 wherein the insertion logic treats packets incoming from the network or switching fabric with highest priority for identifier insertion into a queue, packet identifiers to be requeued with a next highest priority, and identifiers for packets generated by software with a lowest priority.

37. In a data packet processor having a queueing system for managing arriving packets waiting to be processed, a packet queueing system comprising:

a fixed range of packet numbers; and

an assignment facility;

characterized in that the assignment facility accounts for individual numbers in the fixed range, marking numbers invalid as packets in the queueing system are sent to be processed or software activates them, and reassigning invalid numbers to newly arrived packets put into the queueing system;

wherein a packet number created is associated to a memory location where the packet itself is stored during processing; and

wherein the packet identifier created and queued comprises, in addition to the memory location, one or more of an identifier of a device from which the packet was received, an indication of whether the packet has increased or decreased in total size during processing, an indication of whether or not processing was completed on the associated packet, a next queue into which the packet identifier should be inserted, and an identifier of whether the packet is currently being processed.