Abstract | dc.description.abstract | We look at routing and scheduling problems on Kelly type networks where the injection
process is under the control of an adversary. The novelty of the model we consider is that
the adversary injects requests of distinct types. Resources are subject to switch-over delays
or setups when they begin servicing a new request class. In this new setting, we study
the behavior of sensible policies as introduced by Dai and Jennings [J. Dai, O. Jennings,
Stabilizing queueing networks with setups, Math. Oper. Res. (2004) 891 922].
We first show that the model is robust in the sense that under some mild conditions
universal stability of work conserving packet routing protocols is preserved for natural
variants of the underlying model. Also, the model's equivalence to so called token networks
is established.
We adapt to the multi-type request and setup setting, standard arguments for proving
stability. Nevertheless, we provide counterexamples that show that for several reasonable
adaptations of contention resolution protocols to the multi-type case, stability results do
not carry over from the single-type scenario. This motivates us to explore fluid model based
arguments that could be used for proving stability for a given network. Specifically we show
analogues of results obtained by Gamarnik [D. Gamarnik, Stability of adversarial queues via
fluid model, in: Proc. of the 39th Annual Symposium on Foundations of Computer Science,
1998, pp. 60-70] but in the multi-type request with setups scenario. | en_US |