Distributed cache—adaptive multicast architecture for bandwidth reduction

• US 8,000,259 B2
• Filed: 09/04/2009
• Issued: 08/16/2011
• Est. Priority Date: 09/04/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Mills, Raymond L., Hudson, Erwin C.
• Primary Examiner(s): Duong; Frank
• Application Number:
  US12/554,585
• Publication Number:
  US 20110058490A1
• Time in Patent Office: 711 Days
• Field of Search: 370/252, 3703955-39552, 370400-401, 370464-465, 370/468, 370/477
• US Class Current: 370/252
• CPC Class Codes: H04B 7/18523 Satellite systems for providing broadcast service to terrestrial stations, i.e. broadcast satellite service arrangements specially adapted for satellite broadcast receiving H04H40/90; picture transmission via satellite H04N1/00103; television transmission via satellite H04N7/20
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 47/806 Broadcast or multicast traffic
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Disclosed is a method and system for maximizing the use of available bandwidth on an ISP communication system between an Internet Service Provider (ISP) and remote locations where at least one of the remote locations has a remote cache. An embodiment may monitor downstream unicast traffic, estimate the downstream unicast bandwidth used by unicast replies to the remote locations, and determine a remaining multicast bandwidth available to send multicast messages to the remote caches. An embodiment may create a pool of the cacheable objects being sent to the remote locations from the downstream traffic. An embodiment may determine bandwidth savings for each object in the pool of cacheable objects that would be achieved by remotely caching each object and prioritize the pool of cacheable objects based on the determined bandwidth savings for each object. An embodiment may create a queue of objects to multicast to the remote caches based on the pool of cacheable objects and the remaining multicast bandwidth and then multicast the queue to the remote caches. The remote caches may intercept and reply to requests for objects held in the remote cache without accessing the ISP communication system, thus, saving bandwidth on the ISP communication system.

Claims

1. A computerized method for maximizing use of communication bandwidth on an ISP communication system connecting at least one remote location to an Internet Service Provider (ISP), said ISP communication system having a maximum total downstream bandwidth available to transmit objects downstream from said ISP to said at least one remote location, said at least one remote location having a remote cache, said computerized method comprising:

monitoring downstream unicast communication traffic on said ISP communication system;

determining an estimated downstream unicast reply bandwidth based on said monitored downstream unicast communication traffic, said estimated downstream unicast reply bandwidth being an estimated portion of said maximum total downstream bandwidth utilized to deliver unicast replies containing requested objects downstream from said ISP to said at least one remote location in response to requests for said requested objects transmitted upstream from said at least one remote location to said ISP;

placing said requested objects contained in said downstream unicast replies monitored in said downstream communication traffic into a pool of cacheable objects;

determining an available downstream multicast bandwidth based on said maximum total downstream bandwidth and said estimated downstream unicast reply bandwidth;

determining a bandwidth savings from remote caching for each requested object in said pool of cacheable objects as a function of a delivery cost/size of each requested object, a Time To Live (TTL)/expiry time of each requested object, and a frequency of request for each requested object;

prioritizing said requested objects in said pool of cacheable objects based on said determined bandwidth savings for each requested object in said pool of cacheable objects;

determining a sub-group of said requested objects in said pool of cacheable objects to place in a queue of multicast cacheable objects to multicast to said remote cache at said at least one remote location based on said prioritized pool of cacheable objects and said available downstream multicast bandwidth;

delivering objects in said queue of multicast cacheable objects to said remote cache at said at least one remote location via multicast transmissions downstream from said ISP to said remote location;

intercepting requests sent upstream from said at least one remote location for objects contained in said remote cache at said remote cache; and

responding to said intercepted requests by said remote cache at said at least one remote location with replies containing said requested objects contained in said remote cache such that upstream and downstream bandwidth on said ISP communication system is saved by excluding upstream requests for, and downstream replies containing, said requested objects contained in said remote cache.

2. The computerized method of claim 1 wherein said ISP communication system is a satellite based communication system.

3. The computerized method of claim 1 wherein said intercepting and responding of said remote cache at said at least one remote location reduces latency in communication transmissions observed at said at least one remote location in addition to reducing bandwidth.

4. The computerized method of claim 1 wherein said computerized method for maximizing use of communication bandwidth is performed during system operation on a real-time basis in order to adapt to changes in said downstream unicast communication traffic of said ISP communication system during system operation.

5. The computerized method of claim 1 wherein said determining of said bandwidth savings from remote caching for each requested object in said pool of cacheable objects is further a function of a number of remote caches connected to said ISP communication system, said number of remote caches indicating a number of remote locations with said remote cache connected to said ISP communication system.

6. The computerized method of claim 1 wherein said determining of said bandwidth savings from remote caching for each requested object in said pool of cacheable objects is further a function of said maximum total downstream bandwidth currently available to said ISP communication system.

7. The computerized method of claim 1 further comprising updating said maximum total downstream bandwidth available on a real-time basis to incorporate observed fluctuations in the maximum total downstream bandwidth currently available for said ISP communication system.

8. The computerized method of claim 1 wherein said placing of said requested objects monitored in said downstream unicast communication traffic into said pool of cacheable objects excludes objects designated as not being cacheable.

9. The computerized method of claim 1 wherein said placing of said requested objects monitored in said downstream unicast communication traffic into said pool of cacheable objects excludes objects with a Time To Live (TTL)/expiry time determined to be too short to deliver to said remote cache at said at least one remote location.

10. The computerized method of claim 1 wherein said placing of said requested objects monitored in said downstream unicast communication traffic into said pool of cacheable objects excludes objects originating from a domain forbidden to be cached.

11. The computerized method of claim 1 wherein said placing of said requested objects monitored in said downstream unicast communication traffic into said pool of cacheable objects excludes objects designated as undesirable by a content control filter actively monitoring said requested objects monitored in said downstream communication traffic.

12. The computerized method of claim 1 further comprising combining a predefined list of objects with said requested objects monitored in said downstream unicast communication traffic in said pool of cacheable objects.

13. The computerized method of claim 1 further comprising:

examining said Time To Live (TTL)/expiry time of each requested object in said queue of multicast cacheable objects to determine if said Time To Live (TTL)/expiry time of each requested object in said queue of multicast cacheable objects is indeterminate; and

overwriting/creating said Time To Live (TTL)/expiry time in a requested object contained in said queue of multicast cacheable objects with a pre-defined replacement expiry time if said Time To Live (TTL)/expiry time of said requested object contained in said queue of multicast cacheable objects is found to have no expiration, negative expiration, or some otherwise indeterminable expiration.

14. The computerized method of claim 1 wherein said ISP communication system connects to at least one additional remote location that does not have a remote cache.

15. The computerized method of claim 1 wherein said at least one remote location restricts storage of objects in said remote cache of said at least one remote location to objects requested by said at least one remote location and not other remote locations.

16. A distributed cache adaptive multicast system for maximizing use of communication bandwidth on an ISP communication system connecting at least one remote location to an Internet Service Provider (ISP), said ISP communication system having a maximum total downstream bandwidth available to transmit objects downstream from said ISP to said at least one remote location, said at least one remote location having a remote cache, said distributed cache adaptive multicast system comprising:

a listener subsystem that monitors downstream unicast communication traffic on said ISP communication system;

a downstream unicast reply bandwidth estimator subsystem that determines an estimated downstream unicast reply bandwidth based on said monitored downstream unicast communication traffic, said estimated downstream unicast reply bandwidth being an estimated portion of said maximum total downstream bandwidth utilized to deliver unicast replies containing requested objects downstream from said ISP to said at least one remote location in response to requests for said requested objects transmitted upstream from said at least one remote location to said ISP;

a pool of cacheable objects subsystem that places said requested objects contained in said downstream replies monitored by said listener subsystem into a pool of cacheable objects;

an available multicast estimator subsystem that determines an available downstream multicast bandwidth based on said maximum total downstream bandwidth and said estimated downstream unicast reply bandwidth;

a prioritizer subsystem that determines a bandwidth savings from remote caching for each requested object in said pool of cacheable objects as a function of a delivery cost/size of each requested object, a Time To Live (TTL)/expiry time of each requested object, and a frequency of request for each requested object, and that prioritizes said requested objects in said pool of cacheable objects based on said determined bandwidth savings for each requested object in said pool of cacheable objects;

a multicast queue subsystem that determines a sub-group of said requested objects in said pool of cacheable objects to place in a queue of multicast cacheable objects to multicast to said remote cache at said at least one remote location based on said prioritized pool of cacheable objects and said available downstream multicast bandwidth; and

a multicast delivery subsystem that delivers objects in said queue of multicast cacheable objects to said remote cache at said at least one remote location via multicast transmissions downstream from said ISP to said remote location in order to permit said at least one remote cache to intercept requests sent upstream from said at least one remote location for objects contained in said remote cache at said remote cache, and to respond to said intercepted requests by said remote cache at said at least one remote location with replies containing said requested objects contained in said remote cache such that upstream and downstream bandwidth on said ISP communication system is saved by excluding upstream requests for and downstream replies containing said requested objects contained in said remote cache.

17. The distributed cache adaptive multicast system of claim 16 wherein said ISP communication system is a satellite based communication system.

18. The distributed cache adaptive multicast system of claim 16 wherein said intercepting and responding of said remote cache at said at least one remote location reduces latency in communication transmissions observed at said at least one remote location in addition to reducing bandwidth.

19. The distributed cache adaptive multicast system of claim 16 wherein said distributed cache adaptive multicast system operates during normal ISP communication system operation on a real-time basis in order to adapt to changes in said downstream unicast communication traffic of said ISP communication system during system operation.

20. The distributed cache adaptive multicast system of claim 16 wherein said prioritizer subsystem further determines said bandwidth savings from remote caching for each requested object in said pool of cacheable objects as a function of a number of remote caches connected to said ISP communication system, said number of remote caches indicating a number of remote locations with said remote cache connected to said ISP communication system.

21. The distributed cache adaptive multicast system of claim 16 wherein said prioritizer subsystem further determines said bandwidth savings from remote caching for each requested object in said pool of cacheable objects as a function of said maximum total downstream bandwidth currently available to said ISP communication system.

22. The distributed cache adaptive multicast system of claim 16 further comprising a maximum total downstream bandwidth subsystem that updates said maximum total downstream bandwidth available on a real-time basis to incorporate observed fluctuations in the maximum total downstream bandwidth currently available for said ISP communication system.

23. The distributed cache adaptive multicast system of claim 16 wherein said pool of cacheable objects subsystem excludes objects designated as not being cacheable.

24. The distributed cache adaptive multicast system of claim 16 wherein said pool of cacheable objects subsystem excludes objects with a Time To Live (TTL)/expiry time determined to be too short to deliver to said remote cache at said at least one remote location.

25. The distributed cache adaptive multicast system of claim 16 wherein said pool of cacheable objects subsystem excludes objects originating from a domain forbidden to be cached.

26. The distributed cache adaptive multicast system of claim 16 wherein said pool of cacheable objects subsystem excludes objects designated as undesirable by a content control filter actively monitoring said requested objects monitored in said downstream communication traffic.

27. The distributed cache adaptive multicast system of claim 16 further comprising a predefined list subsystem that combines a predefined list of objects with said requested objects monitored in said downstream communication traffic in said pool of cacheable objects.

28. The distributed cache adaptive multicast system of claim 16 further comprising:

an expiry update subsystem that examines said Time To Live (TTL)/expiry time of each requested object in said queue of multicast cacheable objects to determine if said Time To Live (TTL)/expiry time of each requested object in said queue of multicast cacheable objects is indeterminate, and overwrites/creates said Time To Live (TTL)/expiry time in a requested object contained in said queue of multicast cacheable objects with a pre-defined replacement expiry time if said Time To Live (TTL)/expiry time of said requested object contained in said queue of multicast cacheable objects is found to have no expiration, negative expiration, or some otherwise indeterminable expiration.

29. The distributed cache adaptive multicast system of claim 16 wherein said ISP communication system connects to at least one additional remote location that does not have a remote cache.

30. The distributed cache adaptive multicast system of claim 16 wherein said at least one remote location restricts storage of objects in said remote cache of said at least one remote location to objects requested by said at least one remote location and not other remote locations.

31. A distributed cache adaptive multicast system for maximizing use of communication bandwidth on an ISP communication system connecting at least one remote location to an Internet Service Provider (ISP), said ISP communication system having a maximum total downstream bandwidth available to transmit objects downstream from said ISP to said at least one remote location, said at least one remote location having a remote cache, said distributed cache adaptive multicast system comprising:

means for monitoring downstream unicast communication traffic on said ISP communication system;

means for determining an estimated downstream unicast reply bandwidth based on said monitored downstream unicast communication traffic, said estimated downstream unicast reply bandwidth being an estimated portion of said maximum total downstream bandwidth utilized to deliver replies containing requested objects downstream from said ISP to said at least one remote location in response to requests for said requested objects transmitted upstream from said at least one remote location to said ISP;

means for placing said requested objects contained in said downstream unicast replies monitored in said downstream communication traffic into a pool of cacheable objects;

means for determining an available downstream multicast bandwidth based on said maximum total downstream bandwidth and said estimated downstream unicast reply bandwidth;

means for determining a bandwidth savings from remote caching for each requested object in said pool of cacheable objects as a function of a delivery cost/size of each requested object, a Time To Live (TTL)/expiry time of each requested object, and a frequency of request for each requested object;

means for prioritizing said requested objects in said pool of cacheable objects based on said determined bandwidth savings for each requested object in said pool of cacheable objects;

means for determining a sub-group of said requested objects in said pool of cacheable objects to place in a queue of multicast cacheable objects to multicast to said remote cache at said at least one remote location based on said prioritized pool of cacheable objects and said available downstream multicast bandwidth;

means for delivering objects in said queue of multicast cacheable objects to said remote cache at said at least one remote location via multicast transmissions downstream from said ISP to said remote location;

means for intercepting requests sent upstream from said at least one remote location for objects contained in said remote cache at said remote cache; and

means for responding to said intercepted requests by said remote cache at said at least one remote location with replies containing said requested objects contained in said remote cache such that upstream and downstream bandwidth on said ISP communication system is saved by excluding upstream requests for, and downstream replies containing, said requested objects contained in said remote cache.