"Pay bursts only once" does not hold for non-FIFO Guaranteed Rate nodes

We demonstrate that, contrary to what is generally believed, the existing end-to-end delay bounds apply only to GR nodes that are FIFO per flow. We show this by exhibiting a counter-example. Then we show that the proof of the existing bounds has a subtle, but important, dependency on the FIFO assumption, which was never noticed before. Finally, we give a tight delay bound that is valid in the non-FIFO case; it is noticeably higher that the existing one. In particular, the phenomenon known as ?pay bursts only once? does not apply to non-FIFO nodes. These findings are important in the context of differentiated services. Indeed the existing bounds have been applied to cases where a flow (in the sense of the GR definition) is an aggregate of end-user microflows, and it is not generally true that a router is FIFO per aggregate; thus the GR node model of a differentiated services router cannot always be assumed to be FIFO per flow.