Efficient and flexible load-balancing for clusters of caches under latency constraint

Patent metadata

Field	Value
Publication number	US-11470176-B2
Application number	US-201916261462-A
Country	US
Kind code	B2
Filing date	Jan 29, 2019
Priority date	Jan 29, 2019
Publication date	Oct 11, 2022
Grant date	Oct 11, 2022

Abstract

The present technology provides a system, method and computer readable medium for steering a content request among plurality of cache servers based on multi-level assessment of content popularity. In some embodiments a three levels of popularity may be determined comprising popular, semi-popular and unpopular designations for the queried content. The processing of the query and delivery of the requested content depends on the aforementioned popularity level designation and comprises a acceptance of the query at the edge cache server to which the query was originally directed, rejection of the query and re-direction to a second edge cache server or redirection of the query to origin server to thereby deliver the requested content. The proposed technology results in higher hit ratio for edge cache clusters by steering requests for semi-popular content to one or more additional cache servers while forwarding request for unpopular content to origin server.

First claim

The invention claimed is:

1. A method comprising:
receiving, at a first router including a first meta-cache, a content request containing a content-identifier for requested content;
redirecting the content request to an origin server, in response to determining that the content identifier is not present in the first meta-cache;
serving the requested content from a first content cache associated with the first meta-cache, in response to at least the content identifier is present in the first meta- cache at an index position above a first threshold index value;
redirecting the content request to a second router including a second meta-cache, in response to at least determining that the content identifier is present in the first meta-cache at an index position below the first threshold index value;
in response to receiving the redirected content request at the second router:
directly serving the requested content from a second content cache associated with the second meta-cache, in response to at least the indexed position of the content identifier in the second meta-cache being above a second threshold index value;
redirecting the content request to the origin server, in response to determining that the content identifier in the second meta-cache is below the second threshold index value.

2. The method of claim 1 , further comprising:
proxy serving the requested content from the first cache on behalf of the origin server in response to the content identifier being at an index position above the first threshold index value and the requested content not present on the first content cache.

3. The method of claim 1 , further comprising:
adding the requested content to the first cache in response to the content identifier being at an index position above the first threshold index value and the requested content not present on the first content cache.

4. The method of claim 1 , further comprising:
in response to receiving the redirected content request at the second router:
proxy serving the requested content from the second content cache on behalf of the origin server in response to the content identifier being at an index position above the second threshold index value and the requested content not present on the second content cache.

5. The method of claim 1 , further comprising:
in response to receiving the redirected content request at the second router:
adding the requested content to the second content cache in response to the requested content being at an index position above the second threshold index value and requested content not present on the second content cache.

6. The method of claim 1 , further comprising:
inserting the content identifier at the top of the first meta-cache in response to determining that the content identifier is not present in the first meta-cache, and/or
inserting the content identifier at the top of the second meta-cache in response to determining that the content identifier is not present in the second meta-cache.

7. The method of claim 1 , further comprising tuning a value of the first threshold index value using a Proportional-Integral (PI) controller, wherein the tuned value adjusts a tradeoff between a cache hit rate and one or more network performance metrics.

8. A non-transitory computer readable media storing instructions which when executed by a processor cause a system to perform operations comprising:
receiving, at a first router including a first meta-cache, a content request containing a content-identifier for requested content;
redirecting the content request to an origin server, in response to determining that the content identifier is not present in the first meta-cache;
serving the requested content from a first content cache associated with the first meta-cache, in response to at least the content identifier is present in the first meta-cache at an index position above a first threshold index value;
redirecting the content request to a second router including a second meta-cache, in response to at least determining that the content identifier is present in the first meta-cache at an index position below the first threshold index value;
in response to receiving the redirected content request at the second router:
directly serving the requested content from a second content cache associated with the second meta-cache, in response to at least the indexed position of the content identifier in the second meta-cache being above a second threshold index value;
redirecting the content request to the origin server, in response to determining that the content identifier in the second meta-cache is below the second threshold index value.

9. The non-transitory computer readable media of claim 8 , the operations further comprising:
proxy serving the requested content from the first cache on behalf of the origin server in response to the content identifier being at an index position above the first threshold index value and the requested content not present on the first content cache.

10. The non-transitory computer readable media of claim 8 , the operations further comprising:
adding the requested content to the first cache in response to the content identifier being at an index position above the first threshold index value and the requested content not present on the first content cache.

11. The non-transitory computer readable media of claim 8 , the operations further comprising:
in response to receiving the redirected content request at the second router:
proxy serving the requested content from the second content cache on behalf of the origin server in response to the content identifier being at an index position above the second threshold index value and the requested content not present on the second content cache.

12. The non-transitory computer readable media of claim 8 , the operations further comprising:
in response to receiving the redirected content request at the second router:
adding the requested content to the second content cache in response to the requested content being at an index position above the second threshold index value and requested content not present on the second content cache.

13. The non-transitory computer readable media of claim 8 , the operations further comprising:
inserting the content identifier at the top of the first meta-cache in response to determining that the content identifier is not present in the first meta-cache, and/or inserting the content identifier at the top of the second meta-cache in response to determining that the content identifier is not present in the second meta-cache.

14. The non-transitory computer readable media of claim 8 , the operations further comprising tuning a value of the first threshold index value using a Proportional-Integral (PI) controller, wherein the tuned value adjusts a tradeoff between a cache hit rate and one or more network performance metrics.

15. A system, comprising:
a processor; and
a memory storing instructions programmed to cooperate with the processor to cause the system to perform operations comprising:
receiving, at a first router including a first meta-cache, a content request containing a content-identifier for requested content;
redirecting the content request to an origin server, in response to determining that the content identifier is not present in the first meta-cache;
serving the requested content from a first content cache associated with the first meta-cache, in response to at least the content identifier is present in the first meta-cache at an index position above a first threshold index value;
redirecting the content requ

Assignees

• Cisco Tech Inc

Inventors

• Enguehard Marcel Paul Sosthène
• Desmouceaux Yoann
• Pfister Pierre
• Townsley William Mark
• Vyncke Eric

Classifications

• H04L67/568 Primary

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title

• G06F2212/464

  Multimedia object, e.g. image, video · CPC title

• H04L67/563

  Data redirection of data network streams · CPC title

• H04N21/4331

  Caching operations, e.g. of an advertisement for later insertion during playback · CPC title

• H04N21/47202

  for requesting content on demand, e.g. video on demand · CPC title