Transcript dataflow-next

How Dataflow is
opening the
Internet Frontier
Dataflow-to-synthesis Retrospective
David E. Culler
UC Berkeley
Arch Rock
The Internet
2
The Internet Frontier
Low resolution Sensor, Test4, Increasing frequency
1
Acceleration (g)
0.5
0
-0.5
-1
0
2
4
6
8
10
Time (sec)
3
12
14
16
18
Why “Real” Information is so Important?
Save Resources
Improve Productivity
Enable New Knowledge
Increase
Comfort
Enhance Safety & Security
Preventing Failures
High-Confidence Transport
Improve Food & H20
4
Protect Health
…but what has Dataflow got to do with it?
5
all I ever learned …
Arvind’s Law: Value derived from
concurrent activities is inverse to the
cost of integrating communication
and computation
- so tag it and do it all!
Culler’s Corollary: but storage
increases with concurrency
- so do it with bounded resources
6
all I ever learned …
7
so at the public school …
Log of Something
Ninja
Staged Event Driven Arch.
for massive internet servers
NOW
Split-C
Active Messages
TAM
Threaded Abstract Machine
- two level scheduling hierarchy
- expose network to the compiler
- no allocation on arrival
8
Time
Enabling Technology
Microcontroller
9
Flash
Storage
Radio
Communication
IEEE 802.15.4
Sensors
Enabling Technology
Not your 3M’s
• MIPs of proc.
• KB of RAM / Prog
• kbps of bandwith
• uW of power
Physical
World
10
Enabling Research
Build an approximation of the future that you imagine and
study it to learn what “is
true” in that possible world.
Berkeley Mote / TinyOS Platform
Silicon
World
Physical
World
11
Wireless
Processing
Storage
Sensors
WSN Research Phenomenon…
zeevo BT
Intel
rene’
SmartDust
WeC
Intel/UCB
dot
Sensit / Expeditions
Rene
XBOW
rene2
Eyes
NEST Mica
Telos
XBOW
mica
Sensicast
12
nest
6/02
1/02
TIP
BTNode
Intel
cf-mica
XBOW
cc-dot
Bosch
cc-mica
11/00
Intel
MOTE2
Intel
iMOTE
XBOW
mica2
XBOW
micaZ
digital sun
rain-mica
Dust Inc
blue cc-TI
3/03
5/04
trio
Berkeley…and beyond
Wireless Sensor Networks
SmartDust
Wireless
13
NEST
Sensors
Storage
Processing
TinyOS 2.0
The Systems Challenge
Over-the-air
Programming
Network
Protocols
Link
Radio
Serial
Applications and Services
Blocks,
Logs, Files
Flash
Scheduling,
Management
Streaming
drivers
MCU, Timers,
Bus,…
ADC,
Sensor I/F
WSN mote platform
Wireless
14
Storage
Processing
Communication Centric
Resource-Constrained
Event-driven Execution
Sensors
The Solution
• Basically a dataflow engine in disguise
– Two-level Scheduling Hierarchy
• Asynchronous events integrate external world
• Computational Tasks
– Collections of Tasks and Events + Bounded State form a Component.
– Never, never, never wait. Do work or go to sleep!!!!!!!!!!
• Recognition of reality
– Zillions of unattended devices embedded in a noisy physical world require an
unprecedented level of robustness and SIMPLICITY
– Application = Structured Graph of Components connected by Well-Designed
Interfaces.
• Escape Velocity
– Our System and Network Abstractions (ca. Unix + Sockets + TCP) have
been essentially unchanged for decades and are deeply steeped in the 3M
design point!
=> Provide a framework for defining boundaries and let the new layers fall
where they may.
15
What we mean by “Low Power”
• 2 AA => 1.5 amp hours (~4 watt hours)
• Cell => 1 amp hour
(3.5 watt hours)
Cell: 500 -1000 mW
WiFi: 300 - 500 mW
GPS: 50 – 100 mW
=> few hours active
=> several hours
=> couple days
WSN: 50 mW active, 20 uW passive
450 uW => one year
45 uW => ~10 years
* System design
* Leakage (~RAM)
* Nobody fools
mother nature
Ave Power = fact * Pact + fsleep * Psleep + fwaking * Pwaking
16
Wireless Client vs Wireless Server
• Wireless Client
– needs to last a day or two
– has a human to keep them working properly
– mostly formats specific incoming data for display
• Wireless server
–
–
–
–
17
needs to last for long periods
must be self-managing, adaptive, robust
Generates meaningful data for many uses
Often mobile (!!!)
Self-Organized Mesh Routing
2
2
2
2
1
1
2
0
18
Sensor Network “Networking”
Appln
Hood
EnviroTrack
FTSP
Transport
Routing
Scheduling
SPIN
TTDD
Phy
19
Ascent
GPSR
SPAN
ReORg
PC
Drip
Arrive
MintRoute
GRAD
GAF
FPS
Yao
SMAC
PAMAS
Link
Trickle
Deluge
MMRP
TORA
CGSR
AODVDSR
ARA
GSR
DBF
DSDV
TBRPF
Resynch
Topology
TinyDB
Diffusion
Regions
WooMac
TMAC
Pico
WiseMAC
Bluetooth
RadioMetrix
RFM
CC1000
eyes
BMAC
802.15.4
nordic
What WSNs really look like
Client Tools
External Tools
Excel, Matlab
Enshare, etc.
GUI
Internet
Legacy
Data analysis
Embedded Network
20
Gateway
Field Tools
Deploy
Query
Command
Visualize
THE Question
If Wireless Sensor Networks represent a future of
“billions of information devices embedded in the
physical world,”
why don’t they run THE standard internetworking
protocol?
21
THE Question
Web Services
XML / RPC / REST / SOAP / OSGI
HTTP / FTP / SNMP
TCP / UDP
IP
Ethernet Sonet
Enet
10M
Enet
100M
Enet
1G10G
Enet
GPRS
Serial
Plugs and People
22
802.11
802.11a
802.11b
802.11g
RFM,CC10k,…,802.15.4
Self-Contained
The Answer
They should
• Substantially advances the state-of-the-art in both domains.
• Implementing IP requires tackling the general case, not just a specific
operational slice
– Interoperability with all other potential IP network links
– Potential to name and route to any IP-enabled device within security domain
– Robust operation despite external factors
• Coexistence, interference, errant devices, ...
• While meeting the critical embedded wireless requirements
–
–
–
–
23
High reliability and adaptability
Long lifetime on limited energy
Manageability of many devices
Within highly constrained resources
LoWPAN - 802.15.4 the lowpower wireless IP Link
Web Services
XML / RPC / REST / SOAP / OSGI
HTTP / FTP / SNMP
• 1% of 802.11 power,
easier to embed, as easy
to use.
• 8-16 bit MCUs with KBs,
not MBs.
• Off 99% of the time
TCP / UDP
IP
Ethernet
24
Sonet
802.11
802.15.4, …
Web Services
XML / RPC / REST / SOAP / OSGI
HTTP / FTP / SNMP
Proxy / Gateway
Making sensor nets make sense
TCP / UDP
IP
Ethernet
Sonet
802.11
802.15.4, …
IETF 6lowpan
25
Challenges for IP over 802.15.4
• Header
– Standard IPv6 header is 40 bytes [RFC 2460]
– Entire 802.15.4 MTU is 127 bytes [IEEE ]
– Often data payload is small
• Fragmentation
– Interoperability means that applications need not know the constraints of
physical links that might carry their packets
– IP packets may be large, compared to 802.15.4 max frame size
– IPv6 requires all links support 1280 byte packets [RFC 2460]
• Allow link-layer mesh routing under IP topology
– 802.15.4 subnets may utilize multiple radio hops per IP hop
– Similar to LAN switching within IP routing domain in Ethernet
• Allow IP routing over a mesh of 802.15.4 nodes
– Options and capabilities already well-defines
– Various protocols to establish routing tables
26
A little example
Internet
WiFi
192.168.1.xxx
WiFi
ArchRockDemo
6LoWPAN
Router
(6to4)
10.97.0.xxx
FD97::xxx
27
Router
App Server and
Presentation
Web Services
Proxy Server
192.168.1.109
6LoWPAN Format Design
• Orthogonal stackable header format
• Almost no overhead for the ability to interoperate and scale.
• Pay for only what you use
IEEE 802.15.4 Frame Format
FCF
DSN
Len
preamble
Dst EUID 64
SFD
D pan
S pan
Src EUID 64
Max 127 bytes
Dst16 Src16
Fchk
HC1
Message > Frame fragmentation
29
dsp
HC1
HC1
frag
dsp
mhop
frag
Mesh (L2) routing
UDP
HC1
Header compression
IP
dsp
Dispatch: coexistence
mhop
IETF 6LoWPAN Format
dsp
Network Header
Application Data
A new internet citizen
Browser,
Enterprise,
Controller
Rich Web View per Node
Web Services / WSDL
SNMP, Ganglia, Email
Adapters
Data Warehouse
IP - layer 7
Sensor & Mgmt Services
HTTPm
Systat, Netstat, Echo
Ping, Traceroute, DHCP
Reboot
Proxy
Gateway
TCP/UDP IP
WiFi GPRS EtherNet
nc, telnet, ping, traceroute…
31
Router
LoWPAN
High Reliability
Triply Redundant
Ultra-low power
Highly Responsive
AES128 Secured
IP-based Mesh Network
Low-Power Schedule-Free Routing
• Extends preamble sampling [DARPA packet radio, 1984]
and low-power listening [UC Berkeley, 2000] to enable
battery powered routers.
– Simplicity of an “always on” network at low-duty cycle by
shifting effort from (frequent) listening to (infrequent)
transmission.
– Flexible and configurable
– Overlay time synchronization service for correlated sampling
and scheduling optimizations.
• Eliminates need for connectivity / interference survey
• Eliminates schedule incompatibility across clusters
• Eliminates costly scan for schedule on join / rejoin
36
Low Impact of 6LoWPAN on Lifetime –
Comparison to *Raw* 802.15.4 Frame
Energy Cost of Packet Communication vs. Data Size
*
uAs per Packet
Energy Δ for
fixed payload
Max
Payload
RCV 6LoWPAN Local <= Global
RCV 6LoWPAN Local <= Local
RCV Raw 802.15.4
TX 6LoWPAN Local => Global
TX 6LoWPAN Local => Local
TX Raw 802.15.4
0
20
* fully compressed header
* additional 16-byte IPv6 address
37
*
40
60
80
Bytes of Payload
100
120
Power of IP Connectivity
Ethernet
WiFi
GPRS
38
LoWPAN
send (IP_addr, port,
UDP, &data, len)
Still a Role for Proxies
Browser,
Enterprise,
Controller
Rich Web View per Node
Web Services / WSDL
SNMP, Ganglia, Email
Adapters
Data Warehouse
IP - layer 7
Sensor & Mgmt Services
HTTPm
Systat, Netstat, Echo
Ping, Traceroute, DHCP
Reboot
Proxy
Gateway
TCP/UDP IP
WiFi GPRS EtherNet
nc, telnet, ping, traceroute…
40
Router
LoWPAN
High Reliability
Triply Redundant
Ultra-low power
Highly Responsive
AES128 Secured
IP-based Mesh Network
Service Oriented Architecture
Service
Registry
Service
Description
find
Service
Requestor
publish
bind
Service
Provider
• Service Description => interface & implementation
– Operations supported, input/output objects
– Bindings to network and data encoding schemes
– Network address where service can be invoked
• Enough that client can generate code to access the service well
41
Embedded Web Services
Web Services
< get temp …
set sample_rate
set alarm … >
<request www.weather.com
service>
Service
Description
<value>
<value>
source=library
source=library
time=12:53
time=12:31
temp=26.7
temp=25.1
<\value>
<\value>
XML information
Wireless Packets
Sampled Value
int temp;
802.15.4
11 010110111
010010001
010010001
Low resolution Sensor, Test4, Increasing frequency
1
Physical Signal
42
Acceleration (g)
0.5
0
-0.5
-1
0
2
4
6
8
10
Time (sec)
12
14
16
18
A new WSN world
client
tier1
AquaLogic
server
tier2
Perl
tier3
SensorNet
GW/Proxy
Python
physical info net
tier4
NetWeaver
C#
Excel
43
Embedded Services
SensorNet
mote
Sensor
The Next Tier
• Today: we can connect essentially
everybody
Comp:People
• Tomorrow: we will be able to
connect and observe essentially
everything of value
1:1,000,000
Mainframe
1:1,000
Mini
Workstation
PC
1:1
Laptop
PDA
Phone
1000:1
years
44
Motes
– physical spaces, objects, and
their interactions
– physical information, not just
keystrokes
– and we know dataflow is the
technology of tomorrow
45
…and a new IETF working group
• mailto: [email protected]
46