2009-11-18

Replication versus Redundancy in Contact‐aware Opportunistic Routing

by: Gabriel Sandulescu

Abstract: In this presentation we address the replication versus redundancy optimisation problem for a class of intermittently-connected ad hoc networks, also referred to as delay-tolerant networks. In particular we target networks having the following three characteristics: routing is performed by a store-carry-forward mechanism in an opportunistic manner, replication of custodian messages is used to increase the delivery ratio, and erasure coding is used to deal with large messages in short contact windows.
We propose a mathematical model in which the merits of a high replication factor can be compared to a high level of redundancy in erasure coding. The purpose of the model is to identify the optimised level of replication and redundancy for a given probability of successful delivery before a selected time-to-live parameter.
Although the approach is in principle general and can be applied in different opportunistic settings, we illustrate the approach on the SprayAndWait algorithm when extended with a fragmentation/ redundancy mechanism. Finally, we suggest that an initial component of the model, namely a distribution curve for average message latency distribution can be adaptively replaced by a measurement based distribution using recent delivery history information.