Low profile approximative rate limiter

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.

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.

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.