Transcript princeton-acm-ieee - Department of Computer Science • NJIT

Outdoor Distributed Computing
Cristian Borcea
Department of Computer Science
New Jersey Institute of Technology
Computers Embedded Everywhere
2
Outdoor Distributed Applications
Cars collaborating
for a safer and
more fluid traffic
Distributed object
tracking over a large
geographical area
3
Traditional (Indoor) Distributed
Computing


Commonly, computation is distributed for
performance or fault tolerance
Relatively easy to program
– Nodes are computationally equivalent
– Networking is robust and has acceptable delays
– Configuration is stable
4
Outdoor Distributed Computing

Computation is physically distributed
– Nodes distributed across the physical space
– Location-aware computing

Hard to program
– Nodes are functionally heterogeneous and potentially
mobile
– Ad hoc wireless networks of embedded systems
– Volatile configurations
5
How to Program Outdoor Distributed
Applications?

Recent research in networked embedded systems
has focused on
– Hardware (e.g., Berkeley’s motes, MIT’s crickets)
– Operating Systems (e.g., TinyOS)
– Network Protocols (e.g., Directed Diffusion, SPIN)
– Data collection in sensor networks (e.g., TinyDB)

My research focuses on programmability
– How to write distributed programs over outdoor
networks of embedded systems?
6
Outdoor Programming Example
Left Hill
Right Hill
Motion Sensor
Mobile robot
with camera



Intrusion detection across the hills using motion
sensors and mobile robots with cameras
Number and location of systems are unknown
Configuration is not stable over time
– Intrusions can appear randomly
– Robots can move
7
Traditional Distributed Computing
Does Not Work Well Outdoors




End-to-end data transfers may hardly complete
Fixed address naming and routing (e.g., IP) are
too rigid
Difficult to deploy new applications in existing
networks
Outdoor distributed computing requires novel
programming models and system architectures
8
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation

Outdoor applications: EZCab and TrafficView

Conclusions
9
Traditional (Indoor) Programming
Program
Variable access
Virtual Address Space
Page Table + OS
Physical Memory




Programs access data through variables
Variables mapped to physical memory locations
Page Table and OS guarantee reference consistency
Access time has an (acceptable) upper bound
10
From Indoor to Outdoor Computing
Virtual Address Space Space Region
Variables
Spatial References
Variables mapped to
physical memory
Spatial references mapped
to systems embedded in
the physical space
Reference consistency
?
Bounded access time
?
11
Spatial Programming (SP) at a Glance




Provides a virtual name space over outdoor
networks of embedded systems
Embedded systems named by their locations and
properties
Runtime system takes care of name resolution,
reference consistency, and networking aspects
Implementation on top of Smart Messages: SP
applications execute, sequentially, on each system
referenced in their code
12
Space Regions
Hill = new Space({lat, long}, radius);
{lat,long}
radius



Virtual representation of a physical space
Similar to a virtual address space in a conventional
computer system
Defined statically or dynamically
13
Spatial References
Hill
r2
r7
{Hill:robot[0]}
{Hill:robot[1]}
m5
{Hill:motion[0]}

Defined as {space:property} pairs

Virtual names for embedded systems

Similar to variables in conventional programming

Indexes used to distinguish among similar systems
in the same space region
14
From Indoor to Outdoor Computing
Virtual Address Space Space Region
Variables
Spatial References
Variables mapped to
physical memory
Spatial references mapped
to systems embedded in
the physical space
Reference consistency
?
Bounded access time
?
15
Reference Consistency


At first access, a spatial reference is mapped to an
embedded system located in the specified space
Mappings maintained in per-application Mapping
Table (MT) – similar to a page table
{space, property, index}

{unique_address, location}
Subsequent accesses to the same spatial reference
will reach the same system (using MT) as long as it
is located in the same space region
16
Reference Consistency Example
Right Hill
Left Hill
r5
r2
r7
{Left_Hill:robot[0]}.move = OFF;
ON;
17
Space Casting
Right Hill
Left Hill
r7
{Left_Hill:robot[0]}
{Right_Hill:(Left_Hill:robot[0])}
18
From Indoor to Outdoor Computing
Virtual Address Space Space Region
Variables
Spatial References
Variables mapped to
physical memory
Spatial references mapped
to systems embedded in
the physical space
Reference consistency
Bounded access time
Mapping Table
?
19
Bounding the Access Time

How to bound the time to access a spatial
reference?
– Systems may move, go out of space, or disappear

Solution: associate an explicit timeout with each
spatial reference access
try{
{Hill:robot[0], timeout}.move = ON;
}catch(TimeoutException e){
// the programmer decides the next action
}
20
Spatial Programming Example
Left Hill
Right Hill
- Find the sensor
that detected
the “strongest”
motion on Left Hill
- Turn a camera on
in the proximity
of this sensor
for(i=0; i<1000; i++)
try{
if ({Left_Hill:motion[i], timeout}.detect > Max_motion)
Max_motion = {Left_Hill:motion[i], timeout}.detect;
Max_id = i;
}catch(TimeoutException e)
break;
intrusionSpace = rangeOf({Left_Hill:motion[Max_id].location}, Range);
{intrusionSpace:robot[0]}.camera = ON;
{intrusionSpace:robot[0]}.focus = {Left_Hill:motion[Max_id].location};
21
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation

Outdoor applications: EZCab and TrafficView

Conclusions
22
“Dumb” Messages vs. “Smart” Messages
Lunch:
Appetizer
Entree
Dessert
Data migration
Execution migration
23
Smart Messages at a Glance





User-defined distributed applications
Composed of code bricks, data bricks, and
execution control state
Execute on nodes of interest named by
properties
Migrate between nodes of interest
Self-route at every node in the path during
migrations
24
Cooperative Node Architecture
SM Ready
Queue
SM Admission
Network
Manager
Code
Cache
Virtual SM Network
Machine
SM
Platform
Tag
Space
Operating System & I/O
25
SM Execution at a Node

Takes place over a virtual machine

Non-preemptive, but time bounded

Ends with a migration, or terminates

During execution, SMs can
– Spawn new SMs
– Create smaller SMs out of their code and data bricks
– Access the tag space
– Block on a tag to be updated (update-based
synchronization)
26
Tag Space




Collection of application tags and I/O tags
Application tags: persistent memory across SM
executions
I/O tags: access to operating system and I/O
subsystem
Tags used for
– Content-based naming
migrate(tag)
– Inter-SM communication write(tag, data), read(tag)

– Synchronization
block(tag, timeout)
– I/O access
read(temperature)
Protection domains for access control
27
SM Admission





Ensures progress for all SMs in the network
Prevents SMs from migrating to nodes that cannot
provide enough resources
SMs specify lower bounds for resource
requirements (e.g., memory, bandwidth)
SMs accepted if the node can satisfy these
requirements
More resources can be granted according to
admission policy
– If not granted, SMs are allowed to migrate
28
Application Example
need
2 taxis
n=0
n=0
Taxi
Taxi
n=0
n=1
n=0
while (n<NumTaxis)
migrate(Taxi);
if (readTag(Available))
writeTag(Available, false);
writeTag(Location, myLocation);
n++;
n=1
n=2
SM
data brick
application
code brick
routing
code brick
29
SM Migration
migrate(Taxi)
Taxi
1
Taxi
sys_migrate(2)

2
sys_migrate(3)
3
sys_migrate(4)
4
migrate()
– migrates application to next node of interest
– names nodes by tags
– implements routing algorithm

sys_migrate()
– one hop migration
– used by migrate to implement routing
30
Routing Example
1
2
i
Network
RouteToTaxi = 2
RouteToTaxi = j?
migrate(Taxi){
while(readTag(Taxi) == null)
if (readTag(RouteToTaxi))
sys_migrate(readTag(RouteToTaxi));
else
create_SM(DiscoverySM, Taxi);
createTag(RouteToTaxi, lifetime, null);
block_SM(RouteToTaxi, timeout);
}
Taxi
31
SM Self-Routing

SMs carry the routing and execute it at each node

Routing information stored in tag space

SMs control their routing
– Select routing algorithm (migrate primitive)

Multiple library implementations

Implement a new one
– Change routing algorithm during execution in response to

Adverse network conditions

Application’s requirements
32
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation

Outdoor applications: EZCab and TrafficView

Conclusions
33
Spatial Programming Implementation
Using Smart Messages

SP application translates into an SM
– Spatial reference access translates into an SM
migration to the mapped node
– Embedded system properties: Tags


SM self-routes using geographical routing and
content-based routing
Reference consistency
− Unique addresses (stored in mapping table) are unique
tags created at nodes
− SM carries the mapping table
34
SM Prototype Implementation

Modified version of Sun’s Java K Virtual Machine
– Small memory footprint (160KB)


SM and tag space primitives implemented inside
virtual machine as native methods (efficiency)
I/O tags: GPS location, neighbor discovery,
image capture, light sensor, system status
Ad hoc networks of
HP iPAQ PDAs running Linux
35
Smart Phones: The Mobile Computers
of the Future



Accessing our mobile data anytime/anywhere
Proximity-aware interactions with embedded
systems and services
Developed SM implementation that works over
unmodified Java Virtual Machines using bytecode
instrumentation
36
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation

Outdoor applications: EZCab and TrafficView

Conclusions
37
Booking Cabs on Broadway
The nightmare!
Phase1: Fight with other
people for a cab
Phase2: Call a dispatching
center … and wait, and wait
38
EZCab System Overview
Need
a cab


Use mobile ad hoc networks of
cabs to book a free cab
Each cab has short-range
wireless interface and GPS
39
EZCab Implementation

Prototype over Smart Messages
– Evaluated over small scale networks (8 nodes)

Developed and simulated probabilistic routing
algorithms to find free cabs
– Each routing table entry corresponds to a neighbor
address and the estimated probability to find a free
cab through it
– Probabilities account for the distance and number of
free cabs reachable through a neighbor
– Proactive probabilistic routing works best
40
How to Provide Dynamic, Real-Time
View of the Road Traffic?
On foggy days
What’s in
front of
that bus?
On rainy days
What’s
behind the
bend?
41
TrafficView System Overview


Uses vehicle-to-vehicle ad hoc networks
Vehicles have embedded computer, GPS receiver, and
short-range wireless interface (IEEE 802.11)
Traffic
Information
Displayed in the
Last Car
3 cars on Route 1
42
TrafficView Implementation

Implemented in C over Linux
– In the process of porting it over Smart Messages


Developed accurate road identification software
Designed and evaluated scalable data aggregation
algorithms
– Use aggregation to put as much data as possible in one
packet
– Aggregate data for vehicles that are close to each
other
– Perform more aggregation as distance increases
– Maintain “acceptable” accuracy loss
43
Conclusions

Spatial Programming makes outdoor distributed
computing simple
– Volatility, mobility, configuration dynamics, ad hoc
networking are hidden from programmer

Implementation on top of Smart Messages
– Easy to deploy new applications in the network
– Quick adaptation to highly dynamic network
configurations

Demonstrated real-life outdoor distributed
applications
44
What should we expect in the future?

Pervasive computing applications will span nontraditional computing domains
– Healthcare, transportation, homeland security, etc.

To make the pervasive computing a reality, we
need a significant amount of system research
– Crossroad between networking, operating systems,
embedded systems, human-computer interaction,
computer vision, etc.

Inter-disciplinary research is the key to success
in pervasive computing
– Collaborations with civil engineering, cognitive sciences,
biology, etc.
45
Acknowledgments


Liviu Iftode, Ulrich Kremer, Chalermek
Intanagonwiwat
Porlin Kang, Nishkam Ravi, Deepa Iyer, Akhilesh
Saxena, Peng Zhou, Tamer Nadeem, Bogdan
Dorohonceanu
46
Thank you!
http://www.cs.njit.edu/~borcea/
47