Transcript Resource Discovery in Self-Organizing Networks

Resource Discovery in
Self-Organizing Networks
Hari Balakrishnan
MIT Lab for Computer Science
http://inat.lcs.mit.edu/
[email protected]
Application #1: Collab Regions
Servers
Services in
our environment
Application #2: Networks of Devices
• Access and control services provided
by (wireless) networked devices
• Integrate the physical world
– Sensor computing
• Location-dependent applications
– Active maps, mobile camera network,
object tracking system, climate sensing
• Rapidly deployable & configurable
systems
Challenges
•
•
•
•
•
Configuration
Routing
Discovery
Adaptation
Security
Today
Clients
DNS
Hostname
Routers
Address
Servers
• Mostly static topology
& services
• Applications cannot
learn about network
• Deploying new services
cumbersome
• Failures are common!
• High management cost
Configuration
• Manual configuration
– Contact network administrator and get
an address (+ DNS mapping)
– This is the predominant mode today!
• Dynamic Host Configuration Protocol
(DHCP)
• Decentralized ad hoc configuration
(work-in-progress)
Packet Routing
• IP routing & forwarding
– Unicast (RIP, OSPF, BGP)
– Multicast (DVMRP, PIM, CBT, BGMP)
• Mobile IP (RFC 2002)
– Movement (as opposed to relocation)
– Continuous connections to mobile hosts
– Mobile data sources
• Ad hoc routing (IETF MANET WG)
Discovery
• Perhaps the hardest challenge in this area
• Heterogeneity
– Devices
– Services
– User interfaces
• Change
– Mobility
– Data
– Performance
• Robust architecture
• Spontaneous deployment: ZERO config!
Intentional Naming System
Apps know WHAT they want, not WHERE
• Descriptive names
– Describe intent based on attribute-value
tuples
• Self-configuring resolvers
• Integrate resolution and forwarding
– “Late binding” of names to nodes
• Soft-state dissemination protocols
– Periodic announcements and refreshes
INS Architecture
camera510.lcs.mit.edu
Intentional name
[building = ne-43
[room = 510]]
[entity = camera]
Lookup
image
INR
INR
INR
Intentional Name Resolvers
form a distributed overlay
Integrate resolution and message forwarding
How Does It Work
Scaling? Virtual space partitions
Domain Space Resolvers
INR
Inter-domain
information via
DSR protocol
DSR
Exchange names
as if they were routes
Application-level
overlay network
formed based on
performance
Name-Specifiers
• Problem: Expressive name language (like XML)
• Names are descriptive
– Providers announce names
• Names are query expressions
– Attribute-value matches
– Range queries
– Wildcard matches
[vspace = café]
[state = ca
[city = berkeley]
[region = northside]]]
[distance < 0.25 miles]
data
[vspace = camera]
[building = ne-43
[room = 504]]
[resolution=800x600]]
[access = public]
[status = ready]
[vspace = thermometer]
[building = ne-43
[room = *]]
[temperature < 620F]
data
Administratively scoped names (e.g., lcs.mit.edu)
Self-Configuring Resolvers
• Problem: Manual configuration
• Solution: self-configuration protocol
• Bootstrap
– DNS maintains list of per-domain INRs
• Neighbor formation
– Based on metrics like round-trip latency
• Load balancing
– Spawn/kill resolvers on INR nodes
Late Binding
• Problem: Track rapid changes
• Solution: Integrate resolution and
forwarding message
• Periodic advertisements from
provider nodes refresh state in INR
• INRs forward message to
destinations
• Handles mobile, grouped, and
replicated services (& people)
Soft-state Dissemination
• Problem: Robustness and availability
• Solution: Treat names as soft-state;
use “routing” protocols to exchange
• Application-level routing & forwarding
between INR overlay nodes
• To scale well, use bandwidth
management heuristics
– Namespaces become huge quickly
– Treat “hot” and “cold” names differently
Efficient Name Lookups
• Data structure
• Lookup
– AND operations among orthogonal attributes
– For values pick the value(s) satisfying the
lookup
• Polynomial-time in worst case
Applications
• Wireless Networks of Devices (WIND)
– Location-dependent & mobile applications
over RF and IR
– Floorplan: A navigation tool
– Camera: An image/video service
– Printer: A smart print spooler
– TV & jukebox
• Server replication
• Caching service
WIND Demo
• Problem: Firewalls
– E.g., UDP for names, advertisements, video
• Solution: split protocol across firewall
– Completely unchanged applications!
– Transparently replace DatagramSocketImpl
in java.net
TCP
udp_recv()
IBM Firewall
Intranet
Internet
UDP
UDP
MIT
Status & Performance
• Java implementation of system
– Ported to Palm III too!
• PC-based resolver performance
– 1 resolver --> 75,000 names at > 100 lookups/s (untuned)
– Discovery time linear in hops
• Algorithms for robust self-configuration
• Scalability
– Wide-area architecture design in progress
– Problem: Decouple service & network hierarchy
• Deployment
– Hook in wide-area architecture to DNS
– Standardize “virtual spaces” (like MIME data types)
Related Work
• Domain Name System
– Differences in expressiveness and architecture
• Service Location Protocol
– More centralized, less spontaneous
• Jini:
– INS can be used for self-organization
• Universal Plug-and-Play
– XML-based descriptions; INS fits well
• IBM T-spaces
• Intentional names in other contexts
– Semantic file systems, adaptive web caching,
DistributedDirector
INS Summary
• Expressive naming language
• Self-configuring resolvers form an
application-level overlay
• Integrate resolution and routing
• Soft-state dissemination protocols
• Runs on impoverished devices too
• Wide-area architecture in progress
Enables self-organizing networks & applications
Application-Level Networks
Increasing number of services that set
up application-level overlay networks
• Distributed Web caches
• Replica management systems
• Transcoders
• Multi-party communication
• Naming systems
• Resource discovery
What Do They Have in
Common?
• Form an overlay over IP
• Nodes exchange meta-data
information
• Nodes forward messages based on
meta-data
• Incorporate configuration machinery
• Fault/crash recovery
• Load balancing
What’s the “Right” Network
Support?
• Put a lot (and more) in the routers
–
–
–
–
–
IP Multicast
Reliable multicast primitives
Name redirection (“resolution”)
Web caches
Programmable active routers...
• Or, provide more support at the
application-level
Supporting Application-Level
Networks
• General protocols for meta-data
dissemination
– Using all the good stuff we’ve learned about
soft-state protocols
• Fault-tolerance primitives
• Self-configuring overlays: key component
– Bootstrap and placement
– Neighbor formation
– Load balancing
• Security and privacy primitives
– E.g., self-certifying names
Future Internet Architecture
Use each other
to add value
Cache & replica
management
Middleware
Self-configuring
overlays
Media
transcoders
...
Performance
INS
discovery Service
Decentralized
location
security
Jini
UPnP
E-speak
T-spaces
Resource
Traffic
Congestion
management
engineering
Manager
Scheduling, Flexible IP
buffer mgmt
routers
Conclusions
• Achieving self-organization isn’t easy!
–
–
–
–
–
Configuration
Message routing
Discovery: INS has many desirable features!
Adaptation
Security & privacy
• Application-level networking is key to
achieving self-organization and flexibility
– But it is being done in rather ad hoc ways
– It behooves us to ensure that the future
application-level network architecture is at least
as sound as the underlying IP substrate