\begin{document}


\title{Optimal Streaming Erasure Codes over the Three-Node Relay Network}


\author{Silas L.~Fong, Ashish Khisti, Baochun Li, Wai-Tian Tan, Xiaoqing Zhu, and John Apostolopoulos
\thanks{S.~L.~Fong, A.~Khisti and B.~Li are with the Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON M5S 3G4, Canada (E-mails: \texttt{silas.fong@utoronto.ca}, \texttt{akhisti@ece.utoronto.ca}, \texttt{bli@ece.utoronto.edu}).}
\thanks{W.-T.~Tan, X.~Zhu and J.~Apostolopoulos are with Cisco Systems, San Jos\'e, CA 95134, USA.}


}


\maketitle


\begin{abstract}
This paper investigates low-latency streaming codes for a three-node relay network. The source transmits a sequence of messages (streaming messages) to the destination through the relay between them, where the first-hop channel from the source to the relay and the second-hop channel from the relay to the destination are subject to packet erasures. Every source message generated at a time slot must be recovered perfectly at the destination within the subsequent~$T$ time slots. In any sliding window of $T+1$ time slots, we assume no more than~$N_1$ and $N_2$ erasures are introduced by the first-hop channel and second-hop channel respectively. We fully characterize the maximum achievable rate in terms of $T$, $N_1$ and $N_2$. The achievability is proved by using a symbol-wise decode-forward strategy where the source symbols within the same message are decoded by the relay with different delays. The converse is proved by analyzing the maximum achievable rate for each channel when the erasures in the other channel are consecutive (bursty). In addition, we show that traditional message-wise decode-forward strategies, which require the source symbols within the same message to be decoded by the relay with the same delay, are sub-optimal in general.
\end{abstract}


\section{Introduction}\label{sec:introduction}


\IEEEPARstart{R}{eal}-time video streaming is an essential component for many ultra-reliable and low-latency applications over the Internet including high-definition video conferencing, augmented/virtual reality, and online gaming. Service providers for real-time video streaming are typically hosted in a public cloud, with multiple server instances running within geographically distributed data centers. Providers of public cloud content delivery service include Google Cloud, Amazon CloudFront and Microsoft Azure, who have their own cloud content delivery networks (CDNs) to support high-throughput and low-latency communications. It was recently forecasted by Cisco~\cite{CiscoWhitePaper} that 77 percent of all Internet video traffic will cross CDNs by 2021, up from 67 percent in 2016.

We consider the network model as illustrated in Figure~\ref{figureThreeNodeRelay}.
 The data centers within the same cloud are distributed across the continents, and there may not exist a direct link between two data centers which are far away from each other. For example, there is no direct link between Europe and Australia due to the absence of a direct optical fiber connection. Consider a simple relaying scenario within a cloud where a data center transmits streaming messages to another data center through an intermediate data center or other network node~\cite{KachrisTomkos2012}. The simple relaying scenario can be modeled as a source transmitting streaming messages to a destination over a three-node relay network with no direct link between the source node and the destination node, which is illustrated in Figure~\ref{figureThreeNodeRelay}. In this paper, we focus on the three-node relay network model and investigate the performance of streaming codes over the three-node network.

There are two main approaches for implementing error control over the Internet at the physical layer and the network layer: Automatic repeat request (ARQ) and forward error correction (FEC). Both ARQ and FEC can alleviate the damages of packet losses that may be caused by unreliable wireless links or congestion at network bottlenecks. However, ARQ schemes are not suitable for real-time streaming applications that involve arbitrary global users because each retransmission may incur an extra round-trip delay which may be intolerable. Specifically, correcting an erasure using ARQ results in a 3-way delay (forward + backward + forward), and this aggregate (3-way) delay including transmission, propagation and processing delays is required to be lower than~150 ms for interactive applications such as voice and video according to the International Telecommunication Union~\cite{onewayTransTime,StockhammerHannuksela2005}. Furthermore, other applications such as interactive gaming (and multi-user interactive scenarios) require even lower latencies. As an example, this aggregate delay makes ARQ impractical for communication between two distant global users with aggregate delay larger than 150~ms (even if the signals travel at the speed of light, the minimum possible aggregate delay between two diametrically opposite points on the earth's circumference is at least 200~ms~\cite{BKTAmagazine17}).


On the contrary, FEC schemes are amenable to low-latency communications among global users because no retransmission is required. Instead of using retransmissions to achieve high reliability, FEC schemes increase the correlation among the transmitted symbols by adding redundant information. Then, any erased packet may be reconstructed by the redundant information in the subsequent surviving packets. Therefore, we investigate only FEC schemes for the three-node relay network in quest of the highest coding rate.
\begin{figure}[t!]
\centering
\includegraphics[height=0.45in]{relayChannelClip.pdf}
\caption{A three-node relay network.}
\label{figureThreeNodeRelay}
\end{figure}
\subsection{Related Work}
{This paper investigates FEC schemes for interactive low-latency communication. Low-density parity-check (LDPC) and digital fountain codes~\cite{Luby2002,Shokrollahi2006} are two traditional FEC schemes that   
are currently used in the DVB-S2~\cite{DVB-S2} and DVB-IPTV~\cite{DVB-IPTV} standards for non-interactive
streaming applications.} These codes operate over long block
lengths, typically a few thousand symbols, and are thus suitable
for applications in which the delay constraints are not
stringent. However, LDPC and fountain codes are not suitable for interactive streaming applications where short block lengths (e.g., a few hundred symbols) are required due to the stringent delay constraints.


On the other hand, low-latency FEC schemes which operate over short block lengths are used in existing consumer video chat applications (e.g., Skype), which typically {use maximum-distance separable (MDS) codes} to transmit an extra parity-check packet per every two to five packets~\cite{MIT-CSAIL-TR-2010-031}. Indeed, the use of low-latency FEC schemes for protecting voice streams against packet erasures is largely attributed to the success of Skype~\cite{Skype2010}. Recently, several systematic studies have been carried out to investigate the fundamental limits of low-latency FEC schemes for a point-to-point packet erasure channel~\cite{MartinianSundberg2004,BKTA2013,FKLTZA2018,LeungHo2012, LQH2013, AdlerCassuto2017,BPKTA17}. Motivated by the simple relaying scenario as described at the beginning of this paper, we perform the first systematic study which analyzes the fundamental limits of low-latency FEC schemes for the three-node relay network.


\subsection{Network Model}\label{subsecChannelModel}
\begin{figure}[t!]
\centering
\includegraphics[height=0.5in]{relayNetworkSimpleClip.pdf}
\caption{Symbols generated by a streaming code at time~$i$.}
\label{figureThreeNodeRelayNetwork}
\end{figure}
We consider the network model as illustrated in Figure~\ref{figureThreeNodeRelayNetwork}.
A formal description will appear later in Section~\ref{sectionDefinition}. The three-node relay network consists of a source, a destination and a relay between them, which are denoted by $\mathrm{s}$, $\mathrm{d}$ and $\mathrm{r}$ respectively. The channel between node~$\mathrm{s}$ and node~$\mathrm{r}$ is denoted by $(\mathrm{s},\mathrm{r})$, and the channel between node~$\mathrm{r}$ and node~$\mathrm{d}$ is denoted by $(\mathrm{r},\mathrm{d})$. All symbols generated in the network are taken from a common finite field~$\mathbb{F}$. Suppose node~$\mathrm{s}$ sends a sequence of messages to node~$\mathrm{d}$ in a streaming manner where each message consists of~{$k\ge 0$} symbols. In each time slot, node~$\mathrm{s}$ encodes the $k$ symbols into a collection of~{$n\ge 1$} symbols followed by transmitting the~$n$ symbols through $(\mathrm{s},\mathrm{r})$. {The~$n$ transmitted symbols may depend on the current and all previous collections of~$k$ symbols. Therefore, the encoder has infinite memory.} The collection of~$n$ symbols transmitted in a time slot are either received perfectly by node~$\mathrm{r}$ or erased (lost). In the same time slot, node~$\mathrm{r}$ transmits a collection of~{$m\ge 1$} symbols through $(\mathrm{r},\mathrm{d})$, {where the~$m$ symbols may depend on the current and all previous collections of~$n$ received symbols. Therefore, node~$\mathrm{r}$ has infinite storage capacity.} {While our converse result will be established under the assumption of an infinite-memory encoder and an infinite-storage relay, our achievability scheme will use finite memory and storage.} The collection of~$m$ symbols transmitted in a time slot are either received perfectly by node~$\mathrm{d}$ or erased.
 The fraction $\frac{k}{\max\{n,m\}}$ specifies the overall coding rate, which can be interpreted as the reciprocal of the amount of time needed to simultaneously transfer one unit of information over $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$. We call the~$k$ symbols chosen by node~$\mathrm{s}$, the~$n$ symbols transmitted by node~$\mathrm{s}$, the~$n$ symbols received by node~$\mathrm{r}$, the~$m$ symbols transmitted by node~$\mathrm{r}$ and the~$m$ symbols received by node~$\mathrm{d}$ the \emph{message}, the \emph{source packet}, the \emph{relay received packet}, the \emph{relay transmitted packet} and the \emph{destination packet} respectively.
 
 Since every low-latency application is subject to a tight delay constraint, we assume that every message generated in a time slot must be decoded by node~$\mathrm{d}$ with delay~$T$, i.e., within the future~$T$ time slots.

{\subsection{Random Erasures} \label{subsecRandomErasures}
Consider the scenario where the channels~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ are subject to independent and identically distributed (i.i.d.) erasures. Let $\alpha$ and~$\beta$ denote the erasure probabilities associated with $(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ respectively. Given an average tolerable probability of decoding error denoted by~$\varepsilon$ where the average is taken over the streaming messages, we are interested in characterizing the maximum coding rate denoted by~$C_\varepsilon(T, \alpha, \beta)$. The main difficulty in characterizing~$C_\varepsilon(T, \alpha, \beta)$ is due to the delay constraint~$T$. If $T=\infty$ (i.e., no delay constraint), then the problem can be reduced to a classical information theory problem {where a simple decode-forward strategy is known to be optimal~\cite[Ch.\ 16.4]{elgamal}.}

{However, when one considers finite delays the analysis of $C_\epsilon(T, \alpha, \beta)$ becomes intractable.} Therefore, we adopt the following deterministic approach that has been used for many similar problems~\cite{MartinianSundberg2004,BKTA2013,BKTAmagazine17,BPKTA17}: We first find streaming codes that work well for correcting deterministic erasures, and then run simulations to investigate their performance in the original statistical model with random erasures. The deterministic erasure model is described as follows.

}
\subsection{{A Deterministic Erasure Model}} \label{subsecDetErasures}
On the discrete timeline, the channels $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ introduce~$N_1$ and $N_2$ erasures respectively. Under the erasure channel model described above, we are interested in characterizing the \emph{maximum achievable rate} --- the maximum coding rate $\frac{k}{\max\{n,m\}}$ for sending information over the relay network such that every message can be perfectly recovered by node~$\mathrm{d}$ with delay~$T$.

If $N_2=0$, then the three-node relay network with erasures reduces to a point-to-point packet erasure channel. It was previously known that~\cite[Sec.~IV]{BKTA2013} the maximum achievable rate of the point-to-point packet erasure channel with $N_1=N$ and $N_2=0$ denoted by~$C_{T,N}$ satisfies

\begin{align}
C_{T,N} = \begin{cases}\frac{T-N+1}{T+1} & \text{if $T\ge N$,}\\ 0 & \text{otherwise.} \end{cases} \label{capacityPTP}
\end{align}

{Although the deterministic erasure model is formulated in such a way that $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ introduce only a finite number of erasures over the discrete timeline, the maximum coding rate remains unchanged for the following sliding window model that can introduce infinite erasures: Every message must be perfectly recovered with delay~$T$ as long as the numbers of erasures introduced by $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ in every sliding window of size $T+1$ do not exceed $N_1$ and~$N_2$ respectively. In this paper, we will first derive the maximum coding rate for the deterministic model, and then extend the analysis for the sliding window model.}


\subsection{Time-Division Decode-Forward: Message-Wise vs.\ Symbol-Wise} \label{subsecRelatedWork}

A traditional relaying scheme for the three-node relay network is \emph{time-division decode-forward}~\cite[Ch.\ 16.4]{elgamal} where the relay decodes every message with delay~$T_1$ before forwarding it to the destination with an additional delay~$T_2$. We call the traditional relaying scheme described above \emph{message-wise DF} where DF stands for decode-forward. For message-wise DF, all the symbols in the same source message are decoded by the relay subject to the same delay constraint~$T_1$, and similarly all the symbols re-encoded by the relay are decoded by the destination subject to the same delay constraint~$T_2$. A more flexible relaying scheme is to let the relay decode the symbols in the same source message subject to possibly different delay constraints, and similarly let the destination decode the symbols re-encoded by the relay subject to possibly different delay constraints. We call this flexible scheme the \emph{symbol-wise DF}. By definition, every message-wise DF can be viewed as a \emph{symbol-wise DF}. The following example illustrates that symbol-wise DF can outperform message-wise~DF.
\begin{Example}
 {Consider a simple relay network where $N_1=N_2=1$ and every message must be decoded by node~$\mathrm{d}$ with delay~$T=3$.} If the message-wise DF strategy is employed at node~$\mathrm{r}$, then two point-to-point codes with respective delays $T_1$ and $T_2$ are employed for channels $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ respectively where $T_1+T_2=T=3$. Since the maximum achievable rates of channels $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ are~$C_{T_1, 1}=\frac{T_1}{T_1+1}$ and~$C_{T_2, 1}=\frac{T_2}{T_2+1}$ respectively by~\eqref{capacityPTP}, it together with the fact $T_1+T_2=3$ follows that the maximum achievable rate for message-wise DF is $\max\limits_{T_1+T_2\le 3}\min\{\frac{T_1}{T_1+1}, \frac{T_2}{T_2+1}\} = \min\{1/2, 2/3\} = 1/2$.
The following \emph{symbol-wise DF} strategy illustrated in Table~\ref{table1} exploits the delay information of each symbol received by node~$\mathrm{r}$ to outperform message-wise DF.


\begin{table}
\centering
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{5}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}
\\\hline
$a_i$ &\red{$\boxed{a_0}$} &\magenta{$a_1$} & \blue{$a_2$} &$a_3$&$a_4$\\\hline
$b_i$ & $b_0$ &$\red{\boxed{b_1}}$ & $\magenta{b_2}$ & \blue{$b_3$}&$b_4$\\\hline
$a_{i-2}+b_{i-1}$ &$0$ &$b_0$ & $\red{\boxed{a_0+b_1}}$ &\magenta{$a_1+b_2$}& \blue{$a_2+b_3$}\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{s}$ from time~$0$ to~$4$. \label{tab:tab_1}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$b_{i-1}$ &$0$ &\red{$\boxed{b_0}$} &\magenta{$b_1$} & \blue{$b_2$} &$b_3$&$b_4$\\\hline
$a_{i-2}$ &$0$ & $0$ &$\red{\boxed{a_0}}$ & $\magenta{a_1}$ & \blue{$a_2$}&$a_3$\\\hline
$a_{i-3}+b_{i-3}$ &$0$ &$0$ &$0$ & $\red{\boxed{a_0+b_0}}$ &\magenta{$a_1+b_1$}& \blue{$a_2+b_2$}\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{r}$ from time~$0$ to~$5$. \label{tab:tab_2}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$a_{i-3}$&$0$ &  $0$ & $0$ & $a_0$ &$a_1$ & $a_2$\\\hline
$b_{i-3}$&$0$ & $0$ & $0$ & $b_0$ & $b_1$ & $b_2$\\\hline
\end{tabular}
\caption{Symbols recovered by node~$\mathrm{d}$ from time~$0$ to~$5$. \label{tab:tab_3}}
\end{subtable}
\caption{A symbol-wise DF strategy for the three-node relay network with $N_1=N_2=1$ and $T=3$.}
\label{table1}
\end{table}
Suppose node~$\mathrm{s}$ transmits two bits $a_i$ and $b_i$ at each discrete time $i\ge 0$ to node~$\mathrm{d}$ with delay~$3$. For each time~$i$, node~$\mathrm{s}$ transmits the three-symbol packet $[a_i\quad b_i\quad a_{i-2}+b_{i-1}]$ according to Table~\ref{tab:tab_1} where $a_j=b_j=0$ for any $j<0$ by convention, and the symbols highlighted in the same color are generated by the same block code. Since channel $(\mathrm{s},\mathrm{r})$ introduces at most~$N_1=1$ erasure, each $a_i$ and each $b_i$ can be perfectly recovered by node~$\mathrm{r}$ by time $i+2$ and time $i+1$ respectively. Therefore at each time~$i$, node~$\mathrm{r}$ should have recovered $a_{i-2}$ and $b_{i-1}$ perfectly with delays~$2$ and~$1$ respectively, and it will re-encode them into another three-symbol packet $[b_{i-1}\quad a_{i-2}\quad b_{i-3}+a_{i-3}]$ according to Table~\ref{tab:tab_2}, where the symbols highlighted in the same color are generated by the same block code. Since $b_{i-3}$, $a_{i-3}$ and $b_{i-3}+a_{i-3}$ are transmitted by node~$\mathrm{r}$ at time $i-2$, $i-1$ and~$i$ respectively, it follows from the fact $N_2=1$ that {node~$\mathrm{d}$} can recover $a_{i-3}$ and $b_{i-3}$ by time~$i$ for each $i\ge 3$. Consequently, this symbol-wise DF strategy achieves a rate of $2/3$, which outperforms all traditional message-wise DF strategies.
 \end{Example}

\subsection{Delay Profile} \label{subsecDelayProfile}
{In this paper, we propose a symbol-wise DF scheme to achieve the maximum achievable rate over the three-node relay network with deterministic erasures. The proposed symbol-wise DF scheme has the following feature: Let~$s_i[0], s_i[1], \ldots, s_i[k-1]$ be the~$k$ source symbols transmitted by node~$\mathrm{s}$ at each discrete time~$i\ge 0$ where $s_j[0]=s_j[1]=\ldots = s_j[k-1]=0$ for any $j<0$ by convention. Then, there exists a tuple $((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$ such that node~$\mathrm{r}$ and node~$\mathrm{d}$ must produce estimates of the symbols in $\big\{s_i[\ell]\,|\,i\in\{0, 1, \ldots\}\big\}$ for each $\ell\in\{0, 1, \ldots, k-1\}$ with respective delays~$t_\ell$ and $t_\ell+\tau_\ell$. We call the tuple a \emph{delay profile.} To simplify notation, we let $\hat s_i^{(\mathrm{r})}[\ell]$ and $\hat s_i^{(\mathrm{d})}[\ell]$ denote the estimates of $s_i[\ell]$ produced by node~$\mathrm{r}$ and node~$\mathrm{d}$ respectively, which have to be decoded at time~$i+t_\ell$ and time~$i+t_\ell+\tau_\ell$ respectively.}


{Given a symbol-wise DF scheme with delay profile $((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$, we define the \emph{first-hop delay spectrum} and the \emph{second-hop delay spectrum} to be $(t_0, t_1, \ldots, t_{k-1})$ and $(\tau_0, \tau_1, \ldots, \tau_{k-1})$ respectively. The first-hop and second-hop delay spectrums can be interpreted as the channel-level delay profiles attained by the symbol-wise DF scheme for~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ respectively.}
\begin{Example} \label{exampleSymbolWise}
{Consider a symbol-wise DF strategy with delay profile~$((2, 1), (1, 2))$ which is illustrated in Table~\ref{table2}. The first-hop delay spectrum is $(2,1)$, which agrees with the facts that the duration between the arrival of~$s_i[0]$ and the construction of~$\hat{s}_i^{(\mathrm{r})}[0]$ equals~$2$ and that the duration between the arrival of~$s_i[1]$ and the construction of~$\hat{s}_i^{(\mathrm{r})}[1]$ equals~$1$ for each~$i$. Similarly, the second-hop delay spectrum is $(1,2)$, which agrees with the facts that the duration between the construction of $\hat{s}_i^{(\mathrm{r})}[0]$
 and the construction of~$\hat{s}_i^{(\mathrm{d})}[0]$ equals~$1$ and that the duration between the construction of~$\hat{s}_i^{(\mathrm{r})}[1]$ and the construction of~$\hat{s}_i^{(\mathrm{d})}[1]$ equals~$2$ for each~$i$. In other words, for each~$i$, the decoding delays over channels~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ for $s_i[0]$ are~$2$ and~$1$ respectively, and the decoding delays over channels~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ for $s_i[1]$ are~$1$ and~$2$ respectively.}
\end{Example}
\begin{table}
\centering
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{5}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}
\\\hline
$s_i[0]$ &\red{$\boxed{s_0[0]}$} &\magenta{$s_1[0]$} & \blue{$s_2[0]$} &$s_3[0]$&$s_4[0]$\\\hline
$s_i[1]$ & $s_0[1]$ &\red{$\boxed{s_1[1]}$} & \magenta{$s_2[1]$} & \blue{$s_3[1]$}&$s_4[1]$\\\hline
$s_{i-2}[0]+s_{i-1}[1]$ &$0$ &$s_0[1]$ & \red{$\boxed{s_0[0]+s_1[1]}$} &\magenta{$s_1[0]+s_2[1]$}& \blue{$s_2[0]+s_3[1]$}\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{s}$ from time~$0$ to~$4$. \label{table2:tab_1}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$\hat{s}_{i-1}^{(\mathrm{r})}[1]$ & $0$ &\red{$\boxed{\hat{s}_0^{(\mathrm{r})}[1]}$} &\magenta{$\hat{s}_1^{(\mathrm{r})}[1]$} & \blue{$\hat{s}_2^{(\mathrm{r})}[1]$} &$\hat{s}_3^{(\mathrm{r})}[1]$&$\hat{s}_4^{(\mathrm{r})}[1]$\\\hline
$\hat{s}_{i-2}^{(\mathrm{r})}[0]$ & $0$& $0$ &$\red{\boxed{\hat{s}_0^{(\mathrm{r})}[0]}}$ & $\magenta{\hat{s}_1^{(\mathrm{r})}[0]}$ & \blue{$\hat{s}_2^{(\mathrm{r})}[0]$}&$\hat{s}_3^{(\mathrm{r})}[0]$\\\hline
$\hat{s}_{i-3}^{(\mathrm{r})}[0]+\hat{s}_{i-3}^{(\mathrm{r})}[1]$& $0$ &$0$ &$0$ & $\red{\boxed{\hat{s}_0^{(\mathrm{r})}[0]+\hat{s}_0^{(\mathrm{r})}[1]}}$ &\magenta{$\hat{s}_1^{(\mathrm{r})}[0]+\hat{s}_1^{(\mathrm{r})}[1]$}& \blue{$\hat{s}_2^{(\mathrm{r})}[0]+\hat{s}_2^{(\mathrm{r})}[1]$}\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{r}$ from time~$0$ to~$5$. \label{table2:tab_2}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$\hat{s}_{i-3}^{(\mathrm{d})}[0]$& $0$ & $0$ & $0$ &$\hat{s}_0^{(\mathrm{d})}[0]$ & $\hat{s}_1^{(\mathrm{d})}[0]$ & $\hat{s}_2^{(\mathrm{d})}[0]$\\\hline
$\hat{s}_{i-3}^{(\mathrm{d})}[1]$& $0$ &$0$& $0$ &$\hat{s}_0^{(\mathrm{d})}[1]$ &$\hat{s}_1^{(\mathrm{d})}[1]$ & $\hat{s}_2^{(\mathrm{d})}[1]$ \\\hline
\end{tabular}
\caption{Estimates constructed by node~$\mathrm{d}$ from time~$0$ to~$5$. \label{table2:tab_3}}
\end{subtable}
\caption{A symbol-wise DF strategy with delay profile~$((2, 1), (1, 2))$.}
\label{table2}
\end{table}

A symbol-wise DF strategy with delay profile $((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$ is also called a \emph{message-wise DF strategy} if $t_0=t_1=\ldots=t_{k-1}$ and $\tau_0=\tau_1=\ldots=\tau_{k-1}$, {where the decoding delays for all message symbols attained by the message-wise DF strategy for channels~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ are $t_0$ and $\tau_0$ respectively.}
\begin{Example} \label{exampleMessageWise}
Consider a message-wise DF strategy with delay profile~{$((1, 2), (1, 2))$} which is illustrated in Table~\ref{table2msg}. The symbols highlighted in the same color are generated by the same block code. The first-hop delay spectrum equals {$(1, 1)$} and the second-hop delay spectrum equals {$(2,2)$}, which agrees with the facts that the duration between the arrival of~$s_i[\ell]$ and the construction of~$\hat{s}_i^{(\mathrm{r})}[\ell]$ equals~$1$ and that the duration between the construction of~$\hat{s}_i^{(\mathrm{r})}[\ell]$ and the construction of~$\hat{s}_i^{(\mathrm{d})}[\ell]$ equals~$2$ for each $\ell\in\{0,1\}$ and each~$i\in\{0, 1, \ldots\}$. In other words, for each~$i$ and each $\ell\in\{0,1\}$, the decoding delays for channels~$(\mathrm{s},\mathrm{r})$ and~$(\mathrm{r},\mathrm{d})$ for $s_i[\ell]$ are~$1$ and~$2$ respectively.
\end{Example}
\begin{table}
\centering
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{5}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}
\\\hline
$s_i[0]$ &\red{$\boxed{s_0[0]}$} &\magenta{$s_1[0]$} & $s_2[0]$ &$s_3[0]$&$s_4[0]$\\\hline
$s_i[1]$ & \blue{$s_0[1]$} &$s_1[1]$ & $s_2[1]$ & $s_3[1]$&$s_4[1]$\\\hline
$s_{i-1}[0]$ &$0$ &\red{$\boxed{s_0[0]}$} & \magenta{$s_1[0]$} &$s_2[0]$& $s_3[0]$\\\hline
$s_{i-1}[1]$ &$0$ &\blue{$s_0[1]$} & $s_1[1]$ &$s_2[1]$& $s_3[1]$\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{s}$ from time~$0$ to~$4$. \label{table2msg:tab_1}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$\hat{s}_{i-1}^{(\mathrm{r})}[0]$&$0$ &\red{$\boxed{\hat{s}_0^{(\mathrm{r})}[0]}$} &\magenta{$\hat{s}_1^{(\mathrm{r})}[0]$} & $\hat{s}_2^{(\mathrm{r})}[0]$ &$\hat{s}_3^{(\mathrm{r})}[0]$&$\hat{s}_4^{(\mathrm{r})}[0]$\\\hline
$\hat{s}_{i-1}^{(\mathrm{r})}[1]$ &$0$& $\hat{s}_0^{(\mathrm{r})}[1]$ &$\red{\boxed{\hat{s}_1^{(\mathrm{r})}[1]}}$ & $\magenta{\hat{s}_2^{(\mathrm{r})}[1]}$ & $\hat{s}_3^{(\mathrm{r})}[1]$ &$\hat{s}_4^{(\mathrm{r})}[1]$\\\hline
$\hat{s}_{i-3}^{(\mathrm{r})}[0]$ &$0$&$0$ &$0$ & $\red{\boxed{\hat{s}_0^{(\mathrm{r})}[0]}}$ &\magenta{$\hat{s}_1^{(\mathrm{r})}[0]$}& $\hat{s}_2^{(\mathrm{r})}[0]$\\\hline
$\hat{s}_{i-3}^{(\mathrm{r})}[1]$ &$0$&$0$ &$0$ & $\hat{s}_0^{(\mathrm{r})}[1]$ &\red{$\boxed{\hat{s}_1^{(\mathrm{r})}[1]}$}& \magenta{$\hat{s}_2^{(\mathrm{r})}[1]$}\\\hline
\end{tabular}
\caption{Symbols transmitted by node~$\mathrm{r}$ from time~$0$ to~$5$. \label{table2msg:tab_2}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$\hat{s}_{i-3}^{(\mathrm{d})}[0]$&$0$ & $0$ & $0$ &$\hat{s}_0^{(\mathrm{d})}[0]$ & $\hat{s}_1^{(\mathrm{d})}[0]$ & $\hat{s}_2^{(\mathrm{d})}[0]$\\\hline
$\hat{s}_{i-3}^{(\mathrm{d})}[1]$&$0$ &$0$& $0$ &$\hat{s}_0^{(\mathrm{d})}[1]$ &$\hat{s}_1^{(\mathrm{d})}[1]$ & $\hat{s}_2^{(\mathrm{d})}[1]$ \\\hline
\end{tabular}
\caption{Estimates constructed by node~$\mathrm{d}$ from time~$0$ to~$5$. \label{table2msg:tab_3}}
\end{subtable}
\caption{A message-wise DF strategy with delay profile~${((1, 2), (1, 2))}$.}
\label{table2msg}
\end{table}

{Motivated by the definition of a  delay profile for a symbol-wise DF strategy defined for the three-node relay network, we say $(\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$ is a \emph{delay spectrum} for a point-to-point packet erasure code if the following holds: Let~$s_i[0], s_i[1], \ldots, s_i[k-1]$ be the~$k$ source symbols transmitted by the source at each discrete time~$i\ge 0$.
Then, the estimate of symbol $s_i[\ell]$ denoted by~$\hat s_i[\ell]$ must be constructed by the destination by time $i+\Delta_\ell$ for each $\ell\in\{0, 1, \ldots, k-1\}$ and each $i\in\mathbb{Z}_+$.
}
\begin{Example} \label{exampleDelaySpectrumPTP}
Consider a point-to-point code with  delay spectrum~$(2,1)$ which is illustrated in Table~\ref{table3}. The symbols highlighted in the same color are generated by the same block code. For the point-to-point code, every symbol~$s_i[0]$ must be estimated by the destination by time~$i+2$, and every symbol~$s_i[1]$ must be estimated by the destination by time~$i+1$. In other words, the decoding delay constraints imposed for~$s_i[0]$ and~$s_i[1]$ are~$2$ and~$1$ respectively.
\end{Example}
\begin{table}
\centering
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{5}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}
\\\hline
$s_i[0]$ &\red{$\boxed{s_0[0]}$} &\magenta{$s_1[0]$} & \blue{$s_2[0]$} &$s_3[0]$&$s_4[0]$\\\hline
$s_i[1]$ & $s_0[1]$ &\red{$\boxed{s_1[1]}$} & \magenta{$s_2[1]$} & \blue{$s_3[1]$}&$s_4[1]$\\\hline
$s_{i-2}[0]+s_{i-1}[1]$ &$0$ &$s_0[1]$ & \red{$\boxed{s_0[0]+s_1[1]}$} &\magenta{$s_1[0]+s_2[1]$}& \blue{$s_2[0]+s_3[1]$}\\\hline
\end{tabular}
\caption{Symbols transmitted by the source from time~$0$ to~$4$. \label{table3:tab_1}}
\end{subtable}
\bigskip\\
\begin{subtable}{\textwidth}
\centering
\begin{tabular}{|c|*{6}{c|}}\hline
\makebox[2.2em]{ Time $i$ }

&\makebox[1.5em]{$0$}&\makebox[1.5em]{$1$}&\makebox[1.5em]{$2$}&\makebox[1.5em]{$3$}&\makebox[1.5em]{$4$}&\makebox[1.5em]{$5$}
\\\hline
$\hat{s}_{i-2}[0]$ & $0$ & $0$ &$\hat{s}_0[0]$ & $\hat{s}_1[0]$ & $\hat{s}_2[0]$ & $\hat{s}_3[0]$\\\hline
$\hat{s}_{i-1}[1]$ & $0$ &$\hat{s}_0[1]$ &$\hat{s}_1[1]$ & $\hat{s}_2[1]$ & $\hat{s}_3[1]$ & $\hat{s}_4[1]$ \\\hline
\end{tabular}
\caption{Estimates constructed by the destination from time~$0$ to~$5$. \label{table3:tab_3}}
\end{subtable}
\caption{A point-to-point code with  delay spectrum~$(2,1)$.}
\label{table3}
\end{table}
\subsection{Main Contribution}
This paper investigates the three-node relay network subject to arbitrary erasures and characterizes the maximum achievable rate denoted by $C_{T, N_1, N_2}$ as
\begin{align}
C_{T, N_1, N_2} = \min\big\{C_{T-N_2, N_1}, C_{T-N_1, N_2}\big\}=\begin{cases}\frac{T-N_1-N_2+1}{T-\min\{N_1,N_2\}+1} & \text{if $T\ge N_1+N_2$,}\\  0 & \text{otherwise,}\end{cases} \label{mainResultIntro}
\end{align}
where $C_{T, N}$ is the point-to-point channel capacity that satisfies~\eqref{capacityPTP}.

{The converse proof applies to any streaming strategy conforming to the formulation in Section~\ref{subsecChannelModel}, not restricted to the time-division strategies presented in Section~\ref{subsecRelatedWork}. The converse is proved by analyzing the maximum achievable rate for each point-to-point channel when the erasures in the other channel are consecutive (bursty). The proof is similar to the classical cut-set bound~\cite{CEG} in the following sense: It is the minimum of two point-to-point channel capacities~$C_{T-N_2, N_1}$ and $C_{T-N_1, N_2}$ where $T-N_2$ and~$T-N_1$ are the maximum tolerable decoding delays of the source messages for the first and second hops respectively. The maximum tolerable decoding delays $T-N_2$ and~$T-N_1$ can be intuitively explained as follows: If the relay needs to wait more than~$T-N_2$ time slots during the first hop to decode a source message, then the source message would not reach the destination by time~$T$ if the second channel is subject to some length-$N_2$ burst erasure. Similarly, if the relay needs to use more than~$T-N_1$ time slots to deliver a decoded source message to the destination, then the destination would not receive the delivered message by time~$T$ if the first channel is subject to some length-$N_1$ burst erasure.
}

{The achievability is proved by constructing a symbol-wise DF scheme with delay profile~$((T-N_2, N_1), (T-N_2-1, N_1+1), \ldots, (N_1, T-N_2))$ (as illustrated in Example~\ref{exampleSymbolWise}). In particular, the first-hop and second-hop delay spectrums are $(T-N_2, T-N_2-1, \ldots, N_1)$ and $(N_2, N_2+1, \ldots, T-N_1)$ respectively. The symbol-wise DF scheme is constructed by using a point-to-point code with  delay spectrum~$(T-N_2, T-N_2-1, \ldots, N_1)$ for the first hop and using another point-to-point code with  delay spectrum~$(T-N_1, T-N_1-1, \ldots, N_2)$ for the second hop.
}

{Combining the achievability and the converse results, we conclude that symbol-wise DF schemes are optimal in the sense that they attain the maximum achievable rate of the three-node relay network. In addition, we show that the maximum achievable rate for message-wise DF (as illustrated in Example~\ref{exampleMessageWise}) is
\begin{align}
R_{T, N_1, N_2}^{\text{message}} = \max_{(T_1, T_2): T_1+T_2\le T}\min\big\{C_{T_1, N_1}, C_{T_2, N_2}\big\}, \label{mainResultIntroMessagewise}
\end{align}
which together with~\eqref{mainResultIntro} implies that message-wise DF is sub-optimal if and only if $T>N_1+N_2$.}

{Finally, under the random erasure model described in Section~\ref{subsecRandomErasures}, we show that symbol-wise DF achieves an average loss probability decaying exponentially in $\min\{N_1+1, N_2+1\}$ and provide numerical results that demonstrate the advantage of using symbol-wise DF over traditional message-wise DF.}
\subsection{Paper Outline}
This paper is organized as follows. The notation in this paper is explained in the next subsection. Section~\ref{sectionDefinition} presents the formulation of streaming codes for the three-node relay network and states the main result. Section~\ref{sectionConverse} presents the converse proof of the main result. Section~\ref{sectionPrelim} presents the preliminary results that are useful for the achievability proof of the main result, which include the definitions of the delay profile of a symbol-wise DF scheme and the delay spectrum of a point-to-point code. Section~\ref{sectionAchievability} contains the achievability proof of the main result, i.e., the existence of an optimal symbol-wise DF scheme for the three-node relay network for all parameters~$(T, N_1, N_2)$. Section~\ref{sectionMessageWiseDF} investigates message-wise DF and shows that it is sub-optimal in general. {Section~\ref{sectionLossProbBound} shows that symbol-wise DF achieves an average loss probability decaying exponentially fast in~$\min\{N_1+1, N_2+1\}$ for the random erasure model.} Section~\ref{sectionNumerical} presents numerical results that demonstrate the advantage of using symbol-wise DF over message-wise DF when the channels are subject to i.i.d.\ erasures. Section~\ref{sectionSlidingWindow} extends the main result to a sliding window model that can introduce an infinite number of erasures. Section~\ref{sectionConclusion} concludes this paper.


\subsection{Notation}\label{notation}
We use $\Pr\{\mathcal{E}\}$ to represent the probability of an
event~$\mathcal{E}$.
The set of non-negative integers is denoted by $\mathbb{Z}_+$. All the elements of any matrix considered in this paper are taken from a common finite field~$\mathbb{F}$, where~$0$ and~$1$ denote the additive identity and the multiplicative identity respectively. The set of $k$-dimensional row vectors over $\mathbb{F}$ is denoted by $\mathbb{F}^k$, and the set of $k\times n$ matrices over $\mathbb{F}$ is denoted by $\mathbb{F}^{k\times n}$. For any matrix $\mathbf{G}$, we let $\mathbf{G}^t$ and $\rank(\mathbf{G})$ denote respectively the transpose and the rank of $\mathbf{G}$. A row vector in $\mathbb{F}^k$ is denoted by $\mathbf{a} \triangleq [a_0\ a_1\ \ldots \ a_{k-1}]$ where $a_i$ denotes the $(\ell+1)^{\text{th}}$ element of $\mathbf{a}$.
The $k$-dimensional identity matrix is denoted by $\mathbf{I}_k$
and the $L_1\times L_2$ all-zero matrix is denoted by $\mathbf{0}^{L_1\times L_2}$.
{For any natural numbers $L$ and $N$, a systematic maximum-distance separable (MDS) $(L+N, L)$-code is characterized by an $L \times N$ parity matrix
$\mathbf{V}^{L\times N}$ where any~$L$ columns of $[\mathbf{I}_{L} \ \mathbf{V}^{L\times N}]\in \mathbb{F}^{L\times (L+N)}$ are independent.}


It is well known that a systematic MDS $(L+B, L)$-code always exists as long as $|\mathbb{F}|\ge L+B$ \cite{MacWilliamsSloane1988}. We will take all logarithms to base~$2$ throughout this paper.


\section{Streaming Codes for the Three-Node Relay Network with Arbitrary Erasures} \label{sectionDefinition}

\subsection{Problem Formulation}
{Let $k$ be a non-negative integer, and $n$ and $m$ be two natural numbers.} Node~$\mathrm{s}$ wants to send a sequence of messages~$\{\mathbf{s}_i\}_{i=0}^{\infty}$ to node~$\mathrm{d}$ with the help of the middle node~$\mathrm{r}$. Each $\mathbf{s}_i$ is an element in $\mathbb{F}^k$ where $\mathbb{F}$ is some finite field. In each time slot~$i\in\mathbb{Z}_+$, the source message $\mathbf{s}_i$ is encoded into a length-$n$ packet $\mathbf{x}_i\in\mathbb{F}^n$ to be transmitted to the relay through the erasure channel~$(\mathrm{s},\mathrm{r})$, and the relay receives~$\mathbf{y}_i^{(\mathrm{r})}\in\mathbb{F}^n \cup \{*\}$ where $\mathbf{y}_i^{(\mathrm{r})}$ equals either $\mathbf{x}_i$ or the erasure symbol~`$*$'. In the same time slot, the relay transmits~$\mathbf{x}_i^{(\mathrm{r})}\in\mathbb{F}^m$ to the destination through the erasure channel~$(\mathrm{r},\mathrm{d})$, and the destination receives $\mathbf{y}_i\in\mathbb{F}^m \cup \{*\}$ where $\mathbf{y}_i$ equals either $\mathbf{x}_i^{(\mathrm{r})}$ or the erasure symbol~`$*$'. The fraction $\frac{k}{\max\{n,m\}}$ specifies the rate of the code. Every code is subject to a delay constraint of~$T$ time slots, meaning that the destination must produce an estimate of $\mathbf{s}_i$, denoted by $\hat{\mathbf{s}}_i$, upon receiving $\mathbf{y}_{i+T}$.
We assume that on the discrete timeline, channels~$(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ introduce $N_1$ and $N_2$ arbitrary erasures respectively. The symbols generated in the three-node relay network at time~$i$ are illustrated in Figure~\ref{figureThreeNodeRelayNetwork}.


 


\subsection{Standard Definitions and Main Result}
\begin{Definition} \label{definitionCode}
An $(n, m, k, T)_{\mathbb{F}}$-streaming code consists of the following:
\begin{enumerate}
\item A sequence of source messages~$\{\mathbf{s}_i\}_{i=0}^{\infty}$ where $\mathbf{s}_i\in \mathbb{F}^k$.
\item An encoding function~$f_i: \underbrace{\mathbb{F}^k \times \ldots \times \mathbb{F}^k}_{i +1 \text{ times }} \rightarrow \mathbb{F}^n$ for each $i\in\mathbb{Z}_+$, where $f_i$ is used by node~$\mathrm{s}$ at time~$i$ to encode $\mathbf{s}_i$ according to
    \begin{align*}
    \mathbf{x}_i = f_i(\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_i).
    \end{align*}

    \item A relaying function~$f_i^{(\mathrm{r})}: \underbrace{\mathbb{F}^n \cup\{*\}\times \ldots \times \mathbb{F}^n\cup\{*\}}_{i +1 \text{ times }} \rightarrow \mathbb{F}^m$ for each $i\in\mathbb{Z}_+$, where $f_i^{(\mathrm{r})}$ is used by node~$\mathrm{r}$ at time~$i$ to construct
    \begin{align}
    \mathbf{x}_i^{(\mathrm{r})} = f_i^{(\mathrm{r})}(\mathbf{y}_0^{(\mathrm{r})}, \mathbf{y}_1^{(\mathrm{r})}, \ldots, \mathbf{y}_i^{(\mathrm{r})}). \label{defRelaying}
    \end{align}

    \item A decoding function~$\varphi_{i+T}: \underbrace{\mathbb{F}^m\cup\{*\} \times \ldots \times \mathbb{F}^m\cup\{*\}}_{i+T+1 \text{ times }}\rightarrow \mathbb{F}^k$ for each $i\in\mathbb{Z}_+$, where $\varphi_{i+T}$ is used by node~$\mathrm{d}$ at time $i+T$ to estimate $\mathbf{s}_i$ according to
        \begin{align}
       \hat{\mathbf{s}}_i = \varphi_{i+T}(\mathbf{y}_0, \mathbf{y}_1, \ldots, \mathbf{y}_{i+T}). \label{defDecoder}
        \end{align}
\end{enumerate}
\end{Definition}
\medskip


\begin{Definition} \label{definitionErasureSeq}
An erasure sequence is a binary sequence denoted by $e^\infty\triangleq\{e_i\}_{i=0}^{\infty}$ where
\begin{equation*}
e_i=\mathbf{1}\{\text{erasure occurs at time~$i$}\}.
\end{equation*}
An $N$-erasure sequence is an erasure sequence $e^\infty$ that satisfies $\sum_{\ell=0}^\infty e_\ell= N$. In other words, an $N$-erasure sequence introduces~$N$ arbitrary erasures on the discrete timeline. The set of $N$-erasure sequences is denoted by $\Omega_N$.
\end{Definition}
\medskip
\begin{Definition} \label{definitionChannel}
The mapping $g_n: \mathbb{F}^n \times \{0,1\} \rightarrow \mathbb{F}^n \cup \{*\}$ of an erasure channel is defined as
\begin{align}
g_n(\mathbf{x},e)= \begin{cases}\mathbf{x} & \text{if $e=0$,}\\
* & \text{if $e=1$.} \label{defChannelLaw}
\end{cases}
\end{align}
For any erasure sequence $e^\infty$ and any $(n, m, k, T)_{\mathbb{F}}$-streaming code, the following input-output relation holds for the erasure channel~$(\mathrm{s}, \mathrm{r})$ for each $i\in\mathbb{Z}_+$:
\begin{align}
\mathbf{y}_i^{(\mathrm{r})} = g_n(\mathbf{x}_i, e_i). \label{defChannelOutput1}
\end{align}
Similarly, the following input-output relation holds for the erasure channel~$(\mathrm{r}, \mathrm{d})$ for each $i\in\mathbb{Z}_+$:
\begin{align}
\mathbf{y}_i = g_m(\mathbf{x}_i^{(\mathrm{r})}, e_i). \label{defChannelOutput2}
\end{align}
\end{Definition}
\medskip
\begin{Definition} \label{definitionAchievability}
An $(n, m, k, T)_{\mathbb{F}}$-streaming code is said to be $(N_1, N_2)$-achievable if the following holds for any $N_1$-erasure sequence~$e^\infty\in\Omega_{N_1}$ and any $N_2$-erasure sequence~$\epsilon^\infty\in\Omega_{N_2}$: For all $i\in\mathbb{Z}_+$ and all $\mathbf{s}_i\in \mathbb{F}^k$, we have
\begin{equation*}
 \hat{\mathbf{s}}_i = \mathbf{s}_i
\end{equation*}
where
\begin{equation*}
 \hat{\mathbf{s}}_i = \varphi_{i+T}\big( g_m(\mathbf{x}_0^{(\mathrm{r})}, \epsilon_0), \ldots,  g_m(\mathbf{x}_{i+T}^{(\mathrm{r})}, \epsilon_{i+T})\big)
\end{equation*}
due to~\eqref{defDecoder} and~\eqref{defChannelOutput2}
and
\begin{equation*}
\mathbf{x}_i^{(\mathrm{r})} = f_i^{(\mathrm{r})}\big( g_n(\mathbf{x}_0, e_0), \ldots,  g_n(\mathbf{x}_{i}, e_{i})\big)
\end{equation*}
due to~\eqref{defRelaying} and~\eqref{defChannelOutput1}.
\end{Definition}
\medskip
\begin{Definition} \label{defAchievableRate}
The rate of an $(n, m, k, T)_{\mathbb{F}}$-streaming code is $\frac{k}{\max\{n,m\}}$.
\end{Definition}
\medskip
\begin{Remark}
For any $(n, m, k, T)_{\mathbb{F}}$-streaming code, if the transmission time of a packet is proportional to the packet length, then~$n$ units of time are needed to transmit~$k$ units of information over $(\mathrm{s},\mathrm{r})$ and~$m$ units of time are needed to transmit~$k$ units of information over $(\mathrm{s},\mathrm{r})$. Therefore, $\max\{n,m\}$ can be interpreted as the amount of time needed to simultaneously transmit~$k$ units of information over $(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$. Consequently, the rate~$\frac{k}{\max\{n,m\}}$ in Definition~\ref{defAchievableRate} can be interpreted as the reciprocal of the amount of time needed to simultaneously transmit one unit of information over the two channels.
\end{Remark}
\medskip
\begin{Definition} \label{defCapacity}
The $(T, N_1, N_2)$-capacity, denoted by $C_{T, N_1, N_2}$, is the maximum rate achievable by $(n, m, k, T)_{\mathbb{F}}$-streaming codes that are $(N_1, N_2)$-achievable, i.e.,
\begin{equation*}
C_{T, N_1, N_2}\triangleq \sup\left\{\frac{k}{\max\{n,m\}} \left| \,\parbox[c]{3.4 in}{There exists an $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code for some $n$, $m$, $k$ and $\mathbb{F}$.}\right. \right\}.
\end{equation*}
\end{Definition}
\medskip

The following theorem is the main result of this paper. The converse proof is provided in Section~\ref{sectionConverse}, and the achievability proof is provided in Sections~\ref{sectionPrelim} and~\ref{sectionAchievability}.
\begin{Theorem} \label{theoremMain}
 Fix any $(T, N_1, N_2)$. {Recalling that the point-to-point capacity satisfies~\eqref{capacityPTP},} we have
\begin{align}
 C_{T, N_1, N_2} = \min\big\{C_{T-N_2, N_1}, C_{T-N_1, N_2}\big\}. \label{mainResultThm}
\end{align}
{In particular, for any~$\mathbb{F}$ with $|\mathbb{F}|\ge T+1$, there exists an $(N_1, N_2)$-achievable $(n, m, k, T)_\mathbb{F}$-streaming code with~$k=T-N_1-N_2+1$, $n=T-N_2+1$, $m=T-N_1+1$ and rate
\begin{align*}
\frac{k}{\max\{n,m\}} =  C_{T, N_1, N_2}.
\end{align*}
}


\end{Theorem}

\section{Converse Proof of Theorem~\ref{theoremMain}}\label{sectionConverse}
Fix any $(T, N_1, N_2)$. Suppose we are given an $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code for some $n$, $m$, $k$ and $\mathbb{F}$. Our goal is to show that
\begin{align}
\frac{k}{\max\{n, m\}}\le \min\big\{C_{T-N_2, N_1}, C_{T-N_1, N_2}\big\}.  \label{converseProofSt}
\end{align}
To this end, we let $\{\mathbf{s}_i\}_{i\in\mathbb{Z}_+}$ be i.i.d.\ random variables where $\mathbf{s}_0$ is uniform on~$\mathbb{F}^k$. {Since the $(n, m, k, T)_{\mathbb{F}}$-streaming code is $(N_1, N_2)$-achievable, it follows from Definition~\ref{definitionAchievability} that
\begin{align}


 H(\mathbf{s}_i| \mathbf{y}_0, \mathbf{y}_{1}, \ldots, \mathbf{y}_{i+T}) = 0 \label{eqn0ConverseProof}
\end{align}
for any $i\in\mathbb{Z}_+$, any $e^\infty\in\Omega_{N_1}$ and any $\epsilon^\infty\in\Omega_{N_2}$.}
Consider the following two cases.\\
\textbf{Case $T<N_1 + N_2$:}\\
Let $e^\infty\in\Omega_{N_1}$ and $\epsilon^\infty\in\Omega_{N_2}$ such that
\begin{align}
e_i=\begin{cases} 1 & \text{if $0\le i\le N_1-1$,}
\\
0 & \text{otherwise,}
\end{cases} \label{eqn1ConverseProof}
\end{align}
and
\begin{align}
\epsilon_i=\begin{cases} 1 & \text{if $N_1\le i\le N_1+N_2-1$,}
\\
0 & \text{otherwise.}
\end{cases} \label{eqn2ConverseProof}
\end{align}
Due to~\eqref{eqn1ConverseProof} and~\eqref{eqn2ConverseProof} and Definition~\ref{definitionCode}, we have
\begin{align}
I(\mathbf{s}_0;  \mathbf{y}_0, \mathbf{y}_1, \ldots, \mathbf{y}_{N_1+N_2-1})=0. \label{eqn3ConverseProof}
\end{align}
Combining~\eqref{eqn0ConverseProof}, \eqref{eqn3ConverseProof} and the assumption that $T<N_1 + N_2$, we obtain $H(\mathbf{s}_0)=0$. {Since~$\mathbf{s}_0$ consists of~$k$ uniform random variables in $\mathbb{F}$, the only possible value for~$k$ is zero, which together with~\eqref{capacityPTP} implies that
\begin{align}
\frac{k}{\max\{m,n\}} = 0 = \min\big\{C_{T-N_2, N_1}, C_{T-N_1, N_2}\big\}. \label{eqn3+ConverseProof}
\end{align}
}
\textbf{Case $T\ge N_1+N_2$:}\\
For every $i\in\mathbb{Z}_+$ and any $e^\infty\in\Omega_{N_1}$, message~$\mathbf{s}_i$ has to be perfectly recovered by node~$\mathrm{r}$ by time~$i+T-N_2$ given that $\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{i-1}$ have been correctly decoded by node~$\mathrm{r}$, or otherwise a length-$N_2$ burst erasure from time~$i+T-N_2+1$ to~$i+T$ introduced on channel~$(\mathrm{r}, \mathrm{d})$ would result in a decoding failure for both node~$\mathrm{r}$ and node~$\mathrm{d}$.
It then follows that
\begin{align}
H\left(\mathbf{s}_i \left|  \left\{\mathbf{x}_i, \mathbf{x}_{i+1}, \ldots, \mathbf{x}_{i+T-N_2}\right\} \setminus \left\{\mathbf{x}_{\theta_1}, \mathbf{x}_{\theta_2}\ldots, \mathbf{x}_{\theta_{N_1}}\right\}, \mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{i-1} \right.\right)=0 \label{eqn4ConverseProof}
\end{align}
for any $i\in\mathbb{Z}_+$ and any~$N_1$ non-negative integers denoted by $\theta_1, \theta_2, \ldots, \theta_{N_1}$. By~\eqref{eqn4ConverseProof} and the chain rule, we conclude the following for each~$j\in\mathbb{N}$ whose derivation is elaborated in Appendix~\ref{appendixDerivation}:
\begin{align}
&H\left(\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{T-N_2+(j-1)(T-N_2+1)} \left|  \left\{\mathbf{x}_{i(T-N_2+1)}, \mathbf{x}_{1+i(T-N_2+1)}, \ldots, \mathbf{x}_{T-N_1-N_2+i(T-N_2+1)}\right\}_{i=0}^{j}  \right.\right)\notag\\*
&\quad=0 \label{eqn5ConverseProof}
\end{align}
where the conditional entropy involves $j(T-N_2+1)$ source messages and $(j+1)(T-N_1-N_2+1)$ source packets.
{Therefore, the $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code restricted to channel~$(\mathrm{s},\mathrm{r})$ can be viewed as a point-to-point streaming code with rate $k/n$ and delay~$T-N_2$ which can correct any~$N_1$ erasures. In particular, the point-to-point code can correct the periodic erasure sequence $\tilde e^\infty$ illustrated in Figure~\ref{figure1},} which is formally defined as
\begin{align*}
\tilde e_i =
\begin{cases}
0 &\text{if $0\le i \:\text{mod}\: (T-N_2+1) \le T-N_1-N_2,$}\\
1 &\text{otherwise}
\end{cases}
\end{align*}
for all $i\in\mathbb{Z}_+$. By standard arguments which are rigorously elaborated in Appendix~\ref{appendixDerivation}, we conclude that
\begin{equation}
\frac{k}{n}\le \frac{T-N_1-N_2+1}{T-N_2+1}  = C_{T-N_2, N_1}. \label{eqn8ConverseProof}
\end{equation}
\begin{figure}[t!]
\centering
\includegraphics[width=3.5in]{erasurePattern1.pdf}
\caption{A periodic erasure sequence with period $T-N_2+1$.}
\label{figure1}
\end{figure}


In addition, for every $i\in\mathbb{Z}_+$ and any $\epsilon^\infty\in\Omega_{N_2}$, message~$\mathbf{s}_i$ has to be perfectly recovered from\linebreak$(\mathbf{y}_{i+N_1}, \mathbf{y}_{i+N_1+1}, \ldots, \mathbf{y}_{i+T})$ by node~$\mathrm{d}$ given that $\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{i-1}$ have been correctly decoded by node~$\mathrm{d}$, or otherwise a length-$N_1$ burst erasure from time~$i$ to~$i+N_1-1$ introduced on channel~$(\mathrm{s}, \mathrm{r})$ would result in a decoding failure for node~$\mathrm{d}$. It then follows that
\begin{align}
H\left(\mathbf{s}_i \left|  \left\{\mathbf{x}_{i+N_1}^{(\mathrm{r})}, \mathbf{x}_{i+N_1+1}^{(\mathrm{r})}, \ldots, \mathbf{x}_{i+T}^{(\mathrm{r})}\right\} \setminus \left\{\mathbf{x}_{\theta_1}^{(\mathrm{r})}, \mathbf{x}_{\theta_2}^{(\mathrm{r})}\ldots, \mathbf{x}_{\theta_{N_2}}^{(\mathrm{r})}\right\}, \mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{i-1} \right.\right)=0 \label{eqn9ConverseProof}
\end{align}
for any $i\in\mathbb{Z}_+$ and any $N_2$ non-negative integers denoted by $\theta_1, \theta_2, \ldots, \theta_{N_2}$. By~\eqref{eqn9ConverseProof} and the chain rule, we conclude the following for each~$j\in\mathbb{N}$ whose derivation is elaborated in Appendix~\ref{appendixDerivation}:
\begin{align}
H\left(\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{T-N_1+(j-1)(T-N_1+1)} \left|  \left\{\mathbf{x}_{N_1+N_2+i(T-N_1+1)}^{(\mathrm{r})}, \mathbf{x}_{N_1+N_2+1+i(T-N_1+1)}^{(\mathrm{r})}, \ldots, \mathbf{x}_{T+i(T-N_1+1)}^{(\mathrm{r})}\right\}_{i=-1}^{j}  \right.\right)=0 \label{eqn10ConverseProof}
\end{align}
where $\mathbf{x}_t\triangleq \mathbf{0}^{1\times m}$ and the conditional entropy involves $j(T-N_1+1)$ source messages and no more than $(j+2)(T-N_1-N_2+1)$ relay transmitted packets.
Therefore, the $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code restricted to channel~$(\mathrm{r},\mathrm{d})$ can be viewed as  a point-to-point streaming code with rate $k/m$ and delay~$T-N_1$ which can correct any~$N_2$ erasures. In particular, the point-to-point code can correct the periodic erasure sequence $\tilde e^\infty$ illustrated in Figure~\ref{figure2}, which is formally defined as
\begin{align*}
\hat e_i =
\begin{cases}
0 &\text{if $N_1+N_2\le i \:\text{mod}\: (T-N_1+1) \le T,$}\\
1 &\text{otherwise}
\end{cases}
\end{align*}
for all $i\in\mathbb{Z}_+$. By standard arguments which are rigorously elaborated in Appendix~\ref{appendixDerivation}, we conclude that
\begin{equation}
\frac{k}{m}\le \frac{T-N_1-N_2+1}{T-N_1+1}  = C_{T-N_1, N_2}. \label{eqn13ConverseProof}
\end{equation}
\begin{figure}[t!]
\centering
\includegraphics[width=3.5in]{erasurePattern2.pdf}
\caption{A periodic erasure sequence with period $T-N_1+1$.}
\label{figure2}
\end{figure}

Combining the above two cases and using~\eqref{eqn3+ConverseProof}, \eqref{eqn8ConverseProof} and~\eqref{eqn13ConverseProof},
we conclude that~\eqref{converseProofSt} holds for all $(T, N_1, N_2)$.
\section{Symbol-Wise Decode-Forward Strategy} \label{sectionPrelim}


This section provides the preliminary results for the achievability proof of Theorem~\ref{theoremMain}. The symbol-wise DF and its delay profile are formally described in Section~\ref{subsecSymbolWise}, while the point-to-point code and its delay spectrum are formally described in Section~\ref{subsectionPTPcode}
\subsection{Symbol-Wise DF and Its Delay Profile} \label{subsecSymbolWise}
\begin{Definition}  \label{definitionDelayProfile}
{A \emph{delay profile} is defined as
$((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$
for some~$k\in\mathbb{Z}_+$ where
$(t_\ell, \tau_\ell)\in \mathbb{Z}_+^2$.}

\end{Definition}
\begin{Remark}
{Examples of delay profiles are $((2,1),(1,2))$ in Example~\ref{exampleSymbolWise} and $((1,2),(1,2))$ in Example~\ref{exampleMessageWise}.}
\end{Remark}
\begin{Definition} \label{definitionSymbolDFCode}
Let~$k$ be a non-negative integer and fix a delay profile $\mathbf{d} \triangleq ((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$. Define {$T\triangleq \max_{0\le \ell\le k-1} \{t_\ell+\tau_\ell\}$.}
A \emph{symbol-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code} is an $(n,m,k,T)_{\mathbb{F}}$-streaming code (cf.\ Definition~\ref{definitionCode}) which produces estimates of the source symbols at nodes~$\mathrm{r}$ and~$\mathrm{d}$ as follows.
Let $s_i[\ell]\in\mathbb{F}$ be the $(\ell+1)^{\text{th}}$ source symbol generated at time~$i$ for each $\ell\in\{0, 1, \ldots, k-1\}$ and each $i\in\mathbb{Z}_+$, and recall that $\mathbf{x}_i\in\mathbb{F}^n$ and {$\mathbf{y}_i^{(\mathrm{r})}\in\mathbb{F}^n\cup\{*\}$} denote the source packet and the relay received packet respectively at time~$i$. For each $\ell\in\{0, 1, \ldots, k-1\}$ and each~$i\in\mathbb{Z}_+$, an estimate of $s_i[\ell]$ denoted by $\hat s_i^{(\mathrm{r})}[\ell]$ is produced by node~$\mathrm{r}$ at time $i+t_\ell$ based on~$(\mathbf{y}_0^{(\mathrm{r})}, \mathbf{y}_1^{(\mathrm{r})}, \ldots, \mathbf{y}_{i+t_\ell}^{(\mathrm{r})})$. Next, letting
\begin{align*}
\hat{\mathcal{S}}^{(\mathrm{r})}_i\triangleq \left\{ \hat s_j^{(\mathrm{r})}[\ell]\left|\,\parbox[c]{1.7 in}{$j+t_\ell\le i, \\ j\in\mathbb{Z}_+, \ell\in\{0, 1, \ldots, k-1\} $} \right. \right\}
\end{align*}
be the collection of estimates that have been made by node~$\mathrm{r}$ by time~$i$, node~$\mathrm{r}$ constructs and transmits $\mathbf{x}_i^{(\mathrm{r})}\in\mathbb{F}^m$ at time~$i$ for each $i\in\mathbb{Z}_+$ where $\mathbf{x}_i^{(\mathrm{r})}$ is a function of $\hat{\mathcal{S}}^{(\mathrm{r})}_i$. Finally, recalling that {$\mathbf{y}_i\in\mathbb{F}^m\cup\{*\}$} denotes the destination packet received at time~$i$, node~$\mathrm{d}$ constructs an estimate of $\hat s_i^{(\mathrm{r})}[\ell]$ denoted by $\hat s_i^{(\mathrm{d})}[\ell]$ {by time~$i+t_\ell+\tau_\ell$} based on~$(\mathbf{y}_0, \mathbf{y}_1, \ldots, \mathbf{y}_{i+\tau_\ell})$ for each $\ell\in\{0, 1, \ldots, k-1\}$ and each $i\in\mathbb{Z}_+$.
\end{Definition}
\medskip

The following corollary is a direct consequence of Definition~\ref{definitionSymbolDFCode} and Definition~\ref{definitionAchievability}.
\begin{Corollary}
A symbol-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code is $(N_1, N_2)$-achievable if the following holds for any~$e^\infty\in\Omega_{N_1}$ and any~$\epsilon^\infty\in\Omega_{N_2}$: For all $i\in\mathbb{Z}_+$ and all $\mathbf{s}_i=[s_i[0]\ s_i[1]\ \ldots s_i[k-1]]\in \mathbb{F}^k$, we have
\begin{equation*}
 \hat{s}_i^{(\mathrm{d})}[\ell] =  \hat{s}_i^{(\mathrm{r})}[\ell] =  s_i[\ell]
\end{equation*}
for each $\ell\in\{0, 1, \ldots, k-1\}$.
\end{Corollary}
\subsection{Delay Spectrum for Point-to-Point Streaming Code} \label{subsectionPTPcode}
The following three definitions are standard (cf.\ \cite{FKLTZA2018}).
\begin{Definition} \label{definitionCodePTP}
Let $(\mathrm{u}, \mathrm{v})\in\{(\mathrm{s}, \mathrm{r}), (\mathrm{r}, \mathrm{d})\}$ be a point-to-point channel in the relay network.
A point-to-point $(n, k, T)_{\mathbb{F}}$-streaming code over $(\mathrm{u}, \mathrm{v})$ consists of the following:
\begin{enumerate}
\item A sequence of messages~$\{\mathbf{u}_i\}_{i=0}^{\infty}$ where $\mathbf{u}_i\in \mathbb{F}^k$.
\item An encoding function~$f_i^{(\mathrm{u})}: \underbrace{\mathbb{F}^k \times \ldots \times \mathbb{F}^k}_{i +1 \text{ times }} \rightarrow \mathbb{F}^n$ for each $i\in\mathbb{Z}_+$, where $f_i^{(\mathrm{u})}$ is used by node~$\mathrm{u}$ at time~$i$ to encode $\mathbf{u}_i$ according to
    \begin{align*}
    \mathbf{x}_i^{(\mathrm{u})} = f_i(\mathbf{u}_0, \mathbf{u}_1, \ldots, \mathbf{u}_i).
    \end{align*}

   \item
 A decoding function~$\varphi_{i+T}^{(\mathrm{v})}: \underbrace{\mathbb{F}^n\cup\{*\} \times \ldots \times \mathbb{F}^n\cup\{*\}}_{i+T+1 \text{ times }}\rightarrow \mathbb{F}^k$ for each $i\in\mathbb{Z}_+$, where $\varphi_{i+T}^{(\mathrm{v})}$ is used by node~$\mathrm{v}$ at time $i+T$ to estimate $\mathbf{u}_i$ according to
        \begin{align}
       \hat{\mathbf{u}}_i = \varphi_{i+T}^{(\mathrm{v})}(\mathbf{y}_0^{(\mathrm{v})}, \mathbf{y}_1^{(\mathrm{v})}, \ldots, \mathbf{y}_{i+T}^{(\mathrm{v})}). \label{defDecoderPTP}
        \end{align}
        \end{enumerate}
      
\end{Definition}
\medskip
\begin{Definition} \label{definitionAchievabilityPTP}
A point-to-point $(n, k, T)_{\mathbb{F}}$-streaming code over $(\mathrm{u}, \mathrm{v})$ is said to be $N$-achievable if the following holds for any $N$-erasure sequence~$e^\infty\in\Omega_{N}$: For all $i\in\mathbb{Z}_+$ and all $\mathbf{u}_i\in \mathbb{F}^k$, we have
\begin{equation*}
 \hat{\mathbf{u}}_i = \mathbf{u}_i
\end{equation*}
where
\begin{equation*}
 \hat{\mathbf{u}}_i = \varphi_{i+T}^{(\mathrm{v})}\big( g_n(\mathbf{x}_0^{(\mathrm{u})}, e_0), \ldots,  g_n(\mathbf{x}_{i+T}^{(\mathrm{u})}, e_{i+T})\big)
\end{equation*}
due to~\eqref{defDecoderPTP}, \eqref{defChannelOutput1} and \eqref{defChannelOutput2}.
\end{Definition}
\medskip
\begin{Definition} \label{defCapacityPTP}
The $(T, N)$-capacity, denoted by $C_{T,N}$, is the maximum rate achievable by point-to-point $(n, k, T)_{\mathbb{F}}$-streaming codes that are $N$-achievable, i.e.,
\begin{equation*}
C_{T,N}\triangleq \sup\left\{\left.\frac{k}{n} \,\right| \parbox[c]{2.8 in}{There exists an $N$-achievable point-to-point $(n, k, T)_{\mathbb{F}}$-streaming code for some $n$, $k$ and $\mathbb{F}$.} \right\}.
\end{equation*}
\end{Definition}
\medskip
\begin{Theorem}[{\cite[Sec.~IV]{BKTA2013}}] \label{theoremPTP}
For any~$T$ and any~$N$, the $(T, N)$-capacity $C_{T,N}$ is characterized by~\eqref{capacityPTP}.


\end{Theorem}
\medskip
\begin{Definition}  \label{definitionDelaySpectrum}
A \emph{delay spectrum} is defined as
$(\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$
for some~$k\in\mathbb{Z}_+$ where
$\Delta_\ell\in \mathbb{Z}_+$.
\end{Definition}
\begin{Remark}
An example of delay spectrum is~$(2,1)$ in Example~\ref{exampleDelaySpectrumPTP}.
\end{Remark}

\medskip

\begin{Definition} \label{definitionDelaySpectrumCodePTP}
Let~$k$ be a non-negative integer and fix a delay spectrum $\mathbf{\Delta}\triangleq (\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$. Define $T\triangleq \max_{0\le \ell\le k-1} \Delta_\ell$.
A \emph{point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code} over $(\mathrm{u},\mathrm{v})$ is a point-to-point $(n, k,T)_{\mathbb{F}}$-streaming code (cf.\ Definition~\ref{definitionCodePTP}) which produces estimates of the source symbols at node~$\mathrm{d}$ as follows.
Let $u_i[\ell]\in\mathbb{F}$ be the $(\ell+1)^{\text{th}}$ source symbol generated by node~$\mathrm{u}$ at time~$i$ for each $\ell\in\{0, 1, \ldots, k-1\}$ and each $i\in\mathbb{Z}_+$, and let $\mathbf{y}_i^{(\mathrm{v})}\in\mathbb{F}^n$ denote the destination packet received by node~$\mathrm{v}$ at time~$i$. For each time~$i\in\mathbb{Z}_+$ and each $\ell\in\{0, 1, \ldots, k-1\}$, node~$\mathrm{d}$ constructs an estimate of $u_i[\ell]$ denoted by $\hat u_i^{(\mathrm{v})}[\ell]$ by time~$i+\Delta_\ell$ based on~$(\mathbf{y}_0^{(\mathrm{v})}, \mathbf{y}_1^{(\mathrm{v})}, \ldots, \mathbf{y}_{i+\Delta_\ell}^{(\mathrm{v})})$.
\end{Definition}
\medskip

The following corollary is a direct consequence of Definition~\ref{definitionDelaySpectrumCodePTP} and Definition~\ref{definitionAchievabilityPTP}.
\begin{Corollary} \label{corollaryAchievable}
A point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code over $(\mathrm{u},\mathrm{v})$ is $N$-achievable if the following holds for any~$e^\infty\in\Omega_{N}$: For all $i\in\mathbb{Z}_+$ and all $\mathbf{u}_i=[u_i[0]\ u_i[1]\ \ldots\  u_i[k-1]]\in \mathbb{F}^k$, we have
\begin{equation*}
 \hat{u}_i^{(\mathrm{v})}[\ell] = u_i[\ell]
\end{equation*}
for all $\ell\in\{0, 1, \ldots, k-1\}$.
\end{Corollary}

\subsection{Construction of a Point-to-Point Streaming Code Based on a Block Code} \label{subsectionPTPblockCodes}
We would like to construct a point-to-point streaming code as described in Definition~\ref{definitionDelaySpectrumCodePTP} based on a point-to-point block code described below such that they have the same delay spectrum and error-correcting capability. The following two definitions concerning systematic point-to-point block codes are standard (cf.\ \cite{FKLTZA2018}).
\begin{Definition}\label{definitionBlockCodePTP}
A (systematic) point-to-point $(n, k, T)_{\mathbb{F}}$-block code over $(\mathrm{u}, \mathrm{v})$ consists of the following:
\begin{enumerate}
\item A sequence of~$k$ symbols~$\{u[\ell]\}_{\ell=0}^{k-1}$ where $u[\ell]\in\mathbb{F}$.
\item A generator matrix $\mathbf{G}=[\mathbf{I}_k \ \mathbf{P}]\in \mathbb{F}^{k\times n}$ for some parity matrix $\mathbf{P}\in\mathbb{F}^{k\times (n-k)}$. The \textit{source codeword} is generated according to
\begin{align}
[x[0]\ x[1]\ \ldots \ x[n-1]]=[u[0]\ u[1]\ \ldots \ u[k-1]]\, \mathbf{G}. \label{encodingOfBlockCode}
\end{align}
    \item A decoding function~$\varphi_{\ell+T}: \underbrace{\mathbb{F}\cup\{*\} \times \ldots \times \mathbb{F}\cup\{*\}}_{\min\{\ell+T+1,n\} \text{ times }}\rightarrow \mathbb{F}$ for each $\ell\in\{0, 1, \ldots, k-1\}$, where $\varphi_{\ell+T}$ is used by node~$\mathrm{v}$ at time $\min\{\ell+T,n-1\}$ to estimate $u[\ell]$ according to
        \begin{align}
       \hat{u}[\ell] =
       \begin{cases}
        \varphi_{\ell+T}(y[0] ,y[1],\ldots, y[\ell+T]) & \text{if $\ell+T\le n-1$,} \\
        \varphi_{\ell+T}(y[0] ,y[1],\ldots, y[n-1])&  \text{if $\ell+T> n-1$}.
        \end{cases}
        \label{defDecoderBlock}
        \end{align}
\end{enumerate}
\end{Definition}


\begin{Definition} \label{definitionAchievabilityBlockPTP}
A point-to-point $(n, k, T)_{\mathbb{F}}$-block code is said to be $N$-achievable if the following holds for any $N$-erasure sequence~$e^\infty\in \Omega_{N}$: For the $(n, k, T)_{\mathbb{F}}$-block code, we have
\begin{equation*}
 \hat{u}[\ell] = u[\ell]
\end{equation*}
for all $\ell\in\{0, 1, \ldots, k-1\}$ and all $u[\ell]\in \mathbb{F}$, where


  \begin{align*}
       \hat{u}[\ell] =
       \begin{cases}
        \varphi_{\ell+T}(g_1(x[0], e_0),\ldots, g_1(x[\ell+T], e_{\ell+T})) & \text{if $\ell+T\le n-1$,} \\
        \varphi_{\ell+T}(g_1(x[0], e_0),\ldots, g_1(x[n-1], e_{n-1}))&  \text{if $\ell+T> n-1$}
        \end{cases}
        \end{align*}
       with~$g_1$ being the symbol-wise erasure function that was defined in~\eqref{defChannelLaw}.
\end{Definition}
\begin{figure}[t!]
\centering
\includegraphics[height=0.5in]{pointToPointChannelClip.pdf}
\caption{Block code for a point-to-point channel.}
\label{figurePTPchannel}
\end{figure}

The symbols generated by the point-to-point block code described in Definition~\ref{definitionBlockCodePTP} are illustrated in Figure~\ref{figurePTPchannel}, where $[x[0]\ x[1]\ \ldots \ x[n-1]]$ denotes the symbols generated by a systematic block code according to~\eqref{encodingOfBlockCode}. The delay spectrum of a point-to-point block code can be defined in a similar way to that of a point-to-point streaming code (cf.\ Definition~\ref{definitionDelaySpectrumCodePTP}).
\begin{Definition} \label{definitionDelaySpectrumCodePTPblock}
Let~$k$ be a non-negative integer and fix a delay spectrum $\mathbf{\Delta}\triangleq (\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$. Define $T\triangleq \max_{0\le \ell\le k-1} \Delta_\ell$.
A \emph{point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code} over $(\mathrm{u},\mathrm{v})$ is a point-to-point $(n, k, T)_{\mathbb{F}}$-block code (cf.\ Definition~\ref{definitionBlockCodePTP}) which produces estimates of the source symbols at node~$\mathrm{v}$ as follows.
Let $u[\ell]\in\mathbb{F}$ be the source symbol generated by node~$\mathrm{u}$ at time~$\ell$ for each $\ell\in\{0, 1, \ldots, k-1\}$. For each time~$\ell\in\{0, 1, \ldots, k-1\}$, node~$\mathrm{d}$ constructs an estimate of $u[\ell]$ denoted by $\hat u[\ell]$ by time~$\min\{\ell+\Delta_\ell, n-1\}$ based on~$(y[0], y[1], \ldots, y[\min\{\ell+\Delta_\ell, n-1\}])$.
\end{Definition}
\medskip

The following lemma states the delay spectrum of an $N$-achievable point-to-point block code that achieves the rate $C_{T,N}$ as characterized in~\eqref{capacityPTP}.
\begin{Lemma}\label{lemmaBlockCodePTP}
Suppose $T\ge N$, and let $k\triangleq T-N+1$ and $n\triangleq k+N$. For any $\mathbb{F}$ such that $|\mathbb{F}|\ge n$, there exists an $N$-achievable point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code over $(\mathrm{u}, \mathrm{v})$ with delay spectrum
\begin{equation*}
\mathbf{\Delta} = (T, T-1, \ldots, N).
\end{equation*}
\end{Lemma}
\begin{IEEEproof}
Fix any $\mathbb{F}$ such that $|\mathbb{F}|\ge n$ and let $\mathbf{V}^{k\times N}$ be the parity matrix of an MDS code, whose existence is guaranteed due to the explanation given in Section~\ref{notation}. Construct the $(n, k, n-1)$-block code with generator matrix $\mathbf{G}\triangleq [\mathbf{I}_k\ \mathbf{V}^{k\times N}]$ where the decoding delay is at most the number of columns of~$\mathbf{G}$ minus one, i.e., $n-1$. Since the block code is MDS, it is~$N$-achievable. In addition, all the symbols have to be estimated by the end of the block code, which implies that the $(n, k, n-1)$-block code can be viewed as an $(n, k, \mathbf{\Delta})$-block code where
\begin{align*}
\mathbf{\Delta}&\triangleq (n-1, n-2, \ldots, n-k) \\
 & = (T, T-N, \ldots, N).
\end{align*}
\end{IEEEproof}

The following lemma states that we can construct a point-to-point streaming code from a point-to-point block code such that they have the same delay profile and error-correcting capability. The proof is based on periodic interleaving (c.f.\ \cite{Forney1971} and \cite[Sec.\ IV-A]{MartinianSundberg2004})) and is analogous to the proof of~\cite[Lemma~1]{FKLTZA2018}, and therefore is deferred to Appendix~\ref{appendixInterleaving}.
\begin{Lemma} \label{lemmaBlockToStreaming}
Given a point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code which is $N$-achievable, we can construct a point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code which is also $N$-achievable.
\end{Lemma}
{\begin{Remark} \label{remark1}
It follows from the proof of Lemma~\ref{lemmaBlockToStreaming} that the point-to-point streaming code in Lemma~\ref{lemmaBlockToStreaming} is indeed a convolutional code, which is readily seen from the proof of~\cite[Lemma~1]{FKLTZA2018}.
\end{Remark}
}

\begin{Example}\label{exampleBlockToConv}
Suppose we are given a $2$-achievable $(5, 3, (4, 3, 2))_{\mathbb{F}}$-block code with generator matrix
\begin{align*}
\mathbf{G}=\left[\begin{array}{cccccc}1&0&0& 1&1\\0&1&0&1&2\\0&0&1&1&4 \end{array}\right],
\end{align*}
and let $\{\mathbf{u}_i\}_{i\in\mathbb{Z}_+}$ be the streaming messages where $\mathbf{u}_i=\big[u_i[0] \ u_i[1] \ u_i[2]\big]\in \mathbb{F}^{3}$. From time~$i-2$ to $i+5$, the symbols yielded by the $(5, 3, (4, 3, 2))_{\mathbb{F}}$-streaming code constructed by interleaving the length-$5$ block code according Lemma~\ref{lemmaBlockToStreaming} are shown in Table~\ref{tableInterleave}.
\begin{table}[!t]
\centering
\begin{tabular}{|c|*{7}{c|}}\hline
\backslashbox{\small Symbol}{\small Time}

&\makebox[1.5em]{$i-2$}&\makebox[1.5em]{$i-1$}&\makebox[1.5em]{$i$}&\makebox[1.5em]{$i+1$}&\makebox[1.5em]{$i+2$}
&\makebox[1.5em]{$i+3$}&\makebox[1.5em]{$i+4$}\\\hline
$0$ &\red{$\boxed{u_{i-2}[0]}$} &\magenta{$u_{i-1}[0]$} & \blue{$u_i[0]$} &$u_{i+1}[0]$&$u_{i+2}[0]$&$u_{i+3}[0]$ &$u_{i+4}[0]$\\\hline
$1$ & $u_{i-2}[1]$ &$\red{\boxed{u_{i-1}[1]}}$ & $\magenta{u_i[1]}$ & \blue{$u_{i+1}[1]$}&$u_{i+2}[1]$&$u_{i+3}[1]$ &$u_{i+4}[1]$\\\hline
$2$ &$u_{i-2}[2]$ &$u_{i-1}[2]$ & $\red{\boxed{u_i[2]}}$ &\magenta{$u_{i+1}[2]$}& \blue{$u_{i+2}[2]$}&$u_{i+3}[2]$ &$u_{i+4}[2]$\\\hline
$3$ &$\ddots$ & $\ddots$& $\ddots$ &\parbox[c]{0.6 in}{\red{$\boxed{\begin{matrix}u_{i-2}[0]\\ +u_{i-1}[1]\\+ u_{i}[2]\end{matrix}}$}} &  \parbox[c]{0.6 in}{\magenta{$u_{i-1}[0]\\ +u_{i}[1]\\+ u_{i+1}[2]$}}&   \parbox[c]{0.6 in}{\blue{$u_i[0] \\+u_{i+1}[1]\\+ u_{i+2}[2]$}} &$\ddots$\\\hline
$4$ &$\ddots$ &$\ddots$ &$\ddots$  &$\ddots$ &\parbox[c]{0.65 in}{\red{$\boxed{\begin{matrix}u_{i-2}[0]\\ +2u_{i-1}[1]\\+ 4u_{i}[2]\end{matrix}}$}} &  \parbox[c]{0.6 in}{\magenta{$u_{i-1}[0]\\ +2u_{i}[1]\\+ 4u_{i+1}[2]$}}&   \parbox[c]{0.6 in}{\blue{$u_i[0] \\+2u_{i+1}[1]\\+ 4u_{i+2}[2]$}}\\\hline
\end{tabular}\smallskip
\caption{Symbols yielded by a $(5, 3, (4, 3, 2))_{\mathbb{F}}$-streaming code through interleaving a block code.}
\label{tableInterleave}
\end{table}
 The symbols in Table~\ref{tableInterleave} that are highlighted in the same color diagonally (in direction $\searrow$) are encoded using the same block code. Given the fact that each $(5, 3, (4, 3, 2))_{\mathbb{F}}$-block code is $2$-achievable, we can see from Table~\ref{tableInterleave} that $\mathbf{u}_i=\big[u_i[0] \ u_i[1] \ u_i[2]\big]$ can be perfectly recovered by time $i+5$ as long as the erasure sequence is taken from $\Omega_2$.
\end{Example}

The achievability proof of Theorem~\ref{theoremMain} hinges on the next lemma, which investigates the delay profile of a streaming code over the three-node relay network when the streaming code is formed by concatenating two point-to-point codes. More specifically, the resultant first-hop and second-hop delay spectrums of the concatenated codes equal the respective delay spectrums of the two point-to-point codes. The proof of Lemma~\ref{lemmaConcatenation} is straightforward and hence deferred to Appendix~\ref{appendixB}.
\begin{Lemma}\label{lemmaConcatenation}
Fix three natural numbers $k$, $n$ and $m$ such that $k\le \min\{n,m\}$. In addition, let $\mathbf{t}\triangleq (t_0, t_1, \ldots, t_{k-1})$ and $\mathbf{\Delta}\triangleq (\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$ be two delay spectrums. Suppose an $N_1$-achievable point-to-point $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta}_{\mathbb{F}})$-streaming code are given. Then, there exists an $(N_1, N_2)$-achievable $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code over the three-node relay network whose delay profile is
\begin{align}
{\mathbf{d}\triangleq ((t_0,\Delta_0),(t_1,\Delta_1), \ldots, (t_{k-1},\Delta_{k-1})). }\label{delayProfileD}
\end{align}


\end{Lemma}
\section{Achievability Proof of Theorem~\ref{theoremMain}} \label{sectionAchievability}
Fix any $(T, N_1, N_2)$, and fix $\mathbb{F}$ such that $|\mathbb{F}|\ge T+1$. In view of the converse statement~\eqref{converseProofSt} proved in Section~\ref{sectionConverse}, it suffices to prove the existence of an $(N_1, N_2)$-achievable $(\max\{n,m\}, k, T)_{\mathbb{F}}$-streaming code such that
\begin{align}
\frac{k}{\max\{n,m\}} = \min\big\{C_{T-N_2, N_1}, C_{T-N_1, N_2}\big\}, \label{mainResultThmAchievability}
\end{align}
which together with~\eqref{converseProofSt} would imply~\eqref{mainResultThm}.
Since the right hand side of~\eqref{mainResultThmAchievability} equals zero if $T<N_1+N_2$, we assume in the rest of the proof that $T\ge N_1+N_2$.

Define $k\triangleq T-N_1-N_2+1$, $n\triangleq k+N_1$ and $m\triangleq k+N_2$, and we would like to leverage Lemma~\ref{lemmaConcatenation} to prove the existence of an $(N_1, N_2)$-achievable $(\max\{n,m\}, k, T)_{\mathbb{F}}$-streaming code. To this end, we invoke Lemma~\ref{lemmaBlockCodePTP} to obtain an $N_1$-achievable point-to-point $(n, k, \mathbf{t})$-block code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})$-block code where
\begin{equation}
\mathbf{t}\triangleq (T-N_2, T-N_2-1, \ldots, N_1) \label{eq1Achievability}
\end{equation}
and
\begin{equation*}
\mathbf{\Delta}\triangleq (T-N_1, T-N_1-1, \ldots, N_2).
\end{equation*}


Using Lemma~\ref{lemmaBlockToStreaming}, there exist an $N_1$-achievable point-to-point $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})$-streaming code respectively. In addition, by relabeling the~$k$ symbols transmitted at time~$i$ for each $i\in\mathbb{Z}_+$, the $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code can be viewed as an $N_2$-achievable point-to-point $(m, k, \tilde{\mathbf{\Delta}})_{\mathbb{F}}$-streaming code where
\begin{equation}
\tilde{\mathbf{\Delta}}\triangleq (N_2, N_2+1, \ldots, T-N_1). \label{eq2Achievability}
\end{equation}
It then follows from Lemma~\ref{lemmaConcatenation}, \eqref{eq1Achievability} and \eqref{eq2Achievability} that there exists an $(N_1, N_2)$-achievable $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code over the three-node relay network whose delay profile is
\begin{equation}
\mathbf{d}\triangleq ((T-N_2, N_2),(T-N_2-1, N_2+1),\ldots, (N_1, T-N_1)). \label{delayProfile_small_d}
\end{equation}
In particular, the $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code is an $(\max\{n,m\}, k, T)_{\mathbb{F}}$-streaming code that satisfies~\eqref{mainResultThmAchievability}.


 \section{Message-Wise Decode-Forward and Its Achievable Rate} \label{sectionMessageWiseDF}
The following definition of message-wise decode-forward (DF) is consistent with the brief description in Section~\ref{subsecRelatedWork}.
 \begin{Definition} \label{definitionMessageDFCode}
Let $\mathbf{d} =((t_0, \tau_0), (t_1, \tau_1), \ldots, (t_{k-1}, \tau_{k-1}))$ be a delay profile. A \emph{message-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code} is a symbol-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code with the additional delay constraints
\begin{align*}
t_0=t_1=\ldots = t_{k-1}
\end{align*}
and
\begin{align*}
\tau_0=\tau_1=\ldots = \tau_{k-1}.
\end{align*}
 \end{Definition}
 \medskip

 The maximum achievable rate for message-wise DF is characterized in the following definition and theorem.
 \begin{Definition} \label{definitionCapacityMessageDF}
 The maximum achievable rate for message-wise DF is defined as
 \begin{align*}
 R_{T, N_1, N_2}^{\text{message}} \triangleq \sup\left\{\frac{k}{\max\{n,m\}} \left| \,\parbox[c]{3.4 in}{There exists an $(N_1, N_2)$-achievable message-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code for some $n$, $m$, $k$, $\mathbf{d}$ and $\mathbb{F}$ such that $\max_{0\le\ell\le k-1} \{t_\ell+\tau_\ell\}\le T$.}\right. \right\}.
 \end{align*}
 \end{Definition}
 \begin{Theorem} \label{theoremMessageWise}
 Fix any $(T,N_1,N_2)$. {Recalling that the point-to-point capacity satisfies~\eqref{capacityPTP},}
 \begin{align*}
  R_{T, N_1, N_2}^{\text{message}}=\max_{(T_1, T_2): T_1+T_2\le T}\min\big\{C_{T_1, N_1}, C_{T_2, N_2}\big\}. 
 \end{align*}
{In particular, for any~$\mathbb{F}$ with $|\mathbb{F}|\ge T+1$, there exists an $(N_1, N_2)$-achievable message-wise DF $(n, m, k, T)_\mathbb{F}$-streaming code with rate
\begin{align*}
\frac{k}{\max\{n,m\}} =   R_{T, N_1, N_2}^{\text{message}}.
\end{align*}
}

 \end{Theorem}
 \begin{IEEEproof}
 For the achievability part, we first fix any $\mathbb{F}$ with $|\mathbb{F}|\ge T+1$. For any $(T_1, T_2)$ that satisfies $T_1+T_2\le T$, it follows from Lemma~\ref{lemmaBlockCodePTP} that there exists an $N_1$-achievable point-to-point $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code over $(\mathrm{s}, \mathrm{r})$ with delay spectrum
\begin{equation*}
\mathbf{t} = (T_1, T_1, \ldots, T_1)
\end{equation*}
such that
\begin{equation*}
\frac{k}{n}=C_{T_1, N_1},
\end{equation*}
and there exists an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code over $(\mathrm{r}, \mathrm{d})$ with delay spectrum
\begin{equation*}
\mathbf{\Delta} = (T_2, T_2, \ldots, T_2)
\end{equation*}
such that
\begin{equation*}
\frac{k}{m}=C_{T_2, N_2}.
\end{equation*}
 Consequently, it follows from Lemma~\ref{lemmaConcatenation} that
\begin{align*}
 R_{T, N_1, N_2}^{\text{message}}\ge \max_{(T_1, T_2): T_1+T_2\le T}\min\big\{C_{T_1, N_1}, C_{T_2, N_2}\big\}.
\end{align*}

For the converse part, we first fix an arbitrary $(N_1, N_2)$-achievable message-wise DF $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code where $\max_{0\le\ell\le k-1} \{t_\ell+\tau_\ell\}\le T$. By Definition~\ref{definitionMessageDFCode}, there exist non-negative integers $T_1$ and $T_2$ such that $T_1+T_2\le T$ and
\begin{align*}
\mathbf{d} = ((T_1, T_2), (T_1, T_2), \ldots, (T_1, T_2)).
\end{align*}
Since the first-hop and second-hop delay spectrums are $(T_1, T_1, \ldots, T_1)$ and $(T_2, T_2, \ldots, T_2)$ respectively, the $(N_1, N_2)$-achievable $(n, m, k, \mathbf{d})_{\mathbb{F}}$-streaming code restricted to $(\mathrm{s}, \mathrm{r})$ and $(\mathrm{r}, \mathrm{d})$ can be respectively viewed as an $N_1$-achievable point-to-point $(n, k, T_1)$-streaming code and an $N_2$-achievable point-to-point $(m, k, T_2)$-streaming code (cf.\ Definition~\ref{definitionAchievability} and Definition~\ref{definitionSymbolDFCode}). Therefore, we obtain by Theorem~\ref{theoremPTP} that $k/n \le C_{T_1, N_1}$ and $k/m \le C_{T_2, N_2}$. It then follows from Definition~\ref{definitionCapacityMessageDF} that
\begin{align*}
 R_{T, N_1, N_2}^{\text{message}}\le \max_{(T_1, T_2): T_1+T_2\le T}\min\big\{C_{T_1, N_1}, C_{T_2, N_2}\big\}.
\end{align*}
 \end{IEEEproof}

Combining Theorem~\ref{theoremMain} and Theorem~\ref{theoremMessageWise}, we conclude that
 \begin{equation*}
  R_{T, N_1, N_2}^{\text{message}}  < C_{T, N_1, N_2}
 \end{equation*}
 if and only if $T>N_1+N_2$. In other words,
 message-wise DF is sub-optimal if and only if $T>N_1+N_2$. The sub-optimality of message-wise DF can also been seen in Figure~\ref{figure3}, which shows that the set of achievable pairs $(N_1, N_2)$ for symbol-wise DF is strictly larger than that for message-wise DF under the two constraints that $T$ equals $11$ and the rate is no smaller than $2/3$.
 \begin{figure}[!t]
\centering
   \begin{subfigure}{0.45\textwidth}
        \includegraphics[width=0.5\textwidth]{symbolDFachievableErasures.pdf}
        \caption{{Symbol-wise DF with rate $C_{T, N_1, N_2}\ge 2/3$.}}
\end{subfigure}
 \begin{subfigure}{0.45\textwidth}
        \includegraphics[width=0.5\textwidth]{messageDFachievableErasures.pdf}
        \caption{{Message-wise DF with rate $R_{T, N_1, N_2}^{\text{message}}\ge 2/3$.}}
\end{subfigure}
\caption{Set of achievable pairs $(N_1, N_2)$ when $T=11$.}
\label{figure3}
\end{figure}


{\section{An Upper Bound on Loss Probability Attained by Symbol-Wise DF for Random Erasure} \label{sectionLossProbBound}
Our main result stated in Theorem~\ref{theoremMain} characterizes the maximum achievable rate for the three-node relay network subject to deterministic erasures, and the maximum achievable rate can be attained by symbol-wise DF schemes.


{After showing that symbol-wise DF is optimal for the deterministic erasure model, we turn our attention to the more realistic random erasure model as described in Section~\ref{subsecRandomErasures}.} More specifically, we would like to obtain an upper bound on the loss probability attained by the following symbol-wise DF scheme that is used in the achievability proof in Section~\ref{sectionAchievability}:
Fix any $N_1$-achievable point-to-point $(n, k, \mathbf{d})_{\mathbb{F}}$-block code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})$-block code where
\begin{align*}
k&=T-N_1-N_2+1,\\
n&=T-N_1+1,\\
m&=T-N_2+1,\\
\mathbf{d}&=(T-N_2, T-N_2-1, \ldots, N_1)\\
\noalign {\noindent and}
\mathbf{\Delta}&=(N_2, N_2+1, \ldots, T-N_1).
\end{align*}
Then periodically interleave both point-to-point block codes as performed in the proof of Lemma~\ref{lemmaBlockToStreaming} in Appendix~\ref{appendixInterleaving} (illustrated in Table~\ref{tableInterleave}) and obtain an $N_1$-achievable $(n, k, \mathbf{d})_{\mathbb{F}}$-streaming code and an $N_2$-achievable $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code with the following properties:
\begin{enumerate}
\item[(i)] For every $s_i[\ell]$ located at the ${(\ell+1)}^{\text{th}}$ position of the length-$k$ packet transmitted at time~$i$ by the $(n, k, \mathbf{d})_{\mathbb{F}}$-streaming code over~$(\mathrm{s}, \mathrm{r})$, $\hat s_i^{(\mathrm{r})}[\ell]$ is generated by the relay at time~$i-\ell+n-1$. If there are at most~$N_1$ erasures inside the window~$\{i-\ell, i-\ell+1, \ldots, i-\ell+n-1\}$, then $\hat s_i^{(\mathrm{r})}[\ell]=s_i[\ell]$.
\item[(ii)]  For every $u_j[\ell]$ located at the ${(\ell+1)}^{\text{th}}$ position of the length-$k$ packet transmitted at time~$j$ by the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code over~$(\mathrm{r}, \mathrm{d})$, $u_j[\ell]$ can be perfectly recovered by the destination at time~$j+N_2+\ell$ if there are at most~$N_2$ erasures inside the window~$\{j+N_2+\ell-m+1, j+N_2+\ell-m+2, \ldots, j+N_2+\ell\}$.
\end{enumerate}
Then, the two point-to-point streaming codes are concatenated according to Lemma~\ref{lemmaConcatenation} such that every relay estimate~$\hat s_i^{(\mathrm{r})}[\ell]$ is transmitted at the ${(\ell+1)}^{\text{th}}$ position of the length-$k$ packet at time~$j\triangleq i-\ell+n-1$ by the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code over~$(\mathrm{r}, \mathrm{d})$. Then, the following property holds due to Property~(ii):
\begin{enumerate}
\item[(iii)] Every $\hat s_i^{(\mathrm{r})}[\ell]$ transmitted by the relay at time~$i-\ell+n-1$ can be perfectly recovered by the destination at time~$i+N_2+n-1$ if there are at most~$N_2$ erasures inside the window~$\{i+N_2+n-m, i+N_2+n-m+1, \ldots, i+N_2+n-1\}$.
\end{enumerate}
Combining Properties~(i) and~(iii), we conclude that the following $(N_1, N_2)$-acheivability condition holds:
For each $\mathbf{s}_i\in\mathbb{F}^k$, we have $\hat{\mathbf{s}}_i = \mathbf{s}_i$ as long as no more than~$N_1$ erasures occur on~$(\mathrm{s}, \mathrm{r})$ during the time interval~$\{i-k+1, i-k+2, \ldots, i+n-1\}$ and no more than~$N_2$ erasures occur on~$(\mathrm{r}, \mathrm{d})$ during the time interval~$\{i+N_2+n-m, i+N_2+n-m+1, \ldots, i+N_2+n-1\}$. We are ready to obtain an upper bound on the average loss probability
\begin{equation}
P_{T, N_1, N_2}\triangleq\lim_{L\rightarrow \infty} \frac{1}{L}\sum_{i=0}^L \Pr\{\hat{\mathbf{s}}_i \ne \mathbf{s}_i\} \label{defLossProbability}
\end{equation}
achieved by the above symbol-wise DF strategy under the random erasure model.
}


{According to the aforementioned $(N_1, N_2)$-achievability condition, we have
\begin{align}
\Pr\left\{\hat{\mathbf{s}}_i \ne \mathbf{s}_i \left|\, \sum_{\ell=i+N_1}^{i+T-N_2}e_\ell\le N_1,  \sum_{\ell=i-T+2N_1+N_2}^{i+T}\epsilon_\ell\le N_2 \right.\right\}=0 \label{eq1Remark1}
\end{align}
for every~$i\ge T-N_1-N_2$ where $e^\infty$ and $\epsilon^\infty$ denote the random erasure sequences introduced by~$(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ respectively. {Let $\alpha\triangleq\Pr\{e_0=1\}$ and $\beta\triangleq\Pr\{\epsilon_0=1\}$ be two erasure probabilities as defined in Section~\ref{subsecRandomErasures}.} Since
\begin{align}
&\Pr\left\{\bigg\{\sum_{\ell=i-T+N_1+N_2}^{i+T-N_2}e_\ell> N_1\bigg\}\cup\bigg\{\sum_{\ell=i+N_1}^{i+T}\epsilon_\ell> N_2\bigg\}\right\}\notag\\*
&\le \sum_{\ell=N_1+1}^{2T-N_1-2N_2+1} \binom{2T-N_1-2N_2+1}{\ell} \alpha^{\ell}(1-\alpha)^{2T-N_1-2N_2+1-\ell} \notag\\*
&\qquad + \sum_{\ell=N_2+1}^{T-N_1+1} \binom{T-N_1+1}{\ell} \beta^{\ell}(1-\beta)^{T-N_1+1-\ell},\label{eq2Remark1}


\end{align}
it follows from~\eqref{eq1Remark1} that $P_{T, N_1, N_2}$ is bounded above by the right-hand side of~\eqref{eq2Remark1}, which implies that
\begin{align*}
P_{T, N_1, N_2} \le \kappa_1(T, N_1, N_2) \cdot \alpha^{N_1+1}+\kappa_2(T, N_1, N_2) \cdot\beta^{N_2+1}
\end{align*}
for some positive constants $\kappa_1(T, N_1, N_2)$ and $\kappa_2(T, N_1, N_2)$ that do not depend on~$\alpha$ and~$\beta$. In other words, $P_{T, N_1, N_2}$ decays exponentially fast in~$\min\{N_1+1, N_2+1\}$.

}

\section{Numerical Results} \label{sectionNumerical}


{Recall that the motivation of this work is to find streaming codes that perform well not only for the deterministic model described in Section~\ref{subsecDetErasures}, but also for the random model described in Section~\ref{subsecRandomErasures}.} Therefore, we consider a statistical three-node relay network where i.i.d.\ erasures are independently introduced to both channels, and let $\alpha$ and~$\beta$ be the respective probabilities of experiencing an erasure in each time slot for channels~$(\mathrm{s}, \mathrm{r})$ and $(\mathrm{r}, \mathrm{d})$.
We will compare the symbol-wise DF and message-wise DF schemes constructed by concatenating point-to-point streaming codes as prescribed by Lemma~\ref{lemmaBlockCodePTP} (constructing block codes), Lemma~\ref{lemmaBlockToStreaming} (constructing point-to-point streaming codes from block codes) and Lemma~\ref{lemmaConcatenation} (constructing DF schemes by concatenating two point-to-point streaming codes). More precisely, we will consider symbol-wise DF and message-wise DF schemes constructed by concatenating an $(n, k, T_1)_\mathbb{F}$-streaming code and an $(m, k, T_2)_\mathbb{F}$-streaming code where $\mathbb{F}$ is chosen to satisfy $|\mathbb{F}|\ge T+1$. We will also consider an instantaneous forwarding (IF) strategy which uses a point-to-point streaming code (as prescribed by Lemma~\ref{lemmaBlockCodePTP} and Lemma~\ref{lemmaBlockToStreaming}) over the three-node relay network as if the network is a point-to-point channel. More specifically, under the IF strategy, the source transmits symbols generated by the streaming code and the relay forwards every symbol received from $(\mathrm{s}, \mathrm{r})$ to $(\mathrm{r}, \mathrm{d})$ in each time slot. The overall point-to-point channel induced by the IF strategy experiences an erasure if either one of the channels experiences an erasure. It follows from~\eqref{capacityPTP} that the IF strategy achieves the theoretic rate $C_{T, N_1+N_2}$.

In order to demonstrate the advantage of using symbol-wise DF over message-wise DF and IF,
we investigate their loss probabilities {as defined in~\eqref{defLossProbability}} where each loss probability is approximated by simulating the schemes over~$10^8$ channel uses.
Suppose~$T=11$. Choose an arbitrary finite field $\mathbb{F}$ with $|\mathbb{F}|\ge T+1=12$. For each~$N$ and~$\bar T$ satisfying $N\le \bar T\le T$, it follows from Lemma~\ref{lemmaBlockCodePTP} that an $N$-achievable point-to-point $(n, k, \mathbf{\Delta})_\mathbb{F}$-streaming code with
$\mathbf{\Delta}=(\bar T, \bar T-1, \ldots, N)$, $k=\bar T-N+1$ and
$n=\bar T+1$
 always exists, and we will refer such an $(n, k, \mathbf{\Delta})_\mathbb{F}$-streaming code as an $(n, k, \bar T)_\mathbb{F}$-streaming code in the rest of this section. We would like to investigate the error-correcting capabilities of all symbol-wise DF, message-wise DF and IF schemes with delay~$T=11$ whose coding rates are greater than or equal to~$2/3$. Our simulation results reveal the following:
\begin{enumerate}
\item Note that there are~$18$ combinations of $(N_1, N_2)$ for symbol-wise DF schemes with delay~$T=11$ and rate no less than~$2/3$ as shown in Figure~\ref{figure3}a. The symbol-wise DF scheme with parameters~$(N_1, N_2)=(3,3)$ and rate~$2/3$ that is constructed by concatenating two copies of $3$-achievable point-to-point $(9, 6, 8)_{\mathbb{F}}$-streaming code achieves the {largest $N_1+N_2$}. 
\item {Note that there are~$15$ combinations of $(N_1, N_2)$ for message-wise DF schemes with delay~$T=11$ and rate no less than~$2/3$ as shown in Figure~\ref{figure3}b. The message-wise DF scheme with parameters~$(N_1, N_2)=(2,2)$ and rate~$2/3$ that is constructed by concatenating two copies of $2$-achievable point-to-point $(6, 4, 5)_{\mathbb{F}}$-streaming code {achieves the largest $N_1+N_2$}.
     
     Although the message-wise DF with parameters~$(N_1, N_2)=(2,2)$ that is constructed by concatenating a $2$-achievable point-to-point $(6, 4 , 5)_{\mathbb{F}}$-streaming code and a $2$-achievable point-to-point $(7, 5, 6)_{\mathbb{F}}$-streaming code achieves the same rate~$2/3$, it is inferior to the aforementioned one because a point-to-point $(6, 4, 5)_{\mathbb{F}}$-streaming code can correct more erasure patterns than a point-to-point $(7, 5, 6)_{\mathbb{F}}$-streaming code.} For example, the periodic erasure pattern shown in Figure~\ref{figure4} can be perfectly recovered by a point-to-point $(6, 4, 5)_{\mathbb{F}}$-streaming code but not a point-to-point $(7, 5, 6)_{\mathbb{F}}$-streaming code.
\item Note that the set of parameters~$(N_1, N_2)$ that can be chosen by an IF scheme with rate no less than~$2/3$ is~$\{(N_1, N_2): N_1+N_2\le 4\}$ because an IF strategy with parameters $(N_1, N_2)$ achieves the theoretic rate $C_{11, N_1+N_2}=\frac{12-(N_1+N_2)}{12}$. The IF scheme that uses a $4$-achievable point-to-point $(12, 8, 11)_{\mathbb{F}}$-streaming code achieves rate~$2/3$ and the {largest $N_1+N_2=4$}.  
\end{enumerate}
\begin{figure}[t!]
\centering
\includegraphics[width=3.5in]{erasurePattern3.pdf}
\caption{A periodic erasure sequence with period $6$.}
\label{figure4}
\end{figure}
We plot in Figure~\ref{figure5} the loss probabilities of the aforementioned symbol-wise DF, message-wise DF and IF schemes with {largest $N_1+N_2$}. {The upper bound~\eqref{eq2Remark1} on the loss probability for symbol-wise DF with $T=11$, $N_1=N_2=3$ and $\alpha=\beta$ is also plotted on the same figure.}
As shown in Figure~\ref{figure5}, symbol-wise DF uniformly outperforms both message-wise DF and IF for $0.01 \le\alpha=\beta\le 0.2$ where each scheme is operated at rate~$2/3$ with decoding delay~$T=11$.
\begin{figure}[t!]
\centering
\includegraphics[width=4.5in]{IIDmodelPlotRevised.pdf}
\caption{{Loss probabilities for symbol-wise DF, message-wise DF and IF with $T=11$, rate~$2/3$ and largest $N_1+N_2$ where $\alpha$ denotes the symmetric erasure probability.}}
\label{figure5}
\end{figure}

\section{Extension to Sliding Window Model} \label{sectionSlidingWindow}
{Consider the following sliding window model: Channels~$(\mathrm{s},\mathrm{r})$ and $(\mathrm{r},\mathrm{d})$ introduce at most~$N_1$ and~$N_2$ erasures respectively in any period of $T+1$ consecutive time slots (sliding window of size $T+1$). Under the sliding window model described above, we let $C_{T, N_1, N_2}^{\text{SW}}$ be the $(T, N_1, N_2)$-capacity as defined for the deterministic model in Definition~\ref{defCapacity}. Our goal is to show that
\begin{equation}
C_{T, N_1, N_2}^{\text{SW}} = C_{T, N_1, N_2}. \label{eqSlidingWinStatement}
\end{equation}
 Since any $N_1$-erasure sequence can be introduced by channel~$(\mathrm{s},\mathrm{r})$ and any $N_2$-erasure sequence can be introduced by channel~$(\mathrm{r},\mathrm{d})$ in the sliding window model, we have  \begin{equation}
 C_{T, N_1, N_2}^{\text{SW}} \le C_{T, N_1, N_2}. \label{eqSlidingWinConverse}
  \end{equation}
  It remains to show that
 \begin{equation}
 C_{T, N_1, N_2}^{\text{SW}} \ge C_{T, N_1, N_2}. \label{eqSlidingWinAch}
  \end{equation}
  Therefore, it suffices to show that the achievability streaming scheme presented in Section~\ref{sectionAchievability} can be used to achieve $C_{T, N_1, N_2}$ in the sliding window model.
Fix any $(T, N_1, N_2)$, and fix $\mathbb{F}$ such that $|\mathbb{F}|\ge T+1$. Since $C_{T, N_1, N_2}=0$ if $T<N_1+N_2$, we assume in the rest of this section that $T\ge N_1+N_2$. As in Section~\ref{sectionAchievability}, define $k\triangleq T-N_1-N_2+1$, $n\triangleq k+N_1$ and $m\triangleq k+N_2$, and we would like to prove the existence of a $(\max\{n,m\}, k, T)_{\mathbb{F}}$-streaming code that corrects all erasures in the sliding window model. To this end, we invoke Lemma~\ref{lemmaBlockCodePTP} to obtain an $N_1$-achievable point-to-point $(n, k, \mathbf{t})$-block code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})$-block code that satisfy~\eqref{eq1Achievability} and~\eqref{eq2Achievability} respectively. 


It then follows from the proof of Lemma~\ref{lemmaBlockToStreaming} and the proof of Lemma~\ref{lemmaConcatenation} that there exists a $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code with delay profile specified in~\eqref{delayProfile_small_d} such that every message can be recovered as long as the following two conditions hold:
\begin{enumerate}
\item Channel~$(\mathrm{s},\mathrm{r})$ introduces at most~$N_1$ erasures in any period of $n$ consecutive time slots.
\item Channel $(\mathrm{r},\mathrm{d})$ introduces at most~$N_2$ erasures in any period of $m$ consecutive time slots.
\end{enumerate}
Since the two conditions simultaneously hold under the sliding window model, the $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code can recover every message. Consequently, \eqref{eqSlidingWinAch} holds, which together with~\eqref{eqSlidingWinConverse} implies that~\eqref{eqSlidingWinStatement} holds.
}


\section{Concluding Remarks}\label{sectionConclusion}
The maximum coding rate of streaming codes with decoding delay~$T$ that correct $N_1$ and $N_2$ erasures introduced by the respective channels~$(\mathrm{s},\mathrm{r})$ and $(\mathrm{s},\mathrm{r})$ is proved to be $C_{T, N_1, N_2}$ as stated in Theorem~\ref{theoremMain}. The maximum coding rate can be achieved by symbol-wise DF. Symbol-wise DF outperforms message-wise DF if and only if $T>N_1+N_2$ as shown in Section~\ref{sectionMessageWiseDF}.

{The maximum coding rate remain unchanged in the more general sliding window model described in Section~\ref{sectionSlidingWindow}.}
Numerical results in Section~\ref{sectionNumerical} demonstrate that symbol-wise DF outperforms both message-wise DF and IF for some three-node relay network where the channels are subject to i.i.d.\ erasures.

{Since packet erasures often occur in a bursty manner~\cite{Bolot1993,Paxson1999} in addition to a sparse manner, future work may explore streaming codes over the three-node relay network that correct both burst and arbitrary erasures and investigate the corresponding maximum coding rate, similar to the studies carried out for the point-to-point channel in~\cite{BPKTA17,FKLTZA2018}.}  Another direction may generalize the existing streaming models for point-to-point channels~\cite{LeungHo2012, LQH2013, AdlerCassuto2017} and investigate the corresponding streaming codes over the three-node relay network. As explained in Introduction, the motivation behind studying streaming codes over the three-node relay network is to explore streaming codes that are suitable for low-latency applications in a practical cloud CDN that spans across continents. Therefore, future studies may implement the symbol-wise DF, message-wise DF and IF relaying strategies over data centers in practical cloud CDNs.
 


\appendices

\section{Derivations in the Converse Proof of Theorem~\ref{theoremMain}} \label{appendixDerivation}
\begin{IEEEproof}[Derivation of~\eqref{eqn5ConverseProof}]
  For all $\ell\in\mathbb{Z}_+$,
 \begin{align}
 \left|\parbox[c]{4.4 in}{$\{\ell, \ell+1, \ldots, \ell+T-N_2\}\cap \\\left\{{i(T-N_2+1)}, {1+i(T-N_2+1)}, \ldots, {T-N_1-N_2+i(T-N_2+1)}\right\}_{i=0}^{j}$}\right| = T-N_1-N_2+1.   \label{eq1AppendixDerivation}
 \end{align}
Using the chain rule, we have
\begin{align*}
&H\left(\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{T-N_2+(j-1)(T-N_2+1)} \left|  \left\{\mathbf{x}_{i(T-N_2+1)}, \mathbf{x}_{1+i(T-N_2+1)}, \ldots, \mathbf{x}_{T-N_1-N_2+i(T-N_2+1)}\right\}_{i=0}^{j}  \right.\right)\notag\\*
&\quad = \sum_{\ell=0}^{\substack{T-N_2+\\(j-1)(T-N_2+1)}}\!\!\!\!\!\!H\left(\mathbf{s}_\ell \left|  \left\{\mathbf{x}_{i(T-N_2+1)}, \mathbf{x}_{1+i(T-N_2+1)}, \ldots, \mathbf{x}_{T-N_1-N_2+i(T-N_2+1)}\right\}_{i=0}^{j}, \mathbf{s}_0, \mathbf{s}_1,\ldots,  \mathbf{s}_{\ell-1}   \right.\right)\\*

&\quad \le 0
\end{align*}
where the inequality is due to~\eqref{eq1AppendixDerivation} and~\eqref{eqn4ConverseProof}.
\end{IEEEproof}

\begin{IEEEproof}[Derivation of~\eqref{eqn8ConverseProof}]
Since the $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code restricted to channel~$(\mathrm{s},\mathrm{r})$ can be viewed as a point-to-point streaming code with rate $k/n$ and delay~$T-N_2$ which can correct the periodic erasure sequence $\tilde e^\infty$ illustrated in Figure~\ref{figure1}, it follows from the arguments in \cite[IV-A]{BPKTA17} that~\eqref{eqn8ConverseProof} holds. For the sake of completeness, we present a rigorous proof below.

Using~\eqref{eqn5ConverseProof}, we have
\begin{align}
|\mathbb{F}|^{k\times j(T-N_2+1)} &\le |\mathbb{F}|^{n\times(j+1)(T-N_2-N_1+1)} \label{eqn11ConverseProof}
\end{align}
because $j(T-N_2+1)$ source messages can take $|\mathbb{F}|^{k\times j(T-N_2+1)}$ values and $(j+1)(T-N_2-N_1+1)$ source packets can take at most $|\mathbb{F}|^{n\times (j+1)(T-N_2-N_1+1)}$ values for each $j$.
Taking logarithm on both sides of~\eqref{eqn11ConverseProof} followed by dividing both sides by~$j$, we have
\begin{align}
k(T-N_2+1)  \le n (1+1/j)(T-N_1-N_2+1). \label{eqn12ConverseProof}
\end{align}
Since \eqref{eqn12ConverseProof} holds for all $j\in\mathbb{N}$, it follows that~\eqref{eqn8ConverseProof} holds.
\end{IEEEproof}

\begin{IEEEproof}[Derivation of~\eqref{eqn10ConverseProof}]
 For all $\ell\in\mathbb{Z}_+$,
 \begin{align}
& \left|\parbox[c]{5.1 in}{$\{\ell+N_1, \ell+N_1+1, \ldots, \ell+T\}\cap \\\left\{{N_1+N_2+i(T-N_1+1)}, {N_1+N_2+1+i(T-N_1+1)}, \ldots, {T+i(T-N_1+1)}\right\}_{i=0}^{j}$}\right| \notag\\
&\quad = T-N_1-N_2+1.   \label{eq3AppendixDerivation}
 \end{align}
Using the chain rule, we have
\begin{align*}
&H\left(\mathbf{s}_0, \mathbf{s}_1, \ldots, \mathbf{s}_{T-N_1+(j-1)(T-N_1+1)} \left|  \left\{\mathbf{x}_{N_1+N_2+i(T-N_1+1)}^{(\mathrm{r})}, \mathbf{x}_{N_1+N_2+1+i(T-N_1+1)}^{(\mathrm{r})}, \ldots, \mathbf{x}_{T+i(T-N_1+1)}^{(\mathrm{r})}\right\}_{i=0}^{j}  \right.\right)\notag\\*
&\quad = \sum_{\ell=0}^{\substack{T-N_1+\\(j-1)(T-N_1+1)}}\!\!\!\!\!\!H\left(\mathbf{s}_\ell \left|  \left\{\mathbf{x}_{N_1+N_2+i(T-N_1+1)}^{(\mathrm{r})}, \mathbf{x}_{N_1+N_2+1+i(T-N_1+1)}^{(\mathrm{r})}, \ldots, \mathbf{x}_{T+i(T-N_1+1)}^{(\mathrm{r})}\right\}_{i=0}^{j}, \mathbf{s}_0, \mathbf{s}_1,\ldots,  \mathbf{s}_{\ell-1}   \right.\right)\\*
&\quad \le 0
\end{align*}
where the inequality is due to~\eqref{eq3AppendixDerivation} and~\eqref{eqn9ConverseProof}.
\end{IEEEproof}

\begin{IEEEproof}[Derivation of~\eqref{eqn13ConverseProof}]
Since the $(N_1, N_2)$-achievable $(n, m, k, T)_{\mathbb{F}}$-streaming code restricted to channel~$(\mathrm{r},\mathrm{d})$ can be viewed as an $N_2$-achievable point-to-point $(m, k, T-N_1)_{\mathbb{F}}$-streaming code that can correct the periodic erasure sequence $\hat e^\infty$ illustrated in Figure~\ref{figure2}, it follows from the arguments in \cite[IV-A]{BPKTA17} that~\eqref{eqn13ConverseProof} holds. For the sake of completeness, we present a rigorous proof below.

Since $j(T-N_1+1)$ source messages can take $|\mathbb{F}|^{k\times j(T-N_1+1)}$ values and $(j+2)(T-N_1-N_2+1)$ relay transmitted packets can take at most $|\mathbb{F}|^{m\times (j+2)(T-N_1-N_2+1)}$ values for each $j$,  it follows from~\eqref{eqn10ConverseProof} that
\begin{align}
|\mathbb{F}|^{k\times j(T-N_1+1)} &\le |\mathbb{F}|^{m\times(j+2)(T-N_1-N_2+1)}. \label{eqn6ConverseProof}
\end{align}
Taking logarithm on both sides of~\eqref{eqn6ConverseProof} followed by dividing both sides by~$j$, we have
\begin{align}
k(T-N_1+1)  \le m (1+2/j)(T-N_1-N_2+1). \label{eqn7ConverseProof}
\end{align}
Since \eqref{eqn7ConverseProof} holds for all $j\in\mathbb{N}$, it follows that~\eqref{eqn13ConverseProof} holds.
\end{IEEEproof}

\section{Proof of Lemma~\ref{lemmaBlockToStreaming}} \label{appendixInterleaving}
Fix a natural number~$k$ and a delay spectrum~$\mathbf{\Delta}=(\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$. Suppose we are given an $N$-achievable point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code over $(\mathrm{u},\mathrm{v})$, and let
\begin{align*}
\mathbf{G}=[\,\mathbf{I}_k \ \mathbf{P}]\in\mathbb{F}^{k\times n}
\end{align*}
 be the generator matrix. By Definition~\ref{definitionAchievabilityBlockPTP}, the $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code has the following properties:
\begin{enumerate}
\item[(i)] The length of the block code is~$n$.
\item[(ii)] From time $0$ to $k-1$, the source symbols
\begin{align*}
\big[x[0] \ x[1]\ \cdots \ x[k-1]\big]=\big[s[0]\ s[1]\ \cdots \ s[k-1]\big]
\end{align*}
     are transmitted.
    \item[(iii)] From time $k$ to $n-1$, the parity-check symbols
\begin{align*}
\big[x[k] \ x[k+1]\ \cdots \ x[n-1]\big]=\big[s[0]\ s[1]\ \cdots \ s[k-1]\big]\, \mathbf{P}
\end{align*}
     are transmitted.
 \item[(iv)] Let $\Delta_{\ell,n}\triangleq\min\{\Delta_\ell, n-1-\ell\}$ to simplify notation. Upon receiving
 \begin{align*}
 &\big[y[0]\ y[1]\ \ldots\ y[\ell + \Delta_{\ell, n}]\big] \notag\\
 &\quad=  \big[g_1(x[0], e_0)\ g_1(x[1], e_1)\ \ldots\ g_1(x[\ell + \Delta_{\ell, n}], e_{\ell + \Delta_{\ell, n}})\big],
 \end{align*}
  the destination can perfectly recover $s[\ell]$ by time $\ell + \Delta_{\ell, n}$ for each $\ell\in\{0, 1, \ldots, k-1\}$ as long as $e^\infty\in\Omega_{N}$.
\end{enumerate}

In order to construct an~$N$-achievable point-to-point $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code (cf.\ Definition~\ref{definitionDelaySpectrumCodePTPblock}), we first let $\{\mathbf{u}_i\}_{i=0}^\infty$ denote a sequence of length-$k$ packets
 and let $u_i[\ell]$ denote the $(\ell+1)^{\text{th}}$ element of $\mathbf{u}_i$ such that
\begin{align}
\mathbf{u}_i \triangleq [u_i[0]\ u_i[1]\ \cdots \ u_i[k-1] ] \label{defSiAppendixA}
\end{align}
for all $i\in\mathbb{Z}_+$. Then, construct
\begin{align}
\big[x_i[0]\ x_{i+1}[1]\ \cdots \ x_{i+n-1}[n-1] \big] \triangleq \big[u_i[0]\ u_{i+1}[1]\ \cdots \ u_{i+k-1}[k-1] \big] \mathbf{G} \label{appendixAeq1}
\end{align}
for each $i\in\mathbb{Z}_+$ where $\mathbf{G}$ is the generator matrix of the $N$-achievable $(n, k, T)_{\mathbb{F}}$-block code. In other words, we are coding $\mathbf{u}_i$ diagonally as illustrated in Table~\ref{tableInterleave}.
At each time $i\in\mathbb{Z}_+$, node~$\mathrm{u}$ transmits
\begin{align}
\mathbf{x}_i^{(\mathrm{u})}\triangleq \big[x_i[0]\ x_i[1]\ \cdots \ x_i[n-1]\big]. \label{defXiAppendixA}
\end{align}
 Based on the $N$-achievable $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-block code which satisfies Properties~(i) to~(iv) as stated at the beginning of this proof, we construct an $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code where $\mathbf{u}_i$ and $\mathbf{x}_i^{(\mathrm{u})}$ satisfy~\eqref{defSiAppendixA}, \eqref{appendixAeq1} and~\eqref{defXiAppendixA}. Our goal is to show that the streaming code is $N$-achievable. To this end, we fix any $i\in\mathbb{Z}_+$ and any $e^\infty\in\Omega_N$, and would like to show that node~$\mathrm{v}$ can perfectly recover $\mathbf{u}_i=\big[u_i[0]\ u_i[1]\ \cdots \ u_i[k-1]\big]$ based on
  \begin{align}
 [\mathbf{y}_0^{(\mathrm{v})}\ \mathbf{y}_1^{(\mathrm{v})}\ \ldots\ \mathbf{y}_{i+T}^{(\mathrm{v})}]=  [g_n(\mathbf{x}_0^{(\mathrm{u})}, e_0)\ g_n(\mathbf{x}_1^{(\mathrm{u})}, e_1)\ \ldots\ g_n(\mathbf{x}_{i+T}^{(\mathrm{u})}, e_{i+T})]. \label{appendixAeq5}
 \end{align}
According to~\eqref{defXiAppendixA}, for each $i\in\mathbb{Z}_+$, $\big[x_i[0]\ x_{i+1}[1]\ \cdots \ x_{i+n-1}[n-1]\big]$ are transmitted from time~$i$ to $i+n-1$. Therefore, it follows from~\eqref{appendixAeq1}, Property~(iv) and~\eqref{appendixAeq5} that for each $i\in\mathbb{Z}_+$ and each $\ell\in\{0, 1, \ldots, k-1\}$, the destination can perfectly recover $u_i[\ell]$ by time $i+\Delta_\ell$ based on $ [\mathbf{y}_i^{(\mathrm{v})}\ \mathbf{y}_{i+1}^{(\mathrm{v})}\ \ldots\ \mathbf{y}_{i+\Delta_\ell}^{(\mathrm{v})}]$. Consequently, for any $i\in\mathbb{Z}_+$ and any $e^\infty\in\Omega_N$, the destination can perfectly recover $u_i[\ell]$ by time $i+\Delta_\ell$ for each~$\ell\in\{0, 1, \ldots, k-1\}$, which implies by Corollary~\ref{corollaryAchievable} that the $(n, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code is $N$-achievable.


\section{Proof of Lemma~\ref{lemmaConcatenation}} \label{appendixB}
 Suppose we are given an $N_1$-achievable point-to-point $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code and an $N_2$-achievable point-to-point $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code where
$\mathbf{t}=(t_0, t_1, \ldots, t_{k-1})$ and $\mathbf{\Delta}=(\Delta_0, \Delta_1, \ldots, \Delta_{k-1})$.
  We would like to concatenate the two codes over the three-node relay network such that the $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code and the $(m, k, \mathbf{\Delta})$ are used over~$(\mathrm{s}, \mathrm{r})$ and~$(\mathrm{r}, \mathrm{d})$ respectively. To this end, we first let $\{f_i^{(\mathrm{s})}\}_{i\in\mathbb{Z}_+}$ and $\{f_i^{(\mathrm{r})}\}_{i\in\mathbb{Z}_+}$ be the encoding functions of the $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code and the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code respectively. Consider the following symbol-wise DF scheme constructed by concatenating the two point-to-point codes.

 For each time~$i\in\mathbb{Z}_+$, let $\mathbf{s}_i= \big[s_i[0] \ s_i[1] \ \ldots s_i[k-1]\big]$ denote the~$k$ symbols transmitted by node~$\mathrm{s}$, let
 \begin{align*}
 
 \mathbf{x}_i^{(\mathrm{s})}\triangleq f_i^{(\mathrm{s})}(\mathbf{s}_0, \mathbf{s}_1, \ldots,\ \mathbf{s}_{i})
 \end{align*}
  be the length-$n$ source packet generated by the $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code,
  and let
   \begin{align*}
\hat {\mathbf{s}}_i^{(\mathrm{r})}\triangleq \big[\hat s_{i-t_0}^{(\mathrm{r})}[0] \ \hat s_{i-t_1}^{(\mathrm{r})}[1] \ \ldots \ \hat s_{i-t_{k-1}}^{(\mathrm{r})}[k-1]\big]
 \end{align*}
 be the~$k$ estimates for~$s_{i-t_0}[0], s_{i-t_1}[1], \ldots, s_{i-t_{k-1}}[{k-1}]$ constructed by the $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code.

 In addition, let
  \begin{align*}
 
 \mathbf{x}_i^{(\mathrm{r})}\triangleq f_i^{(\mathrm{r})}(\hat {\mathbf{s}}_0^{(\mathrm{r})}, \hat {\mathbf{s}}_1^{(\mathrm{r})}, \ldots,\ \hat {\mathbf{s}}_i^{(\mathrm{r})})
 \end{align*}
  be the length-$m$ relay transmitted packet generated by the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code,
   and let
   \begin{align*}
\hat {\mathbf{s}}_i^{(\mathrm{d})}\triangleq \big[\hat s_{i-t_0-\Delta_0}^{(\mathrm{d})}[0] \ \hat s_{i-t_1-\Delta_1}^{(\mathrm{d})}[1] \ \ldots \ \hat s_{i-t_{k-1}-\Delta_{k-1}}^{(\mathrm{d})}[k-1]\big]
 \end{align*}
 be the~$k$ estimates for~$\hat s_{i-t_0}^{(\mathrm{r})}[0], \hat s_{i-t_1}^{(\mathrm{r})}[1], \ldots, \hat s_{i-t_{k-1}}^{(\mathrm{r})}[k-1]$ constructed by the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code.

 Fix any erasure sequences $e^\infty\in\Omega_{N_1}$ and $\epsilon^\infty\in\Omega_{N_2}$. Since the $(n, k, \mathbf{t})_{\mathbb{F}}$-streaming code is $N_1$-achievable,
 \begin{align}
 \hat s_{i-t_\ell}^{(\mathrm{r})}[\ell] = s_{i-t_\ell}[\ell] \label{appendixBeq1}
 \end{align}
 for all $i\in\mathbb{Z}_+$ and all $\ell\in\{0, 1, \ldots, k-1\}$. Similarly, since the $(m, k, \mathbf{\Delta})_{\mathbb{F}}$-streaming code is $N_2$-achievable,
  \begin{align}
 \hat s_{i-t_\ell-\Delta_\ell}^{(\mathrm{d})}[\ell] = \hat s_{i-t_\ell-\Delta_\ell}^{(\mathrm{r})}[\ell] \label{appendixBeq2}
 \end{align}
 for all $i\in\mathbb{Z}_+$ and all $\ell\in\{0, 1, \ldots, k-1\}$. Combining~\eqref{appendixBeq1} and~\eqref{appendixBeq2}, we have
 \begin{align}
 \hat s_{i-t_\ell-\Delta_\ell}^{(\mathrm{d})}[\ell] = s_{i-t_\ell-\Delta_\ell}[\ell] \label{appendixBeq3}
 \end{align}
 for all $i\in\mathbb{Z}_+$ and all $\ell\in\{0, 1, \ldots, k-1\}$. Since~\eqref{appendixBeq3} holds for any $e^\infty\in\Omega_{N_1}$ and $\epsilon^\infty\in\Omega_{N_2}$, the resultant concatenated code is an $(N_1, N_2)$-achievable $(\max\{n,m\}, k, \mathbf{d})_{\mathbb{F}}$-streaming code where $\mathbf{d}$ is as defined in~\eqref{delayProfileD}.


 \section*{Acknowledgment}
 We would like to thank the Associate Editor Prof. Bikash Dey and the two anonymous reviewers for the useful comments that help us to improve the presentation of this paper.


\ifCLASSOPTIONcaptionsoff
  \newpage
\fi
{"config": "arxiv", "file": "1806.09768/streamingRelayV2.tex"}