The stochastic service provision problem: decomposition methods

Our framework is a distributed telecommunications network, for example as defined by the TINA-C standard. The term service is here used to encompass a set of distributed software applications togetherwith the set of computing and network resources it uses. The service provision problem addresses how to install applications at the computing nodes so that demand can be met for services in the networkIn this paper we assume that the processing capacity need of an application increases linearly with the number of customers using it concurrently. In addition an application uses a fixed amount of the node resources whenever it is installed on the node, even when it is not satisfying a single request. This is illustrated in Figure I for two applications at three computing nodes. There is a lead time both for setting up and shutting down applications, during which demand cannot be met but the fixed resource use is present. The distributed framework makes it possible, under specific assumptions, to aggregate demand for applications over all demand locations. When demand is uncertain this problem can be modeled as a two-stage staochastic integer program. The first-stage variables are binary andindicate whether an application is installed at a node or not. The second stage is contionous and describes what demand is actually met after uncertainty is resolved. This talk suggests decomposition basedbranch and b ound methods for solving the stochastic service provisionproblem.