Probabilistic Analysis of Resequencing Queue Length in Multipath Packet Data Networks

In multipath packet data networks, packets may reach the receiver out-of-sequence, i.e., packets arrive at the receiver in a sequence different from their egressing order at the transmitter. In practice, however, many applications require an in-sequence packet delivery, meaning that packets need to be delivered to an application on the receiver in their original order at the transmitter. The in-sequence packet delivery is usually implemented through the approach of packet resequencing. In this paper, a multipath data network with packet resequencing is modeled and the asymptotic properties of the steady-state probability distribution of the resequencing queue length are studied. The assumptions used are that the packets sent from the transmitter according to a Poisson process, and the transmission period of a packet along a route follows an exponential distribution. An asymptotic distribution function of the resequencing queue length is derived for a large queue length in the steady state of the network. Numerical and simulation examples are presented to validate the derived result. Through comparisons of large deviation and asymptotic values of the resequencing queue length distribution, we show that the asymptotic result provides a better approximation to the distribution function of the resequencing queue length than the large deviation result reported in the literature.