Transcript The Pulse Protocol - Computer Science, Johns Hopkins University

Wave Relay:
Multi-hop Wireless Ad hoc Network
Baruch Awerbuch, David Holmer,
Herbert Rubens
{baruch dholmer herb}@cs.jhu.edu
Johns Hopkins University
Department of Computer Science
www.cnds.jhu.edu/archipelago/
Goals: Design a system that…

Supports a large number of nodes


Moving at high speeds


High multi-path, rapidly fluctuating channels
Running real-time applications


greater then 40 mph
In an urban environment


thousands
Voice, video, interactive distributed applications
With or without help from fixed infrastructure

If its available use it to be more efficient
Wave Relay Test-bed

Over 50 Wave Relay Routers deployed
across JHU Campus




Urban City Environment
Internet Access, Ad hoc Access Points,
Voice over IP
Mobility testing from automobiles
System tested at Holcim Industrial Plant
(Chicago, IL)

Complex propagation environment

Massive multi-path

Enabled real-time industrial process
control

Currently Deployed Custom Applications

Military Distributed Battlefield Mapping



GPS based interactive map
Eventual reliability
Locality Specific Messaging System


GPS based messaging system
Messages targeted to any user at a
specific location
Wave Relay Device
Software

Pulse Protocol [Infocom’04, Milcom’04, WONS’05]


Embedded Single Board Computer
Scalable ad hoc routing protocol
Active path tracking

Based on Tree Routing strategy
Medium Time Metric [MONET,WONS’04]

High Throughput Path Selection

Increased Path Elasticity

Efficient Multi-rate Operation



Leader Election Algorithm

Handles merge, partition, failure
Embedded Linux Distribution






Hardware
Less then 8 MB storage requirement
Linux Kernel Module 2.4 and 2.6 compatibility


Operates at layer 2
Distributed virtual switch architecture provides
seamless bridging





NS Geode SC1100 266 MHz Processor
64 Mb Ram onboard
2 mini-PCI interfaces
1 Compact flash interface
Serial port
10/100 Ethernet
Hardware Watchdog
Power over Ethernet


Atheros 802.11g/b Wireless Card



Stores OS & Wave Relay software
Garmin GPS 16 receiver
Li-Ion Battery Pack


400 mW (26 dBm) output power
16 MB Industrial Compact Flash


+7V to +18V DC Input
~20 hours continuous runtime
Industrial NEMA 67 Enclosure




4 N-type antenna mounts
2 Ethernet Ports
(6) protection against dust
(7) water submersible
Existing Approaches
Receivers
Urban Channel Environment
10
5
• Multi-path fading & shadowing
0
-5
• Rapidly changing channel conditions
-10
-15
-20
0
200
400
600
800
1000
1200
1400
1600
1800
2000
On-Demand Protocols (AODV, DSR)
10
5
• On-demand protocols have no
knowledge of channels conditions
0
-5
-10
• A RREQ packet provides only a single
sample of a complex distribution
-15
-20
0
200
400
600
800
1000
1200
1400
1600
1800
2000
10
5
0
-5
-10
Destination
-15
Source
-20
Link State Protocols (OLSR, TBRPF)
-25
• Channel is continuously changing
-30
-35
-40
0
200
400
600
800
1000
1200
1400
1600
1800
2000
• Continuous flooding from every node in
the network
10
5
0
-5
-10
-15
-20
-25
-30
-35
-40
0
200
400
600
800
1000
1200
1400
1600
1800
2000
You can not accurately track channel
with control packets!
The Pulse Protocol

Proactive Component





Tracks minimum amount of information to avoid flooding for
route establishment and maintenance
Periodic flood operation (similar to Hello Protocol)
Rebuilds spanning tree
Estimates neighbors, density, SNR, loss rates, capabilities,
number of radios, MTM metric
On-Demand Component

Route establishment


Using only UNICASTS!
Gratuitous mechanism




Neighbors promiscuously monitor packets
Metric tracked at the speed of data packets NOT control packets!
Path switches as metrics change
Local changes in connectivity only generate local traffic

Unlike BOTH on-demand and link state 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
Initial Path: 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
Optimized Path
2 Hops
Shortest Path
2 Hops
Node sends gratuitous reply
Proactive Route Maintenance
Proactive Route Maintenance
Proactive Route Maintenance
Pulse Protocol Concepts

Aggregation – for scalability



Spanning tree represents a compressed view of the network
topology
Pro-active component maintains the minimum amount of
information to allow efficient route establishment
De-Aggregation – for efficiency




The routing metric is tracked at the speed of the data flow
Changes to the metric are only reported locally
Routes are continuously adjusted as the metrics change
High speed accurate route tracking is essentially an on-demand
decompression of the topology


However, it occurs ONLY in areas of the network with active data
flows
Result: a scalable routing structure which tracks paths at
the speed of the data flow
Future Work

Security (NDSS 2005)


Wormholes, black-holes, flood rush, replay
Provide





Distributed commit (CNDS-02)



Node authentication
End-to-end encryption
Broadcast/Routing Encryption
Efficient node addition/removal
Consistent, persistent, group communication
e.g. coordinated battlefield view and control
Opportunistic Gradient Forwarding
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
Minimum Hop Metric
(Traditional Technique)




Not designed for multi-rate networks
A small number of long slow hops provide
the minimum hop path
These slow transmissions occupy the
medium for long times, blocking adjacent
senders
Selecting nodes on the fringe of the
communication range results in reduced
reliability
New Approach:
Medium Time Metric (MTM)


Assigns a weight to each link proportional
to the amount of medium time consumed
by transmitting a packet on the link
Enables the Pulse protocol to discover the
path that minimizes total transmission time
MTM Example
Medium Time Usage
Destination
Link Throughput
11 Mbps
2.5ms
4.55 Mbps
5.5 Mbps
3.7ms
3.17 Mbps
2 Mbps
7.6ms
1.54 Mbps
1 Mbps
13.9ms
0.85 Mbps
Source
Path Medium Time Metric (MTM)
Path Throughput
11 Mbps
5.5 Mbps
2 Mbps
1 Mbps
1
13.9ms
= 13.9 ms
0.85 Mbps
MTM Example
Medium Time Usage
Destination
Link Throughput
11 Mbps
2.5ms
4.55 Mbps
5.5 Mbps
3.7ms
3.17 Mbps
2 Mbps
7.6ms
1.54 Mbps
1 Mbps
13.9ms
0.85 Mbps
Source
Path Medium Time Metric (MTM)
11 Mbps
5.5 Mbps
2 Mbps
1 Mbps
5.5 + 2
1
3.7ms
13.9ms
7.6ms
Path Throughput
= 11.3 ms
= 13.9 ms
1.04 Mbps
0.85 Mbps
MTM Example
Medium Time Usage
Destination
Link Throughput
11 Mbps
2.5ms
4.55 Mbps
5.5 Mbps
3.7ms
3.17 Mbps
2 Mbps
7.6ms
1.54 Mbps
1 Mbps
13.9ms
0.85 Mbps
Source
Path Medium Time Metric (MTM)
11 Mbps
5.5 Mbps
2 Mbps
1 Mbps
11 + 2
2.5ms 7.6ms
5.5 + 2
3.7ms
1
13.9ms
7.6ms
Path Throughput
1.15 Mbps
= 10.1 ms
= 11.3 ms
= 13.9 ms
1.04 Mbps
0.85 Mbps
MTM Example
Medium Time Usage
Destination
Link Throughput
11 Mbps
2.5ms
4.55 Mbps
5.5 Mbps
3.7ms
3.17 Mbps
2 Mbps
7.6ms
1.54 Mbps
1 Mbps
13.9ms
0.85 Mbps
Source
Path Medium Time Metric (MTM)
11 + 11
11 Mbps
5.5 Mbps
2 Mbps
1 Mbps
2.5ms 2.5ms = 5.0 ms
11 + 2
2.5ms 7.6ms
5.5 + 2
3.7ms
1
Path Throughput
13.9ms
7.6ms
2.38 Mbps
1.15 Mbps
= 10.1 ms
= 11.3 ms
= 13.9 ms
1.04 Mbps
0.85 Mbps
MTM Advantages

Paths which minimize network utilization,
maximize network capacity



Global optimum under complete interference
Excellent heuristic in even larger networks
Avoiding low speed links inherently
provides increased route stability

High speed links operate with greater margin
and are more elastic under changes