Venu Vasudevan
Object Services and Consulting Inc.
 

January 1998
 

Motivation

Large distributed systems consist of large numbers of components (objects) and large numbers of bindings. The web, as it moves from documents to programs, is an example of such a distributed system. As component technology gets more refined, distributed systems architectures are going to tend towards smaller, more numerous components. This in turn implies a greater number of (client-server or other) bindings in any working distributed system. System stability then requires that the bindings and components be super-reliable, which is hard to do. The alternative is to build  distributed applications layered over an intelligent service discovery framework whereby the bindings between components can be (re)discovered at runtime, and do not have to be static. This helps in overall system scalability and stability in that a system of components can reorganize itself by each of its components dynamically rediscovering (reinstantiating) their bindings.  Another reason for service discovery is component mobility. Components may move, because their containers move, or because they have to move to optimize the distributed computation. The former is the mobile computing case where a Java applet moves because the PC that is carrying it is on a plane. The latter is a case of mobile code, and more extremely, agents. Trading is a simple mechanism that decouples clients and servers by providing an intelligent directory service, the basis for a service discovery framework. This allows for dynamic (re) binding of the sort described above, while ensuring that the reorganized distributed system is functionally equivalent to the original to some degree of tolerance.  The rest of this report describes the themes and variations of trader-based distributed systems architectures in some detail, and surveys existing work.

Design Space

Basics -  Simple Trader

Traders mediate between service providers and service requesters, thus providing a loosely coupled architecture where the binding between provider and requester is established at run-time (and can change). Services advertise themselves by registering  service descriptor objects with the trader (aka exporting to the trader). Service descriptors describe a service offer in terms that will allow the trader to match a service requester's needs against available service offers. As part of the service offer, services provide some name/handle by which a client can bind to them and invoke their capabilities.  This service name space or context space can be flat or hierarchical. Frequently, an existing naming scheme ( X.500, ASN.1 etc.) is used and in large systems, it is common for the namespace to be hierarchical.

Service requesters make requests to the trader for a particular kind of service (aka importing from the trader). The vocabulary of a service request conveys some type-related and some property-based information  about the desired service. The requester may request that all or any one service offer that satisfies the service request be returned. In the former case, the service requester is responsible for iterating through the matching service offer set and picking its favorite offer. Service requesters and providers need to share a service type formalism (e.g. IDL) that describes the service types to each other and to the trader.  If this is the case, then the trader needs to store only type names and implicitly assume a shared type description repository. This approach presumes a homogenous middleware platform (e.g. in the case of ORBs, that providers and requesters are using the same interface repository).

Given a collection of service requests, the trader uses a matching heuristic to find the best matching service offer in response to a service request. The complexity of the matching heuristic is dependent on the service type formalism, and the vocabularies used for service offers and service requests .  In basic trading, the trader is stateless1and does not process the service request itself. The client-side protocol extracts the service handle/name from the service offer object, and binds to the appropriate server. The matching heuristic may be centralized in the trader or distributed amongst service offer objects. In the centralized case, the trader operates on a collection of passive service offer objects using matching algorithms that are internal to the trader. In the distributed matching case, the service offers are active objects external to the trader (perhaps ORB objects) and may encapsulate the matching algorithm within themselves. In this case, the trader multicasts the matching criteria to the service offer objects and collates/transforms the responses. The notion of matching in the basic case is boolean (match or no match).

1 - Stateless refers to the fact that the trader does not maintain any dynamic state information (e.g. service response time) about the service instances it is trading.  Even stateless traders maintain registration information (location, handle etc.) about service instances.

Nuances

There are three drawbacks to the basic trader architecture described above: Recent work in the trading, open distributed processing and electronic marketplaces arena has addressed all of the above to differing degrees. The problem that has received the most attention is the scalability bottleneck caused by a single trader scheme. Various approaches to trader federation have been proposed. In most (but not all) federation schemes, the trader client sees a single logical trader, but the backend is organized as a federation of traders based on an inter-trader protocol.  The more ambitious federation schemes address model heterogeneity, in that they do not require federated traders to share a single type model.

Most approaches to building smarter traders rely on AI and knowledge representation techniques to model service semantics more explicitly, and to make the service matching algorithm concept-based as opposed to property-based.  Reduction in the amount of a priori agreement is claimed to be tackled by the use of learning techniques. Most smart traders use concept graphs or other variants of semantic nets (in contrast to an interface definition language) to specify service offers and service invocation semantics. The same formalism is used to specify service request, and the case is made that a concept-based language for service requests is a more natural language for people (as opposed to programs) to make service requests.  Greater semantics in the service descriptor language and the service requester language imply that the matching heuristic has to get smarter as well (e.g. in the case of semantic nets, some metric like semantic distance ends up being applied for matches).

Some of the above is described in more detail in the taxonomy section below.

A Taxonomy

Below is a taxonomy of classification criteria (row 1) and trader architecture categories within that criteria (rows 2 and 3). Criteria that apply to simple traders are listed before the nuances of advanced trading. Descriptions of the criteria are below the table.
 
 

    Category

    Approach

    Contrasting Approach
Knowledge Representation ODP(Open Distributed Processing) AI
Service Descriptor Explicit Implicit
Service Name Space Flat Hierarchical
Service Invocation None/synchronous Asynchronous
Fault Assumptions Fault-free Fault-Aware
System Assumptions Closed-world Open
Matching Heuristic Property-Based Concept-Based
Matching Heuristic - II Static Dynamic
Request Interception Universal  Optional
Scalability Single (monolithic) Cooperating (federated) - transparent, user-visible
Federation Approach Indirect (repository-based) Direct (trader-trader protocol): further divisions are simple, type-domain based and free
Communication Immediate Store-and-Forward (stateful)

Knowledge Representation

There are two approaches to trader architectures, the ODP (Open Distributed Processing) and the AI approach. The ODP approach is an evolutionary change to current distributed object architectures that solves the mediation problem. The mediation problem being one of loosening the coupling in client-server systems by allowing this binding to be created or changed at runtime. The ODP approach to trading retains much that is present in distributed object architectures such as IDL based typing, the notion of an interface repository, use of properties and a COSS property service-like entities as a building block for matching heuristics.

AI approaches to trader architecture attempt to solve not only the mediation problem, but also address what they view as problems inherent in the distributed object architecture such as the semantic poverty of IDL as a service description language, and therefore the drawbacks of property-based approaches to offer-request matching. They aim to build a trader architecture which requires less explicit information to begin operations, and improves with experience.

Service Descriptor

Service descriptors are used by services to advertise their service offers to the trader. Service descriptors can either be explicitly supplied (pushed) by the service, or inferred by some automated agent like a robot (this is the equivalent of a pull scheme along the lines of  web search engine robots).  In the case of ODP traders, the service descriptor is an interface description augmented by service instance specific property values .  AI approaches to trading use service description formalisms that are variants of semantic nets. The arguments being that decorated interface objects say very little about service semantics, and that smart trading requires deeper knowledge about service semantics. In some AI trader schemes, the semantic net representation of a service offer is constructed implicitly.

Service Name Space

Many systems reuse existing name/directory servers that are typically hierarchical (e.g. X.500) and even their repositories and service offer repositories. In the case of the web, the name hierarchy is flat, and  buried in the URN (URL).

Fault and System Assumptions

Fault assumptions have to do with whether it is assumed that a service that is registered with the trader is assumed to be up, available and fault-free. Although this is frequently not discussed in trader architecture proposals, the assumption seems to be that the trader is not in the fault management business, and therefore assumes that it is operating in a fault-free environment. The closed-world assumption has to do with whether the trader assumes that all service types that are requested by trader clients may be assumed to exist in the system. This seems to be the common assumption in many working systems, especially telecommunication systems.

Matching Heuristic

ODP-based traders presume a service offer to be comprised of an interface definition and a set of properties about the service instance . A service request is presumed to specify the desired service type, and a boolean property expression that the properties of the service offer should satisfy. The matching heuristic is typically a boolean property expression that has to be satisfied by the service offer to match the service request. Some ODP-based traders support dynamic properties, or properties whose value has to be dynamically evaluated (e.g. the current queue length in a printer).  While these have some value, they make the matching algorithm more expensive. An alternative is to have quasi-dynamic properties that are either evaluated periodically (property pull), or are updatable by the service provider (property push).

AI-based traders use semantic matching. The service request is expressed in some sort of concept vocabulary  that is more free-form than the ODP vocabulary of desired service type and properties. The service properties and semantics are represented using one's favorite derivative of a semantic net (concept graphs from natural language processing seem to see much use), as are service offers. Matching is the process of concept graph matching based on some notion of semantic distance between two concept graphs. The claim is made that service descriptions need not be explicit, and that learning algorithms can manufacture these descriptions over time.

Request Interception

Architecturally, a trader could be a universal mediator, or one used by client-choice. In the former case, no direct binding between a client and a server is established, and all communication happens via a trader. In the latter case, clients may choose to bind tightly with a server, or loosely via the trader. Universal mediation has certain architectural advantages but is quite expensive in terms of bandwidth and inefficiency. Most current proposals use a client-choice trading protocol.

Service Invocation

The trader may either be a pure matchmaker or an enactor of the match. In the former case (which is also the predominant case) the trader returns matching service offer(s) to the client. The client is then responsible for binding to the service using information (e.g. service handles) embedded in the matching service offers. In an enactment architecture, the trader processes the matching request on behalf of the client.  A different dimension of service invocation is whether the interaction between client-service-trader is synchronous (via calls) or asynchronous (via events). The only instance of an enactment based trader architecture  is also asynchronous, where the trader may queue requests from trader clients and manage the queue.

Communication

In situations where the trader is also an enactor, there is the issue of whether the trader immediately invokes the matching service, or whether it stores the service request and may wait for a matching service to register itself with the trader. The former is labeled as immediate, and the latter as a store-and-forward architecture. A store-and-forward scenario is depicted in a telecom system proposal based on trading.

Scalability

While the single monolithic trader is an architectural possibility in certain situations (after all,  monolithic search engines are able to handle the internet!), few if any trader proposals suffer from this drawback. Most architectural proposals provide some form of trader-trader communication protocol that allows trading knowledge and computation to be distributed amongst traders. In some of these proposals, the existence of a federation (multiple traders) is visible to all trader clients. In most cases, the federation protocols are transparent to trader clients.

Federation Architecture

This categorization borrows and extends the one from Muller:
 

Description and Analysis of current trading approaches

The trading function in action (Jacob and Mudge)

This work describes the implementation of an evolving telecom switching function using the ODP trading paradigm. The use of trading allows new and personalized telecom services to be easily added to the system, as well as to deal with software versioning (i.e. the replacement of services with new versions in a running system without bringing the system down). The implementation assumes a closed-world  and fault-free operation. Closed-world means that any service request made to the client is known a priori to be satisfiable in that the service exists.  Fault-free operation means that a service that registers itself with the trader is assumed to be operating in a fault-free manner unless and until it deregisters itself from the trader.

Service invocation is asynchronous and store-and-forward. The trader stores time-tagged requests for services in a queue, and forwards the requests to services as they register themselves with the trader.  Properties supplied in the service offers seem to be static, thus leading to a static and property-based matching heuristic. Request interception by the trader is optional, in that a client chooses whether to communicate to the trader by  executing the trading protocol. Traders form  non-communicating federations. There can be multiple traders in the architecture, and clients can route their request to any particular trader. However, all traders are assumed to be equivalent, and multiple traders exist primary for load-sharing. Clients are aware of multiple traders, as there is no inter-trader protocol that facilitates a single, logical trader view of the federation. Traders do not hold any state other than the request queue. It would seem that system exceptions involving trader failure are handled by the retransmission of requests by affected clients.

Support for nomadism in a global environment (Jacob and Mudge)

The goal of nomadic computing is to make one's environment portable, which in turn requires that you find the closest local services (e.g. a print or fax service) that satisfy an interface, when you plug-in your computer or application into a mobile environment. The case is made that traders that have locality information can help nomadic computing, and that an application can plug-in to the local environment by querying such a trader as part of its setup. While this work does not propose any detailed trader architectures, it outlines some pretty compelling scenarios for the use of traders in mobile computing.

Trader Down Under: Upside Down and Inside Out (DSTC)

This is an implementation of an ODP-based trader where the service offer repository is separated from the trader so as to make repository-based federation possible. Both direct and repository-based federation are supported in this architecture. The separation of a service offer service from trader internals allows multiple traders to share service offers, thus facilitating repository-based federation. The service offer service may implement security policies that allow traders at different security levels to get different levels of access to service offer information. A direct federation protocol involves an interface to establish and traverse links that are established between traders. Links are handles to foreign service offer services that allow a trader to query the service offer service of another trader.  The implementation that is outlined deals with a number of efficiency issues in searching a trader federation.

Trading and Distributed Application Management: An Integrated Approach (Kovacs et al.)

This work discusses a trader architecture where the trader uses dynamic network management information to optimally choose a service offer that matches the client request. In the architecture, a service or set of services are associated with an agent that continuously evaluates the dynamic properties (e.g. load) of these services, and notifies the trader of these service properties. The trader is fault-aware. It is  tied into the event notification and fault management infrastructure and is aware of the availability, load and proper functioning of registered services.  While the trader in this architecture is well informed, it is a far more elaborate infrastructure than the one described in the basic trader scenario in an earlier section. The point of view that the trader should be responsible for the QoS of the service offers that it provides to clients, is at odds with several other ODP architectures such as the ISO draft standard,  that explicitly want traders to stay out of QoS.

Interworking of Traders in a Distributed Computing Environment (Vogel et al.)

 This work proposes a trader federation protocol that uses direct trader-to-trader communication. Protocols used for client-trader, trader-trader and service-trader are elaborated on.  The similarity between client-trader and trader-trader protocols is noted. An implementation of a database client discovering a database service via a federation of multiple traders is provided. The performance studies are inconclusive. No comparison is made of the tradeoffs of X.500-like indirect federation approaches and direct federation approaches.

Accomplishing Distributed Traders using the X.500 Directory (Richman and Hong)

This work proposes an implementation of the repository-based trader function adapting the X.500 directory service to be a trader service offer repository.  Thus the federation of traders cooperates by accessing a common X.500 repository. The implementation discusses how a  trader information model can be built in X.500, and various tricks to make X.500 efficiently process ODP trader property-based queries.

New Concepts in Qualitative Trader Cooperation (Puder and Berger)

The claim made here  is that the  ODP trader notion of augmented IDL as a service offer description language is insufficiently semantic, and furthermore requires too much information to be specified before trading function can be effective. A variant of semantic nets (called conceptual graphs) is offered as a more semantically rich representation of service semantics, and one that subsumes IDL. It is suggested that the semantic net representation of services can be learned. Semantic nets also form the vocabulary for client queries to the trader. Some notion of semantic distance serves as the matching heuristic for the trader. While this work presents a direction that is an alternative to ODP like matching heuristics, the examples of use are not very compelling.
 
 

References


This research is sponsored by the Defense Advanced Research Projects Agency and managed by the U.S. Air Force Research Laboratory under contract  F30602-98-C-0159. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, U.S. Air Force Research Laboratory, or the United States Government.

© Copyright 1998 Object Services and Consulting, Inc. Permission is granted to copy this document provided this copyright statement is retained in all copies. Disclaimer: OBJS does not warrant the accuracy or completeness of the information in this survey.

Last Revised:  January 1998