  We consider the problem of video caching across a set of 5G small-cell base
stations (SBS) connected to each other over a high-capacity short-delay
back-haul link, and linked to a remote server over a long-delay connection.
Even though the problem of minimizing the overall video delivery delay is
NP-hard, the Collaborative Caching Algorithm (CCA) that we present can
efficiently compute a solution close to the optimal, where the degree of
sub-optimality depends on the worst case video-to-cache size ratio. The
algorithm is naturally amenable to distributed implementation that requires
zero explicit coordination between the SBSs, and runs in $O(N + K \log K)$
time, where $N$ is the number of SBSs (caches) and $K$ the maximum number of
videos. We extend CCA to an online setting where the video popularities are not
known a priori but are estimated over time through a limited amount of periodic
information sharing between SBSs. We demonstrate that our algorithm closely
approaches the optimal integral caching solution as the cache size increases.
Moreover, via simulations carried out on real video access traces, we show that
our algorithm effectively uses the SBS caches to reduce the video delivery
delay and conserve the remote server's bandwidth, and that it outperforms two
other reference caching methods adapted to our system setting.
