On the large deviation of resequencing queue size: 2-M/M/1 case

Protocols such as TCP require packets to be accepted, i.e., delivered to the receiving application, in the order they are transmitted at the sender. Packets that arrive at the receiving host may be mis-ordered for reasons such as retransmission of dropped packets or multi-path routing. In order to deliver the arrived packets in sequence, the receiver's transport layer is responsible to temporarily buffer out-of-order packets and to resequence them as more packets arrive. We analyze a model where the mis-ordering is caused by multi-path routing. Packets are generated according to a Poisson process. Then, they arrive at a disordering network modelled by two parallel M/M/1 queues, and are routed to each of the queues according to an independent Bernoulli process. A resequencing buffer follows the disordering network. In such a model, the packet resequencing delay is known. However, the size of the resequencing queue is unknown. We derive the probability for the large deviation of the queue size.