# US 2004/0081091 A1 · Priority-based efficient fair queuing for quality of service classificatin for packet processing

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

- Number: US 2004/0081091 A1
- Document ID: US20040081091A1
- Status: Published application
- Kind: A1
- Application number: 10/281,537
- Filed: 2002-10-28
- Published: 2004-04-29
- Earliest claimed: 2002-08-30
- Assignees: Redback Networks Inc.
- Inventors: Robert F. Widmer; Suhail Nanji; Nicholas M. Thille
- Web page: https://patentgrep.com/patent/US20040081091A1

## CPC

- H04L 47/525: by redistribution of residual bandwidth
- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 47/50: Queue scheduling
- H04L 47/522: {Dynamic queue service slot or variable bandwidth allocation}
- H04L 47/527: {Quantum based scheduling, e.g. credit or deficit based scheduling or token bank}
- H04L 47/6255: {queue load conditions, e.g. longest queue first}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, a method comprises recursively selecting a child node of a previously selected node of a port tree and having a highest priority among nodes of a same level within the port tree, until the selected node has associated egress queues of an egress port. The method also includes outputting a number of packets from the associated egress queues of the selected node in a current processing cycle. The number of packets outputted is based on an allocated bandwidth for the associated egress queues, in which the allocated bandwidth accounts for a deficit from a previous processing cycle.

## Claims

### Claim 1

A method comprising:
recursively selecting a child node of a previously selected node of a port tree and having a highest priority among nodes of a same level within the port tree, until the selected node has associated egress queues of an egress port; and
outputting a number of packets from the associated egress queues of the selected node in a current processing cycle, wherein the number of packets outputted is based on an allocated bandwidth for the associated egress queues, in which the allocated bandwidth accounts for a deficit from a previous processing cycle.

### Claim 2 (depends on 1)

The method of claim 1, wherein outputting the number of packets from the associated egress queues of the selected node comprises outputting the number of packets from the associated egress queues in an order of priority among the associated egress queues.

### Claim 3 (depends on 1)

The method of claim 1, comprising redistributing surplus of the portion of the bandwidth that is not used for one of the associated egress queues to at least one other egress queue for the egress port for the current processing cycle.

### Claim 4 (depends on 1)

The method of claim 1, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different contexts for the data.

### Claim 5 (depends on 1)

The method of claim 1, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different tunnels that the data traverses.

### Claim 6 (depends on 1)

The method of claim 1, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different subscribers that the data originates.

### Claim 7

A method comprising:
selecting a node of a port tree having a highest priority among nodes at a level associated with contexts for data packets;
selecting one having a highest priority of a number of children nodes of the selected node at the level associated with contexts for data packets, wherein the number of children nodes of the selected node at the level associated with contexts for the data packets are at a level having nodes associated with tunnels for the data packets;
selecting one having a highest priority of a number of children nodes of the selected node at the level associate with tunnels for the data packet, wherein the number of children nodes of the selected node at the level associated with tunnels for the data packets are at a level having nodes associated with subscribers from which the data packets originate; and
outputting a number of the data packets stored in egress queues associated with the selected node associated with the subscriber from which the data packets originate, wherein the number of data packets outputted is based on an allocated bandwidth for the egress queues in which the allocated bandwidth includes a deficit from a previous processing cycle.

### Claim 8 (depends on 7)

The method of claim 7, wherein outputting the number of the data packets stored in egress queues comprises outputting the number of the data packets stored in the egress queues in an order of priority among the egress queues.

### Claim 9 (depends on 8)

The method of claim 8, comprising redistributing surplus of the portion of the allocated bandwidth that is not used for one of the egress queues to at least one other egress queue for the processing cycle.

### Claim 10

A network element comprising:
a traffic card that includes an egress port, the egress port to include a number of egress queues to store data packets; and
a forwarding card that includes,
a memory to store a port tree, wherein the number of egress queues are associated with leaf nodes of the port tree; and
a forwarding engine to recursively select a child node of a previously selected node of the port tree, which has a highest priority among nodes of a same level within the port tree, until the selected node has associated egress queues of the number of queues, wherein the forwarding engine is to output a number of data packets from the associated egress queues of the selected node in a current processing cycle, wherein the number of data packets outputted is based on an allocated bandwidth for the associated egress queues, in which the allocated bandwidth include a deficit from a previous processing cycle.

### Claim 11 (depends on 10)

The network element of claim 10, wherein the forwarding engine is to output the number of packets from the associated egress queues in an order of priority among the associated egress queues.

### Claim 12 (depends on 10)

The network element of claim 10, wherein the forwarding engine is to redistribute surplus of the portion of the allocated bandwidth that is not used for one of the associated egress queues to at least one other egress queue for the egress port for the current processing cycle.

### Claim 13 (depends on 10)

The network element of claim 10, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different contexts for the data.

### Claim 14 (depends on 10)

The network element of claim 10, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different tunnels that the data traverses.

### Claim 15 (depends on 10)

The network element of claim 10, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different subscribers that the data originates.

### Claim 16

A machine-readable medium that provides instructions, which when executed by a machine, cause said machine to perform operations comprising:
recursively selecting a child node of a previously selected node of a port tree and having a highest priority among nodes of a same level within the port tree, until the selected node has associated egress queues of an egress port; and
outputting a number of packets from the associated egress queues of the selected node in a current processing cycle, wherein the number of packets outputted is based on an allocated bandwidth for the associated egress queues, in which the allocated bandwidth accounts for a deficit from a previous processing cycle.

### Claim 17 (depends on 16)

The machine-readable medium of claim 16, wherein outputting the number of packets from the associated egress queues of the selected node comprises outputting the number of packets from the associated egress queues in an order of priority among the associated egress queues.

### Claim 18 (depends on 16)

The machine-readable medium of claim 16, comprising redistributing surplus of the portion of the bandwidth that is not used for one of the associated egress queues to at least one other egress queue for the egress port for the current processing cycle.

### Claim 19 (depends on 16)

The machine-readable medium of claim 16, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different contexts for the data.

### Claim 20 (depends on 16)

The machine-readable medium of claim 16, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different tunnels that the data traverses.

### Claim 21 (depends on 16)

The machine-readable medium of claim 16, wherein the nodes of the port tree are within different levels of the port tree, wherein a level of the different levels includes nodes that are associated with different subscribers that the data originates.

### Claim 22

A machine-readable medium that provides instructions, which when executed by a machine, cause said machine to perform operations comprising:
selecting a node of a port tree having a highest priority among nodes at a level associated with contexts for data packets;
selecting one having a highest priority of a number of children nodes of the selected node at the level associated with contexts for data packets, wherein the number of children nodes of the selected node at the level associated with contexts for the data packets are at a level having nodes associated with tunnels for the data packets;
selecting one having a highest priority of a number of children nodes of the selected node at the level associate with tunnels for the data packet, wherein the number of children nodes of the selected node at the level associated with tunnels for the data packets are at a level having nodes associated with subscribers from which the data packets originate; and
outputting a number of the data packets stored in egress queues associated with the selected node associated with the subscriber from which the data packets originate, wherein the number of data packets outputted is based on an allocated bandwidth for the egress queues in which the allocated bandwidth includes a deficit from a previous processing cycle.

### Claim 23 (depends on 22)

The machine-readable medium of claim 22, wherein outputting the number of the data packets stored in egress queues comprises outputting the number of the data packets stored in the egress queues in an order of priority among the egress queues.

### Claim 24 (depends on 23)

The machine-readable medium of claim 23, comprising redistributing surplus of the portion of the allocated bandwidth that is not used for one of the egress queues to at least one other egress queue for the processing cycle.
