Fundamental limits of caching: improved bounds for users with small buffers

Zhi Chen; Pingyi Fan; Khaled Ben Letaief

Fundamental limits of caching: improved bounds for users with small buffers

View Fulltext

Author(s): Zhi Chen ¹ ; Pingyi Fan ² ; Khaled Ben Letaief ³
- Affiliations: 1: Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, ON, Canada, N2L3G1 ;
  2: Department of Electrical Engineering, Tsinghua University, Beijing 100084, People's Republic of China ;
  3: Department of Electronic and Computer Engineering, Hong Kong University of Science and Technology, Hong Kong, Hong Kong
Source: Volume 10, Issue 17, 24 November 2016, p. 2315 – 2318
DOI: 10.1049/iet-com.2015.1205 , Print ISSN 1751-8628, Online ISSN 1751-8636

Received 17/02/2016, Accepted 16/07/2016, Revised 08/07/2016, Published 24/11/2016

In this study, the caching problem is investigated. Assuming that the users are only equipped with buffer of small sizes, the peak rate of caching problem is investigated in this study. In contrast to recent results in the literature, this study shows that under some specific condition, i.e. if the number of users is no less than the amount of files in the server, a lower peak rate of caching is achievable. Furthermore, this new presented peak rate of caching is demonstrated to coincide with the well-known cut-set bound.

References

1. 1)
  - 11. Niesen, U., Maddah-Ali, M.A.: ‘Coded caching with nonuniform demands’, arXiv: 1308.0178 [cs.IT], 2013.
2. 2)
  - 3. Dan, A., Sitaram, D., Shahabuddin, P.: ‘Dynamic batching policies for an on-demand video server’, Multimedia Syst., 1996, 4, pp. 112–121 (doi: 10.1007/s005300050016).
3. 3)
  - 10. Maddah-Ali, M.A., Niesen, U.: ‘Decentralized caching attains order-optimal memory-rate tradeoff’, arXiv: 1301.5848 [cs.IT], 2013.
4. 4)
  - 14. Amiri, M.M., Gunduz, D.: ‘Fundamental limits of caching: improved delivery rate-cache capacity trade-off’, arXiv:1604.03888., 2016.
5. 5)
  - 15. Sengupta, A., Tandon, R., Clancy, T.C.: ‘Improved approximation of storage-rate tradeoff for caching via new outer bounds’. IEEE Int. Symp. Information Theory (ISIT'15), June 2015, pp. 1691–1695.
6. 6)
  - 1. Dowdy, L.W., Foster, D.V.: ‘Comparative models of the file assignment problem’, ACM Comput. Surv., 1982, 14, (4), pp. 287–313 (doi: 10.1145/356876.356883).
7. 7)
  - 12. Ji, M., Caire, G., Molisch, A.: ‘Fundamental limits of distributed caching in D2D wireless networks’. Proc. IEEE Information Theory Workshop (ITW'13), September 2013.
8. 8)
  - 8. Bar-Yossef, Z., Birk, Y., Jayram, T.S., et al: ‘Index coding with side information’, IEEE Trans. Inf. Theory, 2011, 57, pp. 1479–1494 (doi: 10.1109/TIT.2010.2103753).
9. 9)
  - 4. Meyerson, A., Munagala, K., Plotkin, S.: ‘Web caching using access statistics’. Proc. 12th ACM-SIAM Symp. Discrete Algorithm (SODA'01), June 2001, pp. 354–363.
10. 10)
  - 2. Almeroth, K.C., Ammar, M.H.: ‘The use of multicast delivery to provide a scalable and interactive video-on-demand service’, IEEE J. Sel. Areas Commun., 1996, 14, pp. 1110–1122 (doi: 10.1109/49.508282).
11. 11)
  - 5. Baev, I., Rajaraman, R., Swamy, C.: ‘Approximation algorithms for data placement problems’, SIAM J. Comput., 2008, 38, pp. 1411–1429 (doi: 10.1137/080715421).
12. 12)
  - 6. Borst, S., Gupta, V., Walid, A.: ‘Distributed caching algorithms for content distribution networks’. Proc. IEEE Int. Conf. Computer Communications (INFOCOM'10), March 2010, pp. 1478–1486.
13. 13)
  - 7. Birk, Y., Kol, T.: ‘Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients’, IEEE Trans. Inf. Theory, 2006, 52, pp. 2825–2830 (doi: 10.1109/TIT.2006.874540).
14. 14)
  - 16. Shariatpanahi, S.P., Motahari, S.A., Khalaj, B.H.: ‘Multi-server coded caching’. arXiv:1503.00265, 2015.
15. 15)
  - 13. Sengupta, A., Tandon, R., Clancy, T.C.: ‘Fundamental limits of caching with secure delivery’, arXiv: 1312.3961 [cs.IT], 2014.
16. 16)
  - 9. Maddah, -Ali, M.A., Niesen, U.: ‘Fundamental limits of caching’, IEEE Trans. Inf. Theory, 2014, 60, (5), pp. 2856–2867 (doi: 10.1109/TIT.2014.2306938).

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Fundamental limits of caching: improved bounds for users with small buffers

References

Related content