  Cache advertisements reduce the access cost by allowing users to skip the
cache when it does not contain their datum. Such advertisements are used in
multiple networked domains such as 5G networks, wide area networks, and
information-centric networking. The selection of an advertisement strategy
exposes a trade-off between the access cost and bandwidth consumption. Still,
existing works mostly apply a trial-and-error approach for selecting the best
strategy, as the rigorous foundations required for optimizing such decisions is
lacking. Our work shows that the desired advertisement policy depends on
numerous parameters such as the cache policy, the workload, the cache size, and
the available bandwidth. In particular, we show that there is no ideal single
configuration. Therefore, we design an adaptive, self-adjusting algorithm that
periodically selects an advertisement policy. Our algorithm does not require
any prior information about the cache policy, cache size, or workload, and does
not require any apriori configuration. Through extensive simulations, using
several state-of-the-art cache policies, and real workloads, we show that our
approach attains a similar cost to that of the best static configuration (which
is only identified in retrospect) in each case.
