Journal Home > Volume 21 , Issue 4
Tsinghua Science and Technology 2016, 21(4): 374-384 https://doi.org/10.1109/TST.2016.7536715
Open Access | Issue | Published: 11 August 2016

An Optimal Content Caching Framework for Utility Maximization

Show Author's Information Ran Bi( ),  Yingshu Li,  Xu Zheng
Department of Computer Science, Dalian University of Technology, Dalian 116024, China.
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA.
Department of Computer Science, Harbin Institute of Technology, Harbin 150000, China.
Keywords:
approximation algorithm, content caching, utility maximization, integer optimization
Cite this article:
Bi R, Li Y, Zheng X. An Optimal Content Caching Framework for Utility Maximization. Tsinghua Science and Technology, 2016, 21(4): 374-384. https://doi.org/10.1109/TST.2016.7536715
Download citation
EndNote(RIS)
BibTeX

390

Views

32

Downloads

Citations

4

Crossref

N/A

WoS

4

Scopus

1

CSCD

Abstract Full text About this article

For desirable quality of service, content providers aim at covering content requests by large network caches. Content caching has been considered as a fundamental module in network architecture. There exist few studies on the optimization of content caching. Most existing works focus on the design of content measurement, and the cached content is replaced by a new one based on the given metric. Therefore, the performance for service provision with multiple levels is decreased. This paper investigates the problem of finding optimal timer for each content. According to the given timer, the caching policies determine whether to cache a content and which existing content should be replaced, when a content miss occurs. Aiming to maximize the aggregate utility with capacity constraint, this problem is formalized as an integer optimization problem. A linear programming based approximation algorithm is proposed, and the approximation ratio is proved. Furthermore, the problem of content caching with relaxed constraints is given. A Lagrange multiplier based approximation algorithm with polynomial time complexity is proposed. Experimental results show that the proposed algorithms have better performance.


menu
Abstract
Full text
Outline
About this article

An Optimal Content Caching Framework for Utility Maximization

Show Author's information Ran Bi( ), Yingshu Li, Xu Zheng
Department of Computer Science, Dalian University of Technology, Dalian 116024, China.
Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA.
Department of Computer Science, Harbin Institute of Technology, Harbin 150000, China.

Abstract

For desirable quality of service, content providers aim at covering content requests by large network caches. Content caching has been considered as a fundamental module in network architecture. There exist few studies on the optimization of content caching. Most existing works focus on the design of content measurement, and the cached content is replaced by a new one based on the given metric. Therefore, the performance for service provision with multiple levels is decreased. This paper investigates the problem of finding optimal timer for each content. According to the given timer, the caching policies determine whether to cache a content and which existing content should be replaced, when a content miss occurs. Aiming to maximize the aggregate utility with capacity constraint, this problem is formalized as an integer optimization problem. A linear programming based approximation algorithm is proposed, and the approximation ratio is proved. Furthermore, the problem of content caching with relaxed constraints is given. A Lagrange multiplier based approximation algorithm with polynomial time complexity is proposed. Experimental results show that the proposed algorithms have better performance.

Keywords: approximation algorithm, content caching, utility maximization, integer optimization

References(28)

[1]
Zheng X., Cai Z., Li J., and Gao H., Scheduling flows with multiple service frequency constraints, IEEE Internet of Things, 2016, .
DOI Google Scholar
[2]
Li J., Cai Z., Yan M., and Li Y., Using crowdsourced data in location-based social networks to explore influence maximization, in Proc. 2016 IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, USA, 2016.
[3]
Duan Z., Yan M., Cai Z., Wang X., Han M., and Li Y., Truthful incentive mechanisms for social cost minimization in mobile crowdsourcing systems, Sensors, vol. 16, no. 4, pp. 481–493, 2016.
DOI Google Scholar
[4]
Zheng X., Cai Z., Li J., and Gao H., An application-aware scheduling policy for real-time traffic, in Proc. 35th International Conference on Distributed Computing Systems (ICDCS), Columbus, OH, USA, 2015, pp. 421-430.
[5]
Li S., Xu J., Schaar M. D., and Li W., Popularity-driven content caching, in Proc. 2016 IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, USA, 2016.
[6]
Amazon CloudFront, http://aws.amazon.com/cloudfront/details/, 2016.
[7]
Nygren E., Sitaraman R. K., and Sun J., The akamai network: A platform for high-performance internet applications, ACM SIGOPS Operating Systems Review, vol. 44, no. 3, pp. 2–19, 2010.10.1145/1842733.1842736
DOI Google Scholar
[8]
Muscariello L., Carofiglio G., and Gallo M., Bandwidth and storage sharing performance in information centric networking, in Proc. 2011 SIGCOMM Workshop on Information-Centric Networking, Toronto, ON, Canada, 2011, pp. 26-31.
[9]
Tan B. and Massouliĺe L., Optimal content placement for peer-to-peer video-on-demand systems, Transactions on Networking (TON), vol. 21, no. 2, pp. 566–579, 2013.
DOI Google Scholar
[10]
Dehghan M., Massoulie L., Towsley D., Menasche D., and Tay Y. C., A utility optimization approach to network cache design, in Proc. 2016 IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, USA, 2016.
[11]
Ahlgren B., Dannewitz C., Imbrenda C., Kutscher D., and Ohlman B., A survey of information-centric networking, IEEE Communications Magazine, vol. 50, no. 7, pp. 26–36, 2012.
DOI Google Scholar
[12]
Jacobson V., Smetters D. K., Thornton J. D., Plass M. F., Briggs N., and Braynard R., Networking named content, Communications of the ACM, vol. 55, no. 1, pp. 117–124, 2012.
DOI Google Scholar
[13]
Wu Y., Wu C., Li B., Zhang L., Li Z., and Lau F., Scaling social media applications into geo-distributed clouds, Transactions on Networking, vol. 23, no. 3, pp. 689–702, 2015.
DOI Google Scholar
[14]
Blasco P. and Gunduz D., Learning-based optimization of cache content in a small cell base station, in Proc. 2014 IEEE International Conference on Communications (ICC), Sydney, Australia, 2014, pp. 1897-1903.
[15]
Famaey J., Iterbeke F., Wauters T., and Turck F. D., Towards a predictive cache replacement strategy for multimedia content, Journal of Network and Computer Applications, vol. 36, no. 1, pp. 219–227, 2013.
DOI Google Scholar
[16]
Guo S., Xie H., and Shi G., Collaborative forwarding and caching in content centric networks, in Proc. 11th International IFIP TC 6 Networking Conference, Prague, Czech Republic, 2012, pp. 41-55.
DOI
[17]
Zhang L., Wang X., Lu J., Li P., and Cai Z., An efficient privacy preserving data aggregation approach for mobile sensing, Security and Communication Networks Journal, 2016, .
DOI Google Scholar
[18]
Zhang L., Cai Z., and Wang X., FakeMask: A novel privacy preserving approach for smartphones. IEEE Transactions on Network and Service Management, vol. 13, no. 2, pp. 335–348, 2016.
DOI Google Scholar
[19]
Maddah-Ali M. A. and Niesen U., Fundamental limits of caching, IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.
DOI Google Scholar
[20]
Hachem J., Karamchandani N., and Diggavi S., Content caching and delivery over heterogeneous wireless networks, in Proc. 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2015, pp. 756-764.
[21]
ElBamby M. S., Bennis M., Saad W., and Latvaaho M., Content-aware user clustering and caching in wireless small cell networks, in 11th International Symposium on Wireless Communications Systems (ISWCS), Barcelona, Spain, 2014, pp. 945-949.
[22]
Leconte M., Paschos G., Gkatzikis L., Draief M., Vassilaras S., and Chouvardas S., Placing dynamic content in caches with small population, in Proc. 2016 IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, USA, 2016.
[23]
Dehghan M., Seetharam A., Jiang B., He T., Salonidis T., Kurose J., Towsley D., and Sitaraman R. K., On the complexity of optimal routing and content caching in heterogeneous networks, in Proc. 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 2015, pp. 936-944.
[24]
Kelly F. P., Maulloo A. K., and Tan D. K., Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of the Operational Research Society, vol. 49, no. 3, pp. 237–252, 1998.
DOI Google Scholar
[25]
Huang L. and Neely M. J., Utility optimal scheduling in energy harvesting networks, Transactions on Networking, vol. 21, no. 4, pp. 1117–1130, 2013.
DOI Google Scholar
[26]
Eryilmaz A. and Srikant R., Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control, Transaction on Networking, vol. 15, no. 6, pp. 1333–1344, 2007.
DOI Google Scholar
[27]
Srikant R. and Ying L., Communication Networks: An Optimization, Control, and Stochastic Networks Perspective. Cambridge University Press, 2013.
[28]
UMass trace repository, http://traces.cs.umass.edu/index.php/network/network, 2016.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 20 June 2016
Accepted: 28 June 2016
Published: 11 August 2016
Issue date: August 2016

Copyright

© The author(s) 2016

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61572104 and 61402076), Startup Fund for the Doctoral Program of Liaoning Province (No. 20141023), the Fundamental Research Funds for the Central Universities (Nos. DUT15RC(3)088, DUT15QY26, and DUT14QY06).

Rights and permissions

Return