A Skorokhod map on measure-valued paths with applications to priority queues

DOI10.1214/17-AAP1309MaRDI QIDQ1751972zbMATH OpenWikidataFDO

Authors Rami Atar, Anup Biswas, Haya Kaspi, Kavita Ramanan

Publication date 25 May 2018

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.04874

zbMATH Keywords

law of large numbersfluid limitsmeasure-valued processesfluid modelspriority queueingearliest-deadline-firstSkorokhod mapmeasure-valued Skorokhod mapshortest-job-firstshortest-remaining-processing time

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Random measures (60G57)

Abstract: The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element $zeta$ of a certain class of c`{a}dl`{a}g paths that take values in the space of signed measures on the half-line to a c`{a}dl`{a}g path that takes values in the space of non-negative measures on $[0,infty)$ in such a way that for each $x>0$, the path $tmapstozet{a}_t[0,x]$ is transformed via a Skorokhod map on the half-line, and the regulating functions for different $x>0$ are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. Three such well known models are the earliest-deadline-first, the shortest-job-first and the shortest-remaining-processing-time scheduling policies. For these applications, we show how the map provides a unified framework within which to form fluid model equations, prove uniqueness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches.

Recommendations

• Double Skorokhod Map and Reneging Real-Time Queues
• Skorohod-Loynes characterizations of queueing, fluid, and inventory processes
• Stationarity of measure-valued stochastic recursions: Applications to the pure delay system and the SRPT queue
• Large deviations of the steady-state distribution of reflected processes with applications to queueing systems
• A Skorokhod problem formulation and large deviation analysis of a processor sharing model

Cites work

• scientific article; zbMATH DE number 4207183 (Why is no real title available?)
• scientific article; zbMATH DE number 3951715 (Why is no real title available?)
• scientific article; zbMATH DE number 193631 (Why is no real title available?)
• scientific article; zbMATH DE number 1834045 (Why is no real title available?)
• scientific article; zbMATH DE number 3342557 (Why is no real title available?)
• An explicit formula for the Skorokhod map on \([0,a]\)
• Diffusion approximation for a processor sharing queue in heavy traffic.
• Diffusion limits for shortest remaining processing time queues
• Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling
• Double Skorokhod Map and Reneging Real-Time Queues
• Fluid Limits of G/G/1+G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline
• Fluid limit of a heavily loaded EDF queue with impatient customers
• Fluid limits for many-server systems with reneging under a priority policy
• Fluid limits for shortest remaining processing time queues
• Fluid limits of many-server queues with reneging
• Heavy traffic analysis for EDF queues with reneging
• Invariance of fluid limits for the shortest remaining processing time and shortest job first policies
• Invariant states for fluid models of EDF networks: nonlinear lifting map
• Law of Large Number Limits of Limited Processor-Sharing Queues
• Law of large numbers limits for many-server queues
• On queues with impatience: stability, and the optimality of earliest deadline first
• On the Skorokhod topology
• Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Reflected diffusions defined via the extended Skorokhod map
• Regulating functions on partially ordered sets
• Robust Statistics
• SPDE limits of many-server queues
• Stability of earliest-due-date, first-served queueing networks
• Stability of two families of real-time queueing networks
• The fluid limit of a heavily loaded processor sharing queue
• Waiting time distributions in the accumulating priority queue

Cited in

(10)

• Minimal and locally edge minimal fluid models for resource-sharing networks
• Local edge minimality of SRPT networks with shared resources
• Instability of SRPT, SERPT and SJF multiclass queueing networks
• Law of large numbers for the many-server earliest-deadline-first queue
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Fluid limits for earliest-deadline-first networks
• Fluid limits for shortest job first with aging
• Double Skorokhod Map and Reneging Real-Time Queues
• Stability of linear EDF networks with resource sharing
• Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions

This page was built for publication: A Skorokhod map on measure-valued paths with applications to priority queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751972)