Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFluid limits for earliest-deadline-first networks
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 from 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.
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.
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.
The paper presents a phenomenon occurring in population processes that start near zero and have large carrying capacity. By the classical result of Kurtz~(1970), such processes, normalized by the carrying capacity, converge on finite intervals to the solutions of ordinary differential equations, also known as the fluid limit. When the initial population is small relative to carrying capacity, this limit is trivial. Here we show that, viewed at suitably chosen times increasing to infinity, the process converges to the fluid limit, governed by the same dynamics, but with a random initial condition. This random initial condition is related to the martingale limit of an associated linear birth and death process.
In this paper, we adopt the fluid limits to analyze Age of Information (AoI) in a wireless multiaccess network with many users. We consider the case wherein users have heterogeneous i.i.d. channel conditions and the statuses are generate-at-will. Convergence of the AoI occupancy measure to the fluid limit, represented by a Partial Derivative Equation (PDE), is proved within an approximation error inversely proportional to the number of users. Global convergence to the equilibrium of the PDE, i.e., stationary AoI distribution, is also proved. Based on this framework, it is shown that an existing AoI lower bound in the literature is in fact asymptotically tight, and a simple threshold policy, with the thresholds explicitly derived, achieves the optimum asymptotically. The proposed threshold-based policy is also much easier to decentralize than the widely-known index-based policies which require comparing user indices. To showcase the usability of the framework, we also use it to analyze the average non-linear AoI functions (with power and logarithm forms) in wireless networks. Again, explicit optimal threshold-based policies are derived, and average age functions proven. Simulation results show that even when the number of users is limited, e.g., $10$, the proposed policy and analysis are still effective.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
