Home

Adaptive Algorithms for Caching Networks with Optimality Guarantees


Speaker

Prof. Edmund Yeh, Northeastern University

Time

2017-12-11 10:00:00 ~ 2017-12-11 11:00:00

Location

SEIEE-1-418A

Host

Xinbing Wang John Hopcroft Center, Department of Electronic Engineering Shanghai Jiao Tong University

Abstract
We study the problem of optimal content placement over a network of caches This problem arises naturally 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 constructs 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
Bio
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 received the Best Paper Award at the 2017 ACM Conference on Information-centric Networking (ICN), and at the 2015 IEEE International Conference on Communications (ICC) Communication Theory Symposium.
© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University
分享到

地址:上海市东川路800号上海交通大学软件大楼专家楼
邮箱:jhc@sjtu.edu.cn 电话:021-54740299
邮编:200240