Network communication rate limiter

• US 9,654,483 B1
• Filed: 12/23/2014
• Issued: 05/16/2017
• Est. Priority Date: 12/23/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Benson, Bryan Mark, Diggins, Michael F., Romanov, Anton, Lu, David Dongyi, Wang, Xingbo
• Primary Examiner(s): Cervetti, David Garcia
• Application Number:
  US14/582,054
• Time in Patent Office: 875 Days
• Field of Search: 713156, 713185, 713172, 726 4
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 63/108 when the policy decisions are valid for a limited amount of time
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 63/1466 Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks

Abstract

A technology is described for limiting the rate at which a number of requests to perform a network action are granted using rate limiters. An example method may include receiving a request for a token granting permission to perform a network action via a computer network. In response, rate limiters may be identified by generating hash values using hash functions and a network address representing a source network where the hash values identify memory locations for the rate limiters. The rate limiters may have a computer memory capacity to store tokens that are distributed in response to the request. Token balances for the rate limiters may be determined, and permission to perform the network action may be granted as a result of at least one of the token balances being greater than zero.

Claims

1. A non-transitory machine readable storage medium having instructions embodied thereon, wherein the instructions, when executed by a processor, cause the processor to:

receive a request for a token granting permission to perform a network action, wherein the request is associated with an IP (Internet Protocol) address used to identify a source network;

identify k rate limiters for the source network by generating k hash values from the IP address using k hash functions where the k hash values identify k memory locations containing the k rate limiters and where k is a natural number greater than zero, a given rate limiter being included in a group of rate limiters having a time counter where each rate limiter has a capacity to store a number of tokens and where tokens are added to each of the rate limiters in the group of rate limiters according to the time counter, wherein a predetermined number of tokens are added to each of the rate limiters in the group of rate limiters as a result of the request for the token being received and a value of the time counter being zero;

determine a respective token balance for each of the k rate limiters for the source network in response to the request;

determine that at least one token balance for a k rate limiter is greater than zero; and

provide a token in response to the request.

2. A non-transitory machine readable storage medium as in claim 1, wherein the instructions further cause the processor to:

determine an expiration of at least one time unit as a result of checking the token balances for the k rate limiters and the token balances being equal to zero; and

add the predetermined number of tokens to each rate limiter included in the group of rate limiters for each time unit that has expired.

3. A non-transitory machine readable storage medium as in claim 1, wherein the k rate limiters are identified in response to the request for the token, the token granting permission to a source client to connect to a destination host via a computer network.

4. A computer implemented method, comprising:

receiving a request for a token granting permission to process a network communication via a computer network;

identifying, using a processor, k rate limiters for a source network by generating k hash values using k hash functions and a network address representing the source network where the k hash values identify k memory locations for the k rate limiters, the k rate limiters having a computer memory capacity to store tokens that are distributed in response to the request, wherein k is a natural number greater than zero;

determining that at least one token balance for the k rate limiters stored in the computer memory is greater than zero in response to the request using the processor;

granting permission to process the network communication; and

decrementing the at least one token balance.

5. A method as in claim 4, further comprising providing the token to a requester granting permission to process the network communication as a result of the at least one of the token balances being greater than zero.

6. A method as in claim 4, further comprising denying permission to a requester to further process the network communication when one of the token balances is equal to zero and a time counter has not expired.

7. A method as in claim 4, wherein identifying the k rate limiters for a source network further comprises, identifying the k rate limiters included in at least one group of rate limiters, wherein each group of rate limiters includes a respective countdown timer that represents when tokens are added to rate limiters included in that group of rate limiters.

8. A method as in claim 4, further comprising adding a predetermined number of tokens to a respective token balance for each of the k rate limiters included in a group of rate limiters as a result of an expiration of a time unit as determined by a time counter.

9. A method as in claim 4, wherein a time counter is used to demarcate a time unit in which an allocation of tokens is added to each of the token balances of at least a subset of the k rate limiters.

10. A method as in claim 4, wherein determining respective token balances for k rate limiters in response to the request comprises:

determining an expiration of a number of time units as determined by a time counter since the respective token balance was last determined; and

adding a predetermined number of tokens to the respective token balance for each of the number of time units that have expired.

11. A method as in claim 10, wherein adding the predetermined number of tokens to the respective token balance for each rate limiter is performed using vector instructions for the processor that add the predetermined number of tokens to the respective token balance of each of the k rate limiters included in a group of rate limiters.

12. A method as in claim 10, wherein adding the predetermined number of tokens to the respective token balance further comprises, determining a maximum token capacity of a given rate limiter and adding a number of tokens equal to a lesser of the predetermined number of tokens and the token capacity minus a current token balance of the given rate limiter.

13. A method as in claim 10, wherein the time counter references a timestamp that records a last refill period.

14. A method as in claim 13, further comprising:

comparing a system time with the timestamp; and

determining whether a predetermined amount of time has passed since the last refill period based on the comparing the system time with the timestamp.

15. A method as in claim 10, wherein an increment of the time counter represents a time unit within which an allocation of the predetermined number of tokens are allocated to each of the k rate limiters.

16. A method as in claim 4, wherein a size of a group of the rate limiters is based on the size of a cache line of the processor, the cache line storing a time counter.

17. A system comprising:

a processor;

a memory device including instructions that, when executed by the processor, cause the system to;

identify k rate limiters for a source network by generating k hash values from a network address representing the source network using k hash functions where the k hash values identify k memory locations containing the k rate limiters where k is a natural number greater than zero;

include a rate limiter of the k rate limiters in a group of rate limiters having a countdown timer, where each rate limiter of the k rate limiters can store a number of tokens used to grant permission to forward a network communication, wherein tokens are added to each rate limiter in the group of rate limiters according to a time counter of the group;

determine respective token balances for the k rate limiters, wherein

a predetermined number of tokens are added to each of the token balances of the rate limiters included in the group of rate limiters as a result of an expiration of a time unit as determined by the time counter;

expiration of at least one time unit is checked for as a result of checking the token balances of the k rate limiters and adding the predetermined number of tokens to the token balances of the rate limiters included in the group of rate limiters for each time unit that has expired;

provide a token as a result of at least one of the token balances of the k rate limiters being greater than zero; and

decrement a token balance for a rate limiter included in the k rate limiters as a result of providing a token.

18. A system as in claim 17, wherein the instructions further cause the system to identify the k rate limiters in response to a request for a token that grants permission to a source client to connect to a destination host via a computer network.

19. A system as in claim 17, wherein the instructions further cause the system:

receive a network packet sent through a computer network;

request a token granting permission to transmit the network packet to a destination host; and

drop the network packet as a result of the respective token balances for the k rate limiters being equal to zero, thereby mitigating a network attack by preventing the network packet from reaching an intended destination host.

20. A system as in claim 17, wherein the instructions further cause the system to add the predetermined number of tokens to the token balance for each rate limiter included in a group of rate limiters using a SIMD (Single Instruction Multiple Data) instruction for the processor.