Decentralized caching system

• US 9,564,960 B2
• Filed: 01/28/2015
• Issued: 02/07/2017
• Est. Priority Date: 09/23/2011
• Status: Active Grant

• Current Assignee: Gilat Satellite Networks Limited
• Original Assignee: Gilat Satellite Networks Limited
• Inventors: Markovitz, Oren, Hecht, Yoseph, Argov, Nitay, Kanfi, Zohar
• Primary Examiner(s): CHOE, YONG J
• Application Number:
  US14/607,202
• Publication Number:
  US 20150139021A1
• Time in Patent Office: 741 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: H04B 7/18517 Transmission equipment in earth stations
• CPC Class Codes: H04B 7/18528 Satellite systems for providing two-way communications service to a network of fixed stations, i.e. fixed satellite service or very small aperture terminal [VSAT] system
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 47/11 Identifying congestion
• 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]
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

In a satellite communication system comprising at least a hub and a plurality of terminals, at least one terminal may include a cache for storing data objects. The cache may be based on a detachable memory device that may be inserted to or removed from the terminal at any given time, including after the terminal is deployed. Aspects are directed to preventing a prefetching of objects already stored in a cache of a remote terminal. In some embodiments, an efficient multicasting of content to terminals over an adaptive link may occur in a manner which may benefit terminals comprising a cache while not affecting or minimally affecting the performance of terminals that may not include a cache.

Claims

1. A method comprising:

receiving, at a hub of a satellite communication system, a request from a first satellite communication terminal;

determining, at the hub, that one or more responses corresponding to the request are associated with a multicast group;

selecting transmission characteristics for transmitting the one or more responses in a multicast transmission, wherein the selecting comprises;

calculating, using a cost function, a cost for selecting the transmission characteristics instead of threshold transmission characteristics that are determined in accordance with a reception capability of only the first satellite communication terminal, wherein the transmission characteristics are at least as robust as the threshold transmission characteristics; and

selecting the transmission characteristics instead of the threshold transmission characteristics if the cost is less than or equal to a cost threshold; and

transmitting the one or more responses in the multicast transmission using the transmission characteristics.

2. The method of claim 1, further comprising setting the cost threshold to zero such that the transmission characteristics are selected if there is no additional cost for selecting the transmission characteristics.

3. The method of claim 1, wherein the calculating the cost for selecting the transmission characteristics comprises:

determining a probability that one or more other satellite communication terminals, which require more robust transmission characteristics than the first satellite communication terminal, will request information included in the one or more responses;

determining a congestion level on a channel used for transmitting data from the hub to satellite communication terminals;

calculating a popularity cost associated with the one or more responses in accordance with the probability; and

calculating a congestion cost in accordance with the congestion level,

wherein the cost function is the following function;

the congestion cost+α

*the popularity cost, and

wherein α

is a weight parameter.

4. The method of claim 3, wherein the popularity cost is calculated using one or more of:

a number of expected requests for information included in the one or more responses if the multicast transmission is not received by any of the one or more other satellite communication terminals;

a ratio of a number of additional satellite communication terminals to receive the multicast transmission if the transmission characteristics are selected to a total number of satellite communication terminals listening on the channel;

a size in bits of the one or more responses;

or

an estimated time for transmitting the one or more responses over the channel.

5. The method of claim 3, wherein the congestion cost is calculated using one or more of:

a figure corresponding to a bandwidth to be consumed if the transmission characteristics are selected;

a figure corresponding to a bandwidth to be consumed if the threshold transmission characteristics are selected;

a figure corresponding to a current available bandwidth;

or

a figure corresponding to spare bandwidth to be reserved.

6. A hub of a satellite communication system, the hub comprising:

hub caching logic configured to;

receive a request from a first satellite communication terminal;

determine that one or more responses corresponding to the request are associated with a multicast group;

select transmission characteristics for transmitting the one or more responses in a multicast transmission, wherein selection of the transmission characteristics comprises;

calculating, using a cost function, a cost for selecting the transmission characteristics instead of threshold transmission characteristics that are determined in accordance with a reception capability of only the first satellite communication terminal wherein the transmission characteristics are at least as robust as the threshold transmission characteristics; and

selecting the transmission characteristics instead of the threshold transmission characteristics if the cost is less than or equal to a cost threshold; and

transmit the one or more responses in the multicast transmission using the transmission characteristics.

7. The hub of claim 6, wherein the hub caching logic is further configured to set the cost threshold to zero such that the transmission characteristics are selected if there is no additional cost associated with the selection.

8. The hub of claim 6, wherein the calculating the cost for selecting the transmission characteristics comprises:

determining a probability that one or more other satellite communication terminals, which require more robust transmission characteristics than the first satellite communication terminal, will request information included in the one or more responses;

determining a congestion level on a channel used for transmitting data from the hub to satellite communication terminals;

calculating a popularity cost associated with the one or more responses in accordance with the probability; and

calculating a congestion cost in accordance with the congestion level,

wherein the cost function is the following function;

the congestion cost+α

*the popularity cost, and

wherein α

is a weight parameter.

9. A method comprising:

receiving, at a hub of a satellite communication system, a request from a first satellite communication terminal;

determining, at the hub, that one or more responses corresponding to the request are associated with a multicast group, wherein the determining, at the hub, that the one or more responses corresponding to the request are associated with the multicast group comprises;

analyzing uniform resource locators (URLs) requested by the first satellite communication terminal and URLs requested by additional terminals;

forming multicast groups by grouping terminals that request similar URLs;

determining, for a particular multicast group among the multicast groups, one or more subgroups and associating each terminal, associated with the particular multicast group, with at least one of the one or more subgroups; and

associating the one or more responses with a particular subgroup;

selecting transmission characteristics for transmitting the one or more responses in a multicast transmission, wherein the transmission characteristics are at least as robust as threshold transmission characteristics required for the first satellite communication terminal to receive the multicast transmission; and

transmitting the one or more responses in the multicast transmission using the transmission characteristics.

10. The method of claim 9, wherein the determining, for the particular multicast group, the one or more subgroups and the associating each terminal, associated with the particular multicast group, with the at least one of the one or more subgroups comprises:

determining the one or more subgroups and associating each terminal with at least one of the one or more subgroups based on link condition information received from terminals associated with the particular multicast group.

11. The method of claim 9, wherein the transmitting the one or more responses in the multicast transmission using the transmission characteristics comprises transmitting the one or more responses towards the first satellite communication terminal and other terminals associated with the particular multicast group.

12. The method of claim 9, wherein the transmitting the one or more responses comprises transmitting one or more objects as native multicast objects, wherein each object includes one or more headers and wherein a terminal identifier corresponding to the first satellite communication terminal is placed either at a predefined offset from a media access control (MAC) address field or at a predefined offset from a beginning of a multicast frame of the multicast transmission.

13. A method comprising:

receiving, at a hub of a satellite communication system, a first request from a first satellite communication terminal;

sending, to a first content server, a second request corresponding to the first request received from the first satellite communication terminal;

analyzing, at the hub, the second request to determine at least one uniform resource locator (URL) included in the second request;

determining, at the hub, one or more additional URLs that are likely to be requested by the first satellite communication terminal or any other terminals of the satellite communication system;

generating one or more third requests for the one or more additional URLs;

sending the one or more third requests to one or more content servers;

receiving, at the hub, one or more communications from the first content server;

sending, to a multicast group classifier of the hub, one or more responses to the first request;

associating, at the multicast group classifier, the one or more responses with a specific multicast group;

selecting transmission characteristics for transmitting the one or more responses in a multicast transmission, wherein the transmission characteristics are at least as robust as threshold transmission characteristics required for the first satellite communication terminal to receive the multicast transmission; and

transmitting the one or more responses in the multicast transmission towards the first satellite communication terminal and other terminals associated with the specific multicast group.

14. The method of claim 13, further comprising:

analyzing a particular communication among the one or more communications received from the first content server;

determining that the particular communication comprises at least one object pointing to one or more additional objects, wherein the one or more additional objects are available during a same session in which the particular communication is received;

generating one or more fourth requests for the one or more additional objects; and

sending the one or more fourth requests for the one or more additional objects to the first content server.

15. The method of claim 13, further comprising:

generating, at the hub, a reference record upon receiving the first request from the first satellite communication terminal, wherein the reference record corresponds to a first URL included in the first request;

analyzing a particular object of a particular communication among the one or more communications received from the first content server upon receiving the particular object;

determining one or more additional objects to be pre-fetched in response to analyzing the particular object;

generating one or more fourth requests for the one or more additional objects;

sending the one or more fourth requests to the first content server;

upon receiving a response to the one or more fourth requests from the first content server, updating the reference record by recording an index for each object received in the response to the one or more fourth requests; and

sending, to the first satellite communication terminal, a copy of the reference record together with each object received in the response to the one or more fourth requests.

16. The method of claim 15, further comprising:

receiving, at the hub after the first request, a subsequent request for the first URL from the first satellite communication terminal, wherein the subsequent request comprises at least an index number and a last modification time associated with the first URL;

determining that the reference record corresponding to the first URL is stored at the hub;

determining, at the hub, whether the first URL has been modified since the last modification time indicated in the subsequent request; and

sending, from the hub to the first satellite communication terminal, a subset of objects associated with the first URL, upon determining that the first URL has not been modified since the last modification time indicated in the subsequent request.

17. The method of claim 15, further comprising:

receiving, at the hub, a subsequent request for the first URL from the first satellite communication terminal, wherein the subsequent request comprises at least an index number and a last modification time associated with the first URL;

determining that the reference record corresponding to the first URL is stored at the hub;

determining, at the hub, whether the first URL has been modified since the last modification time indicated in the subsequent request; and

upon determining that the first URL has been modified since the last modification time indicated in the subsequent request, retrieving at least one new object associated with the first URL from the first content server;

updating the reference record based on the at least one new object; and

after updating the reference record, sending the reference record to the first satellite communication terminal.

18. The method of claim 13, wherein the second request is different from the first request, and wherein the one or more responses are different from the one or more communications.