Method and system for distributed optimal caching of content over a network

Patent metadata

Field	Value
Publication number	US-10291474-B2
Application number	US-201615357241-A
Country	US
Kind code	B2
Filing date	Nov 21, 2016
Priority date	Jan 15, 2016
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

A method and system is provided for distributed optimal caching for information centric networking. The system and method disclosed herein enables each router/node in the network to make an independent decision to solve the optimization problem based upon a cost feedback from its neighbors. Content is received by a first router which determines if it should store the content in its cache based on a Characterizing Metrics (CM) value or send it to a neighbor router j, where the neighbor router j is selected based on a transaction cost determination. The node j on receiving the content shared with itself again performs similar computation to determine if the content should be stored in its cache. The method is performed iteratively for optimal distributed caching.

First claim

What is claimed is:

1. A processor-implemented method for distributed optimal caching of data in a network architecture; said method comprising:
receiving data from a source at a first router, wherein a caching policy is implemented on the first router;
computing a first characterizing metrics (CM) value for the received data using the caching policy, wherein the first CM value is used to determine whether the data can be stored in the cache of the first router;
storing the received data in a cache of the first router when first CM value is higher than a CM value of a previously cached data stored in the cache of the first router:
storing the received data in the cache of a neighbor router when the first CM value is less than a CM value of previously cached data stored in the cache of the first router, wherein storing the received data in the cache of the neighbor router comprises
selecting from a plurality of neighbor routers, the neighbor router with a least transaction cost,
computing a second CM value for the received data to be stored at the neighbor router using the caching policy, wherein the second CM value is used to determine whether the data can be stored at the neighbor router, and
storing the received data at the cache of the neighbor router when the second CM value is greater than a CM value of the data previously stored in the cache of the neighbor router,

wherein the transaction cost is determined such that the first router shares q n data with the neighbor router, the cost to the first router of sharing associated with the neighbor router is a value p j such that the total cost of sharing q n data is (p j ×q n ), wherein p j is a function of importance of the data cached at a router and the cache filling rate.

2. The method according to claim 1 , further comprising providing by the neighbor router, a shareable cache to store the received data wherein the shareable cache is a predetermined portion of the total cache of the neighbor router.

3. The method according to claim 1 wherein the method is used for a plurality of caching problems including Web Caching and mobile ad hoc network (MANET).

4. The method according to claim 1 , wherein the caching policy is Universal Caching (UC) policy and the network architecture is information centric networking (ICN) architecture and wherein a cache list of an ICN manager is updated by the either first router or the neighbor router when the data is stored in the cache of the first router or the neighbor router respectively.

5. The method according to claim 1 further comprising updating the value of p j and the transaction cost when the received data is stored in the cache of the neighbor router, wherein the value of p j is updated based on the received data being stored in the cache of the neighbor router.

6. The method according to claim 1 further comprising iteratively performing the steps of claim 1 based on a predetermined parameter wherein the predetermined parameter is defined by a user.

7. A system for optimal caching of data in a Network architecture; said system comprising at least one source and a plurality of clusters wherein the plurality of clusters comprise a plurality of caching devices communicatively coupled with each other, wherein the plurality of caching devices are a plurality of routers configured to perform operations comprising:
receiving data from a source at a first router of the plurality of routers, wherein a caching policy is implemented on the first router;
computing a first Characterizing metrics (CM) value for the received data using the caching policy, wherein the first CM value is used to determine whether the data can be stored in the cache of the first router;
storing the data in a cache of the first router when first CM value of the data is higher than a CM value of a previously cached data stored in the cache of the first router;
storing the data in the cache of a neighbor router when the first CM value is less than a CM value of previously cached data stored in the cache of the first router, wherein storing the data in the cache of the neighbor router comprises
selecting from a plurality of neighbor routers, the neighbor router with a least transaction cost,
computing a second CM value for the data to be stored at the neighbor router using the caching policy, wherein the second CM value is used to determine whether the data can be stored at the neighbor router, and
storing the data at the cache of the neighbor router when the second CM value is greater than a CM value of the data previously stored in the cache of the neighbor router,
wherein the transaction cost is determined such that the first router shares q n data with the neighbor router, the cost to the first router of sharing associated with the neighbor router is a value p j such that the total cost of sharing q n data is (p j ×q n ), wherein p j is a function of importance of the data cached at a router and the cache filling rate.

8. The system according to claim 7 , wherein the neighbor router is further configured to provide a shareable cache to store the received data, wherein the shareable cache is a predetermined portion of the total cache of the neighbor router.

9. The system according to claim 7 , wherein the caching policy is a Universal Caching (UC) policy and the network architecture is an information centric networking (ICN) architecture and wherein a cache list of an ICN manager is updated by the first router or the neighbor router when the data is stored in the cache of the first router or the neighbor router respectively.

10. The system according to claim 7 , wherein the plurality of routers are further configured to update the value of p j and the transaction cost when the received data is stored in the cache of the neighbor router, wherein the value of p j is updated based on the received data being stored in the cache of the neighbor router.

11. A non-transitory computer readable medium comprising thereon instruction which when executed by a possessor on a system, cause the processor to perform a method comprising:
receiving a data from a source at a first router, wherein a caching policy is implemented on the first router;
computing a first characterizing metrics (CM) value for the received data using the caching policy, wherein the first CM value is used to determine whether the data can be stored in the cache of the first router;
storing the received data in a cache of the first router when first CM value is higher than a CM value of a previously cached data stored in the cache of the first router;
storing the received data in the cache of a neighbor router when the first CM value is less than a CM value of previously cached data stored in the cache of the first router, wherein storing the received data in the cache of the neighbor router comprises
selecting from a plurality of neighbor routers, the neighbor router with a least transaction cost,
computing a second CM value for the received data to be stored at the neighbor router using the caching policy, wherein the second CM value is used to determine whether the data can be stored at the neighbor router, and
storing the received data at the cache of the neighbor router when the second CM value is greater than a CM value of the data previously stored in the cache of the neighbor router,

wherein the transaction cost is determined such that the first router shares q n data with the neighbor router, the cost to the first router of sharing associated with the neighbor router is a value p j such that the total cost of sharing q n data is (p j ×q n ), wherein p j is a function of importance of the data cached at a router and the cache filling ra

Assignees

• Tata Consultancy Services Ltd

Inventors

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

Classifications

• H04L67/2842

  Electricity · mapped topic

• H04L41/0893 Primary

  Assignment of logical groups to network elements · CPC title

• H04L45/124

  using a combination of metrics · CPC title

• H04L67/1097 Primary

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L41/04

  Network management architectures or arrangements · CPC title