We consider network coding in applications where each packet is
labeled with a deadline and is required to be reconstructed at the
receiving end before that deadline. One of the challenges in this
scenario is to characterize the capacity curve of a network, as a
function of the packet deadlines.

In this work we design and analyze the structure of optimal codes
for networks with deadlines. First, we show that linear algebraic
scalar codes do not achieve the optimal rate of linear network
codes with deadlines. Furthermore, we show that any finite
blocklength linear code cannot in general achieve the optimal
rate-deadline performance. Specifically, we show for an example
network that when the source is required to transmit data at the
multicast capacity of the network, linear convolutional codes with
infinite blocklength achieve a strictly smaller deadline than any
linear code with finite blocklength. Additionally, we show that
for that simple example, the rate-deadline performance of
convolutional codes is in fact optimal. This might indicate the
convolutional codes are more adequate for networks with deadline.

While most of the work focuses on the case of a fixed deadline for
all packets, we generalize our approach to networks with two data
types,  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.

As an alternative approach to the problem, we show that multicast
with deadlines can be represented as a non-multicast problem
without deadlines. Using this approach, we find an upper bound on
the complexity of verifying the feasibility of the problem.