Network codes with deadlines

We investigate the effect of decoding deadlines on network coding capacity, specifically, the capacity curve of a network as a function of the allowed delay from the time a set of bits is transmitted by the source to the time it is fully decoded by the sinks. We show that scalar linear codes are not optimal even for multicast when the data has deadlines. In fact, infinite blocklength is required in general in order to achieve the optimal performance of linear block codes in these scenarios. We study the case of two types of data, where the first type has a tighter deadline than the other. We find for an interesting family of networks the optimal linear convolutional codes. We formulate a code design criterion for general networks with two data types. Finally, as an alternative approach, we show that the problem of multicast with deadlines can be transformed into a non-multicast problem without deadlines in an extended network. Using that approach, we find an upper bound on the complexity of checking the feasibility of the problem.