اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAccuracy of state space collapse for earliest-deadline-first Queues
125
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This paper presents a second-order heavy traffic analysis of a single server queue that processes customers having deadlines using the earliest-deadline-first scheduling policy. For such systems, referred to as real-time queueing systems, performance is measured by the fraction of customers who meet their deadline, rather than more traditional performance measures, such as customer delay, queue length or server utilization. To model such systems, one must keep track of customer lead times (the time remaining until a customer deadline elapses) or equivalent information. This paper reviews the earlier heavy traffic analysis of such systems that provided approximations to the systems behavior. The main result of this paper is the development of a second-order analysis that gives the accuracy of the approximations and the rate of convergence of the sequence of real-time queueing systems to its heavy traffic limit.
قيم البحث
اقرأ أيضاً
This paper analyzes fluid scale asymptotics of two models of generalized Jackson networks employing the earliest deadline first (EDF) policy. One applies the soft EDF policy, where deadlines are used to determine priority but jobs do not renege, and
the other implements hard EDF, where jobs renege when deadlines expire, and deadlines are postponed with each migration to a new station. The arrival rates, deadline distribution and service capacity are allowed to fluctuate over time at the fluid scale. Earlier work on EDF network fluid limits, used as a tool to obtain stability of these networks, addressed only the soft version of the policy, and moreover did not contain a full fluid limit result. In this paper, tools that extend the notion of the measure-valued Skorokhod map are developed and used to establish for the first time fluid limits for both the soft and hard EDF network models.
This paper presents a heavy traffic analysis of the behavior of multi-class acyclic queueing networks in which the customers have deadlines. We assume the queueing system consists of J stations, and there are K different customer classes. Customers f
rom each class arrive to the network according to independent renewal processes. The customers from each class are assigned a random deadline drawn from a deadline distribution associated with that class and they move from station to station according to a fixed acyclic route. The customers at a given node are processed according to the earliest-deadline-first (EDF) queue discipline. At any time, the customers of each type at each node have a lead time, the time until their deadline lapses. We model these lead times as a random counting measure on the real line. Under heavy traffic conditions and suitable scaling, it is proved that the measure-valued lead-time process converges to a deterministic function of the workload process.
A many-server queue operating under the earliest deadline first discipline, where the distributions of service time and deadline are generic, is studied at the law of large numbers scale. Fluid model equations, formulated in terms of the many-server
transport equation and the recently introduced measure-valued Skorohod map, are proposed as a means of characterizing the limit. The main results are the uniqueness of solutions to these equations, and the law of large numbers scale convergence to the solutions.
In this paper we analyze the distributional properties of a busy period in an on-off fluid queue and the a first passage time in a fluid queue driven by a finite state Markov process. In particular, we show that in Anick-Mitra-Sondhi model the first
passage time has a IFR distribution and the busy period has a DFR distribution.
This work considers a many-server queueing system in which customers with i.i.d., generally distributed service times enter service in the order of arrival. The dynamics of the system is represented in terms of a process that describes the total numb
er of customers in the system, as well as a measure-valued process that keeps track of the ages of customers in service. Under mild assumptions on the service time distribution, as the number of servers goes to infinity, a law of large numbers (or fluid) limit is established for this pair of processes. The limit is characterised as the unique solution to a coupled pair of integral equations, which admits a fairly explicit representation. As a corollary, the fluid limits of several other functionals of interest, such as the waiting time, are also obtained. Furthermore, in the time-homogeneous setting, the fluid limit is shown to converge to its equilibrium. Along the way, some results of independent interest are obtained, including a continuous mapping result and a maximality property of the fluid limit. A motivation for studying these systems is that they arise as models of computer data systems and call centers.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
