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 service-discovery systems

• Developed architectural and behavioral models for the Jini (in Rapide and SLX), UPnP (in Rapide and SLX), and SLP (in SLX) service-discovery protocols.
   
• 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 discovery systems.
   
• 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.
   

• 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.