A Cache Content Replacement Scheme For Information PDF
A Cache Content Replacement Scheme For Information PDF
A Cache Content Replacement Scheme For Information PDF
com
ScienceDirect
Procedia Computer Science 89 (2016) 73 – 81
Abstract
Nowadays, Information centric networking has tremendous importance in accessing internet based applications. The increasing rate
of Internet traffic has encouraged to adapt content centric architectures to better serve content provider needs and user demand of
internet based applications. These architectures have built-in network Caches and these properties improves efficiency of content
delivery with high speed and great efficiency. By using Information centric architectures, users need not download content from
content server despite they can easily access data from nearby caches. User requested content is independent of the location of the
data by use of caching approaches and does not rely on storage and transmission methodologies of that content. There has been
many researches going on which is based on caching approaches in the Content centric network. Efficient caching is essential to
reduce delay and to enhance performance of the network. Along with caching, a good cache replacement scheme is also necessary
to decide which content item should reside in the cache and which content should be evicted. So, in this paper, we presented a Cache
content replacement (CCR) scheme for information centric network with evaluation of popularity of the content. Performance of
CCR scheme will be evaluated in provision of cache hit ratio and Cache load.
© 2016 The Authors. Published by Elsevier B.V.
© 2016 The Authors.
Peer-review under Published by Elsevier
responsibility B.V. This iscommittee
of organizing an open access
of article under the
the Twelfth CC BY-NC-ND
International license
Multi-Conference on Information
(http://creativecommons.org/licenses/by-nc-nd/4.0/).
Processing-2016 (IMCIP-2016).
Peer-review under responsibility of organizing committee of the Organizing Committee of IMCIP-2016
Keywords: CN; QoS; CCN; PIT; FIB; CS; LRU.
1. Introduction
About 100 years ago,1 a mathematical foundation was created by Erlang which was used to analyze communication
network based on telecommunication. Again 50 years later since that time,2 a concentric information network comes
into account in the area of network research field which was also called as Information centric network (ICN).27
Information centric network basically a model who focuses more on the content item rather the source of content item
where the content is residing. Centric network means, information requested by the client can easily accessed from
one of the intermediate routers rather than the end server. This network exhibit data centric communication instead
of end to end communication between computers.28 The Routers in the ICN network carry two functionalities: first
caching content data and the second is routing of that content data. ICN supports in cooperation with multicasting,
as well as broadcasting. Today, ICN concept can applied and tested easily on26 Software defined network (SDN),25
Wireless sensor network (WSN), Network Clouds, Wireless mesh network (WMN), Ad hoc Network etc. Now a
days, our world is completely technology dependent. We use the internet for our lot of requirements like education,
1877-0509 © 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
(http://creativecommons.org/licenses/by-nc-nd/4.0/).
Peer-review under responsibility of organizing committee of the Organizing Committee of IMCIP-2016
doi:10.1016/j.procs.2016.06.011
74 Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81
entertainment, knowledge and all other general purpose needs. These internet access based applications includes
Gmail, YouTube, Facebook, Google and other web applications.3 In this scenario of the real world, it is reported
that global internet traffic is increasing rapidly day by day or hour by hour and 70% above people are using internet
toady in most of countries in the world. Many social and media applications like HD quality videos, software, Twitter,
Facebook are used by user in large growth rate. So to cope up with these large amounts of requirements, Information
Centric network has been introduced with many advantages like it does not depend on hop to hop communication.
It exhibits the characteristic of communication which lies in receiver based data access methodology.4, 5 The expected
benefits of the proposed content centric network over traditional end to end internet network are high efficiency, better
scalability with respect to information/bandwidth demand, support of high degree of mobility, high performance in
terms of content delivery guarantee and better robustness/reliability in challenging Communication environment. Many
innovative architectures are proposed in the field in terms of DONA6 , CCN7 , NetInf8, PURSUIT9 and PRISP10 .
There are so many options for making caching in ICN like chunk level caching, packet level caching and object
information level caching. Naming of Contents is done by location independent identifying by using two key
approaches: Two phase approach and one phase approach. In one phase approach routing of content is done natively
in the network, whereas in two phase approach, first mapping is done to the content id locators.13, 22 In node centric
design, Sometimes called host to host communication network, same content data are transmitted repeatedly between
the nodes and that costs wastage of bandwidth, high traffic with excessive delay. ICN comes into account to overcome
these drawbacks of host to host communication network. Figure 1 shows the architecture of Host-to-Host network
design. In Fig. 2 showing below, the content data requested by the client is cached by one of intermediate router
in the path from client to server. So content item is instantaneously directed by the caching router to client. Each
caching router in information centric network maintains three data structure named as: Content store (CS), Pending
information table (PIT) and Forwarding information base (FIB). There are two types of information object packets are
used for establishing the communication: interest packet, which is created by client for getting services or content data
and another one is a data packet.11 Content store uses to cache content and servers as a local cache. The task of FIB in
caching router is mapping of information provided by client for requesting data to the output interfaces. PIT basically
keeps records and tracks of incoming interfaces from the requesting interest message were generated/pending. When
interest message from requesting client arrives at the caching router as shown in Fig. 2, then caching router checks the
extracted information about requests content in its local cache called content store.12 If the operation is hit i.e. content
is matching then it sends that content to the requesting client by using incoming interfaces otherwise caching router
further matches the longest prefix of information object in its FIB table to select appropriate path and data source
Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81 75
for forward interest message further. In this case, if a forwarding entry is found in FIB then caching router record
incoming interface of interest message in its PIT table. Following Fig. 3 shows the whole process of a router in ICN.
Here, orange color denotes interest packet and green color bar denotes data packet.
2. Literature Survey
Cache memory is the fastest memory as compared to primary and secondary memory. It is used to store frequently
referred pages to increase the throughput of the system and with minimum delay.20 In ICN, cache placement and cache
replacement are different terms. Cache placement basically references ‘in what place the content should be placed?’
but Cache replacement defines how the event cache content eviction should take place to achieve a high hit ratio and
minimum latency. There are many researchers have been going on strategies of cache replacement. Some of them are
illustrated below:
In random replacement strategy when a content data are requested by requester node (client) and caching router
find that content in its content store (CS) then that event is called hit event and the content data is immediately sent
to the client by the caching router. When the content is not found in the content store (CS) of the caching router then
the respective data request is sent to the server and in returning of that data from server, caching router selects one of
the content in its CS randomly and replace that content with requests incoming content from the server. The selection
criteria of content which has to be replace is done random. This strategy chooses any one content item in its content
store for making replacement.14 In the analysis of this random replacement strategy, it can be seen that Requirement
for memory is less in this strategy as well as replacement time is also very less because there is no criteria for selection.
Least recently used (LRU) is one of famous and mostly used cache replacement strategy in ICN.18, 19 In Least
recently used strategy when a content data are requested by requester node (client) and caching router finds that content
in its content store (CS) then that event is called hit event and the content data is immediately sent to the client by the
caching router.17, 23 When the content is not found in the content store (CS) of the caching router then the respective
data request is sent to the server and in returning of that data from server, caching router selects one of the content
in its CS on the behalf of recency of usage. Most popular content items will be demanded more in the network so its
usage will be more and recency is directly proportional to the usage. So the item which having less recency will be
76 Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81
selected for replacement by a caching router in its CS.15 LRU replacement strategy gives a high hit ratio because the
most popular content is accessed many times in the modern world scenario. For example, in release of the latest action
movie trailer, the percentage of access and demand of that movie trailer will be very high and if this content is stored
by caching router then it will lead to high hit ratio with as compare to random strategy.
As the name indicates, most recently used strategy is just opposite to least frequently used replacement strategy.16
In Most frequently used (MFU) strategy, when a content data are requested by requester node (client) and caching
router finds that content in its content store (CS) then that event is called hit event and the content data is immediately
sent to the client by the caching router. When the content is not found in the content store (CS) of the caching router
then the respective data request is sent to the server and in returning of that data from server, caching router selects one
of the content in its CS on the behalf of the high value of counter. This high value of counter indicates a large number
of times that particular content item is referred.
3. Proposed Work
By using Information centric architectures, users need not download content from content server despite they can
easily access data from nearby caches. User requested content is independent of the location of that data by use of
caching approaches and does not rely on storage and transmission methodologies of that content. There has been
many researches going to base on caching approaches in the Content centric network. Efficient caching is essential to
reduce delay and to enhance performance of the network. Along with caching, a good cache replacement scheme is
Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81 77
Ci ith content
P(Ci) Popularity of ith content
L P(Ci) Local popularity of ith content
Es P(Ci) Expected Popularity of ith content
L P A(Ci . . . n) Local popularity of all the contents in CS
U P(Ci) Universal Popularity of ith Content in CS
R Rank of the content
n Total number of content in CS
Ci ith content
P(Ci) Popularity of ith content
L P(Ci) Local popularity of ith content
Es P(Ci) Expected Popularity of ith content
L P A(Ci . . . n) Local popularity of all the contents in CS
U P(Ci) Universal Popularity of ith Content
R Rank of the content
U P(C j) Universal Popularity of jth content newly arrived
also necessary to decide which content item should reside in the cache and which content should be evicted. So, in this
paper, we presented a Cache content replacement (CCR) scheme for an information centric network with evaluation of
the popularity of the content. Performance of CCR scheme will be evaluated in provision of cache hit ratio and cache
load. Our work proceeds as follows:
• In this paper, evaluation and calculation of content popularity in universal basis (overall in the network).
• Estimation of local content popularity with respect to the overall demand of that item in locally and universally.
• Selection of content to be replaced in the cache of caching router in relation with estimation of instantaneous hit
rate.
• Performance analysis of the proposed CCR replacement scheme in provision of cache hit ratio and cache load in
comparison with replacement policies mentioned in the literature survey like LRU, MFU, RANDOM, FIFO.
Characteristics of the internet content can be understood simply by Zipf law. This law is used to assign a rank to
each content universally based on the frequency of access request of that content. The rank of each content is calculated
using popularity distribution α which ranges 0.6 to 1.2. For analysis of YouTube related content the value of α lies
greater than 2 (α > 2). As the frequency is inversely proportional to the rank of the content data item means the rank
of content will be higher if the access rate (frequency) of that content will be higher. Below Table 1 represents the list
of symbols used to propose CCR replacement scheme.
Popularity of content item c is defined as with relation of rank R of that content item.
1
P(Ci )α (1)
R∞
1/R ∞
U P(Ci ) = N (2)
∞
n=1 1/n
This value of P(Ci ) is the popularity of i th content item c where R denotes the rank of a content item. This universal
popularity listing is maintained in the cluster head (CH) of the ICN.
In ICN, each caching router estimates local popularity of content which is selected for replacement in addition of
newly arrived content. The requirement of estimation of local popularity is made due to the knowledge of rank listing
of content data in its local cache of caching router. To make efficient replacement decision calculation of the local
78 Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81
popularity of content is essential. A caching router estimates Expected popularity of each content item in its caching
router by using equation 2 as follows:
1 1
L Es P(Ci ) = √ Exp − 2 U P(Ci ) (3)
σ 2π 2σ
By using equation 3, caching router estimates an expected popularity of content item Ci with respect to its universal
popularity. Further, Estimation of Local popularity of all the contents denoted by the L P A(Ci . . . n) which are residing
in a content store of caching router will be carried on by using equation 4.
n
L P A(Ci . . . n) = (L Es P(C(i ), U P(C(i ))
i=1
1
n
1 2
= √ Exp − 2 (U P(Ci )) − L Es P(i )) (4)
(σ 2π)n 2σ
i=1
After the estimation of the local popularity of all the contents in the content store, caching router evaluates the local
popularity L P(Ci ) of each content. This value of L P(Ci ) is calculated by using equation 3 and 4.
Es P(Ci )
L P(Ci ) = (5)
L P A(Ci . . . n)
3.3 Content cache replacement strategy
In Information centric network, when a content data is requested by requester node (client) and caching router find
that content in its content store (CS) then that event is called hit event and the content data is immediately sent to the
client by the caching router. When the content is not found in the content store (CS) of the caching router then the
respective data request is sent to the server and in returning of that data from server, caching router selects one of the
content in its CS on the behalf of lower instantaneous hit rate (Hi ). Instantaneous hit rate keeps track averages of all
the hit rates in previous history of content item.
Hi = δi + σ Hi−1 (6)
In the above equation 6, Hi represents the instantaneous hit rate of content i . the value of δi is 1 in the event of hit
event and 0 in the event of a cache miss. Hi−1 denotes the previous history of hit rate of content i and value of σi
lies between 0 and 1 (0.5 in most of the cases). The higher value of instantaneous hit rate indicates higher recent hit
rate. After estimating the value of instantaneous hit rate, the content which has a lower instantaneous hit rate will be
selected. The local popularity of that selected content will be calculated by equation 5 as follows:
√1 Exp − 1 2 U P(Ci )
σ 2π 2σ
L P(Ci ) =
1 n
√1 Exp − 2σ 2 i=1 (U P(Ci ) − Es P(i ))2
(σ 2π) n
The local popularity defines the rank of content which has a low instantaneous hit rate in the cache of caching router
among all the content items stored in the content store. Next step is for estimation of universal popularity of content
item U P(C j ) by using equation 1 and 2 which is newly arrived for storing in the content store with the replacement
of selected data. After the estimation of universal popularity of newly arrived data and local popularity of content data
in a content store of caching router, Decision of replacement will be done as follows:
• If the difference between universal popularity of newly arrived content U P(C j ) and local popularity of content
L P(Ci ) which is selecting for eviction in a content store is greater than 0 then it indicates that the popularity
of content item which is newly arrived is high as compared to data which is selected for replacement in CS. So,
according to high popularity to achieve high performance the selected data from content store will be replaced by
newly arrived data.
Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81 79
• If the difference between universal popularity of newly arrived content U P(C j ) and local popularity of content
L P(Ci ) which is selecting for eviction is less than 0 then it indicates the popularity of content item which is
newly arrived is low as compare to data which is selected for replacement in CS. So, according to high popularity
to achieve high performance the selected data from content store will not be replaced by newly arrived data and
that data will be directly forward towards the requesting client.
In our implemented Content cache replacement (CCR) Strategy, the replacement is done in the relation of content
popularity and low instantaneous hit rate. By following this strategy, instantaneous hit rate maintains recent content
data hits so that if a content has a lower instantaneous hit rate then it indicates that the content is not popular and due
to that it have less hits.
4. Performance Analysis
In this paper, we presented a Cache content replacement (CCR) scheme for an information centric network with the
evaluation of popularity of the content. Performance of CCR scheme will be evaluated in provision of cache hit ratio
and cache load.
Cache hit ratio will be evaluated by achieving the number of hits for overall request of accessing content from the
requested client. If the request for content item made by the client is found in the content store of a caching rather than
this phenomenon is called cache hit. The increasing number of cache hit leads to high performance of the information
centric network because of less delay and content will be reached for the client before expected time. Cache hit ratio
is directly proportional to the number of times content item found in the content store of caching router.
number of times content found in C S
C(hi ) =
Total no. of request in that caching router
Our implemented CCR replacement strategy makes an efficient decision to making replacement of content based on
instantaneous hit rate and local popularity.
From above Fig. 4 shows that simulation results of comparison for cache hit ratio between proposed CCR strategy
with Random, FIFO, LRU and MRU replacement schemes. It can be clearly seen that cache hit ratio of CCR scheme
is high as compared to other schemes.
A. Cache load
The term cache, load is indicated that how much request is processed by a server or a caching router at any particular
time. Load is the total number of requests for accessing the content data/ items from client to the server. For better
performance of the system, it is necessary that the server or caching router should not be overloaded with incoming
requests for content access. So by taking this point into consideration, Proposed CCR replacement scheme replaces the
content in such a manner that the load on caching router will be very less and eventually it will give high performance
as compared to other replacement strategy in terms of cache load.
From above Fig. 5, it can be cleary shown that by using proposed CCR caching strategy the cache load of caching
router of ICN will be low as compare to Random, FIFO, LRU and MRU strategies.
80 Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81
Fig. 4. Cache Hit Ratio of CCR Replacement Scheme with other Fig. 5. Comparison of Cache Load with CCR Scheme with other
Schemes. Schemes.
5. Conclusions
Information centric network becomes a tremendous research area nowadays. Several research challenges are
addressed in this research are of ICN like caching, security, load balancing, naming, data retrieval, scalability and so
much else. Our main focus on caching replacement strategy and by inspire of this topic in networking field, we studied
several researches regarding caching in ICN. Caching is just storage of content data with aiming of speedily served
future request. In this paper, we presented an overview of various caching replacement approaches in ICN with several
features and regarding issues.This paper gives a simple idea about ‘what to cache’ problem with relation of popularity.
Our proposed CCR scheme will give very high performance in terms of cache hit ratio and cach load with comparison
of LRU, MRU, FIFO and Random strategy. Still, there are so many open issues in caching in current ICN architecture
like maintaining the consistency of content data if anything updating occurs, Synchronization with various caching
routers with respect to the server, reducing redundancy of content data item in various caches and optimization of
cache space to achieve high capacity to store content data item and so much else have to consider to make an effective
and efficient cache mechanism in information centric network. This will lead to bright future of ICN in current internet
access scenarios.
References
[1] Kurose Jim, Information-Centric Networking: The Evolution from Circuits to Packets to Content, Computer Networks, vol. 66, pp. 112–120,
(2014).
[2] Chanda, Abhishek, Cedric Westphal and Dipankar Raychaudhuri, Content Based Traffic Engineering in Software Defined Information
Centric Networks, IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2013 IEEE, (2013).
[3] https://www.surrey.ac.uk/sites/default/files/5G-Network-Architecture-Whitepaper-(Jan-2016).pdf
[4] Davies, Elwyn, et al. Information-Centric Networking: Baseline Scenarios, (2015).
[5] You, Wei, Bertrand Mathieu and Gael Simon, Exploiting End-Users Caching Capacities to Improve Content-Centric Networking Delivery,
P2P, Eighth International Conference on Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2013 IEEE, (2013).
[6] T. Koponen, et al., A Data-Oriented (and beyond) Network Architecture, ACM SIGCOMM Comput. Commun. Rev., vol. 37, no. 4,
pp. 181–192, October (2007).
[7] Content Centric Networking Project. [Online]. Available: http://www.ccnx.org/
[8] NSF Named Data Networking Project. [Online]. Available: http://www.named-data.net/
[9] FP7 PURSUIT project. [Online]. Available: http://www.fp7-pursuit.eu/PursuitWeb/
[10] FP7 PSIRP Project. [Online]. Available: http://www.psirp.org/
Kumari Nidhi Lal and Anoj Kumar / Procedia Computer Science 89 (2016) 73 – 81 81
[11] http://www.cnsm-conf.org/2013/documents/CNSM2013-Keynot2-G-Pavlou.pdf
[12] G. Xylomenos, C. N. Ververidis, V. A. Siris, N. Fotiou, C. Tsilopoulos, X. Vasilakos, K. V. Katsaros and G. C. Polyzos, A Survey of
Information-Centric Networking Research, In Communications Surveys & Tutorials, IEEE, vol. 16, no. 2, pp. 1024–1049, Second Quarter
(2014).
[13] Arianfar, Somaya, Pekka Nikander and Jörg Ott, Packet-level Caching for Information-Centric Networking, ACM SIGCOMM, ReArch
Workshop, (2010).
[14] Gallo, Massimo, et al., Performance Evaluation of the Random Replacement Policy for Networks of Caches, ACM SIGMETRICS
Performance Evaluation Review, ACM, vol. 40, no. 1, (2012).
[15] Rossi, Dario and Giuseppe Rossini, Caching Performance of Content Centric Networks Under Multi-Path Routing (and more).
Relatóriotécnico, Telecom Paris Tech, (2011).
[16] K. Katsaros, G. Xylomenos and G. C. Polyzos, MultiCache: An Overlay Architecture for Information-Centric Networking, Computer
Networks, pp. 1–11, (2011).
[17] J. Choi, J. Han, E. Cho, T. T. Kwon and Y. Choi, A Survey on Content-Oriented Networking for Efficient Content Delivery, IEEE
Communications Magazine, pp. 121–127, (2011).
[18] I. Psaras, R. G. Clegg, R. Landa, W. K. Chai and G. Pavlou, Modelling and Evaluation of CCN-Caching Trees, IFIP Networking, (2011).
[19] E. J. Rosensweig and J. Kurose, Breadcrumbs: Efficient, Best-Effort Content Location in Cache Networks, IEEE INFOCOM, (2009).
[20] Suksomboon, Kalika, et al. Popcache: Cache More or Less based on Content Popularity for Information-Centric Networking, IEEE 38th
Conference on Local Computer Networks (LCN), 2013 IEEE, (2013).
[21] Ho, Cheng-Yun, Cheng-Yuan Ho and Chien-Chao Tseng, A Case Study of Cache Performance in ICN—Various Combinations of
Transmission Behavior and Cache Replacement Mechanism, 17th International Conference on Advanced Communication Technology
(ICACT), 2015 IEEE, (2015).
[22] N. Lal, A. P. Singh and S. Kumar, Modified Trial Division Algorithm using KNJ-Factorization Method to Factorize RSA Public Key
Encryption, International Conference on Contemporary Computing and Informatics (IC3I), 2014, pp. 992–995, 27–29 November (2014).
[23] Lal, Kumari Nidhi, and Ashutosh Kumar Singh, Modified Design of Microstrip Patch Antenna for WiMAX Communication System, IEEE
Students’ Technology Symposium (TechSym), 2014 IEEE, (2014).
[24] Lal, Nidhi, et al., A Heuristic EDF Uplink Scheduler for Real Time Application in WiMAX Communication. arXiv preprint
arXiv:1501.04553 (2015).
[25] Yonghui Shim and Young Han Kim, Data Aggregation with Multiple Sinks in Information-Centric Wireless Sensor Network, In International
Conference on Information Networking (ICOIN), 2014, pp. 13–17, 10–12 February (2014).
[26] Salsano, Stefano, et al., Information Centric Networking Over SDN and OpenFlow: Architectural Aspects and Experiments on the OFELIA
Testbed, Computer Networks 57.16, pp. 3207–3221, (2013).
[27] S. Hassan, Z. Aziz and K. Nisar, On the Cache Performance of the Information Centric Network, In International Conference on Computing,
Electrical and Electronics Engineering (ICCEEE), 2013, pp. 477–481, 26–28 August 2013.
[28] B. Azimdoost, C. Westphal and H. R. Sadjadpour, On the Throughput Capacity of Information-Centric Networks, In 25th International
Teletraffic Congress (ITC), 2013, pp. 1–9, 10–12 September (2013).