Transcript Nomadic Information Access in the Oxygen Project

Nomadic Information Access
Hari Balakrishnan
S. Devadas, F. Kaashoek, D. Karger, R. Morris,
K. Steele, I. Stoica, S. Teller & Several Students
MIT Project Oxygen
DARPA Ubiquitous Computing Meeting
January 22, 2002
Imagine this…
• Harry wakes up in the morning later than he should have. He
has a 7am flight to catch.
• He starts downloading huge ppt files and his email while he gets
ready. He’s ready to leave but the download isn’t complete.
Cursing, he aborts it and decides to deal with it in DC.
• He reaches the airport and has a few minutes to spare. He
starts to download things again. Same problem.
• He reaches DC and makes his meeting on time, but he still has
to work on his slides. He gets a network connection and starts
the painful download. His connection to his office server is
reeeeeeallly slow.
• An hour later, he’s finally ready to start on pulling today’s talk
together. He only has 20 minutes left to do this in.
• To get a good overview of all the stuff he should talk about, he
really would like to print some slides. Oops…
• Harry gives a lousy talk 
Instead, what if…
• Harry wakes up in the morning later than he should have. He
has a 7am flight to catch.
• He starts downloading huge ppt files and his email while he gets
ready. He’s ready to leave but the download isn’t complete.
He suspends this and decides to resume it later
• He reaches the airport and has a few minutes to spare. He
resumes his long download. Despite the new network and
disconnection in-between, it continues from where it left off.
• He reaches DC and makes his meeting on time, but he still has
to work on his slides. He gets a network connection and
resumes the download task. Thankfully, his files are in a
globally distributed file system and his software finds a nearby
set of servers to continue from
• 2 minutes later, he’s ready to start on pulling today’s talk
together. He has 78 minutes left to do this in. Piece of cake!
• To get a good overview of all the stuff he should talk about, he
really would like to print some slides. His location-aware
resource discovery system finds an accessible nearby printer
and he’s all set
Nomadic System Architecture
Networked sensors/actuators
Ad hoc network integration
E21 information
Energy-efficient
protocols
“Indoor GPS”
within few cms
Generic API
Location-awareness:
Cricket
Context-aware
Nomadic applications
Secure cooperative
Finding
file system
by intent
Global file access: CFS Global resource discovery: INS
Scalable decentralized lookups: Chord Internet-scale
hashing abstraction
Seamless end-to-end sessions: Migrate
Suspend-resume capability for nomadic applications
Migrate: Towards End-to-end Mobility
(Alex Snoeren’s dissertation)
Location Query
(DNS Lookup)
Location Update
(DNS Update)
Naming Service
(Dynamic DNS)
Session Initiation
Session Migration
via continuation
Correspondent
Host
Mobile Host
foo.bar.edu
xxx.xxx.xxx.xxx
yyy.yyy.yyy.yyy
Migrate Functions
• Locate the mobile host or service
• Preserve communication across movement
– Support changes in network attachment
– Choose best network amongst available choices
• Expect and support disconnection
– Gracefully detect lack of connectivity
– Conserve resources during disconnection
– Reconnect quickly and efficiently
• Key idea: Notion of sessions to preserve application
connectivity across suspensions
– Migrating TCP connections across changes in IP is an
important optimization (solves long-standing open issue in
TCP design)
Session Continuations: A New
Abstraction for Nomadic Access
1. Initialization
– At beginning of session, exchange information for
subsequent migration (crypto token exchange)
2. Disconnection
– Identify critical state (a “session continuation”)
– Package and store
– Suspend applications
3. Resumption
– Resynchronize transport, session, and application state
– Security achieved by presenting token negotiated in #1
– Restart session
A session continuation encapsulates state
Exports migration-awareness API for application adaptation
Interfaces with connectivity monitor and policy module
CFS: Cooperative File System
Server
Server
( & client)
Server
Internet
Server
Server
• Highly available using aggressive replication
• Provides robustness under failures
– No central server; handles joins and leaves robustly
• Incremental scaling with new servers
• Harnesses server resources, cooperatively
• Provides authentic and secure file access
CFS Architecture Layers
File System ID=995 (public key)
File
System
DHash
995:
ID=901
ID=732
Signature
(root block)
144:
ID=431
732:
ID=795
…
(i-node block)
(directory blocks)
Block
732
995:
ID=901
ID=732
Signature
Block
407
901:
“a.txt” ID=144
431:
…
(data)
795:
…
Block
705
Node B
Node A
Internet
Node C
Chord: Maps keys to nodes (e.g., CFS ID’s)
247:
ID=407
ID=992
ID=705
Signature
Chord: Internet-Scale Hash Tables
N5
N10
N110
N20
N99
Circular
ID Space
N32
Stores block IDs 21..32
N80
N60
Block IDs 33..60
• Chord maps ID’s to “successor”
• Nodes and blocks have 160-bit ID’s
• Successor: Node with next highest ID
Basic lookup
N120
N10 “Where is key 80?”
N105
Successor pointer
“N90 has K80”
K80 N90
N60
N32
“Finger table” allows log(N)-time
lookups
¼
½
R = log(n) immediate
Successors for
robustness
1/8
1/16
1/32
1/64
1/128
finger[k] points to
successor (n + 2k) N80
log(n) fingers in all
Stabilization methods
for concurrency
To vu.nl
Lulea.se
OR-DSL
CMU
MIT
MA-Cable
Cisco
Cornell
CA-T1
CCI
Aros
Utah
NYU
RON/CFS Deployment
KAIST, Korea
Venezuela
MSR, UK
~20 RON nodes running CFS servers in 4 continents
Many different Autonomous Systems
Failed Lookups (Fraction)
Robustness Against Failures
1000 CFS servers
Average of 5 runs
Run before stabilization
All failures due to replica
failing
50% of nodes disappear
but only less than
1.6% of lookups fail
Failed Nodes (Fraction)
INS: Nomadic Resource Discovery
[email protected]
Intentional name
[service = printer]
[building = schafer
[room = *]]
Intentional name
[service = printer]
[building = schafer
[room = 405]]
Lookup
Resolver
self-configuration
Intentional name resolvers
form an overlay network
Uses Chord as underlying hash lookup
for scalability
Late binding: integrate resolution and message routing
Cricket: Toward Location-Awareness
Beacons on
ceiling
SPACE=NE43-510
ID=34
COORD=146 272 0
MOREINFO=
http://cricket.lcs.mit.edu/
Cricket
listener
B

Mobile device
Obtain linear distance estimates: RF + ultrasound
Pick nearest to infer “space”
Solve for mobile’s (x, y, z)
Determine  w.r.t. each beacon and deduce
orientation vector
Cricket Architecture
info = “a2”
Beacon
info = “a1”
Listener
Estimate distances
to infer location
No central beacon control or location database
Passive listeners + active beacons preserves privacy
Straightforward deployment and programmability
Determining Distance
Beacon
RF data
(space name)
Ultrasound
(pulse)
Listener
• A
The
beacon
listener
transmits
measures
an RF
the and
timean
gap
ultrasonic
between
signal
the
receipt
simultaneously
of RF and ultrasonic signals
–A
gap location
of x ms roughly
corresponds
a
RFtime
carries
data, ultrasound
is a to
narrow
distance
of x feet from beacon
pulse
– Velocity of ultrasound << velocity of RF
Cricket v1 Prototype
RF module (rcv)
Ultrasonic
sensor
Listener
RF module (xmit)
RF antenna
Beacon
Atmel
processor
RS232
i/f
Host software libraries in Java;
Linux daemon (in C) for Oxygen BackPaq handhelds
Several apps…
Synergies
Networked sensors/actuators
Ad hoc network integration
E21 information
Energy-efficient
protocols
Context-aware
Nomadic applications
“Indoor GPS”
within few cms
Location-awareness:
Cricket
Philips, Nokia, Intel,
Duke, (recently) UW
Secure cooperative
Finding
file system Oceanstore
by intent
SDS, …
Global file access: CFS Global resource discovery: INS
CAN, Pastry, Scalable decentralized lookups: Chord Internet-scale
Tapestry
hashing abstraction
Seamless end-to-end sessions: Migrate
Suspend-resume capability for nomadic applications
“Coda” for network applications
Data staging (Aura)
Summary
• Several new technologies for context-aware nomadic
applications
– Migrate, Chord, CFS, INS, Cricket, energy-efficient
protocols, sensor/device integration
• Fundamental new abstractions
– Session continuations, cooperative overlays, distributed
hash tables, intentional naming, late binding
• Public-domain prototypes and several papers
– Some technologies being used outside of Oxygen
• What next?
– Robust integration of context into application workflow
– Software system architecture for embedded + human-centric
systems
– Dealing with scale and unreliable components
– Handling challenging privacy and security issues