Coded Computation Against Straggling Decoders
for Network Function Virtualization
Malihe Aliasgari∗ , Jörg Kliewer ∗ , and Osvaldo Simeone†

arXiv:1709.01031v1 [] 4 Sep 2017

∗

Helen and John C. Hartmann Department of Electrical and Computer Engineering
New Jersey Institute of Technology, Newark, New Jersey 07102-1982
{ma839, jkliewer}@njit.edu
† Department of Informatics, King’s College London, London, UK
osvaldo.simeone@kcl.ac.uk

Abstract—The uplink of a cloud radio access network (C-RAN)
architecture is studied in which decoding at the cloud takes place
via Network Function Virtualization (NFV) on commercial offthe-shelf (COTS) servers. In order to mitigate the impact of
straggling decoders in the cloud computing platform, a novel
coding strategy is proposed, whereby the cloud re-encodes the
received frames via a linear code before distributing them to
the decoding processors. Upper bounds on the resulting Frame
Error Rate (FER) as a function of the decoding latency are
derived by assuming a binary symmetric channel for uplink
communications. The bounds leverage large deviation results for
correlated variables, and depend on the properties of both the
uplink linear channel code adopted at the user and the NFV
linear code applied at the cloud. Numerical examples demonstrate
that the bounds are useful tools for code design, and that coding
is instrumental in obtaining a desirable trade-off between FER
and decoding latency.
Index Terms—Coded computation, network function virtualization, C-RAN, large deviation.

I. I NTRODUCTION
Promoted by the European Telecommunications Standards
Institute (ETSI), Network Function Virtualization (NFV) has
become a cornerstone of the envisaged architecture of 5G systems [1]. NFV leverages virtualization technologies in order to
implement network functionalities on commercial off-the-shelf
(COTS) programmable hardware, such as general purpose
servers, potentially reducing both capital and operating costs.
An important challenge in the deployment of NFV is ensuring
carrier grade performance while relying on COTS components.
Such components may be subject to temporary unavailability due to malfunctioning, and are generally characterized
by randomness in their execution runtimes [2]. The typical
solution to these problems involves replicating the Virtual
Machines (VMs) that execute given network functions on
multiple processors, e.g., cores or servers [2]–[5].
The problem of straggling processors, that is, of processors
lagging behind in the execution of a certain orchestrated
function, has been well studied in the context of distributed
computing [6]. Recently, it has been pointed out that, for the
important case of linear functions, it is possible to improve
This work was supported in part by U.S. NSF grants CNS-1526547 and
CCF-1525629. O. Simeone has also received funding from the European
Research Council (ERC) under the European Unions Horizon 2020 research
and innovation programme (grant agreement No 725731).

over repetition strategies in terms of the trade-off between
performance and latency by carrying out linear precoding of
the data prior to processing [7]–[12]. The key idea is that,
by employing suitable linear (erasure) block codes operating
over fractions of size 1/K of the original data, a function may
be completed as soon as a number of K or more processors,
depending on the minimum distance of the code, has finalized
its operation, irrespective of their identity.
In this paper we consider the function of decoding in
the uplink of a Cloud Radio Access Network (C-RAN). As
shown in Fig. 1, in a C-RAN system decoding takes place
at the cloud. Keeping the decoding latency to a minimum is
a major challenge in the implementation of C-RAN owing to
timing constraints from the MAC layer retransmission protocol
[13]. Reference [13] argued that exploiting parallelism across
multiple cores in the cloud can reduce the overall decoding
latency. However, parallel processing alone does not address
the discussed unreliability of COTS hardware. In [14], it was
hence proposed to perform linear precoding of the received
frames at the cloud in order to mitigate the impact of unreliable
decoding servers.
In this paper we extend the treatment of linear coding
against unreliable processors in the C-RAN uplink in the
following ways. First, while reference [14] considered only
a toy example with three processors, here we generalize the
approach to any number of processors. Second, unlike the
simple binary availability model of [14], in which a processor
is either on or off, here we adopt a set-up in which the
computing runtime of each processor is random and generally
dependent on the computational load as in, e.g., [7], [8]. Third,
while [14] relied solely on numerical results, here we develop
two analytical upper bounds on the FER as a function of the
decoding delay. The bounds leverage large deviation results
for correlated variables [15], and depend on the properties of
both the uplink linear channel code adopted at the user and the
NFV linear code applied at the cloud. Further, as a byproduct
of the analysis, we introduce the dependency graph of a linear
code and its chromatic number as novel relevant parameters of
a linear code beside the minimum distance, blocklength, and
rate.
The rest of the paper is organized as follows. In Sec. II,
we present the system model focusing, as in [14], on a Binary

Fig. 1: NFV model for uplink channel decoding. The input file u is divided into smaller packets and encoded with a linear code Cu having generator matrix
Gu . The packets are received by the RRH through a BSC and forwarded to a cloud. Server 0 in the cloud re-encodes the received packet with a linear code
Cc in order to enhance robustness against the potentially straggling servers 1, . . . , N .
Symmetric Channel (BSC) for uplink communications. Sec. III
presents the two proposed upper bounds on the Frame Error
Rate (FER), and Sec. IV provides numerical results.
II. S YSTEM M ODEL
As illustrated in Fig. 1, we consider the uplink of a CRAN system in which a user communicates with the cloud
via a remote radio head (RRH). The user is connected to
the RRH via a BSC with bit flipping probability δ, while
the RRH-to-cloud link, typically referred to as fronthaul, is
assumed to be noiseless. Note that the BSC is a simple model
for the uplink channel, while the noiseless fronthaul accounts
for a typical deployment with higher capacity fiber optic
cables. The cloud contains a master server, or server 0, and
N slave servers, i.e., servers 1, . . . , N . The slave servers are
characterized by random computing delays as in related works
on coded computation [7], [8], [12]. Note that we use here the
term “server” to refer to a decoding processor, although, in a
practical implementation, this may correspond to a core of the
cloud computing platform [13].
The user encodes a file u consisting L bits. Before encoding,
the file is divided into K blocks u1 , u2 , . . . , uK ∈ {0, 1}L/K
of equal size, each of them containing L/K bits. As shown in
Fig. 1, in order to combat noise on the BSC, the transmitted
frames are encoded by an (n, k) binary linear code Cu of rate
r = k/n defined by generator matrix Gu ∈ Fn×k
, where n =
2
L/(rK) and k = L/K. Let xj ∈ {0, 1}n with j ∈ {1, . . . , K}
be the K transmitted packets of length n. At the output of the
BSC, the length-n received vector for the jth packet at the
RRH is given as
yj = xj ⊕ zj ,
(1)
where zj is a vector of i.i.d. Bern(δ) random variables (rvs).
The K received packets (y1 , y2 , . . . , yK ) by the RRH are
transmitted to the cloud via the fronthaul link, and the cloud
performs decoding. Specifically, as detailed next, we assume
that each server 1, . . . , N performs decoding of a single packet
of length n bits while server 0 acts as coordinator.
Assuming the overprovisioning of servers, which entails the
condition N ≥ K, we adopt the idea of NFV coding proposed
in [14]. Accordingly, as seen in Fig. 2, the K packets are
first linearly encoded by server 0 into N ≥ K coded blocks

Fig. 2: Coded NFV at the cloud: Server 0 re-encodes the received packets
in Y by a linear NFV code Cc with generator Gc . Each encoded packet ỹi
then conveyed to server i for decoding.

of the same length n bits, each forwarded to a different server
for decoding. This form of encoding is meant to mitigate the
effect of straggling servers in a manner similar to [7], [8],
[12]. Using an (N, K) linear code Cc with K × N generator
matrix Gc ∈ F2N ×K , the encoded packets are obtained as
Ỹ = YGc ,

(2)

where Y = [y1 , . . . , yK ] is the n × K matrix obtained by
including the received signal yj as the jth column and Ỹ =
[ỹ1 , . . . , ỹN ] is the n × N matrix whose ith column ỹi is the
input to server i, where i ∈ {1, . . . , N }. From (1), this vector
can be written as
ỹi =

K
X
j=1

yj gc,ji =

K
X
j=1

xj gc,ji +

K
X

zj gc,ji ,

(3)

j=1

where gc,ji is the (j, i) entry of matrix Gc .
PK
The signal part j=1 xj gc,ji in (3) is a linear combination
of di codewords for the rate-r binary code with generator
matrix Gu , and hence it is a codeword of the same code. The
parameter di , i ∈ {1, . . . , N }, denotes the Hamming weight
of the ith column of matrix Gc , where 0 ≤ di ≤ K. Each
server i receives as input
PK the packets ỹi from which it can
decode the codeword i=1 xi gc,ji . This decoding operation
PK
is affected by the noise vector j=1 zj gji in (3), which has
i.i.d. Bern(γi ) elements. Here γi is obtained as the first row
and second column’s entry of the matrix Qdi , with Q being
the channel matrix Q = (1 − 2δ) I + δ11T (I is the identity
matrix and 1 the all-one column vector). Note that a larger
value of di yields a larger bit flipping probability γi . We define

as Pn,k (γi ) the decoding error probability of server i, which
can be upper bounded by [16, Theorem 33].
Server i requires a random time Ti = T1,i +T2,i to complete
decoding, which is modeled as the sum of a component T1,i
that is independent of the workload and a component T2,i
that instead grows with the size n of the packet processed at
each server, respectively. The first component accounts, e.g.,
for processor unavailability periods, while the second models
the execution runtime from the start of the computation.
The first variable T1,i is assumed to have an exponential
probability density function (pdf) f1 (t) with mean 1/µ1 , while
the variable T2,i has a shifted exponential distribution with
cumulative distribution function (cdf) [17]



rKµ2
L
F2 (t) = 1 − exp −
t−a
,
(4)
L
rK

Fig. 3: Dependency graph associated with an (8,4) NFV code
Cc in Example 1.
(ii) described above occur, respectively, and zero otherwise.
Based on these definitions, the FER is equal to
"N
#
X
Pe (t) = Pr
Ci (t)Di ≤ N − dmin .
(7)
i=1

for t ≥ aL/(rK) and F2 (t) = 0 otherwise. The parameter a
represents the minimum processing time per input bit, while
1/µ2 is the average additional time needed to process one
bit. The cdf ofR the time Ti can hence be written as the
t
integral F (t) = 0 f1 (τ )F2 (t − τ )dτ . We also assume that the
N
runtime rvs {Ti }i=1 are mutually independent. Due to (4), the
probability that a given set of l out of N servers has finished
decoding by time t is given as
al (t) = F (t)l (1 − F (t))N −l .

(5)

Let dmin be the minimum distance of the NFV code Cc . Due
to (3), server 0 in the cloud is able to decode the message u
or equivalently the K packets uj for j ∈ {1, . . . , K}, as soon
as N − dmin + 1 servers have decoded successfully. Let ûi be
the output of the ith server in the cloud upon decoding. The
output û of the decoder at server 0 at time t is then a function
of the vectors ûi (t) for i ∈ {1, . . . , N }, where
(
ûi , if Ti ≤ t,
ûi (t) =
∅, otherwise.
Finally, the frame error rate (FER) at time t is defined as the
probability
Pe (t) = Pr [û(t) 6= u] .
(6)
III. L ARGE D EVIATION B OUND ON THE F RAME E RROR
P ROBABILITY
In this section we derive analytical bounds on the error
probability Pe (t) in (6).
A. Preliminaries
Each server i with i ∈ {1, . . . , N } decodes successfully its
assigned packet ỹi if: (i) the server completes decoding by
time t; (ii) the decoder is able to correct the errors caused by
the BSC. Furthermore as discussed, an error occurs at time
t if the number of servers that have successfully decoded by
time t is smaller than N − dmin + 1. To evaluate the FER, we
hence define the indicator variables Ci (t) = 1{Ti ≤ t} and
Di = 1{ûi = ui }, which are equal to 1 if the events (i) and

The indicator variables Ci (t) are independent Bernoulli rvs
across the servers i ∈ {1, . . . , N }, due to the independence
assumption on the rvs Ti . However, the indicator variable Di
are dependent Bernoulli rvs. The dependence P
of the variables
K
Di is caused by the fact that the noise terms i=1 zj gc,ji in
(3) generally have common terms. In particular, if two columns
i and j of the generator matrix Gc have at least a 1 in the same
row, then the decoding indicators Di and Dj are correlated.
This complicates the evaluation of bounds on the FER (7).
B. Dependency Graph and Chromatic Number of a Linear
Code
To capture the correlation among the indicator variables Di ,
we introduce here the notion of the dependency graph and its
chromatic number for a linear code. These appear to be novel
properties of a linear code, which will be argued below to
determine a code’s performance for the application at hand.
0

0

Definition 1. Let G ∈ F2K ×N be a generator matrix of a
linear code. The dependency graph G(G) = (V, E) comprises
a set V of N 0 vertices and a set E ⊆ V × V of edges, where
edge (i, j) ∈ E is included if both the ith and jth columns of
G have at least a 1 in the same row.
Example 1. For an (8, 4) NFV code Cc with the following
generator matrix
 1 0 0 0 0 1 1 0 
0
Gc =  0
1

0
1
0

0
0
1

1
0
0

1
0
1

0
0
0

0
1
0

1 
1 ,
0

(8)

Fig. 3 shows the resulting dependency graph G(Gc ).
The chromatic number X (G) of the graph G(G) will play
an important role in the analysis. We recall that the chromatic
number is the smallest number of colors needed to color the
vertices of G(G), such that no two adjacent vertices share
the same color (see example in Fig. 3). Generally, finding the
chromatic number of a graph is NP-hard [18]. However, a
simple upper bound on X (G) is given as [19]
X (G) ≤ ∆(G) + 1,
where ∆(G) is the maximum degree of a graph G(G).

(9)

C. Large Deviation Upper Bound
In this subsection, we provide a first upper bound on the
FER. The bound is based on the largePdeviation result in [15]
M
for the tail probabilities of rvs X = i=1 Xi , where the rvs
Xi are generally dependent. The correlation of rvs {Xi } is
described in [15] by a dependency graph. This is defined as
any graph G(X) with Xi as vertices, such that, if a vertex
i ∈ {1, . . . , M } is not connected to any vertex in a subset
J ⊂ {1, . . . , M }, then Xi is independent of {Xj }j∈J .
PM
Lemma 1 ( [15]). Let X = i=1 Xi , where Xi ∼ Bern(pi )
and pi ∈ (0, 1) are generally dependent. For any b ≥ 0,
such that the inequality Xi − E(Xi ) ≥ −b holds for all
i ∈ {1, . . . , M } with probability one, and for any τ ≥ 0
we have



4bτ
S
ϕ
, (12)
Pr[X ≤ E(X) − τ ] ≤ exp − 2
b X (G(X))
5S
∆ PN
∆
where S = i=1 Var(Xi ) and ϕ(x) = (1 + x) ln(1 + x) − x.
The same bound (12) holds for Pr(X ≥ E(X) + τ ), where
Xi − E(Xi ) ≤ b with probability one.
The following theorem uses Lemma 1 to derive a bound on
the FER.
N
Theorem 1. Let Pmin
n,k = mini {Pn,k (γi )}i=1 . Then, for all
!!
PN
dmin − i=1 Pn,k (γi )
1
t ≥ n a − ln
,
(13)
PN
µ
N − i=1 Pn,k (γi )

the FER is upper bounded as in
 (10), shown
 at the bottom
∆
∆
of the page, where b(t) = F (t) 1 − Pmin
− 1 and S(t) =
n,k
PN
i=1 F (t) (1 − Pn,k (γi )) (1 − F (t)(1 − Pn,k (γi ))).
PN
∆
Proof. Let Xi (t) = Ci (t)Di and X(t) = i=1 Xi (t), where
Xi (t) are dependent Bernoulli rvs with probability E[Xi (t)] =
Pr[Xi (t) = 1] = F (t) (1 − Pn,k (γi )). It can be seen that a
valid dependency graph G(X) for the variables {Xi } is the
dependency graph G(Gc ) defined above. This is due to the
fact, discussed in Section III-C, that the rvs Xi and Xj are
dependent if and only if the ith and jth column of Gc have
at least a 1 in a common row. We can hence apply Lemma
1 for every time t by selecting τ = E(X) − N + dmin , and
b(t) as defined above. Note that this choice of b(t) meets the
constraint for b in Lemma 1.
The upper bound (10), on the FER captures the dependency
of the FER on both the channel code and the NFV code.

In particular, the bound is an increasing function of the
error probabilities Pn,k (γi ), which depend on both codes. It
also depends on the NFV code through parameters dmin and
X (Gc ).
D. Union Bound
As indicated in Theorem 1, the large deviation based bound
in (10) is only valid for large enough t, as can be observed
from (13). Furthermore, it may generally not be tight, since
it neglects the independence of the indicator variables Di . In
this subsection, a generally tighter but more complex bound
is derived that is valid for all times t.
Theorem 2. For any subset A ⊆ {1, . . . , N }, define
X
∆
min(A) ∆
Pn,k
= min{Pn,k (γi )}i∈A and PA
Pn,k (γi ),
n,k =
i∈A

and let GA be the K × |A|, submatrix of Gc , with column
indices in the subset A. Then, the FER is upper bounded
by (11), shown at the bottom of the page, where SA (t) ,
P
∆
min(A)
.
i∈A Pn,k (γi ) (1 − Pn,k (γi )) and bA = 1 − Pn,k
Proof. Let Ii = 1 − Di be the indicator variable which
equals 1 if server i fails decoding. Accordingly, we have
Ii ∼ Bern(P
n,k (γi )). For each subset A ⊆ {1, . . . , N }, let
P
IA = i∈A Ii . The complement of the FER Ps (t) = 1−Pe (t)
can hence be written as
"N
#
X
Ps (t) =Pr
Ci (t)Di > N − dmin
(14)
i=1

=

N
X

al (t)

l=N −dmin +1

X

(1 − Pr [IA ≥ l − N + dmin ]) .

A⊆{1,...,N }:
|A|=l

(15)
We can now apply Lemma 1 to the probability in (15)
by noting that G(GA ) is a valid dependency graph for the
variables {Ii }, i ∈ A. In particular, we apply Lemma 1 by
settingP
τA = l − N + dmin − E(IA ), bA ≥ Ii − E[Ii ], and
SA = i∈A Var (Ii ), leading to
Pr [IA ≥ l − N + dmin ] ≤

 


A
4b
l
−
N
+
d
−
P
A
min
n,k
SA
 .
ϕ
exp − 2
bA X (GA )
5SA
(16)
By substituting (16) into (15), the proof is completed.


 
PN
4b(t)
N
F
(t)
−
F
(t)
P
(γ
)
−
N
+
d
n,k
i
min
i=1
S(t)
 ,
Pe (t) ≤ exp − 2
ϕ
b (t)X (Gc )
5S(t)


Pe (t) ≤ 1 −

N
X
l=N −dmin +1




 

4bA l − N + dmin − PA
n,k
S
A
1 − exp −
 .
ϕ
b2A X (GA )
5SA


al (t)

X
A⊆{1,...,N }:
|A|=l

(10)



(11)

Fig. 4: Large deviation (LDB) bound of Theorem 1 and union bound (UB)

Fig. 5: Exact FER for single-server decoding, repetition coding, uncoded

in Theorem 2 for single-server decoding, repetition coding, uncoded approach,
SPC code and the NFV code Cc defined in (8) (L = 504, N = 8, 1/µ1 =
0, µ2 = 10, a = 1, δ = 0.01, r = 0.5).

approach and Monte Carlo simulation results for the SPC code and the NFV
code Cc defined in (8) (L = 504, N = 8, 1/µ1 = 0, µ2 = 10, a = 1, δ =
0.01, r = 0.5).

IV. S IMULATION R ESULTS
In this section we provide some numerical result to validate
the two bounds presented in Theorems 1 and 2, as well as to
assess the importance of coding in obtaining desirable tradeoffs between decoding latency and FER. We employ a frame
length of L = 504 and N = 8 servers. The user code Cu is
selected to be a randomly designed (3, 6) regular (Gallagertype) LDPC code with r = 0.5, which is decoded via belief
propagation.
Figures 4, 5, 6, and 7 compare the performance of the following solutions: (i) Standard single-server decoding, whereby
we assume the use of a single server, that is N = 1, that
decodes the entire frame (K = 1); (ii) Repetition coding,
whereby the entire frame (K = 1) is replicated at all servers;
(iii) Parallel (or uncoded) processing, whereby the frame is
divided into K = N disjoint parts processed by different
servers; (iv) Single parity check code (SPC), with K = 7,
whereby one server decodes a binary sum of all other K
received packets; and (v) an NFV code Cc with the generator
matrix Gc defined in (8), which is instead characterized by
K = 4.
Note that, with both single-server decoding and repetition
coding, we have the blocklength n = 1008 for the channel code. Single-server decoding is trivially characterized by
X (Gc ) = dmin = 1, while repetition coding is such that
the equalities X (Gc ) = dmin = 8 hold. Furthermore, the
uncoded approach is characterized by n = 126, dmin = 1
and X (Gc ) = 1; the SPC code has n = 144, dmin = 2 and
X (Gc ) = 2; and the NFV code Cc has n = 252, dmin = 3 and
X (Gc ) = 3. The exact FER for a given function Pn,k (·) can
easily be computed for cases (i)-(iii). In particular, for single

server decoding, the FER equals
Pe (t) = 1 − a1 (t)(1 − PL/r,L (δ));

(17)

for the repetition code, the FER is
Pe (t) = 1 −

N
X

ai (t)(1 − PL/r,L (δ));

(18)

i=1

and with the uncoded approach, we have
Pe (t) = 1 − aN (t)(1 − PL/(rN ),L/N (δ))N .

(19)

Note that the exact FER for the NFV code SPC code and Cc is
difficult to compute owing to the discussed correlation among
the decoding outcomes at the servers.
In Fig. 4 and Fig. 5, we assume that the latency contribution
that is independent of the workload is negligible, i.e., 1/µ1 =
0. In Fig. 6 and Fig. 7, we consider instead a case with a
positive value for 1/µ1 , in which latency may be dominated
by effects that are independent of n.
Fig. 4 shows both LDB in Theorem 1 and UB in Theorem
2, respectively, for all five schemes, 1/µ1 = 0, a = 1, and
µ2 = 10. As a first observation, Fig. 4 confirms that the
UB bound is tighter than the LDB. Furthermore, we note
that leveraging multiple servers in parallel for decoding yields
significant gains in terms of the trade-off between latency
and FER as argued also in [13] using experimental results.
With regard to the comparison among different NFV coding
schemes, we first observe that the bounds indicate that the
uncoded scheme is to be preferred for lower latencies. This
is due to the shorter blocklength n, which entails a smaller
average decoding time. However, the error floor of the uncoded
scheme is large given the higher error probability on the

Fig. 6: Large deviation (LDB) bound of Theorem 1 and union bound (UB)

Fig. 7: Exact FER for single-server decoding, repetition coding, uncoded

in Theorem 2 for single-server decoding, repetition coding, uncoded approach,
SPC code and the NFV code Cc defined in (8) (L = 504, N = 8, 1/µ1 =
50, µ2 = 20, a = 0.1, δ = 0.01, r = 0.5).

approach and Monte Carlo simulation results for the SPC code and the NFV
code Cc defined in (8) (L = 504, N = 8, 1/µ1 = 50, µ2 = 20, a =
0.1, δ = 0.01, r = 0.5).

V. C ONCLUSIONS
BSC for short blocklengths. In contrast, repetition coding
requires a larger latency in order to obtain acceptable FER
performance owing to the larger blocklength n, but it achieves
a significantly lower error floor. For intermediate latencies,
SPC, and at larger latencies also the NFV code Cc , provide
a lower FER according to the bounds. This suggests the
effectiveness of NFV encoding in obtaining a desirable tradeoff between latency and FER.
In order to validate the conclusion obtained using the
bounds, Fig. 5 shows the exact FER for the schemes (i)-(iii),
as well as Monte Carlo simulation results for schemes (iv)
and (v). While the absolute numerical values of the bounds
in Fig. 4 are not uniformly tight with respect to the actual
performance evaluated by Fig. 5, the relative performance of
the coding schemes in the two figures are well matched. This
demonstrates that the derived bounds can serve as a useful
tool for code design in NFV systems.
Fig. 6 and Fig. 7 are obtained as Fig. 4 and Fig. 5,
respectively, but with the parameters µ1 = 0.02, µ2 = 20, and
a = 0.1. The key difference with respect to Fig. 4 and Fig. 5 is
that, in this regime, repetition coding tends to outperform both
uncoded and the NFV code Cc apart from very small latencies.
This is because repetition coding has the maximum resilience
to the servers unavailability while the latency associated to
the larger blocklength n, is dominated here by effects that are
independent of n. This is not the case, however, for very small
latency levels, where the NFV code Cc provides the smallest
FER given its shorter blocklength as compared to repetition
coding and its larger dmin with respect to the uncoded scheme.

In this paper, we analyzed the performance of a novel coded
NFV approach for the uplink of a C-RAN system in which
decoding takes place at a multi-server or multi-core cloud
processor. The approach is based on the linear combination of
the received packets prior to their distribution to the servers
or cores, and on the exploitation of the algebraic properties
of linear channel codes. The method can be thought of as
an application of the emerging principle of coded computing
to NFV. Analysis and simulation results demonstrate the
significant gains that linear coding of received packets, or NFV
coding, can yield in terms of trade-off between decoding latency and FER. Among interesting open problems, we mention
here the design of optimal NFV codes and the extension of
the principle of NFV coding to Gaussian channels.
R EFERENCES
[1] R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, and
R. Boutaba, “Network function virtualization: State-of-the-art and research challenges,” IEEE Communications Surveys & Tutorials, vol. 18,
no. 1, pp. 236–262, 2016.
[2] European Telecommunications Standards Institute, “Network functions
virtualisation (NFV); reliability; report on models and features for endto-end reliability,” Tech. Rep. GS NFV-REL 003 V1.1.1, Apr. 2016.
[3] J. Liu, Z. Jiang, N. Kato, O. Akashi, and A. Takahara, “Reliability
evaluation for NFV deployment of future mobile broadband networks,”
IEEE Wireless Communications, vol. 23, no. 3, pp. 90–96, 2016.
[4] J. G. Herrera and J. F. Botero, “Resource allocation in NFV: A
comprehensive survey,” IEEE Transactions on Network and Service
Management, vol. 13, no. 3, pp. 518–532, 2016.
[5] J. Kang, O. Simeone, and J. Kang, “On the trade-off between computational load and reliability for network function virtualization,” IEEE
Communications Letters, 2017.
[6] J. Dean and S. Ghemawat, “Mapreduce: simplified data processing on
large clusters,” Commun. of the ACM, vol. 51, no. 1, pp. 107–113, 2008.

[7] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran,
“Speeding up distributed machine learning using codes,” Proc. IEEE
International Symposium on Information Theory, pp. 1143–1147, 2016.
[8] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “Fundamental tradeoff
between computation and communication in distributed computing,”
[Online] www.arxiv.org, arXiv:1609.01690 [], 2016.
[9] Y. Yang, P. Grover, and S. Kar, “Computing linear transformations with
unreliable components,” IEEE Trans. on Inf. Theory, 2017.
[10] T. Rashish, L. Qi, G. D. Alexandros, and K. Nikos, “Gradient coding,”
[Online] www.arxiv.org arXiv:1612.03301 [], 2016.
[11] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear
transforms distributedly using coded short dot products,” Advances In
Neural Information Processing Systems, pp. 2092–2100, 2016.
[12] A. Severison, A. Graell i Amat, and E. Rosnes, “Block-diagonal
coding for distributed computing with straggling servers,” [Online]
www.arxiv.org, arXiv:1701.06631 [], Jan. 2017.
[13] V. Q. Rodriguez and F. Guillemin, “Towards the deployment of a fully
centralized Cloud-RAN architecture,” in IEEE IWCMC, Spain, 2017.
[14] A. Al-Shuwaili, O. Simeone, J. Kliewer, and P. Popovski, “Coded
network function virtualization: Fault tolerance via in-network coding,”
IEEE Wireless Communications Letters, vol. 5, no. 6, pp. 644–647, 2016.
[15] S. Janson, “Large deviations for sums of partly dependent random
variables,” Random Structures & Algorithms, vol. 24, no. 3, pp. 234–
248, 2004.
[16] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the
finite blocklength regime,” IEEE Transactions on Information Theory,
vol. 56, no. 5, pp. 2307–2359, 2010.
[17] A. Reisizadehmobarakeh, S. Prakash, R. Pedarsani, and S. Avestimehr, “Coded computation over heterogeneous clusters,” [Online]
www.arxiv.org, arXiv:1701.05973 [], 2017.
[18] A. Sánchez-Arroyo, “Determining the total colouring number is nphard,” Discrete Mathematics, vol. 78, no. 3, pp. 315–319, 1989.
[19] R. L. Brooks, “On colouring the nodes of a network,” Mathematical
Proceedings of the Cambridge Philosophical Society, vol. 37, no. 02,
pp. 194–197, 1941.

