# US 2003/0214964 A1 · Method and apparatus for scheduling and interleaving items using quantum and deficit values including but not limited to systems using multiple active sets of items or mini-quantum values

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

- Number: US 2003/0214964 A1
- Document ID: US20030214964A1
- Status: Published application
- Kind: A1
- Application number: 10/104,759
- Filed: 2002-03-21
- Published: 2003-11-20
- Earliest claimed: 2002-03-21
- Assignees: Cisco Technology, Inc.
- Inventors: Doron Shoham; Amir Michaeli; David J. Tsiang; Chandrashekhar Appanna
- Web page: https://patentgrep.com/patent/US20030214964A1

## CPC

- H04L 47/6225: {Fixed service order, e.g. Round Robin}
- H04L 47/50: Queue scheduling
- H04L 47/527: {Quantum based scheduling, e.g. credit or deficit based scheduling or token bank}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Methods and apparatus are disclosed for scheduling items (e.g., packets, processes, etc.) in a system, such as, but not limited to a computer or communications system (e.g., router, switch, etc.) In one implementation, multiple sets of items requiring processing to be performed are maintained. A current set of the multiple sets of items is identified. Each of the items in the current set is processed. In one implementation, this processing includes identifying a particular item in the current set, adding a quantum to a deficit of the particular item, processing an entity corresponding to the particular item, decreasing the deficit of the particular item by a value, determining if the deficit allows the particular item to be further processed, and moving the particular item from the current set to another of the multiple sets of items after said determining if deficit allows the particular item to be further processed.

## Claims

### Claim 1

A method comprising:
maintaining a plurality of sets of items requiring processing to be performed;
identifying a current set of the plurality of sets of items; and
processing items in the current set, said processing the items including:
identifying a particular item in the current set;
adding a quantum to a deficit of the particular item;
processing an entity corresponding to the particular item;
decreasing the deficit of the particular item by a value;
determining if the deficit allows the particular item to be further processed; and
moving the particular item from the current set to another of the plurality of sets of items after said determining if deficit allows the particular item to be further processed.

### Claim 2 (depends on 1)

The method of claim 1, wherein each of the items in the plurality of sets of items represents a queue.

### Claim 3 (depends on 2)

The method of claim 2, wherein the entity represents a packet.

### Claim 4 (depends on 3)

The method of claim 3, wherein the value corresponds to a size of the packet.

### Claim 5 (depends on 3)

The method of claim 3, wherein the value corresponds to a constant value.

### Claim 6 (depends on 1)

The method of claim 1, wherein the entity represents a process, thread, or information stream.

### Claim 7 (depends on 1)

The method of claim 1, wherein the value corresponds to a variable amount related to said processing of the entity or a constant value.

### Claim 8 (depends on 1)

The method of claim 1, wherein said determining if the deficit allows the particular item to be further processed includes comparing a value of the deficit to a constant value or zero.

### Claim 9 (depends on 1)

The method of claim 1, wherein said processing items further comprises selecting said another of the plurality of sets of items based on the deficit and the quantum of the particular item.

### Claim 10 (depends on 1)

The method of claim 1, wherein said processing items further comprises removing the particular item from all of the plurality of sets when the particular no longer has any corresponding entities remaining.

### Claim 11 (depends on 1)

The method of claim 1, wherein said processing items further comprises leaving the particular item in the current set when said determining determines that the deficit allows the particular item to be further processed.

### Claim 12 (depends on 11)

The method of claim 11, wherein said moving the particular item from the current set to said another of the plurality of sets of items is performed only when said determining determines that the deficit does not allow the particular item to be further processed.

### Claim 13 (depends on 11)

The method of claim 11, wherein a group including said processing the entity, said decreasing the deficit, and said determining is repeatedly performed on the particular item until said determining determines that the deficit does not allow the particular item to be further processed.

### Claim 14 (depends on 1)

The method of claim 1, wherein said processing items further comprises setting the particular item to be a different item in the current set.

### Claim 15 (depends on 14)

The method of claim 14, wherein a group including said processing the entity, said decreasing the deficit, said determining and said setting is repeatedly performed until the current set becomes empty.

### Claim 16 (depends on 1)

The method of claim 1, wherein said processing items further comprises:
initializing a mini-deficit associated with the particular item;
decreasing the mini-deficit of the particular item by a second value;
determining if the mini-deficit allows the particular item to be further processed; and
setting the particular item to be a different item in the current set after said determining if the mini-deficit allows the particular item to be further processed.

### Claim 17 (depends on 16)

The method of claim 16, wherein a group including said processing the entity, said decreasing the deficit, said decreasing the mini-deficit, said determining if the mini-deficit allows and said determining if the deficit allows is repeatedly performed on the particular item until said determining if the deficit allows determines that the deficit does not allow the particular item to be further processed or until said determining if the mini-deficit does not allow the particular item to be further processed.

### Claim 18 (depends on 16)

The method of claim 16, wherein the value and the second value are equal.

### Claim 19 (depends on 1)

The method of claim 1, further comprising selecting and processing a particular next set from the plurality of sets of items.

### Claim 20 (depends on 19)

The method of claim 19, wherein said selecting and processing the particular next set is performed in response to determining the current set to be empty.

### Claim 21 (depends on 1)

A computer-readable medium containing computer-executable instructions for performing the method of claim 1.

### Claim 22

An apparatus comprising:
a plurality of queues for buffering a plurality of packets; and
a scheduler to perform scheduling of the sending of packets of the plurality of packets, the scheduler including:
control logic; and
one or more memory devices configured to maintain a plurality of sets of indications of queues of the plurality of queues requiring processing to be performed;
wherein said scheduling includes:
identifying a current set of the plurality of sets of indications; and
processing queues corresponding to the one or more indications of queues in the current set, said processing including:
identifying a particular indication of a particular queue of the plurality of queues in the current set;
adding a quantum to a deficit of the particular indication;
sending a packet from the particular queue corresponding to the particular indication;
decreasing the deficit by a value;
determining if the deficit allows the particular queue to be further processed; and
moving the particular indication from the current set to another of the plurality of sets of indications of queues after said determining if deficit allows the particular queue to be further processed.

### Claim 23 (depends on 22)

The apparatus of claim 22, wherein the value corresponds to a size of the packet.

### Claim 24 (depends on 22)

The apparatus of claim 22, wherein said processing queues further comprises selecting said another of the plurality of sets of indications based on the deficit and the quantum.

### Claim 25 (depends on 22)

The apparatus of claim 22, wherein said processing queues further comprises leaving the particular indication in the current set when said determining determines that the deficit allows the particular queue to be further processed.

### Claim 26 (depends on 25)

The apparatus of claim 25, wherein a group including said sending the packet, said decreasing the deficit, and said determining is repeatedly performed based on the particular indication until said determining determines that the deficit does not allow the particular queue to be further processed.

### Claim 27 (depends on 22)

The apparatus of claim 22, wherein said moving the particular indication from the current set to another of the plurality of sets of indications is performed only when said determining determines that the deficit does not allow the particular queue to be further processed.

### Claim 28 (depends on 22)

The apparatus of claim 22, wherein said processing queues further comprises setting the particular indication to be a different particular indication in the current set of the plurality of indications.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein a group including said sending the packet, said decreasing the deficit, said determining and said setting is repeatedly performed until the current set becomes empty.

### Claim 30 (depends on 22)

The apparatus of claim 22, wherein said processing queues further comprises:
initializing a mini-deficit associated with the particular indication;
decreasing the mini-deficit by a second value;
determining if the mini-deficit allows the particular queue to be further processed; and
setting the particular indication to be a different indication in the current set after said determining if the mini-deficit allows the particular queue to be further processed.

### Claim 31 (depends on 30)

The apparatus of claim 30, wherein a group including said sending the packet, said decreasing the deficit, said decreasing the mini-deficit, said determining if the mini-deficit allows, and said determining if the deficit allows is repeatedly performed based on the particular indication until said determining if the deficit allows determines that the deficit does not allow the particular queue to be further processed or until said determining if the mini-deficit does not allow the particular queue to be further processed.

### Claim 32 (depends on 22)

The apparatus of claim 22, further comprising selecting and processing a particular next set from the plurality of sets of indications.

### Claim 33 (depends on 32)

The apparatus of claim 32, wherein said selecting and processing the particular next set is performed in response to determining the current set to be empty.

### Claim 34

An apparatus comprising:
means for maintaining a plurality of sets of items requiring processing to be performed;
means for identifying a current set of the plurality of sets of items; and
means for processing each of the items in the current set, said means for processing each of the items including:
means for identifying a particular item in the current set;
means for adding a quantum to a deficit of the particular item;
means for processing an entity corresponding to the particular item;
means for decreasing the deficit of the particular item by a value; and
means for determining if the deficit allows the particular item to be further processed; and
means for moving the particular item from the current set to another of the plurality of sets of items after said determining if deficit allows the particular item to be further processed.

### Claim 35 (depends on 34)

The apparatus of claim 34, wherein said processing items further comprises setting the particular item to be a different item in the current set.

### Claim 36 (depends on 34)

The method of claim 34, further comprising:
means for initializing a mini-deficit associated with the particular item;
means for decreasing the mini-deficit of the particular item by a second value;
means for determining if the mini-deficit allows the particular item to be further processed; and
means for setting the particular item to be a different item in the current set after determining if the mini-deficit allows the particular item to be further processed.

### Claim 37 (depends on 34)

The method of claim 34, further comprising means for selecting a particular next set from the plurality of sets of items.
