Methods and computer program products for providing a compressed circular buffer for efficient storage of network performance data

1. A method for providing a circular buffer of values representing performance data that corresponds to a network application on a network device, the method comprising:

compressing a binary representation of a value using bit-oriented compression that is biased based on a frequency of occurrence of values and/or value ranges;

appending the compressed binary representation to a circular buffer;

decompressing a plurality of compressed binary representations appended to the circular buffer; and

generating an array containing a plurality of respective values corresponding to the plurality of decompressed binary representations,

wherein the compressing a binary representation and appending the compressed binary representation comprise operations performed using at least one computer processor.

2. A method for providing a circular buffer of values representing performance data that corresponds to a network application on a network device, the method comprising:

compressing a binary representation of a value using bit-oriented compression that is biased based on a frequency of occurrence of values and/or value ranges; and

appending the compressed binary representation to a circular buffer,

wherein the compressing a binary representation and appending the compressed binary representation comprise operations performed using at least one computer processor, and

wherein compressing the binary representation comprises:

compressing values and/or value ranges that occur at a first frequency with a first degree of compression; and

compressing values and/or value ranges that occur at a second frequency with a second degree of compression;

wherein the first frequency is greater than the second frequency and the first degree of compression is greater than the second degree of compression.

3. A method according to claim 1 , wherein the frequency of occurrence is positively correlated with a degree of compression.

4. A method according to claim 1 , wherein the bit-oriented compression includes a Huffman code, a Gray code, an Elias gamma code, a Golomb code, and/or a static Huffman code.

5. A method for providing a circular buffer of values representing performance data that corresponds to a network application on a network device, the method comprising:

compressing a binary representation of a value using bit-oriented compression that is biased based on a frequency of occurrence of values and/or value ranges; and

appending the compressed binary representation to a circular buffer; and

allocating a data store defining the circular buffer, the data store including:

an array of bytes;

a start index that is operable to point into the array of bytes at a most significant bit of an oldest compressed binary representation stored in the array of bytes;

an end index that is operable to point into the array of bytes at a most significant bit of a newest compressed binary representation stored in the array of bytes; and

a rolling sum field that is operable to store an accumulation value of values stored in the array of bytes,

wherein the compressing a binary representation and appending the compressed binary representation comprise operations performed using at least one computer processor.

6. A method according to claim 5 , further comprising initializing the array of bytes to store null values.

7. A method according to claim 5 , wherein appending the compressed binary representation to the circular buffer comprises:

adding an integral number that corresponds to a value of the compressed binary representation to the accumulation value stored in the rolling sum field;

incrementing the end index by a first quantity that corresponds to a size of the newest compressed binary representation pointed to by the end index;

subtracting an integral number that corresponds to a value of the oldest compressed binary representation pointed to by the start index from the accumulation value stored in the rolling sum field;

incrementing the start index by a second quantity that corresponds to a size of the oldest compressed binary representation pointed to by the start index; and

inserting the compressed binary representation into the array of bytes at the location pointed to by the incremented end index.

8. A method according to claim 7 , wherein incrementing the end index by the first quantity comprises:

determining that incrementing the end index by the first quantity exceeds a maximum bound of the array of bytes by a third quantity;

setting the end index to point to a minimum bound of the array of bytes; and

incrementing the end index by the third quantity, and

wherein incrementing the start index by the second quantity comprises:

determining that incrementing the start index by the second quantity exceeds a maximum bound of the ordered array by a fourth quantity;

setting the start index to point to a minimum bound of the array of bytes; and

incrementing the start index by the fourth quantity.

9. A method according to claim 7 , wherein inserting the compressed binary representation into the array of bytes at the location pointed to by the incremented end index comprises:

determining, prior to inserting the compressed binary representation, that a size of the compressed binary representation exceeds a size of available space in the array of bytes;

allocating a data store defining an expanded array of bytes having a size greater than a size of the array of bytes;

copying data from the array of bytes into the expanded array to create an available space in the expanded array having a size greater than the size of available space in the array of bytes;

setting the start index to point into the expanded array at a most significant bit of the oldest compressed binary representation that is stored in the expanded array;

setting the end index to point into the expanded array at a most significant bit of the newest compressed binary representation that is stored in the expanded array;

incrementing the end index by the first quantity; and

inserting the compressed binary representation into the expanded array at the location pointed to by the incremented end index.

10. A method according to claim 9 , wherein the expanded array of bytes has a size greater than the size of the array of bytes by a given constant amount.

11. A method according to claim 9 , wherein the expanded array of bytes has a size greater than the size of the array of bytes by an amount based on the size of the array of bytes and a count of values stored in the array of bytes.

12. A computer program product comprising a non-transitory computer readable storage medium having computer readable program code embodied therein, the computer readable program code configured to carry out the method of claim 1 .

13. A computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therein, the computer readable program code comprising:

computer readable program code configured to allocating a data store defining a circular buffer, the data store including:

an array of bytes;

a start index that is operable to point into the array of bytes at a most significant bit of an oldest compressed binary representation stored in the array of bytes;

an end index that is operable to point into the array of bytes at a most significant bit of a newest compressed binary representation stored in the array of bytes; and

a rolling sum field that is operable to store an accumulation value of values stored in the array of bytes;

computer readable program code configured to compress a binary representation of a value using bit-oriented compression that is biased based on a frequency of occurrence of values and/or value ranges;

computer readable program code configured to append the compressed binary representation to a circular buffer;

computer readable program code configured to decompress a plurality of compressed binary representations appended to the circular buffer; and

computer readable program code configured to generate an array containing a plurality of respective values corresponding to the plurality of decompressed binary representations,

wherein computer readable program code configured to append the compressed binary representation to the circular buffer comprises:

computer readable program code configured to add an integral number that corresponds to a value of the compressed binary representation to the accumulation value stored in the rolling sum field;

computer readable program code configured to increment the end index by a first quantity that corresponds to a size of the newest compressed binary representation pointed to by the end index;

computer readable program code configured to subtract an integral number that corresponds to a value of the oldest compressed binary representation pointed to by the start index from the accumulation value stored in the rolling sum field;

computer readable program code configured to increment the start index by a second quantity that corresponds to a size of the oldest compressed binary representation pointed to by the start index; and

computer readable program code configured to insert the compressed binary representation into the array of bytes at the location pointed to by the incremented end index.

14. A computer program product according to claim 13 , wherein computer readable program code configured to compress a binary representation comprises:

computer readable program code configured to compress values and/or ranges that occur at a first frequency with a first degree of compression; and

computer readable program code configured to compress values and/or ranges that occur at a second frequency with a second degree of compression;

wherein the first frequency is greater than the second frequency and the first degree of compression is greater than the second degree of compression.

15. A computer program product according to claim 13 , wherein the bit-oriented compression includes a Huffman code, a Gray code, an Elias gamma code, a Golomb code, and/or a static Huffman code.

16. A computer program product according to claim 13 , wherein computer readable program code configured to increment the end index by the first quantity comprises:

computer readable program code configured to determine that incrementing the end index by the first quantity exceeds a maximum bound of the array of bytes by a third quantity;

computer readable program code configured to set the end index to point to a minimum bound of the array of bytes; and

computer readable program code configured to increment the end index by the third quantity, and

wherein computer readable program code configured to increment the start index by the second quantity comprises:

computer readable program code configured to determine that incrementing the start index by the second quantity exceeds a maximum bound of the ordered array by a fourth quantity;

computer readable program code configured to set the start index to point to a minimum bound of the array of bytes; and

computer readable program code configured to increment the start index by the fourth quantity.

17. A computer program product according to claim 13 , wherein computer readable program code configured to insert the compressed binary representation into the array of bytes at the location pointed to by the incremented end index comprises:

computer readable program code configured to determine, prior to inserting the compressed binary representation, that a size of the compressed binary representation exceeds a size of available space in the array of bytes;

computer readable program code configured to allocate a data store defining an expanded array of bytes having a size greater than a size of the array of bytes;

computer readable program code configured to copy data from the array of bytes into the expanded array to create an available space in the expanded array having a size greater than the size of available space in the array of bytes;

computer readable program code configured to set the start index to point into the expanded array at a most significant bit of the oldest compressed binary representation that is stored in the expanded array;

computer readable program code configured to set the end index to point into the expanded array at a most significant bit of the newest compressed binary representation that is stored in the expanded array;

computer readable program code configured to increment the end index by the first quantity; and

computer readable program code configured to insert the compressed binary representation into the expanded array at the location pointed to by the incremented end index.

18. A computer program product according to claim 17 , wherein the expanded array of bytes has a size greater than the size of the array of bytes by a given constant amount.

19. A computer program product according to claim 17 , wherein the expanded array of bytes has a size greater than the size of the array of bytes by an amount based on the size of the array of bytes and a count of integral numbers stored in the array of bytes.