  Cloud services and other shared third-party infrastructures allow individual
content providers to easily scale their services based on current resource
demands. In this paper, we consider an individual content provider that wants
to minimize its delivery costs under the assumptions that the storage and
bandwidth resources it requires are elastic, the content provider only pays for
the resources that it consumes, and costs are proportional to the resource
usage. Within this context, we (i) derive worst-case bounds for the optimal
cost and competitive cost ratios of different classes of "cache on $M^{th}$
request" cache insertion policies, (ii) derive explicit average cost
expressions and bounds under arbitrary inter-request distributions, (iii)
derive explicit average cost expressions and bounds for short-tailed
(deterministic, Erlang, and exponential) and heavy-tailed (Pareto)
inter-request distributions, and (iv) present numeric and trace-based
evaluations that reveal insights into the relative cost performance of the
policies. Our results show that a window-based "cache on $2^{nd}$ request"
policy using a single threshold optimized to minimize worst-case costs provides
good average performance across the different distributions and the full
parameter ranges of each considered distribution, making it an attractive
choice for a wide range of practical conditions where request rates of
individual file objects typically are not known and can change quickly.

Networking and Internet Architecture;Distributed, Parallel, and Cluster Computing;Performance