Note: Descriptions are shown in the official language in which they were submitted.
CA 03126708 2021-07-13
WO 2020/160017
PCT/US2020/015452
EFFICIENT AND FLEXIBLE: LOAD-BALANCING FOR CLUSTERS
OF CACHES UNDER L,ATENCY CONSTRAINT
CROSS-REFERENCE TO RELATED APPLICATION
[0001] This
application claims the benefit of, and priority to, U.S. Non-Provisional
Patent
Application No. 16/261,462, filed on January 29, 2019, entitled "EFFICIENT AND
FLEXIBLE
LOAD-BALANCING FOR CLUS FERS OF CACHES UNDER LATENCY CONSTRAINT".
TECHNICAL FIELD
[0002] The present technology pertains to systems and methods for implementing
in-network caching
system. More specifically it is directed to reducing latency and network load
in content delivery
network by increasing the hit-ratio for clusters of in-network caches.
BACKGROUND
[0003] Internet traffic related to Video-on-Demand (VoD) and linear video
streaming services is
projected to approximately reach 74 TB/s by the year 2021, representing 82% 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.
BRIEF DESCRIPTION OF THE DRAWINGS
1
Date Recue/Date Received 2023-05-18
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
[0004] In order to describe the manner in which the above-recited and other
advantages and
features of the disclosure can be obtained, a more particular description of
the principles briefly
described above will be rendered by reference to specific embodiments thereof
which are
illustrated in the appended drawings. Understanding that these drawings depict
only exemplary
embodiments of the disclosure and are not therefore to be considered to be
limiting of its scope,
the principles herein are described and explained with additional specificity
and detail through the
use of the accompanying drawings in which:
[0005] Fig. 1 illustrates a modified IPv6 address format comprising a network
locator portion and
a content identifier portion, in accordance to some embodiments of the present
technology.
[0006] Fig. 2 illustrate a content delivery system with improved cache server
hit rate, in
accordance to some embodiments of the present technology.
[0007] Fig. 3 illustrate a content delivery system with improved cache server
hit rate, in
accordance to some embodiments of the present technology.
[0008] Fig. 4 illustrates a PI-controller used for optimizing a popularity-
based filtering of content
requests in a content delivery network, in accordance to some embodiments of
the present
technology.
[0009] Fig. 5 illustrates a flow diagram for computing a popularity-based
filtering criteria as a
function of acceptance probability output of a Yaksha derived controller, in
accordance to some
embodiments of the present technology.
[0010] Fig. 6 illustrates an example network device in accordance to some
embodiments of the
present technology.
100111 Fig. 7 illustrates an example architecture of a computing device, in
accordance to some
embodiments of the present technology.
[0012] Fig. 8 illustrates a flowchart for an example content-request filtering
process, in accordance
to some embodiments of the present technology.
DESCRIPTION OF EXAMPLE EMBODIMENTS
[0013] 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
2
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
purposes only. A person skilled in the relevant art will recognize that other
components and
configurations may be used without parting from the spirit and scope of the
disclosure. 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.
[0014] Reference to "one embodiment" or "an embodiment" means that a
particular feature,
structure, or characteristic described in connection with the embodiment is
included in at least one
embodiment of the disclosure. The appearances of the phrase "in one
embodiment" in various
places in the specification are not necessarily all referring to the same
embodiment, nor are separate
or alternative embodiments mutually exclusive of other embodiments. Moreover,
various features
are described which may be exhibited by some embodiments and not by others.
[0015] The terms used in this specification generally have their ordinary
meanings in the art,
within the context of the disclosure, and in the specific context where each
term is used.
Alternative language and synonyms may be used for any one or more of the terms
discussed herein,
and no special significance should be placed upon whether or not a term is
elaborated or discussed
herein. In some cases, synonyms for certain terms are provided. A recital of
one or more synonyms
does not exclude the use of other synonyms. The use of examples anywhere in
this specification
including examples of any terms discussed herein is illustrative only, and is
not intended to further
limit the scope and meaning of the disclosure or of any example term.
Likewise, the disclosure is
not limited to various embodiments given in this specification.
[0016] Without intent to limit the scope of the disclosure, examples of
instruments, apparatus,
methods and their related results according to the embodiments of the present
disclosure are given
below. 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 disclosure. Unless otherwise defined,
technical and
scientific terms used herein have the meaning as commonly understood by one of
ordinary skill in
the art to which this disclosure pertains. In the case of conflict, the
present document, including
definitions will control.
3
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
[0017] Additional features and advantages of the disclosure will be set forth
in the description
which follows, and in part will be obvious from the description, or can be
learned by practice of
the herein disclosed principles. The features and advantages of the disclosure
can be realized and
obtained by means of the instruments and combinations particularly pointed out
in the appended
claims. These and other features of the disclosure will become more fully
apparent from the
following description and appended claims, or can be learned by the practice
of the principles set
forth herein.
OVERVI __ IW
[0018] 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.
[0019] 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.
[0020] 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
4
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
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.
100211 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.
100221 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.
DETAILED DESCRIPTION
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
100231 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.
100241 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.
100251 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
3. 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.
6
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
100261 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.
[0027] 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 1P-based networks. Accordingly,
each video segment
may be matched with a unique network identifier, using, for example, a 64-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. 1, an example
of a modified IPv6
address 100 comprises a first 64 bits portion 104 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 lPv6 address 100 further comprises second a 64-bits portion
106 that constitute
content metadata and acts as a content identifier.
[0028] In accordance to some embodiments of the present technology, chunk-
level content
addressing as part of the layer 3 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"
7
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
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.
100291 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.
100301 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, 6 LB load balancing protocol) to
improve performance.
8
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
For example, in some embodiments of the disclosed technology,Pv6 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.
3.
[0031] Fig. 2 illustrates an operation of an example content delivery network
(CDN) 200, in
accordance with some embodiments of the present technology. In the example CDN
network 200
content routers 202 and 204 comprise a Last Recently Used (LRU) filter
components 206 and 208,
respectively. The LRU filter 206 comprises a meta-cache 210 of size Cl with an
associated
(popularity) threshold parameter 211 and the LRU filters 208 comprises a meta-
cache 212 of size
Cl with an associated threshold parameter 213. LRU filters 206 and 208 control
and filter access
to the origin server 216 and the cache server cluster comprising of cache
server 217 and 218. 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.
[0032] Referring back to Fig. 2, an operation of the example CDN 200, upon
receipt of a content
request, is illustrated in accordance with some embodiments, by flow lines
216, 218 and 220. Flow
line 216 corresponds to a scenario wherein the content identifier (217) in the
incoming request
packet is found in the meta-cache 210 of the LRU filter 206, and its
corresponding index value is
smaller than the threshold index value (i.e., its position is above the
threshold index 211 which
corresponds to the popular portion of the meta-cache 210). Accordingly, LRU
filter 206 moves the
corresponding content identifier to the top of the meta-cache 210 and the
query is accepted by the
corresponding cache server (i.e., the query is served by the edge server 217.)
In case of a cache
miss at 217, the requested (popular) content is proxied from origin server 216
and a local copy is
saved on the cache server 217.
9
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
[0033] 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 210 and 212 in Fig. 2, 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 210 and 212 correspond to an
ascending order of index
value arrangement.
[0034] Conversely, flow line 218 corresponds to a scenario wherein the
requested content
identifier is not found in the meta-cache 210 of the LRU filter 206 (i.e.,
unpopular content). As
such, LRU filter 206 adds/inserts the missing content Identifier at the top of
meta-cache 210 (which
causes the removal of the last content identifier in the meta-cache if it is
full), andthe query is
refused (i.e. the request is directly forwarded to the origin server 216.)
[0035] 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 200
of Fig. 2 this is illustrated by flow line 220 which corresponds to a scenario
wherein the requested
content identifier, embedded in layer 3 address portion of the incoming
content request packet,
corresponds to a content identifier (221), which is found in the meta-cache
210 of LRU 206, at a
position with a greater index value than the threshold index 211 (i.e., its
position is below the
threshold index 211 which corresponds to the semi-popular portion of the meta-
cache 210). For
semi-popular content, a cache miss at the initial/first receiving cache server
(cache server 217),
will cause the LRU filter 206 or the content router 202 to re-route the
request to a second pseudo-
randomly-selected cache server (218) through its associated content router 204
(for example by
using a Segment Routing Load Balancing forwarding protocol). Upon receipt of
the re-directed
content request, LRU filter 208 moves the corresponding content identifier
(221) to the top of the
meta-cache 212. If the second LRU filter (208) serving the second pseudo-
randomly chosen cache
server (218) also does not have the requested content (corresponding to
content identifier 221), or
if the second LRU filter (208) serving the second pseudo-randomly chosen cache
server (218) does
have the requested content but at a position above the threshold parameter 213
(i.e., in the semi-
popular portion of the meta-cache 212 , the query is forwarded to the Origin
server 216. If the re-
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
directed content is deemed as popular according to the LRU filter 212 of the
second edge cache
server 218, the request is accepted locally on the second edge cache server
218 and, if locally
unavailable, the content is proxied from the origin server 216.
[0036] 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)
[0037] 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, lPv6 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.
[0038] Fig. 3 illustrates an example of Segment Routing implementation 300 for
a popularity-
based filtering of content request and response traffic in accordance to some
embodiments of the
present technology. In the example implementation 300, a dispatcher unit
(302), which may be
located near the client 304 (e.g. in the clients network stack, or set-top
box) is deployed to inserts
a Segment Routing header (comprising a Segment Identifier List 306) into a
content request. packet
to facilitated a request filtering process upstream. For example, when the
client 304 issues a new-
connection packet (e.g. TCP SYN), the dispatcher 302 inserts a Segment
identifier (SID) list 306
into Segment Routing Header of a request packet. In the example embodiment
illustrated in Fig.
3, SID list 306 comprises three entries, with the first two entries
corresponding to segment
identifiers I and 3, respectively identifying two pseudo-randomly-chosen cache
servers cache
server I and cache server 3. The last entry in SID list 306 corresponds to a
segment identifier for
the origin server 308, For the purpose of clarification, when Segment Routing
is implemented with
11
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
an IPv6 forwarding plane, an SID list may be interchangeably referred to as an
SRv6 (Segment
Routing with IPv6 forwarding) list.
[0039] The accepting server (which may be any of the cache or origin server),
upon acceptance of
the new-connection packet from the client 304, inserts its network or segment
address as metadata
into the response packet back to the client. The dispatcher (302) 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 306 (namely, cache server
1, cache server 3 and
origin server.)
[0040] 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.
[0041] With reference to the example in Fig. 3, LRU filter/content router 310,
311 and 312 are
deployed for the purpose of filtering access to and managing a cache-miss
response of cache
servers 1, 2 and 3, 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. 2 and
3 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.
[0042] Referring back to Fig. 3, the incoming (new-connection) content request
313 destined for
cache server 1 is received at the corresponding LRU filter/content router 310.
If the requested
content identifier (extracted from the content request 313) is found in the
popular portion of the
meta-cache in the LRU filter/content router 310, the requested content is
deemed as 'popular'.
Accordingly, the content request is accepted at cache server 1 (the initial
receiving cache) and the
corresponding connection 313 is terminated there at. As such, the request
packet is forwarded to
the local stack of cache server I without visitine further segments. If the
requested 'popular'
12
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
content is not locally available on cache server 1, the request is proxied to
the origin server 308
and the content is inserted into the cache server I 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 313, Cache server 1 will dispatch a response packet
back to the client with
its segment identifier (1), indicated by reference 314 in Fig. 3.
[0043] However, if the requested content identifier (extracted from the
content request packet) is
found in the semi-popular portion of the meta-cache (items 210 and 212 in Fig.
2) in the LRU
filter/router 310, the requested content is deemed as `semi-popular'.
Accordingly, LRU filter/
router 310 triggers a retry, corresponding to connection 316 in Fig. 3
(connection 220 in Fig. 2)
and forwards the request to the next segment identifier entry (i.e., SED 3) in
the SRv6 list 306
which corresponds to the second pseudo-randomly selected cache server (cache
server 3). This
will require the LRU filter/router 31.0 (associated with cache server 1) to
route/forward the content
request to a corresponding LRU filter/router 312 associated with cache server
3. If the requested
"serni-popular' content is is deemed popular by the LAU filter 312, the re-
tried/re-directed content
request is accepted at cache server 3 (the second receiving cache) and the
corresponding
connection 316 is terminated there. As such, the request packet is forwarded
to the local stack of
cache server 3 without visiting further segments and the requested `semi-
popular' content is served
directly at cache server 3. After terminating the connection 316, the
accepting server (cache server
3) will dispatch a response packet back to the client into which it inserts
its own segment identifier
(3), indicated by reference 317 in Fig. 3. However, If the requested 'semi-
popular' content is not
found nor deemed popular by the LRU filter 312 serving cache server 3, the
connection request
316 is refused and the request is re-directed, across connection 318, to the
origin server 308 (the
last segment specified in the SR.v6 list 306). The origin server 308 will
accept the request and
terminate the corresponding connection 318. As such, the request packet is
forwarded to the local
stack of origin server 308 and the requested 'semi-popular' content is served
directly at origin
server 308, After terminating the connection. 318, the Accepting server
(origin server 308) will
dispatch a response packet back to the client into which it inserts its own
segment identifier
(ORIGIN), indicated by reference 319 in Fig. 3..
[0044] Finally, if the requested content identifier, extracted from the client
request packet destined
towards the initial receiving cache (cache server 1), is not found anywhere in
the meta-cache
(illustrated as items 210 and 212 in Fig. 2) of the corresponding LRU
filter/router 310, the
13
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
requested content is deemed as 'unpopular'. Accordingly, if the requested
'unpopular' content is
not locally available on cache server 1, the missing content identifier is
inserted at the top of the
meta-cache associated with LRU filter/router 310, and the request is re-
directed, across connection
320, to the Origin server 308. Queries directed to the origin server 308 are
terminated and
forwarded to the local stack. After terminating the connection 320, the
accepting server (origin
server 308) will dispatch a response packet back to the client into which it
inserts its own segnent
identifier (ORIGIN), indicated by reference 321 in Fig. 3,
[0045] 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.
[0046] In accordance to some embodiments of the present technology, a
Proportional Integral (PI)
controller may be used to tune the parameters of the LRLI filter. For example,
a P1 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
dine, 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
cad ie access.
[0047] Fig. 4 illustrates an example implementation 400 wherein a content
router 401 working in
conjunction with an LRU filter 402 is used to filter and control access to a
cache server 403. The
LRU filter 402 further comprises a meta-cache 404 of size Ci for storing
content identifiers and a
threshold parameter k associated with identification of popular/semi-
popular/unpopular content_
14
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
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
400, a response time, 'St', of a cache server 403, may be measured and
provided as input to a PI
controller 406. The P1-controller 406, based on the input response time,
optimally tunes the level
of the threshold parameter k in the meta-cache 404 of LRU filter 402. In this
way a PI-controller
may be used to tune and optimize operation of an LItti filter which ultimately
improves edge
caching performance in networks.
[048] 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 characteri sti cs.
[00491 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 (LRL) popularity
threshold.
10050] lithe request pattern follows a Poisson arrival and the popularity
distribution q(r) is known,
in accordance to some embodiments, Chefs 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 (1.1), wherein k
represent the content
popularity threshold and p(k), as defined by equation 1.2, represents the
probability of accepting
a request as a function of the content popularity threshold, k. The parameter
t, in equation 1.1 and
1.2 corresponds to the root of the equation 1.1.
¨ e-teq(1")) = k
(1.1.)
p(k) .Ig(r)(1. e-teq(0)
(1.2)
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
[0051] The probability function defined by (1.2) 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. 5
wherein a response time `St' of a cache server 502 is used as input into a
Yaksha filter 504. The
output 506 of the Yaksha filter, corresponding to acceptance probability p, is
inverted at 506, 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 (506) may be performed through a
pre-computed
inversion tables for efficiency purpose.
[0052] 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.
[0053] The disclosure now turns to FIGS. 6 and 7, which illustrate example
architectures of
computing an network devices, such as client computers, switches, routers,
controllers, servers,
and so forth
[0054] FIG. 6 illustrates a computing system architecture 600 including
components in electrical
communication with each other using a connection 605, such as a bus. System
600 includes a
processing unit (CPU or processor) 610 and a system connection 605 that
couples various system
components including the system memory 615, such as read only memory (ROM) 620
and random
access memory (RAM) 625, to the processor 610. The system 600 can include a
cache of high-
speed memory connected directly with, in close proximity to, or integrated as
part of the processor
610. The system 600 can copy data from the memory 615 and/or the storage
device 630 to the
cache 612 for quick access by the processor 610. In this way, the cache can
provide a performance
boost that avoids processor 610 delays while waiting for data. These and other
modules can control
or be configured to control the processor 610 to perform various actions.
Other system memory
615 may be available for use as well. The memory 615 can include multiple
different types of
memory with different performance characteristics. The processor 610 can
include any general
purpose processor and a hardware or software service, such as service 1 632,
service 2 634, and
16
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
service 3 636 stored in storage device 630, configured to control the
processor 610 as well as a
special-purpose processor where software instructions are incorporated into
the actual processor
design. The processor 610 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.
[0055] To enable user interaction with the computing device 600, an input
device 645 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 635 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 600. The communications
interface 640 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.
[0056] Storage device 630 is a non-volatile memory and can be a hard disk or
other types of
computer readable media which can store data that are accessible by a
computer, such as magnetic
cassettes, flash memory cards, solid state memory devices, digital versatile
disks, cartridges,
random access memories (RAMs) 625, read only memory (ROM) 620, and hybrids
thereof.
[0057] The storage device 630 can include services 632, 634, 636 for
controlling the processor
610. Other hardware or software modules are contemplated. The storage device
630 can be
connected to the system connection 605. 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 610,
connection 605,
output device 635, and so forth, to carry out the function.
[0058] FIG. 7 illustrates an example network device 700 suitable for
performing switching,
routing, assurance, and other networking operations. Network device 700
includes a central
processing unit (CPU) 704, interfaces 702, and a connection 710 (e.g., a PCI
bus). When acting
under the control of appropriate software or firmware, the CPU 704 is
responsible for executing
packet management, error detection, and/or routing functions. The CPU 704
preferably
accomplishes all these functions under the control of software including an
operating system and
17
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
any appropriate applications software. CPU 704 may include one or more
processors 708, such as
a processor from the INTEL X106 family of microprocessors. In some cases,
processor 708 can
be specially designed hardware for controlling the operations of network
device 700. In some
cases, a memory 706 (e.g., non-volatile RAM, ROM, TCAM, etc.) also forms part
of CPU 704.
However, there are many different ways in which memory could be coupled to the
system. In
some cases, the network device 700 can include a memory and/or storage
hardware, such as
TCAM, separate from CPU 704. Such memory and/or storage hardware can be
coupled with the
network device 700 and its components via, for example, connection 710.
[0059] The interfaces 702 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
700. 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, 3G/4G/5G 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 704 to efficiently perform routing computations, network
diagnostics, security
functions, etc.
[0060] Although the system shown in FIG. 7 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 700.
[0061] Regardless of the network device's configuration, it may employ one or
more memories or
memory modules (including memory 706) configured to store program instructions
for the
18
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
general-purpose network operations and mechanisms for roaming, route
optimization and routing
functions described herein. The program instructions may control the operation
of an operating
system and/or one or more applications, for example. The memory or memories
may also be
configured to store tables such as mobility binding, registration, and
association tables, etc.
Memory 706 could also hold various software containers and virtualized
execution environments
and data.
100621 The network device 700 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 700 via the connection
710, to
exchange data and signals and coordinate various types of operations by the
network device 700,
such as routing, switching, and/or data storage operations, for example.
100631 Fig. 8 illustrates an example process flow 800 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. 8 at step 802
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 (804), 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 806. However if the incoming content-identifier is
present in the meta-
cache (808), the operation moves to step 810 wherein an indexed position of
the content-identifier
in the meta-cache is compared to a threshold index value.
100641 If the indexed position of the incoming content-identifier is higher
(closer to the top) in the
LRU meta-cache than the threshold index (812) the content is deemed as popular
and the operation
19
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
moves to step 814 wherein the associated cache server (Cache 1) is checked for
the requested
content. If the content is present in Cache 1(816), it is served directly
therefrom at step 818. If the
content is not present in Cache 1 (820), the operation moves to step 822
wherein the requested
content is proxied, by Cache 1, from the origin server. The content is then
inserted into Cache 1 at
step 824.
[0065] However, if the indexed position of the incoming content-identifier is
lower (closer to the
bottom) in the meta-cache than the threshold index (826), the corresponding
content is deemed as
'semi-popular' and the operation moves to step 834 wherein the content-request
is re-directed, for
example by a first LRU filtering/routing service serving the first cache
server (cache 1) , to a
second LRU filtering/routing service serving a secondary cache server (Cache
2).
[0066] 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.
[0067] Referring back to the example process flow 800 in Fig. 8, the second
receiving LRU
filtering/routing service serving the secondary cache server (Cache 2), 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 836 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 (838) the content is deemed as popular and the operation moves to step
839 wherein the
associated cache server (Cache 2) is checked for the requested content. If the
content is present in
Cache 2 (840), it is served directly therefrom at step 841. If the content is
not present in Cache 2
(842), the operation moves to step 843 wherein the requested content is
proxied, by Cache 2, from
the origin server. The content is then inserted into Cache 2 at step 844.
V06814lowever if the indexed position of the incoming content-identifier is
lower (closer to the
bottom) in the LRU meta-cache than the threshold index (845), the
corresponding content is
deemed as `semi-popular' and the operation moves to step 846 wherein the
content-request is re-
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
directed, for example by the second LRU filtering/routing service serving the
secondary cache
server (cache 2) , to the Origin server (846).
[0069] In some embodiments the computer-readable storage devices, mediums, and
memories can
include a cable or wireless signal containing a bit stream and the like.
However, when mentioned,
non-transitory computer-readable storage media expressly exclude media such as
energy, carrier
signals, electromagnetic waves, and signals per se.
[0070] Methods according to the above-described examples can be implemented
using computer-
executable instructions that are stored or otherwise available from computer
readable media. Such
instructions can comprise, for example, instructions and data which cause or
otherwise configure
a general purpose computer, special purpose computer, or special purpose
processing device to
perform a certain function or group of functions. Portions of computer
resources used can be
accessible over a network. The computer executable instructions may be, for
example, binaries,
intermediate format instructions such as assembly language, firmware, or
source code. Examples
of computer-readable media that may be used to store instructions, information
used, and/or
information created during methods according to described examples include
magnetic or optical
disks, fl ash memory, USB devices provided with non-volatile memory, networked
storage devices,
and so on.
[0071] Devices implementing methods according to these disclosures can
comprise hardware,
firmware and/or software, and can take any of a variety of form factors.
Typical examples of such
form factors include laptops, smart phones, small form factor personal
computers, personal digital
assistants, and so on. Functionality described herein also can be embodied in
peripherals or add-
in cards. Such functionality can also be implemented on a circuit board among
different chips or
different processes executing in a single device, by way of further example.
[0072] 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 in these disclosures.
[0073] Although a variety of examples and other information was used to
explain aspects within
the scope of the appended claims, no limitation of the claims should be
implied based on particular
features or arrangements in such examples, as one of ordinary skill would be
able to use these
21
CA 03126708 2021-07-13
WO 2020/160017 PCT/US2020/015452
examples to derive a wide variety of implementations. Further and although
some subject matter
may have been described in language specific to examples of structural
features and/or method
steps, it is to be understood that the subject matter defined in the appended
claims is not necessarily
limited to these described features or acts. For example, such functionality
can be distributed
differently or performed in components other than those identified herein.
Rather, the described
features and steps are disclosed as examples of components of systems and
methods within the
scope of the appended claims.
22
