all news >


all events >
  • Precision in education, communications and intelligence
    Dec 27Wed.

    Precision in education, communications and intelligence

    Academic Lecture
    Prof. Ren Desheng (Hong Kong University)

    Wednesday December 27th, 2017 at 13.30 PM
    Room 117, Xindian Building, Yuquan Campus




  • Adaptive algorithms for caching networks with optimality guarantees
    Dec 15Fri.

    Adaptive algorithms for caching networks with optimality guarantees

    Academic Lecture
    Prof. Edmund Yeh

    Friday December 15th, 2017 at 14.00 PM
    Conference Room 215, Xindian Building, Yuquan Campus





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


          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.