LOW PROFILE APPROXIMATIVE RATE LIMITER

• US 20160080278A1
• Filed: 09/11/2014
• Published: 03/17/2016
• Est. Priority Date: 09/11/2014
• Status: Abandoned Application

• Current Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation)
• Original Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation)
• Inventors: Raubic, Pawel S., Wu, Guangnian
• Application Number:
  US14/483,850
• Publication Number:
  US 20160080278A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

Various exemplary embodiments relate to a method for detecting that messages are incoming to a networked device above a target rate, the method including recording a timestamp for at least three representative samples of messages arriving at the networked device; calculating the duration of a focus group including one or more of the representative samples, wherein the target rate is a number r messages over a number m seconds and the focus group represents r/2 messages; and determining the duration of the focus group is less than m seconds.

Claims

1. A method for detecting that messages are incoming to a networked device above a target rate, the method comprising:

recording a timestamp for at least three representative samples of messages arriving at the networked device;

calculating the duration of a focus group comprising one or more of the representative samples, wherein the target rate is a number r messages over a number m seconds and the focus group represents r/2 messages; and

determining the duration of the focus group is less than m seconds.

2. The method of claim 1 wherein each representative sample of messages is the same size.

3. The method of claim 1, further comprising:

determining the target rate;

determining an accuracy; and

calculating a number of iterations i based on the accuracy.

4. The method of claim 3, further comprising calculating a partition size based on the accuracy and the target rate;

and

wherein a size of each of the representative sample of messages is the partition size.

5. The method of claim 4 wherein the partition size represents 1 message for every r/2ⁱ messages received by the device.

6. The method of claim 3 wherein the accuracy is 1−

(0.05)ⁱ wherein i is the number of iterations.

7. The method of claim 3, further comprising determining a buffer size, wherein the buffer size is 3/2*2ⁱ multiplied by the size of a timestamp in memory.

8. The method of claim 3, further comprising:

calculating the duration of a prior group comprising one or more of the representative samples, wherein the prior group represents r/2 messages received by the device immediately prior to the focus group; and

determining the duration of the focus group and the prior group is less than m seconds.

9. The method of claim 8, further comprising:

determining an adjusted target rate of a number r/2 messages over a number m′

seconds where m′

is m seconds minus the duration of the focus group;

determining a following group comprising one or more of the representative samples, wherein the following group the represents r/2 messages received by the device immediately after the focus group; and

dividing the prior group and the following group into four groups, a first group, a second group, a third group, and a fourth group, wherein each of the first and second groups represents r/4 messages comprising the r/2 messages comprising the prior group and each of the third and fourth groups represents r/4 messages comprising the r/2 messages comprising the prior group.

10. The method of claim 9, further comprising:

creating a first branch comprising the first group, the second group, and the third group; and

creating a second branch comprising the second group, the third group, and the fourth group.

11. The method of claim 10, further comprising:

creating a first branch comprising the first group, the second group, and the third group; and

creating a second branch comprising the second group, the third group, and the fourth group.

12. The method of claim 11, further comprising:

determining the duration of the second group is less than m′

;

determining the duration of the first group; and

determining the duration of the third group.

13. The method of claim 3, further comprising:

calculating the duration of a following group comprising one or more of the representative samples, wherein the following group represents r/2 messages received by the device immediately after the focus group; and

determining the duration of the focus group and the following group is less than m seconds.

14. The method of claim 13, further comprising determining if there are not enough representative samples to create a following group representing r/2 messages, delaying the step of determining the duration of the focus group and the following group until enough representative samples have been collected to create a following group representing r/2 messages.

15. The method of claim 3, further comprising determining if the focus group comprises more than one representative sample.

16. A method for detecting that messages are incoming to a networked device above a target rate, the method comprising:

determining the target rate of a number r messages over a number m seconds;

determining an accuracy;

calculating a number of iterations i based on the accuracy;

recording a timestamp for at least three representative samples of messages arriving at the networked device;

calculating the duration of a focus group comprising one or more of the representative samples, wherein the focus group represents r/2 messages; and

determining the duration of the focus group is less than m seconds;

calculating the duration of a prior group comprising one or more of the representative samples, wherein the prior group represents r/2 messages received by the device immediately prior to the focus group;

calculating the duration of a following group comprising one or more of the representative samples, wherein the following group the represents r/2 messages received by the device immediately after the focus group;

determining the duration of the focus group and at least one of the prior group and the following group is less than m;

determining an adjusted target rate of the number of messages in the focus group over a number of seconds m′

, wherein m′

is m minus the duration of the focus group;

dividing the prior group and the following group into four groups, a first group, a second group, a third group, and a fourth group, wherein each of the first and second groups represents r/4 messages comprising the r/2 messages comprising the prior group and each of the third and fourth groups represents r/4 messages comprising the r/2 messages comprising the prior group;

creating a first branch comprising the first group, the second group, and the third group; and

creating a second branch comprising the second group, the third group, and the fourth group.

17. The method of claim 16, further comprising:

determining if the focus group comprises more than one representative sample; and

until the focus group does not comprise more than one representative sample, or determining the duration of the focus group and each of the prior group and the following group is greater than or equal to the adjusted rate, repeating the steps of;

calculating the duration of a focus group,

determining the duration of the focus group,

calculating the duration of a prior group,

calculating the duration of a following group,

determining the duration of the focus group and at least one of the prior group and the following group,

determining an adjusted target rate,

dividing the prior group and the following group into four groups,

creating a first branch, and

creating a second branch.

18. A networked device, the device comprising:

a network interface; and

a processor in communication with the network interface, the processor being configured to;

receive, via the network interface, messages;

record a timestamp for at least three representative samples of messages;

calculate the duration of a focus group comprising one or more of the representative samples, wherein a target rate is a number r messages over a number m seconds and the focus group represents r/2 messages; and

determine the duration of the focus group is less than m seconds.

19. The device of claim 18, wherein the processor is further configured to:

determine the target rate;

determine an accuracy;

calculate a number of iterations i based on the accuracy;

calculate a partition size based on the accuracy and the target rate, wherein a size each of the representative sample of messages is the partition size, wherein the partition size represents 1 message for every r/2ⁱ messages received by the device;

calculate the duration of a prior group comprising one or more of the representative samples, wherein the prior group represents r/2 messages received by the device immediately prior to the focus group; and

determine the duration of the focus group and the prior group is less than m seconds.

20. A non-transitory machine-readable storage medium encoded with instructions for execution by a networked device for detecting that messages are incoming to the networked device above a target rate, the non-transitory machine-readable storage medium comprising:

instructions for recording a timestamp for at least three representative samples of messages arriving at the networked device;

instructions for calculating the duration of a focus group comprising one or more of the representative samples, wherein the target rate is a number r messages over a number m seconds and the focus group represents r/2 messages; and

instructions for determining the duration of the focus group is less than m seconds.