The Age of Impatience: Optimal Replication Schemes
for Opportunistic Networks

Augustin Chaintreau
Thomson Technology Paris Laboratory

 

Wednesday, November 18, 2pm
Location: BA 5256 

Abstract:

As the number of mobile users increases, and cell phones become more powerful, delivering rich content to them using a centralized infrastructure becomes both expensive and inadequate. Here we study an alternative p2p solution, which leverages local dedicated caches on these devices to opportunistically fulfill other user requests, in a peer-to-peer manner. In this talk, we address the general problem of choosing, and maintaining, the right "allocation" of content items to these caches, to fulfill the demand of all users in a timely manner.

We first show that the allocation's efficiency itself is determined by a previously overlooked factor, the "impatience" of content requesters. Optimal allocations corresponding to scenarios following different delay utility functions can be poles apart. However, we present a general convexity result, applying to any population of impatient users, which allows to build this optimal allocation efficiently. We then prove that, although no global cache state can be maintained in such opportunistic environment, the optimal cache allocation can be approached by simple reactive replication algorithms that use only local knowledge. This result is presented here for a homogeneous network; it generalizes to much more complex system with heterogeneity, leading to some open questions regarding the connection between human mobility and user profiling for content sharing.

This is joint work with Joshua Reich from Columbia University.

Bio:

A. Chaintreau joined Thomson, soon after graduating in 2006 from INRIA-Ecole Normale Superieure Paris, to work on emerging networking applications and technologies. His research includes projects on social networking, peer-to-peer applications on top of wireless and mobile networks, and the challenges and opportunities arising for routing, resource allocation, congestion control, caching, content search and recommendation. During his Ph.D he worked in collaboration with Alcatel Bell, as well as the IBM Watson T. J. Research Center, on the scalability of TCP controlled P2P delivery systems. He also worked for a year at Intel Research on the measurement of human mobility and its consequences on ad-hoc dissemination. The team in Thomson is always looking for interns and post-doc, and you are welcome to contact him if you think your research could contribute to one of these topics.