Abstract

We study cache networks, i.e., networks in which any node can act as a cache and serve incoming requests. Network traffic in cache networks is determined not only by demand but, crucially, by where objects are stored. We wish to determine how to place objects in such a network to minimize data transfer costs. We show that this optimization problem can be cast as an NP-hard submodular maximization problem subject to matroid constraints, and present constant approximation algorithms for its solution, both in the offline and distributed/adaptive setting. We also discuss how this submodularity structure arises in more complex network models, including ones that account for queueing delays, incorporate fairness objectives, or when caching and routing are jointly optimized; we show that all of these scenarios come with polynomial-time approximation guarantees.

Bio: Stratis Ioannidis is an associate professor in the Electrical and Computer Engineering Department of Northeastern University, in Boston, MA, where he also holds a courtesy appointment with the College of Computer and Information Science. He received his B.Sc. (2002) in Electrical and Computer Engineering from the National Technical University of Athens, Greece, and his M.Sc. (2004) and Ph.D. (2009) in Computer Science from the University of Toronto, Canada. Prior to joining Northeastern, he was a research scientist at the Technicolor research centers in Paris, France, and Palo Alto, CA, as well as at Yahoo Labs in Sunnyvale, CA. He is the recipient of an NSF CAREER award, a Google Faculty Research award, a Facebook Research award, and several best paper awards.