Delay asymptotics and bounds for multitask parallel jobs

Queueing Systems - We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded...     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues

Scheller-Wolf [12] established necessary and sufficient conditions for finite stationary delay moments in stable FIFO GI/GI/s queues that incorporate the interaction between service time distribution, traffic intensity (ρ) and the number of servers in the queue. These conditions can be used to show that when the service time has finite first but infinite αth moment, s slow servers can give lower delays than one fast server. In this paper, we derive an alternative derivation of these moment results: Both upper bounds, that serve as sufficient conditions, and lower bounds, that serve as necessary conditions are presented. In addition, we extend the class of service time distributions for which the necessary conditions are valid. Our new derivations provide a structural interpretation of the moment bounds, giving intuition into their origin: We show that FIFO GI/GI/s delay can be represented as the minimum of (s − k) i.i.d. GI/GI/1 delays, when ρ satisfies k < ρ < k+1. AMS Subject Classification 60K25     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward

The M/M/k/setup model, where there is a penalty for turning servers on, is common in data centers, call centers, and manufacturing systems. Setup costs take the form of a time delay, and sometimes there is additionally a power penalty, as in the case of data centers. While the M/M/1/setup was exactly analyzed in 1964, no exact analysis exists to date for the M/M/k/setup with $k>1$ . In this paper, we provide the first exact, closed-form analysis for the M/M/k/setup and some of its important variants including systems in which idle servers delay for a period of time before turning off or can be put to sleep. Our analysis is made possible by a new way of combining renewal reward theory and recursive techniques to solve Markov chains with a repeating structure. Our renewal-based approach uses ideas from renewal reward theory and busy period analysis to obtain closed-form expressions for metrics of interest such as the transform of time in system and the transform of power consumed by the system. The simplicity, intuitiveness, and versatility of our renewal-based approach makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, our renewal-based approach should be used to reduce the analysis of any 2-dimensional Markov chain which is infinite in at most one dimension and repeating to the problem of solving a system of polynomial equations. In the case where all transitions in the repeating portion of the Markov chain are skip-free and all up/down arrows are unidirectional, the resulting system of equations will yield a closed-form solution.     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Strategic analysis of technology and capacity investments in the liquefied natural gas industry

Energy plays a fundamental role in both manufacturing and services, and natural gas is rapidly becoming a key energy source worldwide. Facilitating this emergence is an expanding network of ocean-going vessels that enable the matching of natural gas supply and demand on a global scale. This is achieved through the transportation of liquefied natural gas (LNG) for eventual regasification at its destination. Until very recently, only one type of technology had been available for transporting and regasifying LNG: Conventional LNG vessels coupled with land based LNG regasification. But it is now possible to transport and regasify LNG onboard special LNG vessels. Companies such as Excelerate Energy and Höegh LNG are currently developing LNG supply chains based on this new technology. Motivated by these developments, we engaged executives at Excelerate Energy to facilitate an investigation of issues related to strategic technology selection, as well as choices around technology configuration and capacity for the incumbent and emerging technologies. The resulting analysis brings to light managerial principles delineating the impact of alternative LNG throughput models on decisions regarding how to deploy each technology option and how to configure and size their capacity. Our findings have additional potential relevance beyond our industry specific analysis.     

Further delay moment results for FIFO multiserver queues

Using a new family of service disciplines, we provide weaker sufficient conditions for finite stationary delay moments in FIFO multiserver queues. This extends the work in Sigman and Scheller-Wolf [6] to GI/GI/s queues with = E[S]/E[T] s-1 are the familiar Kiefer and Wolfowitz conditions actually known to be necessary. For the case when < 1, we provide sufficient conditions for finite mean stationary delay, expressed as a function of the number of servers in the system. The limit of these conditions as s is the requirement that E[S] < , which is the condition for finite mean stationary delay in a FIFO GI/GI/ queue. Both of these results highlight the interplay between traffic intensity and service time distribution in determining the behavior of delay moments in multiserver queues.