|Service-Discovery Research @ NIST: Why, What, and How|
Future software services and automated devices will
exist in large numbers and will operate in a networked world where they can never be quite sure
about the connectivity available, about the other services and devices nearby, or about the state
of the network neighborhood a few minutes in the future. In such uncertain environments, individual
components will need to discover and maintain awareness of their surroundings and to configure and
adapt themselves in response to changing situations.
The beginnings of the necessary capabilities have emerged over the past few years in the
form of service and device discovery protocols, such as Jini Networking Technology, Universal Plug-and-Play,
(UPnP) the Service Location Protocol (SLP), Bluetooth service discovery, the Salutation Consortium protocol suite,
and the protocols developed by the Home Audio-Video interoperability (HAVi) forum. Some of these initiatives
approach the problem from a vertically integrated perspective, coupled with a narrow application focus,
while others propose more widely applicable solutions. Despite differences, all of these initiatives aim
to allow small collections of commercial devices and services to auto-configure, to cooperate, and to
adapt to changes.
In more demanding environments, as found for example in military or emergency response
operations, communicating components will operate in larger collections. Further, in extremely volatile
environments, components may find that cooperating components disappear due to physical or cyber attacks
or due to jamming of communication channels or movement of nodes beyond communications range. To address
such hostile environments, military programs have already begun to experiment with and evaluate some of
the emerging commercial discovery protocols.
Service-discovery research at the NIST Advanced Network Technology Division assisted potential government (particulary military)
users of service-discovery systems, as well as commercial designers and developers of such systems by:
- Characterizing the behavioral and performance properties of selected first-generation service-discovery
protocols when deployed in demanding situations.
- Designing and characterizing self-adaptive mechanisms to improve performance of service-discovery
protocols in volatile and hostile environments
- Developing and publishing an architectural specification that encompasses the general features provided
by a range of first-generation service-discovery protocols.
The results from this project provided information that prospective users of current service-discovery systems can apply to
understand what performance and behavior to expect and can also apply to implement alternate algorithms that may yield improved
performance in volatile environments. The project also provided information that designers can use to improve the next-generation of
|Project Accomplishments in Three Phases|
|Phase I Accomplishments (Performance and Behavior Characterization):
Phase I of the project characterized performance of selected service-discovery
protocols (Jini, UPnP, and SLP) as specified and implemented. The project achieved the following specific accomplishments:
- Developed architectural and behavioral models for the Jini (in Rapide and SLX), UPnP (in Rapide and SLX), and SLP (in SLX)
- Established performance benchmarks for Jini, UPnP, and SLP regarding the following characteristics:
- Functional effectiveness, failure-detection latency, failure-recovery latency, and message overhead when attempting to maintain
an operational set of services in the face of node failures.
- Update effectiveness, responsiveness, and efficiency when attempting to maintain consistent information in the face of
communication failure and message loss.
- Restoration latency (average, maximum, and variance) when attempting to reestablish a previously known discovery topology
after power failure.
- Discovered some undesirable behaviors in selected service-discovery protocols:
- Found that feature interference in various recovery mechanisms can lead to lower than anticipated update effectiveness for
some failure rates.
- Found that interfering interactions between directed and multicast discovery processes can lead to inconsistent states among
components in a service-discovery system.
- Found that insensitivity to dynamic group changes can lead to inconsistent states among components in a service-discovery system.
- Found that lack of guidance about sequencing queries for service descriptions and registrations for notification of service
arrivals can lead to situations where service arrivals go undetected.
- Developed and published a generic architectural model that unifies the structure and behavior of a range
of first-generation service discovery systems. The generic architectural model includes:
- UML class diagrams representing a meta-model through which service-discovery systems can be expressed.
- UML class diagrams and sequence diagrams representing various service-discovery functions and processes, including
discoverable items, configuration discovery and monitoring, registrations and extensions, service-description discovery
and monitoring, and variable discovery and monitoring.
- Identification of functions and processes that are not sufficiently specified or designed in first-generation service
- Optional algorithms to address performance issues (multicast-response implosion, extension policy, and replica selection) that
often arise in first-generation service discovery systems.
- Consistency conditions to express requirements that service-discovery protocols should strive to meet, and to define uncertainties
that exist with regard to the ability of service-discovery protocols to meet the defined consistency conditions.
- Specializations of the generic model showing how selected, specific service-discovery systems can be represented.
|Phase II Accomplishments (Algorithm Development and Evaluation)
Phase II of the project to designed, analyzed, simulated, and characterized self-adaptive mechanisms to improve performance in
volatile environments. project achieved the following specific accomplishments:
- Devised, simulated, and characterized the performance (discovery effectiveness, discovery latency, buffer occupancy, and
processor usage) of four algorithms (random-burst, random-paced, scheduled-burst, and scheduled-paced) designed to
mitigate multicast-response implosion in UPnP service-discovery systems.
- Analyzed the performance characteristics of Jini leasing and devised six candidate algorithms (fixed, random, requested, adaptive,
inverted, and priority) for assigning and renewing leases
- Specified, analyzed, simulated, and characterized the behavior and performance (responsiveness and bandwidth consumption) of two
algorithms (adaptive and inverted) for assigning and renewing Jini leases.
- Generalized the Jini adaptive-leasing algorithm to become an adaptive failure-detection algorithm, and then simulated and characterized
the behavior and performance (failure-detection latency and bandwidth consumption) of the algorithm in three different applications
(assigning Jini leasing intervals, assigning SLP registration-refresh intervals, and assigning SLP polling intervals).
- Devised, simulated, and characterized the behavior and performance (system response time, server-overload rate, and related variances)
of six candidate algorithms (random, greedy, partitioned, weighted, balanced, and balanced-partitioned) for replica selection by clients
in service-discovery systems.
|Phase III Accomplishments (Implementation and Demonstration)
This phase of the project implemented and validated the adaptive algorithm for Jini leases in “reggie” (the lookup service
implementation distributed by Sun Microsystems) and demonstrated the behavior and effectiveness of the algorithm at the IEEE DISCEX III
Conference (April 2003), the ACM Workshop on Self-Managing Systems (June 2003), and the DARPA Fault-Tolerant Networks Principal
Investigators Meeting (July 2003).