Continuity and monotonicity of solutions to a greedy maximization problem
- PDF / 856,853 Bytes
- 44 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 235 Views
Continuity and monotonicity of solutions to a greedy maximization problem Łukasz Kruk1 Received: 12 June 2019 / Revised: 2 December 2019 © The Author(s) 2020
Abstract Motivated by an application to resource sharing network modelling, we consider a problem of greedy maximization (i.e., maximization of the consecutive minima) of a vector in Rn , with the admissible set indexed by the time parameter. The structure of the constraints depends on the underlying network topology. We investigate continuity and monotonicity of the resulting maximizers with respect to time. Our results have important consequences for fluid models of the corresponding networks which are optimal, in the appropriate sense, with respect to handling real-time transmission requests. Keywords Partial order · Greedy maximization · Continuity · Monotonicity · Resource sharing · Fluid model Mathematics Subject Classification 06A06 · 26A15 · 26A48 · 68M20 · 90B10 · 90C35
1 Introduction Starting from seminal papers of Rybko and Stolyar (1992), Dai (1995), Bramson (1996a, b, 1998) and other authors, fluid models have become a standard tool in investigating long-time behaviour of complicated queueing systems. Such models are useful for establishing stability and obtaining hydrodynamic or diffusion limits for multiclass queueing networks and resource sharing networks with various service protocols. Using a similar methodology in the case of real-time earliest deadline first (EDF) networks with resource sharing is hindered by the lack of suitable fluid model equations. To overcome this difficulty, Kruk (2017) suggested the definition of fluid models for
B 1
Łukasz Kruk [email protected] Department of Mathematics, Maria Curie-Skłodowska University, Pl. Marii Curie-Skłodowskiej 1, 20-031 Lublin, Poland
123
Ł. Kruk
these systems by means of an optimality property, called local edge minimality, which is known to characterize the EDF discipline in stochastic resource sharing networks. It turns out that the success of this approach depends on establishing suitable local properties of a vector-valued mapping F : [0, ∞) → Rn , resulting from a greedy maximization (i.e., maximization of the consecutive minima) of a vector in Rn over the admissible set At , depending on the underlying network topology and indexed by the time parameter. A convenient way to describe the value F(t) for a given t ≥ 0 is to define it as the maximal element of At with respect to a suitable “min-sensitive” partial ordering. Roughly speaking, the function F, when well behaved, determines the so-called frontiers (i.e., the left endpoints of the supports) of the states in the corresponding locally edge minimal fluid model [see Definition 3 and formula (10), to follow]. Recall that in a stochastic EDF queueing system, the frontier is the largest lead time of a customer who has ever been in service. The idea of using frontiers for the asymptotics of EDF systems dates back to the paper of Doytchinov et al. (2001) on a G/G/1 queue, and it has been used several times since then. H
Data Loading...
