Adaptive Caching Networks with Optimality Guarantees

Date: 11:00am, May 13, 2016
Location: CS Open area (CSB 477)
Speaker:   Prof. Stratis Ioannidis, Northeastern University

Abstract:    The problem of optimal content placement over a network of caches naturally arises in many networking applications, and has received considerable attention recently in the context of CCNs. Given the content demand, described by content requests and paths they follow, one wishes to determine the content placement that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching. The offline version of this problem is NP-hard. To make matters worse, in most cases, both the demand and the network topology may be a priori unknown; hence, a distributed, adaptive, constant approximation content placement algorithm is desired.

We show that path replication, an algorithm encountered often in both networking literature and in practice, can be arbitrarily suboptimal when combined with traditional cache eviction policies, like LRU, LFU, or FIFO. We propose a distributed, adaptive algorithm that provably constructs a probabilistic content placement within 1−1/e factor from the optimal, in expectation. We also propose a simple greedy eviction policy to be used with path replication, and show through numerical evaluations that both algorithms significantly outperform path replication with traditional eviction policies over a broad array of network topologies.

Biography:    Stratis Ioannidis is an assistant professor in the ECE Department of Northeastern University, in Boston, MA. 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.

Hosted by Professor Augustin Chaintreau

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University