High performance connection scheduler

Patent metadata

Field	Value
Publication number	US-11979476-B2
Application number	US-202217961669-A
Country	US
Kind code	B2
Filing date	Oct 7, 2022
Priority date	Oct 7, 2022
Publication date	May 7, 2024
Grant date	May 7, 2024

Abstract

Aspects of the disclosure are directed to a high performance connection scheduler for reliable transport protocols in data center networking. The connection scheduler can handle enqueue events, dequeue events, and update events. The connection scheduler can include a connection queue, scheduling queue, and quality of service arbiter to support scheduling a large number of connections at a high rate.

First claim

The invention claimed is:

1. A method for scheduling connections related to data packets, the method comprising:
performing, with one or more processors, an eligibility check on a connection, the eligibility check comprising determining that the connection is within one or more congestion windows associated with a transaction type of the connection;
queueing, with the one or more processors, the connection in a scheduling queue of a plurality of scheduling queues based on the transaction type of the connection, each scheduling queue of the plurality of scheduling queues being associated with a transaction type;
selecting, with the one or more processors, the connection from the scheduling queue based on a quality of service (QoS) arbiter decision; and
queueing, with one or more processors, the selected connection in a connection queue of a plurality of connection queues based on the transaction type of the selected connection, each connection queue of the plurality of connection queues being associated with a transaction type.

2. The method of claim 1 , wherein the scheduling queues and the connection queues each comprise a plurality of linked lists, each linked list corresponding to a respective scheduling queue or connection queue.

3. The method of claim 2 , wherein the plurality of linked lists of the scheduling queues and the plurality of linked lists of the connection queues each comprise linked lists for at least one of push requests, unordered push requests, push grants, push data, or pull data transaction types.

4. The method of claim 1 , wherein the one or more congestion windows comprise a network congestion window and an end-node congestion window.

5. The method of claim 4 , wherein passing the eligibility check comprises determining that a number of outstanding requests is less than the end-node congestion window.

6. The method of claim 4 , wherein passing the eligibility check comprises determining that a packet sequence number is less than a base sequence number plus the network congestion window.

7. The method of claim 1 , further comprising performing, with the one or more processors, a solicitation check on the connection, the solicitation check comprising determining that an inflight count based on the connection is within a solicitation window.

8. The method of claim 7 , wherein passing the solicitation check further comprises determining that a rate counter is greater than a threshold.

9. The method of claim 1 , wherein selecting the connection from the scheduling queue further comprises selecting the scheduling queue based on at least one of a priority level or a weight of the scheduling queue.

10. The method of claim 1 , wherein selecting the connection from the scheduling queue is based on a weight of the connection.

11. A system comprising:
one or more processors; and
one or more storage devices coupled to the one or more processors and storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations for scheduling connections related to data packets, the operations comprising:
performing an eligibility check on a connection, the eligibility check comprising determining that the connection is within one or more congestion windows associated with a transaction type of the connection;
queueing the connection in a scheduling queue of a plurality of scheduling queues based on the transaction type of the connection, each scheduling queue of the plurality of scheduling queues being associated with a transaction type;
selecting the connection from the scheduling queue based on a quality of service (QoS) arbiter decision; and
queueing the selected connection in a connection queue of a plurality of connection queues based on the transaction type of the selected connection, each connection queue of the plurality of connection queues being associated with a transaction type.

12. The system of claim 11 , wherein the scheduling queues and the connection queues each comprise a plurality of linked lists, each linked list corresponding to a respective scheduling queue or connection queue.

13. The system of claim 11 , wherein:
the one or more congestion windows comprise a network congestion window and an end-node congestion window;
passing the eligibility check comprises determining that a number of outstanding requests is less than the end-node congestion window; and
passing the eligibility check comprises determining that a packet sequence number is less than a base sequence number plus the network congestion window.

14. The system of claim 11 , wherein the operations further comprise performing a solicitation check on the connection, the solicitation check comprising determining that an inflight count based on the connection is within a solicitation window.

15. The system of claim 11 , wherein selecting the connection from the scheduling queue is based on a weight of the connection and further comprises selecting the scheduling queue based on at least one of a priority level or a weight of the scheduling queue.

16. A non-transitory computer readable medium for storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations for scheduling connections related to data packets, the operations comprising:
performing an eligibility check on a connection, the eligibility check comprising determining that the connection is within one or more congestion windows associated with a transaction type of the connection;
queueing the connection in a scheduling queue of a plurality of scheduling queues based on the transaction type of the connection, each scheduling queue of the plurality of scheduling queues being associated with a transaction type;
selecting the connection from the scheduling queue based on a quality of service (QoS) arbiter decision; and
queueing the selected connection in a connection queue of a plurality of connection queues based on the transaction type of the selected connection, each connection queue of the plurality of connection queues associated with a transaction type.

17. The non-transitory computer readable medium of claim 16 , wherein the scheduling queues and the connection queues each comprise a plurality of linked lists, each linked list corresponding to a respective scheduling queue or connection queue.

18. The non-transitory computer readable medium of claim 16 , wherein:
the one or more congestion windows comprise a network congestion window and an end-node congestion window;
passing the eligibility check comprises determining that a number of outstanding requests is less than the end-node congestion window; and
passing the eligibility check comprises determining that a packet sequence number is less than a base sequence number plus the network congestion window.

19. The non-transitory computer readable medium of claim 16 , wherein the operations further comprise performing a solicitation check on the connection, the solicitation check comprising determining that an inflight count based on the connection is within a solicitation window.

20. The non-transitory computer readable medium of claim 16 , wherein selecting the connection from the scheduling queue is based on a weight of the connection and further comprises selecting the scheduling queue based on at least one of a priority level or a weight of the scheduling queue.

Assignees

• Google Llc

Inventors

• Agarwal Abhishek
• Wang Weihuang
• Jiang Weiwei
• Vaduvatha Srinivas
• Zheng Jiazhen

Classifications

• H04L67/61 Primary

  taking into account QoS or priority requirements · CPC title

• H04L67/55

  Push-based network services · CPC title

• H04L47/50 Primary

  Queue scheduling · CPC title

• H04L47/60 Primary

  implementing hierarchical scheduling · CPC title

• H04L47/622

  Queue service order · CPC title