Estimating cache size for cache routers in information centric networks

Patent metadata

Field	Value
Publication number	US-10069929-B2
Application number	US-201615065520-A
Country	US
Kind code	B2
Filing date	Mar 9, 2016
Priority date	Jun 4, 2015
Publication date	Sep 4, 2018
Grant date	Sep 4, 2018

Abstract

A technique for estimating cache size for cache routers in information centric networks (ICNs) is disclosed. In an example, an average rate of incoming requests and a probability of occurrence of each request at a cache router in a predefined time interval is determined. Further, a relation between cache hit and cache miss with and without replacement is derived based on the probability of occurrence of each request. Furthermore, an entropy of the requests is computed based on the probability of occurrence of each request. Moreover, a diversity index of the requests is calculated based on the entropy and the average rate of the requests. A cache size for the cache router is then estimated based on a user defined probability of cache hit, the average rate of the requests, the diversity index of the requests and the relation between the cache hit and cache miss with and without replacement.

First claim

What is claimed is:

1. A processor-implemented method comprising:
determining, by one or more hardware processors, an average rate of incoming requests and a probability of occurrence of each of the incoming requests at a cache router in a predefined time interval;
deriving, by the one or more hardware processors, a relation between a cache hit, cache miss with replacement and cache miss without replacement in the predefined time interval based on the probability of occurrence of each of the incoming requests;
computing, by the one or more hardware processors, an entropy of the requests based on the probability of occurrence of each of the requests in the predefined time interval;
calculating, by the one or more hardware processors, a diversity index of the requests based on the entropy of the requests and the average rate of the requests;
estimating, by the one or more hardware processors, a cache size for the cache router based on a user defined probability of cache hit, the average rate of the requests, the diversity index and the relation between the cache hit, cache miss with replacement and cache miss without replacement; and
adjusting, by the one or more hardware processors, the cache size of the cache router depending on a pattern of a new incoming request and the user defined probability of cache hit.

2. The method of claim 1 , wherein the cache hit is a function of an available cache size, statistical nature of the requests, and content that is cached in the cache router.

3. The method of claim 1 , wherein the diversity index of the requests ranges between 0 and 1, wherein the diversity index of 0 indicates that the requests at the cache router are same and the diversity index of 1 indicates that the requests at the cache router are different.

4. The method of claim 1 , wherein the cache size for the cache router is estimated based on a rate of arrival of requests for existing content in the cache router, a rate of arrival of requests for non-existing content in the cache router with replacement, a minimum cache size required for the cache router, an average size of content associated with the requests at the cache router, a probability of the cache hit, a probability of the cache miss with replacement, a probability of the cache miss without replacement, the diversity index of the requests and the average rate of the requests.

5. The method of claim 1 , wherein the estimated cache size of the cache router supports the cache hit for the requests and a cache hit for new requests with replacement.

6. A cache router in an information centric network, comprising:
at least one processor; and
a memory and a cache communicatively coupled to the at least processor, wherein the memory comprises a cache size estimation module to:
determine an average rate of incoming requests and a probability of occurrence of each of the incoming requests in a predefined time interval;
derive a relation between a cache hit, cache miss with replacement and cache miss without replacement based on the probability of occurrence of each of the requests;
compute an entropy of the requests based on the probability of occurrence of each of the requests in the predefined time interval;
calculate a diversity index of the requests based on the entropy of the requests and the average rate of the requests;
estimate a cache size of the cache based on a user defined probability of cache hit, the average rate of the requests, the diversity index and the relation between the cache hit, cache miss with replacement and cache miss without replacement; and
adjust the cache size of the cache router depending on a pattern of a new incoming request and the user defined probability of cache hit.

7. The cache router of claim 6 , wherein the cache hit is a function of an available cache size, statistical nature of the requests, and content that is cached in the cache.

8. The cache router of claim 6 , wherein the diversity index of the requests ranges between 0 and 1, wherein the diversity index of 0 indicates that the requests are same and the diversity index of 1 indicates that all the requests are different.

9. The cache router of claim 6 , wherein the cache size estimation module estimates the cache size for the cache based on a rate of arrival of requests for existing content in the cache, a rate of arrival of requests for non-existing content in the cache with replacement, a minimum cache size required for the cache, an average size of content associated with requests, a probability of the cache hit, a probability of the cache miss with replacement, a probability of the cache miss without replacement, the diversity index of the requests and the average rate of the requests.

10. The cache router of claim 6 , wherein the estimated cache size of the cache supports the cache hit for the requests and a cache hit for new requests with replacement.

11. A non-transitory computer readable medium embodying a program executable in a computing device, said program comprising:
a program code for determining an average rate of incoming requests and a probability of occurrence of each of the incoming requests at a cache router in a predefined time interval;
a program code for deriving a relation between a cache hit, cache miss with replacement and cache miss without replacement in the predefined time interval based on the probability of occurrence of each of the incoming requests;
a program code for computing an entropy of the requests based on the probability of occurrence of each of the requests in the predefined time interval;
a program code for calculating a diversity index of the requests based on the entropy of the requests and the average rate of the requests;
a program code for estimating a cache size for the cache router based on a user defined probability of cache hit, the average rate of the requests, the diversity index and the relation between the cache hit, cache miss with replacement and cache miss without replacement; and
a program code for adjusting the cache size of the cache router depending on a pattern of a new incoming request and the user defined probability of cache hit.

Assignees

• Tata Consultancy Services Ltd

Inventors

• Panigrahi Bighnaraj
• Shailendra Samar
• Rath Hemant Kumar
• Simha Anantha

Classifications

• G06F2212/154

  Networked environment · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F12/0813

  with a network or matrix configuration · CPC title

• G06F2212/314

  In storage network, e.g. network attached cache · CPC title

• G06F2212/601

  Reconfiguration of cache memory · CPC title