text:
\section{Introduction}

In recent years, there has been an enormous interest in the design and deployment of wireless networks. Such networks are indispensable for providing ubiquitous network coverage and have many applications in both civil and  military areas.

Recently, it was observed that the broadcast nature of wireless networks can be exploited in order to increase throughput and reduce energy consumption. In a wireless environment, each packet is broadcasted within a small neighborhood, which allows the neighboring nodes to overhear packets sent by their neighbors. When a node needs to transmit packets, it can employ the \emph{opportunistic coding} \cite{WPCPC06,KRHKMC06} approach that uses the knowledge of what the node's neighbors have heard in order to reduce the number of transmissions. With this approach, each transmitted packet is a linear combination of the original packets over a certain finite field.

\begin{example}\label{ex:example1}
Consider the network depicted in \mbox{Figure~\ref{fig:op:coding}}. In this
example,  the central node, referred to as a server, needs to deliver four packets $p_1,\dots, p_4$ to four clients $c_1,\dots,c_4$; packet $p_i$ needs to be received by client $c_i$. Each client $c_i$  has an access to some of the packets overheard from prior transmissions. This set is referred to as its ``has'' set. It is easy to verify that all clients can be satisfied by broadcasting two packets $p_1+p_2+p_3$ and $p_1+p_4$ (all additions are over $GF(2))$. Since without network coding all packets $p_1,\dots, p_4$ are needed to be transmitted, network coding allows to reduce the number of transmissions by $50\%$.
\end{example}

\begin{figure}[t]
\begin{center}
\epsfig{file=broad.eps, scale=0.25}
 \caption{Broadcast coding network \label{fig:op:coding}}%
\end{center}
\end{figure}

In this paper, we focus on the single hop wireless  setting and
consider the problem of minimizing the number of broadcast
transmissions necessary to satisfy all the clients. Our contributions
can be summarized as follows. First, we prove that the problem of determining the minimum number of transmissions over $GF(2)$ is
NP-complete. Next, we show that the number of transmissions may depend on the size of the finite field, and that such a dependence is not necessarily  monotonic. Further, we prove that the problem of finding the size of the finite field which results in the minimum number of transmissions is an NP-hard problem. Next, we establish lower and upper bounds on the \emph{coding advantage}, i.e., the ratio between the total number of packets and the minimum number of transmissions that can be achieved by using network coding.  In particular, we show that the coding advantage depends on the size of the``\emph{has}'' sets. Next, we evaluative the value of coding advantage in random settings. Finally, we present a heuristic solution based on graph coloring and verify its performance through simulations.

The considered problem is a special case of the general \emph{network
coding} \cite{ACLY00} problem for non-multicast networks. The
general network coding problem has recently attracted a large body of research (see e.g., \cite{L05,LL04} and references therein), however, many of the  results (such as NP-hardness) cannot be immediately extended to our problem.

While we present our results in the context  of wireless data
transmission, the considered problem is very general and can arise in many other practical settings. For example, consider a content distribution network that needs to deliver a set of large files (such as video clips) to different clients. In this setting, if some of the files are already available for some clients, the distribution can be efficiently implemented by multicasting a (small) set of linear combinations of the original files.

\section{Model}\label{sec:model}

We consider a one-hop wireless channel with a single server $s$ and a set of $m$ clients $C=\{c_1,\dots,c_m\}$. The server needs to transmit a set $P=\{p_1,p_2,\dots,p_n\}$ of packets to the clients. Each client requires a certain subset of packets in $P$, while some packets in $P$ are already available to it. Specifically, each client $c_i\in C$ is associated with two sets:
\begin{itemize}
\item $W(c_i)\subseteq P$ - the set of packets required by $c_i$.
\item $H(c_i)\subseteq P$ - the set of packets available at $c_i$;
\end{itemize}
We refer to $W(c_i)$ and $H(c_i)$ as the ``wants'' and ``has'' sets of $c_i$, respectively.
The server can transmit any packet from $P$ as well as linear
combinations (over $GF(q)$) of packets in $P$. Each transmission $i$
is specified by an encoding vector $g_i=\{g_i^j\}\in GF(q)^n$ such that
the packet $x_i$ transmitted in communication round $i$ is equal to $x_i=\sum_{j=1}^ng_i^j\cdot p_j$.
The practical issues related to this model are discussed in \cite{KRHKMC06}.

Our goal is to find the set of encoding vectors $\Phi=\{g_i\}$ of minimum cardinality that allow each client to decode the packets it requested. We refer to this problem as Problem \emph{MIN-T-q}.

\begin{problm}[MIN-T-q]\label{prob:MIN-T}
Find the minimum number of transmissions and the corresponding set $\Phi$ of encoding vectors  $\{g_i\}$, $g_i=\{g_i^j\}\in GF(q)^n$, that allow each client $c_i\in C$ to decode all the packets in its ``wants'' set $W(c_i)$.
\end{problm}

We assume, without loss of generality, that for each packet $p_i\in P$, there exists at least one client $c_j\in C$ such that $p_i$ belongs to the ``wants'' set $W(c_j)$ of $c_j$. We also assume that for each client $c_i\in C$ it holds that \mbox{$H(c_i)\cap W(c_i)=\emptyset$}.

\begin{observation}
Without loss of generality, we can assume that the
``wants'' set $W(c_i)$ of each client $c_i\in C$ contains exactly
one packet. Indeed, we can substitute each client $c_i\in C$ whose ``wants'' set includes more than one packet by multiple clients $C_i=\{c_i^1,c_i^2,\dots\}$ such that the ``has'' sets of all clients in $C_i$ are equivalent to that of $c_i$ and each client in $C_i$ requests one of the packets in $W(c_i)$. It is easy to verify that the resulting instance of Problem \emph{MIN-T-q} is equivalent to the original one.
\end{observation}

\section{Hardness results}\label{sec:hardness}

In this section we focus on the case in which the encoding is performed over $GF(2)$ and prove that Problem \emph{MIN-T-2}, which is a special case of Problem \emph{MIN-T-q} for $GF(2)$, is NP-complete.

\begin{theorem}\label{theor:hard}
 Problem \emph{MIN-T-2} is NP-complete.
\end{theorem}
\begin{proof}
It is easy to verify that the problem belongs  to $NP$. To prove that
the problem is NP-complete we show a reduction from the minimum
vertex cover problem. In this problem we are given a graph $G(V,E)$
and need to find a subset $\hat{V}$ of $V$, of minimum cardinality, such
that each edge $e\in E$ is incident to at least one of the nodes in
$\hat{V}$. We denote by $OPT^{VC}=|\hat{V}|$ the size of the optimal solution
for the vertex cover problem.

Given an instance $G(V,E)$ to the vertex  cover problem we build the
following instance for Problem \mbox{\emph{MIN-T-2}}.
The packet set $P$ includes a packet $p_v$ for any node in $V$  and
a packet $p_e$ for any edge in $E$.  We denote by $P_V=\{p_v\ |\ v\in
V\}$ the subset of packets in $P$ that correspond to nodes in $V$
and by $P_E=\{p_e\ |\ e\in E\}$ the subset of packets in $P$ that
correspond to edges in $E$.

For each edge $e(v,u)\in E$ we define two clients $c_e^1$ and $c_e^2$ such that:
\begin{itemize}
\item $H(c_e^1)=\{p_e\}$ and $W(c_e^1)=\{p_v,p_u\}$;
\item $H(c_e^2)=\{p_v,p_u\}$ and $W(c_e^2)=\{p_e\}$.
\end{itemize}

We denote by $OPT$ the size of the optimal solution for this instance of Problem \mbox{\emph{MIN-T-2}}, i.e., the minimum number of transmissions necessary to satisfy all clients. In the following two lemmas we prove that \mbox{$OPT=OPT^{VC}+|E|$}.
\begin{lemma}\label{lemm:1}
$OPT\leq OPT^{VC}+|E|$.
\end{lemma}
\begin{proof}
Let $\hat{V}\subseteq V$ be the optimal solution to  the vertex cover problem. Then, all clients can be satisfied by transmitting the following set of packets of size $OPT^{VC}+|E|$:
\begin{enumerate}
\item For each node $v\in \hat{V}$  we transmit the corresponding packet $p_v$;

\item For each edge $e(v,u)\in E$ we transmit the packet  $p_v+p_u+p_e$, where $p_v$, $p_u$, and $p_e$ are packets that correspond to nodes $v$, $u$, and edge $e$, respectively.
\end{enumerate}

It is easy to verify that the set $\Phi$ of corresponding encoding vectors is a feasible solution to Problem \mbox{\emph{MIN-T-2}}.  Since the total number of transmitted packets is $OPT^{VC}+|E|$ it follows that  $OPT\leq OPT^{VC}+|E|$.
\end{proof}

\begin{lemma}\label{lemm:2}
$OPT\geq OPT^{VC}+|E|$.
\end{lemma}
\begin{proof}
Consider an optimal solution $\Phi=\{g_1,\dots, g_{OPT}\}$ to Problem~\mbox{\emph{MIN-T-2}}, where $$g_i=(g_i^{v_1}, \dots,g_i^{v_{|V|}},
g_i^{e_1},\dots,g_i^{e_{|E|}})\in GF(2)^{|E|+|V|}.$$

With this solution, the packet transmitted at round $i$ is equal to

$$x_i=\sum_{v_j\in V} g_i^{v_j}\cdot p_{v_j}+\sum_{e_j\in E} g_i^{e_j}\cdot p_{e_j}.$$

We denote by
$\langle \Phi\rangle $ the linear subspace of dimension $OPT$ of
$GF(2)^{|V|+|E|}$ generated by the vectors in $\Phi$.

We show that there exist  two sets $\Phi_1$ and $\Phi_2$ of vectors in $\langle \Phi\rangle $ and a vertex cover $\hat{V}\subseteq V$  such that the following three conditions holds:
\begin{enumerate}
\item[(1)] For any edge $e\in E$,  there exists an encoding vector $g_i\in \Phi_1$ such that $g^e_i=1$, and $g^{e'}_i=0$ for any edge $e'\in E\setminus\{e\}$;
\item[(2)] For each $g_i\in \Phi_2$ it holds that $g^e_i=0$ for any edge $e\in E$;

\item[(3)] For each $v\in \hat{V}$ there exists an encoding vector $g_i\in \Phi_2$ such that $g^v_i=1$ and $g^{v'}_i=0$ for any node $v'\in \hat{V}\setminus \{v\}$.
\end{enumerate}

Note that all encoding vectors in $\Phi_1\cup \Phi_2$ are linearly independent, $|\Phi_1|=|E|$, and $|\Phi_2|=|\hat{V}|$.

First, we show how to construct the set $\Phi_1$. Let $e(v,u)$ be an edge in $E$ and let $c_e^1$ and $c_e^2$ be the two clients that correspond to $e$. We note that in order to satisfy $c_e^2$, $\langle \Phi\rangle $ must contain at least one vector $g_i$  for which it  holds $g_i^e=1$ and $g^{e'}_i=0$ for any
edge $e'\in E\setminus\{e\}$. Thus, we can form $\Phi_1$ by including, for each $e\in E$, the vector $g_i\in\langle \Phi\rangle $ that corresponds to
$e$.

Second, we show how to construct set $\Phi_2$ and the vertex cover $\hat{V}$. Again, let $e(v,u)$ be an edge in $E$ and let $c_e^1$ and $c_e^2$ be the two clients that correspond to $e$. Note that, in order to satisfy the client $c_e^1$, the set $\langle \Phi\rangle $ must contain a vector $g_i$ for which it holds that $g^{e'}_i=0$ for all $e'\in E$, $g^w_i=0$ for all $w\in V\setminus \{v,u\}$, and either $g^v_i$ or $g^u_i$ (or both) are non-zero. Let
$T$ be a set that contains such vectors for all $e\in E$. Let
\mbox{$l=\dim \langle T\rangle $}. It follows from linear algebra
that there exists an  $l\times (|V|+|E|)$ matrix $M$ over $GF(2)$
that satisfies the following conditions:
\begin{enumerate}
\item The rows of $M$ span $\langle T\rangle $;
\item  There are $l$ linearly independent columns in $M$ such that each column contains exactly one non-zero element.
\end{enumerate}

Indeed, we can first construct an $l\times (|V|+|E|)$ matrix $M'$ whose rows span $T$. Such matrix is of rank $l$, hence it contains at least $l$ non-zero columns which are linearly independent. The matrix $M$ can be constructed form $M'$ by performing Gaussian elimination. We denote by $\hat{V}$ the subset of $V$ that corresponds to $l$ linearly independent columns of $M$, each column contains exactly one non-zero element. Then, we set $\Phi_2$ to be the set of row vectors of $M$. Note that $\Phi_2$ has $l$ elements.

We proceed to show that $\hat{V}$ is a vertex cover in $G(V,E)$. We note that the structure of $M$ implies that for any non-zero vector $g_i$ in the row span of $M$, and, in turn, in $\langle T\rangle $ it must hold that $g_i^w=1$ for some $w\in \hat{V}$. For each edge $e(v,u)\in E$ let $g_i$ be the vector that correspond to $e$ in $T$. Recall $g_i$ has one or two non-zero components, which are either $g_i^v$ or $g_i^u$, or both. This implies that either $v$ or $u$, or both belong to $\hat{V}$.

We proved that there exist two sets $\Phi_1$ and $\Phi_2$ of independent  vectors in $\langle \Phi\rangle $ such that $|\Phi_1|=|E|$, and $|\Phi_2|\geq OPT^{VC}$. We conclude that
 $$OPT=\dim\langle \Phi\rangle \geq|\Phi_1|+|\Phi_2|\geq OPT^{VC}+|E|.$$
\end{proof}

From lemmas \ref{lemm:1} and \ref{lemm:2} it follows that $OPT= OPT^{VC}+|E|$. Thus,  a polynomial-time algorithm that solves Problem \emph{MIN-T-2} will solve the vertex cover problem as well, resulting in a contradiction.
\end{proof}

\section{Dependence on the field size}\label{sec:large}

In this section we consider a variant of  Problem~\mbox{\emph{MIN-T-q}}
which allows flexibility in choosing the underlying finite filed. $GF(q)$. Specifically, for each instance of the problem, we can choose the finite field that minimizes the required number of transmissions.

We denote by $OPT(q)$ the minimum required number of transmissions over $GF(q)$. We also denote by $OPT$ the minimum number of transmissions that can be achieved over any finite field.

We begin by observing that the minimum number of transmissions may depend on the size of the finite field $GF(q)$. For example, consider the problem described in Table \ref{tab:ex2}, where $P=\{p_1,p_2,p_3,p_4\}$, and for every client $c_i$, $H(c_i)=P\setminus W(c_i)$. We prove that in this problem $OPT(2)>OPT(3)$.

First, we show that $OPT(2)>2$. Suppose, by way of contradiction, that there is a solution  to this problem with two transmissions:
\begin{equation*}
\begin{array}{c}
x_1=g^1_1p_1+\dots+g_1^4p_4 \\
x_2=g_2^1p_1+\dots+g_2^4p_4
\end{array}
\end{equation*}
To satisfy all clients, the vectors $(g^1_1,g_2^1),\dots,(g_1^4,g_2^4)$ should be all distinct and different from $(0,0)$, which is not possible over $GF(2)$. Since the set of transmissions $\{p_1+p_3, p_2+p_3, p_4\}$ satisfies all clients, it follows  that $OPT(2)=3$. We note that $OPT$ is at least two, since $OPT\geq |W(c_i)|=2$. We also observe that over $GF(3)$ only two transmissions
$\{p_1+p_3+p_4, p_2+p_3+2p_4\}$ are sufficient, hence $OPT(3)=OPT=2$.

\begin{table}[!htb]
  \centering
  \begin{tabular}{|c|c|c|}
  \hline

 $C$ & $W(c_i)$& $H(c_i)$ \\
  \hline\hline
 $c_1$& $\{p_1,p_2\}$ & $\{p_3,p_4\}$ \\\hline
 $c_2$& $\{p_1,p_3\}$ & $\{p_2,p_4\}$ \\\hline
 $c_3$& $\{p_1,p_4\}$ & $\{p_2,p_3\}$\\\hline
  $c_4$& $\{p_2,p_3\}$ & $\{p_1,p_4\}$ \\\hline
 $c_5$& $\{p_2,p_4\}$ & $\{p_1,p_3\}$\\\hline
 $c_6$& $\{p_3,p_4\}$ & $\{p_1,p_2\}$\\\hline
 \end{tabular}
 \caption{
 }\label{tab:ex2}
\end{table}

The following lemma shows that $OPT(q)$ is not necessarily a monotonic function of $q$.

\begin{lemma}
There exists an instance of  Problem~\mbox{\emph{MIN-T-q}} for which it holds that $OPT(q)=3$ for fields with odd characteristic, such as $GF(3)$ and $OPT(q)>3$ for fields with even characteristic.
\end{lemma}
\noindent\hspace{2em}{\it Proof (sketch):}
Consider the problem instance described in Table \ref{tab:ex3}, where
$P=\{p_1,\dots,p_{7}\}$, and \mbox{$H(c_i)=P\setminus W(c_i)$}.

\begin{table}[!htb]
  \centering
  \begin{tabular}{|c|c|c|}
  \hline

 $c_i$ &  $W(c_i)$\\
  \hline\hline
 $c_1$& $\{p_1\}$  \\\hline
 $c_2$& $\{p_2\}$ \\\hline
  $c_3$& $\{p_3\}$ \\\hline
   $c_4$& $\{p_2,p_4\}$  \\\hline
 $c_5$& $\{p_3,p_5\}$ \\\hline
  $c_6$& $\{p_3,p_6\}$ \\\hline
  $c_7$& $\{p_4,p_7\}$ \\\hline
  $c_8$& $\{p_5,p_7\}$ \\\hline
  $c_9$& $\{p_6,p_7\}$ \\\hline
  $c_{10}$& $\{p_4,p_5,p_6\}$ \\\hline

 \end{tabular}
 \caption{
 }\label{tab:ex3}
\end{table}
For fields with odd characteristic,  the transmission sequence
$$\{p_1+p_4+p_5+p_7, p_2+p_4+p_6+p_7, p_3+p_5+p_6+p_7 \}$$ satisfies all clients, hence $OPT(q)=OPT=3$.

We observe that for fields with even characteristic ($q=2^k$) it holds that
$OPT(2^k)>3$. Indeed, for any solution \mbox{$\{g_1,g_2,g_3\}\in
GF(q)^3$} with three  transmissions, consider the matrix $T$ whose
row vectors are $g_1$, $g_2$, and $g_3$. To satisfy the demands of all the clients the vector matroid of $T$ should be isomorphic to the Fano matroid
\cite{OX93}. But, the Fano matroid is only representable over fields
with odd characteristics. Therefore, there are no solutions to above
problem with three transmissions over $GF(2^k)$.
\hspace*{\fill}~\QED\par\endtrivlist\unskip

The next lemma shows that deciding whether the optimal number of transmissions can be achieved for a given field $GF(q)$ is an NP-hard problem.

\begin{lemma}
For given a prime power $q$, it is an NP-hard problem to decide whether $OPT(q)=OPT$.
\end{lemma}
\noindent\hspace{2em}{\it Proof (sketch):} Similar to \cite{LL04},
we use a reduction from the problem of graph coloring. Given an
undirected graph $G(V,E)$, we construct the following instance to
the broadcast problem. For each node $v\in V$, the set $P$ includes
a packet $p_v$. For each edge $e(v,u)\in E$, the set $C$ includes a
client $c_e$ such that $W(c_e)=\{p_v,p_u\}$ and $H(c_e)=P\setminus
W(c_e)$. It is easy to verify that for this problem it holds that
$OPT=2$.

We show the problem can be solved with two transmissions over $GF(q)$ if and only if $G$ is $q+1$ colorable.
First, suppose that $G(V,E)$ can be colored with $q+1$ colors. Let $d(v)\in\{1,\dots,q+1\}$ be the
color of vertex $v$. As shown in \cite{LL04}, there exists $q+1$ pairwise independent vectors
$(z_1^1,z_2^1),\dots,(z_1^{q+1},z_2^{q+1})$ over $GF(q)$. For each node  $v\in V$ we set
 $(g_1^v,g_2^v)=(z_1^{d(v)},z_2^{d(v)})$. It is easy to verify that  the two encoding
 vectors $(g_1^v)_{v\in V}$ and $(g_2^v)_{v\in V}$
   constitute a feasible solution for the broadcast problem.

Second, suppose that there exists a solution $\Phi=\{(g_1^v)_{v\in
V}, (g_2^v)_{v\in V} \}$ for the broadcast problem with two
transmissions. We show that this implies that there exists a $q+1$
coloring of graph $G$. For each vertex $v\in V$, the vector
$(g_1^v,g_2^v)$ determines the coefficients for packet $p_v$ for the
first and
 the second transmissions  in $\Phi$. The set of such vectors can be partitioned into $q+1$ equivalence classes, such
 that any two linearly dependent vectors are placed into the same equivalence class. Next, for each equivalence class we
 assign one of the $q+1$ colors.  Next,  for each vertex $v\in V$ we assign the color that corresponds to the equivalence
  class of $(g_1^v,g_2^v)$. It is easy to verify that this will result in a valid coloring of $G$ that requires at most
  $q+1$ colors.
\hspace*{\fill}~\QED\par\endtrivlist\unskip

\section{Bounds on coding advantage}\label{sec:bound}

Given a one-hop transmission problem with $n$ packets $P=\{p_1,p_2,\dots,p_n\}$ and $m$ clients $C=\{c_1,\dots,c_m\}$, we define the coding gain $\Gamma$ as the ratio between the minimum number of transmissions without coding and the minimum number of transmissions with  coding, i.e.,
$$\Gamma=\frac{n}{OPT},$$
where $OPT$ is the minimum number of transmissions achievable over any finite field $GF(q)$.

Let $L=\max_{{c_i}\in C} |H(c_i)|$ and $\ell=\min_{c_i\in C}|H(c_i)|$. The following theorem establishes lower and upper bounds on $\Gamma$.

\begin{theorem}
The coding gain is bounded by
\begin{equation}\label{bounds}
   \frac{n}{n-\ell}\leq \Gamma \leq L+1
\end{equation}

\begin{proof}
We assume, without loss of generality, that $|W(c_i)|=1$
for each  client $c_i\in C$. Let $GF(q)$ be the field that requires $OPT$ transmissions. Consider an optimum solution $\Phi$ that includes $OPT$ encoding vectors $g_1,\dots,g_{OPT}$.

Let $e_j\in GF(q)^n$, $1\leq j\leq n$, be the unit vector whose
components are all zeros except for the $j$-th one which is 1. For
$1\leq i\leq n$, we define $w_i= e_j$ if client $c_i$ wants packet
$p_j$. Also, we define
$$\hat{H}(c_i)=\{e_j; p_j\in H(c_i)\}.$$

To guaranty that each client $c_i$ is able to decode the
packet $h_i$ in its ``wants'' list, there must be a vector $y_i\in \langle \Phi\rangle $ such that $w_i=y_i+h_i$,  $h_i\in \langle\hat{H}(c_i)\rangle$, where $\langle \Phi\rangle $ and $\langle\hat{H}(c_i)\rangle$ are the  linear subspaces generated by the vectors in $\Phi$ and $\hat{H}(c_i)$, respectively. We note that the Hamming weight of $y_i$ is upper bounded by $L+1$.

Let $Y=\{y_i\ | \ c_i\in C \}$. By the optimality of the
solution the dimension of the linear subspace $\langle Y\rangle$ generated by $Y$ is equal to that of $\langle \Phi\rangle $. Let $B$ be the $OPT \times n$ matrix whose row vectors belong to $Y$ and form the basis of $Y$.
 We note that $B$ must satisfy the following two conditions:
\begin{enumerate}
  \item Each row of $B$ contains at most $L+1$ non-zero elements.
  \item $B$ does not contain the all-zero column vector.
\end{enumerate}
The first condition follows from the upper bound on the Hamming
weights of the vectors in $Y$. The second condition follows from the
observation that for every packet $p_i$ at the source, there is at
least one client that wants it. These two conditions imply that $OPT \geq \frac{n}{L+1}$.

We proceed with the lower bound. Given an instance $I_1$ of Problem \emph{MIN-T-q}, we form another instance $I_2$
with where all the ``has'' sets have order $\ell$, and where
$W(c_i)=P\setminus H(c_i)$. Instance $I_2$ is formed by deleting arbitrary elements from the ``has'' sets of $I_1$ and expanding the ``wants'' sets of its elements. Note that any valid solution for instance $I_2$ is also a valid solution for instance $I_1$.

For a field $GF(q)$ of large enough size (larger than the number of
clients), we can always find a subspace $S$ of dimension $n-\ell$ in
$GF(q)^n$ that is simultaneously orthogonal to all the subspaces
$<\hat{H} (c_i)>$ corresponding to  $I_2$ (Theorem 1 in \cite{CAYE01}).
Any basis of $S$ will constitute a solution for $I_2$, and, in turn, for
$I_1$, which requires $n-\ell$ transmissions. Thus, the lower bound follows.
\end{proof}

\end{theorem}

\section{Heuristic Approach and Numerical Results}\label{sec:numerical}

\subsection{Heuristic Approach}\label{sec:heuristic}

In Section \ref{sec:hardness}, we proved that Problem~\emph{MIN-T-2} is NP-complete, hence finding an optimal solution for large instances of the problem can be impractical. In this section, we present a heuristic approach to solve  this problem. Our heuristic solution employs \emph{memoryless decoding}, i.e., each client uses exactly one of the transmitted packets to decode one of the packets in its ``wants'' list and never uses a linear combination of the transmitted packets. While memoryless decoding, in general, results in a suboptimal solution, our numerical results, presented below, show that in many cases the number of required packets is close to the optimum.  We observe that the problem of finding the minimum number of transmissions with memoryless decoding is equivalent to the problem of finding the minimum chromatic number of an undirected graph.

Specifically, consider an instance $I$ problem of Problem
\emph{MIN-T-q}, in which the ``wants'' set of each client is of
cardinality one. Then, we construct an instance $G(V,E)$ to graph
coloring problem through the following procedure:

\begin{itemize}
\item For each client $c_i\in C$ there is a corresponding vertex $v_{c_i}$  in $V$
\item Each two vertices $v_{c_i}$ and $v_{c_j}$ are connected by an edge if one of the following holds:
    \begin{itemize}
        \item Clients $c_i$ and $c_j$ have identical ``wants'' sets;

        \item $W(c_i)\subseteq H(c_j)$ and $W(c_j)\subseteq H(c_i)$.

    \end{itemize}
\end{itemize}

Let $\hat{V}\subseteq V$ be a clique in $G(V,E)$, i.e., each two vertices
of $V$ are connected by an edge in $G$. Note that all clients that
correspond to nodes in $\hat{V}$ can be satisfied by one transmission,
which includes a linear combination of all packets in their
``wants'' sets. Thus, the minimum number of transmissions with
memoryless decoding can be found by solving a \emph{clique partition}
problem \cite{GJ79}, i.e., partition of $V$ into disjoint subsets
$V_1,V_2,\dots, V_k$, such that for $1\leq i\leq k$, the subgraph of
$G$ induced by $V_i$ is a complete graph. This problem, in turn,
corresponds to the minimum graph coloring problem of the
complimentary graph. The latter problem is a well-studied problem
with a wealth of heuristic solutions developed in the recent years.

\begin{figure}[t]
\begin{center}
\epsfig{file=fig2.eps, scale=0.35}
 \caption{Histogram of coding gain for 7 clients with optimal decoding \label{fig:op:coding2}}%
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\epsfig{file=fig4.eps, scale=0.35}
 \caption{Histogram of coding gain for 5 clients using memoryless decoding \label{fig:op:coding4}}%
\end{center}
\end{figure}

\subsection{Numerical results}

We performed several numerical experiments  in order to evaluate the
coding gain as well as the performance of the heuristic solution in
random settings. In all of our experiments described below, the
``wants'' set of each client is of cardinality one, and the number
of clients is equal to the number of packets.

In the first experiment, we evaluated the coding  gain of a
single-hop wireless system with seven clients. Specifically, we
generated 50 instances of Problem \emph{MIN-T-q}, in each setting
the set ``has'' of each client is randomly selected. The results of
the experiment are shown in Figure \ref{fig:op:coding2}. The results
show that in the majority of the experiments, there is a significant
coding gain (more than 1.75).

The second experiment is similar to  the first one, but the clients
only employ memoryless decoding.  The results of the experiment are
shown in Figure \ref{fig:op:coding4}. The results show that a
significant coding gain (up to 2.5) can be achieved, while in the
majority of the cases, the coding gain is at least 1.7.

In the third experiment, we studied  the dependence of average
coding gain on the cardinality of the ``has'' sets. In particular,
we generated a problem instance in which the cardinality of the
``has'' set is equal for all clients, while the content of the
``has'' set was randomly selected. Figure \ref{fig:op:coding3} shows
the average coding gains of the system with seven clients using
optimal decoding as a function of cardinality of the "has" sets,
while Figure \ref{fig:op:coding5} shows the comparison of average
coding gains as a function of cardinality of the "has" sets, for
three techniques i.e., optimal decoding, memoryless decoding and
heuristic approach.The results show that the average coding gain
increases with the size of the ``has'' sets, which confirms the
intuition that coding is more beneficial if the clients have more
packets in their ``has'' sets.

\begin{figure}[t]
\begin{center}
\epsfig{file=fig3.eps, scale=0.35}
 \caption{Average Coding gain as a function of the cardinality of the ``has'' set.\label{fig:op:coding3}}%
\end{center}
\end{figure}

\begin{figure}[t]
\begin{center}
\epsfig{file=fig5.eps, scale=0.4}
 \caption{Average Coding gain as a function of the cardinality of the ``has'' set using different techniques: (1) optimal decoding; (2) memoryless decoding; (3) heuristic approach.\label{fig:op:coding5}}%
\end{center}
\end{figure}

Finally, we evaluated the coding gain  that can be obtained through
the heuristic approach presented in Section \ref{sec:heuristic}. The
results of this experiment are depicted in Figure
\ref{fig:op:coding7}. The results show that the proposed heuristic
approach allows to obtain a significant reduction in the number of
transmitted packets.

\begin{figure}[t]
\begin{center}
\epsfig{file=fig7.eps, scale=0.35}
 \caption{Histogram of coding gain for 20 clients using heuristic approach\label{fig:op:coding7}}%
\end{center}
\end{figure}

\section{Conclusion}\label{sec:conclusion}

The paper focuses on minimizing the  number of transmissions
necessary for satisfying all clients in single-hop wireless settings.
We employ the technique of network coding which allows to
take advantage of the packets that were overheard from  prior
transmissions.

Our paper makes the following contributions.  First, we proved that
the problem of finding the minimum number of transmissions is
NP-complete over the binary field. Second, we analyzed an extended
version of the problem in which the encoding can be performed over a
larger finite field. Furthermore, we established lower and upper
bounds on the value of the  coding gain. Next, we presented a
heuristic solution based on graph coloring. Finally, we conducted a simulation study that evaluates the coding gains in practical settings.

The considered problem presents significant challenges and provides a fertile ground for future research. In particular, we would like to prove the NP-hardness and inapproximability for finite fields of larger size as well as for non-linear network codes.

\bibliographystyle{unsrt}


text:
\section{Introduction}
Dynamic random access memory errors are omnipresent failure types in data centres. A memory error is an event which results in the wrong reading of the logical state of one or multiple bits from how they were last written. An error in a single bit corrupts the stored information and affects the ongoing computation, sometimes leading to system crashes. The root causes of DIMM errors are diverse, ranging from hardware corruption of the memory arrays, up to bit-flips due to electromagnetic influence (e.g., cosmic ray strikes)~\cite{errortypes}. As a preventive strategy for DIMM reliability, the manufacturers integrate different error correcting codes (ECC) onto the chip for single (e.g., parity checking)~\cite{SEC} or multi-bit error correction (e.g., ChipKill~\cite{ChipKill}). While useful in a limited set of circumstances (e.g., SEC corrects a single bit), once the errors exceed the assumptions on the ECC algorithms (e.g., the error occurs in multiple bits), the memory failure externalises and frequently results in a system crash. Therefore, relying on error correction codes as a preventive strategy is insufficient for reliable DIMM behaviour. To reduce the effect of the DIMM failures alternative strategies are needed.

A possible strategy to amortize the effect of DIMM failures is to predict when the memory will fail. By a sufficiently large prediction interval, the correct prediction enables the triggering of preventive measures (e.g., server migration). Therefore, the failure will not be externalised. This makes memory failure prediction an important task for system reliability. The key requirement for memory prediction is the availability of data that encapsulates the properties of a degraded DIMM. Two common data sources are used, i.e., 1) hardware error logs and 2) system-level metrics~\cite{facebookmemoryfailureprediction}. Hardware error logs record the correctable errors generated from the DIMM's ECC chips. These errors are referred to as \textit{correctable errors}. Different studies show that the accumulated repetition of CE on nearby memory locations is correlated with memory failures~\cite{stefanovici2012cosmic,facebookmemoryfailureprediction}. Therefore, DIMM characterization through CEs is useful to model DIMM degradation. In contrast, memory-related system-level metrics are time series points showing the memory utilization (e.g., byte read/write). Although system-level metrics are reported as useful~\cite{memoryfailuresystemmetrics,bogatinovskiMipro2019}, the CEs are generally recognized to better capture the memory degradation and are more frequently used for failure prediction~\cite{facebookmemoryfailureprediction}.

\begin{figure*}[!ht]
\centering
\subfloat{\includegraphics[width=\columnwidth]{figures/time_intervals.pdf}%
\label{timeintervals}}
\hfil
\subfloat{\includegraphics[width=\columnwidth]{figures/pipeline.pdf}%
\label{pipeline}}
\caption{(A) The Memory Failure Prediction Problem; (B) Model learning pipeline;}
\end{figure*}

In this paper, we revisit the problem of memory failure prediction by using CEs. Owning to practical requirements (e.g., unavailable infrastructure for long-term storage of the overall CE log history), existing approaches introduce an observation window with a fixed time duration as part of the algorithm design. Studies typically consider a fixed window of, e.g., one or two weeks~\cite{memoryfailuresystemmetrics, IBM2018, paper3}. However, as the utilization of the servers has a stochastic component, it is often the case that the servers will be accessed time apart at distant intervals. Furthermore, as memories on a single server do not always work with full occupancy, the access of the faulty memory parts (and CE generation thereof) is time-distributed as well. Therefore, by using fixed observation windows, one may expect that important details from CE history may be missed. Based on this intuition, we examine the impact of considering the overall CEs DIMM history instead of using an observation window of fixed size. We used our observations to propose a set of novel features that can be incrementally calculated while preserving the long-term temporal CEs dependencies of a degraded DIMM not needing to store all the data. By pairing the calculated features with machine learning methods, we learn a predictive model that can anticipate memory failures three hours in advance, outperforming operational practices. Our evaluation is performed on \textbf{real-world memory failure data} collected from the server fleet of a large cloud provider, justifying the validity and practicality of our approach.

\section{Background}~\label{background}
\vspace{-6mm}
\subsection{System Memory Organization}
The memory system of a server has a hierarchical organization. A single DIMM (dual in-line memory module) is a computer working memory type. The DIMM stores each data bit in a separate memory cell and is used by the CPU for  different operations (e.g., \textit{add}, \textit{write}). The DIMM is connected with the \textit{integrated memory controller} (IMC) within the CPU via a \textit{memory channel}. To increase the DIMM performance, a DIMM is usually composed of multiple integrated \textit{chips} that are organized in \textit{ranks} (set of connected chips). Each chip is further composed from arrays of transistors identifiable by \textit{rows} and \textit{columns}. The intersection between a row and column is called \textit{cell}. Each cell stores one bit. The DIMM has also additional circuitry that enables effective memory operations, and potentially ECC mechanisms for CE event generation. The CE events can be read out from dedicated CPU register set groups (e.g., the Machine Check Exception (MCE) register set for Intel x86) generating the CE logs. Opposed to the properties of the software logs, like semantics~\cite{bogatinovskiSCC2022}, or sequences~\cite{bogatinovskiCCGRID2022}, the CE logs contain information about the place in the memory where the CE occurred (e.g., specific cell, bank, row, etc).

\subsection{Problem Formulation}
Let $D_i$ is a DIMM that reported a CE log, denoted by $l(t_j)$ at a certain point in time $t_j$, and let $w$ and $m$ denote an observation window length and a prediction time length interval, accordingly. The goal of memory failure prediction is to map $F: \phi(l_{(t_0-w:t_0)}) \mapsto B_m$, where $t_0$ is the current observation moment and $\phi(l_{(t_0-w:t_0)})$ is a representation function $\phi: L_i \mapsto \mathcal{R}^d$ that maps the set of observed correctable errors $L_i$ for DIMM $D_i$ from the time period ($t_0-w$, $t_0$) into a certain representation space $\mathcal{R}^d$, where $d$ is representation size. The set $B_m \in \{0, 1\}$ denotes if the DIMM $i$ will fail in $m$ time units $(1)$ or not $(0)$.

\begin{figure*}[!t]
\centering
\includegraphics[width=0.7\textwidth]{figures/feature_taxonomy.pdf}
\caption{Feature Taxonomy; Based on the hierarchical DIMM organization.}
\label{featuretaxonomy}
\end{figure*}

\textbf{Motivation}. In previous works~\cite{memoryfailuresystemmetrics, IBM2018, paper3}, the observation window $w$ used for feature extraction is usually fixed, e.g., two weeks. Figure~\ref{timeintervals} (A) illustrates this with the time interval $(t_0-w:t_0)$. Intuitively, as the utilization of the servers has a stochastic component, it is often the case that the servers will be accessed at different time intervals. Furthermore, different address locations of the DIMMs on the same server will be accessed at different time intervals. If certain cells are faulty, the sparsity in memory address accesses will lead to non-uniform temporal CEs distribution. By using fixed observation windows $(t_0-w:t_0)$, one may expect to miss details relevant for predicting memory failures. We found that there exist properties of failures that propagate through time through CEs that often surpass the observation window $(t_0-w:t_0)$ (e.g., the number of unique banks that generate CEs). Thereby, we consider structuring the CE reporting history into two disjoint time intervals, i.e., 1) $(-\inf:t_0-w)$ (Figure~\ref{timeintervals} (A) highlighted in grey) and 2) $(t_0-w:t_0)$ (the white rectangle). By proposing novel incrementally calculable features that among others characterize the difference between the disjoint intervals (e.g., the number of new banks generating correctable errors), we can preserve important information for upcoming failures. Motivated by our intuition, the focal point of this paper is to investigate the potential strengths of this view of the memory failure prediction problem.

\section{Predicting Memory Failures with CEs}~\label{methodology}
In this section, we describe the procedure we implemented to learn a memory failure prediction model. It is a standard machine learning pipeline composed of data preprocessing, feature extraction and model learning. Once the model is learned it is used for online prediction. Figure~\ref{pipeline} (B) shows the pipeline. The input data comes in form of CE logs. They contain information for the DIMM name the CE appeared in, the timestamp, and the CE information (e.g., row, columns, banks, and similar). The log information proceeds towards the data preprocessing where CEs with incomplete log information are filtered. The filtered CEs proceed toward the feature extraction part. The latter implements a set of functions that characterize the degradation state of the DIMM. Once the features are extracted the CE represented with the feature vector is given as input for the machine learning model. In the following, we discuss each of the three parts in more detail.

\subsection{CEs Preprocessing and Feature Extraction}
The recorded CEs contain noise. For example, not all CE logs have information for the columns, rows or banks. Additionally, certain types of correctable errors, such as "uce.read" logs appear rarely. Therefore, the CEs preprocessing removes CEs of this kind (e.g., that are of type "uce.read", or have insufficient CE information). The filtered CEs proceeded toward the feature extraction part.

The feature extraction part implements functions that characterize the degradation state of the DIMM. In total, we implemented 189 features calculable incrementally. To better describe them, we organize them in a taxonomy following DIMM properties and the failures are reflected. Figure~\ref{featuretaxonomy} gives the feature taxonomy. On the first level, there are five feature groups: \textit{general DIMM}, \textit{bank}, \textit{column}, \textit{row} and \textit{cell-level} features. The \textit{general DIMM} features characterize the overall CE statistics for the DIMM, irrespective of its components. This category includes features such as the \textit{frequency of errors}, or \textit{frequency} of the \textit{error types} similar as in related work~\cite{facebookmemoryfailureprediction}. We also proposed to use the relative change of the error frequency and error types between the two adjoint time intervals. The \textit{bank-level} features characterize the overall statistics of the CE frequency on a bank level, such as the number of banks that reported CEs, and the number of new banks that reported CEs between the observation window and the CEs before that. The focus of this category of feature is to describe the evolution of the failure on a bank level.

The column, row and cell-level features characterized the DIMM banks on the memory array level. They are different in the way how they group the CEs alongside the memory array (e.g., by row, column or cell). For all the three groups there are three subgroups, i.e., \textit{neighbourhood}, \textit{repeating} and \textit{bank-row}(/column/cell) features. The \textit{repeating} group refers to the repetition of a CE from a single cell address or group of addresses sharing the same row/column. Intuitively, if one transistor is worn-off, any subsequent accesses to that memory will generate CEs. Therefore, repeating the same errors can indicate hard failures. The \textit{neighbourhood} features are similar to the repeating ones, however, they further exploit the concept of the DIMM \textit{bursting} mechanism. This concept enables reading out multiple adjacent memory addresses to speed up performance. Therefore, if an error occurs in the neighbourhood, it is likely that there are issues with the memory. The third group considers row/column/cell properties for the arrays irrespective of the bank and the chip. This group is closely related to the procedure of how the logical reading/writing of a whole word from multiple banks is conducted.

\begin{table*}[!h]
\caption{Experimental Results}
\label{results}
\resizebox{\textwidth}{!}
\begin{tabular}{|c|cc|ccc|ccc|ccc|}
\hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Feature\\ Calculation\\ Strategy\end{tabular}} & \multicolumn{2}{c|}{Method}                                                                                & \multicolumn{3}{c|}{RF}                                                                                & \multicolumn{3}{c|}{XGB}                                                                                & \multicolumn{3}{c|}{\begin{tabular}[c]{@{}c@{}}Operational\\ Practicies\end{tabular}}                                                                          \\ \cline{2-12}
                                                                                & \multicolumn{1}{c|}{\begin{tabular}[c]{@{}c@{}}w\\ {[}h{]}\end{tabular}} & \begin{tabular}[c]{@{}c@{}}\# Normal\\ DIMMs\end{tabular} & \multicolumn{1}{c|}{Precision} & \multicolumn{1}{c|}{Recall}    & \begin{tabular}[c]{@{}c@{}}Error Rate\\ (Normal Test)\end{tabular} & \multicolumn{1}{c|}{Precision} & \multicolumn{1}{c|}{Recall}    & \begin{tabular}[c]{@{}c@{}}Error Rate\\ (Normal Test)\end{tabular} & \multicolumn{1}{c|}{Precision}              & \multicolumn{1}{c|}{Recall}                 & \begin{tabular}[c]{@{}c@{}}Error Rate\\ (Normal Test)\end{tabular} \\ \hline
\multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Overall \\ CE\\ Evolution\end{tabular}}               & \multicolumn{1}{c|}{\multirow{2}{*}{3h}}                                 & 2500                                                      & \multicolumn{1}{c|}{0.24±0.01} & \multicolumn{1}{c|}{0.58±0.01} & 0.27±0.01                                                          & \multicolumn{1}{c|}{0.58±0.01} & \multicolumn{1}{c|}{0.38±0.01} & 0.043±0.0                                                          & \multicolumn{1}{c|}{\multirow{2}{*}{0.279}} & \multicolumn{1}{c|}{\multirow{2}{*}{0.056}} & \multirow{2}{*}{0.027}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.16±0.01} & \multicolumn{1}{c|}{0.49±0.01} & 0.20±0.01                                                          & \multicolumn{1}{c|}{0.48±0.01} & \multicolumn{1}{c|}{0.38±0.01} & 0.033±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \cline{2-12}
                                                                                & \multicolumn{1}{c|}{\multirow{2}{*}{168h}}                               & 2500                                                      & \multicolumn{1}{c|}{0.36±0.01} & \multicolumn{1}{c|}{0.55±0.01} & 0.15±0.01                                                          & \multicolumn{1}{c|}{0.60±0.01} & \multicolumn{1}{c|}{0.42±0.01} & 0.037±0.0                                                          & \multicolumn{1}{c|}{\multirow{2}{*}{0.109}} & \multicolumn{1}{c|}{\multirow{2}{*}{0.015}} & \multirow{2}{*}{0.006}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.30±0.01} & \multicolumn{1}{c|}{0.46±0.01} & 0.09±0.01                                                          & \multicolumn{1}{c|}{0.47±0.01} & \multicolumn{1}{c|}{0.44±0.01} & 0.037±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \cline{2-12}
                                                                                & \multicolumn{1}{c|}{\multirow{2}{*}{336h}}                               & 2500                                                      & \multicolumn{1}{c|}{0.35±0.01} & \multicolumn{1}{c|}{0.54±0.01} & 0.14±0.01                                                          & \multicolumn{1}{c|}{0.61±0.01} & \multicolumn{1}{c|}{0.45±0.01} & 0.046±0.0                                                          & \multicolumn{1}{c|}{\multirow{2}{*}{0.31}}  & \multicolumn{1}{c|}{\multirow{2}{*}{0.06}}  & \multirow{2}{*}{0.011}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.29±0.01} & \multicolumn{1}{c|}{0.45±0.01} & 0.07±0.01                                                          & \multicolumn{1}{c|}{0.48±0.01} & \multicolumn{1}{c|}{0.41±0.01} & 0.034±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \hline
\multirow{6}{*}{\begin{tabular}[c]{@{}c@{}}Fixed\\ Window \\ Size\\ $[w]$\end{tabular}}              & \multicolumn{1}{c|}{\multirow{2}{*}{3h}}                                 & 2500                                                      & \multicolumn{1}{c|}{0.29±0.01} & \multicolumn{1}{c|}{0.48±0.01} & 0.17±0.01                                                          & \multicolumn{1}{c|}{0.37±0.01} & \multicolumn{1}{c|}{0.21±0.01} & 0.056±0.0                                                          & \multicolumn{1}{c|}{\multirow{2}{*}{0.23}}  & \multicolumn{1}{c|}{\multirow{2}{*}{0.023}} & \multirow{2}{*}{0.017}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.20±0.01} & \multicolumn{1}{c|}{0.38±0.01} & 0.12±0.01                                                          & \multicolumn{1}{c|}{0.24±0.01} & \multicolumn{1}{c|}{0.23±0.01} & 0.055±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \cline{2-12}
                                                                                & \multicolumn{1}{c|}{\multirow{2}{*}{168h}}                               & 2500                                                      & \multicolumn{1}{c|}{0.31±0.01} & \multicolumn{1}{c|}{0.57±0.01} & 0.204±0.01                                                         & \multicolumn{1}{c|}{0.54±0.01} & \multicolumn{1}{c|}{0.38±0.01} & 0.05±0.0                                                           & \multicolumn{1}{c|}{\multirow{2}{*}{0.16}}  & \multicolumn{1}{c|}{\multirow{2}{*}{0.06}}  & \multirow{2}{*}{0.025}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.24±0.01} & \multicolumn{1}{c|}{0.52±0.01} & 0.14±0.01                                                          & \multicolumn{1}{c|}{0.42±0.01} & \multicolumn{1}{c|}{0.43±0.01} & 0.047±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \cline{2-12}
                                                                                & \multicolumn{1}{c|}{\multirow{2}{*}{336h}}                               & 2500                                                      & \multicolumn{1}{c|}{0.31±0.01} & \multicolumn{1}{c|}{0.58±0.01} & 0.19±0.01                                                          & \multicolumn{1}{c|}{0.54±0.01} & \multicolumn{1}{c|}{0.35±0.01} & 0.051±0.0                                                          & \multicolumn{1}{c|}{\multirow{2}{*}{0.29}}  & \multicolumn{1}{c|}{\multirow{2}{*}{0.06}}  & \multirow{2}{*}{0.018}                                             \\ \cline{3-9}
                                                                                & \multicolumn{1}{c|}{}                                                    & 5000                                                      & \multicolumn{1}{c|}{0.22±0.02} & \multicolumn{1}{c|}{0.43±0.02} & 0.11±0.01                                                          & \multicolumn{1}{c|}{0.44±0.01} & \multicolumn{1}{c|}{0.37±0.01} & 0.036±0.0                                                          & \multicolumn{1}{c|}{}                       & \multicolumn{1}{c|}{}                       &                                                                    \\ \hline
\end{tabular}
}
\end{table*}

\subsection{Memory Failure Prediction}
As machine learning methods we consider two popular classification methods for tabular data, i.e., Random Forest~\cite{RF} and XGBoost~\cite{XGBoost}. These methods are often shown to achieve high performance on a plethora of tasks concerning tabular input representation~\cite{compariosn2017}.

To learn the models, one requires labels for the individual CEs. As it is not known in advance the exact moment when the DIMM is in a degraded state, to label the data, we used a heuristic (similar as in related works~\cite{stefanovici2012cosmic}). We observed that the CEs for the failure DIMMs are usually generated in bursts that are time-delayed. In the cases when there are prior CE generated from a single DIMM, there is a large time between the adjacent bursts. To label the CEs representing the degraded DIMM state, we first find the largest existing gap between two adjacent CEs. This creates two sets of CE. We label all the CEs from the first set with 0. We consider the CEs from the second set to denote a degraded state and label them with 1. The correctable errors from new DIMMs in the current observation interval are given chronologically to the model. If the model predicts that at least one CE is degraded, the DIMM is predicted to fail. When learning the model, the CEs in the $m$ time units prior to the failure are removed. The final output of the system are the DIMM IDs, predicted to fail.

\section{Evaluation}~\label{evaluation}
\vspace{-6mm}
\subsection{Experimental Setup}
To evaluate our methodology, we collected CE data with memory failures over six months (November-March 2020/21) from part of the server fleet of a large cloud provider. There were 12000 DIMMs with at least one CE. Around 3\% of the DIMMs failed. As the number of failed DIMMs composes 3\% of all the DIMMs, the problem of memory failure prediction indicates imbalanced classification. We adopted subsampling of the majority class (normal DIMMs), as a strategy to deal with this problem. To construct the training and test data, we split the normal DIMMs into two sets. We sampled 5000 normal DIMMs for cross-validation and used the remaining ones as a normal test set. We repeat the sampling five times and report the average results for the evaluation criteria. The validation normal DIMMs are paired with the failure DIMMs and are used to learn the model and access its performance. To access model performance we used 10 Fold CV. Precision and recall are common evaluation criteria for memory failure prediction~\cite{IBM2018}, and we adopt them. We set the value for $m$ to 3 hours, as it is sufficient time for server content migration.

For the window interval used to extract features, we used $w=\{3, 168, 332\}$ hours. The models were learned with the implementations of the sklearn-learn and xgboost Python libraries. Another baseline we consider is the thresholding of domain features (e.g., CE rate, or the number of uncorrectable errors) as frequent operational practices. Specifically, we experiment with all possible values for the CE rate and reported the best values for precision and recall.

\subsection{Results and Discussion}
Table~\ref{results} summarizes the results. When considering the overall CE evolution, one can observe that irrespective of the method or the experiment parameters, the results for both precision and recall are generally improved in comparison to those not considering it. For example, for a time window of 14 days and normal DIMMs 5000, for XGBoost the precision is improved for 9\% $(\frac{(0.48-0.44)}{0.44})$, while the recall for 11\% $(\frac{(0.41-0.37)}{0.37})$. Similar improvements of 32\% on precision and 5\% on recall are observed for RF for 14 days and normal DIMMs 5000. The average improvement in precision and recall for XGBoost is 33.6\% and 33\% accordingly, while for RF it is 8.1\% on precision and 5\% on recall.

As seen by the results, including the long-term dependencies is particularly important for improving precision. This is likely related to the bursting nature of the CEs in anticipation of a failure. The long-term CE preservation enables the inclusion of non-related CEs from the normal DIMM behaviour that later failed. This effectively introduces information about the differences between the CEs of DIMMs that will fail in the future, guiding the model to better learn the normal DIMM states. This ultimately reduces the false positives and increases the precision. Another important point is that the model predictions outperform the manual operational practices. This is to the capabilities of the methods to combine complex information from multiple features.

Finally, by close inspection of the features' importance, we noted that the most important features are the ones characterizing the transition between the two disjoint time intervals formed with the parameter $w$ (i.e., ($-\inf$, $t_0-w$) and ($t_0-w$, $t_0$)). This observation encourages further investigation into finding new features that better utilize the overall information.

\section{Conclusion}~\label{conclusion}
In this paper, we revisited the problem of memory failure prediction with CEs. We found that considering the whole CEs-generation history is more indicative of failures, as compared to considering a fixed observation interval. We proposed a set of incrementally calculable features that preserve long-term CEs dependencies. In the evaluation of memory failures from the server fleet of a large cloud provider, we showed an average improvement of 21\% on precision and 19\% on recall, justifying the validity of our approach. This paper invites further research on how to better utilize the overall CEs data, to improve the performance on memory failure prediction.
\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv