TY - GEN
T1 - Erasure-coding based routing for opportunistic networks
AU - Wang, Yong
AU - Jain, Sushant
AU - Martonosi, Margaret Rose
AU - Fall, Kevin
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - delay tolerant network
KW - erasure coding
KW - routing
UR - http://www.scopus.com/inward/record.url?scp=84871996186&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871996186&partnerID=8YFLogxK
U2 - 10.1145/1080139.1080140
DO - 10.1145/1080139.1080140
M3 - Conference contribution
AN - SCOPUS:84871996186
SN - 1595930264
SN - 9781595930262
T3 - Proceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
SP - 229
EP - 236
BT - Proceedings of the ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
T2 - ACM SIGCOMM 2005 Workshop on Delay-Tolerant Networking, WDTN 2005
Y2 - 26 August 2005 through 26 August 2005
ER -