Adaptive Caching Networks with Optimality Guarantees

13 Jul
Wednesday, 07/13/2016 11:00am
Computer Science Building, Room 151
Seminar

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 conte!
nt 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.

Bio: 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.