Cache Allocations for Consecutive Requests of Categorized Contents: Service Provider’s Perspective

Minseok Choi^†∗, Andreas F. Molisch^†, Dong-Jun Han^‡, Joongheon Kim^∗, and Jaekyun Moon^‡ ^†Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, USA
^‡School of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea
^∗School of Electrical Engineering, Korea University, Seoul, South Korea
E-mails: [email protected], [email protected][email protected], [email protected],
[email protected]

Abstract

In wireless caching networks, a user generally has a concrete purpose of consuming contents in a certain preferred category, and requests multiple contents in sequence. While most existing research on wireless caching and delivery has focused only on one-shot requests, the popularity distribution of contents requested consecutively is definitely different from the one-shot request and has been not considered. Also, especially from the perspective of the service provider, it is advantageous for users to consume as many contents as possible. Thus, this paper proposes two cache allocation policies for categorized contents and consecutive user demands, which maximize 1) the cache hit rate and 2) the number of consecutive content consumption, respectively. Numerical results show how categorized contents and consecutive content requests have impacts on the cache allocation.

I Introduction

In multimedia services, e.g., on-demand streaming services, a relatively small number of popular contents generally occupies a large portion of the massive global data traffic, and most of user demands are overlapped and repeated [1]. To deal with this issue, wireless caching technologies have been studied, wherein the base station (BS) or the server pushes popular contents for off-peak hours to cache-enabled nodes so that these nodes provide contents directly to nearby mobile users during peak hours [2]. In practice, caching nodes (i.e., caching helpers and/or cache-enabled devices) have finite storage sizes, which leads the content placement problem to determine which content is better to be stored in caching nodes [3].

The goal of the content placement problem is to find optimal caching policies according to the popularity distribution of contents and network topology. In stochastic wireless caching networks, there exist research efforts on probabilistic content placement introduced in [4, 5]. Many probabilistic caching methods have been proposed for various systems, e.g., device-to-device (D2D) networks [6], $N$ -tier hierarchical networks [7], multi-quality dynamic streaming [8], and probabilistic coded caching was also recently proposed in [9].

Previous research optimized content placement for users requesting only one content, i.e., one-shot request, under the assumption that all content requests are independent. In multimedia services, the user typically accesses a service platform with the purpose of consuming a specific category of the content, and generally consumes more than one content. In this case, the sequence of consecutively consumed contents is highly correlated. For example, in video services such as YouTube, the related video list is recommended to the user after the first content is consumed [10]. In particular, the view count of a given video varies in almost the same scale as the average view count of the top referrer videos in the related list [11]; therefore, a user is highly likely to request one of the videos in the related category. Therefore, this paper considers the scenario in which a user consecutively requests multiple contents that are likely to be in its preferred category. In this context, this paper proposes two cache allocation policies for categorized contents and consecutive user demands, which maximize the cache hit rate and the expected number of consecutive content consumptions, respectively.

The previous work of [12] has proposed a caching policy for consecutive user demands with the assumption that the number of content requests is fixed. This assumption does not allow the service provider to maximize user’s content consumption; however, in the perspective of service providers, it is important to satisfy as many of the user’s requests as possible. In this paper, each user determines whether to continue to consume more contents depending on cache states in its vicinity, and the service provider aims at making users stay in the service longer.

The main contributions are as follows:

•

Different from most existing results on wireless caching in which one-shot requests are considered only, consecutive requests of categorized contents are considered. In practice, the sequence of consecutively consumed contents is highly correlated, and an advanced caching scheme is required.
•

Based on real data set, the recent work of [13] has modeled the category-based conditional content popularity distribution. This paper uses this measurement-based popularity model to obtain the proposed cache allocation rule for consecutive requests of categorized contents.
•

This paper proposes two cache allocation schemes which maximize cache hit rates and the expected number of consecutive content requests, respectively. The iterative algorithm is presented to find the optimal cache allocation rules and its convergence is proved.
•

Numerical results show how 1) the popularity concentration to the preferred category and 2) different numbers of contents in the different categories influence the cache allocation rule.

The rest of the paper is organized as follows. The system model is described in Section II. The cache allocation rules maximizing the cache hit probability and the number of consecutive content consumption are proposed in Sections III and IV, respectively. The numerical results are shown in Section V and Section VI concludes the paper.

II System Model

II-A Wireless Caching Network

This paper assumes that caching nodes are randomly distributed according to a general spatial distribution $\Phi$ , and the server which has a content library $\mathcal{N}$ pushes some popular contents to each caching node during off-peak hours. Suppose that a library $\mathcal{N}$ consists of $N$ contents and all contents have a normalized unit size. Let all $N$ contents be grouped into $K$ categories, and $N_{i}$ contents are in category $i$ denoted by $\mathcal{C}_{i}$ , for all $i\in\mathcal{K}=\{1,\cdots,K\}$ , satisfying $\sum_{i=1}^{K}N_{i}=N$ . Also, denote the content index set of $\mathcal{C}_{i}$ by $\mathcal{N}_{i}=\{1,\cdots,N_{i}\}$ .

The caching nodes have the finite storage size $M$ , which means only $M$ contents can be cached in each node. Since $N>M$ in practice, caching nodes store a part of contents in $\mathcal{N}$ . A user requests the content from caching nodes in its vicinity. If the user finds at least one caching node that stores the desired content, this case is called the cache hit. When the user requests multiple contents, we define the cache hit as the case where all of requested contents can be found in nearby caching nodes. When there is no caching node having some of the requested contents, the server can deliver them via a cellular link. However, this paper assumes that the transmission quality of the cellular link is insufficient due to delay and/or congestion that leads to unacceptable video quality, so that henceforth we do not consider direct transmission from the server.

Let the storage size $M$ be divided into $K$ fractions with unequal sizes denoted by $\alpha_{i}$ for all $i\in\mathcal{K}$ , and contents in $\mathcal{C}_{i}$ are stored within $\alpha_{i}$ . These fractions will be called cache allocations for categories and satisfy $\sum_{i=1}^{K}\alpha_{i}\leq M$ and $\alpha_{i}\leq N_{i}$ . Given all of $\boldsymbol{\alpha}=(\alpha_{1},\cdots,\alpha_{K})$ , how to store individual contents within each category becomes a classical content placement problem, and we consider the probabilistic caching policy for individual contents as shown in [4, 5].

TABLE I: Key notations

$K$	Number of categories
$N_{i}$	Number of contents in category $i$
$k$	Index of the preferred category
$M$	Cache size
$\alpha_{i}$	Cache allocation for category $i$
$f_{i}$	Global popularity of category $i$
$p_{1}$	Popularity of the preferred category
$r$	Rank of category that requests contents
$l$	Number of consecutive content requests
$l_{r}$	Number of requested contents in the $r$ -ranked category
$i_{r}$	Category index of the $r$ -ranked category
$\epsilon$	Probability of not requesting the next content

II-B Content Popularity Model

This paper focuses on the scenario in which the user requests multiple contents consecutively, different from most of existing caching policies which considered only one-shot requests. A representative example is a video streaming service. For example, a user can access the service platform with a concrete purpose of watching some sports highlight clips. In this case, we can postulate that sports is the user’s preferred category, therefore the probability of requesting sports videos in sequence is very high. In contrast, the probability of requesting contents in other categories, e.g., movie trailers, is very small although not zero.

Accordingly, the content request can be modeled by the following steps. First, the user randomly picks one category in $\mathcal{K}$ . Each category $i\in\mathcal{K}$ has a global category popularity, which follows the Zipf distribution [4]: $f_{i}=i^{-\gamma}/\sum_{j=1}^{K}j^{-\gamma}$ where $\gamma$ denotes the popularity distribution skewness. Then, the selected category has the first rank among all categories; note that the global category popularity is only used for choosing the first rank. Other categories can have any rank except for the first rank, but this paper models all categories that are not the first for this particular user as statistically equivalent; in other words, the relative ranking from $2,\cdots,K$ does not matter. After determining the preferred category, the user chooses one of categories to request the content depending on their ranks. Again, the category rank distribution given the preferred category is assumed to follow the Zipf distribution, i.e., $\mathrm{Pr}\{R=r\}=r^{-\gamma^{\text{out}}}/\sum_{j=1}^{K}j^{-\gamma^{\text{out}}}$ , which represents the popularity of the $r$ -th ranked category and $\gamma^{\text{out}}$ is the Zipf factor. We denote the popularity of the preferred category by $p_{1}=\mathrm{Pr}\{R=1\}$ . Note that $p_{1}$ is the probability of staying within the given preferred category, not the general probability of picking the 1st-ranked category as in [13], which is a different quantity. Here, we also consider the situation in which the user can stop to request contents by itself with small probability of $\epsilon$ . Therefore, the probability of requesting any content in the $r$ -th ranked category after consuming the first content becomes $(1-\epsilon)\cdot\mathrm{Pr}\{R=r\}$ .

After choosing the category rank, the user requests the specific content in the category having the chosen rank. According to [13], the category-based conditional popularity distribution of contents in $\mathcal{C}_{i}$ follows the Mandelbrot-Zipf (M-Zipf) distribution, i.e.,

a_{i,n}=\frac{\frac{1}{(n+c^{\text{in}})^{\gamma_{i}^{\text{in}}}}}{\sum_{m=1}^{N_{i}}\frac{1}{(m+c^{\text{in}})^{\gamma_{i}^{\text{in}}}}},

(1)

which represents the popularity of the $n$ -th content in $\mathcal{C}_{i}$ for $n\in\mathcal{N}_{i}$ . $\gamma_{i}^{\text{in}}$ and $c^{\text{in}}$ are the Zipf factor and the plateau factor of $\mathcal{C}_{i}$ , respectively. Here, if $\gamma^{\text{out}}$ is sufficiently large, $p_{1}\gg 1-\epsilon-p_{1}$ and the popularity of contents in the preferred $\mathcal{C}_{k}$ is much larger than that of any content in $\mathcal{C}_{i}$ for all $i\neq k$ . Fig. 1 shows popularity distribution of 100 contents given the preferred category, grouped into 5 categories consisting of 20 contents. This figure is obtained by multiplying the rank probability and the category-based individual content popularity, when $\gamma^{\text{out}}=5$ , $\gamma_{i}^{\text{in}}=2.4$ and $c^{\text{in}}=69$ . Among them, contents whose indices are from 1 to 20 belong to the first-ranked category, and their popularity is relatively much larger than others. Therefore, if $\gamma^{\text{out}}$ is sufficiently large, we approximate the popularity of contents outside the preferred $\mathcal{C}_{k}$ as uniform distribution, i.e., $a^{k}_{i,n}\approx\frac{1}{N-N_{k}}$ for all $i\in\mathcal{K}\setminus\{k\}$ and $n\in\mathcal{N}_{i}$ , irrespective of ranks of those categories. When given $\mathcal{C}_{k}$ , the popularity of contents in $\mathcal{C}_{k}$ is $a^{k}_{k,n}=a_{k,n}$ for $n\in\mathcal{N}_{k}$ still. Thus, consideration of two exclusive sets of the preferred category and all other contents is reasonable.

III Maximization of Cache Hit Probability

This section derives the cache hit probability and proposes a cache allocation rule that maximizes the cache hit probability.

III-A Cache hit probability

Suppose that the user request $l$ contents in sequence. Among $l$ contents, let $l_{r}$ contents belong to the $r$ -th ranked category satisfying $\sum_{r=1}^{K}l_{r}=l$ . Then, when the preferred category $\mathcal{C}_{k}$ is given, the cache hit probability given $l$ content requests, i.e., the probability that all of $l$ requested contents can be delivered from any caching node, can be expressed as

p_{\text{hit}}^{l,k}=\prod_{r=1}^{K}\Big{[}\mathrm{Pr}\{R=r\}h^{k}_{i_{r}}(\alpha_{i_{r}})\Big{]}^{l_{r}},

(2)

where $i_{r}\in\mathcal{K}$ is the index of the $r$ -th ranked category and

h^{k}_{i}(\alpha_{i})=1-\sum_{n=1}^{N_{i}}a^{k}_{i,n}\sum_{j=0}^{\infty}\mathrm{Pr}_{\Phi}\{J=j\}(1-b_{i,n}(\alpha_{i}))^{j},

(3)

is the cache hit probability of a content request within $\mathcal{C}_{i}$ given $\alpha_{i}$ when $\mathcal{C}_{k}$ is the preferred category. In Eq. (3), $\mathrm{Pr}_{\Phi}\{J=j\}$ is the probability that there are $j$ caching nodes storing the requested content in the vicinity of the user. Also, $b_{i,n}(\alpha_{i})$ is the caching probability of the $n$ -th content in $\mathcal{C}_{i}$ given $\alpha_{i}$ . However, computations required for scanning all combinations of $l_{r}$ values are exponentially increasing as $l$ grows.

When $\gamma^{\text{out}}$ is large, $p_{\text{hit}}^{l,k}$ is simplified by using approximations of $a^{k}_{i,n}\approx\frac{1}{N-N_{k}}$ , $\forall i\in\mathcal{K}\setminus\{k\}$ and $n\in\mathcal{N}_{i}$ into

p_{\text{hit}}^{l,k}\approx\sum_{m=0}^{l}\binom{l}{m}[p_{1}h^{k}_{k}(\alpha_{k})]^{m}\cdot[(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha})]^{l-m},

(4)

where

\displaystyle q_{k}(\boldsymbol{\alpha})=1-\sum_{\begin{subarray}{c}i=1\\ i\neq k\end{subarray}}^{K}\sum_{n=1}^{N_{i}}\frac{1}{N-N_{k}}\sum_{j=0}^{\infty}\mathrm{Pr}_{\Phi}\{J=j\}(1-b_{i,n}(\alpha_{i}))^{j}

(5)

which is the cache hit probability of a content request outside $\mathcal{C}_{k}$ . Each term in Eq. (4) is the probability that among $l$ requested contents, $m$ are in $\mathcal{C}_{k}$ and $l-m$ contents are outside $\mathcal{C}_{k}$ , and all of $l$ contents can be found in caching nodes in the vicinity of the user. For simplicity, we will use the notation $h_{k}(\alpha_{k})=h_{k}^{k}(\alpha_{k})$ in the following sections.

The expected cache hit probability can be finally derived as

	$\displaystyle p_{\text{hit}}$	$\displaystyle=\sum_{k=1}^{K}f_{k}\sum_{l=1}^{\infty}\mathrm{Pr}\{L=l\}\cdot\sum_{m=0}^{l}\binom{l}{m}[p_{1}h_{k}(\alpha_{k})]^{m}$
		$\displaystyle~{}~{}~{}~{}~{}\cdot[(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha})]^{l-m},$		(6)

where $\mathrm{Pr}\{L=l\}$ is the probability that the user requests $l$ contents in sequence, which is given by

\mathrm{Pr}\{L=l\}=\epsilon(1-\epsilon)^{l}.

(7)

Therefore, the cache hit probability is arranged into

	$\displaystyle p_{\text{hit}}$	$\displaystyle=\sum_{k=1}^{K}f_{k}\sum_{l=1}^{\infty}\epsilon(1-\epsilon)^{l}(p_{1}h_{k}(\alpha_{k})+(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha}))^{l}$		(8)
		$\displaystyle=\sum_{k=1}^{K}\frac{f_{k}(1-\epsilon)\epsilon(p_{1}h_{k}(\alpha_{k})+(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha}))}{1-(1-\epsilon)(p_{1}h_{k}(\alpha_{k})+(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha}))}$		(9)

Refer to caption — Figure 1: Popularity of contents given the preferred category

In Eq. (9), any caching policy can be utilized within each category given the preferred $\mathcal{C}_{k}$ and $\boldsymbol{\alpha}$ , and $h_{k}(\alpha_{k})$ and $q_{k}(\boldsymbol{\alpha})$ are determined depending on the caching policy. Then, we can suppose that the caching policy that maximizes the cache hit rate [4, 5] is used for caching of individual contents within every category. Denote the maximum cache hit rates in and outside $\mathcal{C}_{k}$ by $h_{k}^{*}(\alpha_{k})$ and $q_{k}^{*}(\boldsymbol{\alpha})$ , respectively. Then, the cache hit probability of $l$ content requests becomes

	$\displaystyle p^{*}_{\text{hit}}$	$\displaystyle=\sum_{k=1}^{K}\frac{f_{k}(1-\epsilon)\epsilon(p_{1}h^{}_{k}(\alpha_{k})+(1-\epsilon-p_{1})q^{}_{k}(\boldsymbol{\alpha}))}{1-(1-\epsilon)(p_{1}h^{}_{k}(\alpha_{k})+(1-\epsilon-p_{1})q^{}_{k}(\boldsymbol{\alpha}))}$		(10)
		$\displaystyle=\sum_{k=1}^{K}g^{*}_{k}(\boldsymbol{\alpha},f_{k},\epsilon).$		(11)

III-B Problem Formulation

The optimal cache allocations of $\boldsymbol{\alpha}^{\star}=(\alpha_{1}^{\star},\cdots,\alpha_{K}^{\star})$ can be obtained by maximizing (11) as follows:

	$\displaystyle\boldsymbol{\alpha}^{\star}=\underset{\boldsymbol{\alpha}}{\arg\max}~{}~{}p^{*}_{\text{hit}}$		(12)
	$\displaystyle~{}~{}~{}\text{s.t.}~{}\sum_{i=1}^{K}\alpha_{i}\leq M$		(13)
	$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}0\leq\alpha_{i}\leq\min\{M,N_{i}\},~{}\forall i\in\mathcal{K}.$		(14)

The constraint (13) is for the storage size of each caching node and the constraint (14) is for the cache allocation for each category. The following key lemmas are used to solve the above problem of (12)–(14).

Lemma 1.

$p_{1}h_{k}(\alpha_{k})+(1-\epsilon-p_{1})q_{k}(\boldsymbol{\alpha})$ is increasing with $\alpha_{k}$ .

Proof.

In this proof, we simply use the notation of $b_{i,n}=b_{i,n}(\alpha_{i}),~{}\forall i\in\mathcal{K},~{}\forall n\in\mathcal{N}_{i}$ . Let $\alpha^{\prime}_{k}=\alpha_{k}+\delta$ and $\delta>0$ . Then, $h^{*}_{k}(\alpha^{\prime}_{k})\geq\tilde{h}_{k}(\alpha^{\prime}_{k})$ , where $\tilde{h}_{k}(\alpha^{\prime}_{k})$ can be the cache hit probability within $\mathcal{C}_{k}$ of any caching policy $\mathbf{b}^{\prime}_{k}=(b^{\prime}_{k,1},\cdots,b^{\prime}_{k,N_{k}})^{T}$ satisfying $\sum_{n=1}^{N_{k}}b^{\prime}_{k,n}=\alpha^{\prime}_{k}$ . Let $\mathbf{b}^{\prime}_{k}=(b^{\prime}_{k,1}=b^{*}_{k,1}+\delta,b^{\prime}_{k,2}=b^{*}_{k,2}\cdots,b^{\prime}_{k,N_{k}}=b^{*}_{k,N_{k}})^{T}$ . Then, since $0\leq b_{k,1}^{*}\leq 1$ and $b_{k,1}^{*}$ is generally much closer to zero than one when the library size of $N$ is large,

	$\displaystyle p_{1}h^{}_{k}(\alpha^{\prime}_{k})-p_{1}h_{k}^{}(\alpha^{}_{k})\geq p_{1}\tilde{h}_{k}(\alpha^{\prime}_{k})-p_{1}h_{k}^{}(\alpha^{*}_{k})$
	$\displaystyle=p_{1}\sum_{n=1}^{N_{k}}a_{k,n}\sum_{j=0}^{\infty}\mathrm{Pr}_{\Phi}\{J=j\}\{(1-b^{*}_{k,n})^{j}-(1-b^{\prime}_{k,n})^{j}\}$		(15)
	$\displaystyle\approx p_{1}\cdot a_{k,1}\sum_{j=0}^{\infty}\mathrm{Pr}_{\Phi}\{J=j\}\cdot j\cdot\delta$		(16)

is obtained by using the first-order Taylor approximation, i.e., $(1-b^{*}_{k,n})^{j}\approx 1-j\cdot b^{*}_{k,n}$ .

Since the storage size $M$ is fixed, the cache size allocated to all categories except for $\mathcal{C}_{k}$ is $M-\alpha_{k}-\delta$ . With small $\delta$ , there exists any category $u$ for $u\neq k$ such that $\alpha_{u}\geq\delta$ . Then, let $\alpha^{\prime}_{u}=\alpha^{*}_{u}-\delta$ and $b^{\prime}_{u,1}=b^{*}_{u,1}-\eta_{1}$ , $b^{\prime}_{u,2}=b^{*}_{u,2}-\eta_{2}$ , $\cdots$ , $b^{\prime}_{u,N_{u}}=b^{*}_{u,N_{u}}-\eta_{N_{u}}$ , where $0\leq\eta_{u,n}\leq b^{*}_{u,n}$ for all $n\in\mathcal{N}_{u}$ and $\sum_{n=1}^{N_{u}}\eta_{u,n}=\delta$ . In this case, cache allocations for other categories can remain unchanged, i.e., $\alpha^{\prime}_{i}=\alpha^{*}_{i}$ and $b^{\prime}_{i,n}=b^{*}_{i,n}$ for all $i\in\mathcal{K},~{}i\neq k,u$ . Then, similar to before,

	$\displaystyle(1-\epsilon-p_{1})q^{}_{k}(\boldsymbol{\alpha^{\prime}})-(1-\epsilon-p_{1})q^{}_{k}(\boldsymbol{\alpha})\geq$
	$\displaystyle~{}\frac{1-\epsilon-p_{1}}{N-N_{k}}\bigg{[}\sum_{\begin{subarray}{c}i=1\\ i\neq k\end{subarray}}^{K}\sum_{n=1}^{N_{i}}\sum_{j=0}^{\infty}\mathrm{Pr}\{J=j\}\times$
	$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\Big{\{}(1-b_{i,n}^{*})^{j}-(1-b^{\prime}_{i,n})^{j}\Big{\}}\bigg{]}$		(17)
	$\displaystyle~{}\approx-\frac{1-\epsilon-p_{1}}{N-N_{k}}\sum_{j=0}^{J}\mathrm{Pr}\{J=j\}\cdot j\cdot\delta.$		(18)

Since $p_{1}>1-\epsilon-p_{1}$ and $a_{k,1}>\frac{1}{N-N_{k}}$ , $p_{1}h^{*}_{k}(\alpha^{\prime}_{k})+(1-\epsilon-p_{1})q^{*}_{k}(\boldsymbol{\alpha}^{\prime})-p_{1}h^{*}_{k}(\alpha_{k}^{*})-(1-\epsilon-p_{1})q^{*}_{k}(\boldsymbol{\alpha}^{*})>0$ and the above lemma is finally proved. ∎

Algorithm 1 Greedy cache allocation algorithm

\alpha^{*}_{i}=\frac{M}{K}

for all

i\in\mathcal{K}

and

p_{\text{hit}}^{\star}=0

2:for

\forall(u,v)\in\mathcal{K}\times\mathcal{K}

and

u\neq v

\beta_{u,v}=M-\alpha^{*}_{u}-\alpha^{*}_{v}

4: Obtain

b_{i,n}~{}\forall i\in\mathcal{K}

and

i\neq u,v

, and

\forall n\in\mathcal{N}_{i}

according to [4, 5].

5: for

\forall\alpha_{u}\in\{\max(0,\beta_{u,v}-N_{v}),\cdots,\min(\beta_{u,v},N_{u})\}

\alpha_{v}\leftarrow\beta_{u,v}-\alpha_{u}

7: Obtain

b_{u,n}

and

b_{v,m}

\forall n\in\mathcal{N}_{u}

and

\forall m\in\mathcal{N}_{v}

according to [4, 5].

8: Find

p_{\text{hit}}^{*}

based on

\boldsymbol{\alpha}

9: if

p_{\text{hit}}^{\star}<p_{\text{hit}}^{*}

then

p_{\text{hit}}^{\star}=p_{\text{hit}}^{*}

10: end if

11: end for

12:end for

Lemma 2.

The optimum vector $\boldsymbol{\alpha}^{\star}=(\alpha_{1}^{\star},\cdots,\alpha_{K}^{\star})^{T}$ satisfies $\sum_{i=1}^{K}\alpha_{i}^{\star}=M$ .

Proof.

Assume that $\sum_{i=1}^{K}\alpha^{\star}_{i}<M$ , then $\exists\delta>0$ such that $\sum_{i=1}^{K}\alpha^{\star}_{i}+\delta\leq M$ and $\alpha^{\star}_{k}+\delta<\min\{M,N_{k}\}$ for certain $k$ . Let $\boldsymbol{\alpha}^{\prime}=(\alpha^{\star}_{1},\cdots,\alpha_{k}^{\star}+\delta,\cdots,\alpha_{K}^{\star})^{T}$ . According to Lemma 1, $g_{k}^{*}(\boldsymbol{\alpha},f_{k},\epsilon)$ is increasing with $\alpha_{k}$ for all $k\in\mathcal{K}$ . Thus, $p_{\text{hit}}^{*}(\boldsymbol{\alpha}^{\prime})>p_{\text{hit}}^{*}(\boldsymbol{\alpha}^{\star})$ and it obviously leads to contradiction. ∎

According to Lemma 2, an inequality constraint (13) can be converted into the equality constraint. The problem of (12)–(14) has $K$ optimization parameters, and the subproblem for finding the optimal $\alpha_{u}^{\star}$ and $\alpha_{v}^{\star}$ is formulated as follows:

$\displaystyle\{\alpha^{\star}_{u},\alpha^{\star}_{v}\}$	$\displaystyle=\underset{\alpha_{u},\alpha_{v}}{\arg\max}~{}\mathcal{M}_{(u,v)}$	(19)
	$\displaystyle\text{s.t.}~{}\alpha_{u}+\alpha_{v}=\beta_{u,v}=M-\sum_{i=1,i\neq u,v}^{K}\alpha_{i}$	(20)
	$\displaystyle~{}~{}~{}~{}~{}0\leq\alpha_{i}\leq\min\{M,N_{i}\},~{}\forall i\in\mathcal{K},$	(21)

where $\mathcal{M}_{(u,v)}=g^{*}_{u}(\boldsymbol{\alpha},f_{u},\epsilon)+g^{*}_{v}(\boldsymbol{\alpha},f_{v},\epsilon)$ . Since $\{\alpha_{i}\}_{i\neq u,v}$ are fixed, $\alpha_{u}+\alpha_{v}$ also becomes a constant $\beta_{u,v}$ .

A multivariable function $p_{\text{hit}}^{*}$ can be optimized by iteratively optimizing the subset of variables if the convergence is guaranteed. To find $\boldsymbol{\alpha}^{\star}=(\alpha_{1}^{\star},\cdots,\alpha_{K}^{\star})$ , the subproblem of (19)–(21) can be iteratively applied for all combinations of $u$ and $v$ , for $u,v\in\mathcal{K}$ and $u\neq v$ . We find the maximum of the dual-variable problem of (19)–(21) in each iteration, and the sequence of the updated values of $\mathcal{M}_{(u,v)}$ is generated. Since this sequence is non-decreasing and the cache hit probability has a trivial upper bound of 1, i.e., $p_{\text{hit}}^{\star}\leq 1$ , the convergence of the iterative algorithm is guaranteed.

Since $h_{k}(\alpha_{k})$ and $q_{k}(\boldsymbol{\alpha})$ are obtained by using the bisection method [4, 5], however, the objective function of $\mathcal{M}_{(u,v)}$ is not in closed-form and the problem of (19)–(21) should be numerically handled. Therefore, we consider integer values for cache allocations of $\boldsymbol{\alpha}$ and the greedy algorithm can solve the problem with $M$ not very large. If caching of content partitions is not considered, i.e., only caching of the whole content is allowed, the assumption that $\alpha_{i}$ is the integer number for all $i\in\mathcal{K}$ is reasonable. The details of the iterative algorithm to solve the problem of (12)–(14) are described in Algorithm 1.

IV Maximization of expected number of consecutive content requests

From the service provider’s perspective, it is advantageous for the user to consume as many contents as possible. As explained in Section II, the user does not request the next content with the probability of $\epsilon$ . In addition, we assume that the user stops to consume the next content when no caching node in the vicinity of the user stores the desired content, even though the user requests the next one.

The probability of stopping to consume more is given by

p^{k}_{\text{stop}}=\epsilon+p_{1}(1-h_{k}(\alpha_{k}))+(1-\epsilon-p_{1})(1-q_{k}(\boldsymbol{\alpha})).

(22)

In (22), the first term is the probability of not requesting the next content, the second and third terms are probabilities that no caching node stores the requested content when the content belongs to $\mathcal{C}_{k}$ and is not in $\mathcal{C}_{k}$ , respectively. Then, the expected number of consecutive content consumption is computed as

	$\displaystyle\mathbb{E}[L]$	$\displaystyle=\sum_{l=1}^{\infty}l\cdot\mathrm{Pr}\{L=l\}=\sum_{k=1}^{K}f_{k}\sum_{l=1}^{\infty}l\cdot(1-p^{k}_{\text{stop}})^{l}p^{k}_{\text{stop}}$		(23)
		$\displaystyle=\sum_{k=1}^{K}f_{k}\frac{1-p^{k}_{\text{stop}}}{p^{k}_{\text{stop}}}.$		(24)

Then, the optimization problem of maximizing the expected number of consecutive video consumption is as follows:

	$\displaystyle\boldsymbol{\alpha}^{\star}=\underset{\boldsymbol{\alpha}}{\arg\max}~{}\mathbb{E}[L]$		(25)
	$\displaystyle~{}~{}~{}\text{s.t.}~{}\sum_{i=1}^{K}\alpha_{i}\leq M$		(26)
	$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}0\leq\alpha_{i}\leq\min\{M,N_{i}\},~{}\forall i\in\mathcal{K}.$		(27)

Similar to Lemmas 1 and 2, $p^{k}_{\text{stop}}$ can be proved to be increasing with $\alpha_{k}$ and the inequality constraint (26) can be converted into the equality constraint, i.e., $\sum_{i=1}^{K}\alpha_{i}=M$ .

Again, the multivariable function $\mathbb{E}[L]$ can be maximized by iteratively optimizing the following dual-variable subproblem:

	$\displaystyle\{\alpha^{\star}_{u},\alpha^{\star}_{v}\}=\underset{\alpha_{u},\alpha_{v}}{\arg\max}\frac{f_{u}}{p^{u}_{\text{stop}}}+\frac{f_{v}}{p^{v}_{\text{stop}}}$		(28)
	$\displaystyle~{}~{}\text{s.t.}~{}\alpha_{u}+\alpha_{v}=\beta_{u,v}=M-\sum_{i=1,i\neq u,v}^{K}\alpha_{i}$		(29)
	$\displaystyle~{}~{}~{}~{}~{}~{}~{}0\leq\alpha_{i}\leq\min\{M,N_{i}\},~{}\forall i\in\mathcal{K}.$		(30)

The sequence of the updated objective values in (28) is nondecreasing, and $\mathbb{E}[L]\leq\frac{1}{\epsilon}-1$ because $p^{k}_{\text{stop}}\geq\epsilon$ . Thus, the algorithm which solves the problem of (25)–(27) by iteratively optimizing the dual-variable problem of (28)–(30) for all combinations of $u,v\in\mathcal{K}$ and $u\neq v$ , is guaranteed to converge. The whole algorithm is the same as Algorithm 1 except that $p_{\text{hit}}^{*}$ should be changed into $\mathbb{E}[L]$ in lines 2, 9, 10.

V Numerical Results

In the subsequent simulations, $N=100$ contents and $K=5$ categories are considered. The global category popularity follows $f_{i}>f_{j}$ for $i<j$ . Caching nodes are distributed according to a Poisson point process with intensity of $\lambda$ and caching nodes with distances less than $d=10$ from the user are only considered. In addition, $M=30$ , $\gamma=1$ , $\gamma_{i}^{in}=2.4$ , and $c_{i}^{\text{in}}=69$ are used for all $i\in\mathcal{K}$ . We consider three different category structures as follows:

•

Case A: $N_{1}=N_{2}=N_{3}=N_{4}=N_{5}=20$
•

Case B: $N_{1}=35,N_{2}=25,N_{3}=20,N_{4}=15,N_{5}=5$
•

Case C: $N_{1}=5,N_{2}=15,N_{3}=20,N_{4}=25,N_{5}=35$ .

In Figs. 2 and 3, plots of $\alpha_{k}$ for every category are shown with $\lambda=0.02$ and $\epsilon=0.1$ . Case A is considered in Fig. 2. As the skew factor $\gamma^{\text{out}}$ grows, the probability of requesting the content in the preferred category becomes much larger than that of requesting the content in other categories. Therefore, as $\gamma^{\text{out}}$ increases, more cache sizes are allocated to categories having relatively large global category popularities in Fig 2.

In Fig. 3, all plots are obtained with $\gamma^{\text{out}}=5$ . Since all categories in Case A have the same number of contents, cache allocations of Case A depend only on global category popularity. In Case B, the category having a larger global popularity consists of more contents, therefore more cache sizes are allocated, i.e., $\alpha_{1}$ in Case B becomes larger than that in Case A. Interestingly, $\alpha_{5}$ in Case B is also larger than that in Case A. The reason is that $N_{5}$ is the smallest in Case B, i.e., the individual content popularity within $\mathcal{C}_{5}$ is the largest among all categories. Thus, even though $f_{5}$ is smaller than other $f_{i}$ values, caching multiple contents of $\mathcal{C}_{5}$ is favorable for consecutive content requests. On the other hand, in Case C, $\alpha_{1}$ is smaller than $\alpha_{2}$ , $\alpha_{3}$ and $\alpha_{4}$ because $N_{1}=5$ and $\alpha_{1}$ should be smaller than $N_{1}$ . It does not mean that an importance of caching contents in $\mathcal{C}_{1}$ decreases. Rather, it becomes more important because a portion of contents to be stored in caching nodes, i.e., $\frac{\alpha_{1}}{N_{1}}$ , is larger than other cases. By saving the cache size for $\mathcal{C}_{1}$ , a larger cache size can be allocated to other categories with low global popularities compared to Case A. Thus, Figs. 2 and 3 show that the skew factor as well as the number of contents in each category have a strong impact on the proposed cache allocation rule.

Fig. 4 shows plots of cache hit probabilities obtained from the problem of (12)–(14) versus $\lambda$ . In Fig. 5, the expected numbers of consecutive content consumption obtained from the problem of (25)–(27) are shown. We compared the proposed scheme with the conventional caching method optimized for one-shot content request based on popularity of individual contents in [4, 5]. The comparison scheme is named as ‘L1’ in the figures. We can easily see in both figures that the proposed scheme outperforms ‘L1’ with different valuess of $\gamma^{\text{out}}$ and $N_{i}$ for each category. As $\lambda$ grows, i.e., as the number of caching nodes in the vicinity of the user grows, the performance improvement of the proposed scheme decreases, because the user becomes more likely to find caching nodes to deliver multiple requested contents even with ‘L1’. The performance gain of the proposed scheme over ‘L1’ is guaranteed when $\gamma^{\text{out}}$ is large. Especially in Fig. 5, when $\epsilon=0.1$ , $\epsilon$ dominates the term in (22) representing the probability of stopping to consume contents; therefore, the advantage of the proposed scheme is not remarkable. As $\epsilon$ becomes smaller, however, the proposed algorithm is more advantageous for consecutive content consumption than ‘L1’. Thus, the service provider can create the opportunity for users to consume more contents and to stay in the service longer by using the proposed scheme.

VI Concluding Remarks

This paper proposes two optimal cache allocation rules when users request a random number of contents consecutively. The key characteristic that users are likely to consume content highly related to each other consecutively is well captured in the proposed scheme by maximizing the cache hit probability for multiple content requests from the same category. Another cache allocation which maximizes the number of consecutive content consumption is also proposed as it related to the benefits for the service providers. The impacts of categorized contents and consecutive content requests on the cache allocation rule are shown by numerical results.

Acknowledgment

This work was supported by NSF under projects NSF CCF-1423140 and NSF CNS-1816699, and Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No.2018-0-00170, Virtual Presence in Moving Objects through 5G).

References

[1] X. Cheng, J. Liu, and C. Dale, “Understanding the Characteristics of Internet Short Video Sharing: A YouTube-based Measurement Study,” IEEE Trans. on Multimedia, vol. 15, no. 5, pp. 1184–1194, August 2013.
[2] N. Golrezaei, K. Shanmugam, A. G. Dimakis, A. F. Molisch, and G. Caire, “FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers,” in Proc. IEEE INFOCOM, Orlando, FL, USA, 2012.
[3] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers,” IEEE Trans. on Inf. Theory, vol. 59, no. 12, pp. 8402–8413, December 2013.
[4] B. Blaszczyszyn and A. Giovanidis, “Optimal Geographic Caching in Cellular Networks,” in Proc. IEEE Int’l Conf. on Communications (ICC), London, UK, 2015.
[5] Z. Chen, N. Pappas, and M. Kountouris, “Probabilistic Caching in Wireless D2D Networks: Cache Hit Optimal Versus Throughput Optimal,” IEEE Commun. Letters, vol. 21, no. 3, pp. 584–587, March 2017.
[6] M. Ji, G. Caire, and A. F. Molisch, “Wireless Device-to-Device Caching Networks: Basic Principles and System Performance,” IEEE J. Sel. Areas in Commun., vol. 34, no. 1, pp. 176–189, Jan. 2016.
[7] K. Li, C. Yang, Z. Chen and M. Tao, “Optimization and Analysis of Probabilistic Caching in $N$ -Tier Heterogeneous Networks,” IEEE Trans. Wireless Commun., vol. 17, no. 2, pp. 1283-1297, Feb. 2018.
[8] M. Choi, J. Kim, and J. Moon, ”Wireless Video Caching and Dynamic Streaming Under Differentiated Quality Requirements,” IEEE J. Sel. Areas in Commun., vol. 36, no. 6, pp. 1245–1257, June 2018.
[9] D. Ko, B. Hong and W. Choi, “Probabilistic Caching Based on Maximum Distance Separable Code in a User-Centric Clustered Cache-Aided Wireless Network,” IEEE Trans. Wireless Commun., vol. 18, no. 3, pp. 1792-1804, March 2019.
[10] M. Cha, H. Kwak, P. Rodriguez, Y. Ahn and S. Moon, “Analyzing the Video Popularity Characteristics of Large-Scale User Generated Content Systems,” IEEE/ACM Trans. Network., vol. 17, no. 5, pp. 1357-1370, Oct. 2009.
[11] R. Zhou, S. Khemmarat, and L. Gao, “The impact of YouTube recommendation system on video views” in Proc. ACM IMC, New York, NY, USA, 404-410, 2010.
[12] M. Choi, D. Kim, D.-J. Han, J. Kim and J. Moon, “Probabilistic Caching Policy for Categorized Contents and Consecutive User Demands”, IEEE Int’l Conf. on Communications (ICC), May 2019.
[13] M. Lee, A. F. Molisch, N. Sastry and A. Raman, “Individual Preference Probability Modeling and Parameterization for Video Content in Wireless Caching Networks,” IEEE/ACM Trans. Network., 2019.