WAN optimization using probabilistic data filters

1. A method for WAN (wide area network) optimization for a WAN that connects a first site that sends a data stream to a second site, the method comprising:

at the first site:

receiving a probabilistic data filter that the second site creates based on segments of the data stream that the first site sends to the second site; and

for each particular segment in another set of segments that the first site has to send to the second site in the data stream:

examining the probabilistic data filter to determine whether the second site has already received the particular segment; and

replacing the particular segment with a segment identifier corresponding to the particular segment for forwarding to the second site when the examination of the probabilistic filter determines that the second site has already received the particular segment.

2. The method of claim 1 further comprising:

determining, based on the examination of the probabilistic data filter, that the second site has not yet received at least one particular segment; and

sending the at least one particular segment in full to the second site.

3. The method of claim 1 further comprising:

receiving, from the second site, a request for a particular segment in full after a segment identifier corresponding to the particular segment has been sent from the first site to the second site; and

sending the particular segment in full to the destination in response to the request.

4. The method of claim 1 further comprising periodically receiving updated versions of the probabilistic data filter based on subsequent segments of the data stream that the first site sends to the second site.

5. The method of claim 4 , wherein:

the first site is one of a plurality of source sites connected by the WAN that send data streams to the second site; and

the updated versions of the probabilistic data filter are based on segments sent by the plurality of source sites to the second site.

6. The method of claim 1 , wherein the other set of segments that the first site has to send to the second site in the data stream comprise a particular file that the first site has to send to the second site.

7. The method of claim 1 , wherein the WAN connects a plurality of sites including the first and second sites.

8. The method of claim 7 , wherein:

the first site comprises a public cloud,

a source device of the data stream is located at a third site of the plurality of sites connected by the SD-WAN, and

the method is performed by a gateway router deployed to the public cloud first site for forwarding segments in the data stream from the third site to the second site.

9. The method of claim 8 , wherein the gateway router is configured to perform a set of WAN optimization operations on segments sent from the source device at the third site to the second site.

10. The method of claim 9 , wherein the set of WAN optimization operations comprises at least (1) a traffic redundancy elimination (TRE) operation to avoid sending redundant segments to the second site, and (11) a compression operation to reduce a size of each segment sent to the second site.

11. The method of claim 10 , wherein examining the probabilistic data filter to determine whether the second site has already received each particular segment is performed as part of the TRE operation.

12. The method of claim 10 , wherein:

the data stream comprises an encrypted data stream;

each particular segment that the first site has to send to the second site in the encrypted data stream comprises a particular encrypted segment; and

the gateway router performs the set of WAN optimization operations on the encrypted segments without decrypting the encrypted segments.

13. The method of claim 1 , wherein the method is performed by a source device of the data stream at the first site.

14. The method of claim 1 , wherein the data stream comprises an encrypted data stream and the segments comprise encrypted segments.

15. The method of claim 1 , wherein the second site stores segments sent by the first site to the second site in a segment cache at the second site.

16. The method of claim 15 , wherein:

the first site is one of a plurality of source sites connected by the WAN that send data streams to the second site; and

the second site stores segments sent by the plurality of source sites to the second site in the segment cache at the second site.

17. The method of claim 16 , wherein the probabilistic data filter that the second site creates is further based on segments sent from the plurality of source sites to the second site that are stored in the segment cache at the second site.

18. The method of claim 15 , wherein examining the probabilistic data filter to determine whether the second site has already received the particular segment comprises using the probabilistic data filter to determine whether the particular segment is already stored in the segment cache at the second site.

19. A non-transitory machine readable medium storing a program for execution by a set of processing units, the program for providing WAN (wide area network) optimization for a WAN that connects a first site that sends a data stream to a second site, the program comprising sets of instructions for:

at the first site:

receiving a probabilistic data filter that the second site creates based on segments of the data stream that the first site sends to the second site; and

for each particular segment in another set of segments that the first site has to send to the second site in the data stream:

examining the probabilistic data filter to determine whether the second site has already received the particular segment; and

replacing the particular segment with a segment identifier corresponding to the particular segment for forwarding to the second site when the examination of the probabilistic filter determines that the second site has already received the particular segment.