METHOD FOR OPTIMIZING WAN TRAFFIC WITH EFFICIENT INDEXING SCHEME

• US 20140201384A1
• Filed: 01/16/2013
• Published: 07/17/2014
• 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
• Granted Patent: US 9,300,748 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• 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 steams stored in the stream store.

Claims

1. A computer-implemented method for optimizing traffic over a wide area network (WAN) between two nodes, the method comprising:

caching, in a local stream store of a local proxy, 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, chunking using a predetermined chunk algorithm the flow into a plurality of chunks in sequence; and

selectively indexing the plurality of chunks in a chunk index maintained by the local proxy based on locations of the chunks in the flow, wherein 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, and wherein the chunk index includes a plurality of chunk index entries referenced to the steams stored in the stream store.

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 determined 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 fingerprint of the chunk equals to 0 mod 2.

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 a fingerprint of the chunk equals to 0 mod 4.

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 a fingerprint of the chunk equals to 0 mod 8.

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 a fingerprint of the chunk equals to 0 mod 16.

8. The method of claim 1, wherein a chunk is indexed if a fingerprint of the chunk equals to 0 mod 32.

9. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform a method for optimizing traffic over a wide area network (WAN) between two nodes, the method comprising:

caching, in a local stream store of a local proxy, 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, chunking using a predetermined chunk algorithm the flow into a plurality of chunks in sequence; and

selectively indexing the plurality of chunks in a chunk index maintained by the local proxy based on locations of the chunks in the flow, wherein 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, and wherein the chunk index includes a plurality of chunk index entries referenced to the steams stored in the stream store.

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 determined 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 fingerprint of the chunk equals to 0 mod 2.

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 a fingerprint of the chunk equals to 0 mod 4.

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 a fingerprint of the chunk equals to 0 mod 8.

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 a fingerprint of the chunk equals to 0 mod 16.

16. The medium of claim 9, wherein a chunk is indexed if a fingerprint of the chunk equals to 0 mod 32.

17. A data processing system, comprising:

a processor; and

a memory coupled to the processor storing instructions, which when executed from the memory, cause the processor to

cache, 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,

in response to a flow of data received from one of the clients of the local LAN, chunk using a predetermined chunk algorithm the flow into a plurality of chunks in sequence, and

selectively index the plurality of chunks in a chunk index maintained by the local proxy based on locations of the chunks in the flow, wherein 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, and wherein the chunk index includes a plurality of chunk index entries referenced to the steams stored in the stream store.

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 determined 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 fingerprint of the chunk equals to 0 mod 2.

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 a fingerprint of the chunk equals to 0 mod 4.

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 a fingerprint of the chunk equals to 0 mod 8.

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 a fingerprint of the chunk equals to 0 mod 16.

24. The system of claim 17, wherein a chunk is indexed if a fingerprint of the chunk equals to 0 mod 32.