Probabilistic Routing in Intermittently Connected Networks
Lindgren, Doria, Schelen
dtn delay tolerant routing networking prophet mobility
@inproceedings{lindgren:sapir-2004,
title={Probabilistic Routing in Intermittently Connected Networks},
author={Lindgren, A. and Doria, A. and Schelen, O.},
booktitle={Workshop on Service Assurance with Partial
and Intermittent Resources ({SAPIR})},
pages={239--254},
year={2004}
}
[ Download PDF ]
Abstract:
In this paper, we address the problem of routing in intermittently connected networks. In such networks there is no guarantee that a fully connected path between source and destination exists at any time, rendering traditional routing protocols unable to deliver messages between hosts. There does, however, exist a number of scenarios where connectivity is intermittent, but where the possibility of communication still is desirable. Thus, there is a need for a way to route through networks with these properties. We propose PRoPHET, a probabilistic routing protocol for intermittently connected networks and compare it to the earlier presented Epidemic Routing protocol through simulations. We show that PRoPHET is able to deliver more messages than Epidemic Routing with a lower communication overhead.
In many settings, there may not ever be an end-to-end path between nodes
- Have to buffer the contents, route on expected connectivity
- May have to rely on mobility to enable changing, future connectivity
- Could explicitly reason about this, as some work attempts
- This work builds a simple probabilistic model of future connectivity based on previous contact
Compares heavily to epidemic routing
- Big downside is heavy resource use, both network and storage; perhaps latency deficiencies
PROPHET: Probabilistic Routing Protocal using History of Encounters and Transitivity
When nodes meet they exchange a summary vector capturing delivery predictability information
Probabilities capture how likely it is a node will be in contact with another node, given previous contacts
- Can chain these to calculate probabilistic paths through network
Probability $P_(a, b) \in [0, 1]$ is maintained at every node $a$ for each other node $b$
- When a node is encountered, probability is updated as $P_(a, b) = $P_(a, b)_{old} + (1 + $P_(a, b)_{old}) \times P_{init}$
- $P_{init}$ is initialization constant $\in [0, 1]$
- Nodes are aged according to $P_(a, b) = P_(a, b)_{old} \times \gamma^k$ where $\gamma \in [0, 1]$ is the aging constant and $k$ is the number of time units elapsed since the last update
- Paths are computed transitively via $P_(a, c) = P_(a, c)_{old} + (1 - P_(a, c)_{old}) \times P_(a, b) \times P_(b, c) \times \Beta$$ where $\Beta \in [0, 1]$ is a constant weight used to apply some control over the eagerness of using transitive links
Forwarding strategies are potentially complex
- Send to more than one node, incur tradeoff in resources vs success?
- Simple strategy used here: Upon contact, a message is transferred if the delivery predictability of the intended destination is higher at the new node
Evaluation based on a "community model" scenario with arena divided up into grids
- Each grid cell has a home location, representing a village or such
- Nodes are randomly assigned to grid cells and wander about but trend toward repeatedly returning to their home location
- Home locations also have fixed nodes, acting as gateways or storage points
- One home location is distinguished as the special gathering place
Evaluation metrics:
- Message delivery ability---percentage of messages delivered to destinations
- Message delivery delay---how long successful deliveries take
- Message exchanges---how many transmisions are caused
Complex interplay between these metrics
- E.g., increasing queue size (storage space) increases likelihood of message delivery, though it also increases delay, because more messages are delivered that previously were not
- Latency should be presented as a CDF to show this; messages that would be delivered even with small queue will be mostly on left of curve
Even with random movement, nodes that were close have a good chance of not having gone far away, so the scheme still does better than epidemic routing
Would be interesting to add message priority queue; simply done by FIFO here
- On new contact, process messages and forward any worthwhile?
ACKs from recipients would allow messages to be deleted from buffers