PROMOTE-ARC

First, we summarize the ARC algorithm [25]: ARC maintains $c$ pages in the cache and $c$ history pages. LRU list $T_1$ contains pages that have been seen only once recently, and $T_2$ contains the pages that have been seen at least twice recently. The addresses of the pages recently evicted from $T_1$ and $T_2$ are stored in $B_1$ and $B_2$, respectively. $\vert T_1\vert+\vert T_2\vert \le c$ is enforced, while the relative sizes of the lists are adapted according to the relative rates of hits in the corresponding history lists $B_1$ and $B_2$.

For simplicity, consider a single-path hierarchy of ARC caches (Figure 6). Theoretically, the caches could pass the marginal utility of the $T_1$ and $T_2$ lists to lower caches which could dynamically adapt $probPromote$ at each cache level to equalize the utility across the hierarchy. However, it can be challenging to adapt $probPromote$ in a stable way for both $T_1$ and $T_2$ lists at each level. We found a simple policy that works very well for ARC. For traffic destined for $T_1$ lists, $probPromote$ at each cache $C_k$ is set to a fixed value $\sum_{i=1}^{k-1}\vert C_i\vert / \sum_{i=1}^k\vert C_i\vert$. Instead of the cache life, the $life/occupancy$ of the $T_2$ list is passed to lower caches, where $occupancy$ is the fraction of the cache occupied by $T_2$. Merely using the cache life for $T_2$ list did not fare well, compared to DEMOTE-ARC, in unlimited bandwidth cases. The $probPromote$ for the $T_2$ lists is dynamically adapted at each level so as to equalize $life/occupancy$ across the hierarchy (Lines 41-43).

Another hint called the $T_2hint$ is used along with read requests and replies to indicate that the page should be stored in a $T_2$ list as it has been seen earlier (Line 46). If any cache decides to keep the page (Line 59), it creates the page in $T_2$ if $T_2hint$ is true; else it creates it in $T_1$.