Transcript Spatial Programming Using Smart Messages - Disco Lab

Spatial Programming using
Smart Messages:
Design and Implementation
Cristian Borcea, Chalermek Intanagonwiwat,
Porlin Kang, Ulrich Kremer, and Liviu Iftode
Department of Computer Science
Rutgers University
Computers Go Outdoors, Embedded
Everywhere in the Physical World
Cars collaborating
for a safer and
more fluid traffic
Distributed object
tracking over a large
geographical area
2
Traditional (Indoor) Distributed
Computing


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
3
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
4
Example
Left Hill
Right Hill
Mobile sprinkler
with temperature
sensor
Hot spot

“Water the hottest spot on the Left Hill”
Number and location of mobile sprinklers
are unknown

Configuration is not stable over time

–
Sprinklers move
–
Temperature changes
5
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
abstractions and programming models
– How to write outdoor distributed applications?
– How to deploy new applications in existing networks?
6
Outline

Motivation

Spatial Programming (SP) Model

SP Implementation using Smart Messages

SP Application

Conclusions
7
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
8
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
?
9
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
10
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
11
Spatial References
Hill
r2
{Hill:robot[0]}
{Hill:robot[1]}
r7
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
12
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
13
Reference Consistency Example
Right Hill
Left Hill
r5
r2
r7
{Left_Hill:robot[0]}.move = OFF;
ON;
14
Space Casting
Right Hill
Left Hill
r7
{Left_Hill:robot[0]}
{Right_Hill:(Left_Hill:robot[0])}
15
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 the
spatial reference access
try{
{Hill:robot[0], timeout}.move = ON;
}catch(TimeoutException e){
// the programmer decides the next action
}
16
Spatial Programming Example
Left Hill
Right Hill
Mobile sprinkler
with temperature
sensor
Hot spot
Water the hottest spot on the Left Hill
for(i=0; i<1000; i++)
try{
if ({Left_Hill:Hot[i], timeout}.temp > Max_temp)
Max_temp = {Left_Hill:Hot[i], timeout}.temp;
Max_id = i;
}catch(TimeoutException e)
break;
{Left_Hill:Hot[Max_id], timeout}.water = ON;
17
Outline

Motivation

Spatial Programming (SP) Model

SP Implementation using Smart Messages

SP Application

Conclusions
18
Smart Messages at a Glance

Smart Message (SM)
– User defined distributed application similar to a
mobile agent
– Executes on nodes of interest named by properties
– Migrates between nodes of interest using self-routing

Self-Routing
– Application-level routing executed at every node
– Applications can change routing during execution

Cooperative Nodes
– Execution environment (Virtual Machine)
– Memory addressable by names (Tag Space)
– Code cache
19
Smart Messages Prototype

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)
Implemented I/O tags: GPS location, neighbor
discovery, image capture, light sensor, system
status
20
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
21
SP to SM Translation: Example
Left Hill
Right Hill
Spatial Reference Access Max_temp = {Left_Hill:Hot[1], timeout}.temp;
Mapping
{Left_Hill,Hot,1}
Table
Smart Message
Code
{yU78GH5,location}
ret = migrate_geo(location, timeout);
if (ret == LocationUnreachable)
ret = migrate_tag(yU78GH5, timeout);
if ((ret == OK) && (location == Left_Hill))
return readTag(temp);
else throw TimeoutException
22
SP Application: Intrusion Detection
Ad hoc network: HP iPAQs with 802.11 cards and GPS devices
monitored
space
Code Size breakdown for SM
(Application + SP Library)
user node
light sensor
camera node
regular node
Code Size breakdown for
SP library
23
Execution Time Breakdown
24
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
25
Thank you!
http://discolab.rutgers.edu/sp/
26