On the Optimality of Coded Caching With Heterogeneous User Profiles

2025-04-27 0 0 306.23KB 6 页 10玖币

侵权投诉

On the Optimality of Coded Caching With

Heterogeneous User Proﬁles

Federico Brunero and Petros Elia

Communication Systems Department, EURECOM, Sophia Antipolis, France

Email: {brunero, elia}@eurecom.fr

Abstract—In this paper, we consider a coded caching scenario

where users have heterogeneous interests. Taking into considera-

tion the system model originally proposed by Wang and Peleato,

for which the end-receiving users are divided into groups ac-

cording to their ﬁle preferences, we develop a novel information-

theoretic converse on the optimal worst-case communication load

under uncoded cache placement. Interestingly, the developed

converse bound, jointly with one of the coded schemes proposed

by Wang and Peleato, allows us to characterize the optimal worst-

case communication load under uncoded prefetching within a

constant multiplicative gap of 2. Although we restrict the caching

policy to be uncoded, our work improves the previously known

order optimality results for the considered caching problem.

Index Terms—Coded caching, ﬁle popularity, heterogeneous

proﬁles, information-theoretic converse, user preferences.

I. INTRODUCTION

With the introduction of video streaming platforms and

cloud computing services, such as Netﬂix, Amazon Prime and

AWS, we witnessed in the recent years a signiﬁcant rise in

the network trafﬁc. On the one hand, the appearance of data-

intensive network applications clearly entails more services at

disposal of the users, with consequent beneﬁts for the latter. On

the other, communication networks are constantly put under

pressure to deliver increasingly larger volumes of data in a

timely and efﬁcient manner. As a consequence, the explosion

of network trafﬁc has sparked much interest in developing new

communication techniques and, to this end, much research

focused on the pivotal role that caching will play in the future.

The idea of caching simply consists of exploiting low-cost

memories at end-receiving users to diminish signiﬁcantly the

network load from a centralized server to its cache-aided

receiving users. The real challenge is to intelligently design the

placement phase so as to minimize the volume of data that the

server has to deliver during the delivery phase. The seminal

work in [1] tackled this problem introducing the clever concept

of coded caching, a major breakthrough which pushed even

further the beneﬁts of caching. More speciﬁcally, the Maddah-

Ali and Niesen (MAN) coded scheme in [1] shed light on the

actual information-theoretic gains that caching can provide if

the placement phase is carefully designed so that, during the

delivery phase, coding techniques can be employed to align the

interference patterns. Current research on coded caching spans

several topics such as the interplay between multiple antennas

This work was supported by the European Research Council (ERC) through

the EU Horizon 2020 Research and Innovation Program under Grant 725929

(Project DUALITY).

and caching [2]–[5], the construction of converse bounds [6],

[7] and a variety of other scenarios [8]–[11].

A. Coded Caching With Hetereogeneous User Proﬁles

Since the introduction of coded caching, many works studied

several variations of the original information-theoretic system

model. In particular, much research aimed at understanding

how caching policies should reﬂect the possibility that, in real

scenarios, contents may have different degrees of popularity

and users may have diverging interests.

On the one hand, considering that traditional caching

techniques heavily rely on the fact that some contents might

be more popular than others, the works in [12], [13] focused

on the interplay between coded caching and ﬁle popularities.

On the other hand, some other works sought to explore the

scenario where each user is not necessarily interested in the

entire library of contents at the main server — as instead was

implicitly assumed in [1]. For instance, the works in [14], [15]

explored, for the case of

K= 2

users, the performance of

selﬁsh coded caching in the presence of heterogeneous user

proﬁles or, equivalently, heterogeneous ﬁle demand sets (FDSs),

proving that, for the instances proposed therein, unselﬁsh

caching policies can do better than selﬁsh ones. Later, the work

in [16] analyzed for a uniﬁed setting the interplay between

selﬁsh caching policies and coded caching, providing the

meaningful conclusion that unselﬁsh coded caching can be

unboundedly better the selﬁsh caching. Subsequently, the recent

work in [17] characterized the optimal memory-load tradeoff

for a scenario where users are interested in a limited set of

contents which depends on the location of the users themselves.

Recently, the authors in [18]–[20] considered coded caching

with a very well-deﬁned structure for the user proﬁles. As-

suming that the ﬁles in the main library can be classiﬁed as

either common ﬁles (ﬁles that can be requested by any user)

or unique ﬁles (ﬁles that can be requested by groups of users

only), the work in [18] proposed three different coded schemes

for such scenario, providing a related analysis for their peak

load performance. Then, these three schemes were studied also

in [19] in terms of their average load performance, whereas the

work in [20] provided, by means of a converse bound based

on cut-set arguments, some order optimality results.

B. Main Contribution

Our work further explores the system model proposed in [18].

In particular, taking advantage of the genie-aided converse

arXiv:2210.06066v1 [cs.IT] 12 Oct 2022

bound idea from [7], our main result is a lower bound on

the optimal worst-case communication load under uncoded

prefetching. Interestingly, the derived converse, together with

an already existing achievable scheme from [18], allows

us to characterize the memory-load tradeoff under uncoded

placement within a constant multiplicative factor of 2.

C. Paper Outline

The system model and related results are presented in

Section II. Section III presents the information-theoretic

converse and the order optimality result, whose proofs are

provided in Section IV and Section V, respectively. Section VI

concludes the paper.

D. Notation

We denote by

Z+

the set of positive integers. For

n∈Z+

, we

deﬁne

[n]:={1,2, . . . , n}

. If

a, b ∈Z+

such that

a<b

, then

[a:b]:={a, a + 1, . . . , b −1, b}

. For sets we use calligraphic

symbols, whereas for vectors we use bold symbols. Given a

ﬁnite set

, we denote by

|A|

its cardinality. We denote by

n

k

the binomial coefﬁcient and we let

n

k= 0

whenever

n < 0

k < 0

n<k

. For

n∈Z+

, we denote by

the symmetric

group deﬁned over the set [n].

II. SYSTEM MODEL AND RELATED RESULTS

We consider the coded caching setting where there is a single

server connected to

users through an error-free broadcast

channel. The server has access to a central library that contains

ﬁles of

bits each. Each user in the system is equipped with

a cache of size

bits (or, equivalently,

ﬁles). According

to the system model in [18], the

users are split in

groups,

where each group consists of

K/G

users sharing the same

interests. Furthermore, the ﬁles in the library are divided in

two categories, i.e., common ﬁles and unique ﬁles. There are

common ﬁles

{Wc

n:n∈[Nc]}

, where each of them is

of interest to every user in the system. Then, for each group

g∈[G]

, there are

ﬁles

{Wu,g

n:n∈[Nu]}

, where each of

them is of interest to the users belonging to the group

g∈[G]

only. Assuming that

{Wc

n:n∈[Nc]}∩{Wu,g

n:n∈[Nu]}=∅

for each

g∈[G]

, and that

{Wu,g1

n:n∈[Nu]} ∩ {Wu,g2

n:n∈

[Nu]}=∅

for each

g1, g2∈[G]

with

g16=g2

, we have

N=Nc+GNu

ﬁles in total. Deviating from standard notation

practices, we will use

Wfk,g(k)

to denote the ﬁle requested by

user

k∈[K]

, where

fk∈ {c,u}

dk∈[Nfk]

and

g(k)

is an

abuse of notation to denote the group which user

belongs

to, i.e.,

g(k)∈[G]

for each

k∈[K]

. We further assume

that

Wc,g(k)

dk=Wc

, since common ﬁles do not depend on the

group

g∈[G]

. In addition, we let

d= ((d1, f1),...,(dK, fK))

be the demand vector and we denote by

the set of all possible

demand vectors with distinct requested ﬁles, i.e.,

Wfk1,g(k1)

dk16=

Wfk2,g(k2)

dk2

for each

k1, k2∈[K]

with

k16=k2

. Finally, we

assume Nc≥Kand Nu≥K/G.

The caching problem consists of two phases. During the

placement phase, users have access to the main library, and so

each user ﬁlls their cache using the library. Here, we focus on

uncoded caching policies according to the following deﬁnition.

Deﬁnition 1

(Uncoded Prefetching)

A cache placement is

uncoded if each user

k∈[K]

simply copies in their cache a

total of (at most)

bits from the library. Consequently, the

ﬁles are partitioned as

n={Wc

n,T:T ⊆ [K]},∀n∈[Nc](1)

Wu,g

n={Wu,g

n,T:T ⊆ [K]},∀n∈[Nu],∀g∈[G](2)

where

n,T

and

Wu,g

n,T

represent the bits of

and

Wu,g

respectively, which are cached only by the users in T.

During the delivery phase, the demand vector

((d1, f1),...,(dK, fK))

is revealed to the server. Denoting

the set of caching schemes with uncoded placement, the

server transmits a message

R(d, χ, M)B

bits for a given

demand

d∈ D

, a given uncoded cache placement

χ∈ X

and

some given memory

. The quantity

R(d, χ, M)

is called

load and our goal is to characterize the optimal worst-case

communication load under uncoded cache placement, namely,

we aim to characterize the quantity given by

R?(M) = min

χ∈X max

d∈D R(d, χ, M).(3)

In the following, the dependency on

will be implied for

the sake of simplicity.

A. An Existing Achievable Scheme

The authors in [18] proposed for the aforementioned setting

a coded scheme — referred to as Scheme 2 in [18] — which

treats separately the caching and the delivery of common and

unique ﬁles.

1) Placement Phase: First, the cache of each user is split

in two parts for some

0≤β≤1

, so that

βM

is the part of

cache that is devoted to store common ﬁles and

(1 −β)M

the part of cache that is devoted to store unique ﬁles. Then,

common ﬁles {Wc

n:n∈[Nc]}are stored across the Kusers

using the MAN cache placement with memory

βM

. Similarly,

unique ﬁles

{Wu,g

n:n∈[Nu]}

are stored across the

K/G

users in group

g∈[G]

using the MAN algorithm with memory

(1 −β)M.

2) Delivery Phase: It was shown in [18] that, when there

are

users per group requesting unique ﬁles, the optimal

worst-case load can be upper bounded as

R?≤min

βmax

αR(β, α)(4)

where R(β, α)is deﬁned as

R(β, α):=K

tc+1−Gα

tc+1

K

tc+GK/G

tu+1−K/G−α

tu+1 

K/G

tu(5)

with tc:=KβM/Ncand tu:=K(1 −β)M/GNu.

Since the works in [18], [20] treated the variables

and

t:=KM/N

as continuous

, we do the same here

for the sake of simplicity. Further, we extend the Scheme 2

in [18] to the entire memory regime

0≤M≤Nc+Nu

, using

the Gamma function whenever the binomial coefﬁcients in

(5)

have non-integer arguments.

Indeed, if the quantities

and

are large enough, the rounding

errors due to integer effects during calculations can be neglected.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OntheOptimalityofCodedCachingWithHeterogeneousUserProlesFedericoBruneroandPetrosEliaCommunicationSystemsDepartment,EURECOM,SophiaAntipolis,FranceEmail:fbrunero,eliag@eurecom.frAbstractInthispaper,weconsideracodedcachingscenariowhereusershaveheterogeneousinterests.Takingintoconsidera-tionthesystemm...

展开>> 收起<<

On the Optimality of Coded Caching With Heterogeneous User Profiles.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On the Optimality of Coded Caching With Heterogeneous User Profiles

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: