Transcript app_service_discovery

Naming and Service Discovery
in Mobile Computing
4/10/2009
Richard Yang
1
Outline
 Admin. and recap
 Naming and service discovery
 Introduction to mobile application
development
2
Summary of Progress So Far
 We can communicate given the location or
(unique) IP address of the destination
physical layer handles wireless/mobile channels
 link layer handles access control
 routing determines the path(s)
 transport implements rate control and e2e
reliability

 We can determine the location (at some
granularity) of nodes
3
Roadmap
 We need easier-to-use communication
primitives [this class]
 We need to build on the primitives to build
useful mobile/wireless applications
 Mobile
software development environment
[4/14/2009]
• J2ME/.Net Compact/Andriod/TinyOS
User interface design [4/16/2009]
 CPU scheduling and file system [4/21/2009]
 Mobile application adaptation [4/23/2009]

4
Naming and Service Discovery
 Function:

map user-level descriptors to communications
peers
 Example user-level descriptors:
 globally unique name/service:
• http://www.cnn.com, [email protected]
local name: my_iphone
 query string indicating service attributes: printer
on the 5th floor, nearest color printer

5
Today
clients
DNS
<hostname, service>
routers
IP address
servers
6
DNS: Domain Name System
 Function
 map domain name (e.g. cs.yale.edu) and service type (e.g.,
email) to IP address (e.g. 128.36.232.5)
 Domain name: a hierarchical name space implemented
by a distributed database
called a zone
7
DNS
 Hierarchical global name space to allow distributed,
autonomous administration
 Each DNS server stores resource records (RR)
RR format: (name,
 Type=A
 name is hostname
 value is IP address
 Type=NS
 name is domain (e.g.
yale.edu)
 value is the name of the
authoritative name
server for this domain
value, type, ttl)
 Type=CNAME
 name is an alias name
for some “canonical”
(the real) name
 value is canonical name
 Type=MX
 value is hostname of mail
server associated with name
8
Basic DNS Flow
 A host queries local DNS server, who may
forward the query to the corresponding DNS
server
 Host caches the lookup result
9
DNS: Problems
 Hierarchical global name space based on
administration

not flexible for individual users to manage names
 Hosts cache lookup results
 caching is also called early binding to IP address; the bind
may break during a session
 Support fixed types of services, e.g., A, NS,
CNAME, MX

static and fixed record structure makes it difficult to
introduce new services or non-trivial service queries
10
Background: Linda
 “Distributed workspace” by David Gelernter
in the 80’s at Yale
 Nodes write arbitrary tuples
(heterogeneous-type vectors) to shared
memory
 Nodes read matching tuples from shared
memory
 exact
matching is required for extraction
11
Linda: Core API
 out():
 writes tuples to shared space
 example: out("abc", 1.5, 12).
 result: insert (“abc”, 1.5, 12) into space
 read():
 retrieves tuple copy matching arg list (blocking)
 example: read(“abc”, ? A, ? B)
 result: finds (“abc”, 1.5, 12) and sets local variables
A = 1.5, B = 12. Tuple (“abc”, 1.5, 12) is still resident in space.
 in():
 retrieves and deletes matching tuple from space (blocking)
 example: same as above except (“abc”, 1.5, 12) is deleted
12
Linda Extension: JavaSpaces
 Sun took Linda principles and made
modifications
add transactions, leases, events
 store Java objects instead of tuples
 a very comprehensive service discovery
system

 Definitive book, “JavaSpaces Principles,
Patterns, and Practice”

2 of 3 authors got Ph.D.’s under Gelernter on
Linda-related subjects
13
JavaSpaces – Visual Overview
14
Intentional Naming System (INS)
 Based on Linda

names are intentional, based on generic attributes
and values
 Resolves names by lookup-and-forward, no
caching

late binding of names to nodes
15
zoo_lwa.cs.yale.edu
INS Intentional Naming
intentional name
[loc=loc_of_zoo]
[entity = printer]
Lookup
INR
network
Intentional Name Resolvers (INR)
resolve queries
16
Implementing tuple space using an
application-level overlay network
(DHT)
17
DHT: Overview
 Abstraction: a distributed “hash-table” (DHT)
data structure



put(key, value) and get(key)  value
DHT imposes no structure/meaning on keys
one can build complex data structures using DHT
 Implementation:

nodes in system form an interconnection network: ring,
zone, tree, hypercube, butterfly network, ...
Distributed application
get (key)
put(key, data)
DHT
node
node
….
node
18
Basic Structure of DHT
put(key, value)
put(key, value)
get(key)
19
DHT: Basic Idea
DHT: Basic Idea (2)
DHT: Basic Idea (3)
DHT: Basic Idea (4)
DHT: Basic Idea (5)
Discussion: Key issues?
Chord
 m bit identifier space for both keys and
nodes

key identifier = SHA-1(key), where SHA-1() is a
popular hash function,
Key=“Color printer”  ID=60
 node identifier = SHA-1(IP
• IP=“198.10.10.1”  ID=123
address)
Chord: Storage using a Ring
K125, K5, K10
IP=“198.10.10.1”
N10
K11, K20
N123
Circular
7-bit ID Space
K101
N32
N55
N90
K60
Key=“Color printer”
 A key is stored at node with next higher ID
How to Search: One Extreme
 Every node knows of every other node
 that is, “N10” knows “N90” is “198.20.20.1”
 requires global information
 Routing tables are large O(N)
 Lookups are fast O(1)
Where is “Color printer”?
Hash(“Color printer”) = K60
27
How to Search: the Other Extreme
 Every node knows its successor in the ring
Where is “Color printer”?
Hash(“Color printer”) = K60
 Requires O(N) lookups
28
Small-World
 First discovered by Milgrom
 in 1967, Milgram mailed 160 letters to a set of randomly
chosen people in Omaha, Nebraska
 goal: pass the letters to a given person in Boston
• each person can only pass the letter to an intermediary known
on a first-name basis
• pick the person who may make the best progress



result: 42 letters made it through !
median intermediaries was 5.5---thus six degree of
separation
a potential explanation: highly connected people with nonlocal links in mostly locally connected communities improve
search performance !
29
Kleinberg’s Result on Distributed Search
 Question: how many long distance links to maintain
so that distributed (greedy) search is effective?
 Kleinberg’s Law: Distributed algorithm exists only
when probability is proportional to (lattice steps)-d,
where d is the dimension of the space
30
Distributed Search
 In other words, if double distance, increase number of
neighbors by a constant
probability is proportional to (lattice steps)-d
31
Saul Steinberg; View of World from 9th Ave
32
Chord Solution: “finger tables”
 Node K knows the node that is maintaining K
+ 2i, where K is mapped id of current node

increase distance exponentially
K+32
K+64
K+16
K+8
K+4
K+2
K+1
N80
33
Joining the Ring
 transfer keys from successor node to new node
 updating fingers of existing nodes
DHT: Chord Join
 Assume an identifier space [0..8]
 Node n1 joins
Succ. Table
i id+2i succ
0 2
1
1 3
1
2 5
1
0
1
7
6
2
5
3
4
DHT: Chord Join
 Node n2 joins
Succ. Table
i id+2i succ
0 2
2
1 3
1
2 5
1
0
1
7
6
2
Succ. Table
5
3
4
i id+2i succ
0 3
1
1 4
1
2 6
1
DHT: Chord Join
Succ. Table
i id+2i succ
0 1
1
1 2
2
2 4
0
 Nodes n0, n6 join
Succ. Table
i id+2i succ
0 2
2
1 3
6
2 5
6
0
1
7
Succ. Table
i id+2i succ
0 7
0
1 0
0
2 2
2
6
2
Succ. Table
5
3
4
i id+2i succ
0 3
6
1 4
6
2 6
6
DHT: Chord Join
Succ. Table
 Nodes:
i
i id+2
0 1
1 2
2 4
n1, n2, n0, n6
 Items:
f7, f1
Items
7
succ
1
2
0
0
1
7
Succ. Table
i id+2i succ
0 7
0
1 0
0
2 2
2
Succ. Table
6
i
i id+2
0 2
1 3
2 5
Items
succ 1
2
6
6
2
Succ. Table
5
3
4
i id+2i succ
0 3
6
1 4
6
2 6
6
DHT: Chord Routing
Succ. Table
i
 Upon receiving a query for
item id, a node:
 checks whether stores the
item locally
 if not, forwards the query to
the largest node in its
successor table that does not
exceed id
i id+2
0 1
1 2
2 4
Items
succ
7
1
2
0
0
Succ. Table
1
7
i
i id+2
0 2
1 3
2 5
query(7)
Succ. Table
i id+2i succ
0 7
0
1 0
0
2 2
2
6
Items
succ 1
2
6
6
2
Succ. Table
5
3
4
i id+2i succ
0 3
6
1 4
6
2 6
6
There are other DHT algorithms
 CAN
 Tapestry (Zhao et al)
– Keys interpreted as a sequence of digits
– Incremental suffix routing
» Source to target route is accomplished by correcting one
digit at a time
» For instance: (to route from 0312  1643)
» 0312  2173  3243  2643  1643
– Each node has a routing table
 Skip Graphs (Aspnes and Shah)
40
Back to INS
Overlay
Manager
Java implementation of INS & applications
1 resolver: several thousand names @100-1000 lookups/s
Route
Manager
Network
Monitor
neighbors
Forwarder
Client
Manager
NameTreeSet
lookup
Intentional anycast,
multicast
Communicator
Mobility
Sockets
Incoming message
TCP/UDP
41
Applications
 Wireless Networks of Devices (WIND)
 location-dependent mobile applications
 floorplan: a navigation tool
 camera: an image/video service
 printer: a smart print spooler
 TV & jukebox
 network-independent “instant messaging”
 location-support system for services and clients
to learn location
42
43
44
45
46
47
48
Summary of INS Features
 A generic tuple space for flexible naming
 An application overlay to implement the tuple space
 each application-level resolver “owns” some portion of the
key-space
• in Chord, it is the key-id-space between two nodes in 1-D ring
• provides some load balancing
• probabilistically equal division of keys to nodes

we covered only exact match; one can extend to more
flexible query, e.g., range query
 Discussions: problems of INS
49
Mobile Application Development
50
Discussion
 What are major considerations in designing a
programming environment for mobile
devices?
51
Backup Slides
52
Windows .NET Compact Framework
 Scales down a popular programming environment to ease learning





the .NET CF is a subset of the full .NET framework with some additions
designed for resource constrained devices
1,400 classes for .NET CF vs. 8,000 for full
27 UI controls for .NET CF vs. 52 for full
1.5 MB for .NET CF vs. 30 MB for full
 Uses versioning to avoid using lowest common denominator



pocket PC
pocket PC phone version
smart phone version
 Uses virtual machines to mask device heterogeneity

programming languages compile to MSIL
• MSIL is JIT compiled on the device
• MSIL code is smaller than native executables
• MSIL allows your code to be processor independent
53
Windows .NET Compact Framework
 Scales down a popular programming environment to ease learning





the .NET CF is a subset of the full .NET framework with some additions
designed for resource constrained devices
1,400 classes for .NET CF vs. 8,000 for full
27 UI controls for .NET CF vs. 52 for full
1.5 MB for .NET CF vs. 30 MB for full
 Uses versioning to avoid using lowest common denominator



pocket PC
pocket PC phone version
smart phone version
 Uses virtual machines to mask device heterogeneity

programming languages compile to MSIL
• MSIL is JIT compiled on the device
• MSIL code is smaller than native executables
• MSIL allows your code to be processor independent
54
Backup Slides:
CAN
55
CAN Solution: Detail
 Entire key space is partitioned amongst all of
the nodes

virtual Cartesian coordinate space
 Every node “owns” a zone in the overall space
 Abstraction
 insert(key, value): store data (<key, value>) at
“points” (key) in the space
 retrieve(key): route from the initial “point” to the
node that owns the enclosing zone of the target
point
56
CAN Example: Two Dimensional Space
 Space divided
among nodes
 Each node
covers either
a square or a
rectangular
area of ratios
1:2 or 2:1
1
57
CAN Example: Two Dimensional Space
 Space
divided
among
nodes
 Each node
covers
either a
square or a
rectangular
area of
ratios 1:2 or
2:1
1
2
58
CAN Example: Two Dimensional Space
 Space
divided
among
nodes
 Each node
covers
either a
square or a
rectangular
area of
ratios 1:2 or
2:1
3
1
2
59
CAN Example: Two Dimensional Space
 Space
divided
among
nodes
 Each node
covers
either a
square or a
rectangular
area of
ratios 1:2 or
2:1
3
1
2
4
60
CAN Example: Two Dimensional Space
 Space
divided
among
nodes
 Each node
covers
either a
square or a
rectangular
area of
ratios 1:2 or
2:1
61
CAN Insert: Example (1)
node I::insert(K,V)
I
62
CAN Insert: Example (2)
node I::insert(K,V)
(1) a = hx(K)
b = hy(K)
I
y=b
Example: Key=“Matrix3” h(Key)=60
x=a
63
CAN Insert: Example (3)
node I::insert(K,V)
(1) a = hx(K)
b = hy(K)
I
y=b
(2) route(K,V) -> (a,b)
x=a
64
CAN Insert: Example (4)
node I::insert(K,V)
(1) a = hx(K)
b = hy(K)
I
y=b
(2) route(K,V) -> (a,b)
(3) (K,V) is stored at
(a,b)
x=a
65
CAN Retrieve: Example
node J::retrieve(K)
(1) a = hx(K)
b = hy(K)
y=b
(2) route “retrieve(K)” to
(a,b)
J
x=a
66
CAN Feature: Summary
 Data stored in CAN is addressed by name
(i.e. key), not location (i.e. IP address)
67
CAN Insert: Routing
 A node maintains
state only for its
immediate
neighboring nodes
 Forward to
neighbor which is
closest to the
target point

a type of greedy,
local routing
scheme
68
CAN Insert: Join (1)
J
2) pick a
random
point (p,q)
in space
new node
1) Discover some node “J” already in CAN
69
CAN Insert: Join (2)
N
J
new node
3) J routes to (p,q), discovers node N
70
CAN Insert: Join (3)
Inserting a
new node
affects only
a single
other node
and its
immediate
neighbors
N
new node
J
4) split N’s zone in half… new node owns one half
71
Backup Slides:
JavaSpace and Jini
72
JavaSpaces – Visual Overview (cont.)
73
JavaSpaces Compute Server
74
JavaSpaces API
 Object Example:
import net.jini.core.entry.Entry;
public class Message implements Entry {
public String content;
public Message() {
}
}
 Requirements




Implement Net.jini.core.entry.Entry (marker interface)
No-argument constructor (for deserialization)
No primitive types (Integer class instead of int)
Important fields should be public
75
JavaSpaces API (cont.)
 notify(Entry tmpl, Transaction txn, RemoteEventListener listener, long lease,
MarshalledObject handback)


Entry read(Entry tmpl, Transaction txn, long timeout)


Take a matching entry from the space, waiting until one exists.
Entry takeIfExists(Entry tmpl, Transaction txn, long timeout)


Return a snapshot of the given entry.
Entry take(Entry tmpl, Transaction txn, long timeout)


Read any matching entry from the space, returning null if there is currently is none.
Entry snapshot(Entry e)


Read any matching entry from the space, blocking until one exists.
Entry readIfExists(Entry tmpl, Transaction txn, long timeout)


When entries are written that match this template notify the given listener with a
RemoteEvent that includes the handback object.
Take a matching entry from the space, returning null if there is currently is none.
Lease write(Entry entry, Transaction txn, long lease)

Write a new entry into the space.
76
JavaSpaces API (cont.)
 Notify


JavaSpace sends an event when an object matching your template is
written
If used with NotifyDelegator class, the object that triggered the event
may be obtained
 Transactions




Way to lump operations together into a single atomic unit
Basic guarantees of atomicity (all or none commit)
Can deadlock
Two-phase commit model
 Snapshot



Returns a particular JavaSpace’s serialization of an object
Useful for multiple reads, takes
No guarantees if a snapshot from Space1 is used with Space2
77
JavaSpaces API (cont.)
 More on Transactions
 Properties:
•
•
•
•

Atomicity: All or none
Consistency: Completion leaves system in consistent state
Isolation: Concurrent transactions don’t affect each other
Durability: Results as persistent as entity to which they are applied
Effects on operations:
•
•
•
•
Write: Entries are not visible outside transaction until it commits
Read: All entries in & outside of transaction are searched
Take: Same as read
Notify: Applies to all writes as well as those within the current
Transaction
78
JavaSpaces Details
 Internals



Written objects are serialized into JavaSpaces server
Field matching is exact, based on identical serializations in Java Server
Null value is wildcard
• To match an initialization, use a Boolean isInitialized
 Guarantees

None (ha ha)
• Not quite


No persistence guarantee (server crash)
No ordering guarantee
• Thread 1 inserts Object O on Tuesday, Thread 2 can’t find it on Wednesday
• 5 Threads are waiting for an Object O, when it appears they are woken randomly
• 12 copies of Object O are written to server, all O reads return the sixth

Atomicity under Transaction model
79
JavaSpaces Example
public class HelloWorld extends SpaceApplet {
private JavaSpace space;
public void init() {
super.init();
space = (JavaSpace)space();
try {
Message msg = new Message();
msg.content = "Hello World";
space.write(msg, null, Lease.FOREVER);
Message template = new Message();
Message result =(Message)space.take(template, null, Long.MAX_VALUE);
System.out.println(result.content);
} catch (Exception e) {
e.printStackTrace();}}}
80
JavaSpaces Discussion
 Linda concepts in a distributed environment


Vs. MPI?
Vs. Shared memory?
 JavaSpaces (as an implementation of Linda ideas)



Limitations?
Potential?
Where the heck is it? Implemented ’98-’99
 Applicability to Sensor Networks?



New requirements for OS, applications?
Good paradigm for devices that should sleep as often as possible?
Would a java VM be easy to implement in TinyOS?
81
Outline
 Admin. and recap
 Service
 Java space
 Jini
82
Jini - Introduction
 Jini technology allows devices to dynamically
establish communication to share and exchange
services across a network.
 Provides simple mechanisms which enable devices to
plug together to form an impromptu community
(federation)

Lesson in Political Science: In a federation, most power lies
in local authorities. Federal authorities ensure that local
authorities work together.
 Each device provides services that other devices in
the community may use.
 These devices provide their own interfaces which
ensure reliability & compatibility.
83
Jini - Introduction
 Jini is an extension of Java
 Java consists of one virtual machine
 Jini is a kind of virtual network
 Jini Devices must have processing power or memory.
 Otherwise controlled by another device.
 Relies on existence of a network of “reasonable”
speed connecting these devices.
84
Key Concepts
 Services




An Entity used by person, program, or another service. May
be a computation, storage, a communication channel, etc.
You know…a service!
Jini system consists of services that can be collected to
perform a particular task.
Services can be dynamically added or withdrawn from the
system as needed.
Services Communicate using a service protocol which is a
set of interfaces written in Java.
85
Key Concepts
 Lookup Service
 Major point of contact between users of the system and
the system.
 Finds and adds services to the Jini Federation
 Maps functionality to a set of objects in Jini that actually
implement the service
• Can include other lookup services (hierarchy)
• Can for bridges to other lookup services.
 Services added using two protocols
• Discovery – locates appropriate lookup service
• Join – join lookup service.
86
Key Concepts
 Java RMI

Provides communication between services
• Extension to normal remote procedure call.
• Passes not only data, but entire objects and code.

Provides Simplicity
• Code can be encapsulated in an object and can be passed
from service to service.
87
Key Concepts
 Leasing
Access to many services are lease based.
 Guarantees access to a service for a negotiated
period of time.
 Services can be exclusive or non-exclusive.

 Transactions
 A series of operations to be performed.
 Within a single service or spanning multiple
services.
88
Key Concepts
 Security
Built on the twin notions of a principal and an
access control list.
 Jini services are accessed on behalf of some
entity (principal) which traces back to a user of
the system.
 Check object’s access control list to determine
permissions to use a particular service.

89
Key Concepts
 Events
Ability to notify objects when a particular event
occurs.
 Could trigger new task/transaction

90
Components
 Three main components
 Infrastructure
 Programming Model
 Services

Tend to get blurred, but
just an extension of the
virtual machine concept.
91
Components
 Infrastructure
 Discovery & Join Protocol
• Define way services become part of Jini System
 Java RMI
• Base language with which services communicate
 Security Model
• Define how entities are identified and how they get
rights to perform actions.
 Lookup Service
• Marketplace for finding and offering services.
• Entries in Lookup Service are objects written in Java.
Objects can be downloaded and act as local proxies.
92
Components
 Programming Model
Sets of interfaces designed to extend the usual
single virtual machine model.
 Leasing Interfaces

• Adds time-based interface to resources.

Event and Notification Interfaces
• Enable event-based communication between services
93
Components
 Programming Model (Cont)

Transaction Interfaces
• Coordinates the actions of a group of distributed
objects in a two phase system
• Voting Phase
– An object votes on whether it has completed it portion of a
task and is ready to commit.
• Commit Phase
– Coordinator issues a commit request to each object.
94
Components
 Services

Consist of objects coded in Java
• Can be made up of other objects

Has an interface that defines what a service is
capable of doing
95
A Closer Look at JINI
 Similar Technologies
 Limitations of JINI
 Case Studies
 Current Status
96
Similar Technologies
 UPnP, Salutation, NINJA
 Common Object Request Broker Architecture
 CORBA is a specification for a Distributed Object System
 RMI vs CORBA
•
performance and portability tradeoffs
 Distributed Objects vs Distributed Services
 Can be used in complementary fashion?
97
Using CORBA with JINI
98
Limitations: Service Lookups
 Lookup Servers vs Name Servers
Query
by service or name
 Exact Matching
/ ServiceRegistrar provide
limited expressiveness (i.e. for range queries)
 ServiceTemplate
 Fault-tolerance
No defined policies for system recovery
99
Limitations: Low-Resource Hosts
 Servers: Sun’s reference implementation of
Lookup Service consumes 3 MB storage
 Clients: Limitedness of lookup interface can
require a lot of unnecessary overhead
 Is this really a problem (given the success
stories)?
10
Case Studies: Who uses it?













Quantum
Seagate
3COM
Cisco
Xerox
Novell
Nokia
Philips
Sony
Motorola
Kodak
Sharp
Canon
 Siemens
 Toshiba
 Samsung
 Kinko’s
 Hewlett Packard
 AOL
 Adaptive Networks
 Ericsson
10
Case Studies: Success Stories










4D Networks:
Application Services for the Web Built on Jini Network Technology.
Appropria:
Jini Technology Brings Mission-critical Information Out of the Silo.
Entegrity Solutions:
Major Online E-commerce and Enterprise Solutions Company Rely on Jini Network Technology for Secure
E-Commerce.
Eko:
Jini Technology connects medical data and equipment dynamically and reliably.
FETISH Federation:
Jini Network Technology Links Online Travel Services.
Lightflow:
Jini Network Technology Adds "High Touch" to Online Shopping.
Maui High Performance Computing Center:
Sun Architects Jini Network Technology Infrastructure for Military Simulations.
Procoma:
An Innovative Solution for Commerzbank AG with Jini Technology.
Raytheon:
Open, Adaptive, Self-Healing Architecture for DD21.
U.S. Army:
Reliable Battlefield Communication Using Jini Connection Technology.
10
Case Studies: Success Stories
(cont.)
 “We believe that the Jini and Java technologies will dramatically change
the way DD 21 and future Navy systems are developed. The spontaneous
community capabilities of Jini will lead to much more reliable, capable and
maintainable systems. The development and integration cycle will be
reduced significantly, and the use of commercial components will finally be
cost-effective.”
-- Lead Systems Engineer for DD21, Raytheon
 "The cost of manually implementing what Jini network technology is
providing us would have been prohibitive both from an actual cost
perspective (person-hours to build) and time perspective (time to market),"
said Horvath. "Jini technology's increasingly mature and well-documented
capabilities would be very difficult to reproduce. The use of Jini technology
allows our team to stay focused on the problem space of AssureDelivery,
and not on implementation details of the underlying distributed service."
-- Director of Product Development, Entegrity Corp.
10
Current Status
 Increased Deployment:
“Jini Technology Licensees, Including Heartlab Inc, Templar
Corp, Valaran Corp, FETISH Federation, and Cysive Inc., Turn to
Jini Technology to Address Dynamic Networking Challenges”
(May 7, 2003)
 Standardization:
“Jini Community Approves the ServiceUI API” (May 7, 2003)
10
Current Status (cont.)
 Open Issues:
Network
Scalability: In theory, a JINI systerm
can scale if it uses a hierarchy of lookup servers
(like DNS), but no actual ‘wide area’ JINI network
has been deployed. But is this even relevant?
Generality: Can well-defined interfaces be
established for all types of services besides
simple examples like printers and cameras?
10