Flow coupling and stochastic ordering of throughputs in linear networks

Abstract

Robust estimates for the performance of complicated queueing networks can be obtained by showing that the number of jobs in the network is stochastically comparable to a simpler, analytically tractable reference network. Classical coupling results on stochastic ordering of network populations require strong monotonicity assumptions which are often violated in practice. However, in most real-world applications we care more about what goes through a network than whatsits inside it. This paper describes a new approach for ordering flows instead of populations by augmenting network states with their associated flow counting processes and deriving Markov couplings of the augmented state-flow processes.

Keywords

• flow coupling
• non-markov coupling
• strong order
• stochastic comparison
• stochastic domination
• stochastic monotonicity