Resequencing delays under multipath routing -- Asymptotics in a simple queueing model

Abstract

We study the resequencing delay caused by multipath routing. We use a queueing model which consists of parallel queues to model the network routing behavior. We define a new metric denoted by $gamma$, to study the impact of resequencing on the customer end-to-end delay. Our results characterize some properties of $gamma$ with respect to different service time distributions. In particular, the resequencing delay can be negligible when the delay along each path is light-tailed, but can be of major concern when it is heavy-tailed.