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

158 Scopus citations


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
Number of pages8
StatePublished - 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


OtherACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
Country/TerritoryUnited States
CityPhiladelphia, PA

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications


  • delay tolerant network
  • erasure coding
  • routing


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

Cite this