# US 10,454,835 B2 · Device and method for scalable traffic shaping with a time-indexed data structure > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,454,835 B2 - Document ID: US10454835B2 - Status: Granted - Kind: B2 - Application number: 15/411,341 - Filed: 2017-01-20 - Published: 2018-07-26 - Granted: 2019-10-22 - Earliest claimed: 2017-01-20 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Carlo Contavalli; Nandita Dukkipati; Ahmed Said Mohamed Tawfik Issa; Vytautas Valancius - Web page: https://patentgrep.com/patent/US10454835B2 ## CPC - H04L 47/225: {Determination of shaping rate, e.g. using a moving window} - H04L 47/22: Traffic shaping - H04L 47/193: at the transport layer, e.g. TCP related - H04L 47/564: {Attaching a deadline to packets, e.g. earliest due date first} - H04L 47/568: {Calendar queues or timing rings} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) The network device of claim 4, wherein the rate pacing policy further includes a packet class rate policy and/or an aggregate rate policy. ### Claim 6 (depends on 5) The network device of claim 5, wherein the rate pacing policy further includes a weighted fair queueing policy to process multiple packet flows. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 1) The network device of claim 1, wherein the network interface driver executing computer-readable instructions is implemented on a dedicated CPU core. ### Claim 11 (depends on 1) 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. ### Claim 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. ### Claim 13 (depends on 12) 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. ### Claim 14 (depends on 12) 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. ### Claim 15 (depends on 12) The method of claim 12, wherein the at least one rate limit policy further includes a rate pacing policy or a target rate limit. ### Claim 16 (depends on 15) The method of claim 15, wherein the rate pacing policy further includes a packet class rate policy and/or an aggregate rate policy. ### Claim 17 (depends on 16) The method of claim 16, wherein the rate pacing policy further includes a weighted fair queueing policy to process multiple packet flows. ### Claim 18 (depends on 12) 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. ### Claim 19 (depends on 12) 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. ### Claim 20 (depends on 19) 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. ### Claim 21 (depends on 12) The method of claim 12, wherein the method is implemented in computer-readable executable instructions on a dedicated CPU core. ### Claim 22 (depends on 12) 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.