In the service-oriented environment, a single Web service can hardly satisfy the given request, so thecomposition of multiple Web services is required to fulfill the goal. Without considering the inherent stochastic anddynamic nature of Web service, the existing composition methods mostly generate static plans. As a result, Webservice composition often terminates with failure inevitably. In this paper, metrical methods of several random QoSdimensions and QoS Management Architecture are presented, and one reliable Web service composition algorithmis also designed based on markov decision process (MDP)—only dynamic controlling method of stochastic discreteevent system (SDES). Experimental results demonstrate the success rate of Web service composition has beenimproved greatly.