Transcript IrisNet: A Planetary-Scale Architecture for Multimedia Sensors

IrisNet:
A Planetary-Scale Architecture
for Multimedia Sensors
Phillip B. Gibbons
Intel Research Pittsburgh
January 19, 2007
IrisNet
Slides are © Phillip B. Gibbons
What is a Sensor Network?
• Tiny sensor nodes with very limited processing power,
memory, battery. Scalar sensors (e.g., temperature)
• Closely co-located, communicating via an ad hoc
low-bandwidth wireless network
• Singly tasked
Microservers?
not so tiny, PDA-class processor
wide-area, not ad hoc
Fault-line monitoring?
Broadband?
not low-bandwidth
Webcams?
not scalar, can be multi-tasked
Tanker/Fab monitoring?
© Phillip B. Gibbons
IrisNet
powered, wired
2
Sensor Networks is a Rich Space
• Characteristics of sensor network depend on
• Requirements of the application
• Restrictions on the deployment
• Characteristics of sensed data
• Sampling the real world
• Tied to particular place and time
UCLA CENS NIMS
James Reserve
• Often write-dominated:
Data Sampled far more than Data Queried
© Phillip B. Gibbons
IrisNet
3
Multimedia Sensor Systems
• Rich collection of (cheap) sensors
• Cameras, Microphones, RFID readers, vibration
sensors, etc
• Internet-connected. Potentially Internet-scale
• Tens to millions of sensor feeds over wide-area
• Pervasive broadband (wired & wireless)
• Goal: Unified system for accessing, filtering,
processing, querying, and reacting to sensed data
• Programmed to provide useful sensing services
© Phillip B. Gibbons
IrisNet
4
Example Multimedia Sensing Services
Consumer services:
• Parking Space Finder
• Lost & Found / Lost pet
• Watch-my-child / Watch-my-parent
• Congestion avoidance
© Phillip B. Gibbons
IrisNet
5
Example Multimedia Sensing Services
Health, Security, Commerce, and Science services:
• Epidemic Early Warning System
• Homeland Security
• Low Atmosphere Climate Monitoring
• Asset/Supply Chain Tracking
• Internet-scale Sensor Observatories
© Phillip B. Gibbons
IrisNet
Our prototype
6
Sensor Network Challenges?
• Resource-constrained sensor networks present many
unique challenges
• Battery limitations => limiting communication,
duty cycles, etc
• Limited processing power & memory =>
new OS, languages, algorithms, etc
• On the other hand, in multimedia sensor systems
• Nodes are powerful,
well-connected
Where’s the Challenge?
© Phillip B. Gibbons
IrisNet
7
Data & Query Scaling Challenges
• Data scaling
• Millions of sensors
• Globally-dispersed
• High volume feeds
• Historical data
• Query scaling
NetRad: 100Mb/s
• May want sophisticated data processing on all
sensor feeds
• May aggregate over large quantities of data, use
historical data, run continuously
• Want latest data, NOW
© Phillip B. Gibbons
IrisNet
8
Further Challenges
IrisNet
addresses some of these challenges
• System
Scaling
• How to manage a million node system?
Many open problems remain…
• How to write services for a million node system?
• System Heterogeneity
• Sensor types, Nodes, Networks, Admin. Domains
• Shared Resource
• Privacy & Security
• Competing actuation
© Phillip B. Gibbons
IrisNet
9
Outline
• Multimedia Sensor Systems: Opportunities &
Challenges
• IrisNet overview
• IrisNet key features
• Conclusions
© Phillip B. Gibbons
IrisNet
10
IrisNet: Internet-scale Resourceintensive Sensor Network services
• General-purpose architecture for wide-area sensor
systems
• A worldwide sensor web
www.intel-iris.net
• Key Goal: Ease of service authorship
• Provides important functionality for all services
• Intel Research Pittsburgh + many CMU collaborators
• First prototype in late 2002, in use
• In ACM Multimedia, BaseNets, CVPR, DCOSS, DSC, FAST,
NSDI(2), Pervasive Computing, PODC, SenSys, Sigmod(2)
© Phillip B. Gibbons
IrisNet
11
Data & Query Scaling in IrisNet
• Store sensor feeds locally
• Too much data to collect centrally
• Push data processing & filtering to sensor nodes
• Reduce the raw data to derived info, in parallel
near source
• Push queries to sensor nodes
• Data sampled >> Data queried
• Tied to particular place: Queries often local
• Exploit logical hierarchy of sensor data
• Compute answers in-network
© Phillip B. Gibbons
IrisNet
12
Ease of Service Authorship
• What is a minimal service specification?
• Application-specific functionality needed
• Program sensor system as a whole
• Provide a simple, centralized view of the system
• Data as a single queriable unit
• Declarative (database-centric) approach
• Be the Google/Ask Jeeves for live content
IrisNet uses XML: Self-describing tags, Hierarchy
© Phillip B. Gibbons
IrisNet
13
Data Organized as Logical Hierarchy
<State id=“Pennysylvinia”>
<County id=“Allegheny”>
Example XML Hierarchy
<City id=“Pittsburgh”>
<Neighborhood id=“Oakland”>
<total-spaces>200</total-spaces>
<Block id=“1”>
<GPS>…</GPS>
<pSpace id=“1”>
<in-use>no</in-use>
<metered>yes</metered>
</pSpace>
<pSpace id=“2”>
…
</pSpace>
Hierarchy is automatically
</Block>
partitioned among the OAs
</Neighborhood>
<Neighborhood id=“Shadyside”>
…
© Phillip B. Gibbons
IrisNet
14
…
…
…
IrisNet’s Two-Tier Architecture
Two components:
SAs: sensor feed processing
OAs: distributed database
Query
User
Web Server
for the url
...
OA
XML database
OA
XML database
...
SA
SA
senselet
senselet
senselet
senselet
Sensornet
© Phillip B. Gibbons
Sensor
OA
XML database
...
Sensor
SA
senselet
senselet
Sensor
IrisNet
15
SAs and Senselets: Further Details
• Each SA runs a C module that provides a
common runtime environment for senselets
• Senselets are arbitrary Linux binaries
SA
senselet
senselet
Sensor
• Can leverage OpenCV image processing library
• Example senselet: images to parking availability
• Send updates to OAs
• Multiple senselets can share the same sensor feed
• Senselets are uploaded to running SAs
Deployment costs greatly reduced:
Services share same sensors and infrastructure
© Phillip B. Gibbons
IrisNet
16
Creating a New IrisNet Service
Only 500 lines ofFFFFEFF
new code Send to OA
Updates DB
for Parking Space Finder
Image processing steps
Extended code
Senselet
Hierarchy (application-specific
(program to
aggregation)
filter sensor data) (XML schema)
SA
© Phillip B. Gibbons
OAs
IrisNet
Front-end
Query with standard
DB language
SA
17
Outline
• Multimedia Sensor Systems: Opportunities &
Challenges
• IrisNet overview
• IrisNet key features
• Conclusions
© Phillip B. Gibbons
IrisNet
18
IrisNet Key Features
• Distributed data collection and storage
• Support for XML queries for distributed DB
• Transparently routing queries to data
• Automatic data partitioning
• Multi-camera calibration & Image stitching
• Efficient and protected sharing of sensor nodes
• Privacy features
• Triggering and actuation
• Novel fault tolerance schemes
© Phillip B. Gibbons
IrisNet
19
Blind Men and Elephant Problem
• OA’s local DB contains some fragment of the overall
service DB
• Not a federation – A single XML document
• Quickly determining which part of an (XPATH) query
answer can be answered from an XML fragment is a
challenging task, not previously studied
• E.g., can this predicate be correctly evaluated?
• Is the result returned from local DB complete?
• Where can the missing parts be gathered?
© Phillip B. Gibbons
IrisNet
20
Query Evaluate Gather (QEG)
/NE/PA/Allegheny/Pittsburgh/(Oakland | Shadyside) / rest of query
Q
Pittsburgh OA
1. Queries its XML DB
2. Evaluate the result
Discovers Shadyside data
is cached, but not Oakland
Does DNS lookup to find
IP addr for Oakland
3. Gathers the missing data
by sending Q’ to Oakland OA
Combines results & returns
Q’
Oakland OA
QEG
Q’: /NE/PA/Allegheny/Pittsburgh/Oakland/ rest of query
© Phillip B. Gibbons
IrisNet
21
Helping the Blind Men
[Sigmod’03]
• Tag the data
• IrisNet tags the nodes in its fragment with status
info, indicating various degrees of completeness
• Maintains partitioning/tagging invariants
• E.g., when gather data, generalize subquery to
fetch partitionable units
• For each missing part, construct global name from its
id chain & do DNS lookup as before
• Specialize subquery to avoid duplications & ensure
progress
© Phillip B. Gibbons
IrisNet
22
IrisNet’s Query Processing (cont)
• XPATH query converted to an XSLT program that
walks the local XML document & handles the various
tags appropriately
• Conversion done without accessing the DB
IrisNet supports all of XPATH 1.0
Supports (distribution transparent) continuous queries
& application-specific aggregates, predicates, states
(Technically, the unordered projection of XPATH)
© Phillip B. Gibbons
IrisNet
23
IrisNet Key Features
• Distributed data collection and storage
• Support for XML queries for distributed DB
• Transparently routing queries to data
• Automatic data partitioning
• Multi-camera calibration & Image stitching
• Efficient and protected sharing of sensor nodes
• Privacy features
• Triggering and actuation
• Novel fault tolerance schemes
© Phillip B. Gibbons
IrisNet
24
Adaptive Data Partitioning & Placement
Distributed Query Processing
(Internet)
Distributed Storage
Storage
Distributed
Partitioning
Replication
Placement
…
For robustness and performance
Goal: Automate these data-management tasks
© Phillip B. Gibbons
IrisNet
25
Desired Behavior
1. Partitioning +
Placement
2. Replication +
Placement
© Phillip B. Gibbons
IrisNet
26
Problem Statement
Given
Determine
Hierarchical databases
Data
partitioning
Cluster
based on
access locality
Optimize
© Phillip B. Gibbons
Machine capacities
Replication
factor
Data
placement
Write-heavy
Near data
data => few
and
replicas
query sources
Query
latency
Query
traffic
IrisNet
Update
traffic
27
IrisNet Data Placement algorithm
[FAST’05]
• Distributed Algorithm using locally collected stats
• E.g., link use frequency (hierarchy), read/write
ratio, GNP coordinates of readers & writers
• Balances desire to cluster vs. placing near sources
• Replica selection probability ≈ inversely
proportional to recent response time
• Fast response to flash-crowds
• Reacts quickly
• Accounts for delay between off-load decision &
corresponding load decrease
• Approximates globally optimal solution
© Phillip B. Gibbons
IrisNet
28
IDP Adapting to Flash Crowds
IrisNet with IDP
IrisNet without IDP
Response time (sec)
8
6
Flash-crowd
4
2
0
10
20
30
40
50
60
70
80
Time (Minute)
Live PlanetLab deployment with real workload
© Phillip B. Gibbons
IrisNet
29
IrisNet Key Features
• Distributed data collection and storage
• Support for XML queries for distributed DB
• Transparently routing queries to data
• Automatic data partitioning
• Multi-camera calibration & Image stitching
• Efficient and protected sharing of sensor nodes
• Privacy features
• Triggering and actuation
• Novel fault tolerance schemes
© Phillip B. Gibbons
IrisNet
30
Auto-Calibrating Cameras
• Automatic extrinsic calibration
• Many, unattended cameras
• External forces => out-of-band
camera movement
• Goal: Determine physical positions
& orientations of cameras wrt the
scene
• Keypoint algorithm finds
correspondences between cameras
• Key points: rotation & scaling
invariant, plentiful, distinctive
• Calculate homographies & combine images
© Phillip B. Gibbons
IrisNet
31
Improved Key Point Algorithm
SIFT (4/10)
PCA-SIFT (9/10)
[CVPR’04]
White solid – correct matches
Black dotted – incorrect matches
© Phillip B. Gibbons
IrisNet
32
PCA-SIFT In Action
© Phillip B. Gibbons
IrisNet
33
IrisNet Key Features
• Distributed data collection and storage
• Support for XML queries for distributed DB
• Transparently routing queries to data
• Automatic data partitioning
• Multi-camera calibration & Image stitching
• Efficient and protected sharing of sensor nodes
• Privacy features
• Triggering and actuation
• Novel fault tolerance schemes
© Phillip B. Gibbons
IrisNet
34
Network Monitoring using IrisNet
We have deployed IrisNet on the PlanetLab network
• 450+ nodes, 5 continents
• “Sensor” feeds are CPU, memory & network
measurements at each node
Demonstrates wide-area scaling, robustness features
© Phillip B. Gibbons
IrisNet
35
IrisNet’s Deployment on PlanetLab:
Lessons Learned
• Robustness, robustness, robustness
• Platform heterogeneity => VM-based?
• Load balancing
• Processes die; connectivity flaky (on re-connect
incorporate into running aggregate query)
• Correlated failures:
• replication scheme matters: used Signed Quorum
Systems (SQS)
• subtleties arise (can predict 99% of failure
patterns and still not improve availability)
• Importance of relative object assignment
© Phillip B. Gibbons
IrisNet
36
IrisNet’s Availability on PlanetLab
Fraction of available data objects in IrisStore
1
0.9
0.8
Fraction of
available
PlanetLab
nodes
0.7
- 60 - 50 - 40 - 30 - 20
-10
0
Hours before SOSP’05 deadline
• 7 replicas/object with SQS quorum size = 2
© Phillip B. Gibbons
IrisNet
[NSDI’06]
37
Outline
• Multimedia Sensor Systems: Opportunities &
Challenges
• IrisNet overview
• IrisNet key features
• Conclusions
© Phillip B. Gibbons
IrisNet
38
Pervasive Sensing is Emerging
• Planetary-Scale Multimedia Sensor Systems
• Beyond motes: wide-area, broadband, multimedia,
multi-tasked
• Many opportunities for new services
• Many Challenges
• Data & Query Scaling
• System scaling (authoring, robustness)
• System heterogeneity
• Shared resource
© Phillip B. Gibbons
IrisNet
39
A Distributed Systems Nightmare
Planetary-scale Multimedia Sensor Systems are:
Must hide this complexity
• Write-intensive,
time-critical,
high volume, mobile,
from application
developers
heterogeneous, shared, subject to harsh conditions,
include both sensing & actuation
• Continuous/Global/aggregating queries (macroscope)
• Programmed by many developers for many
applications
• …dynamically changing mix
• …sensors shared by many applications
© Phillip B. Gibbons
IrisNet
40
IrisNet: Architecture & Prototype
Two components:
SAs: sensor feed processing
OAs: distributed database
Query
User
Web Server
for the url
...
www.intel-iris.net
open source code,
papers
OA
XML database
OA
XML database
...
SA
SA
senselet
senselet
senselet
senselet
Sensornet
© Phillip B. Gibbons
Sensor
OA
XML database
...
Sensor
SA
senselet
senselet
Sensor
IrisNet
41
IrisNet Team
• Phil Gibbons [project leader, databases, Feb02- ]
• Rahul Sukthankar [computer vision, robotics, Jan03- ]
• Babu Pillai [real-time systems, Sep03- ]
• Jason Campbell [robotics, Oct03- ]
Intel Research
Pittsburgh
• Haifeng Yu [distributed systems, Dec03- ]
• Brad Karp [networking, Nov02-Nov03]
+ many valuable suggestions from M.Satyanarayanan
• Srini Seshan [networking, systems, Mar02- ]
• Suman Nath [grad student, May02-Aug05 ]
• Yan Ke [grad student, Sep02-Apr04 ]
Carnegie Mellon
University
Summer interns: Amol Deshpande [Berkeley], Shimin Chen
[CMU], Dilip Sundarraj [Portland St], Amit Manjhi [CMU],…
© Phillip B. Gibbons
IrisNet
42
Backup Slides
© Phillip B. Gibbons
IrisNet
43
Coastal Imaging using IrisNet
• Working with oceanographers at Oregon State
• Process coastline video to detect & analyze sandbar
formation and riptides, etc
Images from IrisNet prototype
© Phillip B. Gibbons
IrisNet
44
Query-based Image Stitching
• Stitch images from multiple cameras
• What does the LA-region coast look like today?
• How is “this” rip current going to progress
in the next 24 hours?
Use “Key Points” to automatically find
how images fit together (planar scene)
+
© Phillip B. Gibbons
+
IrisNet
=
45
Disconnection-Tolerant Query Processing
• Intermittent sensor disconnections
• Wireless link failures
• Internet delays to remote sites
• Power-saving duty cycles
• Mobile nodes out-of-range
• Why is this important ?
• Disconnected sensors still collecting data
• Data resides only on that node: can’t replicate yet
• Weakest availability link in system
• Query responses based on stale data can be
problematic
© Phillip B. Gibbons
IrisNet
46
Advantage of Disconnection-Tolerant QP
Real World Trace ( 2 sec Delay Jitter Tolerance)
500
Number of Queries
450
432
415
397
400
350
Complete
318
315
100%
300
95-100%
250
200
150
165
127
88
100
50
12 3
81
2 2
90-95%
< 90 %
67
2 1
1 0
14 3
0
30
60
90
120
conventional
Time (in secs)
© Phillip B. Gibbons
IrisNet
47
Relative Object Assignment
ABCD
EFGH
ABCD
ABCD
GHAB
EFGH
CDEF
EFGH
• Do they give us the same availability?
• How large is the difference?
© Phillip B. Gibbons
IrisNet
NO,
Left better
Over 2 nines
for TPC-H
48
Synopsis of Related Work
• Sensor Networks
• Specialized local sensor networks , e.g., home security
• Satellite-based data collection
• Mote-based: local network of sensors with small CPUs
• Large-Scale Distributed Databases
• E.g., PIER (P2P DB), SQL transactions, XML collections
• Multi-Camera Systems & Algorithms
• E.g., VSAM – study detecting & tracking objects
• E.g., Lee at al [PAMI], Stauffer & Tieu [CVPR] – calibration
© Phillip B. Gibbons
IrisNet
49
Logging & Replay of Queries
• Leaf OA detects loss of connection to SA
• Queries and partial results are logged locally
• Partial results sent based on user preference
• Query is replayed only along disconnected branches
SA-1
SA-1
Leaf
Leaf OA
OA
SA-2
SA-2
Replay
Query
Query log
log
Partial
Partial results
results
Disconnected
Reconnected Mode
Mode
© Phillip B. Gibbons
IrisNet
50
Temporal Repair
Temporally Consistent Complete Result
QUERY:
Stitch latest
complete set
of images
(arrives at ‘t’)
1
2
3
Latest complete
set of images at
‘t-x’
4
5
Image at ‘t’
unavailable
At ‘t-x’
Most recent
© Phillip B. Gibbons
At
At ‘t-x’
‘t’
AtAt‘t-x’
‘t’
More recent data
available at ‘t’
IrisNet
51
Actuation Challenges
• Competing actuation: shared resource
• Economic models
• Multiple cameras, set of requests, fidelity based
on resolution & angle
• Real-time control
• Control Theory
• Planning/Coordinating the actuation
• Multiple ways to accomplish the same goal
• Declarative API
• Query-actuated data collection
© Phillip B. Gibbons
IrisNet
52