Method and system for network traffic rate control based on fractional tokens

• US 6,570,847 B1
• Filed: 03/18/1999
• Issued: 05/27/2003
• Est. Priority Date: 12/31/1998
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Hosein, Patrick A.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): SHAND, ROBERTA A
• Application Number:
  US09/271,910
• Time in Patent Office: 1,531 Days
• Field of Search: 370/230, 370/230.1, 370/231, 370/235, 370/236, 370/252, 370/352, 370/389, 370/400, 370/449, 370/450, 370/452, 370/454, 709/230, 709/232, 709/234, 709/235, 709/238
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer

Abstract

The present invention provides a method and system for regulating network traffic levels. The present invention utilizes a token distribution method for allocating traffic rates to network traffic sources that allows the message rate and token balance to be expressed as fractional numbers resulting in improved flexibility and smoother performance.

Claims

1. A method for regulating the traffic level on a telecommunications network, comprising:

using a traffic regulating element that allows the transmission of network messages based on a preallocated number of message tokens per each particular time period, and wherein said each particular time period is divided into subintervals, and wherein an equal portion of said message tokens is allocated to each of said subintervals;

receiving a request from a traffic source for permission to transmit a message;

determining the number of allocated message tokens contained in a token bank; and

transmitting a resoponse to said traffic source.

2. The method of claim 1 wherein:

if the number of message tokens available is greater than or equal to one, said response grants permission to said network traffic source to transmit a message.

3. The method of claim 2 further comprising the step of:

decrementing the number of available message tokens by one if the number of message tokens available is greater than or equal to one.

4. The method of claim 1 wherein:

if the number of message tokens available is less than one, said response denies permission to said network traffic source to transmit messages.

5. The method of claim 1 wherein:

said traffic regulating element increments said number of available message tokens by a number including a fractional component at a specified subinterval of said particular time period.

6. The method of claim 5 wherein;

said number including a fractional component is equal to said preallocated number of message tokens divided by the number of specified subintervals per said particular time period.

20. The method of claim 1 wherein said number of allocated message tokens is stored as a value with a fractional component.

7. A system for regulating the network traffic level on a telecommunications network, comprising:

a network traffic destination;

a plurality of network traffic sources; and

a network traffic regulating element coupled via the network to said plurality of network traffic sources and said network traffic destination,

wherein said network traffic regulating element only allows said plurality of network traffic sources to produce network traffic at a level less than or equal to a predetermined maximum traffic level,

wherein said network traffic regulating element maintains said maximum traffic level as a number of message tokens per each specified time period, wherein said tokens are distributed equally among subintervals over said each specified time period, and each token corresponding to permission to send a single network message, and

wherein said network traffic regulating element maintains a bank of available message tokens in such a way as to allow values with a fractional component.

8. The system of claim 7, wherein said plurality of network traffic sources include telephone switching equipment.

9. The system of claim 8, wherein said network traffic destination comprises a directory providing telephone call routing information.

10. The system of claim 7, wherein said plurality of network traffic sources includes web browser clients.

11. The system of claim 10, wherein said network traffic destination comprises a web server.

12. The system of claim 7 further comprising:

a second network traffic destination;

wherein said network traffic regulating element maintains a second maximum traffic level value separate from that associated with said first network traffic destination and separate token banks for each network traffic destination, and said network traffic level regulating element allows said plurality of network traffic sources to produce network traffic based on the destination of said network traffic produced.

13. A method for regulating the traffic level on a telecommunications network, comprising:

allocating a number of tokens to a token bank based on a predetermined rate of sending network messages;

determining whether a message is waiting to be sent over the network;

determining the amount of tokens in said token bank;

sending said message, if said amount of tokens is greater than or equal to one;

wherein said token bank can store the amount of tokens as a value including a fractional component,

wherein said allocated number of tokens is a number with a fractional component, and

wherein said rate of sending network messages is expressed as the maximum number of messages to be sent in a particular time period.

14. The method of claim 13, further comprising the step of:

decrementing said token bank by one, if said waiting message was sent.

15. The method of claim 14, wherein said allocating step is comprised of the substeps of:

dividing said particular time period into subintervals; and

distributing said number of tokens equally across said subintervals.

16. The method of claim 15 further comprising the step of:

resetting the number of tokens to a particular value if the number of tokens exceeds said particular value.

17. A system for regulating the network traffic level on a telecommunications network, comprising:

a network traffic destination; and

a network traffic source coupled via the network to said network traffic destination,

wherein said network traffic destination provides a maximum traffic level to said network traffic source, and said network traffic source produces network traffic at a level less than or equal to said maximum traffic level,

wherein said network traffic source maintains said maximum traffic level as a number of message tokens per each specified time period, wherein said tokens are distributed equally among subintervals over said each specified time period, and each token corresponding to permission to send a single network message, and

wherein said network traffic source maintains a bank of available message tokens in such a way as to allow values with a fractional component.

18. The system of claim 17, wherein:

said network traffic source is telephone switching equipment.

19. The system of claim 18, wherein:

said network traffic destination is a directory providing telephone call routing information.

21. A program storage device readable by a machine, tangibly embodying a program of executable instructions to perform a method for regulating the traffic level on a telecommunications network, the method comprising:

using a traffic regulating element that allows the transmission of network messages based on a preallocated number of message tokens per each particular time period, and wherein said each particular time period is divided into subintervals, and wherein an equal portion of said message tokens is allocated to each of said subintervals;

receiving a request from a traffic source for permission to transmit a message,

determining the number of allocated message tokens contained in a token bank; and

transmitting a response to said traffic source.

22. A program storage device readable by a machine, tangibly embodying a program of executable instructions to perform a method for regulating the traffic level on a telecommunications network, the method comprising:

allocating a number of tokens to a token bank based on a predetermined rate of sending network messages;

determining whether a message is waiting to be sent over the network;

determining the amount of tokens in said token bank;

sending said message, if said amount of tokens is greater than or equal to one;

wherein said token bank can store the amount of tokens as a value including a fractional component,

wherein said allocated number of tokens is a number with a fractional component, and

wherein said rate of sending network messages is expressed as the maximum number of messages to be sent in a particular time period.