In the last decade, online e-commerce businesses, represented by the e-commerce portals, have grown significantly and become an important sector of world economy. This dissertation helps address the server scalability problem for supporting the sustainable growth of the online e-commerce industries.; Most of today's e-commerce portals are implemented with distributed component technologies and server clusters. Each server application comprises dozens or hundreds of distributed software components, and each of such components can run on any of a cluster of application servers connected by a high-speed fiber local area network (LAN). While multiple server machines support parallel execution of the software components, inter-server communication is a few orders slower than servers' CPU speed. This research studies the optimized allocation of software components to server machines to maximize computation load balance and minimize communication overhead.; Multi-way graph partitioning is first adopted to model the software component allocation problem. The problem is proved to be NP-hard. A novel graph transformation is introduced to combine the two conflicting objectives into a single objective function, and a transformation theorem is proved that problem instances before and after this transformation are equivalent. Based on careful observation of the properties of the solution space, a scheme for incremental objective function evaluation is designed to speed up any iterative solution heuristics to this problem by a factor proportional to the number of software components involved. Simulated annealing is adopted to solve the problem. Extensive experimental study shows that the proposed simulated annealing algorithm can outperform repeated random running in the same amount of time by 20% to 2366.67%, and outperform local optimization by 1.96% to 1000% with a running time about 6 to 100 times of that for the latter.; The major contributions of this research include using multi-way graph partitioning to model a challenging performance problem critical to sustainable growth of e-commerce portals, creative problem transformation for simplifying a complex problem, and incremental objective function evaluation that can benefit any iterative solution heuristics.
展开▼
