Method for optimizing WAN traffic

• US 9,509,736 B2
• Filed: 01/16/2013
• Issued: 11/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,195
• Publication Number:
  US 20140201308A1
• Time in Patent Office: 1,413 Days
• Field of Search: 709/213
• US Class Current: 1/1
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 65/60 Network streaming of media packets
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics

Abstract

A local stream store of a local proxy caches one or more streams of data transmitted over the WAN to a remote proxy, where each stream is stored in a continuous manner and identified by a unique stream identifier (ID). In response to a flow of data received from a client, the local proxy examines the flow of data to determine whether at least a portion of the flow has been previously transmitted to the remote proxy via one of the streams currently stored in the local stream store. If the portion of the flow has been previously transmitted to the remote proxy, the local proxy transmits a first message to the remote proxy without sending actual content of the portion of the flow to indicate that the portion of the flow has been transmitted in one of the streams previously transmitted to the remote proxy.

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, wherein each of the one or more streams is stored in a continuous manner and identified by a respective unique stream identifier (ID);

comparing a flow of data received from a device with the one or more streams cached in the local stream store to determine whether at least a portion of the flow has been previously transmitted to the remote proxy via at least one of the one or more streams currently stored in the local stream store;

if the portion of the flow has been previously transmitted to the remote proxy, transmitting a first message to the remote proxy to indicate that the portion of the flow has been transmitted in at least one of the one or more streams previously transmitted to the remote proxy, wherein the first message includes a first stream ID identifying a first stream from the one or more streams previously transmitted to the remote proxy that is associated with the portion, an offset of the first stream from which the portion of the flow is located, and a length identifying a size of the portion of the flow, wherein the first message is transmitted to the remote proxy without a data content of the portion of the flow.

2. The method of claim 1, further comprising:

if the portion of the flow has not been previously transmitted to the remote proxy, transmitting a second message to the remote proxy representing a second stream identified by a second stream ID as a new stream, the second message containing the data content of the portion of the flow; and

storing the second stream identified by the second stream ID in the local stream store, the second stream containing the data content of the portion of the flow.

3. The method of claim 2, wherein comparing the flow of data comprises:

chunking, using a predetermined chunking algorithm, the flow of data into a plurality of chunks representing the flow of data in a continuous order; and

for each of the plurality of chunks, determining whether the chunk has been previously transmitted to the remote proxy via a previously transmitted stream;

recording the chunk as part of the first stream if the chunk has been previously transmitted to the remote proxy; and

otherwise recording the chunk as part of the second stream.

4. The method of claim 3, wherein determining whether the chunk has been previously transmitted to the remote proxy comprises:

hashing, using a predetermined hash function, content associated with the chunk to generate a fingerprint; and

performing a lookup in a chunk index based on the fingerprint to locate a chunk index entry that matches the fingerprint of the chunk, wherein the chunk is recorded as part of the first stream if a matched chunk index entry is found and wherein otherwise the chunk is recorded as part of the second stream.

5. The method of claim 4, wherein the chunk index comprises a plurality of chunk index entries, wherein each chunk index entry comprises:

a chunk ID represented by a respective fingerprint of a corresponding chunk;

a stream ID identifying a stream currently stored in the local stream store that contains the corresponding chunk; and

a stream offset identifying a location of the corresponding chunk within the stream that is identified by the stream ID of the chunk index entry.

6. The method of claim 4, wherein recording the chunk as part of the first stream if the matched chunk index entry is found comprises:

retrieving, from the local stream store, data based on information provided by the matched chunk index;

performing a byte-to-byte comparison between the retrieved data and the chunk to determine whether the chunk is duplicated data in a previously transmitted stream;

marking the chunk as part of the first stream only if all bytes between the chunk and the retrieved data are matched; and

otherwise marking the chunk as part of the second stream.

7. The method of claim 3, further comprising:

entering a duplicate data state if a first chunk of the chunks in sequence is a duplicated chunk that has been previously transmitted to the remote proxy;

during the duplicate data state, marking the first chunk as part of the first stream;

iteratively marking one or more subsequent bytes in the sequence as part of the first stream if the first subsequent chunks are duplicated bytes, without sending the first message to the remote proxy, until a byte in the sequence is found that has not been previously transmitted to the remote proxy;

transmitting the first message to the remote proxy identifying the first stream and a location in which the first chunk and the first subsequent bytes leading up to the non-matching byte are located.

8. The method of claim 7, further comprising:

entering a new data state once a non-matching byte has been identified;

during the new data state, iteratively marking one or more second subsequent chunks that continuously follow as new chunks in the second stream if the second subsequent chunks are new, until a third chunk in the sequence is found that is a duplicated chunk, upon which the second message containing the second chunk and the second subsequent chunks is sent to the remote proxy; and

entering the duplicate data state once the third chunk is found.

9. The method of claim 2, further comprising:

generating the second stream ID, wherein the second stream ID is unique amongst a plurality of stream IDs identifying a plurality of streams that have been sent to the remote proxy; and

prior to transmitting the second message, transmitting a third message containing the second stream ID to the remote proxy, wherein the third message indicates that subsequent data to be sent to the remote proxy within a same network connection session is associated with the second stream identified by the second stream ID.

10. 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 device, one or more streams of data transmitted over a wide area network to a remote device, wherein each of the one or more streams of data is stored in a continuous manner and identified by a unique stream identifier (ID);

examining the flow of data to determine whether at least a portion of a flow received from a device has been previously transmitted to the remote device, based on the one or more streams cached in the local device; and

if the portion of the flow has been previously transmitted to the remote device, transmitting a first message to the remote device without sending a content of the portion of the flow to indicate that the portion of the flow has been transmitted to the remote device, wherein the first message includes a first stream ID identifying a first stream that is a previously transmitted stream containing data of the portion of the flow, an offset of the first stream from which the portion of the flow is located, and a length identifying a size of the portion of the flow.

11. The medium of claim 10, storing additional instructions which, when executed by the processor, cause the processor to perform operations further comprising:

if the portion of the flow has not been previously transmitted to the remote device, transmitting a second message to the remote device representing a second stream identified by a second stream ID as a new stream, the second message containing the content of the portion of the flow; and

storing the second stream identified by the second stream ID in the local device, the second stream containing the content of the portion of the flow.

12. The medium of claim 11, wherein examining the flow of data to determine whether at least a portion of the flow has been transmitted previously to the remote device comprises:

chunking, using a predetermined chunking algorithm, the flow of data into a plurality of chunks representing the flow of data in a continuous order; and

for each of the plurality of chunks, determining whether a respective chunk has been previously transmitted to the remote device via a previously transmitted stream;

recording the chunk as part of the first stream if the chunk has been previously transmitted to the remote device; and

otherwise recording the chunk as part of the second stream.

13. The medium of claim 12, wherein determining whether the respective chunk has been previously transmitted to the remote device comprises:

hashing using a predetermined hash function content of the chunk to generate a fingerprint; and

performing a lookup in a chunk index based on the fingerprint to locate a chunk index entry that matches the fingerprint of the chunk, wherein the chunk is recorded as part of the first stream if a matched chunk index entry is found and wherein otherwise the chunk is recorded as part of the second stream.

14. The medium of claim 13, wherein the chunk index comprises a plurality of chunk index entries, wherein each chunk index entry comprises:

a chunk ID represented by a respective fingerprint of a corresponding chunk;

a stream ID identifying a stream currently stored in the local device that contains the corresponding chunk; and

a stream offset identifying a location of the corresponding chunk within the stream that is identified by the stream ID of the chunk index entry.

15. The medium of claim 13, wherein recording the chunk as part of the first stream if a matched chunk index entry is found comprises:

retrieving from the local device data based on information provided by the matched chunk index;

performing a byte-to-byte comparison between the retrieved data and the chunk to determine whether the chunk is duplicated data in a previously transmitted stream;

marking the chunk as part of the first stream only if all bytes between the chunk and the retrieved data are matched; and

otherwise marking the chunk as part of the second stream.

16. The medium of claim 12, storing additional instructions which, when executed by the processor, cause the processor to perform operations further comprising:

entering a duplicate data state if a first chunk of the chunks in sequence is a duplicated chunk that has been previously transmitted to the remote device;

during the duplicate data state, marking the first chunk as part of the first stream;

iteratively marking one or more subsequent bytes in the sequence as part of the first stream if first subsequent chunks are duplicated bytes, without sending the first message to the remote device, until a byte in the sequence is found that has not been previously transmitted to the remote device;

transmitting the first message to the remote device identifying the first stream and a location in which the first chunk and the first subsequent bytes leading up to the non-matching byte are located.

17. The medium of claim 16, storing additional instructions which, when executed by the processor, cause the processor to perform operations further comprising:

entering a new data state once a non-matching byte has been identified;

during the new data state, iteratively marking one or more second subsequent chunks that continuously follow as new chunks in the second stream if the second subsequent chunks are new, until a third chunk in the sequence is found that is a duplicated chunk, upon which the second message containing the second subsequent chunks is sent to the remote device; and

entering the duplicate data state once the third chunk is found.

18. The medium of claim 11, storing additional instructions which, when executed by the processor, cause the processor to perform operations further comprising:

generating the second stream ID that is unique amongst a plurality of stream IDs identifying a plurality of streams that have been sent to the remote device; and

prior to transmitting the second message, transmitting a third message containing the second stream ID to the remote device, wherein the third message indicates that subsequent data to be sent to the remote device within a same network connection session is associated with the second stream identified by the second stream ID.

19. A 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 the system, one or more streams of data transmitted over a network to a remote device, wherein each stream is stored in a continuous manner and identified by a unique stream identifier (ID);

in response to a flow of data received by the system, determining whether at least a portion of the flow has been previously transmitted to the remote device based on the one or more streams; and

if the portion of the flow has been previously transmitted to the remote device, transmitting a first message to the remote device without sending a content of the portion of the flow to indicate that the portion of the flow has been transmitted to the remote device, wherein the first message includes a first stream ID identifying a first stream that is a previously transmitted stream containing data of the portion of the flow, an offset of the first stream from which the portion of the flow is located, and a length identifying a size of the portion of the flow.

20. The system of claim 19, wherein the memory stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising:

if the portion of the flow has not been previously transmitted to the remote device, transmitting a second message to the remote device representing a second stream identified by a second stream ID as a new stream, the second message containing the content of the portion of the flow; and

storing the second stream identified by the second stream ID in the system, the second stream containing the content of the portion of the flow.

21. The system of claim 20, wherein determining that at least the portion of the flow has been transmitted previously to the remote device comprises:

chunking using a predetermined chunking algorithm the flow of data into a plurality of chunks representing the flow of data in a continuous order; and

for each of the plurality of chunks, determining whether a respective chunk has been previously transmitted to the remote device via a previously transmitted stream;

recording the respective chunk as part of the first stream if the respective chunk has been previously transmitted to the remote device; and

otherwise recording the respective chunk as part of the second stream.

22. The system of claim 21, wherein determining whether the respective chunk has been previously transmitted to the remote device comprises:

hashing using a predetermined hash function content of the respective chunk to generate a fingerprint; and

performing a lookup in a chunk index based on the fingerprint to locate a chunk index entry that matches the fingerprint of the respective chunk, wherein the respective chunk is recorded as part of the first stream if a matched chunk index entry is found and wherein otherwise the respective chunk is recorded as part of the second stream.

23. The system of claim 22, wherein the chunk index comprises a plurality of chunk index entries, wherein each chunk index entry comprises:

a chunk ID represented by a fingerprint of a corresponding chunk;

a stream ID identifying a stream currently stored in the system that contains the corresponding chunk; and

a stream offset identifying a location of the corresponding chunk within the stream that is identified by the stream ID of the chunk index entry.

24. The system of claim 22, wherein recording the chunk as part of the first stream if a matched chunk index entry is found comprises:

retrieving, from the system, data based on information provided by the matched chunk index;

performing a byte-to-byte comparison between the retrieved data and the respective chunk to determine whether the respective chunk is duplicated data in a previously transmitted stream;

marking the respective chunk as part of the first stream if all bytes between the respective chunk and the retrieved data are matched; and

otherwise marking the chunk as part of the second stream.

25. The system of claim 21, wherein the memory stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising:

entering a duplicate data state if a first chunk of the plurality of chunks in sequence is a duplicated chunk that has been previously transmitted to the remote device;

during the duplicate data state, marking the first chunk as part of the first stream;

iteratively marking one or more subsequent bytes in the sequence as part of the first stream if first subsequent chunks are duplicated bytes, without sending the first message to the remote device, until a byte in the sequence is found that has not been previously transmitted to the remote device;

transmitting the first message to the remote device identifying the first stream and a location in which the first chunk and the first subsequent bytes leading up to the non-matching byte are located.

26. The system of claim 25, wherein the memory stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising:

entering a new data state once a non-matching byte has been identified;

during the new data state, iteratively marking one or more second subsequent chunks that continuously follow as new chunks in the second stream if the second subsequent chunks are new, until a third chunk in the sequence is found that is a duplicated chunk, upon which the second message containing the second subsequent chunks is sent to the remote device; and

entering the duplicate data state once the third chunk is found.

27. The system of claim 20, wherein the memory stores additional instructions which, when executed by the processor, cause the processor to perform operations comprising:

generate the second stream ID that is unique amongst a plurality of stream IDs identifying a plurality of streams that have been sent to the remote device; and

prior to transmitting the second message, transmit a third message containing the second stream ID to the remote device, wherein the third message indicates that subsequent data to be sent to the remote device within a same network connection session is associated with the second stream identified by the second stream ID.