Title: Strong Embeddings for Transitory Queueing Models
In this paper, we establish strong embedding theorems, in the sense of the Komlós-Major-Tusnády framework, for the performance metrics of a general class of transitory queueing models of nonstationary queueing systems. The nonstationary and non-Markovian nature of these models makes the computation of performance metrics hard. The strong embeddings yield error bounds on sample path approximations by diffusion processes in the form of functional strong approximation theorems. more »« less
Florence Merlevede and Magda Peligrad
(, Progress in probability)
Radosław Adamczak, Nathael Gozlan
(Ed.)
In this paper we survey some recent progress on the Gaussian approximation for nonstationary dependent structures via martingale methods. First we present general theorems involving projective conditions for triangular arrays of random variables and then present various applications for rho-mixing and alpha-dependent triangular arrays, stationary sequences in a random time scenery, application to the quenched FCLT, application to linear statistics with alpha-dependent innovations, application to functions of a triangular stationary Markov chain.
We consider a wireless network with a base station serving multiple traffic streams to different destinations. Packets from each stream arrive to the base station according to a stochastic process and are enqueued in a separate (per stream) queue. The queueing discipline controls which packet within each queue is available for transmission. The base station decides, at every time t, which stream to serve to the corresponding destination. The goal of scheduling decisions is to keep the information at the destinations fresh. Information freshness is captured by the Age of Information (AoI) metric. In this paper, we derive a lower bound on the AoI performance achievable by any given network operating under any queueing discipline. Then, we consider three common queueing disciplines and develop both an Optimal Stationary Randomized policy and a Max-Weight policy under each discipline. Our approach allows us to evaluate the combined impact of the stochastic arrivals, queueing discipline and scheduling policy on AoI. We evaluate the AoI performance both analytically and using simulations. Numerical results show that the performance of the Max-Weight policy is close to the analytical lower bound.
Shah, Devavrat
(, INFORMS Applied Probability Society Conference)
The property of (quasi-)reversibility of Markov chains have led to elegant characterization of steady-state distribution for complex queueing networks, e.g. celebrated Jackson networks, BCMP (Baskett, Chandi, Muntz, Palacois) and Kelly theorem. In a nutshell, despite the complicated interaction, in the steady-state, the queues in such networks exhibit independence and subsequently lead to explicit calculations of distributional properties of the queuing network that may seem impossible at the outset. The model of stochastic processing network (cf. Harrison 2000) captures variety of dynamic resource allocation problems including the flow-level networks used for modeling bandwidth sharing in the Internet, switched networks (cf. Shah, Wischik 2006) for modeling packet scheduling in the Internet router and wireless medium access, and hybrid flow-packet networks for modeling job-and-packet level scheduling in data centers. Unlike before, an appropriate resource allocation or scheduling policy is required in such networks to achieve good performance. Given the complexity, asymptotic analytic approaches such as fluid model or Lyapunov-Foster criteria to establish positive-recurrence and heavy traffic or diffusion approximation to characterize the scaled steady-state distribution became method of choice. A remarkable progress has been made along these lines over the past few decades, but there is a need for much more to match the explicit calculations in the context of reversible networks. In this work, we will present an alternative to this approach that leads to non-asymptotic, explicit characterization of steady-state distribution akin BCMP / Kelly theorems. This involves (a) identifying a "relaxation" of the given stochastic processing network in terms of an appropriate (quasi-)reversible queueing network, and (b) finding a resource allocation or scheduling policy of interest that "emulates" the "relaxed" networks within "small error". The proof is in the puddling -- we will present three examples of this program: (i) distributed scheduling in wireless network, (ii) scheduling in switched networks, and (iii) flow-packet scheduling in a data center. The notion of "baseline performance" (cf. Harrison, Mandayam, Shah, Yang 2014) will naturally emerges as a consequence of this program. We will discuss open questions pertaining multi-hop networks and computation complexity.
Chowdhury, Puja; Conrad, Philip; Bakos, Jason D.; Downey, Austin
(, ASME 2021 Conference on Smart Materials, Adaptive Structures and Intelligent Systems)
Abstract In this paper, a method for real-time forecasting of the dynamics of structures experiencing nonstationary inputs is described. This is presented as time series predictions across different timescales. The target applications include hypersonic vehicles, space launch systems, real-time prognostics, and monitoring of high-rate and energetic systems. This work presents numerical analysis and experimental results for the real-time implementation of a Fast Fourier Transform (FFT)-based approach for time series forecasting. For this preliminary study, a testbench structure that consists of a cantilever beam subjected to nonstationary inputs is used to generate experimental data. First, the data is de-trended, then the time series data is transferred into the frequency domain, and measures for frequency, amplitude, and phase are obtained. Thereafter, select frequency components are collected, transformed back to the time domain, recombined, and then the trend in the data is restored. Finally, the recombined signals are propagated into the future to the selected prediction horizon. This preliminary time series forecasting work is done offline using pre-recorded experimental data, and the FFT-based approach is implemented in a rolling window configuration. Here learning windows of 0.1, 0.5, and 1 s are considered with different computation times simulated. Results demonstrate that the proposed FFT-based approach can maintain a constant prediction horizon at 1 s with sufficient accuracy for the considered system. The performance of the system is quantified using a variety of metrics. Computational speed and prediction accuracy as a function of training time and learning window lengths are examined in this work. The algorithm configuration with the shortest learning window (0.1 s) is shown to converge faster following the nonstationary when compared to algorithm configuration with longer learning windows.
Queueing models that are used to capture various service settings typically assume that customers require a single unit of resource (server) to be processed. However, there are many service settings where such an assumption may fail to capture the heterogeneity in resource requirements of different customers. We propose a multiserver queueing model with multiple customer classes in which customers from different classes may require different amounts of resources to be served. We study the optimal scheduling policy for such systems. To balance holding costs, service rates, resource requirement, and priority-induced idleness, we develop an index-based policy that we refer to as the idle-avoid [Formula: see text] rule. For a two-class two-server model, where policy-induced idleness can have a big impact on system performance, we characterize cases where the idle-avoid [Formula: see text] rule is optimal. In other cases, we establish a uniform performance bound on the amount of suboptimality incurred by the idle-avoid [Formula: see text] rule. For general multiclass multiserver queues, we establish the asymptotic optimality of the idle-avoid [Formula: see text] rule in the many-server regime. For long-time horizons, we show that the idle-avoid [Formula: see text] is throughput optimal. Our theoretical results, along with numerical experiments, provide support for the good and robust performance of the proposed policy.
Chakraborty, Prakash, and Honnappa, Harsha. Strong Embeddings for Transitory Queueing Models. Retrieved from https://par.nsf.gov/biblio/10308776. Mathematics of Operations Research . Web. doi:10.1287/moor.2021.1158.
@article{osti_10308776,
place = {Country unknown/Code not available},
title = {Strong Embeddings for Transitory Queueing Models},
url = {https://par.nsf.gov/biblio/10308776},
DOI = {10.1287/moor.2021.1158},
abstractNote = {In this paper, we establish strong embedding theorems, in the sense of the Komlós-Major-Tusnády framework, for the performance metrics of a general class of transitory queueing models of nonstationary queueing systems. The nonstationary and non-Markovian nature of these models makes the computation of performance metrics hard. The strong embeddings yield error bounds on sample path approximations by diffusion processes in the form of functional strong approximation theorems.},
journal = {Mathematics of Operations Research},
author = {Chakraborty, Prakash and Honnappa, Harsha},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
An official website of the United States government
