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.
