The Age of Impatience: Optimal Replication Schemes for Opportunistic Networks
Event details
| Date | 04.09.2009 |
| Hour | 11:15 |
| Speaker | Augustin Chaintreau, Thomson Labs |
| Location | |
| Category | Conferences - Seminars |
Mobile P2P content dissemination may leverage the local dedicated
caches provided by hand-held devices (e.g. smart-phones) and
opportunistic contacts between these devices (e.g. via Bluetooth or
WiFi). In such a distributed environment, each opportunistic contact
represents a current opportunity to replicate local cache content to
fulfill future demand. How and when to replicate depends on the
heterogeneous popularity of items, as well as users's impatience (i.e.
as time passes without fulfillment, the demanding peer loses interest
with increasing probability). This poses the new question on how to
ensure timely fullfilment by mobile caches in the presence of
ephemeral fashions among users.
In this talk, we present results indicating that this cache allocation
problem can be well understood and sometimes solved solely through the
use of locally available information. We first prove that for any
impatience model and general nodes mobility, the efficiency of a cache
allocation satisfy a submodularity property. In the simple case of
homogeneous mobility among a group of nodes, this reduces to a unique
optimal allocation which can be fully characterized. Moreover, a
simple adaptive algorithm called "Query Counting Replication" produces
this optimal allocation with no a priori knowledge of nodes' demand
and current allocation state. We present some results of an early
specification of this algorithm on tops of various mobility traces,
which emphasizes the importance of a "mandate routing" feature to be
implemented along with this replication rule. The talk will conclude
with future works left open by these early steps, for more general
mobility cases and efficient recommendation engines.
Practical information
- General public
- Free
Contact
- Jean-Yves Le Boudec