Home

Document

Project Members

Future Plan

Other Links
 
QCWS Preview

Web services are modular web applications that can be independently deployed and invoked by other software or services on the web. This offers enterprises the capability to integrate in-house business services with external Web services to conduct complex business transactions. For many distributed applications, the runtime performance (e.g. end-to-end delay, overall cost, service reliability and availability) of complex services are very important. . In QCWS project, we propose a broker-based framework to facilitate dynamic integration and adaptation of QoS-aware Web services with end-to-end QoS constraints. We also design various service selection and adaptation algorithms used by QoS brokers in different situations.

QoS Model for Web services

QoS Attributes: In QCWS, we consider following QoS attributes for a service s :

  1. Response Time (Ts): the time interval between when a service is requested and when it is delivered;

  2. Service Cost (Cs): the price that a service customer has to pay for using the service;

  3. Availability (As): the percentage of time that a service is available during some time interval;

  4. Reliability (Rs): the probability that a request is correctly served.

Web service integration: We consider six basic service integration models in QCWS, as shown in Figure 1.

 

Figure 1:Models of Service Flow Integration

 
 

For a complex service composed by several component services, the performance is measured by its end-to-end quality. Figure 2 shows a service process example. Suppose the response time and the cost of service i are ti and ci, the total response time T and the cost C of the whole system can be calculated as:

T = tA +max(tB + p1 * tD + p2 * tE, tC + K * tF)+tG

C = cA + cB + p1 * cD + p2 * cE + cD + K * cF+cF
 

Figure 2: Service Process Integration Example
 

[Back to Top]

 
QBroker Framework
 

The main motivation behind our QBroker framework is to help users identify and select component services for building their distributed service process. A broker can be used to conduct service integration for clients according to their needs. In our design, a broker has the Service Info Manager, the Selection Manager, the Composition Manager, and the Adaptation Manager to conduct service information tracking, composition, selection, and adaptation respectively. Figure 3 shows the architecture of QBroker. (Publication [C1],[C4])

 

Figure 3: QBroker Architecture

 
 
Service Selection Algorithms
 

In QBroker, service composition with QoS assurance is conducted in two steps: service planning and service selection, as shown in Figure 4. They are accomplished by the Composition Manager (CM) and the Selection Manager (SM) respectively. The mapping from a user request to process plans (step 1) only considers the functional requirements of the service request and has no consideration for QoS requirements. The second step is the most important and challenging step in QoS service composition. In this step, SM maps the functional graph produced by CM to a service candidate graph and constructs an executable distributed process. The mapping from a functional graph to an executable application is decided by the distributed performance of services and manages a user's QoS requirements.

Figure 4. QoS Web service composition

 

In our research, the service selection problem can be modelled using either the combinatorial model or the graph model. The biggest difference between the two models lies on their ability to account for the network QoS factor (transmission delay, cost, etc.) Algorithms using the combinatorial model have no flow concept and can not do the accurate estimation about network QoS values. While the algorithms solving the graph model can accurately take network QoS values into consideration but at the cost of a high algorithm complexity.

Another dimension of the service selection problem is the number of QoS constraints to be considered. The problem can be solved by different algorithms if the end-to-end process has only one QoS constraint or multiple QoS constraints. So there are 4 different problem formulations. Each can be solved by different algorithms.

  • Combinatorial model, One QoS constraint: Problem can be defined as a Multiple-Choice Knapsack Problem (MCKP) and solved by exhaustive search, dynamic programming or Dr. Pisinger's algorithm. (Publication [J1],[C4])
  • Graph model, one QoS constraint: Problem can be defined as delay-constrained shortest path problem and solved by constrained bellman-ford (CBF) or constrained shortest path (CSP) algorithm. (Publication [J1],[C4])
  • Combinatorial model, mulitple QoS constraint: Problem can be defined as a Multi-dimension Multi-choice Knapsack Problem (MMKP) and solved by branch-and-band algorithm (BBLP) or heuristic (HEU) algorithm. (Publication [C1])
  • Graph model, multiple QoS constraint: Problem can be defined as multi-constrained optimal path problem (MCOP) and solved by multi-constrained shortest path (MCSP) algorithm or heuristic MCSP (MCSP-K) algorithm. (Publication [C1])
 
 
Service Adaptation Algorithms
 

During the execution of a complex business process, if one component service fails or becomes overloaded, a mechanism is needed to ensure that the running process is not interrupted and the failed service is quickly and efficiently replaced. In QCWS, we design two algorithms to solve the problem. The first algorithm uses the backup path approach so that the predecessor of a failed service may quickly switch to a predefined backup path. The second algorithm uses the replacement path approach to re-construct a new process by skipping a failed service. All these dynamic adaptations can be done by business process itself or QBroker to handle single point failure. Producing the information needed for dynamic adaptation only increases the business process composition time by a constant factor regardless of the system size. (Publication [C5])