Transcript Document

Cooperative Computing for Distributed
Embedded Systems*
Cristian Borcea, Deepa Iyer, Porlin Kang,
Akhilesh Saxena, and Liviu Iftode
Division of Computer and Information Sciences
Rutgers University
* Work supported in part by the NSF under the ITR grant ANI-0121416
1
Programming Challenge

How to program ?

A single computer

Parallel computers

Networks of computers

Next challenge: Networks of Embedded Systems
(NES)

How to program NES to perform distributed tasks ?
2
Networks of Embedded Systems (NES)
Sensor
Networks
Intelligent
Highways
Collaborative
Robots
Wildlife
Monitoring

Large scale, ad hoc networks

Heterogeneous node functionality: sensors, intelligent
cameras, smart appliances

Limited resources: CPU, memory, bandwidth, energy

Wireless Communication: 802.11, Bluetooth

Volatile, possibly mobile
3
Sensor Networks
Data dissemination

Programmability issues:



Data collection
How to add a new application ?
How to execute user-defined applications ?
Our goal: a general programming model for NES
4
Traditional Distributed Computing Does
Not Work for NES


Traditional distributed computing

Stable configuration of functionally homogeneous nodes

Fixed-address naming and routing (e.g., IP)

Failures are exceptions
Networks of Embedded Systems

Ad hoc configurations of nodes with different properties

Content-based naming and routing

Volatile nodes are common
5
Outline

Motivation

Cooperative Computing

Smart Messages (SM)

Tag Space

Node Architecture & SM Lifecycle

API & Examples

Prototype & Simulation Results

Conclusions
6
Execution Migration Example
Bob’s dinner:
Appetizer
Entree
Dessert
Data migration
Execution migration
7
Cooperative Computing

Distributed computing over NES based on execution
migration

Smart Messages (SM)

User-defined applications which migrate through the network

Execute at each node in the path
• Application executes at nodes of interest
• Migration occurs between nodes of interest

Tag Space

Name-based node memory

Persistent across SM executions

Used by SM for addressing, storage, synchronization, I/O access
8
Smart Messages (SM)
Code
Bricks
Data
Bricks
Execution
State
Signature
Resource
Table

Code Bricks: application & routing code

Data Bricks: mobile data carried by SM during migration

Execution State: used for execution migration

Signature: access control to Tag Space

Resource Table: tags to be accessed, memory, CPU cycles, and
generated traffic estimates
9
Tag Space

Tag structure

Application tags


Appetizer
Signature Lifetime
SM_Sign
10 hours
Data
5$
Created by SMs
I/O tags

Name
Neighbors
Node1,Node2
Provide interface to OS and I/O system
10
Node Architecture
SM Arrival Admission
Manager
Virtual
Machine
SM Migration
Tag Space
OS & I/O
11
Admission Control

At arrival each SM presents its resource requirements

Admission manager decides whether or not to accept an
SM

Each accepted SM becomes a task ready for scheduling

Optimization: code bricks are cached upon SM acceptance
12
Execution

Takes place over a virtual machine (VM)

Non-preemptive, but time bounded

Interrupted by SM admission

May block on tags to be updated

Terminate or continue on another node (SM migration)
13
Migration
Appetizer
$5
eat(Appetizer);
migrate_SM(Entree);
eat(Entree);
Entree
Network

migrate_SM is a user-level library call

Implements content-based routing using

eat(Appetizer);
migrate_SM(Entree);
eat(Entree);
A one-hop migration primitive: sys_migrate


$10
Captures execution state, transfers SM one hop, resumes execution
Routing tags
14
Self Routing
route_to_Entree 2
1
route_to_Entree 3
sys_migrate(2)
2
route_to_Entree 4
sys_migrate(3)
3
Entree $10
sys_migrate(4)
4
migrate_SM(Entree, timeout)

Application controls routing in two ways:

Can choose among multiple migrate_SM implementations

Can change its routing algorithm during execution
15
Cooperative SMs
 Applications can be dynamic collections of SMs
cooperating to perform a distributed task
Route_to_Entree
route_to_Entree
next_hop
?
ifif(!route_to_Entree)
(!route_to_Entree)
DiscoverySM
create_SM(DiscoverySM,
create_SM(DiscoverySM, Entree);
Entree);
block_SM(route_to_Entree);
block_SM(route_to_Entree);
sys_migrate(next_hop);
sys_migrate(next_hop);
Network
DiscoverySM
16
Smart Messages API


Operations on Tag Space

createTag(name, lifetime, data), deleteTag(name)

readTag(name), writeTag(name, value)
SM Creation


SM Spawning


spawn_SM()
SM Synchronization


create_SM(code_bricks, data_bricks)
block_SM(tag_name, timeout)
SM Migration

migrate_SM(tag_names, timeout), sys_migrate(next_hop)
17
Code Example
Application:
migrate_SM(appetizer, timeout);
eat(appetizer);
migrate_SM(entree, timeout);
eat(entree);
migrate_SM(dessert, timeout);
eat(dessert);
migrate_SM(home, timeout);
migrate_SM:
while(!readTag(tag))
if (readTag(route_to_tag))
sys_migrate(readTag(route_to_tag));
else
create_SM(DiscoverySM, tag);
block_SM(route_to_tag, timeout);
DiscoverySM:
//forward
do{
sys_migrate(All_Neighbors);
createTag(prev_to_tag, lifetime, prev_hop());
}while(!(readTag(tag) || readTag(route_to_tag)));
//backward
do{
sys_migrate(readTag(prev_to_tag));
createTag(route_to_tag, lifetime, prev_hop());
}while(readTag(prev_to_tag));
writeTag(route_to_tag, prev_hop());
18
Evaluation goals

Expressiveness


Performance


Ability to implement various user-defined distributed applications
Cost of execution migration vs. data migration
Practicality

SM prototype
19
Prototype Implementation

Compaq’s iPAQs running Linux

802.11 & Bluetooth for wireless communication

Modified version of Sun’s Java KVM
20
Micro-benchmark Results
Tag Space Operation Time (microsec)
createTag
55.8
deleteTag
30.8
readTag
25.0
writeTag
28.0
block_SM
24.6
 Processor: 206 MHz Intel StrongARM
 Bandwidth: 11 Mbps (802.11), 1Mbps (Bluetooth)
 Single SM execution with one-hop discovery
 SM: 829 bytes (731 code, 20 data, 78 stack)
 55.2 ms with 802.11
 452.8 ms with Bluetooth
21
Simulation

Event-driven simulator extended with support for SM
execution



Accounts for both communication and computation time
Accurate measurements for execution time by counting at
the VM level the number of cycles per VM instruction

Each node is simulated by a Java thread

Thread scheduling controlled by simulator
Implemented two previously proposed applications for
sensor networks using SMs:

Data collection: Directed Diffusion [Estrin ’99]

Data dissemination: SPIN [Heinzelman ’99]
22
Smart Messages vs. Message Passing
Directed Diffusion
SPIN
23
Related Work

Mobile Agents

Active Networks

Mobile ad hoc networking

Pervasive Computing

Sensor Networks
24
Conclusions

Propose Cooperative Computing and Smart Messages for
programming Networks of Embedded Systems (NES)

Implement and evaluate two SM distributed applications

Smart Messages offer a promising programming model for
NES

SM software distribution to be released this summer
25
Future Work

Security


Distributed trust model for SM
Energy

Use the simulator to design and analyze energy efficient routing
algorithms

Spatial Programming with SM

We propose it as a novel paradigm for programming NES

Network resources represented as {space:tag} spatial references

Translation from SP programs to SM programs
26
Thank you !
http://discolab.rutgers.edu/sm/
27
SM Admission Protocol
Source
Destination
resource table and code brick IDs
IDs for code bricks not cached at destination
data bricks and missing code bricks
insert task in Ready Queue
28