Method for optimizing WAN traffic with efficient indexing scheme

1. A computer-implemented method comprising:

caching, in a local stream store of a local proxy, one or more streams of data transmitted over a wide area network to a remote proxy;

chunking a flow of data received from a device into a plurality of chunks in a sequence; and

selectively indexing a portion of the plurality of chunks in a chunk index maintained by the local proxy based on locations of the plurality of chunks in the flow, wherein a first number of chunks located closer to a beginning of the flow and farther from an end of the flow is indexed at a higher frequency than a second number of chunks located farther from the beginning of the flow and closer to the end of the flow, and wherein the chunk index includes a plurality of chunk index entries referenced to the one or more streams stored in the local stream store, the portion of the plurality of chunks comprising less than all of the plurality of chunks.

2. The method of claim 1 , wherein selectively indexing the plurality of chunks comprises:

for a first chunk located in a first region of the flow, hashing using a predetermined hash function the first chunk to generate a first fingerprint for the first chunk;

examining the first fingerprint of the first chunk to determine whether at least a portion of the first fingerprint matches a first predetermined pattern that is associated with the first region; and

indexing the first chunk in the chunk index if at least a portion of the first fingerprint matches the first predetermined pattern.

3. The method of claim 1 , wherein a chunk is indexed if the chunk is located within first 1 kilobytes (KB) of the flow.

4. The method of claim 1 , wherein a chunk is indexed if the chunk is located within first 4 kilobytes (KB) of the flow and if a least significant bit of a fingerprint of the chunk equals to 0.

5. The method of claim 1 , wherein a chunk is indexed if the chunk is located within first 16 kilobytes (KB) of the flow and if two least significant bits of a fingerprint of the chunk equal 0.

6. The method of claim 1 , wherein a chunk is indexed if the chunk is located within first 64 kilobytes (KB) of the flow and if three least significant bits of a fingerprint of the chunk equal 0.

7. The method of claim 1 , wherein a chunk is indexed if the chunk is located within first 256 kilobytes (KB) of the flow and if four least significant bits of a fingerprint of the chunk equal 0.

8. The method of claim 1 , wherein a chunk is indexed if five least significant bits of a fingerprint of the chunk equal 0.

9. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations comprising:

caching, in a local stream store of a local proxy, one or more streams of data transmitted over a wide area network to a remote proxy;

in response to a flow of data received from a client, chunking using a predetermined chunk algorithm the flow into a plurality of chunks in sequence; and

selectively indexing a portion of the plurality of chunks in a chunk index maintained by the local proxy based on locations of the plurality of chunks in the flow, wherein first a number of chunks located closer to a beginning of the flow and farther from an end of the flow is indexed at a higher frequency than a second number of chunks located farther from the beginning of the flow and closer to the end of the flow, and wherein the chunk index includes a plurality of chunk index entries referenced to the one or more streams stored in the local stream store, the portion of the plurality of chunks comprising less than all of the plurality of chunks.

10. The medium of claim 9 , wherein selectively indexing the plurality of chunks comprises:

for a first chunk located in a first region of the flow, hashing using a predetermined hash function the first chunk to generate a first fingerprint for the first chunk;

examining the first fingerprint of the first chunk to determine whether at least a portion of the first fingerprint matches a first predetermined pattern that is associated with the first region; and

indexing the first chunk in the chunk index if at least a portion of the first fingerprint matches the first predetermined pattern.

11. The medium of claim 9 , wherein a chunk is indexed if the chunk is located within first 1 kilobytes (KB) of the flow.

12. The medium of claim 9 , wherein a chunk is indexed if the chunk is located within first 4 kilobytes (KB) of the flow and if a least significant bit of a fingerprint of the chunk equals to 0.

13. The medium of claim 9 , wherein a chunk is indexed if the chunk is located within first 16 kilobytes (KB) of the flow and if two least significant bits of a fingerprint of the chunk equal 0.

14. The medium of claim 9 , wherein a chunk is indexed if the chunk is located within first 64 kilobytes (KB) of the flow and if three least significant bits of a fingerprint of the chunk equal 0.

15. The medium of claim 9 , wherein a chunk is indexed if the chunk is located within first 256 kilobytes (KB) of the flow and if four least significant bits of a fingerprint of the chunk equal 0.

16. The medium of claim 9 , wherein a chunk is indexed if five least significant bits of a fingerprint of the chunk equal 0.

17. A data processing system, comprising:

a processor; and

a memory coupled to the processor storing instructions, which when executed by the processor, cause the processor to perform operations comprising:

caching, in a local stream store of a local proxy represented by the data processing system, one or more streams of data transmitted over a wide area network (WAN) to a remote proxy,

chunking a flow of data received from a device into a plurality of chunks in sequence, and

selectively indexing a portion of the plurality of chunks in a chunk index maintained by the local proxy based on locations of the plurality of chunks in the flow, wherein a first number of chunks located closer to a beginning of the flow and farther from an end of the flow is indexed at a higher frequency than a second number of chunks located farther from the beginning of the flow and closer to the end of the flow, and wherein the chunk index includes a plurality of chunk index entries referenced to the one or more streams stored in the local stream store, the portion of the plurality of chunks comprising less than all of the plurality of chunks.

18. The system of claim 17 , wherein selectively indexing the plurality of chunks comprises:

for a first chunk located in a first region of the flow, hashing using a predetermined hash function the first chunk to generate a first fingerprint for the first chunk;

examining the first fingerprint of the first chunk to determine whether at least a portion of the first fingerprint matches a first predetermined pattern that is associated with the first region; and

indexing the first chunk in the chunk index if at least a portion of the first fingerprint matches the first predetermined pattern.

19. The system of claim 17 , wherein a chunk is indexed if the chunk is located within first 1 kilobytes (KB) of the flow.

20. The system of claim 17 , wherein a chunk is indexed if the chunk is located within first 4 kilobytes (KB) of the flow and if a least significant bit of a fingerprint of the chunk equals to 0.

21. The system of claim 17 , wherein a chunk is indexed if the chunk is located within first 16 kilobytes (KB) of the flow and if two least significant bits of a fingerprint of the chunk equal 0.

22. The system of claim 17 , wherein a chunk is indexed if the chunk is located within first 64 kilobytes (KB) of the flow and if three least significant bits of a fingerprint of the chunk equal 0.

23. The system of claim 17 , wherein a chunk is indexed if the chunk is located within first 256 kilobytes (KB) of the flow and if four least significant bits of a fingerprint of the chunk equal 0.

24. The system of claim 17 , wherein a chunk is indexed if five least significant bits of a fingerprint of the chunk equal 0.