Transcript Collection, Dissemination, and Management

Remote Programming
Dissemination
Collection
Network Management
Gilman Tolle
(also speaking for Jonathan Hui)
A Sensor Network Link?
A Sensor Network Link!
Why Over-The-Air Reprogramming?




Embedded nature of sensor networks – they’re small!
Network scales reaching thousands of nodes – there’s a lot of them!
A necessity in debugging and testing cycle – we can’t stop messing!
Learn about the environment after deployment – things change!

sensing data, network characteristics, etc.
What is Deluge?

A reliable data dissemination protocol for program images over a
multihop network.
Program
01010
10101
01010
10110
10101
10101
01010
10101

Combined with a bootloader (TOSBoot)
 Network Programming
Deluge Data Representation

Program divided into pages, each consisting of N packets.
Program
101 110 010
110 010 000
101 000
111 011
Packets
1234


Reduced RAM requirements
Allows for spatial multiplexing
N
How Does Deluge Work?

Nodes periodically advertise

Suppress similar advertisements
I only have
version 1.
Version 2 here.
I only have
version 1.
How Does Deluge Work?

Neighboring nodes request data

Suppress similar requests
Send me page 1!
Send me
page 1!
How Does Deluge Work?

Requested data is broadcast
Packet 12
of page 1!
How Does Deluge Work?

Dropped packets are NACKed
Repeat packet 4
of page 1!
Repeat packet 32
of page 1!
How Does Deluge Work?

Dropped packets are sent again
Packet 4
of page 1!
How Does Deluge Work?

Advertise for propagation to next hop
Version 2 here.
I only have
version 1.
Spatial Multiplexing

Propagate in “waves”

Exploit limited radio range for
concurrent broadcasts.

Reduced completion time
o(d + Sobj) vs. o(d * Sobj)

Page 1
Page 0
Epidemic Propagation

Epidemic propagation from one source
Deluge Features

Epidemic propagation from one source or many
 Continuous
propagation effort by all nodes
 Turn on/off radios at will
 Reach nodes with intermittent connectivity

Will find a path if it exists

Aggressive message suppression
 Scales
with density
 Ultra low quiescent traffic
Deluge Features



Multiple program images
Image metadata
User confirmation on expensive operations
 Minimize operator error
Robustness



Redundant CRCs
Golden Image with write protect
Load Golden Image
 Watchdog trigger
 Golden gesture
ProgA
ProgB
ProgC
01010
10101
01010
10110
10101
10101
01010
10101
01010
10101
01010
10110
10101
10101
01010
10101
01010
10101
01010
10110
10101
10101
01010
10101
CRASH!

TOSBoot



TOSBoot as isolated code
Verify CRCs
Verify system voltage
CRC CRC CRC CRC

CRC CRC CRC CRC
Management
CRC CRC CRC CRC

Program Name
Compile Time
UserID
Hostname
Platform
Deluge Lessons

Advantages







Ease of reprogramming 100’s-1000’s of nodes
Does not erase node IDs
Golden Image is immensely useful
Quickly switch between images
More reliable than uisp or msp430-bsl
Deluge over 802.15.4 more efficient that 802.11!
Disadvantages

Ease of reprogramming 100’s-1000’s of nodes :)
Routing

Getting the packets through, across many hops


Every node is a router too
Gateway-centric
Get data from the gateway to all the nodes – dissemination
 Get data from all the nodes to the gateway – collection
 Node-to-node?


Message-based


Transferring single packets, datagram-style
A layer, with clients above and services below

Attribute Queries and Changes
 Event Reporting
 RPC Command Layer

IP is not the right solution

Any-to-any is not useful enough to justify the state and complexity
Drip Dissemination Layer

Each sent message reaches all nodes in the network


Good for sending commands and queries
A generic single-message communication layer
command send[type](message) on the host
 event receive[type](message) on the node


Lightweight header – type and sequence number


Higher layer can add destination addressing
Uses Trickle epidemic algorithm (Phil Levis)

Dynamic forwarder selection
 Periodic retransmissions
 Neighborhood suppression

Caches latest message on each channel
GW
Client
Drain Collection Layer


Every node needs to send data to a gateway
A generic single-message communication layer
command send[type](message) on the node
 event receive[type](message) on the host


Very well-studied problem (Too many authors to list)


Client
Link estimation plus distributed execution of shortest-path algorithm
Ours must support multiple gateways

Each gateway builds a tree -- each node selects the cheapest next-hop
 Automatic subdivision of the network into pieces
GW
GW
Routing Goals

No predefined geographic structure

Routing decisions based only on connectivity and link estimators
 Makes it easier to deploy and move nodes
 Minimal state – single next hop, update-in-place

Robust to lossy networks

Drip periodically retransmits cached data with exponential backoff
 Drain uses link-layer ACKs, retransmissions, and long retry window
 Experiment with simple duty cycle: 1 second on, 1 second off
 Looks just like a lossy network, but the protocols keep working

Include rich metadata (source addresse, ttl, sequence numbers)
“How are those bad packets getting into the network?”
 Impossible to answer without metadata
 Enables network management through packet sniffing
 Even without a specific “management” layer

Network Management

Sensor networks fail


All networks fail sometimes!
Management lets us detect and respond to problems

Just as important for our networks
 Harder to do, thanks to highly dynamic networks!

Passive Packet Sniffing

Active Network-Layer Monitoring

Management Queries

Monitoring Policies and Statistics
The Unbearable Lightness of Sniffing

Just sniffing packets reveals a wealth of information






Active nodes from routed Drain messages
Network topology from Drain beacon messages
Dissemination behavior from Drip messages
Reprogramming status from Deluge advertisement messages
Overall traffic rates and histograms by type
Doesn’t make any extra demands on the network
“If you’re going to send the packet anyway…”
 Passive management information gathering


Works when the network isn’t running the management layer

Sometimes, you really need that extra few kB of code space
GW
The Story About Ping


Characterizing the performance of a dynamic network is HARD
The first tool of network management: ping


The second tool of network management: the ping daemon


Best with a few nodes that you don’t check very often
Can provide historical and current data on many nodes
The third tool of network management: the ping visualizer

Scalable way to handle large complex networks
 Most networks don’t have a natural spatial realization

Our network is firmly embedded in space
The 10,000-Foot View
Management: The Gathering

Sometimes, you need to know more than ping can tell you

How long has the node been running?
 Has the node been dropping any packets?

… and in our energy-constrained mote-land
What is the node’s power source?
 Does the node have enough energy to run?

System & App Components


Management can be seen as a database problem
TinyOS application exports information


Named attributes, variables in RAM
Attribute schema generated at compile time
Replace long names with short integers – save bandwidth
 Store schema on mote using Deluge Supplement


Attribute Dispatcher
Query Processor
Nucleus component responds to queries

“Get attributes {2, 3, 6} and RAM variable at {0x1a8c} with length {2}”
Drip/Drain
Nucleus Host Architecture
Pixels
Characters
Web Visualization
Other Mgmt Tools
XML-RPC
Command-Line Tools
XML-RPC
Monitoring Daemon
XML-RPC
Query Translator
Other Client Applications
Binary Data
Packet Forwarder
GW
GW
Binary Data