WAN optimization using probabilistic data filters

Patent metadata

Field	Value
Publication number	US-12267250-B2
Application number	US-202218076313-A
Country	US
Kind code	B2
Filing date	Dec 6, 2022
Priority date	Dec 6, 2022
Publication date	Apr 1, 2025
Grant date	Apr 1, 2025

Abstract

Some embodiments of the invention provide a method for WAN (wide area network) optimization for a WAN that connects multiple sites, each of which has at least one router. At a gateway router deployed to a public cloud, the method receives from at least two routers at least two sites, multiple data streams destined for a particular centralized datacenter. The method performs a WAN optimization operation to aggregate the multiple streams into one outbound stream that is WAN optimized for forwarding to the particular centralized datacenter. The method then forwards the WAN-optimized data stream to the particular centralized datacenter.

First claim

The invention claimed is:

1. A method for WAN (wide area network) optimization for a WAN that connects a plurality of sites, the method comprising:
at a particular gateway router that forwards data streams to and from a first site of the plurality of sites, generating a probabilistic data filter representing a set of segment identifiers stored in a segment cache at the first site;
performing a compression operation to reduce a size of the probabilistic data filter; and
sending the compressed probabilistic data filter to a set of source sites of the plurality of sites that send data streams to the first site;

wherein the method further comprises:
periodically updating the probabilistic data filter based on segments received at the first site from the set of source sites, wherein each new segment received at the first site is stored in the segment cache at the first site; and
sending the periodically updated probabilistic data filter to the set of source sites.

2. The method of claim 1 , wherein generating the probabilistic data filter further comprises iterating over each segment in a set of segments represented by the set of segment identifiers.

3. The method of claim 1 , wherein the probabilistic data filter is used at the set of source sites to determine whether segments to be sent from each source site of the set of source sites to the first site are already stored in the segment cache at the first site.

4. The method of claim 3 , wherein when a particular segment is determined to already be stored in the segment cache based on the probabilistic data filter, a particular segment identifier corresponding to the particular segment is sent to the first site in place of the particular segment.

5. The method of claim 4 , wherein upon receiving the particular segment identifier as part of a data stream sent by a particular site, the particular gateway router (i) performs a lookup in the segment cache at the first site to identify the corresponding particular segment, (ii) retrieves the particular segment from the segment cache, and (iii) replaces the particular segment identifier with the retrieved particular segment.

6. The method of claim 3 , wherein when a particular segment is determined to not be stored in the segment cache based on the probabilistic data filter, the particular segment is sent in full to the first site.

7. The method of claim 1 further comprising:
receiving from a particular source site of the set of source sites that send data streams to the first site (i) a set of segments and (ii) a set of segment identifiers;
determining that a particular segment identifier in the set of segment identifiers corresponds to a particular segment that is not stored in the segment cache at the first site; and
sending a request for the particular segment in full to the particular source site.

8. The method of claim 7 further comprising:
in response to the request for the particular segment in full, receiving the particular segment in full from the particular source site;
storing the particular segment in the segment cache at the first site; and
updating the probabilistic data filter to reflect the particular segment that is now stored in the segment cache at the first site.

9. The method of claim 1 further comprising:
receiving from a particular source site of the set of source sites that send data streams to the first site (i) a set of segments and (ii) a set of segment identifiers;
determining that a particular segment in the set of segments is already stored in the segment cache at the first site; and
discarding the particular segment without storing the particular segment in the segment cache at the first site.

10. The method of claim 9 , wherein the particular source site is a particular first source site, wherein before receiving the set of segments and set of segment identifiers from the particular first source site, the method further comprises receiving the particular segment from a particular second source site of the set of source sites and storing the particular segment to the segment cache at the first site.

11. The method of claim 1 further comprising:
receiving, from a particular source site of the set of source sites, a set of segment identifiers corresponding to a set of segments already stored in the segment cache at the first site; and
updating a last-seen timestamp for each segment in the set of segments already stored in the segment cache at the first site.

12. The method of claim 11 , wherein:
an expiration period is defined for each segment stored in the segment cache based on the last-seen time stamp for the segment, and
when the last-seen timestamp for the segment has not been updated within the defined expiration period, the segment is deleted from the segment cache.

13. The method of claim 12 further comprising:
periodically updating the probabilistic data filter based on segments deleted from the segment cache; and
sending the periodically updated probabilistic data filter to the set of source sites.

14. The method of claim 1 , wherein the particular gateway router is deployed to a public cloud to forward data streams to and from the first site.

15. A non-transitory machine readable medium storing a program for execution by a set of processing units, the program for a particular gateway router that forwards data streams to and from a first site of a plurality of sites to provide WAN (wide area network) optimization for a WAN that connects the plurality of sites, the program comprising sets of instructions for:
generating a probabilistic data filter representing a set of segment identifiers stored in a segment cache at the first site;
performing a compression operation to reduce a size of the probabilistic data filter; and
sending the compressed probabilistic data filter to a set of source sites of the plurality of sites that send data streams to the first site;
wherein the probabilistic data filter is used at the set of source sites to determine whether segments to be sent from each source site of the set of source sites to the first site are already stored in the segment cache at the first site.

16. The non-transitory machine readable medium of claim 15 , wherein the set of instructions for generating the probabilistic data filter further comprises a set of instructions for iterating over each segment in a set of segments represented by the set of segment identifiers.

17. The non-transitory machine readable medium of claim 15 , wherein:
when a particular segment is determined to already be stored in the segment cache based on the probabilistic data filter, a particular segment identifier corresponding to the particular segment is sent to the first site in place of the particular segment; and
upon receiving the particular segment identifier as part of a data stream sent by a particular site, the particular gateway router (i) performs a lookup in the segment cache at the first site to identify the corresponding particular segment, (ii) retrieves the particular segment from the segment cache, and (iii) replaces the particular segment identifier with the retrieved particular segment.

18. The non-transitory machine readable medium of claim 15 , wherein when a particular segment is determined to not be stored in the segment cache based on the probabilistic data filter, the particular segment is sent in full to the first site.

Assignees

• VMware LLC

Inventors

• Golikov Igor
• Bergman Aran
• Gal Lior
• Yanai Avishay
• Cidon Israel
• Markuze Alex
• Zohar Eyal

Classifications

• H04L47/32

  by discarding or delaying data units, e.g. packets or frames · CPC title

• H04L12/66

  Arrangements for connecting between networks having differing types of switching systems, e.g. gateways · CPC title

• H04L67/5651

  Reducing the amount or size of exchanged application data · CPC title

• H04L67/568

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title

• H04L67/34

  involving the movement of software or configuration parameters  (network booting or remote initial program loading [RIPL] G06F9/4416) · CPC title