Operations Research seminar

Operations Research seminar

Decoding delay in network coded multipath transmissions

Berksan S╠žerbetci, UT-EWI-SOR


We investigate the decoding delay performance of a communication network in which a single source is transmitting data packets to a single receiver via multiple routers. New data packets arrive at the source according to a Poisson process. The intermediate network consists of two routers that receive packets from the source and forward these to the receiver. The source and the routers have exponential service rates with different parameters. The source transmits network coded packets through the network. In particular, at each transmission opportunity, the source transmits a random linear combination over all data packets that are present at the source at that time. Each network coded packet is then transmitted to one of the routers with probabilistic routing. Once a network coded packet is transmitted to one of the routers, the source drops the data packet that is located at the front of the queue.

As the receiver obtains network coded packets from multiple routers, it is necessary to decode these network coded packets in order to retrieve the data packets. Decoding is only possible when the number of network coded packets is at least equal to the number of data packets involved in the received linear combinations. We show that once the source queue becomes empty and all network coded packets that have been generated so far have been received by the receiver, it decodes all these network coded packets and retrieve data packets.

This work mainly focuses on analyzing the delay where the delay is defined as the time between arrival of a data packet at the source and decoding of all the packets served in the busy period of the source queue starting from the arrival of that data packet. We show that the delay can be expressed in closed form.