Mostrando recursos 1 - 20 de 66

  1. Heavy traffic queue length behavior in a switch under the MaxWeight algorithm

    Maguluri, Siva Theja; Srikant, R.
    We consider a switch operating under the MaxWeight scheduling algorithm, under any traffic pattern such that all the ports are loaded. This system is interesting to study since the queue lengths exhibit a multi-dimensional state-space collapse in the heavy-traffic regime. We use a Lyapunov-type drift technique to characterize the heavy-traffic behavior of the expectation of the sum queue lengths in steady-state, under the assumption that all ports are saturated and all queues receive non-zero traffic. Under these conditions, we show that the heavy-traffic scaled queue length is given by $(1-\frac{1}{2n})||\sigma||^{2}$, where $\sigma$ is the vector of the standard deviations of...

  2. Chattering and congestion collapse in an overload switching control

    Perry, Ohad; Whitt, Ward
    Routing mechanisms for stochastic networks are often designed to produce state space collapse (SSC) in a heavy-traffic limit, i.e., to confine the limiting process to a lower-dimensional subset of its full state space. In a fluid limit, a control producing asymptotic SSC corresponds to an ideal sliding mode control that forces the fluid trajectories to a lower-dimensional sliding manifold. Within deterministic dynamical systems theory, it is well known that sliding-mode controls can cause the system to chatter back and forth along the sliding manifold due to delays in activation of the control. For the prelimit stochastic system, chattering implies fluid-scaled...

  3. Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay

    Mukhopadhyay, Arpan; Karthik, A.; Mazumdar, Ravi R.
    We consider the problem of assignning jobs to servers in a multi-server system consisting of $N$ parallel processor sharing servers, categorized into $M$ ($\ll N$) different types according to their processing capacities or speeds. Jobs of random sizes arrive at the system according to a Poisson process with rate $N\lambda$. Upon each arrival, some servers of each type are sampled uniformly at random. The job is then assigned to one of the sampled servers based on their states. We propose two schemes, which differ in the metric for choosing the destination server for each arriving job. Our aim is to...

  4. Dynamic scheduling for parallel server systems in heavy traffic: Graphical structure, decoupled workload matrix and some sufficient conditions for solvability of the Brownian control problem

    Pesic, V.; Williams, R. J.
    We consider a dynamic scheduling problem for parallel server systems. J. M. Harrison has proposed a scheme for using diffusion control problems to approximately solve such control problems for heavily loaded systems. This approach has been very successfully used in the special case when the diffusion control problem can be reduced to an equivalent one for a one-dimensional workload process. However, it remains a challenging open problem to make substantial progress on using Harrison’s scheme when the workload process is more than one-dimensional. Here we present some new structural results concerning the diffusion control problem for parallel server systems with...

  5. On queue-size scaling for input-queued switches

    Shah, D.; Tsitsiklis, J. N.; Zhong, Y.
    We study the optimal scaling of the expected total queue size in an $n\times n$ input-queued switch, as a function of the number of ports $n$ and the load factor $\rho$, which has been conjectured to be $\Theta(n/{(}1-\rho{)})$ (cf. [15]). In a recent work [16], the validity of this conjecture has been established for the regime where $1-\rho=O(1/n^{2})$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O\big(n^{1.5}(1-\rho)^{-1}\log\big(1/(1-\rho)\big)\big)$ when $1-\rho=O(1/n)$. This is an improvement over the state of the...

  6. Giant component in random multipartite graphs with given degree sequences

    Gamarnik, David; Misra, Sidhant
    We study the problem of the existence of a giant component in a random multipartite graph. We consider a random multipartite graph with $p$ parts generated according to a given degree sequence $n_{i}^{\mathbf{d}}(n),n\ge1$ which denotes the number of vertices in part $i$ of the multipartite graph with degree given by the vector $\mathbf{d}$ in an $n$-node graph. We assume that the empirical distribution of the degree sequence converges to a limiting probability distribution. Under certain mild regularity assumptions, we characterize the conditions under which, with high probability, there exists a component of linear size. The characterization involves checking whether the...

  7. Solving the drift control problem

    Ormeci Matoglu, Melda; Vande Vate, John; Wang, Huizhu
    We model the problem of managing capacity in a build-to-order environment as a Brownian drift control problem. We formulate a structured linear program that models a practical discretization of the problem and exploit a strong relationship between relative value functions and dual solutions to develop a functional lower bound for the continuous problem from a dual solution to the discrete problem. Refining the discretization proves a functional strong duality for the continuous problem. The linear programming formulation is so badly scaled, however, that solving it is beyond the capabilities of standard solvers. By demonstrating the equivalence between strongly feasible bases...

  8. On bid-price controls for network revenue management

    Ata, Barış; Akan, Mustafa
    We consider a network revenue management problem and advance its dual formulation. The dual formulation reveals that the (optimal) shadow price of capacity forms a nonnegative martingale. This result is proved under minimal assumptions on network topology and stochastic nature of demand, allowing an arbitrary statistical dependence structure across time and products. Next, we consider a quadratic perturbation of the network revenue management problem and show that a simple (perturbed) bid-price control is optimal for the perturbed problem; and it is $\varepsilon$-optimal for the original network revenue management problem. Finally, we consider a predictable version of this control, where the...

  9. Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime

    Stolyar, Alexander L.
    A large-scale flexible service system with two large server pools and two types of customers is considered. Servers in pool 1 can only serve type 1 customers, while server in pool 2 are flexible – they can serve both types 1 and 2. (This is a so-called “N-system.”) The customer arrival processes are Poisson and customer service requirements are independent exponentially distributed. The service rate of a customer depends both on its type and the pool where it is served. A priority service discipline, where type 2 has priority in pool 2, and type 1 prefers pool 1, is considered....

  10. Models with hidden regular variation: Generation and detection

    Das, Bikramjit; Resnick, Sidney I.
    We review the notions of multivariate regular variation (MRV) and hidden regular variation (HRV) for distributions of random vectors and then discuss methods for generating models exhibiting both properties concentrating on the non-negative orthant in dimension two. Furthermore we suggest diagnostic techniques that detect these properties in multivariate data and indicate when models exhibiting both MRV and HRV are plausible fits for the data. We illustrate our techniques on simulated data, as well as two real Internet data sets.

  11. On patient flow in hospitals: A data-based queueing-science perspective

    Armony, Mor; Israelit, Shlomo; Mandelbaum, Avishai; Marmor, Yariv N.; Tseytlin, Yulia; Yom-Tov, Galit B.
    Hospitals are complex systems with essential societal benefits and huge mounting costs. These costs are exacerbated by inefficiencies in hospital processes, which are often manifested by congestion and long delays in patient care. Thus, a queueing-network view of patient flow in hospitals is natural for studying and improving its performance. The goal of our research is to explore patient flow data through the lens of a queueing scientist. The means is exploratory data analysis (EDA) in a large Israeli hospital, which reveals important features that are not readily explainable by existing models. ¶ Questions raised by our EDA include: Can a simple...

  12. Control of parallel non-observable queues: Asymptotic equivalence and optimality of periodic policies

    Anselmi, Jonatha; Gaujal, Bruno; Nesti, Tommaso
    We consider a queueing system composed of a dispatcher that routes jobs to a set of non-observable queues working in parallel. In this setting, the fundamental problem is which policy should the dispatcher implement to minimize the stationary mean waiting time of the incoming jobs. We present a structural property that holds in the classic scaling of the system where the network demand (arrival rate of jobs) grows proportionally with the number of queues. Assuming that each queue of type $r$ is replicated $k$ times, we consider a set of policies that are periodic with period $k\sum_{r}p_{r}$ and such that...

  13. Moderate deviations for recursive stochastic algorithms

    Dupuis, Paul; Johnson, Dane
    We prove a moderate deviation principle for the continuous time interpolation of discrete time recursive stochastic processes. The methods of proof are somewhat different from the corresponding large deviation result, and in particular the proof of the upper bound is more complicated.

  14. The morphing of fluid queues into Markov-modulated Brownian motion

    Latouche, Guy; Nguyen, Giang T.
    Ramaswami showed recently that standard Brownian motion arises as the limit of a family of Markov-modulated linear fluid processes. We pursue this analysis with a fluid approximation for Markov-modulated Brownian motion. We follow a Markov-renewal approach and we prove that the stationary distribution of a Markov-modulated Brownian motion reflected at zero is the limit from the well-analyzed stationary distribution of approximating linear fluid processes. Thus, we provide a new approach for obtaining the stationary distribution of a reflected MMBM without time-reversal or solving partial differential equations. Our results open the way to the analysis of more complex Markov-modulated processes. ¶ Key matrices...

  15. Diffusion models for double-ended queues with renewal arrival processes

    Liu, Xin; Gong, Qi; Kulkarni, Vidyadhar G.
    We study a double-ended queue where buyers and sellers arrive to conduct trades. When there is a pair of buyer and seller in the system, they immediately transact a trade and leave. Thus there cannot be a non-zero number of buyers and sellers simultaneously in the system. We assume that sellers and buyers arrive at the system according to independent renewal processes, and they would leave the system after independent exponential patience times. We establish fluid and diffusion approximations for the queue length process under a suitable asymptotic regime. The fluid limit is the solution of an ordinary differential equation,...

  16. An asymptotic optimality result for the multiclass queue with finite buffers in heavy traffic

    Atar, Rami; Shifrin, Mark
    For a multiclass G/G/1 queue with finite buffers, admission and scheduling control, and holding and rejection costs, we construct a policy that is asymptotically optimal in the heavy traffic limit. The policy is specified in terms of a single parameter which constitutes the free boundary point from the Harrison-Taksar free boundary problem, but otherwise depends explicitly on the problem data. The $c\mu$ priority rule is also used by the policy, but in a way that is novel, and, in particular, different than that used in problems with infinite buffers. We also address an analogous problem where buffer constraints are replaced...

  17. Resource sharing networks: Overview and an open problem

    Harrison, J. Michael; Mandayam, Chinmoy; Shah, Devavrat; Yang, Yang
    This paper provides an overview of the resource sharing networks introduced by Massoulié and Roberts [20] to model the dynamic behavior of Internet flows. Striving to separate the model class from the applications that motivated its development, we assume no prior knowledge of communication networks. The paper also presents an open problem, along with simulation results, a formal analysis, and a selective literature review that provide context and motivation. The open problem is to devise a policy for dynamic resource allocation that achieves what we call hierarchical greedy ideal (HGI) performance in the heavy traffic limit. The existence of such...

  18. On the dynamic control of matching queues

    Gurvich, Itai; Ward, Amy
    We consider the optimal control of matching queues with random arrivals. In this model, items arrive to dedicated queues, and wait to be matched with items from other (possibly multiple) queues. A match type corresponds to the set of item classes required for a match. Once a decision has been made to perform a match, the matching itself is instantaneous and the matched items depart from the system. We consider the problem of minimizing finite-horizon cumulative holding costs. The controller must decide which matchings to execute given multiple options. In principle, the controller may choose to wait until some “inventory”...

  19. Bandwidth sharing networks with multiscale traffic

    Feuillet, Mathieu; Jonckheere, Matthieu; Prabhu, Balakrishna
    In multi-class communication networks, traffic surges due to one class of users can significantly degrade the performance for other classes. During these transient periods, it is thus of crucial importance to implement priority mechanisms that conserve the quality of service experienced by the affected classes, while ensuring that the temporarily unstable class is not entirely neglected. In this paper, we examine the complex interaction occurring between several classes of traffic when classes obtain bandwidth proportionally to their incoming traffic. We characterize the evolution of the performance measures of the network from the moment the initial surge takes place until the...

  20. A two-dimensional, two-sided Euler inversion algorithm with computable error bounds and its financial applications

    Cai, Ning; Shi, Chao
    In this paper we propose an inversion algorithm with computable error bounds for two-dimensional, two-sided Laplace transforms. The algorithm consists of two discretization parameters and two truncation parameters. Based on the computable error bounds, we can select these parameters appropriately to achieve any desired accuracy. Hence this algorithm is particularly useful to provide benchmarks. In many cases, the error bounds decay quickly (e.g., exponentially), making the algorithm very efficient. We apply this algorithm to price exotic options such as spread options and barrier options under various asset pricing models as well as to evaluate the joint cumulative distribution functions of...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.