The analysis of temporal connectivity graphs associated to real mobility traces in structureless Delay Tolerant Networks (DTN) has revealed the existence of a portion of nodes, called hubs, appearing frequently in optimal paths connecting arbitrary node pairs. Based on these findings, hub-based routing has become one of the most promising strategies in order to successfully deliver messages in DTNs. Considering human mobility traces, we empirically prove that the selection of a suitable set of hubs as relays, not only ensures the same probability of successful delivery, but also leads to a decrease in the mean shortest path length, combined with a limited increase of the delivery time with respect to the optimal case. By analyzing the empirical distributions of path length and travel times, we study the conditions for the best trade-off between delay-optimal and delay-sub-optimal shortest paths, which uniquely depends on the number of hubs enabled as forwarders. This analysis turns out to be useful in the design of energy-saving routing algorithms based on epidemic propagation. We found that in some real experiments, using a very little set of hubs (under 50%) and limiting the number of hops per packet to three (corresponding to the mean delay-optimal shortest path length), epidemic routing guaranteed a delivery ratio around 90%, when tolerating at most double travel time only for a little fraction of messages.

Trade-off between hops and delays in hub-based forwarding in DTNs / A. Adamo, G. Grossi, F. Pedersini - In: 2010 IFIP Wireless days : Venice (Italy), october 20-22, 2010Piscataway : IEEE, 2010. - ISBN 9781424492305. (( convegno IFIP Wireless Days tenutosi a Venezia, Italy nel 2010 [10.1109/WD.2010.5657728].

Trade-off between hops and delays in hub-based forwarding in DTNs

A. Adamo
Primo
;
G. Grossi
Secondo
;
F. Pedersini
Ultimo
2010

Abstract

The analysis of temporal connectivity graphs associated to real mobility traces in structureless Delay Tolerant Networks (DTN) has revealed the existence of a portion of nodes, called hubs, appearing frequently in optimal paths connecting arbitrary node pairs. Based on these findings, hub-based routing has become one of the most promising strategies in order to successfully deliver messages in DTNs. Considering human mobility traces, we empirically prove that the selection of a suitable set of hubs as relays, not only ensures the same probability of successful delivery, but also leads to a decrease in the mean shortest path length, combined with a limited increase of the delivery time with respect to the optimal case. By analyzing the empirical distributions of path length and travel times, we study the conditions for the best trade-off between delay-optimal and delay-sub-optimal shortest paths, which uniquely depends on the number of hubs enabled as forwarders. This analysis turns out to be useful in the design of energy-saving routing algorithms based on epidemic propagation. We found that in some real experiments, using a very little set of hubs (under 50%) and limiting the number of hops per packet to three (corresponding to the mean delay-optimal shortest path length), epidemic routing guaranteed a delivery ratio around 90%, when tolerating at most double travel time only for a little fraction of messages.
Settore INF/01 - Informatica
Settore ING-INF/03 - Telecomunicazioni
IEEE
IFIP
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/154417
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact