We investigate dynamic decision mechanisms for composite web services maximizing the expected revenue for the providers of composite services. A composite web service is represented by a (sequential) workflow, and for each task within this workflow, a number of service alternatives may be available. These alternatives offer the same functionality at different price-quality levels. After executing a sub-service, it is decided which alternative of the next sub-service in the workflow is invoked. The decisions optimizing expected revenue are based on observed response times, costs and response-time characteristics of the alternatives as well as end-to-end response-time objectives and corresponding rewards and penalties. We propose an approach, based on dynamic programming, to determine the optimal, dynamic selection policy. Extensive numerical examples show significant potential gain in expected revenues using the dynamic approach compared to other, non-dynamic approaches.

In this paper we investigate sequential decision mechanisms for composite web services. After executing each sub-service within a sequential workflow, decisions are made whether to terminate or continue the execution of the workflow. These decisions are based on observed response times, expected rewards, and typical Service Level Agreement parameters such as costs, penalties, and agreed response-time objectives. We propose a model for the sequential decision-making process within which we explore a couple of decision algorithms. We benchmarked these algorithms against the profit made when executing the workflow without decision-making. We show that algorithm based on backward recursion principle of dynamic programming is optimal with respect to profit. Next, we analyse the structure of erroneous decisions for both algorithms and show that significant profit gains can be obtained by sequential decision making.

In this paper we obtain the scaling law for the mean broadcast time of a file in a P2P network with an initial population of N nodes. In the model, at Poisson rate lambda a node initiates a contact with another node chosen uniformly at random. This contact is said to be successful if the contacted node possesses the file, in which case the initiator downloads the file and can later upload it to other nodes. In a network with altruistic nodes (i.e., nodes do not leave the network) we show that the mean broadcast time is O(log(N)). In a network with free-riding nodes, our main result shows that a O(log(N)) mean broadcast time can be achieved if nodes remain connected to the network for the duration of at least one more contact after downloading the file, otherwise a significantly worse O(N) time is required to broadcast the file.

We show that different flavors of TCP may be viewed as implementations of age-based scheduling disciplines. By parameterizing the scheduling disciplines of interest we are able to position variants of TCP in a wide spectrum having FCFS (first-come first-served) and LAS (least attained service first) as extremal policies, and including PS (processor sharing) as an intermediate case. We argue that for highly loaded systems, providing a fair bandwidth allocation among all users is secondary to ensuring network stability. So as to isolate protocol fairness from congestion effects, we therefore focus on scenarios with infinite buffers. This way, asymmetries in capacity shares are the consequences of the protocol only, and not affected by the packet loss process. The model, however, is flexible enough to include finite buffers with random packet loss as a special case (for example to capture Active Queue Management). The results are helpful in studying fairness and performance concerned with transmission protocols in communication networks. For persistent HTTP connections we study the distributions of the transmission rates and the relative fairness index under various assumptions on the file size distributions and scheduling disciplines. For infinite file sizes, we show that protocols that increase priority more than linearly with the attained service asymptotically behave similar to FCFS. In contrast, protocols with at most linearly increasing (or even decreasing) priority, with TCP's Congestion Avoidance mechanism as the most prominent example, converge to PS scheduling (even in absence of losses). When the priority is exactly linear in the attained service, such as for scalable TCP and TCP's slow start phase, the shares remain constant in between file initiations and completions.

Third generation wireless systems can simultaneously accommodate flow transmissions of users with widely heterogeneous applications. As resources are limited (particularly in the air interface), admission control is necessary to ensure that all active users are accommodated with sufficient capacity to meet their specific Quality of Service requirements. Our admission control rule protects users with stringent capacity requirements ("streaming traffic") while offering sufficient capacity over longer time intervals to delay-tolerant users ("elastic traffic"). Performance evaluation of wireline differentiated-services platforms is already difficult due to the inherently large dimensionality of models to capture the diversity of user applications. In wireless systems, this is further exemplified as the location of users adds to the dimensionality problem. Using time-scale decomposition, we develop approximations to evaluate the performance of a differentiated admission control strategy to support integrated services with capacity requirements in a realistic downlink transmission scenario for a single radio cell.

As a natural multi-class generalization of the well-known (egalitarian) processor sharing (PS) service discipline, discriminatory processor sharing (DPS) is of great interest in many application areas, including telecommunications. Under DPS, the mean response time conditional on the service requirement is only known in closed form when all classes have exponential service requirement distributions. For generally distributed service requirements, Fayolle et al. (1980) showed that the expected conditional response times satisfy a system of integro-differential equations. In this paper, we exploit that result to prove that, provided the system is stable, for each class the expected unconditional response time is finite and that the expected conditional response time has an asymptote. The asymptotic bias of each class is found in closed form, involving the mean service requirements of all classes and the second moments of all classes but the one under consideration. In the course of the development we prove two other results that are of independent interest: we establish a conservation law for the time average unfinished work of all classes and, using a stochastic coupling argument, we show that the response times of different classes are stochastically ordered according to the DPS weights. Finally, we study DPS as a tool to achieve size based scheduling and we provide guidelines as to how the weights of DPS must be chosen such that DPS outperforms PS.

We consider a multi-class queueing system operating under the discriminatory processor-sharing (DPS) discipline. The DPS discipline provides a natural approach for modeling the flow-level performance of differentiated bandwidth-sharing mechanisms. Motivated by the extreme diversity in flow sizes observed in the Internet, we examine the system performance in an asymptotic regime where the flow dynamics of the various classes occur on separate time scales. Specifically, from the perspective of a given class, the arrival and service completions of some of the competing classes (called mice) evolve on an extremely fast time scale. In contrast, the flow dynamics of the remaining classes (referred to as elephants) occur on a comparatively slow time scale. Assuming a strict separation of time scales, we obtain simple explicit expressions for various performance measures of interest, such as the distribution of the numbers of flows, mean delays, and flow throughputs. In particular, the latter performance measures are insensitive, in the sense that they only depend on the service requirement distributions through their first moments. Numerical experiments show that the limiting results provide remarkably accurate approximations in certain cases.

We study in this paper a TCP-like linear-increase multiplicative-decrease flow control mechanism. We consider congestion signals that arrive in batches according to a Poisson process. We focus on the case when the transmission rate cannot exceed a certain maximum value. We write the Kolmogorov equations and we use Laplace transforms to calculate the distribution of the transmission rate in the steady state as well as its moments. Our model is particularly useful to study the behavior of TCP, the congestion control mechanism in the Internet. By a simple transformation, the problem can be reformulated in terms of an equivalent M/G/1 queue, where the transmission rate in the original model corresponds to the workload in the 'dual' queue. The service times in the queueing model are not i.i.d., and they depend on the workload in the system.