Transcript The Design and Implementation of an intentional naming system

The Design and Implementation of an
intentional naming system
William Adjie-Winoto, Elliot Schwartz, Hari
Balakrishnan, Jeremy Lilley
MIT Lab of Computer Science
Presenter: Vincent Matossian - February 2002
the context and the goal


Dynamic and mobile network
Idea is:


Need for naming service that is




2/25
Describe What to look for, not Where to find it
Expressive
Responsive
Robust
Easily configurable
INS- February 2002
Vincent Matossian CS545
naming language

Simple and lightweight


Hierarchy of Attributes and Values allows



3/25
Small set of operators
nodes providing a service to describe what they provide
Consumers to describe what they require
INS resolution architecture designed independently
of the query language
INS- February 2002
Vincent Matossian CS545
overview




4/25
Decentralized network of resolvers (to discover
names and route messages) self-configured into
an application-level overlay network
Use of intentional names for routing
soft-state periodic advertisements from services
Not yet meant for WAN internet
INS- February 2002
Vincent Matossian CS545
system architecture



5/25
Every request goes to an INR (resolver)
INRs self-configure into a spanning-tree overlay network using INR-to-INR
round trip time measurements
INRs route clients to services
INS- February 2002
Vincent Matossian CS545
name specifiers
• Hierarchical arrangement of attribute value pairs
•Providers announce descriptive names
• Clients make queries
–Attribute-value matches
–Wildcard matches
–Ranges
6/25
INS- February 2002
Vincent Matossian CS545
discovering names

Updates contain:







7/25
IP address + [port number, transport-type]
Application-advertised metric for late binding
Next-hop INR and INR-to-INR round trip time
AnnouncerID for differentiation between similar names
Advertisement on specific port
Name information is treated as soft-state  no need for
registration, deregistration
Information dissemination done using a routing protocol
that includes periodic updates and triggered updates.
INS- February 2002
Vincent Matossian CS545
name lookup


•
•
Lookup returns a name-record which includes
IP address of destination advertising name +
set of “routes” to next-hop INRs
Name trees store correspondence between
name-specifiers and name-records
Lookup
– Tree-matching algorithm
– AND operations among orthogonal
attributes
Polynomial-time in number of attributes
– O(nd) where n is number of attributes and
d is the ½ depth of tree
8/25
INS- February 2002
Vincent Matossian CS545
resolver network



9/25
INRs self-configure to form a spanning tree overlaynetwork over UDP tunnels
INR-pings send a small name between INRs and
measure the time it takes to process this message
and get a response
Domain Space Resolver (DSR) keeps track of all
INRs in the system
INS- February 2002
Vincent Matossian CS545
late binding



Mapping from name to location can change rapidly
Overlay routing protocol uses triggered updates
Resolver performs lookup-and-forward


Two styles of message delivery


11/25
lookup(name) is a route; forward along route
Anycast
Multicast
INS- February 2002
Vincent Matossian CS545
intentional anycast


lookup(name) yields all matches
Resolver selects location based on advertised
service-controlled metric



Tunnels message to selected node
Application-level vs. IP-level anycast

12/25
E.g., server load
Service-advertised metric is meaningful to the
application
INS- February 2002
Vincent Matossian CS545
intentional multicast



Use intentional name as group handle
Each resolver maintains list of neighbors for a name
Data forwarded along a spanning tree of the overlay
network


13/25
Shared tree, rather than per-source trees
Enables more than just receiver-initiated group
communication
INS- February 2002
Vincent Matossian CS545
robustness


Decentralized name resolution and routing in “serverless”
fashion
Names are weakly consistent, like network-layer routes


Routing state is soft



14/25
Routing protocol with periodic & triggered updates to exchange
names
Expires if not updated
Robust against service/client failure
No need for explicit de-registration
INS- February 2002
Vincent Matossian CS545
load Balancing and Scaling

Name processing dominates lookup processing
1 Mb/s link
•Virtual space: application-specified set of names that share some
attributes in common
15/25
INS- February 2002
Vincent Matossian CS545
routing Protocol Scalability
Name-tree at resolver
vspace=camera
Routing updates
for all names


16/25
vspace=5th-floor
Delegate this to
another INR
vspace = Set of names with common attributes
Virtual-space partitioning: each resolver now
handles subset of all vspaces
INS- February 2002
Vincent Matossian CS545
message header format
B: Binding bit flag {early, late}
D: Delivery bit flag {anycast, multicast}
Hop limit sets a time to live for each message
Cache lifetime : 0 disallows cache
18/25
INS- February 2002
Vincent Matossian CS545
applications

Location-dependent mobile applications






19/25
Floorplan: An map-based navigation tool
Camera: A mobile image/video service
Load-balancing printer
TV & jukebox service
Sensor computing
Network-independent “instant messaging”
INS- February 2002
Vincent Matossian CS545
experimental results
For ra=3; rv=3, na=2 and d=3; strings were one 16 bit character
20/25
Max = 900 lookups/sec
Size of Name-tree varies
Min = 700 lookups/sec
From 0.5 MB to 3 MB!
INS- February 2002
Vincent Matossian CS545
results
100 packets: 82B Header+586B payload
15-second periodic updates
Time to discover a new network name
is linear in the number of INR hops
Order of 10’s ms
21/25
Local: [310ms,1.9s]
Remote, same vspace: ~ 1s
Remote, different vspace: 381 ms
INS- February 2002
Vincent Matossian CS545
status

Java implementation of INS & applications



Scalability


Wide-area implementation in progress
Deployment


22/25
Several thousand names on single Pentium PC; discovery
time linear in hops
Integration with Jini, XML/RDF descriptions in progress
Hook in wide-area architecture to DNS
Standardize virtual space names (like MIME for
devices/services)
INS- February 2002
Vincent Matossian CS545
naming and service discovery





23/25
Wide-area naming
 DNS, Global Name Service, Grapevine
Attribute-based systems
 X.500, Information Bus, Discover query routing
Service location
 IETF SLP, Berkeley service discovery service
Device discovery
 Jini, Universal plug-and-play
Intentional Naming System (INS)
 Mobility & dynamism via late binding
 Decentralized, serverless operation
 Easy configuration
INS- February 2002
Vincent Matossian CS545
conclusions 1/2

24/25
Presented an intentional naming scheme where applications
describe what they are looking not where to find data.
 Expressiveness: Achieved through a simple naming language
based on av-pairs
 Responsiveness: by integrating name resolution and message
routing coping with mobility and performance changes
 Robustness: periodic service advertisements and soft-state
name dissemination protocols between replicated resolvers
 Ease of configuration: by deploying self-configuring name
resolvers
INS- February 2002
Vincent Matossian CS545
conclusions 2/2

Three resolution types:


Early binding: like DNS
Late Binding:



Java implementation performs:




25/25
Intentional anycast: returns optimal node providing service
Intentional multicast: distributes to all names satisfying a query
[100s,1000s] lookups/sec depending on name complexity
Dissemination of new names in tens of milliseconds
Name space partitioning improves the scalability of INS
No WAN deployment; No security; Improve name matching
operations and soft-state dissemination protocol to take into account
importance of certain names
INS- February 2002
Vincent Matossian CS545