Transcript Service Discovery in Ubiquitous and Pervasive Environments

Service Discovery in Ubiquitous
and Pervasive Environments
Presented by Knarig Arabshian
PhD candidacy exam
October 26, 2004
Overview

Introduction
History of service discovery, challenges

Components
Description, distribution, query

Existing systems
Mainstream, ad-hoc, location aware,
semantic, Internet-scale
http://www.cs.columbia.edu/~knarig/candidacy/candidacyList.html
What is service discovery?
Query
Distribution
Provider
Directory
Service description
Service vs resource discovery
Consumer
History
of resource discovery
System
Resource
Example
Remarks
RLP
(1983)
IP Address
of some
host
Finding an internet
gateway
Request is directed to IP or
broadcast to subnet.
Whois
(1985)
Users
Domain names
Centralized, Localized information
X.500
(1988)
General
User directory
Distributed storage, Complexity
(maintaining, populating and
querying databases)
Archie
(1992)
Files
User information
Automated (FTP) directory updates,
regular expression query
WWW
(1992)
Document
Web pages
Distributed, URL
[6] A comparison of internet resource discovery approaches, 1992
[7] Resource location protocol, 1983
Motivation
for new service discovery protocols
Static resource information (whois, RLP, X.500)
Automatic discovery of LAN network services (SLP, Jini, UPnP)

Automatic


Automatically announce or register service
instead of manually entering information.
LAN services

Printer, FAX machine, …
[8] Protocols for service discovery in dynamic and mobile networks, IJCR (Journal), 2002
Motivation
for new service discovery protocols
Static resource information (whois, RLP, X.500)
Automatic discovery of LAN network services (SLP, Jini, UPnP)
Internet scale discovery (INS/Twine, Ninja)

Wide-area service discovery





Multiple attributes
Auto configured and rapid availability
Automated discovery without user input
Policy support by agent
Scalable
Motivation
for new service discovery protocols

Pervasive computing
Static resource information (whois, RLP, X.500)
 Me-services
 User intent





Client thickness
 Personal and pervasive
discovery
LAN network
services service
(SLP, Jini,
UPnP)
Cyber Automatic
foraging (living
off the of
land)
 Semantic
discovery
Context awareness
 Dynamic service composition
Proactive vs transparent
 Distributed trust management
Ninja, CoolTown)
Ad hocInternet
networksscale discovery (INS/Twine,
 Profile driven management
 Semantic web
Ad hoc discovery without infrastructure (Konark, DEAPSpace)

Express meaning

Knowledge representation using ontologies

Improving accuracy of web search
Location aware discovery (Agents2Go, Splendor)
 Agents exchange ontology information to
Semantic service discovery
(Ronin, DReggie)
perform service discovery
[1] The semantic web, Scientific American, 2001
[2] Pervasive computing: vision and challenges, IEEE personal communications, 2001
[4] Me-services: a framework for secure and personalized discovery…, 2002
Components

Directory repository

Provider
Directory

Consumer
Centralized
Distributed




Hierarchical
Structured P2P
Ad hoc
Service description




Attribute/value
Tree-like
XML
Ontologies (DAML)
Components

Announcement

Provider
Directory

Consumer

Register
Multicast/broadcast
Query/Service Access



Syntax
Ontology
Programming language
dependency
References for mainstream protocols:
[9] The Service Location Protocol, IEEE Internet Computing, 1999
[11] Jini architecture specification, Sun Microsystems, 2003
[12] Understanding Universal Plug and Play white paper, Microsoft, 2000
[13] Specification of the Bluetooth system, Bluetooth
[14] Salutation architecture specification version 2.1, The Salutation Consortium, 1999
Mainstream protocols
Jini
Salutation
SLP
UPnP
Bluetooth
Main
Entities
Lookup
Service,
Client,
Service
Salutation
Manager,
Transport
Manager,
Client Server
Directory
Agent, Service
Agent, User
Agent
Control Point,
Devices
(Services)
SDP Client,
SDP Server
(or both)
Service
Repository
Lookup
Service
A set of SLMs
DA (directory
agent)
None
SDP Server
Service
Announcement
Discovery/
Join protocol
Registering
with local SLM
Service
Registration
Multicast
Not
advertisement Supported
Access to
Service
Service proxy Service
object based Session
on RMI
Management
Service type
for discovered
service
Invoking
Action to
service
Not
Supported
Service
Description
Interface
type and
attribute
matching
Service type
and attribute
matching
Description in
XML
Attribute ID
and Attribute
Value
Functional
Unit and
attributes
within it
Mainstream protocols
Jini
Salutation
SLP
UPnP
Bluetooth
Service
Group
Group
No
Scope
No
Service Class
Event
Notification
Remote Events
Availability
Checking
(periodic &
automatic)
SLP
extension for
event
notification
Service
publishes
event when
state variable
changes
Not Supported
Other
Features
Java-centric
architecture
Transport
independence
Authenticatio Automatic
n security
configuration
feature
Services could
be browsed
from a
hierarchy
Usage
CNN and sprint
Web/ Directory
Servers, Email, Calendar,
Collaboration
Servers
Novell
Netware
Bluetooth
access points,
print adaptors,
Palm OS
bluetooth
system
WinXP for
gateways,
Internet
connectivity
and NAT
More protocols…
mSLP: mesh-enhanced SLP




Fully-meshed peering DA
architecture with one or
more scopes in common
Reliability
Scalability
Backward Compatibilityextends DA Advertisement
with a “mesh-enhanced”
attribute
[10] mSLP – mesh enhanced SLP, ICCCN, 2000
More protocols…
UDDI: Universal Description, Discovery and Integration




UDDI specifications and schemas used to build
discovery services on Internet
Provide consistent publishing interface
Allow programmatic discovery of services
Who: Sun, IBM, Microsoft partnership
[15] UDDI technical white paper, 2000
More Protocols…
UDDI: Universal Description, Discovery and Integration
Services described
in XML and
published using
Publisher’s API
Consumers access
services by using
the Programmer’s
API built on SOAP
Business registry
contains yellow,
white, green
pages
Design for ad hoc networks





No central directory service
Limited use of network/device resources
Reliability
Pervasive
Distributed
Konark
DeapSpace
GSD
Allia
Design for ad hoc networks

Main entities


Node acts as client+server
Service announcement

Flooding





On device join
Periodically, delta announcement (Konark)
Slotted (DEAPSpace uses slotted+periodic)
Cache advertisements
TTL
Design for ad hoc networks

Service description

What is described?




service name, type, attribute, keywords, properties and
functions
Service hierarchy - tree like structure (Konark, GSD)
Interface format, e.g., function prototype.
How is it described and stored?


WSDL file (Konark)
Data structures similar to ASN.1 (DEAPSpace)


Encoder/decoder
Ontology: DAML+OIL (GSD)
Design for ad hoc networks

Access to the service

RPC


SOAP/HTTP (Konark)
Specific Interface, e.g., function prototype


Query formation


Encoder/decoder (DEAPSpace)
Path based or syntax based
Request routing


Policy based (Allia)
Group based (GSD)
Contributions
Konark
DEAPSpace
GSD
Allia
Service
Description
WSDL,
hierarchy of
services
Data structures
(encoder/decoder)
DAML+OIL
N/A
Service
Announcement
Delta gossip
protocol
Slotted+periodic
broadcast
Broadcast
(broadcastID)
Policy based
alliance of nearby
nodes
Access to
Service
SOAP/HTTP;
path or syntax
based query
Interface
N/D
N/D
Intelligently
routes to the
service groups
Provides a policy
based framework
(Advertisement,
Cache and
Forwarding
Managers)
Other Remarks
[17]
[18]
[19]
[20]
Konark – a service discovery and delivery protocol for ad hoc networks, WCNC, 2003
DEAPspace – transient ad hoc networking of pervasive devices, Computer Networks, 2001
GSD: a novel group-based service discovery for MANETS, MWCN, 2002
Allia: alliance-based service discovery for ad-hoc environments, WMC, 2002
Design for semantic ontologies




Use of semantic ontologies
Inexact/exact querying
More powerful reasoning engines and AI tools
Enhancing current service location protocols
Ronin Agent Framework
DReggie
Find me the
best cab
service…
Contributions
Ronin Agent Framework

Built on top of Jini


Jini Prolog engine

Java classes and interfaces


Agent deputy




printing service, restaurant
service
Communicate with other
agents using Agent
Communication Language
Mediates agent
communication
Represents owner agent in
the network
Located in the Jini Lookup
Service
Enhance Jini

Agent-oriented development


Dreggie for M-commerce

Matching mechanism of
Jini’s LookupService
Prolog reasoning engine
used for matching
Service registration along
with interface registration


Services register with DAML
description and interface
DAML gives hierarchical
description of services
[21] Dynamic service discovery for mobile computing, BSJCC (Journal), 2001
[22] Dreggie: semantic service discovery for M-commerce applications, 2001
Location-aware service
discovery
Where is the closest Italian restaurant
to me?
• Location sensing
• Nomadic users
• Handy devices
CoolTown,
Splendor,
Agents2Go
CoolTown




Every service (e.g., printer) has a web server, and a tag.
Users walk in and receive URL from tag beacons
Connect to the URL which describes the service and can invokes it
Place manager maintains resources in a place, with web interface
(HTML and XML)


Resources can be grouped.
Also acts as a resolver for some places
Splendor

Tag-based location aware


Tag label location and people
Proxies


Enhanced security
Service management (registration, security)
Bootstrapping using
multicast
Trusted servers
managing
services
Agents2Go
PalmApp (with
CDPD modem)
Cell tower
Location
identified
by cell
tower id
register
Restaurant agent
or other services
User
query
Brokers
Initial
query
form
User
query
Area 2
Locator
Area 3
Maps
geographic
area to
broker
Agents2Go Server
Contributions



Attach web URL to services and
periodically broadcast (CoolTown)
Intermediate trusted proxy for security
and service management (Splendor)
Localized brokers store services in the
location and are mapped to based on
the user location (Agent2Go)
[23] Agents2Go: an infrastructure for location-dependent service discovery, 2001
[24] Splendor: a secure, private, location-aware service discovery protocol, 2003
[25] A web-based nomadic computing system, Computer Networks, 2001
Internet-scale discovery





Construct scalable, robust services
Huge throughput demands and availability
Interoperability
Efficiency
Fault tolerance
INS/Twine,
Ninja/SDS,
WSPDS
INS/Twine
root
res
subject
camera
man

resolver
traffic
Uses Chord

model

ACompany AModel
Resource is a camera, manufactured by
ACompany and filming traffic.

structured peer to peer
system
Lookup in Log(N)
Service Propagation
StrandMapper Resource state changes,
Hash(strand)
update is propagated

Distributed hash
table (Chord).
KeyRouter maps
to Chord.
Periodic refreshing of
resource information


edge resolvers
attached to clients
update frequently
Internal resolvers
infrequently
[30] INS/Twine: a scalable p2p architecture for intentional resource discovery, 2002
Ninja
Services
running on
clusters of
workstations
A chain across
proxies and
bases to find
better service
Stateless
and softstate
proxy
Heterogeneous
devices and
sensors
Secure Service Discovery
Service (SDS)

Distributed data
structures



Uses XML to encode
service descriptions
Certificate Authority
and Capability
Managers for security
Servers dynamically
organize themselves
into hierarchies for
scalability
Filters query upwards
to avoid overloading
one node (Bloom filter)
[28] The ninja architecture for robust Internet-scale systems and services, JCN, 2001
[27] An architecture for a secure service discovery service, MobiCom, 1999
Multi-tier ubiquitous service
discovery protocol
Global Services
Registry-gateway
to global network

Brokering
Agentrecommends
appropriate
service
Context attributes provided
by services





Attribute-value pair service
description
Localized Service
Propagation

Global Services

propagate upward with
attenuation factor of service
attributes
Query Routing

Domain
Hierarchy
Distance to server
Server load
Service channel
Overlay hierarchy
[26] A multi-tier ubiquitous service discovery
protocol, Mobisys, 2003
WSPDS: Web Services P2P
Discovery Service



Servent: Server/Client
DAML ontology for service description
Querical data network




Probabilistic flooding
Each node defined by content
Node links to other nodes of smiliar
content
Semantic matching algorithm used to
choose neighbor
[29] WSPDS: web services p2p discovery service, ISWS, 2004
Contributions




INS/Twine: structured P2P lookup on
strands
Ninja/SDS: query filtering and service
aggregation
Multi-tier Ubiquitous SDP: context
attributes, hierarchical, localized service
propagation
WSPDS: QDN, DAML for service
description
Conclusions



Service discovery for different scenarios
in ubiquitous and pervasive
environments: ad-hoc, location-aware,
semantic and Internet-scale, and
combinations of these
Tackle problems in service distribution,
query and description
Not much work done in semantic
service discovery
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
T. Berners-Lee, J. Hendler, and O. Lassila, The Semantic Web, Scientific American , May 2001
M. Satyanarayanan, Pervasive Computing: Vision and Challenges, IEEE Personal Communications , August 2001.
M. Weiser, The computer for the twenty-first century Scientific American, pp 94-103, September 1992
Anupam Joshi, Tim Finin, and Yelena Yesha, Me-Services: A Framework for Secure and Personalized Discovery, Composition and
Management of Services in Pervasive Environments, in Web Services, E-Business, and the Semantic Web, C. Bussler, R. Hull, S.
McIlraith, M.E. Orlowska, B. Pernici, J. Yang (Eds.), LNCS 2512, p. 248 ff., Springer, ISBN:3540001980, December 2002
J. Rosenberg, E. Guttman, R. Moats, H. Schulzrinne, WASRV Architectural Principles Internet Draft, Internet Engineering Task
Force, Feb. 1998. Work in progress.
Michael F. Schwartz, Alan Emtage, Brewster Kahle, and B. Clifford Newman. A comparison of internet resource discovery
approaches, Computing Systems, 5(4):466-493, Fall 1992.
M. Accetta, Resource Location Protocol RFC 887, Internet Engineering Task Force, December 1983.
C. Lee, S. Helal, Protocols for Service Discovery in Dynamic and Mobile Networks, International Journal of Computer Research,
Volume 11, pp 1-12, 2002
Erik Guttman, The Service Location Protocol, IEEE Internet Computing July 1999.
Weibin Zhao, Henning Schulzrinne and Erik Guttman, "mSLP - Mesh-enhanced Service Location Protocol", International
Conference on Computer Communications and Networks (ICCCN'00), October, 2000.
Jini Architecture Specification, Sun Microsystems, June 2003
Understanding Universal Plug and Play White Paper, Microsoft Corporation, June 2000.
Specification of the Bluetooth System, Bluetooth (www.bluetooth.org), pp 113-156
Salutation Architecture Specification Version 2.1, The Salutation Consortium, 1999
UDDI Technical White Paper, UDDI (Universal Description, Discovery and Integration), September 2000.
A. Gulbrandsen, P. Vixie, L. Esibov, A DNS RR for specifying the location of services (DNS SRV) RFC 2782, Internet Engineering
Task Force, February 2000.
References
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
S. Helal, N. Desai, V. Verma and C. Lee, Konark--A Service Discovery and Delivery Protocol for Ad-hoc Networks, Proceedings of the Third IEEE Conference
on Wireless Communication Networks (WCNC), New Orleans, March 2003.
R. Hermann, D. Husemann, M. Moser, M. Nidd, C. Rohner, A. Schade, DEAPspace--Transient ad hoc networking of pervasive devices, Computer Networks
Volume 35 pp 411-428, 2001
D. Chakraborty, A. Joshi, , GSD: A Novel Group-based Service Discovery Protocol for MANETS, 4th IEEE Conference on Mobile and Wireless
Communications Networks (MWCN 2002). Stockholm. Sweden. September. 2002
Olga Ratsimor, Dipanjan Chakraborty, Sovrin Tolia, Deepali Kushraj, Anugeetha Kunjithapatham, Gaurav Gupta, Anupam Joshi, Timothy Finin, Allia:
Alliance-based Service Discovery for Ad-Hoc Environments, Second ACM International Workshop on Mobile Commerce, in conjunction with Mobicom 2002,
Sep 28, 2002, Atlanta GA, USA
H. Chen, A. Joshi, T. Finin. Dynamic Service Discovery for Mobile Computing: Intelligent Agents Meet Jini in the Aether, Baltzer Science Journal on Cluster
Computing, Vol. 4, No. 4, March 2001
D. Chakraborty, F. Perich, S. Avancha, and A. Joshi. DReggie: Semantic Service Discovery for M-Commerce Applications In Workshop on Reliable and
Secure Applications in Mobile Environment, Symposium on Reliable Distributed Systems, October 2001.
O. Ratsimor, V. Korolev, A. Joshi, T. Finin. Agents2Go: An Infrastructure for Location-Dependent Service Discovery in The Mobile Electronic Commerce
Environment ACM Mobile Commerce Workshop, July, 2001
F. Zhu, M. Mutka, and L. Ni, Splendor: A Secure, Private, and Location-aware Service Discovery Protocol Supporting Mobile Services 1st IEEE Annual
Conference on Pervasive Computing and Communications, IEEE Computer Society Press, Fort Worth, Texas, 2003
T. Kindberg and J. Barton, A Web-based nomadic computing system, Computer Networks, Esevier. Vol 35, No. 4, March 2001, 443-456
C. Lee and A. Helal, A Multi-tier Ubiquitous Service Discovery Protocol First ACM International Conference on Mobile Systems and Applications (Mobisys),
May 2003
S.E. Czerwinski, B. Zhao, T. Hodes, A. Joseph, and R. Katz, An Architecture for a Secure Service Discovery Service, Fifth Annual International Conference
on Mobile Computing and Networks (MobiCom '99), Seattle, WA, August 1999, pp. 24-35
S. D. Gribble, M. Welsh, R. von Behren, E. A. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. H. Katz, Z. M. Mao, S. Ross,
and B. Zhao, The Ninja architecture for robust Internet-scale systems and services, Journal of Computer Networks, vol. 35, no. 4, March 2001.
Farnoush Banaei-Kashani, Ching-Chien Chen, Cyrus Shahabi, WSPDS: Web Services Peer-to-peer Discovery Service , International Symposium on Web
Services and Applications(ISWS'04) , Las Vegas, Nevada, USA, June, 2004
M. Balazinska, H. Balakrishnan, D. Karger, INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery, International Conference on
Pervasive Computing August 2002