User device ad-hoc distributed caching of content

A device receives a user election of participation in a distributed cache service, and receives user selection of one or more devices, that are each associated with the user, to register with the distributed cache service as participant nodes. The device determines an amount of available storage offered to the cache service for each of the one or more participant nodes, and determines an available bandwidth of a respective network connection associated with each of the one or more participant nodes. The device admits selected devices of the one or more participant nodes into the distributed cache service based on the available storage and the available bandwidth, and interleaves storage of multiple chunks of content across a subset of the participant nodes admitted into the distributed cache service. The device enables client access to the multiple chunks of content interleaved across the subset of the participant nodes.

BACKGROUND

Content servers may deliver various types of content to endpoint client devices via a network. The content may include any type of digital content that may be sent from a content server across a network to a requesting client device. Each unit of digital content may include, for example, a segment of text, a defined set of graphics, a Uniform Resource Locator (URL), a script, a program, an application or other unit of software, a media file (e.g., a movie, television content, music, etc.), a document, or an interconnected sequence of files (e.g., Hypertext Transfer Protocol (HTTP) Live Streaming (HLS) media files).

A content delivery network (CDN) includes a large distributed system of content servers deployed in multiple data centers across the Internet. The CDN serves content, including different types of media, to end users with a high level of performance. The CDN serves, for example, web objects (text, graphics and/or scripts), downloadable objects (images, audio media, video media, software, and/or documents), applications, and live streaming media (e.g., HLS media). CDN nodes are typically deployed in multiple locations, often over multiple backbones. The benefits of a CDN include reduction of bandwidth costs, improving web page load times, and increasing the availability of content.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

High traffic web content servers must support content requests from, and content delivery to, numerous (e.g., hundreds of thousands or even millions) different client devices. In addition to adding more server hardware, web acceleration techniques are often employed to scale to meet high volumes of this content delivery. Web acceleration includes the speeding up of the transfer of content between web servers and client devices. Caching is one technique used for web acceleration, and involves the pre-fetching and caching of content at a location that is either local to a particular client device(s), or that is “closer” to a particular client device(s). The “closer” proximity of the cache location may relate to an amount of bandwidth of connections to and from the cache location, and/or to a latency associated with delivering content from the cache location to a particular client device(s), where the latency may further relate to a network “distance” (e.g., number of hops) between the cache location and the particular client device(s). Pre-fetching includes retrieving an item of content (e.g., video content) from a web content server in advance of content requests from client devices. Caching includes identifying an appropriate cache storage location at which to store the item of content, and temporarily storing the item content at the identified cache storage. When a client device(s) requests the item of content, the item of content can be retrieved from the cache storage location and provided to the client device(s) more efficiently than if the item of content was provided from the original web content server.

Exemplary embodiments described herein implement the caching of content at devices within a “user space,” where the user space includes user devices owned and/or operated by individual users. Such “user space” devices may include, but are not limited to, cellular telephones; laptop, desktop, palmtop or tablet computers; set-top boxes (STBs); wearable computer devices; media playing devices; game playing devices; digital camera devices; or personal digital assistants (PDAs). As described herein, a caching controller identifies a set of user devices, within the “user space,” for serving as “cache storage” for caching content (e.g., for particular content-consuming client devices), divides each of item of content into multiple chunks of content, and interleaves the multiple chunks of content across the set of user devices for cache storage at those user devices. User devices may, thus, be used, as described herein, for the ad-hoc distributed caching of content for eventual retrieval by content consuming end-point client devices.

FIG. 1depicts an exemplary network environment100in which participant nodes (e.g., user devices) are selectively used to cache portions of content. Network environment100may include content servers105-1through105-n(generically referred to as “content server105” or “content servers105”), a network110, a participant node caching controller115(referred to as “caching controller115”), multiple caching participant nodes120-1through120-x(generically referred to as “caching participant node120,” “caching participant nodes120,” “participant node120,” or “participant nodes120”), and multiple client devices125-1through125-q(generically referred to as “client devices125” or “client device125”).

Content servers105may each include one or more network devices that store items of content, and deliver the items of content via network110. The items of content may include items of audio only content (e.g., MP3, Windows Media Audio (WMA), etc.), items of video content (e.g., Audio Video Interleave (AVI) files, QuickTime files, Windows Media Video (WMV) files, MPEG-4 files, file segments for streaming media, etc.), web objects (e.g., text, graphics and/or scripts), documents, software, images, and/or other types of items of digital content.

Network110includes one or more networks of various types, including, for example, a wireless public land mobile network (PLMN) (e.g., a Code Division Multiple Access (CDMA) 2000 PLMN, a Global System for Mobile Communications (GSM) PLMN, a Long Term Evolution (LTE) PLMN and/or other types of PLMNs), a telecommunications network (e.g., Public Switched Telephone Networks (PSTNs)), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), an intranet, the Internet, or a cable network (e.g., an optical cable network). Network110may further include a content delivery network (CDN) that includes various network nodes for facilitating the delivery of content from content servers105to participant nodes120, from participant nodes120to client devices125, or from content servers105to client devices125. Network110enables content servers105, caching controller115, participant nodes120, and client devices125to communicate with one another, including delivering content from content servers105to participant nodes120, and delivering content from participant nodes120to client devices125.

Caching controller115includes one or more network devices that identify a set of participant nodes120for caching content, dividing the content into chunks, and interleaving the chunks of content across the set of participant nodes120for cache storage of the content. Caching controller115, in one embodiment, may admit particular participant nodes into the ad-hoc distributed cache service based on a user election or request to participate in the cache service. Caching the content at the participant nodes120enables caching controller115to speed up the transfer of content between content servers105and client devices125when content is requested at the client devices125. In addition to caching techniques, described herein, caching controller115may additionally use load balancing techniques for optimizing the flow of content between content servers105and participant nodes120.

Participant nodes120each includes an electronic device associated with a user (e.g., a temporary or permanent owner or user of a particular user device). Participant nodes120may each include any type of electronic device (e.g., a digital computing device) that has a capability to communicate via a wired or wireless connection with network110, and which also has a memory device that permits the storage of data. Participant nodes120may each include, for example, a cellular telephone (e.g., smart phone); a laptop, desktop, palmtop or tablet computer; a set-top box (STB); a wearable computer device (e.g., a wrist watch, glasses, etc.); a media playing device; a game playing device; a digital camera device; or a personal digital assistant (PDA). Each of participant nodes120-1through120-xmay include a respective cache application (app)130-1through130-x(generically referred to as “cache app130” or “cache apps130”). Cache app130includes, for example, a software entity that further includes functionality for caching chunks of content based on interactions with, and instructions from, caching controller115. Cache app120may additionally include functionality for partitioning memory storage at participant node120to create a first portion of memory storage available for normal usage by the participant node120, and a second portion of memory storage reserved for usage by the cache service for caching content.

Client devices125each include an electronic device that “consumes” content. Client devices125may, for example, execute one or more applications (e.g., video or audio playing applications) that consume content provided by content servers105. Client devices125may each include, for example, a cellular telephone (e.g., smart phone); a laptop, desktop, palmtop or tablet computer; a set-top box (STB); a wearable computer device (e.g., a wrist watch, glasses, etc.); a media playing device; a game playing device; a digital camera device; or a personal digital assistant (PDA). In some implementations, a particular electronic device may be both a participant node120that caches content, and a client device125that also consumes content.

The configuration of the components of network environment100depicted inFIG. 1is for illustrative purposes only, and other configurations may be implemented. Therefore, network environment100may include additional, fewer and/or different components, that may be configured differently, than depicted inFIG. 1.

FIG. 2Adepicts an example of the caching of chunks of content in participant node ad-hoc distributed cache storage200at multiple different participant nodes120(e.g., user devices) of the network environment100ofFIG. 1. In one embodiment, the ad-hoc distributed cache storage200may include, at least in part, ad-hoc distributed cache storage located at multiple different participant nodes (e.g., user devices). As shown in the example, caching controller115may obtain an item of content (e.g., from a content server105) and may perform content chunking210to divide the item of content into multiple content chunks. Caching controller115may then engage in interleaved chunk caching215to interleave the multiple content chunks across cache storages205-1through205-x, at multiple different participant nodes120-1through120-x, within participant node ad-hoc distributed cache storage200. The interleaved chunk caching215may additionally include applying techniques for error correction and/or redundancy such that if certain chunks stored at a particular user device are corrupted, lost, or cannot be retrieved (e.g., loss of connection) at least one backup version of those chunks may be stored elsewhere, such as a backup participant node120. In the exemplary implementation shown inFIG. 2A, participant nodes120may include STBs120-1,120-2and120-3, a tablet computer120-4, and a laptop computer120-x. As further shown, the content may be divided into content chunks1through x, and each chunk is then stored in a respective cache storage205. For example, caching controller115stores chunk1in cache storage205-1at STB120-1, stores chunk2in cache storage205-2at STB120-2, stores chunk3in cache storage205-3at STB120-3, etc. The participant nodes120selected for inclusion in participant node ad-hoc distributed cache storage200may be based on a number of factors, described in further detail below with respect toFIG. 9. For example, the participant nodes120selected for inclusion may include participant nodes120maintaining a certain network proximity to one or more particular content consuming client devices125(not shown inFIG. 2A).

FIG. 2Bdepicts an example of the retrieval of chunks of content from participant node ad-hoc distributed cache storage200for consumption at a client device125, subsequent to the interleaved chunk caching210depicted inFIG. 2A. As shown in the example, a client device125may send a content request220, via network110, to caching controller115. The content request220may identify a particular item of content for downloading by, and consumption at, client device125. Caching controller115may determine whether to grant permission to client device125to access the requested content. Caching controller115may use various techniques to determine whether to grant content access permission to client device125, as described in further detail below. Upon determining that it is permissible to grant access to the particular client device125for the particular requested content, caching controller115returns a chunk access permission225to client device125. Chunk access permission225may include, for example, a network address(es), a unique device ID(s), and storage locations (e.g., file paths, etc.) at which chunks of the requested content are interleaved in cache storages205within the participant node ad-hoc distributed cache storage200.

Client device125may, based on receipt of chunk access permission225, engage in chunk retrieval230to retrieve respective content chunks from each cache storage205. For example, in the example depicted inFIG. 2B, client device125may retrieve chunk1240-1from cache storage205-1of STB120-1, chunk2240-2from cache storage205-2of STB120-2, chunk3240-3from cache storage205-3of STB120-3, chunk4240-4from cache storage205-4of tablet120-4, and chunk x240-xfrom cache storage205-xof laptop120-x. Upon retrieval of the content chunks, client device125may order the chunks in proper sequence to produce content for consumption (e.g., for presentation to a user of client device125). For example, if the content chunks include chunks of video content, client device125may order the content chunks into the original temporal sequence for playback by a media player at client device125.

FIG. 2Cdepicts an example of the use of a mesh network(s)250for connecting participant nodes120among one another to establish dynamic paths for relaying, storing and retrieving content chunks via the mesh network(s)250. A “mesh network,” as referred to herein, includes a network topology in which mesh nodes may relay and store data for the cache service in the network, and may otherwise cooperate in the distribution and storage of data for the cache service in the network. A “mesh network” may organically organize itself in an ad-hoc fashion, where the mesh nodes include participant nodes120, and possibly other mesh nodes, that may be ephemeral components of the mesh network. As shown, mesh network(s)250may include multiple different sub-mesh networks255-1through255-m(generically referred to herein as “mesh networks255” or “mesh network255”), where each sub-mesh network250connects between at least two different participant nodes120, or between a first participant node120and a mesh relay node (not shown) that relays content chunks between the first participant node120and a second participant node120. Each of mesh networks225may include, for example, a local area network (LAN) over which content chunks are relayed from a first participant node120to a second participant node120. In one embodiment, each of the LANs may include a wireless LAN (WLAN), such as a Wireless Fidelity (Wi-Fi) network based on the IEEE 802.11 standards. A different service set identifier (SSID) may be attached to the header of packets sent over a particular WLAN, where the SSID uniquely names a WLAN and enables a connection to the basic service set (BSS) of the WLAN. The SSID differentiates one WLAN from another, so participant nodes120attempting to connect to a particular WLAN mesh network255must use a same SSID in their packet headers. As shown in the example mesh network topology ofFIG. 2C, participant node120-1connects to mesh network255-1,255-2, and255-m. Participant node120-2connects to mesh network255-1,255-2,255-3and255-m. Participant node120-3connects to mesh network255-2,255-3, and255-m.

FIG. 2Ddepicts examples of dynamic paths for storing and/or retrieving content chunks via mesh networks255, and/or for relaying content chunks between participant nodes120via the mesh networks255. As shown inFIG. 2D, participant node120-1may use a path260-1, via mesh network255-1, for storing content chunks at participant node120-2, for retrieving content chunks from participant node120-2, and for relaying content chunks, received from another participant node (not shown) to participant node120-2. As further shown, participant node120-3may use a path260-2, via mesh network255-2, for storing content chunks at participant node120-1, for retrieving content chunks from participant node120-1, and for relaying content chunks, received from another participant node (not shown) to participant node120-1.FIG. 2Dalso depicts that participant node120-2may use a path260-3, via mesh network255-3, for storing content chunks at participant node120-3, for retrieving content chunks from participant node120-3, and for relaying content chunks, received from another participant node (not shown) to participant node120-3.FIG. 2Dadditionally depicts that participant node120-1may use a path260-m, via mesh network255-m, for storing content chunks at participant node120-3, for retrieving content chunks from participant node120-3, and for relaying content chunks, received from another participant node (not shown) to participant node120-3. Paths260-1,260-2,260-3and260-mmay also be used to store, retrieve and/or relay content chunks in an opposite direction to that described above. Though point-to-point (P2P) paths are depicted inFIG. 2D, point-to-multipoint (PMP) paths may additionally, or alternatively, be used for storing and retrieving content chunks.

FIG. 2Edepicts an exemplary embodiment in which multiple different caching controllers115-1through115-ymay be used to control the caching of content chunks in ad-hoc distributed cache storage200. In this embodiment, particular participant nodes120of participant nodes120-1through120-xmay be assigned to certain ones of caching controllers115-1through115-y. The assignment of participant nodes120to caching controllers115may, for example, be negotiated among the caching controllers115based on criteria such as proximity, mesh network communication range, current loading on each of the caching controllers115, and/or stability (e.g., bandwidth, connectivity, etc.) associated with each of the caching controllers115. Other criteria not described herein may, however, be used by caching controllers115for negotiating the assignment of participant nodes120. The proximity criteria may be a geographic proximity where the geographic distance between each caching controller and each participant node120is used as a basis for assignment, or may be a network hop proximity where the number of hops across network110, between each caching controller115and each participant node120, is used as a basis for assignment. If participant nodes120are associated with different CDNs or with different data centers, then the different CDNs, or different data centers, along with their associated participant nodes120, may be assigned to particular caching controllers115based on, for example, negotiation among the caching controllers115.

FIG. 3is a diagram that depicts exemplary components of a device300. Content servers105, caching controller115, participant nodes120, and client devices120may each be configured the same as, or similar to, device300shown inFIG. 3. Device300may include a bus310, a processing unit320, a main memory330, a read only memory (ROM)340, a storage device350, an input device(s)360, an output device(s)370, and a communication interface(s)380. Bus310may include a path that permits communication among the components of device100. Bus310may include, for example, a wired electrical, optical, or wireless path among the components of device100.

Processing unit320may include one or more processors or microprocessors, or processing logic (i.e., hardware), which may execute instructions. Main memory330may include a random access memory (RAM) or another type of dynamic storage device that may store information and instructions for execution by processing unit320. ROM340may include a ROM device or another type of static storage device that may store static information and instructions for use by processing unit320. Storage device350may include a magnetic, flash memory, and/or optical recording medium. Main memory330, ROM340and storage device350may each be referred to herein as a “tangible and/or non-transitory computer-readable medium.”

Input device360may include one or more mechanisms that permit an operator to input information to device300, such as, for example, a keypad or a keyboard, a display with a touch sensitive panel, voice recognition and/or biometric mechanisms, etc. Output device370may include one or more mechanisms that output information to the operator, including a display, a speaker, etc. Input device360and output device370may, in some implementations, be implemented as a user interface (UI) that displays UI information and which receives user input via the UI. Communication interface(s)380may include one or more transceivers that enable device300to communicate with other devices and/or systems. For example, communication interface(s)380may include one or more wired or wireless transceivers for communicating via network110.

The configuration of components of device300shown inFIG. 3is for illustrative purposes. Other configurations may be implemented. Therefore, device300may include additional, fewer and/or different components, arranged in a different configuration, than depicted inFIG. 3.

FIG. 4is a diagram that depicts exemplary functional components of caching controller115. The functional components depicted inFIG. 4may be implemented in software or hardware, or in a combination of software and hardware. For example, if implemented in software, then the functionality of each of the components depicted inFIG. 4may be implemented as instructions stored in main memory330, ROM340, and/or storage device350for execution by processing unit320ofFIG. 3. Caching controller115may include a node state unit400, a permission manager410, a session manager420, a transfer manager430, a mesh controller440, and a cache storage manager450. The various functional components400-450of caching controller115may, in one embodiment, be implemented in a single network device. In other embodiments, the various functional components400-450of caching controller115may be implemented in a distributed fashion (e.g., in a cloud) across a system of network devices that includes multiple different network devices. For example, in the system of network devices a first network device of caching controller115may implement node state unit400, a second network device of caching controller115may implement mesh controller440, a third network device of caching controller115may implement cache storage manager450, etc.

Node state unit400determines a state of participant nodes120for purposes of the participant node ad-hoc distributed caching service. Node state unit400may, for example, perform the “health checks” of the exemplary process ofFIGS. 8A and 8B. Node state unit400may, for example, determine an amount of available storage at each participant node120registered with the cache service, and may determine the available bandwidth of one or more network connections associated with each participant node120registered with the cache service. Node state unit400may, for example, also determine the stability and/or volatility of each participant node120, registered with the cache service, with respect to each participant node120's continuous availability for use by the cache service.

Permission manager410grants, or denies, access permission to client devices125for obtaining access to content stored in participant node ad-hoc distributed cache storage200. Permission manager410may also include functionality for granting permission to content servers105to store content in cache storage205.

Session Manager420manages sessions related to requesting or accessing content by client devices125. Transfer manager430controls the transfer of data from content servers105to participant node ad-hoc distributed cache storage200, and from participant node ad-hoc distributed cache storage200to client devices125. Mesh Controller440keeps track of one or more mesh networks formed between particular participant nodes120, and one or more other network nodes, where the particular participant nodes120may act as relays for relaying content chunks for storage in cache storage at an endpoint network node (e.g., another participant node120only connected to the particular participant node120). For example, participant node120-1may connect via a wireless local area network (LAN) (e.g., a Wi-Fi network) to another participant node120-2, where participant node120-2has no other connection to network110. In this example, participant node120-2may act as a relay for relaying content chunks to, and from, cache storage205at the other participant node120-2connected to the same wireless LAN.

Cache storage manager450controls the storage of content, received from content servers105, in participant node ad-hoc distributed cache storage200. Cache storage manager450may also divide received content in chunks, for encrypting the chunks of content, and for interleaving the encrypted chunks across multiple different cache storages205of participant nodes120. Cache storage manager450may interact with mesh controller440when storing content chunks at a participant node120accessible via a mesh network.

The configuration of functional components of caching controller115shown inFIG. 4is for illustrative purposes. Other configurations may be implemented. Therefore, caching controller115may include additional, fewer and/or different functional components, than depicted inFIG. 4.

FIG. 5is a flow diagram that illustrates an exemplary overall process for implementing a participant node ad-hoc distributed cache service. The exemplary process ofFIG. 5may be implemented by caching controller115, possibly in conjunction with other nodes.

The exemplary process includes caching controller115admitting selected user devices into the participant node ad-hoc distributed cache service as participant nodes (block500). A set of user devices, to be used in the distributed ad-hoc cache service as participant nodes, may be created based on, for example, user election of participation in the cache service, and user selection of particular ones of the user's devices to register with the cache service. The set of user devices may further be created based on a determined amount of available storage, offered to the cache service, for each user device, based on a determined available bandwidth of a respective network connection associated with each user device, and/or based on a determined stability or volatility of each registered participant node as being available to the cache service. Details of block500ofFIG. 5(i.e., the admission of selected user devices into the distributed ad-hoc cache service as participant nodes), according to one exemplary embodiment, is described below with respect to the process ofFIGS. 6A and 6B. Caching controller115may also, once selected user devices have been admitted into the cache service as participant nodes, permit the user devices to be removed from participation in the cache service. For example, the user of the participant node120may change their mind about their devices' participation in the cache service, and may notify caching controller115that their devices have been removed from participation in the cache service.

Caching controller115may perform “health checks” on each participant node120(e.g., user device) admitted in the cache service to maintain each participant node120in the cache service or to remove each participant node120from the cache service (block510). The “health checks” may include, for example, determining a current amount of available storage at each participant node, determining a current bandwidth of a network connection(s) to each participant node, and/or determining a stability and/or volatility of each participant node with respect to being available to the cache service upon demand. Details of block510ofFIG. 5(i.e., the performance of “health checks” on each user device admitted into the cache service), according to one exemplary embodiment, is described below with respect toFIGS. 8A and 8B.

Caching controller115may interleave storage of chunks of content across selected devices of the participant nodes admitted into the cache service (block520). Caching controller115may identify content for caching, divide the content into chunks, encrypt the divided chunks, and send the encrypted chunks to selected devices of the set of participant nodes admitted into the cache service for interleaving across cache storage205at the selected devices. Details of the interleaving of chunks of content across cache storage of different participant nodes, according to one embodiment, is described below with respect toFIG. 9.

Caching controller115enables client device access to the chunks of content stored at the selected devices of the participant nodes (block530). In response to a content request from a client device125, caching controller115may authenticate the client device125, and may grant or deny content access to the requesting client device125based on the authentication. If content access is granted, caching controller115returns a chunk access permission message to the requesting client device125that includes, among other data, unique device IDs and/or network addresses associated with the participant nodes at which the content chunks are interleaved. The message may further include chunks names associated with each cached content chunk, a decryption key for decrypting the content chunks, and the storage locations of the content chunks in cache storage205at the participant nodes120. Details of the requesting of content, the provision of chunk access permission, and client retrieval of content chunks from cache storage205at participant nodes120, according to one embodiment, is described below with respect toFIG. 11.

Blocks500,510,520and530may be continuously, or periodically, repeated in the sequence shown inFIG. 5. Alternatively, one or more of blocks500,510,520and/or530may be executed in parallel with other of the blocks. For example, block510may be executed independently, and in parallel with, execution of the other blocks ofFIG. 5.

FIGS. 6A and 6Bare flow diagrams that illustrate an exemplary process for admitting selected participant nodes into the ad-hoc distributed cache service. The exemplary process ofFIGS. 6A and 6Bmay be implemented by caching controller115, possibly in conjunction with other nodes. The exemplary process ofFIGS. 6A and 6Brepresents one exemplary implementation of block500ofFIG. 5, and is described below with reference to the example ofFIG. 7.

The exemplary process includes caching controller115receiving a device user's election of participation in the participant node distributed ad-hoc cache service (block600). A user (e.g., owner, operator and/or administrator) of a participant node120(e.g., a user device) may, via a user interface of the participant node or via the user interface of another node/device, provide information to caching controller115that indicates that the user elects to participate in the ad-hoc distributed cache service. In one embodiment, the user may be a subscriber to content from a particular content server105, and participation in the ad-hoc distributed cache service may earn the user a discount on the user's subscription rate to the content from that content server105. Caching controller115receives user selection of the user's device(s)120to register with the cache service as participant nodes (block610). As a follow-up to electing to participate in the cache service, the user may elect one or more devices, from a group of devices owned, used and/or operated by the user. For example, the group of the user's devices may include one or more STBs residing at the user's home location, a cellular telephone, a smart phone, and/or a tablet computer owned by the user, and a desktop computer owned by the user, and the user may elect one or more devices from this group to participate in the cache service.

Caching controller115obtains a network address, and a unique device identifier (ID), of the registered participant node(s) (block620). The user of the registered participant node(s) may manually supply the network address and/or the unique device ID of the registered participant node(s). Alternatively, caching controller115may obtain the network address and/or the unique device ID from a node in network110that maintains a record of such information. For example, a server associated with a service provider that provides network service to the registered user device(s) may keep track of the network address(es) and/or unique device ID(s) of the registered user device(s), and caching controller115may obtain the network address(es) and/or the unique device ID(s) from the server. Caching controller115may additionally, or as an alternative to the network address, obtain a network location at which the registered participant node120attaches to network110. For example, if the registered participant node120attaches to a local area network (LAN), which in turn connects to network110via a server, router, or gateway, then caching controller115may obtain the network location (e.g., the network address) of the network attachment via the server, router, or gateway.

Caching controller115determines a current amount of available storage, offered to the cache service, of each registered participant node(s) (block630). In addition to receiving a user registration for particular devices/nodes, caching controller115may receive an indication from the user of how much storage of the participant nodes is being offered to the cache service by the user. Caching controller115may further receive an indication of how much of the storage of the devices/nodes, offered by the user, is currently available for use by the cache service. The storage offered to the cache service by the user may be selected by the user per device for each of the participant nodes, or may be selected globally for an entire group of participant nodes. For example, a user may have two devices being registered with the cache service, with device1having 100 Gigabytes (GB) of free storage space and device2having 10 GB of free storage space. The user may offer 10 GB of device1, and 1 GB of device2, for use by the cache service for caching content chunks. The user may offer any desired portion of available free storage space (i.e., any percentage) at a user device for use by the cache service. Using the network address(es) or unique device ID(s) obtained in block620, caching controller115may query each registered participant node to determine how much total free storage space is currently unused by the participant node(s).

Caching controller115determines the current available bandwidth of a respective network connection(s) associated with each registered participant node(s) (block640). Caching controller115may determine, for example, an overall upload speed (i.e., bandwidth) for sending data for storage at each registered participant node, and an overall download speed (i.e., bandwidth) for retrieving data from storage at each registered participant node. The determined overall upload and download speeds provides an indication to caching controller115of the available bandwidth(s) of one or more network connections between caching controller115and the participant node(s).

Caching controller115determines a stability and/or volatility of each registered participant node as being available to the ad-hoc distributed cache service (block650). Caching controller115may make a determination in regards to any issue that affects the stability and/or volatility of each participant node120being available for use by the cache service. The determined stability and/or volatility of each participant node120being available to the cache service may be, for example, based on an amount of time that each participant node120is turned on, power instability issues associated with each participant node (e.g., frequent power outages), the user of each participant node120frequently dropping, and re-joining the cache service, or frequent and significant reductions in bandwidth available for connecting to each participant node120. The determined stability of each participant node120being available to the cache service may further be based on predictive modeling that predicts a future availability of a participant node120based on a prior history of availability of the participant node120, such as when the prior history indicates a pattern of availability or non-availability of participant node120. For example, a prior history may indicate that a “user device1” (e.g., a STB) associated with a user is turned off every night from 11 pm to 6 am; a “user device2” (e.g., tablet computer) associated with the user is only turned on Friday-Sunday each week or every holiday, during work hours, or school hours; and a “user device3” (e.g., a smart phone) associated with the user leaves a certain geographic area during Monday-Friday work hours or enters a certain geographic area during weekend periods. Based on this prior history, predictions may be made regarding the availability of these user devices to the cache service during various days of the week, during particular days of a month, and/or during particular hours of each day. For example, a “calendar of availability” may be constructed for each participant node, based on a prior history that indicates a pattern (e.g., daily/hourly) of availability or non-availability to the cache service.

In one embodiment, the determined stability and/or volatility of each participant node120being available to the cache service may be formalized as an admission “score” or “ranking” that can be used as a mechanism to determine whether to admit (or deny) a participant node120into the cache service. Various algorithms may be used to generate the admission score or ranking based on, for example, the “calendar of availability” for each participant node120and/or based on other factors described above with respect to block650.

Caching controller115admits/denies selected participant node(s) into the ad-hoc distributed cache service based on the current available storage, the current available bandwidth and/or the determined stability/volatility of node availability (block660) as determined in blocks630,640and650. Caching controller115may analyze the amount of available storage, offered to the cache service, determined in block630for each participant node120, the available bandwidth of a network connection(s) to each participant node120determined in block640, and/or the stability or volatility of each participant node as being available to the cache service as determined in block650, and then admit or deny the registered participant node(s)120into the ad-hoc distributed cache service. The participant node(s)120selected for admission into the cache service may be added to a set of participant nodes120available for use in the cache service.

FIG. 7depicts one example of the admission/denial of participant nodes120-1through120-xinto the ad-hoc distributed cache service. As shown inFIG. 7, a group of nodes/devices120-1through120-zmay be selected by a particular user for participation in the cache service. As further shown inFIG. 7, participant node120-1may be determined to have an available storage offered to the cache service of 1 GB, and a determined available bandwidth of 1 Megabits per second (Mbps); participant node120-2may be determined to have an available storage offered to the cache service of 2 GB, and a determined available bandwidth of 100 Mbps; participant node120-3may be determined to have an available storage offered to the cache service of 500 Megabytes (MB), and a determined available bandwidth of 500 Kilobits per second (Kbps); participant node120-4may be determined to have an available storage offered to the cache service of 200 MB, and a determined available bandwidth of 100 Kbps; and participant node120-zmay be determined to have an available storage offered to the cache service of 3 GB, and a determined available bandwidth of 50 Mbps.

Caching controller115analyzes the current available storage, and the current available bandwidth, for each of the participant nodes120, and determines which of the devices has a sufficient available quantity of both storage and bandwidth. In one exemplary implementation, a pre-set threshold minimum value may be required for each of the available storage, and the available bandwidth. In other implementations, the threshold minimum for each of the available storage and the available bandwidth may vary based on the different devices registered for participation in the cache service and/or based on current network conditions. For example, if a high percentage of devices/nodes selected for participation in the cache service have a relatively high quantity of available storage offered to the cache service, then the threshold minimum value required of the available storage may be increased. Those participant nodes120determined to have a sufficient quantity of both available storage and available bandwidth may be admitted to a set of devices available for use in the cache service. Conversely, those participant nodes120determined to not have a sufficient quantity of either available storage or available bandwidth may be denied admission to the set of devices available for use in the cache service.

Returning to the example ofFIG. 7, an analysis of the current available storage, and the current available bandwidth, of each of the participant nodes120-1through120-zresults in a determination that, since participant nodes120-1,120-2and120-zeach have an available storage of at least 1 GB and an available bandwidth of at least 1 Mbps, that participant nodes120-1,120-2and120-zare admitted to the set of devices available for use in the cache service. Participant nodes120-3and120-4, with both having less than 1 GB of available bandwidth and less than 1 Mbps bandwidth, are denied admission to the set of devices available for use in the cache service. This minimum threshold of 1 GB available storage, and 1 Mbps of available bandwidth represents only one example. In other embodiments, different minimum thresholds for available storage and/or available bandwidth may be selected at caching controller115.

Caching controller115enables uploading of a distributed cache service application to admitted device(s) of the registered user device(s) (block670). Caching controller115uploads, either directly subsequent to execution of block660, or at some future time determined by the admitted participant node120, a cache app130to the participant node120. The cache app130may execute in the background of participant node120for, among other functions, managing the storage of, and retrieval of, content chunks in cache storage205at the participant node120.

FIGS. 8A and 8Bare flow diagrams that illustrate an exemplary process for performing “health checks” on each participant node120admitted into the ad-hoc distributed cache service. The exemplary process ofFIGS. 8A and 8Bmay be implemented by caching controller115, possibly in conjunction with other nodes. The exemplary process of8A and8B represents one exemplary implementation of block510ofFIG. 5. The exemplary process ofFIGS. 8A and 8Bmay be executed, continuously or periodically, for each device/node registered with the ad-hoc distributed cache service, and initially admitted in the set of devices/nodes available for use in the cache service, as described with respect to blocks630,640,650, and660ofFIGS. 6A and 6Babove.

The exemplary process includes caching controller115determining a current amount of available storage at participant node120(block800). For example, using the network address and/or unique device ID obtained in block620ofFIG. 6A, caching controller115may query the registered participant node120to determine how much total free storage space is currently unused by the participant node(s). Caching controller115may additionally compare this determined total free storage space with the amount of storage, offered by the user in block630ofFIG. 6A, to determine the amount of available storage space that is currently available for use at the participant node120by the cache service. As one example, if the total free storage space of a participant node120is determined by caching controller115to be 1 GB, and the user of the participant node120has offered 5 GB to the cache service, then caching controller115determines that 1 GB of the participant node120storage is currently available for use by the cache service. As another example, if the total free storage space of the participant node120is determined by caching controller115to be 5 GB, but the user of the participant node has only offered 1 GB to the cache service, then caching controller115determines that 1 GB of the participant node120is currently available for use by the cache service.

Caching controller115determines a current bandwidth of one or more network connections to the participant node120(block805). Since network conditions may be transient (e.g., due to current network traffic loads), caching controller115may determine an updated, current bandwidth associated with one or more network connections to the participant node120. For example, similar to block640ofFIG. 6A, caching controller115may determine an overall upload speed (i.e., bandwidth) for sending data for storage at each registered participant node, and an overall download speed (i.e., bandwidth) for retrieving data from storage at the participant node120. The determined overall upload and download speeds provide an indication to caching controller115of the available bandwidth(s) of one or more network connections traversing a path between caching controller115and the participant node120.

Caching controller115determines a stability and/or volatility of the participant node120as being available to the ad-hoc distributed cache service (block810). Caching controller115may make a determination in regards to any issue that affects the stability and/or volatility of the participant node120being available for use by the cache service. The determined stability and/or volatility of the participant node120being available to the cache service may be, for example, based on an amount of time that the participant node120is turned on, power instability issues associated with the node (e.g., frequent power outages), the user of the participant node120frequently dropping, and re-joining the cache service, or frequent and significant reductions in bandwidth available for connecting to the participant node120. The determined stability of each participant node120being available to the cache service may further be, similar to the description above with respect to block650, based on predictive modeling that predicts a future availability of a participant node120based on a prior history of availability of the participant node120, such as when the prior history indicates a pattern of availability or non-availability of participant node120. Based on this prior history, predictions may be made regarding the availability of these user devices to the cache service during various days of the week, during particular days of a month, and/or during particular hours of each day. For example, a “calendar of availability” may be constructed for each participant node, based on a prior history that indicates a pattern (e.g., daily/hourly) of availability or non-availability to the cache service.

In one embodiment, the determined stability and/or volatility of each participant node120being available to the cache service may be formalized as a retention “score” or “ranking” that can be used as a mechanism to determine whether to retain a participant node120as an active participant in the cache service, or whether to withdraw the participant node120, at least temporarily, from participation in the cache service. Various algorithms may be used to generate the retention score or ranking based on, for example, the “calendar of availability” for each participant node120and/or based on other factors described above with respect to block810.

Caching controller115determines whether to withdraw the participant node120from the cache service based on the determinations of blocks800,805and/or810(block815). Caching controller115may, for example, apply a threshold minimum to the amount of available storage determined in block800, and/or a threshold minimum to the amount of current bandwidth available for connecting to the participant node120in block805, to determine whether to remove the participant node120from the cache service. In one example, caching controller115may apply a minimum threshold of 500 MB as the minimum amount of storage of the participant node120available for use by the cache service, and a minimum threshold of 1 Mbps as the minimum available bandwidth for sending data to/from the participant node120. Other minimum threshold may be applied by caching controller115in block815.

Caching controller115may additionally, or alternatively, determine whether to remove the participant node120from the cache service based on whether the determined stability or volatility of the participant node120being available for use by the cache service is inadequate. Thus, if the participant node is not turned on a signification portion of the time, then caching controller115may determine that the participant node120's availability to the cache service is not sufficiently stable enough, and may remove the participant node120from the cache service. Additionally, if the participant node120has frequent power outages (e.g., failing battery, or unstable electrical power system), or if there are frequent and significant reductions in available bandwidth for connecting to the participant node120, then caching controller115may determine that the participant node120's availability to cache service is too volatile, and may remove the participant node120from the cache service.

If caching controller115makes a determination to not withdraw the participant node120from the cache service (NO—block815), then the exemplary process may return to block800, with a repeat of the performance of “health checks” for the participant node120. If caching controller115makes a determination to withdraw the participant node120from the cache service (YES—block815), then caching controller115removes the participant node120from the set of devices/nodes available for use in the cache service (block820). Content chunks currently stored at participant node120removed from the set of devices available for use in the cache service may be stored at an alternative participant node(s)120.

Caching controller115determines a current amount of available storage at participant node120(block825). Block825is performed similarly to block800, described above inFIG. 8A. Caching controller115determines a current bandwidth of a network connection to the participant node120(block830). Block830is performed similarly to block805, described above inFIG. 8A. Caching controller115determines a stability and/or volatility of the participant node120as being available to the ad-hoc distributed cache service (block835). Block835is performed similarly to block810, described above inFIG. 8A.

Caching controller115determines whether to re-admit the participant node120to cache service based on the determinations in blocks825,830and/or835(block840). Caching controller115may, for example, apply a threshold minimum to the amount of available storage determined in block825, and/or a threshold minimum to the amount of current bandwidth available for connecting to the participant node120in block830, to determine whether to remove the participant node120from the cache service. In one example, caching controller115may apply a minimum threshold of 750 MB as the minimum amount of storage of the participant node120available for use by the cache service, and a minimum threshold of 500 Mbps as the minimum available bandwidth for sending data to/from the participant node120. Other minimum thresholds may be applied by caching controller115in block840. Caching controller115may additionally, or alternatively, determine whether to re-admit the participant node120to the cache service based on whether the determined stability or volatility of the participant node120being available for use by the cache service has again become adequate. Thus, if the participant node120is once again turned on a signification portion of the time (e.g., 23.5 hours out of a 24 hour day), then caching controller115may determine that the participant node120's availability to the cache service is sufficiently stable enough, and may re-admit the participant node120to the cache service. Additionally, if the participant node120now has infrequent power outages, or if there are no frequent and significant reductions in available bandwidth for connecting to the participant node120, then caching controller115may determine that the participant node120's availability to cache service is not volatile, and may re-admit the participant node120to the cache service.

If caching controller115makes a determination to not re-admit the participant node120to the cache service (NO—block840), then the exemplary process may return to block825, with a repeat of the performance of “health checks” for the participant node120. If caching controller115makes a determination to re-admit the participant node120to the cache service (YES—block840), then caching controller115adds the participant node120to the set of devices available for use in the cache service (block845). The exemplary process may then return to block800ofFIG. 8A, with a continued performance of “health checks” for the participant node120.

FIG. 9is a flow diagram that illustrates an exemplary process for interleaving chunks of content across selected devices of participant nodes120admitted into the ad-hoc distributed cache service. The exemplary process ofFIG. 9may be implemented by caching controller115, possibly in conjunction with other nodes. The exemplary process ofFIG. 9represents one exemplary implementation of block520ofFIG. 5. The exemplary process ofFIG. 9may be executed for each item of content to be cached using the caching service described herein. The exemplary process ofFIG. 9is described below with reference toFIG. 10.

The exemplary process includes caching controller115identifying content for caching using the ad-hoc distributed caching service (block900), and dividing the content into chunks and identifying a chunk name for each chunk of the content (block910). Caching controller115may, in one implementation, divide the content into a number of chunks determined by a number of the participant nodes120currently having cache storage205available for use in the cache service. In another implementation, caching controller115may determine an amount of available storage at a certain number of participant nodes admitted into the cache service, and may divide the content into a number of chunks that fills the amount of available storage at the participant nodes.FIG. 10depicts one example of a particular item of content (e.g., video) being divided into chunks. As shown inFIG. 10, content1000is divided into chunks using a content chunking process1010. In the example shown, content1000is divided into chunks1through5.

Caching controller115encrypts each of the divided chunks (block920). Caching controller115may obtain, using existing techniques, an encryption key for the content. In one implementation, the encryption algorithm used by caching controller115may be a symmetric encryption algorithm, and the encryption key may serve as both an encryption key and a decryption key. In another implementation, the encryption algorithm used by caching controller115may be an asymmetric encryption algorithm (i.e., a public/private key encryption algorithm), and the encryption key may be the public key, and the decryption key may be the private key. Caching controller115may encrypt each of the divided chunks using the encryption algorithm and the encryption key. In the example shown inFIG. 10, a chunk encrypting process1020is performed to encrypt chunks1through5into encrypted chunks1through5.

Caching controller115determines a participant node(s), of a set of nodes/devices available for use in the cache service, to be used for caching the chunks of content (block930). Caching controller115may use one or more different techniques for determining which device(s)/node(s) to be used for caching the chunks of content. One technique may, for example, determine which participant nodes120in the set of devices/nodes to use for caching based on their network locations relative to one or more client devices125(e.g., a certain range of network hops from one or more client devices125). An additional technique may determine which devices/nodes in the set of devices/nodes to use for caching based on load balancing principles. A further technique may determine which devices/nodes in the set of devices/nodes to use for caching based on traffic loads (e.g., traffic hotspots) in the vicinities of the participant nodes120. The one or more different techniques may be used alone, or in combination with one another. If the total set of devices/nodes available for use in the cache service includes {D1, D2, . . . , Dt}, caching controller115may determine a set of devices/nodes {D1, D2, . . . , Dc} to be used for caching the chunks, where c is less than, or equal to, t. In the example ofFIG. 10, caching controller115determines that encrypted chunk1and encrypted chunk2is to be stored at cache storage205-1of participant node120-1, encrypted chunk3is to be stored at cache storage205-2of participant node120-2, encrypted chunk4is to be stored at cache storage205-3of participant node120-3, and encrypted chunk5is to be stored at cache storage205-4of participant node120-4.

When determining which node(s) of participant nodes120in the set of devices/nodes are to be used for caching the content, caching controller115may also identify one or more “backup” participant nodes120at which content may be cached in the event that any particular participant node120, initially chosen for content caching, becomes unavailable (e.g., due to lost network connection, device power outage, device turned off, etc.). Identification of the one or more “backup” participant nodes120may be based on various factors, including network proximity to certain client devices125, available storage at each candidate “backup” participant node, and/or available bandwidth at each candidate “backup” participant node.

Caching controller115sends the divided chunks of data to the determined participant node(s) so as to interleave the chunks across the node(s) (block940). In the example ofFIG. 10, caching controller115engages in an interleaved chunk caching process1030to send encrypted chunk1and encrypted chunk2to cache storage205-1of participant node120-1, encrypted chunk3to cache storage205-2of participant node120-2, encrypted chunk4to cache storage205-3of participant node120-3, and encrypted chunk5to cache storage205-4of participant node120-4.

Caching controller115stores the network addresses and unique device IDs of the participant nodes120, the chunk name(s), and the storage locations at which the interleaved chunks are stored, to enable future retrieval (block950). For example, caching controller115may store the network addresses and unique device IDs of the participant nodes120, the chunk name(s), and the storage locations at which the interleaved chunks are stored, in main memory330of caching controller115. Alternatively, caching controller115may store this data in, for example, an external database not depicted in the network environment100ofFIG. 1. Caching controller115may additionally, or as an alternative to the network address, obtain and store the network location at which the registered participant node120attaches to network110. For example, if the registered participant node120attaches to a local area network (LAN), which in turn connects to network110via a server, router, or gateway, then caching controller115may obtain the network location (e.g., the network address) of the network attachment at the server, router, or gateway.

FIG. 11is a flow diagram that illustrates an exemplary process for client device125access to, and retrieval of, chunks of content from cache storage205at one or more participant nodes120. The exemplary process ofFIG. 11represents one exemplary implementation of block530ofFIG. 5. The exemplary process ofFIG. 11may be implemented by caching controller115, in conjunction with client device125. The exemplary process ofFIG. 11may be executed for each item of content to be requested for retrieval from cache storage205at participant nodes120. The exemplary process ofFIG. 11is described below with reference toFIG. 2BandFIG. 12.

The exemplary process includes caching controller115receiving a content request from client device125(block1100). The content request may identify the particular item of content (e.g., particular item of video) that the user at client device125wishes to access. Referring again toFIG. 2B, client device125is shown as sending a content request220to caching controller115for obtaining permission to access content chunks stored in cache storage.

Caching controller115obtains a device network address(es), a unique device ID(s), and storage locations at which the chunks of the requested content are interleaved in participant node ad-hoc distributed cache storage200(block1110). Caching controller115may have previously, in block950ofFIG. 9, stored this information subsequent to interleaving the chunks of the content across cache storage at multiple different participant nodes120. The device network address(es), unique device ID(s), and storage locations may include a network address and unique device ID for each participant node120at which a chunk(s) is stored. Each storage location includes an identification of a location in memory (i.e., of cache storage205) at which each chunk is stored. Caching controller115may have additionally, or as an alternative to the network address, stored a network location at which the participant node120attaches to network110. For example, if the participant node120attaches to a local area network (LAN), which in turn connects to network110via a server, router, or gateway, then caching controller115may obtain the network location (e.g., the network address) of the network attachment at the server, router, or gateway.

Caching controller115sends a chunk access permission, the unique device ID(s), the chunk name(s), a decryption key, the network address(es), and the storage locations of the chunks to client device125(block1120). Caching controller115may authenticate, or otherwise identify the legitimacy of the content request from, client device125, and may grant or deny access permission to client device125based on results of the authentication.

Referring again toFIG. 2B, caching controller115returns a chunk access permission225to client device125, where the chunk access permission225may further include the unique device ID(s), the chunk name(s), a decryption key, the network addresses, and the storage locations of the chunks at the respective participant nodes120. The unique device ID(s) uniquely identifies each participant node120at which chunks of the requested content has been stored in cache storage205. The decryption key includes the key that client device125may use to decrypt the chunks of content retrieved from cache storage205at participant nodes120. The network addresses include the network address of each of the participant nodes120at which chunks of content are stored in cache storage205. The storage locations identify locations in memory, in cache storage205, at each of the participant nodes120at which each chunk of the requested content is stored. Caching controller115may additionally, or as an alternative to the network address, send the network location at which the registered participant node120attaches to network110.

Client device125retrieves, using the network address(es) and storage locations, the chunks of content (block1130). Client device125sends a chunk retrieval request to each participant node120identified by a unique device ID and located at a network address contained in the chunk access permission225. A cache app130, at each participant node120that receives a chunk retrieval request, may validate the client device125identified in the chunk retrieval request prior to retrieving and returning the request chunk(s) of content to the client device125. In the example ofFIG. 12, encrypted chunks are depicted as being returned from cache storage205at participant nodes120-1through120-4.

Client device125, using the decryption key, decrypts the retrieved chunks, and orders the decrypted chunks to produce the content for presentation (block1140). The example ofFIG. 12depicts a chunk decrypting process1200being performed upon encrypted chunks1-5to produce original chunks1-5.FIG. 12further depicts a chunk ordering and combining process1210applied to the original chunks1-5to take the out-of-order chunks, place them in their proper sequential order, and to combine the ordered chunks to produce the content in its original un-cached form. A client application, at client device125, may then “consume” the content, such as, for example, presenting the content to a user of client125. If the content comprises a video file, the client application, as a media player, may play back the video file via a display unit of client device125. If the content comprises an audio-only file, the client application, as a media player, may play back the audio file via a speaker of client device125.

The foregoing description of implementations provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. For example, while series of blocks have been described with respect toFIGS. 5, 6A, 6B, 8A, 8B, 9, and 11, the order of the blocks may be varied in other implementations. Moreover, non-dependent blocks may be performed in parallel. Some embodiments have been described herein with respect to media that includes HLS media. However, the embodiments described herein may also be applied to Smooth Streaming or Adaptive Bit Rate Streaming media. Certain embodiments have been described herein as involving content caching with respect to content in a CDN. However, the systems and processes described herein may be applied to any application in which any type of content, or other forms of data, is delivered across network110from a content source to content receiving endpoints, and where content chunks are cached in association with such content delivery. Embodiments have been described herein as using divisions of physical memory for caching content chunks. Virtual or logical divisions of memory may also, or alternatively, be used for caching content chunks.