Patent Description:
Internet traffic related to Video-on-Demand (VoD) and linear video streaming services is projected to approximately reach <NUM> TB/s by the year <NUM>, representing <NUM>% of the total internet traffic. As such, Content Delivery Networks (CDN) have been deployed to facilitate scaling of the network while providing better Quality of Experience to clients. However, the sheer scale of the video traffic and the ever-increasing expectations with regards to the Quality of Experience raises stringent engineering challenges for Content delivery Networks. Under such conditions, network scalability becomes a critical problem for video delivery as traditional Content Delivery Networks (CDN) struggle to cope with the demand. Amongst those challenges, a crucial one involves enhancing the efficiency with which relevant resources are utilized (network, storage, and compute). This is an essential improvement as simple scale up in processing hardware in response to an increasing network load is, in many cases, insufficient to meet the required Quality of Experience for content user.

In <CIT>, a content delivery network may provide content items to requesting devices using a popularity-based distribution hierarchy. A central analysis system may determine popularity data for a content item stored in a first caching device. At a later time, the central analysis system may determine that a change in the popularity data is beyond a threshold value. The central analysis system may then transmit an instruction to move the content item from the first caching device to a second caching device in a different tier of caching devices than the first caching device. The central analysis system may update a content index to indicate that the content item has been moved to the second caching device. A user device may then be redirected to request the content item directly from the second caching device.

Various example embodiments of the disclosure are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without departing from the scope of the invention as defined by the appended claims. Thus, the following description and drawings are illustrative and are not to be construed as limiting. Numerous specific details are described to provide a thorough understanding of the disclosure. However, in certain instances, well-known or conventional details are not described in order to avoid obscuring the description. References to one or an embodiment in the present disclosure can be references to the same embodiment or any embodiment; and, such references mean at least one of the embodiments.

Note that titles or subtitles may be used in the examples for convenience of a reader, which in no way should limit the scope of the invention, whose scope is defined by the appended claims.

These and other features of the disclosure will become more fully apparent from the following description and appended claims.

The invention is set out in the claims. To the extent that any matter herein does not fall within the scope of the claims, that matter does not form part of the invention.

Disclosed are systems, methods, and computer-readable media for optimizing a hit rate performance and service level response times for a cluster of in-network cache servers. Aspects of the disclosed technology are directed to a filtering scheme based on a multi-level popularity assessment of content request traffic. In some embodiments of the present technology, a controller-tuned threshold parameter is used for differentiating between popular and semi-popular contents.

In one aspect of the present technology, a method includes specifying, at an edge device, a threshold parameter for partitioning a meta-cache, comprising a plurality of last requested content identifiers, into a popular portion and a semi-popular portion; re-directing, using an appropriate forwarding/routing protocol, a first cache-miss request generated for a content identifier in the semi-popular portion of the meta-cache, to one or more additional cache servers; re-directing, using appropriates forwarding/routing protocol, a second cache-miss request generated by the one or more additional cache servers for the content identifiers in the semi-popular portion of the meta-cache to an origin server hosting the requested content. Some embodiments of the present technology further comprise a step of tuning a value of the threshold parameter, using a Proportional-Integrate controller, to optimize a tradeoff between cache hit rate and one or more other network performance metrics.

As such, embodiments of the present technology provide for a multi-level popularity based filtering of content requests for enhancing a hit rate of edge cache servers in content delivery networks. In some embodiments, this is accomplished by maintaining a meta-cache of content-identifiers corresponding to a number of most recently requested contents along with a threshold parameter for partitioning meta-cache entries into popular and semi-popular categories. For example, contents identified as semi-popular are associated with a different cache miss forwarding policy as opposed to contents deemed as popular and similarly for contents deemed as unpopular. To further expand upon the aforementioned feature, in an event of cache-miss request for content identified in semi-popular portion of the meta-cache, the first receiving cache server may re-direct the request to another cache server that may have been pseudo-randomly chosen rather than forwarding the request directly to the origin server.

In one aspect of the present technology, a system includes one or more content-request filtering units communicatively coupled to one or more edge cache servers, each content-request filtering unit may further comprise: a meta-cache of a plurality of most recently requested content identifiers partitioned across a threshold index, into a popular and a semi-popular portions, wherein requests for content identifiers in the semi-popular portion are forwarded to an origin content server only in an event of a cache miss from each of a plurality of cache servers across which a semi-popular content request is sequentially steered. In some embodiments of the present technology, the system may further comprise one or more PI controller operative to tune the threshold parameter of the meta-cache to thereby optimize a trade-off between cache hit rate and one or more other performance attributes.

Therefore, a content filtering/routing unit comprising a meta-cache of most recently used content identifiers may apply a different cache-miss forwarding policy to requests for contents based on a popularity level of the aforementioned content. In some embodiments, the present technology includes a threshold parameter for differentiating between popular and semi-popular contents in the meta-cache of most recently used content identifiers. The threshold parameter may be tuned using a self-tuning Proportional-Integral controller, in accordance with some embodiments. For example, request for contents identified in a semi-popular portion of the meta cache may be re-directed to one or more additional cache servers after encountering an initial cash miss from a first cache server. Accordingly, embodiments of the present technology enable a more thorough cache search to be performed for requested contents prior to re-directing the content request to an origin content server.

Multi-tiered video Content Delivery Network (CDN) architectures, generally consist of three main components: (i) clients who request and consume video chunks, (ii) origin servers that serve the requested content, and (iii) edge caches, located closer to the clients (i.e., in an ISP network), which store the most popular video chunks to reduce the load on the origin servers. A key property to be satisfied by a Content Delivery Networks (CDN) is to serve content with small latency while minimizing the infrastructure costs. One approach to achieve low-latency content delivery without incurring significant infrastructure cost is based on caching popular content close to the users, while keeping less popular content on the more centralized servers. As such, a network of caches, each reasonably close to the clients, and capable of serving the same content as provided by a single origin server may be used to cache as much of the content as possible at the edge, and let as much as possible of the unpopular content be served by the origin server.

The rate at which content is requested and successfully served from a selected server, such as an edge cache server, can be termed a "hit rate. " The hit rate on edge caches has a strong impact on Quality of Experience (QoE) related factors, such as chunk download time. For example, it has been shown that cache misses increase server latency by up to an order of magnitude, which in turn translates into increased client start-up times. One reason for this degradation of server latency involves the incurred network cost of proxying Hypertext Transfer Protocol (HTTP or HTTPS) connections to the origin server in an event of a cache miss at a cache server. It is, therefore, important to the scalability of the CDN architecture that most requests for content are successfully served from edge caches, as this decreases the load on the origin servers.

However, as the load on edge caches increases, addressing the capacity issue by simply using more powerful servers or adding hardware resources may become prohibitively costly. Popularity based filtering at the edge may therefore become necessary in order to decide where the content should be cached, whether to re-direct the request or proxy the content, as well as where to re-direct content requests. Current architectures suffer from two main issues. Namely, upon cache miss, HTTP proxying is used in order to fetch content from the origin. This has a non-negligible performance cost compared to rerouting the requests towards the origin directly at layer <NUM>. Furthermore, existing architectures do not utilize the horizontal scaling of the cache for collaboration between caches, instead, when there is a cache miss, the request is usually forwarded back to the origin, whereas trying another cache beforehand could be beneficial for semi-popular content.

The forgoing is addressed by embodiments of the present technology directed to system, method and computer-readable medium for video Content Delivery Networks (CDN) that utilizes chunk-level content addressing and multi-tiered content popularity assessment (in deployed networking technologies) to make intelligent decision with regards to optimal processing of content request and content delivery. The optimal processing of content-related traffic, in one regard, is directed to enhancing a hit ratio of a cache system, which in turn reduces latency and network loading associated with servicing of request for contents such as video. As such, some embodiments of the present invention are directed to increasing cache hit rate at the network edge while also reducing adverse impacts (i.e., latency and network load) associated with cache misses. To that end, embodiments of the disclosed technology utilize network-layer video chunk naming to facilitate popularity-based multi-tier classification for the requested contents.

In some embodiments, named-video chunks (content identifier embedded within network address of the request packet header) may be used in the forwarding plane within a system and/or configuration that is deployable in current IP-based networks. Accordingly, each video segment may be matched with a unique network identifier, using, for example, a <NUM>-bit encoding to contain the video identifier, the identifier of the segment within the video, and potentially additional metadata such as the segment duration and the requested video bitrate/quality. An IPv6 address may then be constructed from this name. With reference to <FIG>, an example of a modified IPv6 address <NUM> comprises a first <NUM> bits portion <NUM> that constitute a routing prefix and subnet identifier that may be specific to the video producer and acts as a network locator. Moreover, the modified example IPv6 address <NUM> further comprises second a <NUM>-bits portion <NUM> that constitute content metadata and acts as a content identifier.

In accordance to some embodiments of the present technology, chunk-level content addressing as part of the layer <NUM> address portion of a content request packet header may be used to provide content-awareness and tracking at the network layer. In some embodiments of the present technology the aforementioned Network level content-awareness and tracking may be used in conjunction with a Last Recently Used (LRU) filtering policy to provide a multi-level popularity based filtering of content requests. In some embodiments, popularity-based LRU filtering may be implemented by keeping a "meta-cache" of identifiers, driven by a Least Recently Used replacement policy. Presence of a content identifier in the meta-cache may be considered as an indicator of popularity. However, instead of classifying between "popular" and "unpopular" content, embodiments of the present technology disclose a three-tiered classification approach which classifies content between "popular", "semi-popular" and "unpopular". Thus enhancing an accuracy and efficiency with which the delivery of unpopular content are offloaded to the origin server and popular content are served at the cache.

In accordance with some embodiments of the present technology, chunk-level content addressing consists of assigning a unique and globally routable IPv6 address to each video chunk. Exposing the chunk and video identifiers in the IPv6 addresses space provides network layer visibility to the requested content. Accordingly, a content routing/filtering service, disposed between client system and network caching resources may be used to examine content request packets destined for one or more edge cache servers, in order to construct a meta-cache of the Last Recently Used content identifiers from the content-identifiers exposed as IP addresses in the content request packet. The content routing/filtering service may then assign specific popularity ratings (i.e., popular or a semi-popular rating) to different client-requested content based on the indexed position of the corresponding content identifier in the meta-cache of the Last Recently Used content identifiers. In some embodiments, the indexed position, for the purpose of popularity rating, may be determined in relation to a statically or dynamically computed threshold level. Contents may be identified as popular or semi-popular depending on whether the corresponding content identifier is disposed above or below the threshold level, while content identifiers missing from the meta-cache deemed to correspond to un-popular content. The content routing/filtering service may then make in-band content request forwarding decisions based on content popularity classification of the requested content.

According to some embodiments of the present technology, content deemed as popular may be served locally at the cache server. Conversely, requests for contents deemed as unpopular may be directed to the origin server and served by the same. For semi-popular content unavailable at the initial cache server, it may be likely that another (edge) cache has a copy of the content. Therefore, in those cases, rather than directly going back to the origin, embodiments provide for a detour through another pseudo-randomly-chosen edge cache. The re-direction/detour to a second cache server and/or the origin server on cache misses may be handled, in accordance to some embodiments, with the use of HTTP proxy. However, in some embodiments of the present technology, the re-direction/detour may be performed using a Segment Routing Load Balancing (SRLB) approach (such as, for example, <NUM> LB load balancing protocol) to improve performance. For example, in some embodiments of the disclosed technology, IPv6 Segment Routing (SRv6) is utilized to steer client requests through a chain of candidate servers based on a determined popularity level of the requested content. An example of SRv6 implementation is provided in <FIG>.

<FIG> illustrates an operation of an example content delivery network (CDN) <NUM>, in accordance with some embodiments of the present technology. In the example CDN network <NUM> content routers <NUM> and <NUM> comprise a Last Recently Used (LRU) filter components <NUM> and <NUM>, respectively. The LRU filter <NUM> comprises a meta-cache <NUM> of size C1 with an associated (popularity) threshold parameter <NUM> and the LRU filters <NUM> comprises a meta-cache <NUM> of size C1 with an associated threshold parameter <NUM>. LRU filters <NUM> and <NUM> control and filter access to the origin server <NUM> and the cache server cluster comprising of cache server <NUM> and <NUM>. In some embodiments, LRU filter functionality may be incorporated into one or more content routers. In some embodiments, LRU filters may be implemented as independent devices, software services, protocols, or a combination software/hardware service. LRU filters may be disposed close to the network edge and tasked with controlling and filtering of content requests to and from one or more associated cache servers and/or one or more origin content servers. In some embodiments, LRU filter may be implemented as a unit that is communicatively coupled to one or more content routers and provides necessary information to the corresponding content routers as to how to route requests for different contents.

Referring back to <FIG>, an operation of the example CDN <NUM>, upon receipt of a content request, is illustrated in accordance with some embodiments, by flow lines <NUM>, <NUM> and <NUM>. Flow line <NUM> corresponds to a scenario wherein the content identifier (<NUM>) in the incoming request packet is found in the meta-cache <NUM> of the LRU filter <NUM>, and its corresponding index value is smaller than the threshold index value (i.e., its position is above the threshold index <NUM> which corresponds to the popular portion of the meta-cache <NUM>). Accordingly, LRU filter <NUM> moves the corresponding content identifier to the top of the meta-cache <NUM> and the query is accepted by the corresponding cache server (i.e., the query is served by the edge server <NUM>. ) In case of a cache miss at <NUM>, the requested (popular) content is proxied from origin server <NUM> and a local copy is saved on the cache server <NUM>.

When considering the index of an element in the LRU cache, the smaller the index, the earlier the element appears in the cache list. As a consequence the smaller the index, the greater the popularity. A content may therefore be deemed as popular whenever its index is smaller than the threshold, and semi-popular whenever its index is greater than the threshold in accordance to some embodiments of the present technology. However, It should be noted that with respect to the illustration of the LRU cache <NUM> and <NUM> in <FIG>, the bottom of the LRU heap corresponding to the more recently observed contents is depicted on the top part of the LRU cache illustration. Therefore, example LRU cache illustrations <NUM> and <NUM> correspond to an ascending order of index value arrangement.

Conversely, flow line <NUM> corresponds to a scenario wherein the requested content identifier is not found in the meta-cache <NUM> of the LRU filter <NUM> (i.e., unpopular content). As such, LRU filter <NUM> adds/inserts the missing content Identifier at the top of meta-cache <NUM> (which causes the removal of the last content identifier in the meta-cache if it is full), and the query is refused (i.e. the request is directly forwarded to the origin server <NUM>.

As described, embodiments of the present technology provide for a mid-level rating of popularity (semi-popular) that is between unpopular and popular level. In the example CDN <NUM> of <FIG> this is illustrated by flow line <NUM> which corresponds to a scenario wherein the requested content identifier, embedded in layer <NUM> address portion of the incoming content request packet, corresponds to a content identifier (<NUM>), which is found in the meta-cache <NUM> of LRU <NUM>, at a position with a greater index value than the threshold index <NUM> (i.e., its position is below the threshold index <NUM> which corresponds to the semi-popular portion of the meta-cache <NUM>). For semi-popular content, a cache miss at the initial/first receiving cache server (cache server <NUM>), will cause the LRU filter <NUM> or the content router <NUM> to re-route the request to a second pseudo-randomly-selected cache server (<NUM>) through its associated content router <NUM> (for example by using a Segment Routing Load Balancing forwarding protocol). Upon receipt of the re-directed content request, LRU filter <NUM> moves the corresponding content identifier (<NUM>) to the top of the meta-cache <NUM>. If the second LRU filter (<NUM>) serving the second pseudo-randomly chosen cache server (<NUM>) also does not have the requested content (corresponding to content identifier <NUM>), or if the second LRU filter (<NUM>) serving the second pseudo-randomly chosen cache server (<NUM>) does have the requested content but at a position above the threshold parameter <NUM> (i.e., in the semi-popular portion of the meta-cache <NUM> , the query is forwarded to the Origin server <NUM>. If the re-directed content is deemed as popular according to the LRU filter <NUM> of the second edge cache server <NUM>, the request is accepted locally on the second edge cache server <NUM> and, if locally unavailable, the content is proxied from the origin server <NUM>.

In some embodiments, the aforementioned cache system may be implemented as a doubly linked list joined to a hash map of pointers to entries within the list. In one embodiment of the present technology, a size of the meta-cache is set to six times the size of the cache to which it filters access. This provides almost-optimal hit-rate in the case of a light load (where threshold is thus equal to size ).

Some embodiments of the present technology is directed to a filtering scheme for semi-popular content that involves re-directing a cache miss from a first receiving cache server to another cache server. This feature is based on the likelihood that a semi-popular content will be available at another edge cache, and thus incurring the forwarding latency of triangular routing between two caches to visit another cache before going back to the origin (which is typically geographically farther away) is deemed as worthwhile. To that purpose, in accordance to some embodiments, IPv6 Segment Routing (SRv6) and Segment Routing Load Balancing (SRLB) protocol(s) may be leveraged to visit multiple pseudo-randomly-chosen caches before re-directing the request back to the origin server.

<FIG> illustrates an example of Segment Routing implementation <NUM> for a popularity-based filtering of content request and response traffic in accordance to some embodiments of the present technology. In the example implementation <NUM>, a dispatcher unit (<NUM>), which may be located near the client <NUM> (e.g. in the clients network stack, or set-top box) is deployed to inserts a Segment Routing header (comprising a Segment Identifier List <NUM>) into a content request packet to facilitated a request filtering process upstream. For example, when the client <NUM> issues a new-connection packet (e.g. TCP SYN), the dispatcher <NUM> inserts a Segment Identifier (SID) list <NUM> into Segment Routing Header of a request packet. In the example embodiment illustrated in <FIG>, SID list <NUM> comprises three entries, with the first two entries corresponding to segment identifiers <NUM> and <NUM>, respectively identifying two pseudo-randomly-chosen cache servers cache server <NUM> and cache server <NUM>. The last entry in SID list <NUM> corresponds to a segment identifier for the origin server <NUM>. For the purpose of clarification, when Segment Routing is implemented with an IPv6 forwarding plane, an SID list may be interchangeably referred to as an SRv6 (Segment Routing with IPv6 forwarding) list.

The accepting server (which may be any of the cache or origin server), upon acceptance of the new-connection packet from the client <NUM>, inserts its network or segment address as metadata into the response packet back to the client. The dispatcher (<NUM>) then records the address of the responding server for the remainder of the lifetime of the connection. Accordingly, when the client issues a further packet (e.g. TCP ACK) to the accepting server, the dispatcher inserts a Segment Routing header with only one segment identifier, that identifies the accepting server from the original trio of servers identified in the SID list <NUM> (namely, cache server <NUM>, cache server <NUM> and origin server.

Therefore once a response containing metadata with the address of the accepting server is received by the dispatcher, all subsequent packets associated with the established connection (to the accepting server) will only include the one segment identifier (from the three specified in the original Segment Identifier list embedded in the initial content request or new-connection packet) corresponding to the server/node which accepted the content request and terminated the connection. Consequently, the client is able to establish a direct data connection to the accepting server for the delivery of the requested content.

With reference to the example in <FIG>, LRU filter/content router <NUM>, <NUM> and <NUM> are deployed for the purpose of filtering access to and managing a cache-miss response of cache servers <NUM>, <NUM> and <NUM>, respectively. As such each LRU filter/content router is disposed in proximity to the cache server to which it filters access. In accordance to the example embodiments in <FIG> and <FIG> the filtering/managing operation of the LRU filter/content router depends upon a threshold-based popularity classification of the requested content as popular, semi-popular or unpopular.

Referring back to <FIG>, the incoming (new-connection) content request <NUM> destined for cache server <NUM> is received at the corresponding LRU filter/content router <NUM>. If the requested content identifier (extracted from the content request <NUM>) is found in the popular portion of the meta-cache in the LRU filter/content router <NUM>, the requested content is deemed as 'popular'. Accordingly, the content request is accepted at cache server <NUM> (the initial receiving cache) and the corresponding connection <NUM> is terminated there at. As such, the request packet is forwarded to the local stack of cache server <NUM> without visiting further segments. If the requested 'popular' content is not locally available on cache server <NUM>, the request is proxied to the origin server <NUM> and the content is inserted into the cache server <NUM> according to the insertion policy of the caching software (i.e., Least Recently Used, Least Frequently Used, Fist In Fist Out, etc.). After terminating connection <NUM>, Cache server <NUM> will dispatch a response packet back to the client with its segment identifier (<NUM>), indicated by reference <NUM> in <FIG>.

However, if the requested content identifier (extracted from the content request packet) is found in the semi-popular portion of the meta-cache (items <NUM> and <NUM> in <FIG>) in the LRU filter/router <NUM>, the requested content is deemed as 'semi-popular'. Accordingly, LRU filter/ router <NUM> triggers a retry, corresponding to connection <NUM> in <FIG> (connection <NUM> in <FIG>) and forwards the request to the next segment identifier entry (i.e., SID <NUM>) in the SRv6 list <NUM> which corresponds to the second pseudo-randomly selected cache server (cache server <NUM>). This will require the LRU filter/router <NUM> (associated with cache server <NUM>) to route/forward the content request to a corresponding LRU filter/router <NUM> associated with cache server <NUM>. If the requested "semi-popular' content is is deemed popular by the LRU filter <NUM>, the re-tried/re-directed content request is accepted at cache server <NUM> (the second receiving cache) and the corresponding connection <NUM> is terminated there. As such, the request packet is forwarded to the local stack of cache server <NUM> without visiting further segments and the requested 'semi-popular' content is served directly at cache server <NUM>. After terminating the connection <NUM>, the accepting server (cache server <NUM>) will dispatch a response packet back to the client into which it inserts its own segment identifier (<NUM>), indicated by reference <NUM> in <FIG>. However, If the requested "semi-popular' content is not found nor deemed popular by the LRU filter <NUM> serving cache server <NUM>, the connection request <NUM> is refused and the request is re-directed, across connection <NUM>, to the origin server <NUM> (the last segment specified in the SRv6 list <NUM>). The origin server <NUM> will accept the request and terminate the corresponding connection <NUM>. As such, the request packet is forwarded to the local stack of origin server <NUM> and the requested 'semi-popular' content is served directly at origin server <NUM>. After terminating the connection <NUM>, the Accepting server (origin server <NUM>) will dispatch a response packet back to the client into which it inserts its own segment identifier (ORIGIN), indicated by reference <NUM> in <FIG>.

Finally, if the requested content identifier, extracted from the client request packet destined towards the initial receiving cache (cache server <NUM>), is not found anywhere in the meta-cache (illustrated as items <NUM> and <NUM> in <FIG>) of the corresponding LRU filter/router <NUM>, the requested content is deemed as 'unpopular'. Accordingly, if the requested 'unpopular' content is not locally available on cache server <NUM>, the missing content identifier is inserted at the top of the meta-cache associated with LRU filter/router <NUM>, and the request is re-directed, across connection <NUM>, to the Origin server <NUM>. Queries directed to the origin server <NUM> are terminated and forwarded to the local stack. After terminating the connection <NUM>, the accepting server (origin server <NUM>) will dispatch a response packet back to the client into which it inserts its own segment identifier (ORIGIN), indicated by reference <NUM> in <FIG>.

Hence, with high probability, unpopular content are not served by the edge cache but rather directly offloaded (at the network layer) to the origin server. The offloaded connections no longer need to be proxied at the edge, thus avoiding unnecessary HTTP terminations and the cache of the edge proxy is not be polluted with unpopular content, consequently increasing the hit rate.

In accordance to some embodiments of the present technology, a Proportional Integral (PI) controller may be used to tune the parameters of the LRU filter. For example, a PI controller may be used to tune the (popularity) threshold parameter which partitions a meta-cache of last recently requested content identifiers into popular and semi-popular portions, in such a way to control and optimize a trade-off between cache hit rate performance and average response time of network cache servers. For example, raising the popularity threshold in the meta-cache of an LRU filter, brings about an increase in the number of requests accepted at the corresponding cache server, hence a corresponding increase in the response time of the cache server. In some embodiments, a PI controller may be used in conjunction with the LRU filter in order to tune a popularity threshold parameter (for identification of popular content) of the LRU filter. A PI-controller accomplishes this by, for example, taking the current response time of the associated cache server (to which the LRU filters access), as an input parameter, and comparing it with an objective flow completion time, to make according adjustments to a value of the (popularity) threshold parameter of the LRU filter, until a desired balance is reached. In this way, PI controller may be used to optimize network cache access.

<FIG> illustrates an example implementation <NUM> wherein a content router <NUM> working in conjunction with an LRU filter <NUM> is used to filter and control access to a cache server <NUM>. The LRU filter <NUM> further comprises a meta-cache <NUM> of size C1 for storing content identifiers and a threshold parameter k associated with identification of popular/semi-popular/unpopular content. The popular/semi-popular/unpopular classification of content requests ultimately determines which content requests are accepted at the cache server, which are retried with a different cache server, and which are refused and re-directed to the origin server. In the example implementation <NUM>, a response time, 'δt', of a cache server <NUM>, may be measured and provided as input to a PI controller <NUM>. The PI-controller <NUM>, based on the input response time, optimally tunes the level of the threshold parameter k in the meta-cache <NUM> of LRU filter <NUM>. In this way a PI-controller may be used to tune and optimize operation of an LRU filter which ultimately irnproves edges caching performance in networks.

In one embodiment of the invention, a PI-controller may be implemented using a self-tuning PI such as Yaksha that controls a web server response time by filtering requests according to an acceptance probability. One advantage of such self-tuning PI-controller is that it may act as an independent module in front of the cache without requiring any integration effort. Furthermore, the self-tuning functionality obviates requirements for human input or prior-knowledge of the server characteristics.

According to some embodiment, Yaksha-based filtering may be adapted for operation as prescribed by some embodiments of the present technology, by converting the filtering criteria from an acceptance probability into a Last Recently Used (LRU) popularity threshold.

If the request pattern follows a Poisson arrival and the popularity distribution q(r) is known, in accordance to some embodiments, Che's approximation may be utilized to compute the probability of accepting a request for a content as a function of the content popularity threshold. Content popularity threshold, may be defined by equation (<NUM>), wherein k represent the content popularity threshold and p(k), as defined by equation <NUM>, represents the probability of accepting a request as a function of the content popularity threshold, k. The parameter tc in equation <NUM> and <NUM> corresponds to the root of the equation <NUM>. <MAT>
<MAT>.

The probability function defined by (<NUM>) may then be inverted in order to compute k as a function of the acceptance probability output by a Yaksha filter (i.e., a self-tuning PI, configured to filter server requests in accordance to an acceptance probability. ) This is illustrated in <FIG> wherein a response time 'δt' of a cache server <NUM> is used as input into a Yaksha filter <NUM>. The output <NUM> of the Yaksha filter, corresponding to acceptance probability p, is inverted at <NUM>, to thus, compute a content popularity threshold parameter k as a function of p. The threshold parameter k may then be used to provide a multi-tiered popularity rating for the requested contents. In some embodiments, the inversion operation (<NUM>) may be performed through a pre-computed inversion tables for efficiency purpose.

It should be noted that embodiments of the disclosed technology provide for any self-tuning PI-controller to be used directly on the popularity threshold parameter k. In some embodiments, the tuning may be performed on server-side metrics, such as CPU usage or TCP queue length instead of the flow completion time. Such metrics may be more precise and instantaneous than flow completion time but may require tighter coupling of the acceptance system and the cache server.

The disclosure now turns to <FIG> and <FIG>, which illustrate example architectures of computing an network devices, such as client computers, switches, routers, controllers, servers, and so forth.

<FIG> illustrates a computing system architecture <NUM> including components in electrical communication with each other using a connection <NUM>, such as a bus. System <NUM> includes a processing unit (CPU or processor) <NUM> and a system connection <NUM> that couples various system components including the system memory <NUM>, such as read only memory (ROM) <NUM> and random access memory (RAM) <NUM>, to the processor <NUM>. The system <NUM> can include a cache of high-speed memory connected directly with, in close proximity to, or integrated as part of the processor <NUM>. The system <NUM> can copy data from the memory <NUM> and/or the storage device <NUM> to the cache <NUM> for quick access by the processor <NUM>. In this way, the cache can provide a performance boost that avoids processor <NUM> delays while waiting for data. These and other modules can control or be configured to control the processor <NUM> to perform various actions. Other system memory <NUM> may be available for use as well. The memory <NUM> can include multiple different types of memory with different performance characteristics. The processor <NUM> can include any general purpose processor and a hardware or software service, such as service <NUM><NUM>, service <NUM><NUM>, and service <NUM><NUM> stored in storage device <NUM>, configured to control the processor <NUM> as well as a special-purpose processor where software instructions are incorporated into the actual processor design. The processor <NUM> may be a completely self-contained computing system, containing multiple cores or processors, a bus, memory controller, cache, etc. A multi-core processor may be symmetric or asymmetric.

To enable user interaction with the computing device <NUM>, an input device <NUM> can represent any number of input mechanisms, such as a microphone for speech, a touch-sensitive screen for gesture or graphical input, keyboard, mouse, motion input, speech and so forth. An output device <NUM> can also be one or more of a number of output mechanisms known to those of skill in the art. In some instances, multimodal systems can enable a user to provide multiple types of input to communicate with the computing device <NUM>. The communications interface <NUM> can generally govern and manage the user input and system output. There is no restriction on operating on any particular hardware arrangement and therefore the basic features here may easily be substituted for improved hardware or firmware arrangements as they are developed.

The storage device <NUM> can include services <NUM>, <NUM>, <NUM> for controlling the processor <NUM>. Other hardware or software modules are contemplated. The storage device <NUM> can be connected to the system connection <NUM>. In one aspect, a hardware module that performs a particular function can include the software component stored in a computer-readable medium in connection with the necessary hardware components, such as the processor <NUM>, connection <NUM>, output device <NUM>, and so forth, to carry out the function.

<FIG> illustrates an example network device <NUM> suitable for performing switching, routing, assurance, and other networking operations. Network device <NUM> includes a central processing unit (CPU) <NUM>, interfaces <NUM>, and a connection <NUM> (e.g., a PCI bus). When acting under the control of appropriate software or firmware, the CPU <NUM> is responsible for executing packet management, error detection, and/or routing functions. The CPU <NUM> preferably accomplishes all these functions under the control of software including an operating system and any appropriate applications software. CPU <NUM> may include one or more processors <NUM>, such as a processor from the INTEL X106 family of microprocessors. In some cases, processor <NUM> can be specially designed hardware for controlling the operations of network device <NUM>. In some cases, a memory <NUM> (e.g., non-volatile RAM, ROM, TCAM, etc.) also forms part of CPU <NUM>. However, there are many different ways in which memory could be coupled to the system. In some cases, the network device <NUM> can include a memory and/or storage hardware, such as TCAM, separate from CPU <NUM>. Such memory and/or storage hardware can be coupled with the network device <NUM> and its components via, for example, connection <NUM>.

The interfaces <NUM> are typically provided as modular interface cards (sometimes referred to as "line cards"). Generally, they control the sending and receiving of data packets over the network and sometimes support other peripherals used with the network device <NUM>. Among the interfaces that may be provided are Ethernet interfaces, frame relay interfaces, cable interfaces, DSL interfaces, token ring interfaces, and the like. In addition, various very high-speed interfaces may be provided such as fast token ring interfaces, wireless interfaces, Ethernet interfaces, Gigabit Ethernet interfaces, ATM interfaces, HSSI interfaces, POS interfaces, FDDI interfaces, WIFI interfaces, <NUM>/<NUM>/<NUM> cellular interfaces, CAN BUS, LoRA, and the like. Generally, these interfaces may include ports appropriate for communication with the appropriate media. In some cases, they may also include an independent processor and, in some instances, volatile RAM. The independent processors may control such communications intensive tasks as packet switching, media control, signal processing, crypto processing, and management. By providing separate processors for the communications intensive tasks, these interfaces allow the master microprocessor <NUM> to efficiently perform routing computations, network diagnostics, security functions, etc..

Although the system shown in <FIG> is one specific network device of the present disclosure, it is by no means the only network device architecture on which the concepts herein can be implemented. For example, an architecture having a single processor that handles communications as well as routing computations, etc., can be used. Further, other types of interfaces and media could also be used with the network device <NUM>.

The network device <NUM> can also include an application-specific integrated circuit (ASIC), which can be configured to perform routing, switching, and/or other operations. The ASIC can communicate with other components in the network device <NUM> via the connection <NUM>, to exchange data and signals and coordinate various types of operations by the network device <NUM>, such as routing, switching, and/or data storage operations, for example.

<FIG> illustrates an example process flow <NUM> for a popularity-based content-request filtering process based on applying a popularity threshold parameter to a meta-cache of last recently used content-identifiers. Popularity of a requested content chunk is determined based on a comparison of an index position of the corresponding content-identifier with a threshold index within the meta-cache of the last recently used content-identifiers. For example content-identifiers disposed in the meta-cache at index positions above the threshold index may be deemed as more popular whereas those disposed at indexed positions below the threshold index may be deemed as less popular (semi-popular). Content with no corresponding content-identifier within the meta-cache may be deemed as unpopular. The popularity determination may then determine how an LRU filtering/routing service will forward the content-request. With reference to <FIG> at step <NUM> a content-identifier embedded in an incoming content-request packet is examined with respect to the entries in a meta-cache of last recently used content-identifiers. If the incoming content-identifier is not present in the meta-cache (<NUM>), the requested content is deemed as unpopular, the missing content-identifier is inserted at the top of the meta-cache and the request is re-directed to the origin server at step <NUM>. However if the incoming content-identifier is present in the meta-cache (<NUM>), the operation moves to step <NUM> wherein an indexed position of the content-identifier in the meta-cache is compared to a threshold index value.

If the indexed position of the incoming content-identifier is higher (closer to the top) in the LRU meta-cache than the threshold index (<NUM>) the content is deemed as popular and the operation moves to step <NUM> wherein the associated cache server (Cache <NUM>) is checked for the requested content. If the content is present in Cache <NUM> (<NUM>), it is served directly therefrom at step <NUM>. If the content is not present in Cache <NUM> (<NUM>), the operation moves to step <NUM> wherein the requested content is proxied, by Cache <NUM>, from the origin server. The content is then inserted into Cache <NUM> at step <NUM>.

However, if the indexed position of the incoming content-identifier is lower (closer to the bottom) in the meta-cache than the threshold index (<NUM>), the corresponding content is deemed as 'semi-popular' and the operation moves to step <NUM> wherein the content-request is re-directed, for example by a first LRU filtering/routing service serving the first cache server (cache <NUM>) , to a second LRU filtering/routing service serving a secondary cache server (Cache <NUM>).

In some embodiments, the forwarding and redirection operation may be implemented using an SRv6 based approach, wherein segment identifiers for each of the first and the second cache servers and the origin servers are inserted as an SID list into a header of the content-request packet from the client.

Referring back to the example process flow <NUM> in <FIG>, the second receiving LRU filtering/routing service serving the secondary cache server (Cache <NUM>), upon receiving the re-directed content-request from the first LRU filtering/routing service, verifies the presence of the incoming content-identifier in the local meta-cache. If the incoming content-identifier is present in the meta-cache, the operation moves to step <NUM> wherein an indexed position of the content-identifier in the meta-cache is compared to a threshold index value. If the indexed position of the incoming content-identifier is higher (closer to the top) in the LRU meta-cache than the threshold index (<NUM>) the content is deemed as popular and the operation moves to step <NUM> wherein the associated cache server (Cache <NUM>) is checked for the requested content. If the content is present in Cache <NUM> (<NUM>), it is served directly therefrom at step <NUM>. If the content is not present in Cache <NUM> (<NUM>), the operation moves to step <NUM> wherein the requested content is proxied, by Cache <NUM>, from the origin server. The content is then inserted into Cache <NUM> at step <NUM>.

However, if the indexed position of the incoming content-identifier is lower (closer to the bottom) in the LRU meta-cache than the threshold index (<NUM>), the corresponding content is deemed as 'semi-popular' and the operation moves to step <NUM> wherein the content-request is re-directed, for example by the second LRU filtering/routing service serving the secondary cache server (cache <NUM>) , to the Origin server (<NUM>).

Typical examples of such form factors include laptops, smart phones, small form factor personal computers, personal digital assistants, and so on.

The instructions, media for conveying such instructions, computing resources for executing them, and other structures for supporting such computing resources are means for providing the functions described above.

Claim 1:
A method for multi-level assessment of content popularity to optimize caching, comprising:
re-directing (<NUM>) a first cache-miss request, associated with a first cache server, for a content identifier in a first semi-popular portion of a first meta-cache comprising a plurality of last-requested content identifiers, to a second cache server in response to determining that the content identifier is not present in the first semi-popular portion of the first meta-cache; and
re-directing (<NUM>) a second cache-miss request associated with the second cache server, for the content identifier in a second semi-popular portion of a second meta-cache, comprising a plurality of last-requested content identifiers, to an origin server (<NUM>) hosting a content associated with the content identifier in response to determining that the content identifier is not present in the second semi-popular portion of the second meta-cache, the second cache-miss request having been issued consequent to the re-directing (<NUM>) of the first cache-miss request,
the method further comprising specifying a first threshold parameter, for partitioning the first meta-cache into a first popular portion and the first semi-popular portion, and a second threshold parameter for partitioning the second meta-cache into a second popular portion and the second semi-popular portion, wherein the first meta-cache is communicatively coupled to the first cache server and the second meta-cache is communicatively coupled to the second cache server.