Device and method for scalable traffic shaping with a time-indexed data structure

Patent metadata

Field	Value
Publication number	US-10454835-B2
Application number	US-201715411341-A
Country	US
Kind code	B2
Filing date	Jan 20, 2017
Priority date	Jan 20, 2017
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

Systems and methods of performing rate limiting traffic shaping with a time-indexed data structure in a network device are provided. A network interface driver of the network device can received packets at the packet layer of a network host from a plurality of applications. The network interface driver can prevent one of the applications from sending additional packets for transmission until the application received a transmission completion notification indicating a packet previously forwarded to the packet layer of the network host has been transmitted. The network interface driver can process the received packets to determine a transmission time for each packet based on at least on rate limit policy. The network interface driver can store an identifier associated with the respective packet in a time-indexed data structure at a position associated with the transmission time determined for the packet. The network interface driver can determine that a time indexed in the time-indexed data structure has been reached and in response transmit a packet associated with the identifier stored in the time-indexed data structure at a position associated with the reached time. The network interface driver can communicate a transmission completion notification subsequent to the network interface driver transmitting the packet.

First claim

What is claimed is:

1. A network device, comprising:
a network interface card,
at least one processor,
a memory; and
a network interface driver comprising computer-readable instructions executing on the at least one processor configured to:
receive packets at a packet layer of the network device from a plurality of applications executing on the network device;
prevent one of the applications executing on the network device from sending additional packets to the packet layer for transmission until the application receives a transmission completion notification indicating a packet previously forwarded by the application to the packet layer of the network device has been transmitted;
process, by a scheduling module, the received packets to determine a transmission time for each packet based on at least one rate limit policy;
for each of the packets to be transmitted, store an identifier associated with the respective packet in a time-indexed data structure at a position in the time-indexed data structure associated with the transmission time determined for the packet;
determine, by the scheduling module, that a time indexed in the time-indexed data structure has been reached, and in response, transmitting by the network interface card a packet associated with an identifier stored in the time-indexed data structure at a position associated with the reached time; and
subsequent to the network interface card transmitting the packet, communicate a transmission completion notification back to the application executing on the network device from which the packet was received at the packet layer.

2. The network device of claim 1 , wherein the network interface driver is further configured to receive a predetermined number of packets from one of the plurality of applications prior to preventing such application from sending additional packets for transmission.

3. The network device of claim 1 , wherein the network interface driver is further configured to receive packets from a plurality of applications executing in one of virtual machines, container execution environments, or a combination of virtual machines and container execution environments.

4. The network device of claim 1 , wherein the network interface driver is further configured determine a transmission time for each packet based on a rate pacing policy or a target rate limit.

5. The network device of claim 4 , wherein the rate pacing policy further includes a packet class rate policy and/or an aggregate rate policy.

6. The network device of claim 5 , wherein the rate pacing policy further includes a weighted fair queueing policy to process multiple packet flows.

7. The network device of claim 1 , wherein the network interface driver is further configured to receive packets including a requested transmission time assigned to the packet by one of the plurality of applications before being received at the packet layer and before being processed by the scheduling module.

8. The network device of claim 7 , wherein the network interface driver is further configured to determine an updated transmission time based on at least one rate limit policy being exceeded and invoking a rate limit algorithm associated with the received packet.

9. The network device of claim 8 , wherein the network interface driver is further configured to find the associated rate limit algorithm using a hash table or a mapping identifying a rate limit algorithm associated with the received packet.

10. The network device of claim 1 , wherein the network interface driver executing computer-readable instructions is implemented on a dedicated CPU core.

11. The network device of claim 1 , wherein the network interface driver is further configured to identify a transmission time older than now and in response to the determining, transmitting the packet by the network interface card.

12. A method, comprising:
receiving packets at a packet layer of a network host from a plurality of applications executing on the network host;
preventing one of the applications executing on the network host from sending additional packets to the packet layer for transmission until the application receives a transmission completion notification indicating a packet previously forwarded by the application to the packet layer of the network host has been transmitted;
processing, by a scheduling module, the received packets to determine a transmission time for each packet based on at least one rate limit policy;
for each of the packets to be transmitted, storing an identifier associated with the respective packet in a time-indexed data structure at a position in the time-indexed data structure associated with the transmission time determined for the packet;
determining, by the scheduling module, that a time indexed in the time-indexed data structure has been reached, and in response, transmitting by a network interface card a packet associated with an identifier stored in the time-indexed data structure at a position associated with the reached time; and
subsequent to the network interface card transmitting the packet, communicating, a transmission completion notification back to the application executing on the network host from which the packet was received at the packet layer.

13. The method of claim 12 , wherein, prior to preventing one of the applications from sending additional packets for transmission, receiving a predetermined number of packets from such application.

14. The method of claim 12 , wherein the received packets comprise packets received from a plurality of applications executing in one of virtual machines, container execution environments, or a combination of virtual machines and container execution environments.

15. The method of claim 12 , wherein the at least one rate limit policy further includes a rate pacing policy or a target rate limit.

16. The method of claim 15 , wherein the rate pacing policy further includes a packet class rate policy and/or an aggregate rate policy.

17. The method of claim 16 , wherein the rate pacing policy further includes a weighted fair queueing policy to process multiple packet flows.

18. The method of claim 12 , wherein the transmission time for at least one packet is based on a requested transmission time assigned to the packet by one of the plurality of applications before being received at the packet layer and before being processed by the scheduling module.

19. The method of claim 12 , wherein determining a transmission time for each packet further comprises:
determining an updated transmission time based on at least one rate limit policy being exceeded and invoking a rate limit algorithm associated with the received packet.

20. The method of claim 19 , wherein the algorithm used to find the associated rate limit algorithm includes a hash table or a mapping identifying a rate limit algorithm associated with the received packet.

21. The method of claim 12 , wherein the method is implemented in computer-readable executable instructions on a dedicated CPU core.

22. The method of claim 12 , wherein in determining a transmission time for each packet further comprises:
identifying a transmission time older than now and in response to the determining, transmitting the packet by the network interface card.

Assignees

• Google Llc

Inventors

• Contavalli Carlo
• Dukkipati Nandita
• Issa Ahmed Said Mohamed Tawfik
• Valancius Vytautas

Classifications

• H04L47/193

  at the transport layer, e.g. TCP related · CPC title

• H04L47/225 Primary

  Determination of shaping rate, e.g. using a moving window · CPC title

• H04L47/568

  Calendar queues or timing rings · CPC title

• H04L47/564

  Attaching a deadline to packets, e.g. earliest due date first · CPC title

• H04L69/163

  In-band adaptation of TCP data exchange; In-band control procedures · CPC title