Hierarchical Cache-Aided Networks for Linear Function Retrieval

2.1. System Model

• Placement phase: The mirror site M_k1 caches some parts of the files by using a cache function ${\phi }_{k_1}:{\mathbb{F}}_2^{NB}\to {\mathbb{F}}_2^{M_{1}B}$, where $\frac{M_1}{N}$ is the memory ratio of the mirror in the first layer, $M_1\in [0:N]$. The cache contents of mirror ${\mathrm{M}}_{k_1}$ are

  $${\mathcal{Z}}_{k_1}={\phi }_{k_1}\left(\mathcal{W}\right), k_1\in \left[K_1\right].$$
  The user ${\mathrm{U}}_{k_1,k_2}$ caches some parts of the files by using a cache function ${\varphi }_{k_1,k_2}:{\mathbb{F}}_2^{NB}\to {\mathbb{F}}_2^{M_{2}B}$, where $\frac{M_2}{N}$ is the memory ratio of users in the second layer, $M_2\in [0:N]$. Then, the cache contents of ${\mathrm{U}}_{k_1,k_2}$ are

  $${\tilde{\mathcal{Z}}}_{k_1,k_2}={\varphi }_{k_1,k_2}\left(\mathcal{W}\right),k_1\in \left[K_1\right], k_2\in \left[K_2\right].$$
• Delivery phase: Each user ${\mathrm{U}}_{k_1,k_2}$ randomly requests a linear combination of the files

  $$L_{k_1,k_2}=d_{k_1,k_2}^{\left(1\right)}{W}^{\left(1\right)}+d_{k_1,k_2}^{\left(2\right)}{W}^{\left(2\right)}+\dots +d_{k_1,k_2}^{\left(N\right)}{W}^{\left(N\right)}.$$

  for any $k_1\in \left[K_1\right],k_2\in \left[K_2\right]$, where ${\mathbf{d}}_{k_1,k_2}=(d_{k_1,k_2}^{\left(1\right)},\dots$, $d_{k_1,k_2}^{\left(N\right)})\in {\mathbb{F}}_2^N$ denotes the demand vector of user $U_{k_1,k_2}$. When each user requests a single file, the demand vector $d_{k_1,k_2}$ is a N-length unit vector. For example, if user ${\mathrm{U}}_{k_1,k_2}$ only requests the 1-st file, then the demand vector is set as ${\mathbf{d}}_{k_1,k_2}=(1,\dots ,0)\in {\mathbb{F}}_2^N,k_1\in \left[K_1\right],k_2\in \left[K_2\right]$, which is a special case of our proposed scheme. We can obtain the demand matrices of all users as follows:

  $${\mathbf{D}}^{\left(k_1\right)}=\left(\begin{array}{c}{\mathbf{d}}_{k_1,1}\\ ⋮\\ {\mathbf{d}}_{k_1,K_2}\end{array}\right),\mathbf{D}=\left(\begin{array}{c}{\mathbf{D}}^{\left(1\right)}\\ ⋮\\ {\mathbf{D}}^{\left(K_1\right)}\end{array}\right).$$

  (1)

  where ${\mathbf{D}}^{\left(k_1\right)}$ represents the demand vectors of ${\mathcal{U}}_{k_1}$. Given the demand matrix $\mathbf{D}$, we should consider the following two types of messages.

  –

  The messages sent by the server: The server generates signal $X^{\mathrm{server}}$ by using an encoding function $\chi :{\mathbb{F}}_2^{K_1{K}_{2}N}\times {\mathbb{F}}_2^{NB}\to {\mathbb{F}}_2^{R_{1}B}$, where

  $$X^{\mathrm{server}}=\chi (\mathbf{D},\mathcal{W}).$$

  and then the server sends $X^{\mathrm{server}}$ to the mirrors. The normalized number of transmissions $R_1$ is called the transmission load for the first layer.

  –

  The messages sent by the mirror: Based on $X^{\mathrm{server}}$, ${\mathcal{Z}}_{k_1}$, and $\mathbf{D}$, each mirror ${\mathrm{M}}_{k_1}$ generates a signal $X_{k_1}^{\mathrm{mirror}}$ by using the encoding function $\kappa :{\mathbb{F}}_2^{K_{2}N}\times {\mathbb{F}}_2^{M_{1}B}\times X^{\mathrm{server}}\to {\mathbb{F}}_2^{R_{2}B}$, where

  $$X_{k_1}^{\mathrm{mirror}}=\kappa ({\mathbf{D}}^{(k_1)},{\mathcal{Z}}_{k_1},X^{\mathrm{server}}).$$

  and then mirror ${\mathrm{M}}_{k_1}$ sends $X_{k_1}^{\mathrm{mirror}}$ to its connected users. The normalized number of transmissions $R_2$ is called the transmission load for the second layer.

  For the retrieval process, each user ${\mathrm{U}}_{k_1,k_2}$ can decode its required linear combination of files from $(\mathbf{D},{\tilde{\mathcal{Z}}}_{k_1,k_2},X_{k_1}^{\mathrm{mirror}})$, which means that there exist decoding functions ${\xi }_{k_1,k_2}:{\mathbb{F}}_2^{K_1{K}_{2}N}\times {\mathbb{F}}_2^{M_{2}B}\times {\mathbb{F}}_2^{R_{2}B}\to {\mathbb{F}}_2^B$, $k_1\in \left[K_1\right],k_2\in \left[K_2\right]$, such that

  $${\xi }_{k_1,k_2}(\mathbf{D},{\tilde{\mathcal{Z}}}_{k_1,k_2},X_{k_1}^{\mathrm{mirror}})=d_{k_1,k_2}^{\left(1\right)}{W}^{\left(1\right)}+\dots +d_{k_1,k_2}^{\left(N\right)}{W}^{\left(N\right)}.$$

2.2. Existing Schemes

4.1. An Example for Theorem 2

• Placement phase: Each file from ${\mathbb{F}}_2^B$ is divided into $\left(\genfrac{}{}{0pt}{}{3}{1}\right)\left(\genfrac{}{}{0pt}{}{2}{1}\right)=6$ subfiles with equal size, i.e., $W^{\left(n\right)}=\{W_{1,1}^{\left(n\right)}$, $W_{1,2}^{\left(n\right)},\dots ,W_{3,1}^{\left(n\right)},W_{3,2}^{\left(n\right)}\}$, $n\in \left[6\right]$. For simplicity, we represent a set that is the subscript of some studied object by a string. For example, ${\mathcal{T}}_{\{1,2\}}$ is represented by ${\mathcal{T}}_{12}$. The contents cached by the mirrors are as follows:

  $$\begin{array}{c}\hfill {\mathcal{Z}}_1=\{W_{1,1}^{\left(n\right)},W_{1,2}^{\left(n\right)}|n\in \left[6\right]\},{\mathcal{Z}}_2=\{W_{2,1}^{\left(n\right)},W_{2,2}^{\left(n\right)}|n\in \left[6\right]\},{\mathcal{Z}}_3=\{W_{3,1}^{\left(n\right)},W_{3,2}^{\left(n\right)}|n\in \left[6\right]\}.\end{array}$$
  The subfiles cached by the users are as follows:

  $$\begin{array}{c}\hfill {\tilde{\mathcal{Z}}}_{1,1}={\tilde{\mathcal{Z}}}_{2,1}={\tilde{\mathcal{Z}}}_{3,1}=\{W_{1,1}^{\left(n\right)},W_{2,1}^{\left(n\right)},W_{3,1}^{\left(n\right)}|n\in \left[6\right]\},\\ \hfill {\tilde{\mathcal{Z}}}_{1,2}={\tilde{\mathcal{Z}}}_{2,2}={\tilde{\mathcal{Z}}}_{3,2}=\{W_{1,2}^{\left(n\right)},W_{2,2}^{\left(n\right)},W_{3,2}^{\left(n\right)}|n\in \left[6\right]\}.\end{array}$$
• Delivery phase: In the delivery phase, the demand vectors with length 12 are ${\mathbf{d}}_{k_1,1}=(1,1,0,0,0,0),{\mathbf{d}}_{k_1,2}=(0,0,1,1,0,0),k_1\in \left[3\right]$. As we can see, ${\mathbf{D}}^{\left(1\right)}={\mathbf{D}}^{\left(2\right)}={\mathbf{D}}^{\left(3\right)}$. Without loss of generality, we set ${\mathcal{L}}_{\mathrm{M}}=\left\{1\right\}$. We denote a linear combination of subfiles as

  $$L_{{\mathbf{d}}_{k_1,k_2}{\mathcal{T}}_1,{\mathcal{T}}_2}=\sum _{n\in \left[N\right]}{\mathbf{d}}_{k_1,k_2}^{\left(n\right)}·W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}.$$

  where ${\mathcal{T}}_1\in \{\left\{1\right\},\left\{2\right\},\left\{3\right\}\}$ and ${\mathcal{T}}_2\in \{\left\{1\right\},\left\{2\right\}\}$, $k_1\in \left[3\right]$, $k_2\in \left[2\right]$. Then, the messages sent in this hierarchical system consist of the following two parts.

  –

  The messages sent by the server: The server generates signal $X_{\mathcal{A},\mathcal{B}}$ satisfying $\mathcal{A}\in \left(\genfrac{}{}{0pt}{}{\left[3\right]}{2}\right),\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[2\right]}{2}\right)$ and $\mathcal{A}\bigcap {\mathcal{L}}_{\mathrm{M}}\ne ⌀$ as follows:

  $$\begin{array}{cc}\hfill X_{12,12}=& L_{{\mathbf{d}}_{1,1},2,2}\oplus L_{{\mathbf{d}}_{1,2},2,1}\oplus L_{{\mathbf{d}}_{2,1},1,2}\oplus L_{{\mathbf{d}}_{2,2},1,1}\hfill \\ \hfill =& ({\oplus }_{i\in \left[2\right]}(W_{2,2}^{(i)}\oplus W_{1,2}^{(i)}))\oplus ({\oplus }_{i\in [3:4]}(W_{2,1}^{(i)}\oplus W_{1,1}^{(i)})),\hfill \\ \hfill X_{13,12}=& L_{{\mathbf{d}}_{1,1},3,2}\oplus L_{{\mathbf{d}}_{1,2},3,1}\oplus L_{{\mathbf{d}}_{3,1},1,2}\oplus L_{{\mathbf{d}}_{3,2},1,1}\hfill \\ \hfill =& ({\oplus }_{i\in \left[2\right]}(W_{3,2}^{(i)}\oplus W_{1,2}^{(i)}))\oplus ({\oplus }_{i\in [3:4]}(W_{3,1}^{(i)}\oplus W_{1,1}^{(i)})).\hfill \end{array}$$

  In this example, we have ${\mathcal{L}}_{\mathrm{M}}=\left\{1\right\}$, and $\mathcal{A}=\{2,3\}$ has no intersection with ${\mathcal{L}}_{\mathrm{M}}$. Here, we have $\mathcal{C}={\mathcal{L}}_{\mathrm{M}}\bigcup \mathcal{A}=\{1,2,3\}$ and ${\mathfrak{V}}_{\mathcal{C}}=\{\left\{1\right\},\left\{2\right\},\left\{3\right\}\}$. By Lemma 2, we can generate $X_{23,12}=X_{12,12}+X_{13,12}=({\oplus }_{i\in \left[2\right]}(W_{3,2}^{(i)}\oplus W_{2,2}^{(i)}))\oplus ({\oplus }_{i\in [3:4]}(W_{3,1}^{(i)}\oplus W_{2,1}^{(i)}))$. Thus, the transmission load of the first layer is $R_1=\frac{3-1}{6}=1/3$.

  –

  The messages sent by mirror ${\mathrm{M}}_{k_1}$: Here, we take mirror ${\mathrm{M}}_1$ as an example. From $D^{(1)}$, we have ${\mathcal{L}}_1=\{1,2\}$, and ${\mathrm{M}}_1$ transmits $X_{{\mathcal{T}}_1,\mathcal{B}}^{(1)}$, where ${\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[3\right]}{1}\right)$, $\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[2\right]}{2}\right)$, $\mathcal{B}\bigcap {\mathcal{L}}_1\ne \varnothing$, i.e.,

  $$\begin{array}{cc}\hfill X_{2,12}^{(1)}& =X_{12,12}-X_{1,12}^{(2)}=({\oplus }_{i\in \left[2\right]}{W}_{2,2}^{(i)})\oplus ({\oplus }_{i\in [3:4]}{W}_{2,1}^{(i)}),\hfill \\ \hfill X_{3,12}^{(1)}& =X_{13,12}-X_{1,12}^{(3)}=({\oplus }_{i\in \left[2\right]}{W}_{3,2}^{(i)})\oplus ({\oplus }_{i\in [3:4]}{W}_{3,1}^{(i)}),\hfill \\ \hfill X_{1,12}^{(1)}& =W_{1,2}^{(1)}\oplus W_{1,2}^{(2)}\oplus W_{1,1}^{(3)}\oplus W_{1,1}^{(4)}.\hfill \end{array}$$

  Then, the transmission amount by mirror ${\mathrm{M}}_1$ is 3 packets, and the transmission load of the second layer is $R_2=\frac{3}{6}=\frac{1}{2}$.

4.2. General Description of Scheme for Theorem 2

• Placement phase: Firstly, we divide each file into $\left(\genfrac{}{}{0pt}{}{K_1}{t_1}\right)$ equal-size subfiles; then, we further divide each subfile into $\left(\genfrac{}{}{0pt}{}{K_2}{t_2}\right)$ sub-subfiles. The index of subfiles consists of two parts, ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$, i.e., $W^{\left(n\right)}=\{W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}|{\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right),{\mathcal{T}}_2\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2}\right)\}$, $n\in \left[N\right]$. Each mirror site ${\mathrm{M}}_{k_1},k_1\in \left[K_1\right]$ caches subfiles $W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}$ according to the following rule, which is mainly related to the first subscript ${\mathcal{T}}_1$.

  $${\mathcal{Z}}_{k_1}=\left\{W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}|{\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right),{\mathcal{T}}_2\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2}\right),k_1\in {\mathcal{T}}_1,n\in \left[N\right]\right\}.$$
  Similarly, each user ${\mathrm{U}}_{k_1,k_2}$, $k_1\in \left[K_1\right],k_2\in \left[K_2\right]$ caches subfiles $W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}$ according to the following rule, which is mainly related to the second subscript ${\mathcal{T}}_2$.

  $${\tilde{\mathcal{Z}}}_{k_1,k_2}=\left\{W_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)}|{\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right),{\mathcal{T}}_2\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2}\right),k_2\in {\mathcal{T}}_2,n\in \left[N\right]\right\}.$$
  Under this caching strategy, we can verify that it satisfies the memory constraints stated in Theorem 2. Each mirror caches $\left(\genfrac{}{}{0pt}{}{K_1-1}{t_1-1}\right)\left(\genfrac{}{}{0pt}{}{K_2}{t_2}\right)N$ subfiles and each user caches $\left(\genfrac{}{}{0pt}{}{K_1}{t_1}\right)\left(\genfrac{}{}{0pt}{}{K_2-1}{t_2-1}\right)N$ subfiles, where each subfile is $B/\left(\genfrac{}{}{0pt}{}{K_1}{t_1}\right)\left(\genfrac{}{}{0pt}{}{K_2}{t_2}\right)$ bits. Thus, the memory ratios of the mirror and user are $\frac{M_1}{N}=\frac{t_1}{K_1}$ and $\frac{M_2}{N}=\frac{t_2}{K_2}$, respectively. For any user’s demand vector ${\mathbf{d}}_{{\mathbf{k}}_{\mathbf{1}},{\mathbf{k}}_{\mathbf{2}}}=(d_{k_1,k_2}^{\left(1\right)},\dots ,d_{k_1,k_2}^{\left(N\right)})$ of N-length, we use the notation as follows to denote a linear combination of subfiles:

  $$\begin{array}{c}\hfill L_{{\mathbf{d}}_{k_1,k_2}{\mathcal{T}}_1,{\mathcal{T}}_2}=\sum _{n\in \left[N\right]}{\mathbf{d}}_{k_1,k_2}^{\left(n\right)}{W}_{{\mathcal{T}}_1,{\mathcal{T}}_2}^{\left(n\right)},{\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right),{\mathcal{T}}_2\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2}\right).\end{array}$$

  (7)
• Delivery phase: For the convenience of the subsequent discussion, we first give the following two definitions of the signals transmitted in the first layer, say $X_{\mathcal{A},\mathcal{B}}$, and the second layer, say $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$. For any mirror set containing $t_1+1$ mirrors defined as $\mathcal{A}\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1+1}\right)$, any mirror site set containing $t_1$ mirror sites defined as ${\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right)$, and any user set containing $t_2+1$ users defined as $\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2+1}\right)$, we define

  $$\begin{array}{cc}\hfill X_{\mathcal{A},\mathcal{B}}=& \sum _{k_1\in \mathcal{A}}\sum _{k_2\in \mathcal{B}}{L}_{{\mathbf{d}}_{k_1,k_2},\mathcal{A}\setminus \left\{k_1\right\},\mathcal{B}\setminus \left\{k_2\right\}},\hfill \end{array}$$

  (8)

  $$\begin{array}{cc}\hfill X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}=& \sum _{k_2\in \mathcal{B}}{L}_{{\mathbf{d}}_{k_1,k_2},{\mathcal{T}}_1,\mathcal{B}\setminus \left\{k_2\right\}}.\hfill \end{array}$$

  (9)
  After the demand matrix $\mathbf{D}$ of size $K_1{K}_2\times N$ and its sub-matrix ${\mathbf{D}}^{\left(k_1\right)}$ of size $K_2\times N$ in (1) are revealed, we have the leader mirror set ${\mathcal{L}}_{\mathrm{M}}$ according to Definition 1. For each sub-matrix ${\mathbf{D}}^{\left(k_1\right)}$ of $\mathbf{D}$, $k_1\in \left[K_1\right]$, we have the leader user set ${\mathcal{L}}_{k_1}$, ${\mathcal{L}}_{k_1}\subseteq \left[K_2\right]$ according to Definition 2. There are two types of messages transmitted by the server and mirror, respectively.

  –

  The messages sent by the server: For each $\mathcal{A}\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1+1}\right)$, $\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2+1}\right)$, ${\mathcal{L}}_{\mathrm{M}}\bigcap \mathcal{A}\ne \varnothing$, the server transmits $X_{\mathcal{A},\mathcal{B}}$ to the mirror sites.

  –

  The messages sent by the mirror: Mirror site ${\mathrm{M}}_{k_1}$ transmits $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$ via the following rules.

  (1) For each ${\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right)$, $k_1\notin {\mathcal{T}}_1$, $\mathcal{A}={\mathcal{T}}_1\bigcup \left\{k_1\right\}$, $\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2+1}\right)$, $\mathcal{B}\bigcap {\mathcal{L}}_{k_1}\ne \varnothing$, mirror ${\mathrm{M}}_{k_1}$ transmits $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$ by subtracting ${\sum }_{k_1^{\prime }\in {\mathcal{T}}_1}{X}_{\mathcal{A}\setminus \left\{k_1^{\prime }\right\},\mathcal{B}}^{\left(k_1^{\prime }\right)}$ from $X_{\mathcal{A},\mathcal{B}}$, i.e.,

  $$\begin{array}{c}\hfill X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}=X_{\mathcal{A},\mathcal{B}}-\sum _{k_1^{\prime }\in {\mathcal{T}}_1}{X}_{\mathcal{A}\setminus \left\{k_1^{\prime }\right\},\mathcal{B}}^{\left(k_1^{\prime }\right)}.\end{array}$$

  (2) For each ${\mathcal{T}}_1\in \left(\genfrac{}{}{0pt}{}{\left[K_1\right]}{t_1}\right)$, $k_1\in {\mathcal{T}}_1$, $\mathcal{B}\in \left(\genfrac{}{}{0pt}{}{\left[K_2\right]}{t_2+1}\right)$, $\mathcal{B}\bigcap {\mathcal{L}}_{k_1}\ne \varnothing$, mirror ${\mathrm{M}}_{k_1}$ directly transmits $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$ to its connected users generated from its cached content ${\mathcal{Z}}_{k_1}$.

  As regards the messages $X_{\mathcal{A},\mathcal{B}}$, $\mathcal{A}\bigcap {\mathcal{L}}_{\mathrm{M}}=\varnothing$, and $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$, $\mathcal{B}\bigcap {\mathcal{L}}_{k_1}=\varnothing$, which are also necessary for the users, these messages can be computed from the sent messages by using Lemmas 1 and 2. More precisely, $X_{\mathcal{A},\mathcal{B}}$, $\mathcal{A}\bigcap {\mathcal{L}}_{\mathrm{M}}=\varnothing$ can be obtained by (5), and $X_{{\mathcal{T}}_1,\mathcal{B}}^{\left(k_1\right)}$, $\mathcal{B}\bigcap {\mathcal{L}}_{k_1}=\varnothing$ can be obtained by (6).