Fundamental Limits of Online Network-Caching Article Swipe

PDF

Rajarshi Bhattacharjee , Subhankar Banerjee , Abhishek Sinha ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2003.14085

Optimal caching of files in a content distribution network (CDN) is a problem of fundamental and growing commercial interest. Although many different caching algorithms are in use today, the fundamental performance limits of network caching algorithms from an online learning point-of-view remain poorly understood to date. In this paper, we resolve this question in the following two settings: (1) a single user connected to a single cache, and (2) a set of users and a set of caches interconnected through a bipartite network. Recently, an online gradient-based coded caching policy was shown to enjoy sub-linear regret. However, due to the lack of known regret lower bounds, the question of the optimality of the proposed policy was left open. In this paper, we settle this question by deriving tight non-asymptotic regret lower bounds in both of the above settings. In addition to that, we propose a new Follow-the-Perturbed-Leader-based uncoded caching policy with near-optimal regret. Technically, the lower-bounds are obtained by relating the online caching problem to the classic probabilistic paradigm of balls-into-bins. Our proofs make extensive use of a new result on the expected load in the most populated half of the bins, which might also be of independent interest. We evaluate the performance of the caching policies by experimenting with the popular MovieLens dataset and conclude the paper with design recommendations and a list of open problems.

Related Topics

Computer Science

Concepts

Computer science Computer network

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2003.14085
PDF: https://arxiv.org/pdf/2003.14085
OA Status: green
Cited By: 1
References: 51
Related Works: 10
OpenAlex ID: https://openalex.org/W3014839426

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3014839426

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2003.14085

Digital Object Identifier
Title: Fundamental Limits of Online Network-Caching

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-03-31

Full publication date if available
Authors: Rajarshi Bhattacharjee, Subhankar Banerjee, Abhishek Sinha

List of authors in order
Landing page: https://arxiv.org/abs/2003.14085

Publisher landing page
PDF URL: https://arxiv.org/pdf/2003.14085

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2003.14085

Direct OA link when available
Concepts: Computer science, Computer network

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2023: 1

Per-year citation counts (last 5 years)
References (count): 51

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3014839426
doi	https://doi.org/10.48550/arxiv.2003.14085
ids.doi	https://doi.org/10.48550/arxiv.2003.14085
ids.mag	3014839426
ids.openalex	https://openalex.org/W3014839426
fwci
type	preprint
title	Fundamental Limits of Online Network-Caching
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11478
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1705
topics[0].subfield.display_name	Computer Networks and Communications
topics[0].display_name	Caching and Content Delivery
topics[1].id	https://openalex.org/T10796
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9947999715805054
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Cooperative Communication and Network Coding
topics[2].id	https://openalex.org/T11896
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.989300012588501
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Opportunistic and Delay-Tolerant Networks
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.6386242508888245
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C31258907
concepts[1].level	1
concepts[1].score	0.36042505502700806
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1301371
concepts[1].display_name	Computer network
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.6386242508888245
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/computer-network
keywords[1].score	0.36042505502700806
keywords[1].display_name	Computer network
language	en
locations[0].id	pmh:oai:arXiv.org:2003.14085
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2003.14085
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2003.14085
locations[1].id	doi:10.48550/arxiv.2003.14085
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2003.14085
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5050233131
authorships[0].author.orcid	https://orcid.org/0000-0003-4732-2632
authorships[0].author.display_name	Rajarshi Bhattacharjee
authorships[0].author_position	first
authorships[0].raw_author_name	Rajarshi Bhattacharjee
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5005656212
authorships[1].author.orcid	https://orcid.org/0000-0002-8355-9162
authorships[1].author.display_name	Subhankar Banerjee
authorships[1].author_position	middle
authorships[1].raw_author_name	Subhankar Banerjee
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5057128963
authorships[2].author.orcid	https://orcid.org/0000-0001-7220-0691
authorships[2].author.display_name	Abhishek Sinha
authorships[2].author_position	last
authorships[2].raw_author_name	Abhishek Sinha
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2003.14085
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Fundamental Limits of Online Network-Caching
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11478
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1705
primary_topic.subfield.display_name	Computer Networks and Communications
primary_topic.display_name	Caching and Content Delivery
related_works	https://openalex.org/W4391375266, https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W4391913857, https://openalex.org/W2350741829
cited_by_count	1
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2003.14085
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2003.14085
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2003.14085
primary_location.id	pmh:oai:arXiv.org:2003.14085
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2003.14085
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2003.14085
publication_date	2020-03-31
publication_year	2020
referenced_works	https://openalex.org/W2129160848, https://openalex.org/W1972738071, https://openalex.org/W567076915, https://openalex.org/W2112716715, https://openalex.org/W1587463421, https://openalex.org/W2005830269, https://openalex.org/W2077723394, https://openalex.org/W2028404160, https://openalex.org/W1976986662, https://openalex.org/W2293000460, https://openalex.org/W2106248279, https://openalex.org/W2333682396, https://openalex.org/W2141645258, https://openalex.org/W2068871408, https://openalex.org/W2963465792, https://openalex.org/W2627076442, https://openalex.org/W3022520632, https://openalex.org/W2513905736, https://openalex.org/W2059475362, https://openalex.org/W2744431661, https://openalex.org/W2112053513, https://openalex.org/W1531395835, https://openalex.org/W2144315751, https://openalex.org/W2219888463, https://openalex.org/W2967531314, https://openalex.org/W1544602402, https://openalex.org/W2919316173, https://openalex.org/W2964007796, https://openalex.org/W2963905788, https://openalex.org/W2233344468, https://openalex.org/W889419725, https://openalex.org/W2105185344, https://openalex.org/W2091323212, https://openalex.org/W1985573567, https://openalex.org/W2034681107, https://openalex.org/W2039189705, https://openalex.org/W2121284183, https://openalex.org/W1963831729, https://openalex.org/W2149055490, https://openalex.org/W60189517, https://openalex.org/W1606035500, https://openalex.org/W1591588763, https://openalex.org/W1409984952, https://openalex.org/W2117702591, https://openalex.org/W2970222725, https://openalex.org/W2951590424, https://openalex.org/W2154682027, https://openalex.org/W2004335587, https://openalex.org/W2138350977, https://openalex.org/W2119738171, https://openalex.org/W2078205146
referenced_works_count	51
abstract_inverted_index.a	5, 11, 59, 64, 69, 74, 80, 144, 177, 222
abstract_inverted_index.In	46, 118, 138
abstract_inverted_index.We	199
abstract_inverted_index.an	37, 84
abstract_inverted_index.be	195
abstract_inverted_index.by	125, 158, 207
abstract_inverted_index.in	4, 25, 53, 132, 184
abstract_inverted_index.is	10
abstract_inverted_index.of	2, 13, 32, 71, 76, 101, 108, 111, 134, 169, 176, 189, 196, 203, 224
abstract_inverted_index.on	180
abstract_inverted_index.to	44, 63, 92, 98, 140, 164
abstract_inverted_index.we	49, 121, 142
abstract_inverted_index.(1)	58
abstract_inverted_index.(2)	68
abstract_inverted_index.Our	171
abstract_inverted_index.and	15, 67, 73, 214, 221
abstract_inverted_index.are	24, 156
abstract_inverted_index.due	97
abstract_inverted_index.new	145, 178
abstract_inverted_index.set	70, 75
abstract_inverted_index.the	28, 54, 99, 106, 109, 112, 135, 154, 160, 165, 181, 185, 190, 201, 204, 210, 216
abstract_inverted_index.two	56
abstract_inverted_index.use	26, 175
abstract_inverted_index.was	90, 115
abstract_inverted_index.also	194
abstract_inverted_index.both	133
abstract_inverted_index.from	36
abstract_inverted_index.half	188
abstract_inverted_index.lack	100
abstract_inverted_index.left	116
abstract_inverted_index.list	223
abstract_inverted_index.load	183
abstract_inverted_index.make	173
abstract_inverted_index.many	20
abstract_inverted_index.most	186
abstract_inverted_index.open	225
abstract_inverted_index.this	47, 51, 119, 123
abstract_inverted_index.user	61
abstract_inverted_index.with	150, 209, 218
abstract_inverted_index.(CDN)	9
abstract_inverted_index.above	136
abstract_inverted_index.bins,	191
abstract_inverted_index.coded	87
abstract_inverted_index.date.	45
abstract_inverted_index.enjoy	93
abstract_inverted_index.files	3
abstract_inverted_index.known	102
abstract_inverted_index.lower	104, 130
abstract_inverted_index.might	193
abstract_inverted_index.open.	117
abstract_inverted_index.paper	217
abstract_inverted_index.shown	91
abstract_inverted_index.that,	141
abstract_inverted_index.tight	127
abstract_inverted_index.users	72
abstract_inverted_index.which	192
abstract_inverted_index.bounds	131
abstract_inverted_index.cache,	66
abstract_inverted_index.caches	77
abstract_inverted_index.design	219
abstract_inverted_index.limits	31
abstract_inverted_index.online	38, 85, 161
abstract_inverted_index.paper,	48, 120
abstract_inverted_index.policy	89, 114, 149
abstract_inverted_index.poorly	42
abstract_inverted_index.proofs	172
abstract_inverted_index.regret	103, 129
abstract_inverted_index.remain	41
abstract_inverted_index.result	179
abstract_inverted_index.settle	122
abstract_inverted_index.single	60, 65
abstract_inverted_index.today,	27
abstract_inverted_index.Optimal	0
abstract_inverted_index.bounds,	105
abstract_inverted_index.caching	1, 22, 34, 88, 148, 162, 205
abstract_inverted_index.classic	166
abstract_inverted_index.content	6
abstract_inverted_index.dataset	213
abstract_inverted_index.growing	16
abstract_inverted_index.network	8, 33
abstract_inverted_index.popular	211
abstract_inverted_index.problem	12, 163
abstract_inverted_index.propose	143
abstract_inverted_index.regret.	95, 152
abstract_inverted_index.resolve	50
abstract_inverted_index.through	79
abstract_inverted_index.uncoded	147
abstract_inverted_index.Although	19
abstract_inverted_index.However,	96
abstract_inverted_index.addition	139
abstract_inverted_index.conclude	215
abstract_inverted_index.deriving	126
abstract_inverted_index.evaluate	200
abstract_inverted_index.expected	182
abstract_inverted_index.learning	39
abstract_inverted_index.network.	82
abstract_inverted_index.obtained	157
abstract_inverted_index.paradigm	168
abstract_inverted_index.policies	206
abstract_inverted_index.proposed	113
abstract_inverted_index.question	52, 107, 124
abstract_inverted_index.relating	159
abstract_inverted_index.MovieLens	212
abstract_inverted_index.Recently,	83
abstract_inverted_index.bipartite	81
abstract_inverted_index.connected	62
abstract_inverted_index.different	21
abstract_inverted_index.extensive	174
abstract_inverted_index.following	55
abstract_inverted_index.interest.	18, 198
abstract_inverted_index.populated	187
abstract_inverted_index.problems.	226
abstract_inverted_index.settings.	137
abstract_inverted_index.settings:	57
abstract_inverted_index.algorithms	23, 35
abstract_inverted_index.commercial	17
abstract_inverted_index.optimality	110
abstract_inverted_index.sub-linear	94
abstract_inverted_index.understood	43
abstract_inverted_index.fundamental	14, 29
abstract_inverted_index.independent	197
abstract_inverted_index.performance	30, 202
abstract_inverted_index.Technically,	153
abstract_inverted_index.distribution	7
abstract_inverted_index.lower-bounds	155
abstract_inverted_index.near-optimal	151
abstract_inverted_index.experimenting	208
abstract_inverted_index.point-of-view	40
abstract_inverted_index.probabilistic	167
abstract_inverted_index.gradient-based	86
abstract_inverted_index.interconnected	78
abstract_inverted_index.non-asymptotic	128
abstract_inverted_index.recommendations	220
abstract_inverted_index.balls-into-bins.	170
abstract_inverted_index.Follow-the-Perturbed-Leader-based	146
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
sustainable_development_goals[0].id	https://metadata.un.org/sdg/17
sustainable_development_goals[0].score	0.4399999976158142
sustainable_development_goals[0].display_name	Partnerships for the goals
citation_normalized_percentile