Transcript Epidemic Routing and Message Ferrying

Group 3
Sandeep Chinni
Arif Khan
Venkat Rajiv
Delay Tolerant Networks
 Path from source to destination is not present at any
single point in time.
 Combining snapshots of the network at different times
may result in the formation of a source-destination
path.
Protocols for DTN
 Prioritized Epidemic Routing for Opportunistic
Networks
 Ram Ramanathan, Regina Rosales-hain

ACM MobiOpp 2007
 Oracle Based Routing
 S. Jain, K. Fall, and R. Patra. Routing in a Delay Tolerant
Network.

In Proc. ACM Sigcomm, pages 145–158, 2004
Epidemic Routing
 Goal is to deliver messages with high probability even
when there is never a fully connected path.
Epidemic Routing
 Goal is to deliver messages with high probability even
when there is never a fully connected path.- Can we
do better?
 The overall goal of Epidemic Routing is to
 maximize message delivery rate
 minimize message delivery latency
 minimizing the aggregate system resources consumed in
message delivery
Epidemic Routing Protocol
 Anti-Entropy sessions
Message Information
 Message ID – a unique ID for all the messages that will
be transmitted.
 Hop Count – The maximum hops that a message can
take before reaching the destination.
 Optional Ack request
Hosts/Nodes
 Nodes set a maximum buffer size to aid epidemic
routing.
 This setting will limit memory and network usage.
 There is a trade off between resource consumption and
message delivery rate/latency.
 Simple buffer management strategies like FIFO can be
used when there is contention for resources - not the
best though.
Prioritized Epidemic Routing(PREP)
 Prioritizes the messages for transmission and deletion
using a priority function.
 Priority function is based on
 Current cost to destination
 Current cost from source
 Expiry time
 Generation time
 Inter-node costs are computed with a metric called
average availability.
Features of PREP
 PREP has two modules:
 Topology awareness

Helps in calculating routing costs from a node to a
destination.
 Message drop and Transmit property

A priority scheme for deleting and transmitting message
packets.
Topology Awareness
 Each node runs a neighbor discovery algorithm to find
out its neighbors.
 Each link between two nodes has a metric called the
Average Availability(AA).
 The average availability is calculated based on a short
history of node link availability information.
 If a link is not available for a configured time, then it is
forgotten.
 Periodically or whenever sufficient new link
information is available Link State Advertisements
(LSA) are exchanged between nodes.
Topology Awareness
 This LSA exchange is called Topology Sync as the
nodes learn from each other.
 LSA exchange gives the nodes the knowledge of the
network topology during the recent time period.
 This “best effort” topology awareness is used to
compute routing costs.
 Formula : (1-AA)+0.01
 AA-Average Availability
 Dijkstra’s algorithm is used for lowest cost route.
Message Drop & Transmit Priority
 Each message has a drop priority(Pd) and transmit
priority(Pt).
 Pd of a packet is the lowest cost path from the current
node to the destination.
 Pt of a packet is based on the cost to the destination
and time-to-expire of the packet.
 When the buffer of a node crosses a threshold, it starts
to drop packets based on Pd and stops only after a lower
threshold is crossed.
Simulation
 PREP compared with Epidemic routing and AODV and
simulation done in NS-2.
 Simulation Parameters
Advantages of PREP
 Successful, as long as the resources are not overloaded.
 Does not rely on extrapolating previous contact
information.
 Improves performance of Epidemic routing at high
loads.
Disadvantages
 Very high resource utilization even when less number
of messages are being transmitted.
 Route cost calculation is not possible in all cases and Pd
cannot be computed.
Oracle Based Routing
 Knowledge centers (Oracles) are used to make routing
decisions.
 Based on the amount of information and network
resources available suitable Routing protocols can be
used.
Oracles
 Contacts Summary Oracle
 can answer questions about time-invariant aggregate statistics or
summary characteristics about contacts.
 Contacts Oracle
 can answer any question regarding contacts between two nodes at any
point in time.
 Can be used for admission control.
 Queuing Oracle
 gives information about instantaneous buffer occupancies (queuing) at
any node at any time.
 can be used to route around congested nodes.
 Traffic Demand Oracle
 Can answer any questions regarding present or future traffic demand.
Components for Path Calculation
 Queuing time:

Time until a contact becomes available.
 Transmission delay:

Time to inject a message completely into an edge.
 Propagation delay:

Time to deliver the message (includes any intermediate queuing
delay).
 Storage Capacity.
Routing Algorithm Classes
 No knowledge
 They do not use any oracles and hence perform badly.
 Complete Knowledge
 They utilize contacts, traffic and queuing oracles.
 Partial Knowledge
 They find routes in the absence of traffic demand oracle
and use other oracles.
Oracle Based Routing Algorithms
 Schemes:
Simulation with Bus Routes
Average Delay
Delivery Ratio
Bandwidth Variation
Advantages & Drawbacks
 Advantages
 Based on the oracles available we can choose an
appropriate algorithm for route calculation.
 Drawbacks
 Creating and maintaining oracles is a significant
distributed systems problem.
What have we taken out of these
papers?
 Prioritized epidemic routing might be of interest in
worst case scenarios for our DTN protocol.
References
[1] A. Vahdat and D. Becker. Epidemic routing for
partially connected ad hoc networks, 2000.