Abstract: The generalized stochastic Petri net (GSPN) model for large scale Web service composition system with complex timing constraints is usually hard to understand. System performance is difficult to analyze because of the explosion of state apace. By associating different kinds of timing constraints to place, transition and arc respectively, an extended GSPN (EGSPN) model is presented to reflect such Web service composition system in a compact and comprehensible manner. Furthermore, to deal with the problem of lacking general reduction methods for GSPN and overcome the difficulty in preserving timing constraints in model reduction process, a set of reduction rules are presented to facilitate the model reduction of EGSPN for some model
structures in common use. The model state space is decreased via model reduction. Examples show that the presented method provides an effective way to reduce complexity of initial model. It can be used to rapidly analyze performance of the most Web service composition systems.

Key words: Web service composition, generalized stochastic Petri net, reduction, performance analysis