Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks.

Jean-Claude Bermond 1 Eitan Altman 2 Philippe Nain 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This work focuses on a class of distributed storage systems whose content may evolve over time. Each component or node of the storage system is mobile and the set of all nodes forms a delay tolerant (ad hoc) network (DTN). The goal of the paper is to study efficient ways for distributing evolving files within DTNs and for managing dynamically their content. We specify to dynamic files where not only the latest version is useful but also previous ones; we restrict however to files where a file has no use if another more recent version is available. There are $N+1$ mobile nodes including a {\em single} source which at some points in time makes available a new version of a {\em single} file $F$. We consider both the cases when (a) nodes do not cooperate and (b) nodes cooperate. In case (a) only the source may transmit a copy of the latest version of $F$ to a node that it meets, while in case (b) any node may transmit a copy of $F$ to a node that it meets. A file management policy is a set of rules specifying when a node may send a copy of $F$ to a node that it meets. The objective is to find file management policies which maximize some system utility functions under a constraint on the resource consumption. Both myopic ({\em static}) and state-dependent ({\em dynamic}) policies are considered, where the state of a node is the age of the copy of $F$ it carries. Scenario (a) is studied under the assumption that the source updates $F$ at discrete times $t=0,1,\ldots$. During a slot $[t,t+1)$ the source meets any node with a fixed probability. We find the optimal static (resp. dynamic) policy which maximizes a general utility function under a constraint on the number of transmissions within a slot. In particular, we show the existence of a threshold dynamic policy. In scenario (b) $F$ is updated at random points in time, with the consequence that between two meetings with the source a node does not know the age evolution of the version of $F$ it holds. Under Markovian assumptions regarding nodes mobility and update frequency of $F$, we study the stability of the system (aging of the nodes) and derive an (approximate) optimal static policy. We then revisit scenario (a) when the source does not know parameter $N$ (node population) and $q$ (node meeting probability) and derive a stochastic approximation algorithm which we show to converge to the optimal static policy found in the complete information setting. Numerical results illustrate the respective performance of optimal static and dynamic policies as well as the benefit of node cooperation.
Type de document :
Communication dans un congrès
INFOCOM 2009, Apr 2009, Rio de janeiro, Brazil. pp.1431-1439, 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00505520
Contributeur : Jean-Claude Bermond <>
Soumis le : vendredi 23 juillet 2010 - 23:09:22
Dernière modification le : mardi 17 août 2010 - 23:47:49

Identifiants

  • HAL Id : inria-00505520, version 1

Collections

Citation

Jean-Claude Bermond, Eitan Altman, Philippe Nain. Distributed Storage Management of Evolving Files in Delay Tolerant Ad Hoc Networks.. INFOCOM 2009, Apr 2009, Rio de janeiro, Brazil. pp.1431-1439, 2009. <inria-00505520>

Partager

Métriques

Consultations de la notice

147