Incentive-aware routing in DTNs
Authors:
- 1 October 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 2008 IEEE International Conference on Network Protocols
- No. 10921648,p. 238-247
Abstract
Disruption tolerant networks (DTNs) are a class of networks in which no contemporaneous path may exist between the source and destination at a given time. In such a network, routing takes place with the help of relay nodes and in a store-and-forward fashion. If the nodes in a DTN are controlled by rational entities, such as people or organizations, the nodes can be expected to behave selfishly and attempt to maximize their utilities and conserve their resources. Since routing is an inherently cooperative activity, system operation will be critically impaired unless cooperation is somehow incentivized. The lack of end-to-end paths, high variation in network conditions, and long feedback delay in DTNs imply that existing solutions for mobile ad-hoc networks do not apply to DTNs. In this paper, we propose the use of pair-wise tit-for-tat (TFT) as a simple, robust and practical incentive mechanism for DTNs. Existing TFT mechanisms often face bootstrapping problems or suffer from exploitation. We propose a TFT mechanism that incorporates generosity and contrition to address these issues. We then develop an incentive-aware routing protocol that allows selfish nodes to maximize their own performance while conforming to TFT constraints. For comparison, we also develop techniques to optimize the system-wide performance when all nodes are cooperative. Using both synthetic and real DTN traces, we show that without an incentive mechanism, the delivery ratio among selfish nodes can be as low as 20% as what is achieved under full cooperation; in contrast, with TFT as a basis of cooperation among selfish nodes, the delivery ratio increases to 60% or higher as under full cooperation. We also address the practical challenges involved in implementing the TFT mechanism. To our knowledge, this is the first practical incentive-aware routing scheme for DTNs.Keywords
This publication has 14 references indexed in Scilit:
- Bittorrent is an auction2008
- DARWIN2007
- MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks2006
- Practical security for disconnected nodes2005
- Sprite: a simple, cheat-proof, credit-based system for mobile ad-hoc networks2004
- On selfish routing in internet-like environments2003
- Fast accurate computation of large-scale IP traffic matrices from link loads2003
- Cooperation in wireless ad hoc networks2003
- Energy-efficient computing for wildlife tracking2002
- Web caching and Zipf-like distributions: evidence and implications1999