# US 2006/0153197 A1 · Queueing system for processors in packet routing operations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0153197 A1
- Document ID: US20060153197A1
- Status: Published application
- Kind: A1
- Application number: 11/360,338
- Filed: 2006-02-23
- Published: 2006-07-13
- Earliest claimed: 2000-02-08
- Assignees: MIPS Technologies, Inc.
- Inventors: Mario Nemirovsky; Enric Musoll; Stephen Melvin; Narendra Sankar; Nandakumar Sampath; Adolfo Nemirovsky
- Web page: https://patentgrep.com/patent/US20060153197A1

## CPC

- G06F 9/546: {Message passing systems or structures, e.g. queues}
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L 47/621: {Individual queue per connection or flow, e.g. per VC}
- H04L 47/6215: {Individual queue per QOS, rate or priority}
- H04L 49/201: Multicast operation; Broadcast operation
- H04L 49/90: Buffering arrangements
- H04L 49/901: using storage descriptor, e.g. read or write pointers
- H04L 49/9073: {Early interruption upon arrival of a fraction of a packet}
- H04L 49/205: {Quality of Service based}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 1

(canceled)

### Claim 2

(canceled)

### Claim 3

(canceled)

### Claim 4

(canceled)

### Claim 5

(canceled)

### Claim 6

(canceled)

### Claim 7

(canceled)

### Claim 8

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 or said packet identifiers.

### Claim 9 (depends on 8)

The queuing system as recited in claim 8, 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.

### Claim 10 (depends on 9)

The queuing system as recited in claim 9, wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number.

### Claim 11 (depends on 8)

The queuing system as recited in claim 8, 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.

### Claim 12 (depends on 8)

The queuing system, as recited in claim 8, further comprising: selection logic, for selecting said packet identifiers from said plurality of queues to initiate processing of identified packets, downnloading 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.

### Claim 13

(canceled)

### Claim 14

(canceled)

### Claim 15 (depends on 8)

The queuing system as recited in claim 8, 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.

### Claim 16 (depends on 15)

The queuing system as recited in claim 15, wherein there are more of said contexts 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.

### Claim 17

(canceled)

### Claim 18

(canceled)

### Claim 19

(canceled)

### Claim 20

(canceled)

### Claim 21

(canceled)

### Claim 22

(canceled)

### Claim 23

(canceled)

### Claim 24

(canceled)

### Claim 25

(canceled)

### Claim 26

(canceled)

### Claim 27

(canceled)

### Claim 28

(canceled)

### Claim 29

(canceled)

### Claim 30

(canceled)

### Claim 31

(canceled)

### Claim 32

(canceled)

### Claim 33

(canceled)

### Claim 34

(canceled)

### Claim 35

(canceled)

### Claim 36

(canceled)

### Claim 37

(canceled)

### Claim 38

(canceled)

### Claim 39

(canceled)

### Claim 40

(canceled)

### Claim 41

(canceled)

### Claim 42

(canceled)

### Claim 43

(canceled)

### Claim 44

(canceled)

### Claim 45

(canceled)

### Claim 46

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 if queues.

### Claim 47 (depends on 46)

The method as recited in claim 46, wherein said inserting comprises:
determining a priority for the arriving packet, and placing the arriving packet into a particular queue depending on the priority.

### Claim 48

(canceled)

### Claim 49 (depends on 46)

The method as recited in claim 46, 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.

### Claim 50 (depends on 46)

The method as recited in claim 46, 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.

### Claim 51

(canceled)

### Claim 52

(canceled)

### Claim 53 (depends on 46)

The method of as recited in claim 46, 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.

### Claim 54

(canceled)

### Claim 55

(canceled)

### Claim 56

(canceled)

### Claim 57

(canceled)

### Claim 58

(canceled)

### Claim 59

(canceled)

### Claim 60

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 or said packet identifiers.

### Claim 61 (depends on 60)

The data packet processor as recited in claim 60, 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.

### Claim 62 (depends on 61)

The data packet processor as recited in claim 61, wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number.

### Claim 63 (depends on 60)

The data packet processor as recited in claim 60, 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.

### Claim 64 (depends on 60)

The data packet processor as recited in claim 60, 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.

### Claim 65 (depends on 60)

The data packet processor as recited in claim 60, 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.

### Claim 66 (depends on 65)

The data packet processor as recited in claim 65, 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.

### Claim 67

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 or said packet identifiers.

### Claim 68 (depends on 67)

The queuing apparatus as recited in claim 67, 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.

### Claim 69 (depends on 68)

The queuing apparatus as recited in claim 68, wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number.

### Claim 70 (depends on 67)

The queuing apparatus as recited in claim 67, 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.

### Claim 71 (depends on 67)

The queuing apparatus as recited in claim 67, 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.

### Claim 72 (depends on 67)

The queuing apparatus r as recited in claim 67, 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.

### Claim 73 (depends on 72)

The queuing apparatus as recited in claim 72, 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.

### Claim 74

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 or said packet identifiers.

### Claim 75 (depends on 74)

The apparatus as recited in claim 74, 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.

### Claim 76 (depends on 75)

The apparatus as recited in claim 75, wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number.

### Claim 77 (depends on 74)

The apparatus r as recited in claim 74, 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.

### Claim 78 (depends on 74)

The apparatus as recited in claim 74, 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.

### Claim 79 (depends on 74)

The apparatus as recited in claim 74, 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.

### Claim 80 (depends on 79)

The apparatus as recited in claim 79, 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.

### Claim 81

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 or said packet identifiers.

### Claim 82 (depends on 81)

The apparatus as recited in claim 81, 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.

### Claim 83 (depends on 82)

The apparatus as recited in claim 82, wherein said one or more clusters are numbered, and priority for processing identified packets is by cluster number.

### Claim 84 (depends on 81)

The apparatus r as recited in claim 81, 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.

### Claim 85 (depends on 81)

The apparatus as recited in claim 81, 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.

### Claim 86 (depends on 81)

The apparatus as recited in claim 81, 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.

### Claim 87 (depends on 86)

The apparatus as recited in claim 86, 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.
