Stochastic comparisons for a static routing problem with resequencing

Abstract

In communication networks, packets from the same source-destination pair may be routed along several paths and arrive at their receiver out of order. This often necessitates the use of a resequencing buffer at the destination. We consider such a network of parallel links with general packet arrival and service processes, and resequencing. We establish stochastic comparisons for the end-to-end delay (including the time at the resequencing buffer) in the heavy and light traffic regimes, between two different static scheduling mechanisms, namely Bernoulli and Round-Robin routing. The results show that Round-Robin outperforms Bernoulli routing, as yet another instance of the folk theorem that "determinism minimizes delays.".