New model for reliable web service

Abstract

In this thesis a new model for a distributed web service system is presented. The proposed " system is composed of multiple web service components having multiple alternative versions distributed among multiple servers. Each of the versions of a component has its own multidimensional resource requirements. A request is placed by a client for a specific web service component to a broker, which can allocate more than one version to increase satisfaction of the client by redundant allocation. The satisfaction of a client depends on the reliable service of redundant versions served by multiple servers. In the proposed model an allocation is to be found that maximizes total client satisfaction subject to the resource constraints of the servers. A variant of the network flow maximization algorithm has been used to address the proposed problem. The resource requirements and constraints can be mapped onto a multidimensional flow model. Each augmenting path represents one allocation of a version of a web service component at a server. Clearly, there is no scope for partial flows and the flow conservation principle must not be broken. Considering these two algorithmic constraints, the basic Push- Relabel algorithm is modified to solve the problem. The resource allocation problem considered here is a Multidimensional Knapsack Problem which is NP hard and has exponential time complexity. In the proposed algorithm this Multidimensional Knapsack Problem has been reduced to a Single Knapsack Problem at each server with necessary communications among the servers. This communication among the servers is achieved through the flow of resources in the network. Thus the presented heuristic running with polynomial time complexity and produc,ing suboptimal solution is attractive for a web service system, a real time application, The proposed heuristic algorithm has been compared with a Brute Force and a Greedy algorithm. It is found that the solutions of the proposed algorithm are very close to the optimal solutions provided by the Brute Force algorithm. On the other hand, the proposed algorithm provides far better solutions than the Greedy algorithm. Since the running components can not be allocated to another server in the middle of their execution, the new '-',. component requests must be allocated using the remaining free resources. That means each VI ., \." ., iteration is an independent problem to be solved using this heuristic algorithm. In addition to that, the network flow model presented in this thesis inherently rules out the number of requests from contributing in time complexity of the algorithm.