Estimating end-to-end delays under changing conditions

Abstract : We consider the problem of estimating the end-to-end latency of intermittently connected paths in disruption/delay tolerant networks. This is useful when performing source routing, in which a complete path is chosen for a packet to travel from source to destination (when intermediate nodes are really low complexity devices that can only forward packets but cannot perform route computations), or in linear network topologies. While computing the time to traverse such a path may be straightforward in fixed, static networks, doing so becomes much more challenging in dynamic networks, in which the state of an edge in one timeslot (i.e., its presence or absence) is random, and may depend on its state in the previous timeslot. The traversal time is due to both time spent waiting for edges to appear and time spent crossing them once they become available. We compute the expected traversal time (ETT) for a dynamic path in a number of special cases of stochastic edge dynamics models, and for three different edge failure models, culminating in a surprisingly nontrivial yet realistic ''hybrid network" setting in which the initial configuration of edge states for the entire path is known. We show that the ETT for this "initial configuration" setting can be computed in quadratic time (as a function of path length), by an algorithm based on probability generating functions. We also give several linear-time upper and lower bounds on the ETT, which we evaluate, along with our ETT algorithm, using numerical simulations.
Type de document :
Communication dans un congrès
CHANTS - 8th ACM MobiCom workshop on Challenged networks, Sep 2013, Miami, Florida, United States. pp.1-6, 2013, 〈10.1145/2505494.2505495〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00933322
Contributeur : Sara Alouf <>
Soumis le : lundi 20 janvier 2014 - 12:43:46
Dernière modification le : jeudi 21 juin 2018 - 16:38:01

Identifiants

Collections

Citation

Philippe Nain, Don Towsley, Amotz Bar-Noy, Prithwish Basu, Matthew P. Johnson, et al.. Estimating end-to-end delays under changing conditions. CHANTS - 8th ACM MobiCom workshop on Challenged networks, Sep 2013, Miami, Florida, United States. pp.1-6, 2013, 〈10.1145/2505494.2505495〉. 〈hal-00933322〉

Partager

Métriques

Consultations de la notice

149