Transcript The Pulse Protocol: Energy Efficient Infrastructure Access

The Pulse Protocol:
Mobile Ad hoc Network Performance
Evaluation
Baruch Awerbuch, David Holmer,
Herbert Rubens
{baruch dholmer herb}@cs.jhu.edu
Johns Hopkins University
Department of Computer Science
WONS Jan 2005
www.cnds.jhu.edu/archipelago/
Presentation Overview

Pulse Protocol Overview




Scalable multi-hop ad hoc routing protocol
Based on Tree Routing
Tree Routing vs. Direct Routing
Performance Evaluation

Comparison with existing ad hoc wireless
routing protocols
Ad hoc Nodes
Network Connectivity
Pulse Flood
Spanning Tree
Source and Destination Need to
Establish a Path
Pulse Response Sent to Root
Destination Paged on Next Pulse
Destination Sends Pulse Response
Path Option 1: Through the Root
Through the Root Path
9 Hops
Shortest Path
2 Hops
This option is inefficient! It is not necessary to go to the root. Better routes already exist!
Path Option 2: Tree Traversal
Tree Traversal Path
5 Hops
Shortest Path
2 Hops
Path Option 3: Tree Shortcut
Tree Shortcut Path
3 Hops
Shortest Path
This is the initially selected path of the Pulse protocol.
2 Hops
Path Optimization: Gratuitous Reply
Selected Path
2 Hops
Shortest Path
2 Hops
Node sends gratuitous reply
Tree Routing vs. Direct Routing

Direct Routing

Attempts initially discover the shortest path


Link state



tracks every link in the network regardless of whether it is used
a shortest path spanning tree for every node in the network
On-Demand




Requires large overhead
floods the network to establish a route
re-floods when ever the path breaks
a shortest path spanning tree for all nodes transferring data
Tree Routing




Proactively rebuilds a single spanning tree on top of the network
Boot straps communication off of the tree route
Route are not initially the direct shortest path, but routing mechanism
allows the path to converge towards the shortest path
Active destinations can be reached without flooding the network

Efficient operation for realistic traffic patterns
Pulse Concepts

Aggregation – for scalability



All nodes have a route to the Pulse Source
All communication initiates through Pulse Source
Pulse Source can “Page” multiple nodes on the same
Pulse packet, to activate them


Uses a single flood instead of one per source/dest pair
De-Aggregation – for efficiency

Routing control packets allow optimized routes to be
located using these mechanisms




Through Root of Tree
Tree Traversal
Shortcuts
Gratuitous Reply
Network Traffic Patterns

Most existing traffic patterns in networks involve many nodes
communicating with a common subset




Client Server Model
All nodes going to the internet gateways
Nodes reporting information to a number of sinks
Network Services



Ad hoc DNS Service
Voice Over IP server
Local Information Database



Nearby restaurants
Shops/Advertising
Military Applications

Blue Force Tracker




All soldiers send GPS coordinates to collection node
Target Identification
Surveillance Reporting
Sensor Network

Source  Sink model
Common Destination
All of these reverse routes are established with a single unicast packet!
Node wants to sent packets
Doesn’t currently have a route
Must forward the packet to the Pulse Source.
Parent however DOES have route!
Can send packet directly to the destination. No paging involved.
Multiple Sources Send Data
Multiple Sources Send Data
Route initially twice the length of shortest path!
Properties




Pulse flood proactively maintains a routing
tree across the network
Active destinations unicast a pulse
response to maintain reverse routes
All nodes can route to all active
destinations without flooding
Paging of inactive destinations is
aggregated to limit impact on network
NS2 General Simulation Setup


All nodes use random way-point mobility including the
Pulse Source
Exponential on/off traffic model





Many randomly changing CBR flows
(different sources & destinations over time)
Average flow duration of 10 seconds
Each flow offers 0.01 Mbps w/ 512 byte packets
Total load controlled by the number of flows
Energy efficient version of protocol (INFOCOM 2004)



No gratuitous reply mechanism
10% of bandwidth wasted on power saving mechanism
Randomized traffic model is worst case for protocol
Delivery Ratio at 10m/s
DSR
1k x 1k 50 Nodes
Low Density
Pulse
1k x 1k 100 Nodes
Medium Density
1k x 1k 200 Nodes
High Density
Delivery Ratio at 20m/s
DSR
1k x 1k 50 Nodes
Low Density
Pulse
1k x 1k 100 Nodes
Medium Density
1k x 1k 200 Nodes
High Density
Pulse Protocol Conclusion

Excellent performance compared with
existing ad hoc routing protocols

High delivery ratio under
High Mobility
 High Density
 Large number of flows


Scalable routing solution for multi-hop ad
hoc peer-to-peer networks
Real World Implementation

Completed Features

Linux Kernel Module 2.4 and 2.6 compatibility



Pulse Protocol






Internet Access, Ad hoc Access Points, Voice over IP
Mobility testing from automobiles
Leader Election Algorithm



Shortcuts and gratuitous reply
Instantaneous loop freedom
Fast parent switching (with loop freedom)
Medium Time Metric route selection metric (WONS 2004)
50 Nodes deployed across JHU Campus


Operates at layer 2
Distributed virtual switch architecture provides seamless bridging
Fault tolerance, switches pulse source to most accessed destination
Handle merge and partition
In Progress

Efficient Tree Flooding


Similar to expanding ring search but with no duplicates
Security – (NDSS 2005)

Flood Rushing, Wormholes, Blackholes, any NON-Byzantine attack
Thank You!
Questions??
Baruch Awerbuch, David Holmer, Herbert Rubens
(baruch,dholmer,herb)@cs.jhu.edu
http://www.cnds.jhu.edu/archipelago/
Wave Relay Ad hoc Networking Test-bed
http://www.cnds.jhu.edu/research/networks/archipelago/testbed/testbed.html
Secure Ad hoc Networking for Industrial Process Control
http://www.cnds.jhu.edu/research/networks/archipelago/industrial/industrial.html
Density Performance
DSR
Low Traffic
0.10 Mbps
Pulse
Medium Traffic
0.15 Mbps
1km x 1km with 5 m/s Max Speed
High Traffic
0.20 Mbps
Routing Methods
Pulse Source
Source
Destination
Through the Root
Pulse Source
Source
Destination
Through the Root
Pulse Source
Source
Destination
Tree Traversal
Pulse Source
Source
Destination
Tree Short Cuts
Pulse Source
Source
Destination
Gratuitous Reply
Pulse Source
Source
Destination
Ad hoc Nodes
Network Connectivity
Spanning Tree
Source and Destination Need to
Establish a Path
Reservation Sent to Root of Tree
Routes to Source Installed at
Adjacent Nodes
Destination Paged on Next Pulse
Destination Paged on Next Pulse
Communication Begins
Gratuitous Reply