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

161 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 ACM SIGCOMM 2005 Workshops
Subtitle of host publicationConference on Computer Communications
Pages229-236
Number of pages8
StatePublished - Dec 30 2005
EventACM SIGCOMM 2005 Workshops: Conference on Computer Communications - Philadelphia, PA, United States
Duration: Aug 22 2005Aug 26 2005

Publication series

NameProceedings of ACM SIGCOMM 2005 Workshops: Conference on Computer Communications

Other

OtherACM SIGCOMM 2005 Workshops: Conference on Computer Communications
CountryUnited States
CityPhiladelphia, PA
Period8/22/058/26/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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 ACM SIGCOMM 2005 Workshops: Conference on Computer Communications (pp. 229-236). (Proceedings of ACM SIGCOMM 2005 Workshops: Conference on Computer Communications).