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

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 13 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.