Supporting Multimedia Service Polymorphism in Dynamic and Heterogeneous Environments Dongyan Xu, Klara Nahrstedt Department of Computer Science University of Illinois at Urbana-Champaign Urbana, IL 61801 d-xu, klara @cs.uiuc.edu Phone: (217)244-6624, Fax: (217)244-6869 Abstract Future multimedia services are expected to be available anytime, anywhere, and by using any computing device. However, clients of a multimedia service may vary significantly in their processing capability and network connectivity. In addition, even between the same multimedia service provider and client, there may be dynamic variation in end-to-end resource availability. In such a dynamic and heterogeneous environment, the challenge in multimedia service is to provide each client with satisfactory Quality of Service (QoS), under the constraint of current end-to-end resource availability. Many existing QoS adaptation techniques are very service-specific, and targets only specific types of critical resources. In this paper, we present , an enabling framework for multimedia service provision in dynam- ic and heterogeneous environments. Instead of providing a specific technique, provides uniform programming interface, architecture, and runtime support that integrate and dynamically select from var- ious service-specific QoS techniques. The key idea behind is QoS and resource-aware service polymorphism: the same multimedia service can be delivered in multiple forms, called service configura- tions. Each service configuration consists of a different set of service components, which are suitable for service delivery under a certain resource condition. At runtime, dynamically selects an appro- priate service configuration for each service request, based on the current end-to-end resource availability. The selected service configuration then delivers the service with customized and satisfactory QoS to the requesting client. We have implemented a prototype of framework, and validated it by building an example Video Streaming (VS) service on top of it. Our experimental results show the soundness of . This work was supported by the National Science Foundation under contract number 9870736, the Air Force Grant under contract number F30602-97-2-0121, and National Science Foundation Career Grant under contract number NSF CCR 96-23867. Submitted for publication. 1 1 Introduction Future multimedia services are expected to be available anytime, anywhere, and by using any computing device. Services such as News-on-Demand, digital libraries, on-line shopping malls, and remote camera surveillance and tracking, are becoming more ubiquitous. This has been made possible by the rapid deploy- ment of the Internet infrastructure, as well as the emergence of non-traditional computing devices. Network access is becoming more like a power supply - it is available for a computing device's plug-in whenever and wherever needed. Imagine, a user will be able to access the same multimedia service through an HDTV appliance at home using cable or xDSL connection, through a desktop workstation connected by a high speed LAN at work, via a laptop PC or cellular phone with wireless or wireline connections on a business trip, or via a PDA during a vacation tour. One major challenge in the above scenario is to provide a flexible multimedia service enabling system in a highly heterogeneous and dynamic environment. The heterogeneity in clients' processing capability and network connectivity is only one aspect of the problem. The other aspect is the dynamic variations of end- to-end resource availability, even between the same multimedia client and service provider. For example, the end-to-end network bandwidth may fluctuate, and the load of a multimedia service provider may change over time. In such a dynamic and heterogeneous environment, the goal of multimedia service provision is to provide clients with customized and satisfactory QoS, under the constraint of current end-to-end resource availability observed by each client. There have been numerous individual solutions to the problem of QoS adaptation for different multimedia services. For example, for media content distribution services, we have adaptive delivery of media data [1], media data prefetching [27], smoothing [6], and transcoding [2]; for visual tracking services, there is the trade-off between tracking precision of moving object and number of objects being tracked [14]. However, these techniques are data and service specific, and they focus only on specific types of critical resources - for example, some on network bandwidth, and some on CPU. In this paper, we present , an enabling framework for multimedia service provision in dy- namic and heterogeneous environments. Different from the individual solutions above, it provides unifor- m programming interface, architecture, and runtime support that integrates and selectively leverages the service-specific QoS techniques. The programming interface and runtime support are applicable to different types of multimedia services which need QoS customization and adaptation. The key idea behind is the QoS and resource-aware service polymorphism. Under , a multimedia service can be delivered in multiple forms, called service configurations. Each service con- figuration consists of a different set of service components, which is suitable for service delivery under a certain resource condition - the service components involved employ certain QoS techniques to deal with this resource condition. At runtime, will dynamically select an appropriate service configuration 2 for each service request. The selection is made by comparing the end-to-end resource requirement of each service configuration, with the end-to-end resource availability observed by the client. Service polymorphis- m realizes the mapping from a logical multimedia service to a customized service delivery with satisfactory QoS, for each individual service request. Via 's programming interface, developer or administra- tor of a multimedia service is able to specify the candidate service configurations, as well as their applicable end-to-end resource conditions. The major contributions of include: (1) it deals with clients' heterogeneity and dynamic end- to-end resource variation in a generic and systematic manner, providing both developer interface and runtime support; (2) it enables the selective application of existing service-specific QoS adaptation techniques with- out end-user's manual and maybe ad hoc selection at runtime; (3) it integrates the operations of multimedia service configuration selection and service discovery. The decisions on service configuration and service discovery are both resource-driven; (4) it introduces a new paradigm of component-based programming for QoS: a multimedia service developer not only programs for the functionalities of service components, but also specifies the corresponding `knowledge' on how to select and organize these service components to achieve customized and satisfactory QoS. We have implemented a prototype of called , as a CORBA-enabled middleware. is part of - a component-based distributed operating system for the new Millennium [22]. We have also implemented a proof-of-concept multimedia service on top of . enables customized delivery of the example service to a wide range of clients including desktop, laptop, and palmtop computers, under different end-to-end resource availability conditions. In addition, our experiments also show high overall success rate of all service requests. The rest of the paper is organized as follows. Section 2 introduces the concept of service polymorphism. Section 3 describes programming interface for service polymorphism specification. Section 4 presents the architecture of runtime support. Section 5 presents the mechanism of runtime support - a resource-aware service configuration selection protocol. Section 6 gives a detailed example of building a multimedia service using . Section 7 presents experimental results obtained from the middleware prototype and from the example multimedia service on top of it. Section 8 discusses related work. Finally, Section 9 concludes this paper. 2 Service Polymorphism: Concept and Framework 2.1 The Basic Concept In a highly dynamic and heterogeneous environment (Figure 1), multimedia services are deployed in wide-area networks, and are accessible to any networked client. The services range from media content distribution (live or stored), to media data processing, querying, and storage. We call a host providing 3 a multimedia service a multimedia service provider. Some service providers store or generate their own media data source, such as a video server or a camera server, while some service providers accept and process media data from others, such as a media gateway. Clients of multimedia services may include desktop and mobile computers, light-weight PDAs, and computerized electronic appliances. They connect to the network from different network access points via various types of connections, such as LAN, cable, xDSL, dial-up, or wireless connections. Multimedia Clients Media Gateway Multimedia Service Provider Multimedia Clients Multimedia Clients Figure 1: Multimedia Service in a Heterogeneous Environment Meanwhile, with the wide acceptance of distributed object programming techniques such as CORBA and DCOM, it is now possible to implement a multimedia service as the composition of multimedia service components, rather than as a monolithic program. A service component is a functional unit participating in one or more services, and multiple service components work collaboratively to deliver a service. More importantly, the same type of service may be delivered by different combinations of service components. This is what we call service polymorphism: one multimedia service is associated with multiple delivery forms called service configurations. Each service configuration consists of a set of service components at the service provider, at the client, and if needed, at some auxiliary service provider(s), so that it delivers the service with customized and satisfactory quality under certain end-to-end resource constraints. For example, service polymorphism for a Video Streaming service may involve three candidate service configurations , and , as shown in Figure 2. The Video Streaming server has a service compo- nent MpegSender (MS), which retrieves and transmits the MPEG videos stored in the server; the media gateway has two service components MpegH261Transcoder (MHT) and MpegBitmapTranscoder (MBT), which transcode MPEG frames to H261 frames and to Bitmap frames, respectively; and the Video Stream- ing clients have one or more of service components MpegPlayer (MP), H261Player (HP), and BitmapPlayer (BP). Among the three service configurations, performs end-to-end adaptive MPEG video streaming; is suitable for clients connected via a low bandwidth network, because MpegH261Transcoder is employed to `scale down' the high-bit-rate MPEG stream; is designed for clients with very limited CPU, memory, or battery power, and MpegBitmapTranscoder is used to perform the CPU and power-consuming task of video decoding on behalf of the client. 4 Video Streaming server media gateway Video Streaming clients MS MHT MBT MP HP BP MP BP Service configurations: C1: MS MP C2: MS MHT HP C3: MS MBT BP Figure 2: An Example of Multimedia Service Polymorphism We want to point out that the techniques of adaptive streaming and transcoding in , and are not new. They are only examples of QoS adaptation techniques which can be dynamically selected for individual service requests under service polymorphism. 2.2 The Framework Polymorphism Service Polymorphism in Programming Languages Programming Relevant syntax and semantics Service polymorphism specification Interface (e.g. virtual function, polymorphic type) (e.g. candidate service configurations) Method invocation Service request Runtime Runtime type checking Runtime end-to-end resource checking Support Dynamic binding Dynamic service configuration selection Instantiation of selected Execution of selected method service configuration (service discovery and launching) Figure 3: The Analogy: Service Polymorphism and Polymorphism in Programming Languages The novelty of our work is a systematic framework of service polymorphism, called . The framework consists of three major parts: (1) the component-based application-level service mod- el, (2) the developer's programming interface for service polymorphism specification, and (3) the runtime support architecture and mechanism for service polymorphism. This is analogous to the support for poly- morphism in programming languages, as shown in Figure 3. Under ServiPoly runtime support, for each service request, a suitable service configuration will be selected, based on an end-to-end (from the request- ing client to the service provider) resource checking. The selected service configuration is then instantiated by discovering and launching every service component involved. 5 3 Programming Interface We first describe the programming interface for service developers. Our framework prototype provides both a GUI interface and a script language interface. A developer or administrator uses the interface to create a service-specific service polymorphism specification. Figure 4 shows an example of service polymorphism specification for a video streaming service, using the GUI interface. An example of using the script language interface will be shown in Section 7.1. CL (Candidate Service Configuration List): C1 C C C C 2 3 DGs (Dependency Graphs): Q-R Translators: Q-R Translator for C C 1 MS 1 00101010011010010101101 MP (local) 11101010000011010101111 MpegSender MpegPlayer C C C MS Q-R Translator for C C C 2 2 MHT HP (local) 10111001001101001010110 10011010101010010101101 MpegSender MpegH261Transcoder H261Player (unresolved) Q-R Translator for C C MS 3 3 BP MBT 11010010111010010101101 (local) 11001010011010010101101 MpegSender MpegBitmapTranscoder BitmapPlayer (unresolved) Figure 4: Example Service Polymorphism Specification 3.1 Service Polymorphism Specification: CL and DGs CL is a list of candidate service configurations for this service. Each candidate service configuration in CL is further represented by a Dependency Graph (DG). Nodes of a DG represent service components involved in this service configuration. Edges of the DG represent media data dependencies between the service components. Locations of some service components may not be known at the time of specification. We mark them as unresolved service components, which will be dynamically discovered at runtime. Candidate service configurations in a CL are arranged in such an order that: the lower the index in the CL, the higher the service quality it generally provides. This order can be subjective and fuzzy, because there may not be an objective criteria to determine which service configuration generally provides `better' quality. The developer/administrator of a multimedia service specifies a default order based on users' general preference. This order may be dynamically changed at runtime according to the preference of a specific user. 6 3.2 Service Polymorphism Specification: Q-R Translators For each DG of a candidate service configuration, the developer also provides a Q-R Translator. Q- R Translators are plug-in functions (as shown in Figure 4), to be called by runtime support entities. A Q-R Translator dynamically computes the end-to-end resource requirement for the corresponding service configuration. The end-to-end resources may involve: (1) local resources of a host where a service component will run (i.e. the service provider, the client, or the auxiliary service provider(s) - if involved), such as CPU, buffer space, local network bandwidth1, display area, and battery power; and (2) end-to-end network bandwidth between the hosts. defines a uniform interface for Q-R Translators to be pluggin-able: The input of a Q-R Trans- lator is the descriptor of a service request. The output of the Q-R Translator is an end-to-end resource requirement vector. Each element of the vector is a resource type, required amount pair. The resource type is specific to each node in the corresponding DG. An example resource requirement vector for the DG of in Figure 4 can be: 2 , , and represent the outbound local network bandwidth of MS, inbound local bandwidth of MP, and end-to-end bandwidth from MS to MP, respectively. When a Q-R Translator computes a resource requirement vector, its target end-to-end QoS is the mini- mum acceptable end-to-end QoS delivered by this service configuration. The service developer defines the minimum acceptable QoS internally in the Q-R Translator. Therefore at runtime, for a service request, the computed resource requirement vector sets the `low-water-mark' of resource availability acceptable to this service configuration. During the service session, the selected service configuration will remain in opera- tion, as long as the actual resource availability does not fall below the low-water-mark. Here, we make the assumption that a service configuration is able to achieve a certain range of QoS, within a certain range of resource availability. This assumption is well-supported by today's multimedia service components, which are implemented by using certain QoS adaptation techniques. Each Q-R Translator can be implemented as follows: first, it maps the service request descriptor to a set of media data sources ... involved in this service request. Then it derives QoS parameters from each media data source 3; sets the minimum acceptable end-to-end QoS for this request; and computes and returns the end-to-end resource requirement vector. 1We define the local network bandwidth as the bandwidth between the host and the edge of its domain - for example, the edge router of an intranet, or the base station of a cellular network. 2The CPU percentages are all relative (approximately) to the capacity of a reference CPU, for example, a 200MHz UltraSPARC CPU. 3Example QoS parameters include the length, frame rate, and avg/max/min frame size of a video file. 7 4 Runtime Support Architecture After describing the programming interface, we present the runtime support, which will answer the following questions: where will the service polymorphism specification be stored? and how will it be accessed and enforced? The runtime architecture, shown in Figure 5, consists of the following entities: service components, Proxies (SP-Proxies), Resource Monitors (RMs). service client service components service provider ... service components ....... .... ...... ............ service polymorphism SP-Proxy specification ....... .... ...... ............ SP-Proxy RM ... RM RM RM ... RM RM service query / response service advertisement DS DS service advertisement / query exchange service advertisement / DS query exchange service discovery system in wide-area networks Figure 5: Runtime Support Architecture Proxies (SP-Proxies): Proxies are key entities in architecture. There is an SP-Proxy controlling the service components on each host. It maintains information about the local service components. Furthermore, the service polymorphism specification will be stored in the SP-Proxy of the corresponding service provider. For each service request, the SP-Proxies check the end-to-end resource condition, select an appropriate service configuration, and start the service components involved. Resource Monitors (RMs): One or more RMs run below the SP-Proxy on each host. RMs are re- sponsible for monitoring and reporting resource availability information to the SP-Proxy during the end-to-end resource checking. In addition, the SP-Proxies communicate with a service discovery system to discover service providers whose locations are not known at the time of service request. Service discovery is especially useful in environments with mobile clients and replicated service providers. The wide-area network is divided into different domains, and the service discovery system is a set of Discovery Servers (DS) in the domains. To discover a service, the SP-Proxy of a host submits a service query to its home DS - the DS in the same domain. To advertise a service, the SP-Proxy of a service provider periodically sends out service 8 advertisements to its home DS. The DSes may exchange service queries and/or service advertisements between each other, in order to perform inter-domain service discovery. The following subsections describe the entities and their interactions in greater detail. 4.1 SP-Proxy Each SP-Proxy maintains a Service Component Table, as shown in Figure 6. The table records informa- tion about each service component on the host - for example, the name and interface of a service component, and names of critical resources required by this service component. client service components ... Service Component Table SP-Proxy RM ... RM RM SP-Proxy of a client service provider service components service polymorphism spec. Service Component Table CL: SPS SP-Proxy DGs: Q-R Translators: RM ... RM RM SP-Proxy of a service provider SPS: service polymorphism specification Figure 6: Inside a SP-Proxy The service polymorphism specification is stored in the SP-Proxy of the corresponding service provider. At runtime, the SP-Proxy will use the service polymorphism specification to make service configuration selections. In particular, it will call the Q-R Translators (Section 3.2) to perform end-to-end resource check- ing. The reasons why we place service polymorphism specification on the service provider side include: (1) the service developer/administrator is more likely to have the incentive and domain knowledge to accommo- date heterogeneous clients; (2) on the other hand, clients may wish to be simple and free from complicated (and sometimes manual) service management tasks, and it is generally difficult to predict what services a client will request. Reason (2) is especially true for the emerging mobile clients, and clients embedded in electronic appliances with limited capability. Therefore, assumes that the SP-Proxy of a client is less `knowledgeable' about service polymorphism than the SP-Proxy of a service provider. 4.2 Resource Monitor (RM) To perform end-to-end resource checking, the resource availability condition must be visible to SP- Proxies. We therefore introduce Resource Monitors (RMs). The minimum function of a RM is to monitor 9 the availability of one or more of these resources, and report it to the local SP-Proxy4. Besides the minimum functions, a RM may also be enhanced to perform resource reservation and scheduling. This is desirable for the provision of more guaranteed service quality. However, a lightweight RM with the minimum functions may be more suitable for simple or dedicated devices, such as PDAs and computerized home appliances. Our earlier work of QualMan[16] provides the design and implementation of RMs for CPU, memory, and local network bandwidth. RM for disk I/O bandwidth is proposed in [20] by Shenoy et al. RM for end-to-end bandwidth can also be implemented by leveraging the emerging network measurement services [9, 15, 21]. We have also implemented more lightweight RMs - for example, a RM for battery power which reports the remaining battery level of a laptop PC; a mini RM for palmtop computers which simply reports a static resource availability `signature' of very limited CPU, memory, and battery power. 4.3 Service Discovery System A dynamic service discovery system is needed by . Specifically, the need for service discovery arises when (1) a client wishes to request a multimedia service, but does not know where the service provider is; and (2) a service configuration is selected, but one of its service components, which runs on some auxiliary service provider, is still unresolved. The Discovery Server (DS) in each domain is the key entity of the service discovery system5. Several service discovery systems have been proposed, such as the Service Location Protocol (SLP) [11] and the Service Discovery Service (SDS) [5]. To make more generic, we do not assume a specific service discovery system. In , we only make the following common and minimum assumptions about the service discovery system: (1) the SP-Proxy of a service provider sends service advertisements only to its home DS; (2) the SP-Proxy of a querying host sends the service query to its home DS; and (3) the DS which originally accepts a service query is also responsible for gathering discovery results from other DSes, and selecting one to return to the querying host. In addition, we enhance the service discovery system with resource-awareness (detail described in the Appendix), so that it tries to identify a service provider which is likely to have sufficient resources to ful- fill the service request. The enhancement is independent of the service query processing and forwarding techniques used in a specific service discovery system. Therefore, it is possible to integrate this resource- awareness enhancement into an existing service discovery system. The address of a host's home DS may be obtained via the DNS system: we propose a new Resource Record (RR) type DS in the DNS system. A DNS lookup for a host with the new RR type will return the 4For a resource whose availability tends to fluctuate, the RM decouples the processes of measurement and reporting, and reports the availability in a conservative manner: it maintains the measurements obtained during the past units of time; while it reports the lowest average value of any consecutive measurements. 5Since domain partitions can be hierarchical, the DSes may be organized in a hierarchy. The Berkeley Service Discovery Service (SDS) [5] assumes such a hierarchy. 10 address of host 's home DS. This is similar to other RR types such as MX, which returns the address of host 's mail exchanger. 5 Runtime Support Mechanism - REACTS Protocol With the architecture, we present 's runtime support mechanism. Specifically, this is performed by REACTS - a REsource-Aware service ConfiguraTion Selection protocol. As indicated by its name, decisions and actions in REACTS are driven by the availability and requirement of end-to-end resources. In the following subsections, we first describe a typical execution of REACTS protocol. We then discuss some key design issues of REACTS. 5.1 Typical Execution of REACTS Client SP-Proxy - service request: The SP-Proxy of a client intercepts a multimedia service request (step 1 in Figure 7). If the location of the service provider is unknown, the SP-Proxy will query the service discovery system for the requested service (step 2 in Figure 7). There may be more than one qualified service provider which provides this service. The service discovery system will choose one of them which is likely to have sufficient resources to fulfill the service request, due to our resource-awareness enhancement. discovered auxiliary service provider service components ... 9 SPS: service polymorphism specification service client SP-Proxy service components 8 service provider RM ... RM ... RM 1 service components 9 9 8 SP-Proxy 3 3 SPS 6 3 ........ ...... SP-Proxy RM ... RM 4 RM 2 5 5 5 RM ... RM RM 7 DS DS DS Figure 7: Typical Execution of REACTS The client's SP-Proxy then collects resource availability information from its local RMs (step 3 in Figure 7). The collected information is represented as a client-side resource availability vector - each element is a resource type, available amount pair. Next, the client's SP-Proxy contacts the SP-Proxy of the service provider (step 4 in Figure 7), with the following information: (1) descriptor of the service request; 11 (2) ; and (3) name(s) of local service component(s) that may be used to receive the service - for example, various media players. Service provider SP-Proxy - service configuration selection: The SP-Proxy of the service provider receives the service request. Like its client-side counterpart, it collects server-side resource availability information from its local RMs, and generates a server-side resource availability vector (step 5 in Figure 7). is then combined with to form - the resource availability information from both sides. Using its service polymorphism specification, the SP-Proxy selects an appropriate service configuration for this service request in the following manner (step 6 in Figure 7): starting from the head of CL, for each candidate service configuration , the SP-Proxy calls - the Q-R Translator of : (1) The result is the end-to-end resource requirement vector of for the service request . If (2) then will be selected as the suitable service configuration for this service request. Otherwise, the procedure is repeated for the next candidate service configuration in CL... Here, the relation represents a weak `greater than' relation: for each type of resource in both and , the amount in is greater than the amount in . All SP-Proxies involved - service instantiation: The service will be instantiated according to the select- ed service configuration. However, it may be possible that a service component in the service configuration is unresolved - the service component runs on some auxiliary service provider (for example, a media gate- way) whose location is unknown. In this case, the service component will be resolved by querying the service discovery system (step 7 in Figure 7). Again, our resource-awareness enhancement to the service discovery system increases the possibility that the discovered auxiliary service provider, on which the ser- vice component runs, will have sufficient resources for this service session. After each service component in the selected service configuration has been resolved, the SP-Proxy of the service provider will notify the SP-Proxies involved in this service configuration (step 8 in Figure 7), with the following information: (1) the DG and of the selected service configuration; and (2) the location of each service component in the DG. Finally, each SP-Proxy will start its local service component(s) in the selected service configuration (step 9 in Figure 7). The multimedia service session begins. 5.2 Key Design Issues in REACTS 5.2.1 Partial Resource Checking In step 6 of the REACTS execution, we notice that by definition of the ' ' relation, the SP-Proxy of the service provider only performs a partial resource checking when making the service configuration selection. 12 Resource availability on the auxiliary service provider, if involved in a service configuration, is not checked. For an individual service request, this partial resource checking may provide less QoS assurance than a complete resource checking. However, we take the partial resource checking approach for the following reasons: (1) the collection of availability information of every resource introduces extra latency and overhead to each service session; (2) in many cases, the resource availability information from the service provider and from the client is already sufficient to uniquely identify a service configuration; (3) although service configuration selections may not be 100 successful, we do try to improve the overall success rate of service sessions. In , this is achieved by the resource-awareness enhancement to the service discovery system. In summary, we introduce two basic techniques in the resource-awareness enhancement. First, we use discovery result caching to lower the service discovery latency. A DS will cache the service advertisements returned by other DSes for a query, so that future queries from the same domain for the same service can be resolved locally by the DS. Second, we associate each cached service advertisement with `customer feedbacks' about the resource supply/demand condition at the corresponding service provider. The feedback is in the form of a resource Availability/Requirement Index (ARI) generated during each service session. When the session completes, the ARI value will be sent to the caching DS together with the session's exit status (success or failure). Later, when a host in the same domain queries the same service (occur at step 2 or 7 in REACTS), the DS will identify a qualified service provider based on the cached service advertisements as well as on the average ARI values associated with them. Therefore, with our resource- awareness enhancement, a resource in a selected service configuration is checked either when REACTS makes a service configuration decision (step 6 in Section 5.1), or when REACTS performs resource-aware service discovery - although in the latter case it may be more approximate. Details of the resource-awareness enhancement and its integration into our framework will be given in the Appendix. 5.2.2 Special Service Configurations In REACTS, besides normal service configurations, we also introduce two special types of service config- urations: dynamic service creation and service re-direction. The selection of these special service configu- rations are also resource-driven. Dynamic service creation: this special service configuration will lead to the dynamic creation of a new service. A new service can be created on a host that supports dynamic service hosting. In service poly- morphism specification, a dynamic service creation is represented by a DG with a thick dashed edge, which indicates the issuing of a service creation request (Figure 8, left). The service hosting server node in the DG may not be resolved (and need be discovered). Upon receiving a service creation re- quest, the SP-Proxy of the service hosting server will install: (1) service polymorphism specification; 13 and (2) service component(s) of the new service6. Then, it will send service advertisements for the new service to the service discovery system, so that clients may begin to request this new service. * self ServiceHostingServer self AnotherServiceProvider (new-service-name) (service-name) DG for service re-direction DG for dynamic service creation (with `create-if-not-found' option '*') Figure 8: DGs for dynamic service creation and service re-direction Service re-direction: this special service configuration will trigger the SP-Proxy of a service provider to forward a service request to another service provider - for example, a mirror server or a proxy server. The SP-Proxy of the destination service provider will then execute REACTS for this service request. In service polymorphism specification, a service re-direction is represented by a DG with a thick dotted edge, which indicates the forwarding of the service request (Figure 8, right). The destination service provider node in the DG may not be resolved (and need to be discovered). Furthermore, if the destination service provider can not be found, we define a `create-if-not-found' option of creating the service, similar to the dynamic service creation. In the DG, this option is indicated by a '*' on the dotted edge. Dynamic service creation and service re-direction are common and powerful mechanisms for multimedia service provision in a dynamic environment. This will be illustrated by the example in Section 6. 5.2.3 Service Query Submission In step 7 of the REACTS execution, the service query for an auxiliary service provider may be submitted either by the client or by the main service provider (it is the latter in Figure 7). This is decided by its expected proximity to the main service provider or to the client. For example, to discover a video cache auxiliary service, which is expected to be near the client, the query should be submitted by the SP-Proxy of the client; however, to discover an MPEG-to-H261 transcoding auxiliary service, which is expected to be near the MPEG video server, the query should be submitted by the SP-Proxy of the video server. To specify this proximity preference, the service developer/administrator can add a proximity preference tag to each unresolved service component node in a DG. The tag specifies: this service component is expected to be located near host/service component . We also introduce a scoped service query. A scoped query is used to discover a service provider within a certain scope, preventing a global search. Each DS defines its own scope. For example, a DS may specify 6(1) and (2) may be obtained in two ways: they can be pre-installed in the hosting server, and get activated upon the service creation request; or, in an active environment, they can be dynamically downloaded from the initiating service provider. 14 its scope as the domains belonging to the same parent domain. 6 An Example Using To illustrate the effectiveness of , we present an example of building a multimedia service using . First, we describe the multimedia service itself, then we describe how to deploy and deliver the service with the support of . 6.1 A Video Streaming (VS) Service The example multimedia service is a Video Streaming (VS) service. It extends our earlier example in Figure 2 of Section 2. The VS server maintains a library of MPEG movies. Different clients request the VS service. The VS clients range from high-end desktop computers to light-weight palmtop devices. Their network connections range from high-speed wired or wireless LANs to low-speed links such as CDPD and dial-up phone line. First, we deal with heterogeneity in the capability and network connection of VS clients. Three candidate service configurations , and are already described in Section 2. performs normal end-to-end MPEG video streaming; is suitable for clients connected by a low bandwidth network; is designed for clients with very limited CPU, memory, or battery power. Second, we deal with dynamic load variation of the VS server. Although the VS service components leverage QoS adaptation techniques such as dynamic frame dropping and buffering, the capacity of the VS server is still limited. In order to make the VS service more scalable with respect to the number of VS clients, we adopt a dynamic service replication technique. The basic idea is the following: when resource availability of the VS server falls below a threshold, the VS service will be dynamically replicated on some proxy servers. Each of them will serve a subset of the VS clients, alleviating the load of the original VS server. A replicated VS server may not keep the complete library of MPEG movies as on the original VS server. It uses its own caching and replacement policy to dynamically decide which movie to cache. 6.2 Service Polymorphism Specification and Deployment (Off-Line) We now describe how the VS service is deployed using . Note that the deployment is an off-line activity before the VS service is ready to deliver. For a VS client, the user installs one or more of the client-side service components: MpegPlayer, H261Player, and BitmapPlayer. During the installation, the service components are registered in the Service Component Table maintained by the client's SP-Proxy. For a media gateway that has either MpegH261Transcoder or MpegBitmapTranscoder, the service com- ponent is also registered in the Service Component Table maintained by the gateway's SP-Proxy. 15 For the VS server, its service component MpegSender is registered in the Service Component Table of the server's SP-Proxy. Next step is for the service developer or administrator to provide the VS service polymorphism specifica- tion to the server's SP-Proxy. We have four candidate service configurations for the VS service. Besides , and described earlier, we add a special service configuration to support dynamic service replication. is a service re-direction with the `create-if-not-found' option. When the local resource availability of the VS server falls below a certain threshold, will be selected for each incoming VS service request. Under , the request will be re-directed to a replicated VS server near the client, whose location will be discovered by submitting a scoped query to the service discovery system. However, no replicated VS server exists initially. In that case, a new replicated VS service will be created upon the selection of , according its `create-if-not-found' option. CL (Candidate Service Configuration List): 1 C' C C2 C' C' C' C C C' C' 3 4 5 6 DGs (' near client/server ' is the proximity preference tag): CL (Candidate Service Configuration List): C0 C1 C C C2 C3 1 C' MPS MP (local) MpegProxySender MpegPlayer DGs ('near client/MS' is the proximity preference tag): MPS (local) MHT HP C'2 MpegProxySenderMpegH261Transcoder H261Player C * 0 (unresolved, near MPS) self VS (unresolved, near client) BP 3 C' MPS MBT (local) MS C MpegProxySender MpegBitmapTranscoder BitmapPlayer 1 MP (local) (unresolved, near MPS) MpegSender MpegPlayer MPS MS MP C C C' (local) 4 MpegSender MpegProxySender MpegPlayer C C C MS (location of the VS server) 2 MHT HP (local) MpegSender MpegH261Transcoder H261Player MPS (unresolved, near MS) MS C C C' MHT HP (local) 5 MpegSender MpegProxySender MpegH261Transcoder H261Player (location of the VS server) (unresolved, near MPS) C MS 3 BP MBT (local) C C C' MPS MpegSender MpegBitmapTranscoder BitmapPlayer 6 MS (local) MBT BP (unresolved, near MS) MpegSender MpegProxySender MpegBitmapTranscoder BitmapPlayer (location of the VS server) (unresolved, near MPS) (a) CL and DGs for the VS Server (b) CL and DGs for a Replicated VS Server Figure 9: CLs and DGs for the VS Server and for a Replicated VS Server The CL and DGs for are shown in Figure 9(a). Notice that is the at the head of the CL. This means that when a VS request arrives, the SP-Proxy of the VS server will first check if a service re-direction is necessary, i.e. if its local resource availability is already below the threshold (threshold values are set 16 in 's Q-R Translator). The corresponding Q-R Translators for are also provided by the service developer. For a replicated VS server, it has a service component MpegProxySender (MPS). There are six candidate service configurations , as shown in Figure 9(b). are for the case of `cache hit' - i.e. the requested movie is on the replicated VS server. and handle heterogeneity in clients' capability and network connection, similar to and for the VS server. are for the case of `cache miss' - i.e. the requested movie is not on the replicated VS server. In this case, the original VS server also has to get involved. MpegProxySender acts as a relay between the original VS server and the client. Meanwhile, based on its caching and replacement policy, MpegProxySender may choose to cache the requested movie. Again, and are provided to handle heterogeneity in clients' capability and network connection. 6.3 Service Delivery (On-Line) After the VS service has been deployed, different clients can now receive customized VS service delivered by different service configurations. This is enabled by the runtime support. Initially, the SP-Proxy of the VS server sends VS service advertisements to the service discovery system. For each VS service request, the REACTS protocol is executed. At first, since the resources of the VS server are sufficient, will not be selected. , or will be selected for each request by the SP-Proxy of the VS server. For ( ), a media gateway with MpegH261Transcoder (MpegBitmapTranscoder) component has to be discovered. If there are multiple qualified media gateways, the resource-aware service discovery system (Section 5.2.1) will dynamically pick one which is likely to have sufficient resources for this service session. With the increase of VS server load, the resource availability of the VS server will fall below the threshold set for . Now, for each VS service request, will be selected, and the request will be re-directed to a replicated VS server close to the client. If no replicated VS server is found within the scope of the query, according to the `create-if-not-found' option of , a service hosting server will be discovered within the same scope, and a replicated VS service will be created on it. After the creation, the SP-Proxy of the service hosting server (which is now also the SP-Proxy of the replicated VS server) sends new service advertisements of the replicated VS service to the service discovery system. As a result, subsequent service requests from clients in the same scope will be served by the new replicated VS server. Its SP-Proxy makes service configuration selections among . After some time, the most popular movies will be cached in the replicated VS server. In this way, multiple replicated VS servers can be created in different scopes. The load of the original VS server is effectively alleviated, although it still gets involved in service configurations in the case of a `cache-miss'. 17 7 Prototype Implementation and Performance We have implemented a prototype of called , a CORBA-enabled middleware. In order to show the effectiveness of the prototype, we have also built the VS service described in Section 6 on top of . 7.1 Prototype Implementation entities and their interactions: The entities in are implemented as CORBA objects. The CORBA implementation we use is dynamicTAO [18] in the system. dynamicTAO adds self-tailoring capability to the original TAO [19] developed at Washington University. To enable interactions among entities, we leverage CORBA's Naming, Property, and Trader Services. When a client requests a multimedia service , the intercept request method of the client's SP-Proxy is invoked by some front-end object such as a web browser. The client's SP-Proxy will invoke: (1) the discover service method of the DS in the same domain, if does not contain the service provider's location; and (2) the get availability method of the local RMs to form . With and , the client's SP-Proxy invokes the configure service method of the SP-Proxy of the service provider. The latter will invoke: (1) the compute resource requirement method of Q-R Translators of the candidate service configurations; (2) the get availability method of the local RMs (to form ); and (3) the discover service method of a DS, if some service component in the selected service configuration is unresolved. During service instantiation, each SP-Proxy involved will invoke (1) the service launch method of its direct downstream SP-Proxy (or SP-Proxies); and (2) the start method of its local service component in the selected service configuration. Script language for service polymorphism specification: also provides a simple script language for service developers/administrators to create service polymorphism specification. By using the script language, the CL, DGs, and corresponding Q-R Translators can also be specified. For example, Figure 10 shows the script version of the service polymorphism specification for the original VS server (GUI version in Figure 9(a)). By executing the script on the VS server, the CL and DGs will be created, and the Q-R Translators (TransX.QRT) will be `hooked' to the SP-Proxy of the VS server. Support for dynamic service creation: To support this special service configuration, provides the capability of dynamic downloading of (1) service components, and (2) service polymorphism specification for the service to be created. The downloading is initiated by the SP-Proxy of the original service provider. As an alternative, also provides a static approach: the service components and service polymorphism specification are stored on the hosting server ahead of time, and gets activated only when a service creation request comes. 18 ServiceComponents = {MS ("MpegSender", LOCAL), MP ("MpegPlayer", CLIENT), HP ("H261Player", CLIENT), BP ("BitmapPlayer", CLIENT), MHT ("MpegH261Transcoder", UNRESOLVED, NEAR(MS)), MBT ("MpegBitmapTranscoder", UNRESOLVED, NEAR(MS))} CandidateServiceConfigurations = {C0, C1, C2, C3} DefineCL { CL = NULL; CL = add_to_list (CL, C0); CL = add_to_list (CL, C1); CL = add_to_list (CL, C2); CL = add_to_list (CL, C3); } DefineDG (C0) { C0->type = "service redirection -creation"; C0->QRTranslator = "Trans0.QRT"; // specify its Q-R Translator Nodes = {SELF, ("VS", UNRESOLVED)}; add_edge = (SELF, ("VS", UNRESOLVED)); } DefineDG (C1) { C1->type = NORMAL; C1->QRTranslator = "Trans1.QRT"; Nodes = {MS, MP}; add_edge = (MS, MP); } DefineDG (C2) { C2->type = NORMAL; C2->QRTranslator = "Trans2.QRT"; Nodes = {MS, MHT, HP}; add_edge = (MS, MHT); add_edge (MHT, HP); } DefineDG (C3) { C3->type = NORMAL; C3->QRTranslator = "Trans3.QRT"; Nodes = {MS, MBT, BP}; add_edge = (MS, MBT); add_edge (MBT, BP); } Figure 10: Script of Service Polymorphism Specification for the Original VS Server 7.2 Example VS Service Implementation Service component implementation: The service components in the VS service are also implemented as CORBA objects. Each service component has an entry in the Service Component Table of its local SP- Proxy. A method start is defined for each service component. start will be invoked by the local SP-Proxy during service instantiation. Note that does require that every service component has the start method, and its IDL definition should conform to the following convention: If a service component runs on the service provider (for example, MpegSender and MpegProxy- Sender), the first parameter of its start method is the service request descriptor. Otherwise, the odd-number parameter(s) of the start method is(are) the IOR(s) (Interoperable Object Reference) of its direct upstream service component(s), and the even-number parameter(s) of the start method is(are) the IOR(s) of its direct downstream service component(s). This convention will enable a SP-Proxy to inform a local service component of its dependency relations with other service components in a selected service configuration. Service polymorphism specification: When deploying the VS service, the service developer creates the service polymorphism specification using either the GUI or the script language interface. Different 19 specifications have to be provided for the original VS server and for the replicated VS server - the latter remains inactive until it is downloaded to the hosting server at runtime. The Q-R Translators we implement for the candidate service configurations are quite simple and approx- imate. However, one may choose to implement more complicated and accurate Q-R Translators. The Q-R Translators compute resource requirement vectors based on the requested movie's recording frame rate, show time, average and maximum frame sizes, and display size. For example, the following formula is used in the Q-R Translator of , when computing the end-to-end bandwidth requirement (in bps) between the VS server and the client: (3) It is difficult to compute the CPU requirement. In this case, we roughly estimate CPU requirement based on off-line probing. Representative off-line probing results can be listed in a table in the Q-R Translator. By looking up the table, the Q-R Translator gives an estimate on CPU requirement. For example, the Q-R Translator of will estimate that for service component MpegPlayer, roughly 10% of a 200MHz UltraSPARC CPU is required to play back an MPEG movie at 8fps, with a display size of 352x240 pixels. 7.3 Performance Evaluation We evaluate the performance of prototype. We first measure the service configuration overhead in REACTS protocol. We then present the customized VS QoS delivered to different clients with the support of . The testbed of our prototype is shown in Figure 11. There are four domains I, II, III, and IV. Hosts in the testbed include: Domain II Service hosting server (munich) media gateway (lima) desktop client Domain I Domain III DS II media getaway (monet) PalmPilot client Laptop client DS I DS III VS server (budapest) DS IV laptop client wearable client Domain IV Figure 11: Testbed of Our Prototype The VS server budapest (Sun Ultra-2 with dual UltraSPARC 200MHz, 256MB RAM, Solaris 2.6); Four types of VS clients: (1) desktop computers (either workstation with Sun UltraSPARC 200MHz, 128MB RAM, Solaris 2.6, or PC with Pentium II 266MHz, 128MB RAM, Windows NT 4.0), (2) 20 laptop PCs (IBM ThinkPad 570, Pentium II 366MHz, 128MB RAM, Windows NT 4.0), (3) wearable PCs (Xybernaut, Pentium 166MHz, 64MB RAM, Windows NT 4.0), and (4) PalmPilots (3COM PalmIII, 3MB RAM, PalmOS 3.0); The media gateways (which provide auxiliary video transcoding services) lima and monet (Sun Ultra- 2, UltraSPARC 200Mhz, 128MB RAM, Solaris 2.6). Each gateway has both MpegH261Transcoder and MpegBitmapTranscoder service components; The service hosting server munich (same system parameters as the desktop PC VS clients); The discovery servers , and for the four domains, respectively. and define their scope as their own domains; while and define their scope as their own domains plus domain II. Each of domains I, II, and III is on a 10Mbps Ethernet LAN, the LANs are interconnected by high speed departmental routers. Domain IV is on an in-building wireless LAN (however, for domain IV is on the wireline side), and the laptop and wearable PCs are connected by Proxim wireless network cards. The available wireless bandwidth ranges from tens of Kbps to a few hundred Kbps. In domain III, we set up a Windows NT RAS (Remote Access Service) server, and each PalmPilot is connected to the network via the RAS server on a 57.6Kbps serial line. 7.3.1 REACTS Execution Overhead We first study the overhead of executing the REACTS protocol, based on our measurements of the VS service configurations. The execution time of REACTS protocol begins when a client raises a service request, and ends when the service components in the selected service configuration have been started. In Table 1, we show the average execution time (each over 10 trials) of REACTS when different service configurations are chosen. For , the first value is the execution time of the service creation option, and the second value is the execution time of service re-direction. In Table 2, we show the breakdown of the REACTS execution time, i.e. the average time for each key step. For multimedia services (contrary to non-multimedia Web data services), the REACTS execution time is not significant comparing with the duration of actual service sessions. We assume that each client does not know the location of the VS server before each service request. Therefore, when , , or is chosen, the execution of REACTS involves one service discovery for the VS service. In other cases, there are two service discoveries - one for the VS service (the discov- ery result is either the VS server or a replicated VS server), and one for the auxiliary transcoding service ( , or ), or for the service hosting service ( ). To reduce service discovery overhead, SP-Proxies can cache the discovery results for future use. However, resource availability of the discovered 21 Config. REACTS Execution Time Config. REACTS Execution Time 363.5ms/95.9ms 97.1ms 104.3ms 124.2ms 151.2ms 122.5ms 142.6ms 113.8ms - - 162.9ms - - 158.2ms Table 1: REACTS Execution Time When Different Service Configurations Are Chosen Step Time Service discovery 20.3ms Contacting RMs (each SP-Proxy) 15.6ms Translation and decision making 2920ms/2.1ms Service launching (each SP-Proxy) 26.7ms Dynamic downloading ( 100KB) 291.9ms Table 2: Breakdown of REACTS Execution Time service providers may change over time. Therefore, cached discovery results have to be deleted after a time-out, and new service discoveries will be performed. The QoS-resource translation step may potentially incur a large overhead. For example, in order to calculate the network bandwidth requirement, the Q-R Translators have to parse the entire MPEG file to derive the maximum and average frame sizes. The translation takes almost 3 seconds for our movie test file. This is obviously undesirable for the SP-Proxy, which may receive a large number of simultaneous service requests. Fortunately, notice that the QoS parameters of a stored media data source do not change over time. Therefore, they can be recorded after one round of parsing. In the future, a translator will not have to parse the media data source again. By using this method, the average translation and decision making time drops to just about 2ms. We observe that the downloading time in dynamic service creation grows linearly with the size of content (service components and service polymorphism specification) to be downloaded. However, this is just a one-time overhead for all the clients that will be using the created service. 7.3.2 Service Configuration Selections and VS QoS In this section, we show how provides runtime support, and achieves customized VS QoS for different clients. In our experiments, we use a MPEG-I movie test file. Its recording frame rate is 24fps, show time is 20 minutes, display size is 352x240 pixels, and the average and maximum frame sizes 22 are 3.2KB and 18.0KB, respectively. In our Q-R Translators, the minimum acceptable VS QoS for each candidate service configuration is set as in Table 3. Config. Framerate Size(pixels) Delay 8fps 352x240 10sec 8fps 176x120 5sec 4fps 88x56 3sec 8fps 352x240 15sec 8fps 176x120 10sec 4fps 88x56 8sec Table 3: Minimum acceptable VS QoS for each candidate service configuration At runtime, selects different service configurations for VS clients under different resource condi- tions: For a desktop client in domain II, Table 4 shows: (1) resource availability measured at different times - and denote the available CPU and local network bandwidth on the service provider and on the client, respectively (vectors with a rep subscript indicate the replicated VS server); (2) the selected service configurations under these resource conditions; and (3) the actual VS QoS achieved by the selected service configurations. At first, no replicated VS service exists. The SP-Proxy of the VS server selects for the client (Row 1 in Table 4). The actual VS QoS is much better than the minimum acceptable QoS in Table 3, due to sufficient resources. Later, we burden the VS server with some heavy background load, so that its available CPU drops to 15%. Now, when the client makes a service request, the SP-Proxy of the VS server selects (Row 2 in Table 4). The bold value in the Table indicates: this resource leads to the selection of this service configuration. Since there is no replicated VS server in domain II, creates one on the service hosting server munich. The new service advertisement is sent to . After the creation of the replicated VS service, the client sends service request to the replicated VS server. However, a `cache miss' occurs, and the SP-Proxy of the replicated VS server selects for the client (Row 3 Table 4). After this VS session, the movie is cached in the replicated VS server. If the client makes another service request now, will be selected (Row 4 in Table 4). Config. Framerate Size(pixels) Delay 23.9fps 352x240 4.3sec (create) - - - 24.0fps 352x240 10.0sec 24.0fps 352x240 3.8sec Table 4: Service Configurations and VS QoS for a Domain II Desktop Client (due to space limitation, we do not show the resource type in the vectors) For a laptop PC client, Table 5 shows the results: also includes the available battery power on 23 the laptop. Before the replicated service is created, the client is in the wireless domain IV. The SP-Proxy of the VS server selects for it (Row 1 in Table 5), due to the limited wireless network bandwidth. Media gateway monet in domain I is discovered to provide the auxiliary transcoding service. Later, the laptop is moved to (wireline) domain III and hooked to the Ethernet, after the replicated VS service has been created and the movie has been cached. When the client queries for VS service, it will get the replicated VS server instead of the original VS server, due to the resource-awareness of the service discovery system. The SP-Proxy of the replicated VS server selects for the laptop (Row 2 in Table 5), because it now has sufficient wireline bandwidth. However, if the laptop makes another request when its remaining battery is only 10%, will be selected (Row 3 in Table 5). requires much less client-side CPU and network bandwidth, conserving the laptop's battery power. Media gateway lima in domain II is discovered to provide the auxiliary transcoding service. Config. Framerate Size(pixels) Delay 12.8fps 176x120 3.0sec 23.9fps 352x240 4.4sec 4.0fps 88x56 5.2sec Table 5: Service Configurations and VS QoS for a Laptop Client For a wearable PC client in the wireless domain IV, Table 6 shows the results. Before the replicated service is created, the SP-Proxy of the VS server selects for the client (Row 1 in Table 6), due to the limited wireless bandwidth. Media gateway monet in domain I is discovered to provide the auxiliary transcoding service. Later, the replicated VS service is created and the movie has been cached. However, the client is not aware of the replicated VS server. When it submits a service request again to the VS server, the SP-Proxy of the VS server selects , which re-directs the request to the replicated VS server. There, is selected for the client by the SP-Proxy of the replicated VS server (Row 2 in Table 6). Media gateway lima in domain II is discovered to provide the auxiliary transcoding service. Config. Framerate Size(pixels) Delay 20.8fps 176x120 5.4sec 17.1fps 176x120 4.7sec 19.0fps 176x120 5.7sec Table 6: Service Configurations and VS QoS for a Wearable PC Client For a PalmPilot client in domain III, Table 7 shows the results - the RM on the PalmPilot always reports fixed values as shown in . Before the replicated service is created, the SP-Proxy of the VS server selects for the client (Row 1 in Table 7), due to its very limited system resources. Media gateway monet in domain I is discovered to provide the auxiliary transcoding service. Later, the replicated VS service is 24 created and the movie has been cached. However, similar to the wearable PC, the PalmPilot is not aware of the replicated VS server. When it submits a service request again to the original VS server, the request also gets re-directed to the replicated VS server, and will then be selected (Row 2 in Table 7). The media gateway also changes to lima. Config. Framerate Size(pixels) Delay 4.0fps 88x56 3.6sec 4.0fps 88x56 3.2sec 4.0fps 88x56 2.8sec Table 7: Service Configurations and VS QoS for a PalmPilot Client From the experiments, we show that , our prototype is adaptive to the heterogeneous and changing environment. The selected service configurations always achieve satisfactory QoS under the current resource availability constraint. There is, however, a limitation in the current implementation of : it assumes that the selected service configuration never changes throughout the service session, i.e. it does not consider service re-configurations. To support service re-configuration during a service session, we need to provide a smooth and generic mechanism to handle service state switching. Otherwise, serious service glitches may occur. This is our on-going work. 8 Related Work There have been numerous individual solutions to the problem of QoS provision in dynamic and het- erogeneous environments. For example, for the `media content distribution' type of services, there exist techniques such as adaptive data delivery [1], media data prefetching [27], smoothing [6], layering [17], transcoding [2], and replication [4]; for the `visual tracking' type of services, there exist techniques such as trading the number of objects tracked for tracking precision [14], and switching tracking servers for load balancing [13]. However, these techniques may be service-specific, and they may only target specific types of resources - for example, some on network bandwidth and some on CPU. On the other hand, is a service-independent enabling framework for multimedia service management. There are other systems and frameworks for service and resource management. In the Adapt Project [7], the concept of open binding is introduced as a programming model for the implementation of adaptation policies in mobile multimedia applications. Like , open binding is also component-based. How- ever, it does not consider dynamic service discovery, and does not provide a general service management protocol like REACTS. In the Darwin Project [3], a hierarchical service brokerage architecture is proposed for composing complicated and value-added distributed services. Darwin focuses more on the distributed signaling aspect of the service management issue, while not emphasizing the problem of heterogeneity in clients' capability and connectivity. In the Cactus Project [23], a framework is proposed for supporting 25 customizable fine-grain QoS attributes related to dependability, real-time, and security. It aims to provide a more generic multi-dimensional QoS provision framework, and could potentially be plugged in to handle multimedia QoS provision. Several architectures have been proposed that explicitly consider dynamic service discovery. In Active Names [25], a programmable model is introduced to map names to a chain of mobile programs, which can customize how a service is located and how its results are transformed and transported back to the clien- t. Active Names shares the same motivation as that of , and its name resolution is similar to 's service configuration selection. However, is different from Active Names in that: (1) supports not only the programming of service components, but also the programming of ser- vice polymorphism knowledge; (2) is more resource-aware: every service configuration or discovery decision is resource-driven. Sun's Jini [26] is a software infrastructure to discover and federate networked devices and software components into ubiquitous and dynamically composable distributed services. The key concepts of Jini also influence our work. However, Jini has not yet addressed the QoS and resource awareness issue in multimedia service composition. The Ninja Project [12, 5] also supports ad hoc and dynamic service composition for heterogeneous clients. However, it focuses more on service composition, rather than on service polymorphism. Distributed meta-computing systems such as Globus [8], Legion [10], and Condor [24] also advocate dynamic discovery of computing resources over a wide-area networked environment. These systems, in one way or another, also perform service-independent resource management and service configuration. How- ever, they focus more on the discovery of general-purpose resources, while focuses more on the discovery of application-level services. In addition, could potentially be enhanced by making use of these systems' resource allocation and monitoring capability. Finally, emerging service discovery systems [11, 5] and network measurement systems [21, 9, 15] will greatly benefit : the tasks of service discovery and network performance measurement will be delegated to these public and widely-deployed services. Furthermore, our resource-awareness enhancements (Section 5.2.1) can be easily integrated into the proposed service discovery systems. 9 Conclusion Multimedia services are becoming ubiquitous - they are expected to be available anytime, anywhere, and by using any computing device. In the meantime, the distributed environment is becoming more hetero- geneous and dynamic: traditional and non-traditional clients co-exist with different processing capability and network connectivity; and end-to-end resource availability varies from time to time between service providers and clients. These trends call for a new multimedia service management framework, which will enable composable and customized service delivery to each individual client. The challenge is to provide 26 each client with satisfactory QoS, under the constraint of current end-to-end resource availability. In this paper, we present a solution to this challenge: the framework based on the idea of QoS and resource-aware service polymorphism. does not override existing QoS adaptation tech- niques. Instead, it provides generic programming interface, architecture, and runtime support to integrate and dynamically select from these techniques. In this sense, it serves as a `dispatcher', mapping logical mul- timedia service requests to different service delivery forms, i.e. different service configurations. However, is not responsible for QoS adaptation within a service configuration, which is the task of the QoS technique(s) implemented in the selected service configuration. The key features of include: (1) service polymorphism is programmable to service developers/administrators; (2) service configuration se- lections are free from users' intervention; and (3) service configuration and service discovery are seamlessly integrated, and the decisions on service configuration selection and service discovery are both resource- driven. middleware - our prototype of , and an example multimedia service built on top of demonstrate the soundness of . We expect the deployment of other ubiquitous multime- dia services on top of , involving more devices and service components, and accessible to clients in a wider-area environment. References [1] T. Abdelzaher and N. Bhatti. Adaptive Content Delivery for Web Server QoS. Proceedings of IEEE IWQoS '99, June 1999. [2] E. Amir, S. McCanne, and H. Zhang. An Application Level Video Gateway. Proceedings of ACM Multimedia'95, November 1995. [3] P. Chandra, A. Fisher, C. Kosak, T. Ng, P. Steenkiste, E. Takahashi, and H. Zhang. Darwin: Re- source Management for Value-Added Customizable Network Service. Proceedings of IEEE ICNP'98, October 1998. [4] C. Chou, L. Golubchik, and J. Lui. A Performance Study of Dynamic Replication Techniques in Continuous Media Servers. Proceedings of ACM SIGMETRICS '99, May 1999. [5] S. Czerwinski, B. Zhao, T. Hodes, A. Joseph, and R. Katz. An Architecture for a Secure Service Discovery Service. Proceedings of ACM MobiCom'99, September 1999. [6] W. Feng. Rate-Constrained Bandwidth Smoothing for the Delivery of Stored Video. Proceedings of MMCN'97, 1997. [7] T. Fitzpatrick, G. Blair, G. Coulson, N. Davies, and P. Robin. Supporting Adaptive Multimedia Appli- cations through Open Bindings. Proceedings of International Conference on Configurable Distributed Systems (ICCDS'98), May 1998. [8] I. Foster and C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. International Journal of Supercomputer Applications, 1997. 27 [9] P. Francis, S. Jamin, V. Paxson, L. Zhang, D. Gryniewicz, and Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. Proceedings of IEEE Infocom '99, March 1999. [10] A. Grimshaw, Wm. Wulf, and the Legion Team. The Legion Vision of a Worldwide Virtual Computer. Communications of ACM, January 1997. [11] E. Guttman, C. Perkins, J. Veizades, and M. Day. Service Location Protocol, Version 2. IETF RFC- 2165, November 1998. [12] T. Hodes and R. Katz. Composable Ad Hoc Location-Based Services for Heterogeneous Mobile Clients. ACM Wireless Networks Journal, October 1999. [13] B. Li, W. Jeon, W. Kalter, K. Nahrstedt, and J. Seo. Adaptive Middleware Architecture for a Distributed Omni-Directional Visual Tracking System. Proceedings of SPIE/ACM MMCN 2000, January 2000. [14] B. Li and K. Nahrstedt. Dynamic Reconfigurations for Complex Multimedia Applications. Proceed- ings of IEEE ICMCS'99, June 1999. [15] N. Miller and P. Steenkiste. Collecting Network Status Information for Network-Aware Applications. Proceedings of IEEE Infocom 2000, March 2000. [16] K. Nahrstedt, H. Chu, and S. Narayan. QoS-Aware Resource Management for Distributed Multimedia Applications. Journal of High-Speed Networks, Special Issue on Multimedia Networking, 7, 1998. [17] R. Rejaie, M. Handley, and D. Estrin. Quality Adaptation for Congestion Controlled Video Playback over the Internet. Proceedings of ACM SIGCOMM '99, August 1999. [18] M. Roman, F. Kon, and R. Campbell. Design and Implementation of Runtime Reflection in Communi- cation Middleware: the dynamicTao Case. Proceedings of ICDCS'99 Workshop on Middleware, May 1999. [19] D. Schmidt, D. Levine, and C. Cleeland. Architectures and Patterns for High-performance, Real-time CORBA Object Request Brokers. Advances in Computers, Academic Press, Ed., Marvin Zelkowitz, to appear. [20] P. Shenoy and H. Vin. Cello: A Disk Scheduling Framework for Next Generation Operating Systems. Proceedings of ACM SIGMETRICS'98, June 1998. [21] M. Stemm, R. Katz, and S. Seshan. A Network Measurement Architecture for Adaptive Applications. Proceedings of IEEE Infocom 2000, March 2000. [22] The 2K Team. The 2K Project. http://choices.cs.uiuc.edu/2K. [23] The Cactus Project Team. The Cactus Project. http://www.cs.arizona.edu/cactus. [24] The Condor Project Team. The Condor Project. http://www.cs.wisc.edu/condor. [25] A. Vahdat, M. Dahlin, T. Anderson, and A. Aggarwal. Active Names: Flexible Location and Transport of Wide-Area Resources. Proceedings of 1999 USENIX Symposium on Internet Technologies and Systems (USITS '99), October 1999. [26] J. Waldo. The Jini Architecture for Network-Centric Computing. Communications of ACM, July 1999. [27] Y. Wang, Z. Zhang, D. Du, and D. Su. A Network-Conscious Approach to End-to-End Video Delivery over Wide Area Networks Using Proxy Servers. Proceedings of IEEE Infocom '98, March 1998. 28 10 Resource-Awareness Enhancement to Service Discovery Systems In this Appendix, we present the resource-awareness enhancement to the service discovery system. The goals are: (1) it should increase the probability that a discovered service provider has sufficient resources to fulfill a service request; (2) it should be easily integrated into an existing service discovery system. In the design of the resource-awareness enhancement, we only make the following minimum assumptions about the `base' service discovery system: (1) the SP-Proxy of a service provider sends service advertisements only to its home DS; (2) the SP-Proxy of a querying host sends the service query to its home DS; and (3) the DS which originally accepts a service query is also responsible for gathering discovery results from other DSes, and selecting one to return to the querying host. There are two basic ideas behind the resource-awareness enhancement: (1) caching of discovery results by the DS which submits an initial query; (2) using `customer feedbacks' about resource conditions to select a `good' service provider for a service query, with respect to resource availability. 10.1 Discovery Result Caching A home DS accepts service queries from hosts in the same domain. However, the discovery results may be returned from DSes of other domains7. In this case, the home DS will cache the results (in the form of service advertisements) for future queries, from the same domain and about the same service. The caching will lower both the query response time and the service discovery overhead. The caching policy is based on the query frequency of each service within the domain. With discovery result caching, it is natural to go one step further to associate each cached service adver- tisement with `customer feedbacks' regarding the resource condition of the corresponding service provider. The feedbacks are from hosts in the same domain which have recently used its service. This domain-specific view of service providers is useful, due to the varying end-to-end network performance between the same service provider and hosts in different domains. The DS will then use the feedbacks as hints to select a `good' service provider for upcoming service queries for the same service. 10.2 Resource Condition Feedback Generation The architecture and REACTS protocol make it possible to generate feedbacks about resource conditions. Recall that during the service instantiation phase of REACTS protocol (step 8 of Figure 7), the following information is propagated to each SP-Proxy involved in the service session: (1) the DG and of the selected service configuration; and (2) the location of each service component in the DG. With the information, we propose the following operations for each service session (Figure 12), as an extension to the execution of REACTS: During the service session, the SP-Proxy of each participating service provider periodically generates a resource Availability/Requirement Index (ARI) value. ARI indicates the current resource condition of the service provider (its computation to be described shortly). The SP-Proxy of the service provider sends every ARI value to the SP-Proxy of the host which previsouly queried for this service during REACTS (step a.1 in Figure 12). The latter host is regarded as the `customer' of the former. For example, in Figure 12, the service client is the customer of the service provider8. The SP-Proxy of the customer maintains an average of the ARI values received. 7To preserve the generality of the resource-aware enhancement, we make no assumption about how the service discovery system identifies these DSes. 8However, a customer can be itself a service provider. For example, in Figure 7 of Section 5.1, the service provider is the customer of the auxiliary service provider. 29 SPS: service polymorphism specification service client service components ... service provider service components a.2 `success' or `failure' SP-Proxy SPS ........ ...... SP-Proxy a.1 RM ... RM ARI of Service Provider (periodic) RM a.1 a.1 a.1 a.2 RM ... RM Feedback (avg. ARI or 0) RM about Service Provider DS 3 DS (caching the service advertisement of 1 Service Provider from DS1) DS 2 Figure 12: Resource Condition Feedback Generation from Each Service Session The ARI value is computed by the SP-Proxy of a service provider as follows: first, the SP-Proxy queries its RMs to obtain local resource availability information . and denote the type and availability of a local resource, respectively. Let denote the corresponding element in the of the current service session, then: ARI (4) The higher the ARI value, the higher the probability that the service provider has sufficient resources for this session. More importantly, ARI values are simple and not resource-specific. Therefore, their generation and transmission will not introduce additional complexity to 's runtime support, and will not significantly increase the signaling bandwidth and storage space. After the service session, the SP-Proxy of each customer sends a resource condition feedback to its home DS, which is caching the service advertisement of the corresponding service provider (step a.2 in Figure 12). The feedback includes: (1) the address of the service provider, and (2) the average ARI during the session - if the session was successful; or zero - if the session failed9. For each discovery result, the home DS maintains an average of ARI values received from different (in-domain) customers during the past amount of time. 10.3 Resource-Aware Service Provider Selection Using resource condition feedbacks, a DS is able to perform resource-aware selection from multiple qualified discovery results, in response to an upcoming service query. There are many policies for this selection. Here, we compare the following three representative policies: (1) Randomly pick one from the qualified discovery results; (2) Pick the one with the highest ARI; 9Here, we assume that when a service component terminates, it will return the status of the service session - either a success or a failure, to the local SP-Proxy. Our experience with the VS service prototype proves it feasible to implement a service component in this fashion. 30 (3) Pick the ith discovery result with probability: (5) This policy tries to avoid the synchronization effect of policy (2): the service provider with the highest ARI may be selected simultaneously for many other queries, causing its load to increase and then decrease rapidly. We illustrate the effectiveness of each policy by the following simulation. Assume there are three service providers that provide the same service. Each of them requires two types of resources and . The initial resource availability vectors of , and are , , and , respectively. Meanwhile, multiple queries for this service are submitted to the service discovery system. Each query will lead to a service session which requires amount of and amount of . is randomly distributed in , and is randomly distributed in . The duration of each service session is random- ly distributed between 10 and 50 minutes. We also assume that other resources except are always sufficient. 100 Least R/A ratio Prob. proportional 90 Random 80 70 60 50 40 30 20 Average service session success rate (%, over 1000 minutes) 10 20 30 40 50 60 70 80 Average service query arrival rate (queries/minute) Figure 13: Average Service Session Success Rate: a Simulation In our simulation, service queries arrive at the DS according to a Poisson process. We simulate different arrival rates (ranging from 15 queries/min to 80 queries/min) for a period of 1000 minutes. A service session is successful, if its requirement for and is always satisfied on the discovered service provider throughout the service session. Figure 13 shows the average success rate of service sessions (vs. different arrival rates) achieved by the three policies. We find that policy (3) (Prob. proportional) achieves higher success rate than policy (2) (Least R/A ratio), which achieves higher success rate than the random policy (Random). 31