Method for optimizing WAN traffic with efficient indexing scheme

• US 9,300,748 B2
• Filed: 01/16/2013
• Issued: 03/29/2016
• Est. Priority Date: 01/16/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Rhea, Sean Christopher
• Primary Examiner(s): Harrell, Robert B
• Application Number:
  US13/743,197
• Publication Number:
  US 20140201384A1
• Time in Patent Office: 1,168 Days
• Field of Search: 709/231
• US Class Current: 1/1
• CPC Class Codes: H04L 65/765 intermediate
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

According to one embodiment, a local proxy caches in a local stream store one or more streams of data transmitted over the WAN to a remote proxy. In response to a flow of data received from one of the clients of the local LAN, the local proxy chunks using a predetermined chunk algorithm the flow into chunks in sequence, and selectively indexes the chunks in a chunk index maintained by the local proxy based on locations of the chunks in the flow, where a number of chunks in a first region of the flow indexed is different than a number of chunks in a second region of the flow indexed. The chunk index includes multiple chunk index entries referenced to the streams stored in the stream store.

Claims

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.