Browsing by Subject "Diffusion approximation"

Now showing 1 - 1 of 1

Policy robustness : robust stability of multiclass queueing networks
(2024-05) Zhao, Feiyang ; Hasenbein, John J.; Gurvich, Itai, 1975-; Gurvich, Itai; Hanasusanto, Grani Adiwena; Caramanis, Constantine
Robustness has been a prominent topic for decades in the optimization literature. However, it is only a few years that robust techniques have been imported and further developed for stochastic models, particularly stochastic processing networks. A reason for this late adoption might be that “non-robust” analysis of general stochastic networks has already presented significant mathematical challenges. This dissertation focuses on the robust stability of stochastic processing networks. We re-visit the global—relative to control policies—stability of multiclass queueing networks. In these, as is known, it is generally insufficient that the nominal utilization at each server is below 100%. Certain policies, although work conserving, may destabilize a network that satisfies the nominal-load conditions; additional conditions on the primitives are needed for global stability (stability under any work-conserving policy). The global-stability region was fully characterized for two-station networks in Dai and Vande Vate (1996), but a general framework for networks with more than two stations remains elusive. In this dissertation, we offer progress on this front by considering a subset of non-idling control policies, namely queue-ratio (QR) policies. These include as special cases all static-priority policies. With this restriction, we are able to introduce a novel and complete framework that applies to networks of any size. Our framework breaks the analysis of robust QR stability (stability under any QR policy) into (i) robust state-space collapse and (ii) robust stability of the Skorohod problem (SP) representing the fluid workload. Sufficient conditions for both are specified in terms of, and make new connections to, optimization problems. We use these optimization problems to prove that the family of QR policies satisfies a weak form of convexity relative to policies. A direct implication of this convexity is that: if the SP is stable for all static-priority policies (the “extreme” QR policies), then it is also stable under any QR policy. We show how the stability of a family of policies is inherited from the stability of some “corner” policies. While robust QR stability is weaker than global stability, our framework recovers necessary and sufficient conditions for global stability in specific networks. Furthermore, we inform rules for the design of networks that are robustly stable, in particular, robust to decentralized work prioritization decisions by servers at different stations. More specifically, the idea is to identify network assembly operations that preserve stability properties when robustly stable component networks are linked to form larger robustly stable networks.