Cache eviction

Patent metadata

Field	Value
Publication number	US-9380323-B2
Application number	US-201514850007-A
Country	US
Kind code	B2
Filing date	Sep 10, 2015
Priority date	May 25, 2011
Publication date	Jun 28, 2016
Grant date	Jun 28, 2016

Abstract

A method and apparatus for downloading content within a video-on-demand system is provided herein. During operation a Video Home Office (VHO) will cache a subset of the Video Service Office (VSO) content. When a user requests content that is not stored on the VHO, the VHO will request that content from another VHO or the VSO. In order to reduce the additional network load imposed during item forwarding while attempting to balance the total load on all the links interconnecting the VSO and VHOs, recorded traffic history metrics are used to predict their future or current traffic. A VHO or VSO is chosen for fetching the content that will result in the lowest predicted traffic on the interconnecting links.

First claim

What is claimed is:

1. A method comprising:
receiving, by a processing apparatus at a first server, a request for content from a client device;
determining that the content is not stored by the first server;
determining that there is not enough room to cache the content at the first server; and
selecting one or more items to evict from a cache at the first server to make room for the content, wherein the selection of the items minimizes a network penalty associated with the eviction of the items, wherein the network penalty is based on sizes of the content and the items, numbers of requests expected to be received for the content and the items, and fetch costs associated with retrieving the content and the items, wherein each of the fetch costs is based on a sum of link weights of links in a network path for fetching each of the content and the items, and wherein each of the link weights is based on traffic predicted on a link in the links of the network path.

2. The method of claim 1 further comprising:
determining that a second server has the content;
determining that a third server has the content;
determining that a second cost associated with retrieving the content from the second server is less than a third cost associated with retrieving the content from the third server, wherein the second cost is based on traffic which is predicted to occur over a most utilized link to the second server, and wherein the third cost is based on traffic which is predicted to occur over a most utilized link to the third server; and
in response to determining that the second cost is less than the third cost, requesting the content from the second server, wherein the first server, the second server, and the third server each maintain a different subset of content available from a master server.

3. The method of claim 2 wherein determining that the second server has the content comprises:
sending a first message to the second server, wherein the first message identifies the content; and
receiving a second message from the second server, wherein the second message indicates that the second server has the content.

4. The method of claim 2 wherein the second cost and the third cost are based on historical traffic data.

5. The method of claim 4 wherein the second cost and the third cost are further based on predicted traffic.

6. The method of claim 2 wherein the second cost and the third cost are based on predicted traffic for one or more specific time intervals during a day, and wherein the predicted traffic is based on an analysis of repetitive traffic patterns.

7. The method of claim 2 wherein the first server is a first video home office (VHO), the second server is a second VHO, and the third server is a third VHO, wherein the master server is a video service office (VSO), and wherein the client device is a set-top box (STB).

8. A non-transitory computer-readable memory comprising instructions that, when executed by a processing apparatus, cause the processing apparatus to perform operations comprising:
receiving, by the processing apparatus at a first server, a request for content from a client device;
determining that the content is not stored by the first server;
determining that there is not enough room to cache the content at the first server; and
selecting one or more items to evict from a cache at the first server to make room for the content, wherein the selection of the items minimizes a network penalty associated with the eviction of the items, wherein the network penalty is based on sizes of the content and the items, numbers of requests expected to be received for the content and the items, and fetch costs associated with retrieving the content and the items, wherein each of the fetch costs is based on a sum of link weights of links in a network path for fetching each of the content and the items, and wherein each of the link weights is based on traffic predicted on a link in the links of the network path.

9. The non-transitory computer-readable memory of claim 8 wherein the operations further comprise:
determining that a second server has the content;
determining that a third server has the content;
determining that a second cost associated with retrieving the content from the second server is less than a third cost associated with retrieving the content from the third server, wherein the second cost is based on traffic which is predicted to occur over a most utilized link to the second server, and wherein the third cost is based on traffic which is predicted to occur over a most utilized link to the third server; and
in response to determining that the second cost is less than the third cost, requesting the content from the second server, wherein the first server, the second server, and the third server each maintain a different subset of content available from a master server.

10. The non-transitory computer-readable memory of claim 9 wherein determining that the second server has the content comprises:
sending a first message to the second server, wherein the first message identifies the content; and
receiving a second message from the second server, wherein the second message indicates that the second server has the content.

11. The non-transitory computer-readable memory of claim 9 wherein the second cost and the third cost are based on historical traffic data.

12. The non-transitory computer-readable memory of claim 11 wherein the second cost and the third cost are further based on predicted traffic.

13. The non-transitory computer-readable memory of claim 9 wherein the second cost and the third cost are based on predicted traffic for one or more specific time intervals during a day, and wherein the predicted traffic is based on an analysis of repetitive traffic patterns.

14. The non-transitory computer-readable memory of claim 9 wherein the first server is a first video home office (VHO), the second server is a second VHO, and the third server is a third VHO, wherein the master server is a video service office (VSO), and wherein the client device is a set-top box (STB).

15. A system comprising:
a storage at a first server; and
a processing apparatus at the first server to:
receive a request for content from a client device;
determine that the content is not stored by the storage;
determine that there is not enough room to cache the content at the first server; and
select one or more items to evict from a cache at the first server to make room for the content, wherein the selection of the items minimizes a network penalty associated with the eviction of the items, wherein the network penalty is based on sizes of the content and the items, numbers of requests expected to be received for the content and the items, and fetch costs associated with retrieving the content and the items, wherein each of the fetch costs is based on a sum of link weights of links in a network path for fetching each of the content and the items, and wherein each of the link weights is based on traffic predicted on a link in the links of the network path.

16. The system of claim 15 wherein the processing apparatus is further to:
determine that a second server has the content;
determine that a third server has the content;
determine that a second cost associated with receipt of the content from the second server is less than a third cost associated with receipt of the content from the third server, wherein the second cost is based on traffic which is predicted to occur over a most utilized link to the second server, and wherein the third cost is based on traffic which is pred

Assignees

• Google Technology Holdings LLC

Inventors

• Carbunar Bogdan O
• Pearce Michael D
• Vasudevan Venugopal
• Rittle Loren J
• Needham Michael L

Classifications

• H04N21/23106

  involving caching operations (prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568) · CPC title

• H04N21/23113 Primary

  involving housekeeping operations for stored content, e.g. prioritizing content for deletion because of storage space restrictions (storage management, e.g. defragmentation G06F3/0604; snloading stored programs G06F9/445; housekeeping operations in file systems, e.g. deletion policies G06F16/10; buffering arrangements in a network node or in an end terminal in packet networks H04L49/90) · CPC title

• H04N21/2402

  Monitoring of the downstream path of the transmission network, e.g. bandwidth available (traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876) · CPC title

• H04N21/64738

  Monitoring network characteristics, e.g. bandwidth, congestion level (data switched network analysis H04L41/14; monitoring functioning in data switched networks H04L43/0817; flow control in packet networks H04L47/10) · CPC title

• H04N21/2225

  Local VOD servers · CPC title