Method and system for hierarchical tracking of content and cache for networking and distribution to wired and mobile devices

FIELD OF THE INVENTION

This invention is directed to a method and apparatus for hierarchical tracking of content and/or cache for efficient delivery and distribution of information to wired and mobile devices.

Background

In a traditional content delivery/distribution network, the contents are stored in one or more centralized locations, and then distributed to the endpoints from centralized servers. The contents are distributed either directly or through a pre-arranged proxy server. This arrangement works well in a small-scale system where the contents are mostly static.

However, when the contents are updated very often, and when the set of users and the distribution network are very large, both the distribution of the contents among the servers and medium and long-haul access to these servers for up-to-date contents cause several problems. For example, this causes an excessive amount of traffic in the transport network which leads to excessive delay in downloading the contents because of congestion in the transport segment of the network.

In order to overcome these problems, researchers have experimented with the concept of distributed hash tables (DHT) for peer-to-peer communications and file sharing. DHT relieves the system of the need for centralized servers by using an algorithmic approach for efficient routing to disseminate control information related to the content or file from peer-to-peer. The DHT approach, therefore, helps to achieve an improved level of scalability and storage.

However, because DHT does not use keyword searches to find the desired information or files, the probability of successfully finding the exact desired information varies significantly. The probability of success can be improved if specific information were to be employed. However, the specific information required is rarely available. Because of the use of different virus protection mechanisms in each peer, the downloaded files could inadvertently bring in serious security threats to the hosts and the mobile devices.

<patcit id="pcit0001" dnum="WO2008024037A"><text>WO-A 2008/024037</text></patcit> describes a hierarchical distributed server network in which the least popular content is stored on the central server, and all content is distributed from the central server. More popular content is cached in larger numbers of copies on lower level servers. Complete content location information is stored only in a tracker at the central server. Lower level servers contain partial location information obtained from transactions in which the individual server has been involved.

BRIEF SUMMARY OF THE INVENTION

An embodiment of the present invention is directed to a method and apparatus for tracking media content (storage) and its cache (that is synched with the original content) in a large-scale wide-area distributed network. The system is capable of seamlessly distributing media content to wired and mobile-wireless devices. The system supports the required level of scalability, resiliency, security, and efficiency, and is suitable for next-generation content distribution networking (NG-CDN). Embodiments of the present invention implement hierarchical tracking of media content by employing four types of trackers in a system for hierarchical dissemination of control information related to the media content or file.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the invention will now be further described in the following more detailed description of the specification when read with reference to the accompanying drawing in which: <ul id="ul0001" list-style="none"><li><figref idref="f0001">Figure 1</figref> illustrates an embodiment of a hierarchical tracker-based NG-CDN architecture;</li><li><figref idref="f0002">Figure 2</figref> illustrates an embodiment of the invention for the distribution of storage, cache, and chunk location information from a master/super tracker to a micro-tracker;</li><li><figref idref="f0003">Figure 3</figref> illustrates steps implemented in an embodiment of the invention in updating of chunk/storage location information in the micro-tracker; and</li><li><figref idref="f0004">Figure 4</figref> illustrates steps implemented in an embodiment of the invention in the bypassing of the edge/mini-tracker and zonal/regional tracker by the micro-tracker for obtaining chunk/storage location information.</li></ul>

DETAILED DESCRIPTION OF THE INVENTION

The present inventions now will be described more fully hereinafter with reference to the accompanying drawings, in which some examples of the embodiments of the inventions are shown. Indeed, these inventions may be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided by way of example so that this disclosure will satisfy applicable legal requirements.

When a system uses a hierarchical topology, a prefix routing mechanism is required or a routing key must be aggregate-able. In a content distribution networking (CDN) system, a routing key is a content identifier (ID) or chunk ID, and is typically hashed from a file/chunk name, which is a random number and not aggregate-able. A chunk is a file or a segment of the content. In addition, it is not possible to deduce location information from the file/chunk name. If a content producer inserts its own location information into the content ID or chunk ID, there may be difficulty in determining the original location information and formulating a correct content/chunk ID by the content consumers. One solution would be to use a virtual prefixing method and, in the worst case, a few redirection or embedded URL procedure may be needed to identify original location.

As is known to those skilled in the art, in a small network, it is a common practice to partition the capacity of the storage servers in order to utilize the same physical platform for caching and storing the contents and chunks. However, in a very large network, the use of centralized servers is not recommended because that will generate significant amount of transport traffic when a user wants to download content, and will negatively impact both cost for service and performance of the service. Managed peer-to-peer and peer-to-peer streaming techniques attempt to improve the situation in CDN by distributing the information about content and chunk locations so that the user can download content from the nearest content/chunk server.

Embodiments of the present invention allow for incorporation of hierarchy information and additions of multiple layers (in multiple domains) which will make the CDN system more scalable because of the distributed and hierarchical nature of the system. Incorporation of hierarchy information and multiple layers in multiple domains will also make the CDN system very cost-effective because cheap storage capacity can be added incrementally without impacting reliability.

When a hierarchal mechanism is utilized, any wired and mobile device can obtain updated information about the location of the chunk and/or content through multiple ways. For example, updated information about the location of the chunk and/or content can be obtained from a mini-tracker or a regional-tracker and from multiple sources if the primary source is overloaded or malfunctioning. Hierarchical organization not only provides robustness or storage, it also guarantees accessibility within bounded time, just like the PSTN (public switched telephone network) networks

<figref idref="f0001">Figure 1</figref> illustrates an embodiment of a hierarchical tracker-based NG-CDN architecture. Four types of trackers are defined for hierarchical dissemination of control information related to the content or file. These trackers include micro-trackers (µ-Trackers), mini-trackers (MNT), zonal/regional trackers (Z/RT), and a master or super tracker (M/ST). In general, multiple micro-trackers (µTrackers) are served by one mini tracker (MNT), multiple clusters (in one admin domain) of mini-trackers are served by one zonal/regional tracker (Z/RT), and multiple zonal/regional trackers are served by one logical (virtual) master or super tracker (M/ST). One M/ST can be implemented by a full-protected logical ring of high-capacity trackers (servers), and these servers can be geographically distributed to support geo-redundancy.

A micro-tracker provides a sort of default or pre-provisioned or most-likely location of content or a chunk, a file or a segment of the content. Micro-trackers can be embedded in soft-endpoints and hard-endpoints. A mini-tracker keeps information on a location of the contents and the chunks, and then distributes this information to the micro-trackers within its jurisdiction. Multiple micro-trackers are served by one mini-tracker. A zonal/regional tracker keeps information on the location of the contents and the chunks in a zone or region (logical or physical geographical boundary), and then distributes this information to the mini-trackers within its jurisdiction. Multiple clusters (in one admin domain) of mini-trackers are served by one zonal/regional tracker. A master/super tracker keeps information on location of the contents and the chunks in all zones or regions (logical or physical geographical boundary) within its jurisdiction, and then distributes this information to these zonal/regional trackers. Multiple zonal/regional trackers are served by one logical (virtual) master/super tracker.

Hence, <figref idref="f0001">Figure 1</figref> illustrates a hierarchical system in which a master/super tracker serves multiple zonal/regional trackers. A zonal/regional tracker serves several edge/mini-trackers. An edge/mini-tracker serves several endpoints, each with an embedded micro-tracker. Under normal operations where there is no overloading or malfunctioning of any category of the hosts, endpoints receive up-to-date information about location of the chunk/storage from the next host in the hierarchy, i.e., an associated edge/mini-tracker. However, during fault or overload situations, the endpoint has the authority to bypass the faulty (or overloaded) hosts.

When a hierarchal mechanism is utilized, multilevel authentication and authorization can be easily implemented and maintained because it offers a higher level of scalability. Access to the regional-tracker and/or super-tracker can be allowed only when the endpoint with embedded micro-tracker cannot get timely update from the mini-tracker.

<figref idref="f0002">Figure 2</figref> illustrates an embodiment of the invention for the distribution of storage, cache, and chunk location information from a master/super tracker to a micro-tracker. According to an embodiment of the invention, one or more of a broadcast, Group/Select-Cast, multi-cast, and On-Demand technique may be used in the dissemination of information. For on-demand dissemination of location information, real-time, non-real-time, and off-time (in the background) updating are supported.

As shown in <figref idref="f0002">Figure 2</figref> information is initially sent from the master/super tracker to the micro-tracker through the zonal/regional tracker and the mini-tracker, respectively. The information may be sent at a predefined time, for example, hourly. Thereafter, the zonal/regional tracker may request and receive a real-time update from the master/super tracker, the mini-tracker may request and receive a real-time update from the zonal/regional tracker, and the micro-tracker may request and receive a real-time update from the mini-tracker. At a predefined period (say every 3 or 6 or 12 hours), the mini-tracker may request and receive an update from the master/super tracker, via the zonal/regional tracker, and the micro tracker may request and receive an update from the zonal/regional tracker, via the mini-tracker.

<figref idref="f0003">Figure 3</figref> illustrates steps implemented in an embodiment of the invention in updating of chunk/storage location information in the micro-tracker. Primary, secondary, and tertiary sources are maintained in the micro-tracker. Once again, under normal operations where there is no overloading and no malfunctioning of any category of the hosts, endpoints get up-to-date information about location of the chunk/storage from the primary host in the hierarchy. However, during verified (e.g., no response received within a preset time interval) fault or overload situations, the endpoint will have the authority to bypass the faulty (or overloaded) hosts, and can use the secondary and/or tertiary hosts in order to retrieve the latest location information.

<figref idref="f0004">Figure 4</figref> illustrates steps implemented in an embodiment of the invention in the bypassing of the edge/mini-tracker and zonal/regional tracker by the micro-tracker for obtaining chunk/storage location information. A micro-tracker may bypass the home edge/mini-tracker and home zonal/regional tracker only when an alternative/shadow host family (edge/mini-tracker and/or zonal/regional tracker) is discovered, and the home edge/mini-tracker and home zonal/regional tracker have verifiable overload and/or fault conditions.

One M/ST can be implemented via a fully-protected (in each direction of transmission) logical ring of high-capacity trackers (servers), and these servers can be geographically distributed to support geo-redundancy. The same mechanism can be utilized for other trackers as well, except for the micro-trackers.

The foregoing description of the invention illustrates and describes embodiments of the present invention. It is to be understood that the invention is capable of use in various other combinations, modifications, and environments and is capable of changes or modifications within the scope of the inventive concept as expressed herein, commensurate with the above teachings and/or the skill or knowledge of the relevant art. The embodiments described hereinabove are further intended to explain best modes known of practicing the invention and to enable others skilled in the art to utilize the invention in such, or other, embodiments and with the various modifications required by the particular applications or uses of the invention. Accordingly, the description is not intended to limit the invention to the form or application disclosed herein.