Erasure-coding based routing for opportunistic networks

Yong Wang, Sushant Jain, Margaret Rose Martonosi, Kevin Fall

Research output: Chapter in Book/Report/Conference proceedingConference contribution

150 Scopus citations

Abstract

Routing in Delay Tolerant Networks (DTN) with unpredictable node mobility is a challenging problem because disconnections are prevalent and lack of knowledge about network dynamics hinders good decision making. Current approaches are primarily based on redundant transmissions. They have either high overhead due to excessive transmissions or long delays due to the possibility of making wrong choices when forwarding a few redundant copies. In this paper, we propose a novel forwarding algorithm based on the idea of erasure codes. Erasure coding allows use of a large number of relays while maintaining a constant overhead, which results in fewer cases of long delays.We use simulation to compare the routing performance of using erasure codes in DTN with four other categories of forwarding algorithms proposed in the literature. Our simulations are based on a real-world mobility trace collected in a large outdoor wild-life environment. The results show that the erasure-coding based algorithm provides the best worst-case delay performance with a fixed amount of overhead. We also present a simple analytical model to capture the delay characteristics of erasure-coding based forwarding, which provides insights on the potential of our approach.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
Pages229-236
Number of pages8
DOIs
StatePublished - Dec 1 2005
EventACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005 - Philadelphia, PA, United States
Duration: Aug 26 2005Aug 26 2005

Publication series

NameProceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005

Other

OtherACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
CountryUnited States
CityPhiladelphia, PA
Period8/26/058/26/05

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • delay tolerant network
  • erasure coding
  • routing

Fingerprint Dive into the research topics of 'Erasure-coding based routing for opportunistic networks'. Together they form a unique fingerprint.

  • Cite this

    Wang, Y., Jain, S., Martonosi, M. R., & Fall, K. (2005). Erasure-coding based routing for opportunistic networks. In Proceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005 (pp. 229-236). (Proceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005). https://doi.org/10.1145/1080139.1080140