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

DOI10.1214/17-AAP1309zbMATH Open1391.60220arXiv1604.04874WikidataQ130161060 ScholiaQ130161060MaRDI QIDQ1751972FDOQ1751972

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)

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.

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

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

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)

Cites Work

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

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)