# US 2024/0406117 A1 · Virtual-time rate for managing queues

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

- Number: US 2024/0406117 A1
- Document ID: US20240406117A1
- Status: Published application
- Kind: A1
- Application number: 18/498,460
- Filed: 2023-10-31
- Published: 2024-12-05
- Earliest claimed: 2023-06-02
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Jean Tourrilhes; Puneet Sharma
- Web page: https://patentgrep.com/patent/US20240406117A1

## CPC

- H04L 47/6255: {queue load conditions, e.g. longest queue first}
- H04L 47/12: Avoiding congestion; Recovering from congestion
- H04L 47/122: by diverting traffic away from congested entities
- H04L 47/2483: involving identification of individual flows
- H04L 47/30: in combination with information about buffer occupancy at either end or at transit nodes
- H04L 47/32: by discarding or delaying data units, e.g. packets or frames
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system maintains a queue structure used for storing packets and comprising a plurality of sub-queues used to process the packets, wherein the packets in the queue structure are to be dequeued by a scheduler. The system computes a respective packet virtual time for a respective packet based on at least a packet virtual time of a previous packet processed by the same sub-queue. The system computes a global virtual time based on a packet virtual time of a packet being dequeued from the queue structure. The system measures a rate at which the global virtual time progresses based on the virtual time of packets dequeued from the queue structure. The system manages congestion in the sub-queues based on the rate at which the global virtual time progresses, a metric of a respective sub-queue, and an amount of a resource for the queue structure.

## Claims

### Claim 1

A computer-implemented method for managing congestion in a network, the method comprising:
maintaining a queue structure used for storing packets and comprising a plurality of sub-queues used to process the packets, wherein the packets in the queue structure are to be dequeued by a scheduler;
computing a respective packet virtual time for a respective packet based on at least a packet virtual time of a previous packet processed by the same sub-queue, wherein the respective packet virtual time indicates a relative progress of the respective packet in the sub-queue;
computing a global virtual time based on a packet virtual time of a packet being dequeued from the queue structure by the scheduler;
measuring a rate at which the global virtual time progresses based on the virtual time of packets dequeued by the scheduler from the queue structure; and
managing congestion in a respective sub-queue based on the rate at which the global virtual time progresses, a metric of the respective sub-queue, and an amount of a resource for the queue structure.

### Claim 2 (depends on 1)

The method of claim 1,
wherein managing the congestion in the respective sub-queue comprises dropping one or more packets.

### Claim 3 (depends on 1)

The method of claim 1,
wherein managing the congestion in the respective sub-queue comprises changing an explicit congestion notification (ECN) value in a header of one or more packets.

### Claim 4 (depends on 1)

The method of claim 1,
wherein managing the congestion in the respective sub-queue comprises transmitting a pause frame.

### Claim 5 (depends on 1)

The method of claim 1,
wherein managing the congestion in the respective sub-queue comprises transmitting a flow control signal or a flow control packet.

### Claim 6 (depends on 1)

The method of claim 1, wherein managing the congestion in the respective sub-queue comprises:
scaling the metric of the respective sub-queue based on the rate at which the global virtual time progresses;
comparing the scaled metric of the respective sub-queue with the amount of the resource for the queue structure; and
managing the congestion in the respective sub-queue based on the comparison.

### Claim 7 (depends on 1)

The method of claim 1,
wherein managing the congestion in the respective sub-queue is further based on a length of the respective sub-queue.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
determining a predicted delay based on the length of the respective sub-queue;
computing a probability based on the predicted delay and a configured target delay; and
managing the congestion in the respective sub-queue further based on the probability.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
computing a dynamic threshold based on the amount of the resource and the measured global virtual time rate;
comparing a current size of the respective sub-queue to the dynamic threshold; and
managing the congestion in the respective sub-queue further based on the comparison.

### Claim 10 (depends on 1)

The method of claim 1, wherein the amount of the resource comprises at least one of:
a byte value;
a number of packet buffers; or
a delay threshold.

### Claim 11

A computer system, comprising:
at least one processing resource; and
at least one non-transitory machine-readable storage device comprising instructions executable by the at least one processing resource to:
maintain a queue structure used for storing packets and comprising a plurality of sub-queues used to process the packets, wherein the packets in the queue structure are to be dequeued by a scheduler;
compute a respective packet virtual time for a respective packet based on at least a packet virtual time of a previous packet processed by the same sub-queue, wherein the respective packet virtual time indicates a relative progress of the respective packet in the sub-queue;
compute a global virtual time based on a packet virtual time of a packet being dequeued from the queue structure by the scheduler;
measure a rate at which the global virtual time progresses based on the virtual time of packets dequeued by the scheduler from the queue structure; and
manage congestion in the sub-queues based on the rate at which the global virtual time progresses, a metric of a respective sub-queue, and an amount of a resource for the queue structure.

### Claim 12 (depends on 11)

The computer system of claim 11,
wherein the instructions to manage the congestion in the sub-queues are further to perform at least one of: drop one or more packets; or change an explicit congestion notification (ECN) value in a header of one or more packets.

### Claim 13 (depends on 11)

The computer system of claim 11,
wherein the instructions to manage the congestion in the sub-queues are further to transmit at least one of: a pause frame; a flow control signal; or a flow control packet.

### Claim 14 (depends on 11)

The computer system of claim 11, wherein the instructions to manage the congestion in the sub-queues are further to:
scale the metric of the respective sub-queue based on the rate at which the global virtual time progresses;
compare the scaled metric of the respective sub-queue with the amount of the resource for the queue structure; and
manage the congestion in the respective sub-queue based on the comparison.

### Claim 15 (depends on 11)

The computer system of claim 11, wherein the instructions to manage the congestion in the sub-queues are further based on a length of the respective sub-queue.

### Claim 16 (depends on 15)

The computer system of claim 15, wherein the instructions are further to:
determine a predicted delay based on the length of the respective sub-queue;
compute a probability based on the predicted delay and a configured target delay; and
manage the congestion in the respective sub-queue further based on the probability.

### Claim 17 (depends on 11)

The computer system of claim 11, wherein the instructions are further to:
compute a dynamic threshold based on the amount of the resource and the measured global virtual time rate;
compare a current size of the respective sub-queue to the dynamic threshold; and
manage the congestion in the respective sub-queue further based on the comparison.

### Claim 18 (depends on 11)

The computer system of claim 11, wherein the amount of the resource comprises at least one of:
a byte value;
a number of packet buffers; or
a delay threshold.

### Claim 19

A non-transitory computer-readable storage medium comprising instructions executable by a processing resource to:
maintain a queue structure used for storing packets and comprising a plurality of sub-queues used to process the packets, wherein the packets in the queue structure are to be dequeued by a scheduler;
maintain a respective packet virtual time for a respective packet based on at least a packet virtual time of a previous packet processed by the same sub-queue, wherein the respective packet virtual time indicates a relative progress of the respective packet in the sub-queue;
compute a global virtual time based on a packet virtual time of a packet being dequeued from the queue structure by the scheduler;
measure a rate at which the global virtual time progresses based on the virtual time of packets dequeued by the scheduler from the queue structure; and
manage congestion in the sub-queues based on the rate at which the global virtual time progresses, a metric of a respective sub-queue, and an amount of a resource for the queue structure.

### Claim 20 (depends on 19)

The non-transitory computer-readable storage medium of claim 19, wherein the instructions to manage the congestion in the respective sub-queue are further to:
scale the metric of the respective sub-queue based on the rate at which the global virtual time progresses;
compare the scaled metric of the respective sub-queue with the amount of the resource for the queue structure; and
manage the congestion in the respective sub-queue based on the comparison.
