Methods for traffic rate control and devices thereof

• US 10,187,317 B1
• Filed: 11/17/2014
• Issued: 01/22/2019
• Est. Priority Date: 11/15/2013
• Status: Active Grant

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Amdahl, Saxon, Majee, Sumandra, Shukla, Rajendra
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): Zhang, Zhensheng
• Application Number:
  US14/542,840
• Time in Patent Office: 1,527 Days
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/39 Credit based

Abstract

A method, non-transitory computer readable medium, and traffic management computing device that allocates a subset of tokens to active subscribers based on an estimated number of subscribers that will be active in a next sampling period. A request to transmit a first packet is received from one of the active subscribers. A determination is made when a current time is prior to an expiration of the allocated subset of the tokens. Another determination is made when a length of the first packet is less than a size corresponding to an available portion of the allocated subset of the tokens when the current time is determined to be prior to the expiration of the allocated subset of the tokens. The first packet is transmitted when the length of the first packet is determined to be less than a size corresponding to an available portion of the allocated subset of the tokens.

Claims

1. A method for traffic rate control implemented by a network traffic management system comprising one or more network traffic management devices, server devices, or client devices, the method comprising:

allocating a proportional subset of an amount of tokens to a plurality of subscribers based on an estimated number of the plurality of subscribers that will be active in a next sampling period;

receiving a request to transmit a first packet from a subscriber of the plurality of subscribers;

querying a database to retrieve a state value associated with the subscriber;

determining when the subscriber is in an active state based on analyzing the retrieved state value;

determining an expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens, when the determination indicates that the subscriber is in the active state;

comparing the determined expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens with a current time;

determining the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired when the comparison indicates that the current time is less than an expiration time;

determining when the first packet is to be transmitted based on one or more token policies upon determining that the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired;

queuing the first packet in a first queue when the determining indicates that the first packet cannot transmitted based on the one or more token policies;

retrieving one of a plurality of subscriber contexts associated with the subscriber of the plurality of subscribers;

determining when a difference between a current time and a last visit time of the one subscriber context is less than a size of a sampling period, a transmission count of the one subscriber context is equal to zero for a last sampling period, and a state of the one subscriber context indicates an active state;

setting a last visit time of the one subscriber context to the current time; and

repeating the retrieving, determining, and setting for each other of the plurality of subscriber contexts.

2. The method of claim 1, further comprising:

transmitting the first packet, without queueing the first packet, when the determining indicates that the first packet is to be transmitted based on the one or more token policies, wherein the one or more token policies comprises borrowing tokens from the next sampling period.

3. The method of claim 1, further comprising:

determining when a flow time associated with the first packet has expired;

scheduling a resubmission of the queued first packet when the determination indicates that the flow time has expired;

receiving a request to transmit a second packet from one currently inactive subscriber of the plurality of subscribers;

allocating a plurality of tokens equivalent to the proportional subset of the amount of tokens to the one currently inactive subscriber;

transmitting the second packet;

incrementing a transmission count for a current sampling period for the one currently inactive subscriber;

debiting the proportional subset of tokens allocated to the one currently inactive subscriber based on a length of the second packet; and

modifying a subscriber context corresponding to the one currently inactive subscriber to indicate an active state.

4. The method of claim 1, further comprising:

determining when there are one or more outstanding packets;

implementing the one or more token policies to determine when one or more of the outstanding packets are able to be transmitted when the determining indicates that there are the one or more outstanding packets; and

transmitting the one or more of the outstanding packets and repeating the allocating, wherein the amount of tokens is reduced based on a size of the one or more of the outstanding packets, when the determining indicates that the one or more of the outstanding packets are able to be transmitted.

5. The method of claim 1, further comprising:

implementing an early drop policy to determine when the first packet is able to be transmitted when a length of the first packet is determined to be less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state;

only transmitting the first packet when the determining indicates that the first packet is able to be transmitted; and

marking the first packet as not transmitted, setting a TCP flow timer, determining when the TCP flow timer has expired, and receiving another request to transmit the first packet when the determining indicates that the TCP flow timer has expired, when the determining indicates that the first packet is able to be transmitted based on the implemented early drop policy or when the determining indicates that the length of the first packet is not less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state.

6. A traffic management computing device, comprising memory comprising programmed instructions stored thereon and one or more processors configured to be capable of executing the stored programmed instructions to:

allocate a proportional subset of an amount of tokens to a plurality of subscribers based on an estimated number of the plurality of subscribers that will be active in a next sampling period;

receive a request to transmit a first packet from a subscriber of the plurality of subscribers;

query a database to retrieve a state value associated with the subscriber;

determine when the subscriber is in an active state based on analyzing the retrieved state value;

determine an expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens, when the determination indicates that the subscriber is in the active state;

compare the determined expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens with a current time;

determine the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired, when the comparison indicates that the current time is less than an expiration time;

determine when the first packet is to be transmitted based on one or more token policies upon determining that the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired;

queue the first packet in a first queue when the determining indicates that the first packet cannot be transmitted based on the one or more token policies;

retrieve one of a plurality of subscriber contexts associated with the subscriber of the plurality of subscribers;

determine when a difference between a current time and a last visit time of the one subscriber context is less than a size of a sampling period, a transmission count of the one subscriber context is equal to zero for a last sampling period, and a state of the one subscriber context indicates an active state;

set a last visit time of the one subscriber context to the current time; and

repeat the retrieving, determining, and setting for each other of the plurality of subscriber contexts.

7. The traffic management computing device of claim 6, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

transmit the first packet, without queueing the first packet, when the determining indicates that the first packet is to be transmitted based on the one or more token policies, wherein the one or more token policies comprises borrowing tokens from the next sampling period.

8. The traffic management computing device of claim 6, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

determine when a flow time associated with the first packet has expired;

schedule a resubmission of the queued first packet when the determination indicates that the flow time has expired;

receive a request to transmit a second packet from one currently inactive subscriber of the plurality of subscribers;

allocate a plurality of tokens equivalent to the proportional subset of the amount of tokens to the one currently active subscriber;

transmit the second packet;

increment a transmission count for a current sampling period for the one currently inactive subscriber;

debit the proportional subset of tokens allocated to the one currently inactive subscriber based on a length of the second packet; and

modify a subscriber context corresponding to the one currently inactive subscriber to indicate an active state.

9. The traffic management computing device of claim 6, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

determine when there are one or more outstanding packets;

implement the one or more token policies to determine when one or more of the outstanding packets are able to be transmitted when the determining indicates that there are the one or more outstanding packets; and

transmit the one or more of the outstanding packets and repeat the allocating, wherein the amount of tokens is reduced based on a size of the one or more of the outstanding packets, when the determining indicates that the one or more of the outstanding packets are able to be transmitted.

10. The traffic management computing device of claim 6, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

implement an early drop policy to determine when the first packet is able to be transmitted when a length of the first packet is determined to be less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state;

only transmit the first packet when the determining indicates that the first packet is able to be transmitted; and

mark the first packet as not transmitted, setting a TCP flow timer, determining when the TCP flow timer has expired, and receiving another request to transmit the first packet when the determining indicates that the TCP flow timer has expired, when the determining indicates that the first packet is able to be transmitted based on the implemented early drop policy or when the determining indicates that the length of the first packet is not less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state.

11. A non-transitory computer readable medium having stored thereon instructions for traffic rate control comprising machine executable code which when executed by one or more processors, causes the one or more processors to:

allocate a proportional subset of an amount of tokens to a plurality of subscribers based on an estimated number of the plurality of subscribers that will be active in a next sampling period;

receive a request to transmit a first packet from a subscriber of the plurality of subscribers;

query a database to retrieve a state value associated with the subscriber;

determine when subscriber is in an active state based on analyzing the retrieved state value;

determine an expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens, when the determination indicates that the subscriber is in the active state;

compare the determined expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens with a current time;

determine the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired when the comparison indicates that the current time is less than an expiration time;

determine when the first packet is to be transmitted based on one or more token policies upon determining that the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired;

queue the first packet in a first queue when the determining indicates that the first packet cannot-be transmitted based on the one or more token policies;

retrieve one of a plurality of subscriber contexts associated with the subscriber of the plurality of subscribers;

determine when a difference between a current time and a last visit time of the one subscriber context is less than a size of a sampling period, a transmission count of the one subscriber context is equal to zero for a last sampling period, and a state of the one subscriber context indicates an active state;

set a last visit time of the one subscriber context to the current time; and

repeat the retrieving, determining, and setting for each other of the plurality of subscriber contexts.

12. The non-transitory computer readable medium of claim 11, wherein the machine executable code when executed by the one or more processors further causes the one or more processors to:

transmit the first packet, without queueing the first packet, when the determining indicates that the first packet is to be transmitted based on the one or more token policies, wherein the one or more token policies comprises borrowing tokens from the next sampling period.

13. The non-transitory computer readable medium of claim 11, wherein the machine executable code when executed by the one or more processors further causes the one or more processors to:

determine when a flow time associated with the first packet has expired;

schedule a resubmission of the queued first packet when the determination indicates that the flow time has expired;

receive a request to transmit a second packet from one currently inactive subscriber of the plurality of subscribers;

allocate a plurality of tokens equivalent to the proportional subset of the amount of tokens to the one currently active subscriber;

transmit the second packet;

increment a transmission count for a current sampling period for the one currently inactive subscriber;

debit the proportional subset of tokens allocated to the one currently inactive subscriber based on a length of the second packet; and

modify a subscriber context corresponding to the one currently inactive subscriber to indicate an active state.

14. The non-transitory computer readable medium of claim 11, wherein the machine executable code when executed by the one or more processors further causes the one or more processors to:

determine when there are one or more outstanding packets;

implement the one or more token policies to determine when one or more of the outstanding packets are able to be transmitted when the determining indicates that there are the one or more outstanding packets; and

transmit the one or more of the outstanding packets and repeat the allocating, wherein the amount of tokens is reduced based on a size of the one or more of the outstanding packets, when the determining indicates that the one or more of the outstanding packets are able to be transmitted.

15. The non-transitory computer readable medium of claim 11, wherein the machine executable code when executed by the one or more processors further causes the one or more processors to:

implement an early drop policy to determine when the first packet is able to be transmitted when a length of the first packet is determined to be less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state;

only transmit the first packet when the determining indicates that the first packet is able to be transmitted; and

mark the first packet as not transmitted, setting a TCP flow timer, determining when the TCP flow timer has expired, and receiving another request to transmit the first packet when the determining indicates that the TCP flow timer has expired, when the determining indicates that the first packet is able to be transmitted based on the implemented early drop policy or when the determining indicates that the length of the first packet is not less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state.

16. A network traffic management system, comprising one or more network traffic management devices, server devices, or client devices, the network traffic management system comprising memory comprising programmed instructions stored thereon and one or more processors configured to be capable of executing the stored programmed instructions to:

allocate a proportional subset of an amount of tokens to a plurality of subscribers based on an estimated number of the plurality of subscribers that will be active in a next sampling period;

receive a request to transmit a first packet from a subscriber of the plurality of subscribers;

query a database to retrieve a state value associated with the subscriber;

determine when the subscriber is in an active state based on analyzing the retrieved state value;

determine an expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens, when the determination indicates that the subscriber is in the active state;

compare the determined expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens with a current time;

determine the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired when the comparison indicates that the current time is less than an expiration time;

determine when the first packet is to be transmitted based on one or more token policies upon determining that the expiration time associated with each of the tokens in the allocated proportional subset of the amount of tokens has not expired;

queue the first packet in a first queue when the determining indicates that the first packet cannot be transmitted based on the one or more token policies;

retrieve one of a plurality of subscriber contexts associated with the subscriber of the plurality of subscribers;

determine when a difference between a current time and a last visit time of the one subscriber context is less than a size of a sampling period, a transmission count of the one subscriber context is equal to zero for a last sampling period, and a state of the one subscriber context indicates an active state;

set a last visit time of the one subscriber context to the current time; and

repeat the retrieving, determining, and setting for each other of the plurality of subscriber contexts.

17. The network traffic management system of claim 16, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

transmit the first packet, without queueing the first packet, when the determining indicates that the first packet is to be transmitted based on the one or more token policies, wherein the one or more token policies comprises borrowing tokens from the next sampling period.

18. The network traffic management system of claim 16, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

determine when a flow time associated with the first packet has expired; and

schedule a resubmission of the queued first packet when the determination indicates that the flow time has expired;

receive a request to transmit a second packet from one currently inactive subscriber of the plurality of subscribers;

allocate a plurality of tokens equivalent to the proportional subset of the amount of tokens to the one currently active subscriber;

transmit the second packet;

increment a transmission count for a current sampling period for the one currently inactive subscriber;

debit the proportional subset of tokens allocated to the one currently inactive subscriber based on a length of the second packet; and

modify a subscriber context corresponding to the one currently inactive subscriber to indicate an active state.

19. The network traffic management system of claim 16, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

determine when there are one or more outstanding packets;

implement the one or more token policies to determine when one or more of the outstanding packets are able to be transmitted when the determining indicates that there are the one or more outstanding packets; and

transmit the one or more of the outstanding packets and repeat the allocating, wherein the amount of tokens is reduced based on a size of the one or more of the outstanding packets, when the determining indicates that the one or more of the outstanding packets are able to be transmitted.

20. The network traffic management system of claim 16, wherein the one or more processors are further configured to be capable of executing the stored programmed instructions to:

implement an early drop policy to determine when the first packet is able to be transmitted when a length of the first packet is determined to be less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state;

only transmit the first packet when the determining indicates that the first packet is able to be transmitted; and

mark the first packet as not transmitted, setting a TCP flow timer, determining when the TCP flow timer has expired, and receiving another request to transmit the first packet when the determining indicates that the TCP flow timer has expired, when the determining indicates that the first packet is able to be transmitted based on the implemented early drop policy or when the determining indicates that the length of the first packet is not less than a size corresponding to the allocated proportional subset of the amount of tokens allocated to the one of the subscriber in the active state.