Object Services and Consulting Inc.
A Reference Model for Trader-Based Distributed Systems Architectures
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.
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
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.
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.
it is not smart enough and requires too much a priori information
the vocabulary makes it more suitable for programs than humans (related
to the previous point)
a single trader is not a scalable solution. There are also other less obvious
impediments to scalability
it works only in a homogenous middleware environment where there is strong
agreement on what things mean (e.g. a common interface repository)
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 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.
||ODP(Open Distributed Processing)
|Service Name Space
|Matching Heuristic - II
||Cooperating (federated) - transparent, user-visible
||Direct (trader-trader protocol): further divisions are simple,
based and free
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 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
Service Name Space
Many systems reuse existing name/directory servers that are typically hierarchical
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.
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.
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.
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.
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.
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.
This categorization borrows and extends the one from Muller:
Non-communicative federation - Here multiple traders exist primarily
for the purposes of load balancing. Members of the federation are
separately visible to trader client, and the client has to choose the individual
trader it wants to import from.
Repository-based Federation - This is a database-like scheme where
multiple traders read and write to the same service offer repository. This
federation approach assumes standardization across traders of service offer
vocabulary, the accessibility of a single (logical) service offer repository
to all traders, and the applicability of a common set of policies (technical,
administrative, security) for the federating traders. It is felt that this
approach would be hard to operate across multiple organizations. The approach
is indirect in that participating traders are not directly aware
of each other.
Direct Federation - This is a direct federation scheme whereby
cooperating traders selectively forward requests to each other. Link
within a trader hold information about other traders (e.g. how to bind
to the target trader, what domains are handled by the target trader etc.).
A source trader may examine the link objects it holds to determine which
of many possible target traders to delegate a particular client request
to. The simple federation scheme still requires some implicit agreement
on the service offer model amongst federated traders.
Type Manager Based Federation - In this scheme, traders in different
domains are managed by type managers. Type managers take care of
translating between type domains, and therefore allow traders with different
type domains and different service offer vocabularies to communicate with
each other without being aware of the vocabulary mismatches. Type domains
may have different names and identifiers for equivalent types. The type
manager communication protocol takes care of doing the appropriate name/identifier
mapping, and giving the participating traders the impression of operating
under a single type model. Some schemes have proposed an architectural
agent called an interceptor to mediate
conversations between traders and/or type managers. Interceptors may act
as vocabulary gateways, security monitors or other functions. Type manager
based federation assumes homogeneous middleware.
Heterogeneous Federation - This scheme extends trader federations
to heterogenous middleware platforms by adding the notion of proxies
the architecture. Proxies may transform data and bindings so that client
data and bindings make sense to the service and vice-versa. Without proxy
capability, it is possible for a server to return a handle to something
that is not interpretable by the middleware platform on the client-side.
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
Support for nomadism in a global environment (Jacob
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
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
Accomplishing Distributed Traders using the X.500 Directory (Richman
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
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.
[Bear92] M. Bearman and K. Raymond, Federating
Traders: an ODP Adventure, Open Distributed Processing,, ed. J. de
Meer, V. Heymer, and R. Roth, North-Holland, (1992), pp. 125-143.
[Bear95] Bearman,M., Trading in Open Distributed
Environments, Proc. of the International Conference on Open Distributed
Processing, February 1995, Brisbane, Australia.
[DSOM94] E.Kovacs and S.Wing, Trading and
Distributed Application Management : An Integrated Approach, The Third
Conference on Open Distributed Processing, Brisbane, Australia, 1995.
DIS 13235 -ODP Trading Function, 1995
[Jaco96a] B. L. Jacob and T. Mudge. The
trading function in action. Proc. 7th ACM SIGOPS European Workshop,
Connemara, Ireland, Sep. 1996, pp. 241-247. Also at http://mosquitonet.stanford.edu/sigops96/papers/index.html
[Jaco96b] B. L. Jacob and T. Mudge. Support
for nomadism in a global environment. Workshop on Object Replication
and Mobile Computing, San Jose, CA,, Oct., 1996.
[Kova94] Kovacs, E. and Wirag,S., Trading and
Distributed Application Management: An Integrated Approach, Proc. of
the Fifth IEEE Workshop on Distributed Systems: Operations and Management,
[Merz94] M. Merz, K. Muller, and W. Lamersdorf,
Trading and Mediation in Distributed Computing Systems, Proceeding
of the 14th International Conference on Distributed Computing Systems,
IEEE Computer Society Press, Los Alamitos, CA, (1994), pp. 450-457.
[Merz96] M. Merz, K. Müller-Jones, W. Lamersdorf
, Agents, Services, and Markets: How do they integrate? , ICDP96,
27. Feb. - 1. Mar. 1996
[Mull96]Muller, M. et al., Global
Trader Cooperation in Open Service Markets , Univ. of Hamburg Technical
[Popi91] C. Popien and B. Meyer, Federating ODP
Traders: An X.500 Approach, Proceedings of the International Conference
on Communications, ed. J. Siegel, Geneva, (1991), pp. 313-317
[Prat94] W. Pratten, J. W. Hong, J. M. Bennett,
M. A. Bauer, and H. Lutfiyya, Design and Implementation of a Trader-Based
Resource Management System, Proceedings of CASCON'94, Toronto, (1994).
[Prat95] Pratten et al., A Resource Management
System Based on ODP Trader Concepts and X.500, Proc. of the International
Symposium on Integrated Network Management, 1995
[Pude] Puder, A. et al., AI-Based Trading in Open
[Rich] Richman,A. and Hoang, D., Accomplishing
Distributed Traders using the X.500 Directory
[Vahd97] WebOS: Operating System Services for
Wide Area Applications , University of California-Berkeley Technical
[Voge95] A. Vogel, A. Beitz, and R. Ianella, Discovery
and Access of Services in Globally Distributed Systems, DSTC Symposium,
DSTC Pty. Ltd., Brisbane, (1995).
[Voge95b] A. Vogel, M. Bearman, and A. Beitz,
Interworking of Traders, Open Distributed Processing III, ed. K. Raymond
and E. Amstrong, Chapman & Hall, London, (1995, in press).
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