241 research outputs found
Scheduling in Stochastic Resource-Sharing Systems
No full textIn this thesis we study queueing models that arise in the context of resource sharing in communication networks. We determine scheduling policies that (asymptotically) optimize the performance of the system, and evaluate policies that share the resources among the users in a fair manner. Chapter 1 gives an overview of several concepts related to resource-sharing systems and introduces the queueing models and main techniques used throughout the thesis. We describe the work-conserving single-server system, the linear bandwidthsharing network, and the parallel two-server model. In the latter two models the speed at which the system works depends on the scheduling decision taken and on the types of users presently in the system. These models can therefore be seen as extensions of the single-server model. The stochastic evolution of the numbers of users is determined by the scheduling policy, which specifies how the resources are shared among all users. We use sample-path techniques and stochastic dynamic programming tools in order to characterize policies that minimize the holding cost. Since the original stochastic model is not always tractable, we also investigate two limiting regimes. One of them is the heavy-traffic regime where we let the offered load approach the maximum capacity. In the other regime we consider the queuelength processes under the so-called fluid scaling. In Chapter 2 we focus on the single-server system in heavy traffic and analyze a generalization of the DPS policy. More specifically, we consider phase-type distributed service requirements and allow customers to have different weights in various phases of their service. In our main result we establish a state-space collapse for the scaled steady-state queue length vector in heavy traffic. The result shows that in the limit, the queue length vector is the product of an exponentially distributed random variable and a deterministic vector. The proof consists in showing that the joint probability generating function of the queue lengths satisfies a partial differential equation that allows a closed-form solution after passing to the heavy-traffic limit. Our result has several interesting consequences for the standard DPS queue. We derive that, conditioned on the number of customers, the remaining service requirements of the various customers are independent and distributed according to the forward recurrence times. In addition, we show that the scaled holding cost stochastically reduces as more preference is given according to the mean forward recurrence times of the service requirements. In Chapters 3–7 we study the linear bandwidth-sharing network. This network provides a natural modeling framework for the dynamic flow-level interaction among data transfers in wired communication networks. It models the bandwidth sharing of data traffic that traverses multiple links and the cross traffic it meets on its route. Size-based scheduling policies, such as SRPT and LAS, are popular mechanisms for reducing the number of users in single-server systems by favoring smaller requests over larger ones. In Chapter 3 we prove that straightforward extensions of such policies may cause instability effects in the linear network and will therefore certainly not yield optimal performance. For networks with sufficiently many nodes, instability phenomena may in fact arise at arbitrarily low traffic loads. In Chapters 4–6 we turn to finding policies that minimize the holding cost in a linear network. In Chapter 4 we restrict the search to the class of non-anticipating policies and assume exponentially distributed service requirements. We show that simple priority rules are optimal for certain settings of the parameters of the service requirements. For the remaining cases we prove that, in the case of a two-node linear network, an average-cost optimal policy is characterized by "switching curves", i.e., the policy dynamically switches between several priority rules. Since an exact characterization of these curves is not possible in general, we study in Chapter 5 the related fluid control problem. We show that the optimal fluid control can be explicitly characterized by linear switching curves. In most cases these curves provide asymptotically fluid-optimal policies in the original stochastic model as well. For some scenarios however, fluid-based switching curves may result in a policy that is unstable. In that case, the diffusion scaling is appropriate and efficient switchingcurve policies have a square-root shape. The class of weighted a-fair bandwidth-sharing policies are commonly accepted to model the dynamic flow-level bandwidth-allocation as realized by packet-based protocols. Through numerical experiments we evaluate the performance of these policies by comparing them to asymptotically optimal policies. In Chapter 4 we find that the gap between a-fair policies and optimal policies is not that large provided the system load is moderate. In addition, the performance under a-fair policies is quite insensitive to a, as long as this value is not too small. In Chapter 5 we observe that weighted a-fair policies can approach the optimal performance when choosingthe weights appropriately. In Chapter 6 we consider a linear network with generally distributed service requirements and allow anticipating policies. We focus on policies that allocate the capacity across the classes such that stability of the system is guaranteed. Motivated by the size-based scheduling results for single-server systems, we then prioritize within a class the large requests over the small ones. These size-based scheduling policies are proven to be asymptotically optimal in a heavy-traffic setting for service requirements with bounded support. In addition, we show that these policies may outperform a-fair policies, which are non-anticipating, by an arbitrarily large factor when the load is sufficiently high. In Chapter 7 we first focus on a multi-class queueing system with general interarrival times and service requirements, and give sufficient conditions in order to compare sample-path wise the workload and the number of users under different policies. This allows us to evaluate the performance of the system under various policies in terms of stability and the mean holding cost. We then apply this framework to the linear network under weighted a-fair policies. We obtain stability results and, in the case of exponentially distributed service requirements, establish monotonicity of the mean holding cost with respect to the fairness parameter a and the relative weights. In addition, we investigate the monotonicity properties in a heavytraffic regime and perform numerical experiments. Furthermore, for a single-server system with two user classes we obtain that under DPS and GPS the mean holding cost is monotone with respect to their relative weights. This result is in line with the monotonicity result for DPS under a heavy-traffic setting as obtained in Chapter 2. In Chapter 8 we focus on a parallel two-servermodel with two classes of users with exponentially distributed service requirements. The study of this model is motivated by scheduling questions in wireless cellular communication networks. It may model for example the power control of two interfering base stations. For certain choices of the parameters of the service requirements we give an exact characterization of an optimal policy. For the remaining cases we study the related deterministic fluid control model for which we show that the optimal control is described by a switching curve. Using similar techniques as in Chapter 5, we prove that policies characterized by either linear or exponential switching curves are asymptotically fluid-optimal in the original stochastic model. For a moderately-loaded system, we numerically compare these fluid-based policies with Max-Weight and threshold-based policies, which are known to be optimal in a heavy-traffic setting. We observe that the fluidbased and the threshold-based policies perform well, while significant performance gains can be achieved over Max-Weight policies
State of the art of prosthesis simulators for the upper limb: A narrative review
No full textBackground: Research into prosthesis training and design puts a burden on the small population of people with upper-limb absence who can participate in these studies. One solution is to use a prosthetic hand simulator, which allows for attaching a hand prosthesis to an intact limb. However, whether the results of prosthesis simulator studies can be translated to people with upper-limb absence using a hand prosthesis is unclear. Objective: To review the literature on prosthetic hand simulators, provide an overview of current designs, and highlight the differences and similarities between prosthesis simulators and traditional prostheses. Methods: A Boolean combination of keywords was used to search 3 electronic databases: PubMed, Scopus and Web of Science. Relevant articles in English were selected. Results: In total, 52 papers were included in the review, and an overview of the state of the art was presented. We identified the key differences between prosthesis simulators and traditional prostheses as the position of the terminal device and the available degrees of freedom of the arm and (prosthetic) wrist. Conclusions: This paper provides an overview of prosthesis simulator designs over the past 27 years and an overview of the similarities and differences between prosthesis simulators and prostheses. The literature does not provide enough evidence to establish whether the results obtained from simulator studies could be translated to prostheses. A recommendation for future simulator design is to constrain pro- and supination of the forearm of anatomically intact participants and add a prosthetic wrist that can pro- and supinate. Additional research is required to find the ideal terminal device position for a prosthesis simulator with respect to the person's hand.Medical Instruments & Bio-Inspired Technolog
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 2)
No full textInternational audience8 articles in this issu
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 1)
No full textInternational audience10 articles in this issu
QUESTA special volume on ‘Current Trends in Queueing Theory' of the second ECQT conference (Part 2)
No full textInternational audience8 articles in this issu
Markov-modulated M/G/1-type queue in heavy traffic and its application to time-sharing disciplines
No full textThis paper deals with a single-server queue with modulated arrivals, service requirements and service capacity. In our first result, we derive the mean of the total workload assuming generally distributed service requirements and any service discipline which does not depend on the modulating environment. We then show that the workload is exponentially distributed under heavy-traffic scaling. In our second result, we focus on the discriminatory processor sharing (DPS) discipline. Assuming exponential, class-dependent service requirements, we show that the joint distribution of the queue lengths of different customer classes under DPS undergoes a state-space collapse when subject to heavy-traffic scaling. That is, the limiting distribution of the queue-length vector is shown to be exponential, times a deterministic vector. The distribution of the scaled workload, as derived for general service disciplines, is a key quantity in the proof of the state-space collapse
Interpolation approximations for the steady-state distribution in multi-class resource-sharing systems
No full textInternational audienceWe consider a single-server multi-class queue that implements relative priorities among customers of the various classes. The discipline might serve one customer at a time in a non-preemptive way, or serve all customers simultaneously. The analysis of the steady-state distribution of the queue-length and the waiting time in such systems is complex and closed-form results are available only in particular cases. We therefore set out to develop approximations for the steady-state distribution of these performance metrics. We first analyze the performance in light traffic. Using known results in the heavy-traffic regime, we then show how to develop an interpolation-based approximation that is valid for any load in the system. An advantage of the approach taken is that it is not model dependent and hence could potentially be applied to other complex queueing models. We numerically assess the accuracy of the interpolation approximation through the first and second moments
Dynamic fluid-based scheduling in a multi-class abandonment queue
No full textInternational audienceWe investigate how to share a common resource among multiple classes of customers in the presence of abandonments. We consider two different models: (1) customers can abandon both while waiting in the queue and while being served, (2) only customers that are in the queue can abandon. Given the complexity of the stochastic optimization problem we propose a fluid model as a deterministic approximation. For the overload case we directly obtain that the c˜µ/θ rule is optimal. For the underload case we use Pontryagin’s Maximum Principle to obtain the optimal solution for two classes of customers; there exists a switching curve that splits the two-dimensional state-space into two regions such that when the number of customers in both classes is sufficiently small the optimal policy follows the c˜µ-rule and when the number of customers is sufficiently large the optimal policy follows the c˜µ/θ-rule. The same structure is observed in the optimal policy of the stochastic model for an arbitrary number of classes. Based on this we develop a heuristic and by numerical experiments we evaluate its performance and compare it to several index policies. We observe that the suboptimality gap of our solution is small
- …
