Transcript Programming Outdoor Distributed Embedded Systems

Outdoor Distributed Computing*
Cristian Borcea
Department of Computer Science
New Jersey Institute of Technology
* Work done at Rutgers prior to September 2004
Computers Embedded Everywhere
2
Outdoor Distributed Applications
Cars collaborating
for a safer and
more fluid traffic

Distributed object
tracking over a large
geographical area
How to write distributed programs over outdoor
networks of embedded systems?
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
Outdoor Programming Example
Left Hill
Right Hill
Motion Sensor
Mobile robot
with camera



Intrusion detection across the hills using motion
sensors and autonomous mobile robots with
cameras
Number and location of systems are unknown
Configuration is not stable over time
– Intrusions can appear randomly
– Robots can move
6
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
7
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation Details

Experimental Results

Conclusions
8
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
9
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
?
10
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
11
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
12
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
13
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
?
14
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
15
Reference Consistency Example
Right Hill
Left Hill
r5
r2
r7
{Left_Hill:robot[0]}.move = OFF;
ON;
16
Space Casting
Right Hill
Left Hill
r7
{Left_Hill:robot[0]}
{Right_Hill:(Left_Hill:robot[0])}
17
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
?
18
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
}
19
Spatial Programming Example
Left Hill
Right Hill
- Find the sensor
that detected
the “strongest”
motion on Left Hill
- Turn on a camera
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};
20
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation Details

Experimental Results

Conclusions
21
“Dumb” Messages vs. “Smart” Messages
Lunch:
Appetizer
Entree
Dessert
Data migration
Execution migration
22
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
23
Cooperative Node Architecture
SM Ready
Queue
SM Admission
Network
Manager
Code
Cache
Virtual SM Network
Machine
Authorization
SM
Tag
Platform Space
Operating System & I/O
24
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)
25
Tag Space

Collection of application tags and I/O tags
– Essentially, tags are (name, value) pairs



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)
26
Protection Domains for Tag Space
Owner
Origin





Family
Code
Others
Owner: SM that creates the tag
Family: all SMs having a common ancestor with the
SM that owns the tag
Origin: all SMs created on the same node as the
family originator of the tag owner
Code: all SMs carrying a specific code brick
Others: all the other SMs
27
Access Control Example
(Code-based protection domain)
SM1
SM1
C1 Cr
Code
Bricks
Node1
Node2
SM2
SM2
Node3
C2 Cr
SM2
SM1
SM3
C3 C4
Node5
Node4
Tag
Owner = SM1
[Hash(Cr), RW]
Cr
Same routing used by SM1 and SM2
Access permission granted for SM2
Access permission denied for SM3
28
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
29
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
30
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
31
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
32
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
33
Self-Routing Simulation Results
Geographic + On-Demand Routing performs
better than simple on-demand routing
 25%-40% decrease in completion time
 62%-92% reduction in amount of bytes
starting node
sent in the network
node of interest - Less energy and bandwidth consumption
other node

On-Demand Routing
Geographic+On-Demand Routing
On-Demand Routing
4500
Bytes Sent in the Network (KBytes)
3
Completion Time (sec)
Geographic+On-Demand Routing
2.5
2
1.5
1
0.5
0
0
100
200
300
400
500
Region Radius (meters)
600
700
800
4000
3500
3000
2500
2000
1500
1000
500
0
0
100
200
300
400
500
Region Radius (meters)
600
700
800
34
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation Details

Experimental Results

Conclusions
35
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
36
SP to SM Translation: Example
Left Hill
Spatial Reference
Access
Smart Message
Right Hill
Max_motion = {Left_Hill:motion[1], timeout}.detect;
Mapping
{Left_Hill,motion,1}
Table
Code
Brick
{yU78GH5,location}
ret = migrate_geo(location, timeout);
if (ret == LocationUnreachable)
ret = migrate_tag(yU78GH5, timeout);
if ((ret == OK) && (location == Left_Hill))
return readTag(detect);
else throw TimeoutException
37
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
38
Lightweight Migration

Traditional process migration difficult
– Strong coupling between execution entity and host
– Needs to take care of operating system state (e.g.,
open sockets, file descriptors)


Tag space decouples the SM execution state
from the operating system state
SM migration transfers only
– Data bricks explicitly specified by programmer
– Minimal execution control state required to resume
the SM at the next instruction (e.g., instruction
pointer, operand stack pointer)
39
Outline

Motivation

Spatial Programming Model

Smart Messages System Architecture

Implementation Details

Experimental Results

Conclusions
40
Micro-benchmark Results
7
30
Java object array
Java int array
6
Code Uncached
25
Code Cached
5
Time (ms)
Tme (ms)
20
4
3
15
10
2
5
1
0
0
2
4
8
16
Size (KBytes)
Cost of data serialization
1224
2236
4294
Code Size (Bytes)
8383
Cost of single hop migration
41
Experimental Results for Simple
Routing Algorithms
8 HP iPAQs running Linux and using
IEEE 802.11 for wireless communication
user node
node of interest
intermediate node
Routing algorithm Code not cached (ms) Code cached (ms)
Geographic
415.6
126.6
On-demand
506.6
314.7
Completion Time
42
SP Application: Intrusion Detection
10 HP iPAQs with 802.11 cards and GPS devices
monitored
space
user node
light sensor
camera node
regular node
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

Acknowledgments: Liviu Iftode, Ulrich Kremer,
Chalermek Intanagonwiwat, Porlin Kang
44
Other projects based on Smart Messages

Portable Smart Messages: work over unmodified
JVMs using bytecode instrumentation (done by
Nishkam)
– Tested on iPAQs, Ericsson P900, and Nokia Communicator


Context-aware Migratory Services in Ad Hoc
Networks (Oriana will present it after this talk)
Spatial Views: A location-aware, declarative
programming language (Uli Kremer will present it on
Friday)
45
Two of my current projects

Intelligent distributed transportation systems
– Sponsored by NSF, collaboration with Rutgers University
(Pravin will talk about it in the afternoon)
– Design a vehicular network architecture and build a
prototype for distributed computing over vehicular
networks

SmartCampus
– Sponsored by NSF, joint work with IS & ECE
departments at NJIT
– Investigate mobile computing applications, protocols,
middleware over a campus-wide, location-aware, mobile
community test-bed (100s of users with mobile devices)
46
Thank you!
http://www.cs.njit.edu/~borcea/
47