EE Systems Seminar

Abstract: The problem of optimal content placement over a network of caches arises in several contexts, including information-centric networks (ICNs), content delivery networks (CDNs), and peer-to-peer (P2P) networks.  Under a set of demands and routes that requests follow, we wish to determine the content placement across the network that maximizes the expected caching gain, i.e., the reduction of routing costs due to intermediate caching.  This objective is not convex, and the offline version of this problem is NP-hard.  We seek adaptive algorithms for assigning content to caches that operate without prior knowledge of the demand.  We propose a distributed, adaptive algorithm that performs stochastic gradient ascent on a concave relaxation of the caching gain, and construct a probabilistic content placement within a 1-1/e approximation factor from the optimal allocation, in expectation.  Motivated by our analysis, we also propose a simpler adaptive heuristic, and show through numerical evaluations that both algorithms significantly outperform traditional algorithms like LRU and LFU over a broad array of network topologies.   Next, we focus on the more general problem of jointly optimizing caching and routing decisions to minimize routing costs over an arbitrary network topology.  We show that our concave relaxation approach extends to this more general setting, and produce distributed, adaptive algorithms with the same approximation guarantees.  The resulting algorithms are shown to outperform the state of the art by several orders of magnitude.

Joint work with Stratis Ioannidis

Biography: Edmund Yeh received his B.S. in Electrical Engineering with Distinction and Phi Beta Kappa from Stanford University in 1994.  He then studied at Cambridge University on the Winston Churchill Scholarship, obtaining his M.Phil in Engineering in 1995.  He received his Ph.D. in Electrical Engineering and Computer Science from MIT under Professor Robert Gallager in 2001.  He is currently Professor of Electrical and Computer Engineering at Northeastern University. He was previously Assistant and Associate Professor of Electrical Engineering, Computer Science, and Statistics at Yale University. He has held visiting positions at MIT, Stanford, Princeton, UC Berkeley, NYU, EPFL, and TU Munich.  Professor Yeh was one of the PIs on the original NSF-funded FIA Named Data Networking project.  He will serve as General Co-Chair for ACM Conference on Information Centric Networking (ICN) 2018 in Boston.  He is the recipient of the Alexander von Humboldt Research Fellowship, the Army Research Office Young Investigator Award, the Winston Churchill Scholarship, the National Science Foundation and Office of Naval Research Graduate Fellowships, the Barry M. Goldwater Scholarship, the Frederick Emmons Terman Engineering Scholastic Award, and the President's Award for Academic Excellence (Stanford University).  Professor Yeh has served as the Secretary of the Board of Governors of the IEEE Information Theory Society, as well as Associate Editor for IEEE Transactions on Networking, IEEE Transactions on Mobile Computing, and IEEE Transactions on Network Science and Engineering.  He has received three Best Paper Awards, including awards at the 2017 ACM Conference on Information-Centric Networking (ICN), and at the 2015 IEEE International Conference on Communications (ICC) Communication Theory Symposium.