Search our
entire site
Enter your search
terms below, or visit
our search page

Search case
studies only
Enter your search
terms below:

For the table
of contents and
hyperlinks to
general topics
proceed to toc

Augmenting OMG traders to handle service composition

Problem description

Much the same way as the WWW  enabled an explosion of globally available documents, it is now enabling an explosion of globally distributed, widely available services.  The ability to access these services via object frameworks such as CORBA and Java, makes it possible to build worldwide distributed object systems that are configured from globally distributed service objects.  The ability to use any object on the internet offers the possibility of reduced engineering effort as well as increased resilience in developing internet-based OSA applications. Such a worldwide OSA architecture also poses a number of scaling problems, a significant one being that of service discovery.  Given the large population of internet-accessible service objects, a large number of service instances will be available that perform equivalent functions. However, these service instances  may differ in significant ways, such as geographic location, content pedigree, mirroring and replication, QoS and other gurantees, data quality, protocols and delivery mechanisms, and payment schemes, to name a few.  From the point of view of any object that is part of an OSA application, the service discovery problem is one of finding the service instances that will provide it the appropriate gurantees, and choosing the best instance for its needs. From an overall application perspective, it is desirable to optimize each binding in this way, ensure that the bindings stay optimized under changing network and traffic conditions, and being able to trigger a rediscovery process when the environmental changes are significant.
 
OSA (as well as internet and agent) architectures have proposed trading services (and traders as objects that support the trading facility) that begin to address service discovery. Server objects (or other objects acting on their behalf) advertise or export their service offers to traders in terms of the  invocation interface and instance-specific properties of the service instance. Client objects invoke traders to discover or import service offers matching a given service interface, as well as the desired instance properties. This model of trading is quite similar to the use of  search engines in information retrieval, in that the matchmaking is done against static attributes of the entity being searched for.

The search engine model of document discovery offers a good starting point for a trading architecture for service discovery, but is not without drawbacks. The drawbacks of current trader architectures come from the fact that they are impoverished search engines, and more importantly from the differences between the goals of document discovery and service discovery.   In service discovery, we are trying to establish a satisfactory end-to-end, persistent and long-lived interaction client and service objects. Furthermore, unlike document objects, both client and service objects (and the bindind in between) are active, exhibit time-variant behavior, and are potentially configurable. An example of configuring service properties directly and indirectly is that of changing the bandwidth property of a video service by choosing a particular protocol, or by changing the making the transmitted video monochromatic. For a trader to explore the different indirect ways to configure a particular service property,  it must understand the service configuration space and be able take configured service behavior into account in matchmaking. This might involve reformulating a trader query  to other semantically equivalent queries in the configurable property space . Another variable that the trader needs to take into account in matchmaking is the commitment a service makes to delivering the advertised properties. The commitment a service can make to whether a particular property (e.g reduced jitter in delivered video) is delivered to the end-user, is dependent on both the service and mediating entities (e.g  the network). Increased commitment can be achieved by either configuring the service, or composing the service with monitoring, translation and other function which change the properties (and commitment) of the delivered function. Furthermore, guranteeing an end-to-end property may require hooking into the client object to assemble a feedback loop (e.g multimedia feedback loops [Cowa96]) , something that is not modelled in current traders that view the client as a black-box.

This paper explores bacwkard compatible augmentations that can be made to the  OMG trading model to build a smarter trader. Specifically desirable qualities include being able to  reformulate queries to more easily solvable ones, awareness of the configurability of service objects and its effect on service properties, the ability to  compose services with other behaviors to reconcile interoperability problems, and the ability to provide continuous and end-to-end gurantees.  Since we are attempting to enrich the OMG trading framework in a backward compatible fashion, a brief description of the current OMG trading framework is included. More detail of OMG and OMG-like traders can be obtained in a companion report [Venu98]

OMG Trading Model Augmentations

The OMG Trading Framework in Brief

In describing the model of compositional trading, we conform to the framework in which the OMG/ODP traders are described. In the OMG/ODP case, the trading model consists of :  service type model, service offers, and service requests. The service type model specifies what a trader needs to know about a service type to be able to trade with instances of this type. The OMG trader models a   service type is as offering an interface and a collection of properties. The schema for these properties (i.e the property name and the domain or its values) is part of the service type specification. Auxillary aspects of service properties such as whether they are editable and whether they are mandatory to specify in all advertisements, are also part of the trading service type model. Individual service offers  conform to the service type specification, and define property values specific to a service instance. Examples of service instance properties include attributes  such as the bit-rate of a video service, and  the languages supported by a document service. Service requests are client queries to the trader, stated as the property predicates the client would desire in a service of a certain interface type. The OMG service request model also allows the specification of policies (that control query propogation) and preferences (that control rank ordering, query result cardinality etc.). This description of the OMG trading model is not complete, and is provided because we reuse the type model, offer model and request model framework that is used by the OMG trader. In the description below, we discuss why the OMG model is not adequate for compositional trading, and additions to it that would facilitate such trading.

Service Type Model

The passive catalog model supported by the OMG trading service models neither the configurability nor the composability of service objects. This is adequate for the exact  matching clients to single, perfectly matching service instances, but insufficient to actively compose multiple service objects to satisfy a client request. To support composition, we therefore  augment the OMG service type model with  configuration and composition models.

The default behavior of service instances may be captured by a property vector with discrete values, but services can frequently be configured to support a range of property values. The service configuration model captures the extent to which services can be configured and the mechanisms for configuring them. In the simple case, there might be a set of operations that directly manipulate a certain property of the service. Realistically however, the property space is not orthogonal, and changing a particular property affects others. Thus, the configuration model needs to capture side-effects and dependencies between different configuration actions. Manipulating the properties of service composites (i.e. services that use other services) requires capturing the relationship between the properties of a used service, and that of the service that uses it.

The composition model specifies  services as adaptors of other services (or data objects produced by other services). While the OMG trading model captures services  characteristics, but not as adapters (wrappers) of services that modify the properties of the wrapped service. This  allows the trader to assemble service composites with desired aggregate properties.   The behavioral specification of services as adaptors is dependent on both the behavior a  service is providing and the manner in which it is implemented.  Two document distillers may both reduce the bandwidth needed to trasmit a document, but one that does so by reducing the images in the document will have different auxillary properties than one that removes irrelevant textual information. The composition model is therefore split between the type model and the service offer model,with implementation specific properties of the adaptor specified in the latter. In both cases, the composition model is further partitioned into specifications for behavior and docking. The former specifies what an adaptor does, while the latter helps the trader determine where it can be placed in a binding.

Configuration Model

The OMG/ODP trading model represents properties of a service type as static and non-configurable. This can lead to false matches where the commitment of a service to providing a particular property value is misinterpreted,  and false mismatches where one ignores the fact that a service can be configured to match a client's request even if it does not do so with the default parameters advertised in a service offer.  Metaproperties are used as a general mechanism in the compositional trader, to describe these second order aspects of the service advertisement. While some metaproperties may be domain or application specific, we discuss a few that seem to be broadly useful, and therefore treated as a core part of the trader vocabulary.

Commitment, negotiability and influences  appear to be broadly useful metaproperties for almost any property on a service instance. The comitment metaproperty (also called level of service in QoS literature [Chat97a], [Yead96]) indicates the commitment made by a service instance to a specific property value. A video server may gurantee to a constant bit-rate output. In this case, the commitment meta-property for this service advertisement (or a subset thereof) has a value guranteed. Clients that bind to this service instance then know that the bit-rate is guranteed by the service.  A metaproperty such as commitment is equally useful outside the multimedia QoS domain. A web annotation service (i.e one that serves annotations made by third parties to web documents) may choose to make a best-effort commitment to the language in which the annotations are recorded. This would mean that the document reader may occasionally  be confronted with german annotations on an english document. In a number of situations, a service instance provides a default property value for some property, but the property is directly configurable or negotiable. In such cases,  the negotiability metaproperty records that a property is negotiable, perhaps upper and lower bounds of negotiation and details of the negotiation protocol. The property space is not an orthogonal one, and modifying the value of one property can have side-effects on another. Reducing the color in an image or a video, for example, reduces the bandwidth required to transmit it. Looked at in reverse, reducing the color depth in an image indirectly configures the bandwidth property of an image or video.   The influences metaproperty is used to capture dependencies between properties within a service schema.Traders can use property influence information to reformulate service requests (e.g ones with predicates that involve non-configurable properties), or to compare direct and indirect configuration approaches to satisfy a service request.
 
Complex services that depend on other service instances can be configured both directly (as above) and transitively.  Transitive configuration means that a service is configured by configuring the services it directly or indirectly uses. A system state monitoring service that provides high-level state information about nodes in a system, uses one of a number of telemetry services to receive low-level, continuous measurement information about these devices. The properties of a state monitoring service instances are then a function of the telemetry service instance (and implementation) that it uses.  A state monitoring service can be transitively configured by using a telemetry service with differing QoS or other properties (more accurate, more reliable, more timely for certain kinds of information etc.).  The property aggregation model specifies the service dependency graph specifying the transitive dependency between the service type we are interested in, and the services it uses.  This structural model is augmented with property expressions that relate property values of the service in terms of properties of the services it depends on.

Composition Model

Adaptors may modify service behavior along three dimensions : interface, properties and metaproperties.  Interface reconcilers [Nimble,Matz96, Seni96] adapt a service to provide a different interface than what it natively provides. [Katz] describes some uses for interface adaptation in mobile computing, and [Senigvonse] in software versioning.  Instances of interface adaptors specialize in the source interface they can adapt from, and the destination interface they can adapt to.  Property adaptors adjust the property values of a delivered service without changing its interface. Format translators, protocol gateways [McCanne] , information distillers [Bick97], text-to-speech transformers[Ye96] are some examples of property adaptors that adapt particular properties of the delivered service by transforming the content. However, property adaptors are not necessarily content transformers. An availability adaptor may transparently allow access to two different instances of the same service, giving the end client the illusion of a single service instance with higher availability.  Property adapters specialize in terms of the property they adapt, and the service interfaces they apply to. The side-effects of a property adaptor are typically a property of its implementation, and are therefore specified in the service offer model. Metaproperty adaptors  don't change the property value of a particular property, but can increase the certainty that the property value will be maintained. A feedback component may act as a property stabilizer, damping the range within which the property may vary and therefore increasing the chances that it will stay within bounds. [Cowa95] provides a number of examples of software feedback components that specialize to stabilize particular properties of a multimedia service. Property cross-checkers will examine the results of a service, and may discard parts of the result that do not posess a certain property. An english  language filter increases the probability that the  document produced by a service is in english only, by removing non-english phrases from it.

Given that we know the adaptor behaviors of services, the placement of adaptors in the binding is driven by soft matchmaking. Given that a perfect match is absent, the soft matchmaking algorithm points out which properties are the most mismatched, and what are the closest matching service instances.  The main cause of the mismatch determines which adaptors are inserted into the binding.  A common  approach is to specify distance functions that measure the distance between the properties of a service advertisement and those specified by a client request. In QoS where properties are continuous, both provided and required properties are more naturally specified as regions with upper and lower bounds.  Individual property-specific distance functions are aggregated to a distance metric between the service instance and the client request. The compositional matchmaker picks certain service instances that are fairly close in aggregate, and uses property and metaproperty adaptors that reduce the distance measure further. If no services of a matching interface can be made to match, the matchmaker resorts to using interface adaptors on other types of service instances and then performs the above step.

To support composition, the OMG trading model has first to support soft matchmaking. That means support for property ranges (and potentially other probabilistic and statistical techniques for specifying property values), the ability for matchmakers to support different aggregate and per property distance functions, and the ability for clients to choose the distance function and the weighting on a per request basis, and a matchmaking function that returns inexact matches based on some distance constraints. Some of this has been pointed out in [Popi96].  To additionally support composition, the matchmaker must not only return the best matches, but also some metrics of the major cause of mismatch. This information determines the kind of  property adaptation that should take place. Finally, adaptors themselves need to be specified in terms of preconditions to their operation, their adaptation behavior and side-effects.
 
The docking specification of a service type determines both ordering (where the service instance is placed), containment (whether the adaptor is free standing or hosted) and binding (how the adaptor is bound into the adaptor chain). Adaptors may be placed in-line or in the feedback portion of a binding. In some cases, the kind of property being adapted places implicitly specifies placement constraints. For example,  adaptors for end-to-end properties like encryption need to be embedded in the data source (and compensated by a decryptor at the client side). Client-side properties such as the format in which information is recieved can be placed anywhere in-line. An ordering of  in-line adaptors can be inferred based on data flow constraints. If an adaptor needs its inputs to have property P, then it is placed after the adaptor that gurantees the property P.  Pluggable (or extensible) adaptors are frequently architected as container-blade architectures, where the blades collectively provide the  'bag of tricks'   Containers may support a common intermediate format for a particular class of blades, generic administrative functions for extending behavior (e.g adding, removing blades),  control strategies for the selection, invocation and composition of blades, and reassembly of transformed information into an outgoing object. Pythia and Digestor  provide some examples of container-blade adaptors for web services implmented using proxy servers. Video transcoders [Amir96] that can be extended to translate between various delivery protocols are architected as containers that accept encode and decode blades for each added protocol.  Along the containment dimensions, adaptors are classified as containers or blades, and explicit compatability relationships are specified between blade and container types. The placement of a blade is then determined by where a  compatible, in-line container is placed in the binding.

Service Offer Model

 In the OMG service offer model, service advertisements specify the supported interface and provide values for properties that are mandated by the service type model for instances of this type. For services that are adaptors, this service offer model needs to be augmented to specify the specifics of an adaptor implementation. In many ways, the service type model for adaptors describes the qualitative effect of the adaptor, but the precise adaptor  behavior is a function of the implementation and is therefore part of the service offer. For example, the adaptor specification for all document distiller  objects might specify that they reduce the size (and therfore the required bandwidth) of the input object. The extent of size reduction depends on the distillation algorithm (e.g does the distiller remove images or text, or does it summarize each paragraph to a fixed size etc.). The service offer adaptor specification refines its service type specification while conforming to it. Conformance means that the refines the adaptor behavior specified as part of the type without violating it. If the type specification of distiller objects says that they reduce bandwidth, the offer specification must not increase the bandwidth instead.

Qualitative models of efficiency and information loss are useful to traders in optimizing the composition. Efficiency metrics  indicate the time overhead added by composition, while information loss metrics provide an indication of how much information is lost by the adaptors in the process of composition. Adaptor efficiency is frequently a function of whether the adaptor needs to translate the object into an intermediate form to operate on it.  Information loss is a function of whether the adaptor elides or transforms the input object. Elision (e.g removal of images from a document) is irreversible, while transformation (e.g reducing image size) is potentially reversible. Both approaches may offer bandwidth reduction, but the image reduction implementation loses less information. Translation type, intermediate format and translation operation are three properties that provide a domain-neutral specification of efficiency and information loss which can be refined to particular domains. Translation type can be either syntactic or semantic depending on whether the adaptor understands the semantics of the content it adapts, or just the structure. Structure-based adaptors tend to be faster but with greater information loss.  Greater distance between the required intermediate format and the format of the incoming object makes it likely that the adaptation is going to take longer. The translation operation may be universal or selective. In the first case, the operation is applied to all parts of the input object, and therefore likely to be less efficient. In the latter case, it is applied to selected subobjects within the composite input object (e.g an image transformer operates only on the GIF images in the document, not the text).

Client Object Model

In the OMG trading model, the relationship between the trading client and the trader is a memoryless client-server relationship. The client is an opaque object that invokes a query on the trader. Other than the query, the trader has no ability to query or manipulate the client in a peer-to-peer fashion. Additionally, the trader is memoryless in that no history of queries from a single client is maintained at the trader. Both these assumptions need to be relaxed for applications that require iterative composition.

QoS applications use composition to make end-to-end property gurantees. Making such a gurantee requires composing configuring the two ends (client and server) as well as composing the core service with auxillary services. The use of software feedback loops for bandwidth adaption [Cowa95], for example, requires the feedback component to hook-in to the client object, and potentially (re)configure it at runtime. The object model underlying the OMG audio-video service proposal [AVSS97] also presumes knowledge and access to the client device API (via a controller object).

Iterative construction of a composite binding (by binding and subsequently rebinding) requires the trader to not only manipulate the client object, but to have a model of stateful interactions with the client (even if it doesn't maintain the state internally). A trader's choice of a new matching service instance may depend on the kinds of failures encountered by the client in the previous binding set up by the trader. Additionally, setting up a semantically correct binding might involve recovering some or all of the state information from a previous binding. Again, while the trader does not need to perform the binding recovery operation, it needs to understand what binding recovery operations need to be performed, so that clients do not need to understand the intricacies of binding management.

Augmentations required to the trading model to provide end-to-end gurantees are not drastic. The notion of a peer-to-peer architecture where the client object API is also exposed is already part of other OMG service proposals [AVSS97]. However, adding stateful binding management capabilities to the trading model is a significant step, although one that has been taken by the RM-ODP archiecture, which is closely related to the OMA architecture.

Related Work

Work related to augmented tradng  falls into one of several categories:

• Related proposals for augmented OMG trading:  Work discussed in [Popi96] is directly involved in the construction of traders that are specialized to QoS applications. It points out continuous properties (i.e properties whose values are ranges) and approximate matchmaking as missing aspects in the current trader proposals that are necessary for QoS.  It discussed specific proposals for how the OMG trader API is augmented to add these capabilities.  While both these capabilities are also needed for a compositonal trader, the work does not specifically discuss the incorporation of compositonal techniques into the OMG trader. Work in [Seni96] incorporates a limited hardwired composition algorithm into trading to deal with service evolution. A mapping operator buffers the client of a service from changes to the service interface. If a client requests an "old" service interface that is no longer available, the trader composes an instance of a new service interface with a specialized mapping object to collectively simulate the old service interface for the client.  This approach does not work for arbitrary forms of service evolution, and past work in database schema evolution points to the evolution patterns that can be hidden by this approach. Other standards work [Slum97, AVSS97] talks about the need to incorporate composition into trading, but makes no specific proposals.Mobile ubiquitous computing work from UC Berkeley [Hode97] uses a trader-based architecture, with the trader implemented using IETF's service location protocol proposal [SLP97]. It discusses the use of a compositional trader to dynamically reconcile the interface of available mobile services with the interface applets that are available on a mobile client. As explored extensively in Smalltalk's model-view-controller paradigm, gui elements may be developed independently of back-end services, therefore leading to reconcilable differences between the interface required by the GUI element and that provided by a nearly matching backend service. [Hode97] suggests that the controller that reconciles available viewers with available model providers can be trader for, or even generated at runtime.
• Proposals for Compositional Primitives: Both Cardelli [Card97] and Kistler [Kist97] propose a scripting language with service combinator language primitives that allow you to overlay an added requirement (e.g a QoS requirement, or a concurrency requirement that two GETs happen simultaneously) on an HTTP GET or a CGI invocation.  Some of these primitives are useful in a richer service request notation than is currently supported by OMG (or the compositional) trader. The trader is then a component of the run-time system that fulfills the combinators of Cardelli's language. Other work in [Matz97] discusses configuration, composition and placement issues for interface reconcilers, which are one category of composers that the compositional trader deals with.
• QoS examples of service composition:  Multimedia systems provide severl useful examples of diverse tool compositions and compositional techniques, each of which is provides different qualities of deliverred service, and different gurantees.   Work in [Cowa95] uses software feedbaclk loops to stabilize a particular property of a connection. The same idea can be used by a compositional trader to provide greater gurantees about some property of a connection.  Work in [Chat97a,Chat97b] and the application gateway work in [Amir96] provide other examples of service composition in multimedia applications.
• Service composition on the web: Digestor [Bick97], Pythia [Fox96] and Zippers[Brow96] provide three different examples of document reorganization  that are tuned to the end user. In trading terms, all three system compose the core function of web document retrieval (an HTTP GET) with document reorganization composers of different sorts (in all cases organized as specialized containers supporting a particular container-specific intermediate format and blade API) to overlay a client-requested property that was not previously present. The zippers work uses fairly simple tree-based outlining, Pythia a more versatile set of document distillation blades. Digestor provides the most interesting and semantically rich set of document re-authoring techniques.
• Other Relevant Work: [Klei95] talks about nomadic routers that perform proxy-like distillation, except at the packet level (see Active_Net_Survey_ieeecomms97.ps). Qualitative process theory [Forb93] - a composer's model is similar to a qualititative process.

References

• [Amir96] Amir,E., McCanne, S. and Zhang,H., "An Application Level Video Gateway"
• [AVSS97] "Control and Management of Audio/Video Stream, Revised Submission", telecom/97-05-07, see www.omg.org
• [Bick97] Timothy W. Bickmore and Bill N. Schilit,  Digestor: Device-Independent Access To The World Wide Web.  Proceedings for the Sixth International World Wide Web Conference, 1997, pp. 655-663.
• Adrian Friday, Gordon Blair, Keith Cheverst and Nigel Davies , Extensions to ANSAware for Advanced Mobile Applications, Proc. of 1st. Int. Conference on Distributed Platforms, Dresden, Germany, 27 February-1 March 1996.
• [Brow96] Brown, M., "Zippers: A Focus+Context Display of Web Pages", DEC SRC Research Report #140, 1996.
• [Card97] Cardelli,L. and Davies,R., "Service Combinators in Web Computing", DEC-SRC Research Report #148, 1997.
• [Chat97a] Chatterjee,S. et al., "Taxonomy of QoS Specifications", Proceedings of WORDS '97.
• [Chat97b] Chatterjee,S. et al., "Modeling Applications for Adaptive QoS-based Resource Management", Proceeedings of the 2nd IEEE High Assurance Systems Engineering Workshop, 1997.
• [Cowa95] Cowan,C. et al., "Adaptive Methods for Distributed Video Presentation", ACM Computing Surveys, Special Issues on Multimedia Systems - Symposium on Multimedia, 27(4):580-583, Dec. 1995.
• [Fox96] Fox,A. and Brewer,E., "Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation", Fifth International WWW Conference, 1996.
• [Fox] Fox,A. et al., "Adapting to Network and Client Variability via On-Demand Dynamic Distillation"
• [Frol98] Frolund,S. and  Koistinen, J., "QML: A Language for Quality of Service Specification", HP Labs Technical Report HPL-98-10, 1998.
• [Kist97] Kistler, T. and Marais, H., "WebL - a programming language for the Web".
• [Klei95] Kleinrock, L., Keynote Address on Nomadic Computing, Intl. Conference on Mobile Computing and Networking, 1995.
• [Matz97] Matzel, K.U et al., "Dynamic Component Adaptation",  Ubilab Technical Report 97-6-1.
• [Yead96] "QoS Filters: Addressing the Heterogeneity Gap", Proceedings of Interactive Multimedia Systems and Services, 1996.
• [Inou97] Inouye,J., Pu,C. et al., "System Support for Mobile Multimedia Applications", NOSSDAV'97,pp.143-154, 1997.
• [Hode97] Hodes,T.D, Katz,R. et al., "Composable Ad Hoc Mobile Services for Universal Interaction", UC Berkeley BMRC Technical Report.
• [Heterodyne]
• [Forb93] Forbus,K. and DeKleer,J., "Building Problem Solvers", MIT Press, 1993.
• [Ocke95] Ockerbloom,J., "Exploiting Structured Data in Wide-Area Information Systems"
• [Popi96] Popien,C. and Thissen,D., "Integrating QoS Restrictions into the Process of Service Selection", IWQoS '97.
• [Seni96] Senigvonse,T.  and Utting,I., "A model for evolution of services in distributed systems",  Proceedings of the IFIP/IEEE International Conference on Distributed Platforms: Client/Server and Beyond: DCE, CORBA, ODP and Advanced  Distributed Applications, pp. 373-85, 1996.
• [SLP97] "IETF - Service Location Protocol Proposal", IETF Network Working Group, RFC2165, ftp://ds.internic.net/rfc/rfc2165.txtJune 1997
• [Slum97] Sluman,C. et al., "Quality of Service, OMG Green paper", OMG Working draft, March 1997 (see www.omg.org)
• [Venu98] Vasudevan,V., A Reference Model for Trader-Based Distributed Systems Architectures , OBJS Technical Report.
• [Ye96]   T.Ye "Real Time Traffic Reporting Application with Text-to-speech Transcoding In  the Proxy" ,  UC Berkeley Project Report