System and method for utilizing a data reducing module for dictionary compression of encoded data

• US 10,033,837 B1
• Filed: 09/30/2013
• Issued: 07/24/2018
• Est. Priority Date: 09/29/2012
• Status: Active Grant

• Current Assignee: F5 Networks, Inc. (F5 Incorporated)
• Original Assignee: F5 Networks, Inc. (F5 Incorporated)
• Inventors: Amdahl, Saxon
• Primary Examiner(s): Zand, Davoud
• Application Number:
  US14/042,237
• Time in Patent Office: 1,758 Days
• Field of Search: 709201, 709202, 709203, 709217229, 709217, 709229, 726 1, 726 29
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A system, medium and method of performing dictionary compression is disclosed. A first data segment received at a receiver device (RD) from a transmiter device (TD) is selected A global bloom filter of the TD is queried to determine if the RD has a stored copy of a first plurality of content data bytes and corresponding first identifier and data length information for the first data segment. A first encoded data packet is prepared and sent which includes the first identifier and data length information without the first plurality of content data bytes. The RD utilizes the received first identifier and data length information to retrieve the first plurality of content data bytes associated with the first data segment from the RD'"'"'s data store and decodes the first data segment to include the first plurality of content data bytes.

Claims

1. A method for facilitating deduplication in mesh networks using dictionary compression of encoded data to improve bandwidth utilization and scalability, the method implemented by a network traffic management system comprising one or more transmitter devices (TDs), one or more receiver devices (RDs), one or more client devices, or one or more server devices and comprising:

selecting a first data segment in a received data stream having a universal first identifier and data length information and a corresponding first plurality of content data bytes;

querying a global probabilistic data structure to determine when an RD has a stored copy of the first plurality of content data bytes and the corresponding universal first identifier and data length information for the first data segment, and when the determining indicates that the RD has the stored copy of the universal first identifier and data length information and first plurality of content data bytes for the first data segment;

performing dictionary compression by preparing a first encoded data packet, wherein the first encoded data packet includes the universal first identifier and data length information without the first plurality of content data bytes for the data segment; and

sending the first encoded data packet over a network to the RD to facilitate retrieval of the first plurality of content data bytes associated with the first data segment from the RD'"'"'s data store and decoding of the first data segment to include the first plurality of content data bytes without requiring that the first plurality of content data bytes for the data segment be transmitted over the network.

2. The method of claim 1, further comprising:

querying a local probabilistic data structure to determine when a copy of the universal first identifier and data length information and first content data bytes for the first data segment is stored locally; and

storing the universal first identifier and data length information in one or more index components, storing the first content data bytes in a data store, and updating the local probabilistic data structure to reflect that a copy of the universal first identifier and data length information and the first content data bytes for the first data segment is locally stored, when the determining indicates that a copy of the universal first identifier and data length information and first content data bytes is not locally stored.

3. The method of claim 1, further comprising:

marking the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as locked, wherein the universal first identifier and data length information and the first plurality of content data bytes cannot be deleted when marked as locked;

receiving a confirmation communication from the RD for the first data segment;

updating the global probabilistic data structure to reflect that the RD has the universal first identifier and data length information and first plurality of content data bytes of the first data segment stored locally in the RD; and

marking the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as being unlocked, wherein the universal first identifier and data length information and the first plurality of content data bytes are able to be deleted when marked as unlocked.

4. The method of claim 1, further comprising:

receiving a resend request from the RD, wherein the resend request comprises an instruction to send the first plurality of content data bytes for the first data segment;

retrieving the first content data bytes from a data store utilizing the universal first identifier and data length information;

sending the universal first identifier and the first plurality of bytes to the RD, wherein the universal first identifier and the first plurality of bytes remain in a locked status.

5. The method of claim 1, further comprising:

selecting a second data segment in the data stream, the second data segment including a plurality of second content data bytes;

determining a partial match between the plurality of content data bytes of the second data segment and content data bytes of a stored segment following a stored version of the first content data bytes of the first data segment;

identifying one or more non-matching content data bytes between the second data segment and the first data segment; and

generating a universal second identifier corresponding to a universal third identifier of the stored segment following the stored version of the first content data bytes of the first data segment.

6. The method of claim 1, wherein the global probabilistic data structure comprises a bloom filter.

7. A non-transitory computer readable medium having stored thereon instructions for facilitating deduplication in mesh networks using dictionary compression of encoded data to improve bandwidth utilization and scalability comprising executable code, which when executed by at least one processor, causes the at least one processor to:

select a first data segment in a received data stream having a universal first identifier and data length information and a corresponding first plurality of content data bytes;

query a global probabilistic data structure to determine when a receiver device (RD) has a stored copy of the first plurality of content data bytes and the corresponding universal first identifier and data length information for the first data segment, and when the determining indicates that the RD has the stored copy of the universal first identifier and data length information and first plurality of content data bytes for the first data segment;

perform dictionary compression by preparing a first encoded data packet, wherein the first encoded data packet includes the universal first identifier and data length information without the first plurality of content data bytes for the data segment; and

send the first encoded data packet over a network to the RD to facilitate retrieval of the first plurality of content data bytes associated with the first data segment from the RD'"'"'s data store and decoding of the first data segment to include the first plurality of content data bytes without requiring that the first plurality of content data bytes for the data segment be transmitted over the network.

8. The non-transitory computer readable medium of claim 7, wherein the executable code, when executed by the at least one processor, further causes the processor to:

query a local probabilistic data structure to determine when a copy of the universal first identifier and data length information and first content data bytes for the first data segment is stored locally; and

store the universal first identifier and data length information in one or more index components, store the first content data bytes in a data store, and update the local probabilistic data structure to reflect that a copy of the universal first identifier and data length information and the first content data bytes for the first data segment is locally stored, when the determining indicates that a copy of the universal first identifier and data length information and first content data bytes is not locally stored.

9. The non-transitory computer readable medium of claim 7, wherein the executable code, when executed by the at least one processor, further causes the processor to:

mark the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as locked, wherein the universal first identifier and data length information and the first plurality of content data bytes cannot be deleted when marked as locked;

receive a confirmation communication from the RD for the first data segment;

update the global probabilistic data structure to reflect that the RD has the universal first identifier and data length information and first plurality of content data bytes of the first data segment stored locally in the RD; and

mark the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as being unlocked, wherein the universal first identifier and data length information and the first plurality of content data bytes are able to be deleted when marked as unlocked.

10. The non-transitory computer readable medium of claim 7, wherein the executable code, when executed by the at least one processor, further causes the processor to:

receive a resend request from the RD, wherein the resend request comprises an instruction to send the first plurality of content data bytes for the first data segment;

retrieve the first content data bytes from a data store utilizing the universal first identifier and data length information; and

send the universal first identifier and the first plurality of bytes to the RD, wherein the universal first identifier and the first plurality of bytes remain in a locked status.

11. The non-transitory computer readable medium of claim 7, wherein the executable code, when executed by the at least one processor, further causes the processor to:

select a second data segment in the data stream, the second data segment including a plurality of second content data bytes;

determine a partial match between the plurality of content data bytes of the second data segment and content data bytes of a stored segment following a stored version of the first content data bytes of the first data segment;

identify one or more non-matching content data bytes between the second data segment and the first data segment; and

generate a universal second identifier corresponding to a universal third identifier of the stored segment following the stored version of the first content data bytes of the first data segment.

12. The non-transitory computer readable medium of claim 7, wherein the global probabilistic data structure comprises a bloom filter.

13. A transmitter device (TD) comprising memory comprising programmed instructions stored thereon and one or more processors configured to be capable of executing the stored programmed instructions to:

select a first data segment in a received data stream having a universal first identifier and data length information and a corresponding first plurality of content data bytes;

query a global probabilistic data structure to determine when a receiver device (RD) has a stored copy of the first plurality of content data bytes and the corresponding universal first identifier and data length information for the first data segment, and when the determining indicates that the RD has the stored copy of the universal first identifier and data length information and first plurality of content data bytes for the first data segment;

perform dictionary compression by preparing a first encoded data packet, wherein the first encoded data packet includes the universal first identifier and data length information without the first plurality of content data bytes for the data segment; and

send the first encoded data packet over a network to the RD to facilitate retrieval of the first plurality of content data bytes associated with the first data segment from the RD'"'"'s data store and decoding of the first data segment to include the first plurality of content data bytes without requiring that the first plurality of content data bytes for the data segment be transmitted over the network.

14. The transmitter device (TD) of claim 13, wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

query a local probabilistic data structure to determine when a copy of the universal first identifier and data length information and first content data bytes for the first data segment is stored locally; and

store the universal first identifier and data length information in one or more index components, store the first content data bytes in a data store, and update the local probabilistic data structure to reflect that a copy of the universal first identifier and data length information and the first content data bytes for the first data segment is locally stored, when the determining indicates that a copy of the universal first identifier and data length information and first content data bytes is not locally stored.

15. The transmitter device (TD) of claim 13, wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

mark the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as locked, wherein the universal first identifier and data length information and the first plurality of content data bytes cannot be deleted when marked as locked;

receive a confirmation communication from the RD for the first data segment;

update the global probabilistic data structure to reflect that the RD has the universal first identifier and data length information and first plurality of content data bytes of the first data segment stored locally in the RD; and

mark the universal first identifier and data length information and the first plurality of content data bytes for the first data segment as being unlocked, wherein the universal first identifier and data length information and the first plurality of content data bytes are able to be deleted when marked as unlocked.

16. The transmitter device (TD) of claim 13, wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

receive a resend request from the RD, wherein the resend request comprises an instruction to send the first plurality of content data bytes for the first data segment;

retrieve the first content data bytes from a data store utilizing the universal first identifier and data length information; and

send the universal first identifier and the first plurality of bytes to the RD, wherein the universal first identifier and the first plurality of bytes remain in a locked status.

17. The transmitter device (TD) of claim 13, wherein the one or more processors are further configured to be capable of executing the programmed instructions stored in the memory to:

select a second data segment in the data stream, the second data segment including a plurality of second content data bytes;

determine a partial match between the plurality of content data bytes of the second data segment and content data bytes of a stored segment following a stored version of the first content data bytes of the first data segment;

identify one or more non-matching content data bytes between the second data segment and the first data segment; and

generate a universal second identifier corresponding to a universal third identifier of the stored segment following the stored version of the first content data bytes of the first data segment.

18. The transmitter device (TD) of claim 13, wherein the global probabilistic data structure comprises a bloom filter.

19. A network traffic management system comprising one or more transmitter devices (TDs), one or more receiver devices (RDs), one or more client devices, or one or more server devices, the system comprising memory comprising programmed instructions stored thereon and one or more processors configured to be capable of executing the stored programmed instructions to:

select a first data segment in a received data stream having a universal first identifier and data length information and a corresponding first plurality of content data bytes;

query a global probabilistic data structure to determine when an RD has a stored copy of the first plurality of content data bytes and the corresponding universal first identifier and data length information for the first data segment, and when the determining indicates that the RD has the stored copy of the universal first identifier and data length information and first plurality of content data bytes for the first data segment;

perform dictionary compression by preparing a first encoded data packet, wherein the first encoded data packet includes the universal first identifier and data length information without the first plurality of content data bytes for the data segment; and

send the first encoded data packet over a network to the RD to facilitate retrieval of the first plurality of content data bytes associated with the first data segment from the RD'"'"'s data store and decoding of the first data segment to include the first plurality of content data bytes without requiring that the first plurality of content data bytes for the data segment be transmitted over the network.

20. The network traffic management system of claim 19, wherein the global probabilistic data structure comprises a bloom filter.