Transcript Playing Distributed Systems with Memory-to

Outdoor Distributed Computing
Liviu Iftode
Department of Computer Science
Rutgers University
http://discolab.rutgers.edu
Supported by NSF through ITR grant ANI-0121416
Traditional Programming Model
Program
Variable access
Virtual Address Space
Page Table + OS
Physical Memory
 Programs access data through variables
 Variables mapped to physical memory locations
 Runtime + OS guarantees reference consistency
 Access time has an (acceptable) upper bound
“Indoor” Distributed Computing
 Computing distributed for performance or fault tolerance
 Nodes are computationally equivalent
 Configuration is stable (failures are exceptions)
 Networking is robust and has acceptable delays
 Relatively easy to program
Message passing or shared memory
Naming easy to translate to network addresses
Correct programs complete and return deterministic results
Computers “Move” Outdoors
Distributed object
tracking over a large
geographical area
Cars collaborating
for a safer and
more fluent traffic
Outdoor Distributed Systems
Sensors
Linux Watch
Linux Camera
Linux Car
 Nodes are volatile and/or mobile: dynamic configurations
 Networking is wireless and ad-hoc: unpredictable delays
 Location dictates the computation: naming must include
location
 How to program and execute distributed applications
outdoors?
Traditional distributed computing does not work
How to Program Outdoor Distributed
Embedded Systems?
Recent research in networked embedded systems
Hardware
Operating Systems
Network Protocols
Data collection/dissemination in sensor networks
Our research focuses on programmability
How to code distributed applications to execute over
networks of embedded systems?
Traditional Distributed Computing
Does Not Work Well over Ad-Hoc
Fixed address naming and routing (e.g., IP)
are too rigid
End-to-end data transfer may hardly
complete
Outdoor distributed computing requires
novel system architectures and programming
models
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 is unknown
Configuration is not stable in time
 sprinklers move
 temperature changes
What is a good result?
Quality of Result
QoR
100%
ideal
real
0
100%
Outdoors Adversity
Talk at a Glance
 Outdoor Programming Model
 Outdoor Execution Model
 Applications
Outdoor Programming
Left Hill
Right Hill
– How to program an unknown number of mobile systems
to execute an intrusion detection application in a certain
physical space?
- Programming model must be simple to use
- Networking aspects should be hidden from programmer
- Access to mobile systems as simple as access to variables
- A virtual address space for the physical space?
Sequential Programming Example
struct temp a[N];
for(i=0;i<N;i++) {
if (a[i].temp> Max_temp) {
Max_temp = a[i].temp;
Max_id = i;
}
}
a[Max_id].water = ON;
Distributed Programming using
Message Passing
Struct temp a[N/P], b[P];
for(i=0;i<N/P;i++) {
if (a[i].temp> Max_temp) {
Max_temp = a[i].temp;
Max_id = i;
}
}
send(0,Max_temp,sizeof(int));
If (my_node_id == 0) {
for(i=0;j<P;i++)
recv(i,&b[i],sizeof(int));
<compute max of b: b_max is in b_max_id>
…
Software Distributed Shared Memory
Distributed Application
Variable accesses
Shared virtual address space
Page Table + Message Passing
Physical memories
 Applications access distributed data through shared
variables
 Runtime system translates variable accesses into
message passing (when necessary)
Shared Memory Distributed Computing
struct a[N], b[P];
Thread worker(k) {
int Max_temp, Max_id,i;
for(i=k*N/P; i< (k+1)*N/P; i++) {
if (a[i].temp> Max_temp) {
Max_temp = a[i].temp;
Max_id = i;
}
}
b[k]=Max_temp;
barrier()
if (k==0) {
<calculate b_max and b_max_id>
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
?
Spatial Programming (SP) at a Glance
Outdoor distributed applications are
programmed using spatial references
A virtual address space hides networking
Embedded systems/nodes named by their
expected locations and properties
Space Region
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
Spatial References
Hill
{Hill:robot[0]}
{Hill:robot[1]}
{Hill:truck}
– Defined as {space:property} pairs
–Similar to variables in conventional programming
–Used to name systems embedded in physical space
–Indexes used to distinguish among similar systems in
the same space region
-Same index maps to the same system (reference consistency)
-Distinct indexes map to distinct systems
Reference Consistency
At the time of the first access, a spatial reference
is mapped to an unmapped embedded system
located in the specified space
Mappings maintained in per-application Mapping
Tables (MT)
{space, property, index}
{network_address, location}
A spatial reference refers the same system as long
as it is located in the same space, fails otherwise
Reference Consistency
{Hill:robot[0]}
Left Hill
{Hill:robot[1]}
For (i=0;i<1000;i++)
{Left_Hill:robot[i]}.stop =ON;
Right Hill
Reference Consistency (con’t)
Left Hill
Right Hill
{Left_Hill:robot[0]}.move = ON;
Left Hill
Time
Right Hill
{Left_Hill:robot[0]}.move = OFF;
Space Casting
Left Hill
time
Right Hill
{Right_Hill:robot[0]}
Left Hill
{Left_Hill:{Right_Hill:robot[0]}}
Right Hill
Relative Spaces
Left Hill
Right Hill
{rangeOf({Left_Hill:robot[0]}, radius):robot[0]}
Space Composition
Left Hill
Right Hill
{(Left_Hill + Right_Hill):robot[0]}
Bounding the Access Time
 A spatial reference can take an infinite time
Discover an unmapped system for a new spatial reference
Mapped systems may move, go out of space, or disappear
 How to bound the time to access a spatial reference?
 Associate an explicit timeout with each spatial reference
access
try{
{Hill:robot[0], timeout}.camera = ON;
}catch(TimeoutException e){
// the programmer decides the next action
}
Configuration Changes During Execution
System
State
Hills
{Hills:robot[0]}
Hills
{Hills:robot[2]}
Hills
{Hills:robot[1]}
Execution
Time
Spatial Programming Example
Left Hill
Right Hill
Mobile sprinkler
with temperature
sensor
Hot spot
Application: 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]}.water = ON;
Talk at a Glance
 Outdoor Programming Model
 Outdoor Execution Model
 Applications
Smart Message Architecture
Smart Message (SM)
User-defined distributed application
Executes on nodes of interest named by
properties
Migrates between nodes of interest
Self-Routing
Application-controlled routing to perform
migration
Executed on every node on the path between
nodes of interest
Cooperative Nodes
Execution environment (Virtual Machine)
Memory addressable by names (Tag Space
Smart vs. “Dumb” Messages
Mary’s lunch:
Appetizer
Entree
Dessert
Data migration
Execution migration
•`
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
data brick
application
code brick
routing
code brick
Cooperative Node Architecture
SM Ready
Queue
SM Admission
Network
Manager
Code
Cache
Virtual SM Network
Machine
SM
Platform
Tag
Space
Operating System & I/O
Smart Message Admission
Prevents SMs from migrating to nodes where they
cannot execute
SMs specify resources requirements
Lower bounds for virtual machine cycles, tag space
memory, runtime memory, network bandwidth, etc.
Specified by programmer or derived using compiler
support
SMs accepted if the node can satisfy SM
requirements
SMs transfer only the missing code bricks
More resources can be granted according to
admission policy
If not granted, SM is allowed to migrate
Smart Message Execution
Takes place over a virtual machine
Non-preemptive but time bounded
Ends with migration or terminates
During execution, SMs can
Create new SMs
Spawn new SMs
Access the tag space
Block on a tags to be updated
Tag Space
 Local memory that SMs can use
SM-created tags: limited lifetime, persistent across SM
executions
I/O tags: maintained by the system
 Multiple Roles
Node addressing
migrate (tag,timeout)
I/O port access
read (temperature)
Store data
write (tag,value)
Inter -SM communication
Synchronization on write block(tag,timeout)
Routing
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
creates the tag
 Origin: all SMs created on the same node as the family
originator of the tag owner
 Code: all SMs that carry the same code brick(s)
 Others: all SMs
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
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
data brick
application
code brick
routing
code brick
Migration
migrate(Taxi)
Taxi
1
Taxi
sys_migrate(2)

2
sys_migrate(3)
3
sys_migrate(4)
migrate()
4
– implements routing algorithm
– migrates application to next node of interest
– node of interest named by tags
– sys_migrate()
– one hop migration
– used in migrate to implement routing
Routing Example
1
2
i
Network
RouteToTaxi = 2
RouteToTaxi = j?
migrate(Taxi){
while(!readTag(Taxi))
if (readTag(RouteToTaxi))
sys_migrate(readTag(RouteToTaxi));
else
create_SM(DiscoverySM, Taxi);
createTag(RouteToTaxi, lifetime, null);
block_SM(RouteToTaxi, timeout);
}
Taxi
Self-Routing
SMs carry the routing brick and execute it at each
node
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
Dynamic Change of Routing
SM starts with
proactive routing
migrate(Taxi, timeout1)
Dense network
Low mobility
Proactive routing
Sparse network
High mobility
On-demand routing
migrate timeouts
SM changes routing to on-demand
migrate(Taxi, timeout2)
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)
 Implemented I/O tags: GPS location, neighbor discovery,
image capture, light sensor, system status
Prototype Node with GPS
receiver and video camera
Lightweight Migration
Traditional process migration difficult
 Strong coupling between execution entity and host
 OS state (e.g., open sockets, file descriptors) hard
to transfer
Tag space decouples the SM execution state
from the OS state
SM migration transfers
Data bricks explicitly specified by programmer as
mobile data
Minimal execution control state required to resume
the SM at the next node (e.g., instruction pointer,
operand stack pointer)
Experimental Results for Simple
Routing Algorithms
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
Self-Routing Simulation
On-Demand Routing versus Geographic and On-Demand Routing
3 nodes of interest located in the corners
have to be visited in clockwise order
 vary the radius from 100m to 700m

starting node
On-Demand Routing
node of interest
Geographic+On-Demand Routing
On-Demand Routing
Geographic+On-Demand Routing
4500
Bytes Sent in the Network (KBytes)
3
Completion Time (sec)
other node
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
SP Implementation using SM
 SP application -> SM
 Embedded system properties -> Tags
 SM self-routing
Content-based routing using tags
Geographical routing
 Reference consistency
unique tag created on the node which a spatial reference is
mapped to
MappingTable (MT) maps spatial reference to the unique tag
and expected location
MT is carried by the SM that implements the SP application
 Spatial reference access -> an SM migration to the
node where the spatial reference is mapped to
SP using SMs: Example
Right Hill
Left Hill
Mobile sprinkler
with temperature
sensors
Hot spot
Spatial Reference Access Max_temp = {Left_Hill:Hot[1], timeout}.temp;
MT
Smart Message
Code
Brick
{Left_Hill,Hot,1}
{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
SP Application: Intrusion detection
Testbed: 10 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
Execution Time Breakdown
Talk at a Glance
 Outdoor Programming Model
 Outdoor Execution Model
 Applications
Intelligent Distributed Transportation
Systems
Infrastructure-free approach based on car-to-car
communication

short-range wireless communication
 location information from GPS receiver
 vehicle’s data from sensors through on-board diagnostic
system (OBD-II)

Two projects:
EZCab: An Automatic System
for Booking Cabs
Traffic Viewer: A Scalable
Traffic Monitoring System
EZCab Idea
allow people to book cabs in dense cab area
using ad-hoc networking
Finding Free Cabs
Booking a cab
Phase 2 & 3: Report and Validation
TrafficView
• Enable drivers to monitor traffic in front of their cars,
farther than they can see
• Based exclusively on vehicle-to-vehicle ad hoc
communication
How TrafficView Works
Receive data from
remote vehicle
Local data
Broadcast data
Validate
Non-validated
dataset
Validated
dataset
Display
Data Aggregation
How to aggregate data to collect monitor
vehicles as far as possible with “acceptable”
accuracy loss
Natural Solution
Aggregate data for vehicles that are close to each
other
Perform more aggregation as distance increases
Smart Phones as Universal Personal
Servers
Mobile phones and PDAs converge into Smart Phones
Programmable
Dual-connectivity (BT & GPRS)
How to build pervasive applications on them?
Summary
 Spatial Programming makes outdoor distributed
computing simple
 Volatility, mobility, configuration dynamics, ad-hoc
networking are all hidden from programmer
 Spatial Programming can be implemented using
Smart Messages
 Outdoor applications: intelligent transportation,
pervasive computing using smart phones
Acknowledgements
 Faculty
Uli Kremer (check our PLDI’05 paper!)
 Graduate Students
Cristian Borcea (currently on the NJIT faculty)
Porlin Kang
Nishkam Ravi
Pravin Shankar
Peng Zhou
Deepa Iyer
Akhilesh Saxena
 Visitors
Chalermek Intanagonwiwat (post-doc, currently on the
faculty of Chulalongkorn University, Thailand)
Oriana Riva (grad student, University of Helsinki)
Tamer Nadeem (grad student, UMD)
Marios Dikaiakos (faculty, Univ of Cyprus)
 Undergraduate students:
Niket Desai, Peter Stern, Yan Nuriyev
Thank you!
http://discolab.rutgers.edu