Modeling packet traffic using an inverse leaky bucket

• US 8,385,205 B2
• Filed: 09/20/2007
• Issued: 02/26/2013
• Est. Priority Date: 09/20/2007
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Inventors: Kenney, John Belden
• Primary Examiner(s): Rinehart, Mark
• Assistant Examiner(s): HOPKINS, MATTHEW A
• Application Number:
  US11/858,856
• Publication Number:
  US 20090080331A1
• Time in Patent Office: 1,986 Days
• Field of Search: 370/235.1
• US Class Current: 370/235.1
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 41/5061 characterised by the interaction between service providers and their network customers, e.g. customer relationship management
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 47/21 using leaky-bucket

Abstract

An apparatus, method, and computer program of modeling packet traffic in terms of Leaky Bucket parameters. The Leaky Bucket parameters are tested based on conformance of packet traffic. If a result of the testing is nonconformance of the packet traffic, one or more of the Leaky Bucket parameters is modified such that the packet traffic is conforming. The one or more modified Leaky Bucket parameters is stored in a computer-readable storage medium.

Claims

1. A method of determining Leaky Bucket parameters for modeling packet traffic, wherein the packet traffic includes a plurality of provided packets, the method comprising:

for at least one packet among the plurality of provided packets,

obtaining packet traffic information associated with the packet;

comparing the obtained packet traffic information with stored Leaky Bucket parameters;

determining, based on the comparing, whether the packet associated with the packet traffic information conforms to a Leaky Bucket defined by the stored Leaky Bucket parameters, including at least a tolerance parameter L;

if it is determined that the packet does not conform based on a value of the packet information being determined to be greater than the tolerance parameter L, modifying one or more of the Leaky Bucket parameters, without discarding the packet, to make the packet conform;

storing the one or more modified Leaky Bucket parameters in a non-transitory computer-readable storage medium;

consolidating packet information of consecutive packets of the packet traffic; and

updating the packet traffic information to include the consolidated packet information,

wherein

the Leaky Bucket parameters include the tolerance parameter L and a target packet inter-arrival interval,

the determining includes

determining, based on the obtained packet traffic information, whether the packet would be a conforming packet in the Leaky Bucket parameterized by the tolerance parameter L and the target packet inter-arrival interval, and

the modifying includes

generating, if the determining determines that the packet would not be a conforming packet, a new target packet inter-arrival interval for which the packet would be a conforming packet.

2. The method of claim 1, wherein

the packet traffic information includes packet set information of a set of one or more consecutive packets, the set including a beginning packet that is a most recent packet having an arrival state less than or equal to zero, and an ending packet that is a current packet, and

the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet.

3. The method of claim 2, wherein the generating comprises:

generating an estimated new target inter-arrival interval based on the packet set information;

updating arrival states of packets in the set based on the estimated new target inter-arrival interval;

determining a most recent packet having an updated arrival state less than or equal to zero;

outputting the estimated new target inter-arrival interval as the new target inter-arrival interval if the most recent packet having an updated arrival state less than or equal to zero is the beginning packet of the set; and

if the most recent packet having an updated arrival state less than or equal to zero is not the beginning packet of the set, redefining the set to begin with the most recent packet having an updated arrival state less than or equal to zero.

4. The method of claim 2, further comprising:

discarding packet information of one or more packets preceding the beginning packet of the set.

5. The method of claim 1, wherein the consolidating comprises:

comparing an arrival state of the provided packet with an arrival state of a prior packet that immediately precedes the provided packet, wherein the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet; and

consolidating the packet information of the prior packet with the packet information of a packet immediately preceding the prior packet, if an arrival state of the prior packet is greater than the arrival state of the provided packet.

6. The method of claim 1, wherein the consolidating comprises:

setting a consolidated arrival time equal to an arrival time of an earliest arriving packet of the consecutive packets; and

setting a consolidated packet length equal to a sum of packet lengths of the consecutive packets.

7. The method of claim 1, further comprising:

discarding non-consolidated packet information of the consecutive packets that were consolidated.

8. The method of claim 1, further comprising selecting a service level based on the stored one or more modified Leaky Bucket parameters.

9. An apparatus for determining Leaky Bucket parameters for modeling packet traffic, wherein the packet traffic includes a plurality of provided packets, the apparatus comprising:

an obtainer that obtains packet traffic information associated with at least one packet among the plurality of packet;

a comparer that compares the obtained packet traffic information with stored Leaky Bucket parameters, including at least a tolerance parameter L;

a determiner that, based on the comparison of the comparer, determines whether the packet associated with the packet traffic information conforms to a Leaky Bucket defined by the stored Leaky Bucket parameters;

a modifier that, if it is determined that the packet does not conform based on a value of the packet information being determined to be greater than the tolerance parameter L, modifies one or more of the Leaky Bucket parameters, without discarding the packet, to make the packet conform;

a storage unit that stores the one or more modified Leaky Bucket parameters; and

a packet consolidator that consolidates packet information of consecutive packets of the packet traffic, and updates the packet traffic information to include the consolidated packet information,

wherein

the Leaky Bucket parameters include a tolerance parameter L and a target packet inter-arrival interval,

the determiner determines, based on the obtained packet traffic information, whether the packet would be a conforming packet in the Leaky Bucket parameterized by the tolerance parameter L and the target packet inter-arrival interval, and

the modifier generates, if the determiner determines that the packet would not be a conforming packet, a new target packet inter-arrival interval for which the provided packet would be a conforming packet.

10. The apparatus of claim 9, wherein

the packet traffic information includes packet set information of a set of one or more consecutive packets, the set including a beginning packet that is a most recent packet having an arrival state less than or equal to zero, and an ending packet that is a current packet, and

the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet.

11. The apparatus of claim 10, wherein the modifier:

generates an estimated new target inter-arrival interval based on the packet set information;

updates arrival states of packets in the set based on the estimated new target inter-arrival interval;

determines a most recent packet having an updated arrival state less than or equal to zero;

outputs the estimated new target inter-arrival interval as the new target inter-arrival interval if the most recent packet having an updated arrival state less than or equal to zero is the beginning packet of the set; and

if the most recent packet having an updated arrival state less than or equal to zero is not the beginning packet of the set, redefines the set to begin with the most recent packet having an updated arrival state less than or equal to zero.

12. The apparatus of claim 9, wherein the consolidator:

compares an arrival state of the packet with an arrival state of a prior packet that immediately precedes the packet, wherein the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet; and

consolidates the packet information of the prior packet with the packet information of a packet immediately preceding the prior packet, if an arrival state of the prior packet is greater than the arrival state of the packet.

13. The apparatus of claim 9, wherein the consolidator:

sets a consolidated arrival time equal to an arrival time of an earliest arriving packet of the consecutive packets; and

sets a consolidated packet length equal to a sum of packet lengths of the consecutive packets.

14. The apparatus of claim 9, further comprising a selector that selects a service level based on the stored one or more modified Leaky Bucket parameters.

15. A non-transitory computer readable storage medium having computer-executable program instructions stored thereon, for determining Leaky Bucket parameters for modeling packet traffic, wherein the packet traffic includes a plurality of provided packets, the program instructions being executable by a computer to perform the method of

for each packet,

obtaining packet traffic information associated with the packet;

comparing the obtained packet traffic information with stored Leaky Bucket parameters;

determining, based on the comparing, whether the packet associated with the packet traffic information conforms to a Leaky Bucket defined by the stored Leaky Bucket parameters, including at least a tolerance parameter L;

if it is determined that the packet does not conform based on a value of the packet information being determined to be greater than the tolerance parameter L, modifying one or more of the Leaky Bucket parameters, without discarding the packet, to make the packet conform;

storing the one or more modified Leaky Bucket parameters in the non-transitory computer-readable storage medium;

consolidating packet information of consecutive packets of the packet traffic; and

updating the packet traffic information to include the consolidated packet information,

wherein

the Leaky Bucket parameters include tolerance parameter L and a target packet inter-arrival interval,

the determining includes

determining, based on the obtained packet traffic information, whether the packet would be a conforming packet in the Leaky Bucket parameterized by the tolerance parameter L and the target packet inter-arrival interval, and

the modifying includes

generating, if the determining determines that the packet would not be a conforming packet, a new target packet inter-arrival interval for which the packet would be a conforming packet.

16. The medium of claim 15, wherein

the packet traffic information includes packet set information of a set of one or more consecutive packets, the set including a beginning packet that is a most recent packet having an arrival state less than or equal to zero, and an ending packet that is a current packet, and

the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet.

17. The medium of claim 16, wherein the generating comprises:

generating an estimated new target inter-arrival interval based on the packet set information;

updating arrival states of packets in the set based on the estimated new target inter-arrival interval;

determining a most recent packet having an updated arrival state less than or equal to zero;

outputting the estimated new target inter-arrival interval as the new target inter-arrival interval if the most recent packet having an updated arrival state less than or equal to zero is the beginning packet of the set; and

redefining the set to begin with the most recent packet having an updated arrival state less than or equal to zero, if the most recent packet having an updated arrival state less than or equal to zero is not the beginning packet of the set.

18. The medium of claim 15, wherein the consolidating comprises:

comparing an arrival state of the packet with an arrival state of a prior packet that immediately precedes the packet, wherein the arrival state of a respective packet corresponds to a state of the Leaky Bucket at an arrival time of the respective packet; and

consolidating the packet information of the prior packet with the packet information of a packet immediately preceding the prior packet, if an arrival state of the prior packet is greater than the arrival state of the packet.

19. The medium of claim 15, wherein the consolidating comprises:

setting a consolidated arrival time equal to an arrival time of an earliest arriving packet of the consecutive packets; and

setting a consolidated packet length equal to a sum of packet lengths of the consecutive packets.

20. The medium of claim 15, wherein the method further comprises selecting a service level based on the stored one or more modified Leaky Bucket parameters.