Interference Alignment as a Tool in Network Coding as Applied to Distributed Storage

Interference Alignment as a Tool in Network Coding as Applied to Distributed Storage

K. V. Rashmi

, Nihar B. Shah

, P. Vijay Kumar

, Kannan Ramchandran

†

Dept. of ECE, Indian Institute Of Science, Bangalore, India.

Email:

#

Dept. of EECS, University of California, Berkeley, USA.

Email: kannanr@eecs.berkeley.edu

Abstract—In this paper, we outline an approach to the task of designing network codes in a non-multicast setting. Our approach makes use of the concept of interference alignment.

As an example, we consider the distributed storage problem where the data is stored across the network inn nodes and where a data collector can recover the data by connecting to anykof thennodes and where furthermore, upon failure of a node, a new node can replicate the data stored in the failed node while minimizing the repair bandwidth.

I. INTRODUCTION

We begin with a detailed description of the distributed storage setup. A file of sizeBis to be stored in a distributed manner across n storage nodes, each having a storage capacity ofαunits of data (symbols). Each symbol belongs to a finite field Fq of sizeq. A data collector (DC) which downloads data stored in anykout of thennodes should be able toreconstruct the entire file. We consider the setting in which each node stores the minimum amount of data required for any DC to reconstruct the data i.e

α=B/k (1)

When a node fails, the new node replacing the failed node is permitted to download β symbols each from d existing nodes in order to obtain (and store) the same data as the failed node. This is termed asexact regeneration. We assume that the data is stored in systematic form in some k out of the n nodes, say nodes 1, . . . , k. Our interest is in minimizing the repair bandwidth for exact regeneration of the systematic nodes. For the purposes of this paper, we will refer to this problem as the distributed storage problem. Only linear codes will be considered.

The pioneering paper in this area [1] considers a more general setting in which the regenerated node need not be identical to the failed node and goes on to present bounds and achievability proofs for that setting.

In our previous work [2], we considered the problem of exact regeneration, however for the case when a node is allowed to store extra data in order to reduce the repair bandwidth. We also gave an approximately exact regenerating code when nodes have minimum storage and for the parameter setd=k+ 1. Each of these codes meet the lower bound on the repair bandwidth.

In [3] authors consider the setting of exact regeneration and apply interference alignment to this specific setting.

They provide schemes which reduce the dimension of

interference, but to values larger than optimal, resulting in a suboptimal scheme.

The problem of obtaining codes to minimize the repair bandwidth is a non-multicast network coding problem, for which very few results are available. In [4] it is shown that determining whether a linear network coding solution exists for an arbitrary network is NP-hard. The insufficiency of linear coding for the non-multicast case is shown in [5].

We make the observation that in this class of net- works, the notions of interference alignment and useful information flow are essential. Using these concepts, we provide a solution to the distributed storage problem which minimizes the repair bandwidth for exact regeneration of the systematic nodes for the case of d≥2k−1.

We also show how these concepts can be applied to a larger class of networks as well as provide insight that will aid in code design. It will also be shown to help tighten existing cut-set based upper bounds.

The paper is organized as follows. Section II presents the distributed storage problem as a non-multicast problem.

In Section III a set of necessary and sufficient conditions based on interference alignment are provided for a network of non-multicast type to be linearly solvable. In Section IV we apply these conditions to a class of networks - networks with crosslinks and obtain tighter upper bounds on the achievable rates as compared to the traditional cut- set bound. Section V specializes to the case of distributed storage problem. Finally, using the insights obtained here, a code minimizing the repair bandwidth is constructed in Section VI.

II. DISTRIBUTED STORAGE AS A NON-MULTICAST PROBLEM

We now present the distributed storage problem as an instance of a non-multicast network coding problem in which the graph of the network is directed, delay free and acyclic. The network is viewed as having ksource nodes, each corresponding to a systematic node and generating α symbols each per unit time. The non-systematic nodes are simply viewed as downlink nodes. Since it is only possible to download α symbols from a downlink node, this is taken care of in the graph as in [1], by (i) splitting each non-systematic nodeminto two nodes:min andmout

with an edge of capacity α linking the two with (ii) all

node 2

node 3_out

node 1 1'

2'

DC

DC DC DC

DC DC

node 3_in

node 4_in

α β

ββ β ββ

α _{node 4out} α

α

Fig. 1: Complete network for the distributed storage prob- lem for n= 4, k= 2 andd = 3. Unmarked edges have capacityα.

incoming edges arriving into min and all outgoing edges emanating frommout. The sinks in the network are of two types. The first type correspond to data collectors which connect to some collection ofk nodes in the network for the purposes of data reconstruction. Hence there are ⁿ_k sinks of this type. The second type of sinks represents a new node that is attempting to duplicate a failed systematic node. Nodes of this type are assumed to connect to the remainingk−1 systematic nodes and anyd−(k−1)of the non-systematic nodes. Hence there are _d−k+1^n−k

sinks of this type. The non-multicast network for the parameter set n= 4, k = 2, d = 3 is shown in Figure 1. A part of the network for the general problem is given in Figure 2.

We now introduce some additional notation with respect to this non-multicast network. Figure 2 shows a part of the network, and depicts one of the DCs which connects to somek nodes and two possible new nodes corresponding to failure of the first systematic node connecting to two different sets of dexisting nodes.

Let f be a vector of length B corresponding to the B symbols produced by the k sources (systematic nodes).

Let f^t = [f₁. . . f_k] where f_l is an α length row vector corresponding to the α symbols generated by systematic nodel.

Every edgeeis associated with a matrixMe of dimen- sionCe×BwhereCeis the capacity of that edge. The rows of the matrixMeare theCeglobal kernels associated with Ce symbols flowing along the edge. The actual symbols carried by the edge isMef. Columns(l−1)α+ 1tolαof Me for any l ∈ {1, . . . , k} are referred to as the columns corresponding to systematic nodel.

Let tail(e) and head(e)be the tail and head vertices of edge erespectively. If the tail(e)of an edge eis a source node i.e. systematic nodel(∈ {1, . . . , k})then inMe, the columns corresponding to any other systematic node have to be zero. For any other edge e, Me is a linear combi- nation of matricesMe⁰ ∀e⁰ such that head(e⁰) = tail(e), where the coefficients of linear combination themselves are matrices.

node 2 node k+1_out

node m_out node 1

1' 1' DC

node k+1_in

node n_in α

α node k

ββ β Systematic nodes

(sources) Non-systematic nodes

(intermediate nodes)

d edges

k edges DCs and regenerated nodes

(sinks)

α

α

α

Fig. 2: Part of the multicast network of the general dis- tributed storage problem. Unmarked edges have capacity α.

In the next section we will show how it is possible to use the concept of interference alignment to set up a framework for code design in a general network of non-multicast type.

We will return in the subsequent sections to the problem of distributed storage.

III. NECESSARY AND SUFFICIENT CONDITIONS FOR A GENERAL NETWORK

The theorems stated in this section give a set of neces- sary and sufficient conditions that need to be satisfied by any linear coding solution to a general network of non- multicast type.

While the theorems on the one hand are intuitively obvi- ous, they nevertheless provide a new and useful perspective to the problem of code design and this will be illustrated in the subsequent sections. In general, the viewpoint yields heuristics that aid in code construction and sometimes permit tighter upper bounds on achievable rates than the cut-based bounds.

Setting and notation: As mentioned earlier we consider delay free, acyclic, directed graphs. We also assume the networks to be error free. We consider scalar linear network coding solution for these networks. All symbols belong to some finite field Fq. An edgee in the network can carry an integral number of symbols fromFq, and the maximum number of such symbols it can carry at a time is called the capacity of that edgeC_e.

There are k independent sources S₁, . . . , S_k. Without loss of generality we assume that each sink demands all the information from exactly one source. If a sink demands multiple sources, or a part of a source, then an equivalent network can be constructed by splitting the sink or the source respectively. Also, we assume that there is at least one sink corresponding to every source. A sink is namedTl

if it demands sourceSl. The source and sink nodes do not have any incoming and outgoing edges respectively. LetRl

be the rate of the sourceSl (l = 1, . . . , k). An edge from vertex utov is represented asu→v.

A cut Ω (as illustrated in Figure 3) is a partition of vertices into two sets, called the source side and thesink

S₁ S₂

A

B

T₂ T₁

Ω S₃

T₁ T₃ C

S_D S_I

S_N

source side

sink side

Fig. 3: An illustration of a cutΩand associated source-sets

sidepartitions. Edges going across the cut from source side to sink side are said to belong to the cut. The capacity of a cutΩ, denoted by C(Ω) is the sum of capacities of all the edges in the cut.

For any cut, the set of sources are divided into three sets:

SD(Ω) is the set of desired sources, i.e. those which are on the source side of the cut and having at least one of its corresponding sinks on the sink side; SI(Ω) is the set of interfering sources, i.e. those which are on the source side of the cut and having none of its corresponding sinks on the sink side; and SN(Ω) is the set ofneutralsources, i.e. those which are on the sink side of the cut. RD(Ω), RI(Ω) andRN(Ω) are the total rates of the three sets of sources respectively.

LetR=Pk

l=1Rl. As defined in Section II, each edge is associated with a matrix of dimensionCe×R.

Consider any cut Ω and an arbitrary set of sources S.

The dimension of S in the cut, denoted as dim(S,Ω) is defined as the dimension of the vector space spanned by the rows of M_e ∀e ∈ Ω considering only the columns corresponding to the sources inS. LetE(Ω)for any cutΩ denote the set of rows of matrices of all the edges in that cut.

Theorem 1 (Useful Information Flow): A necessary condition for a code to achieve the rate tuple(R1, . . . , Rk) is that for any cut Ω,

dim(SD(Ω),Ω)≥RD(Ω) (2) Theorem 2 (Interference Alignment): A necessary con- dition for a code to achieve the rate tuple(R₁, . . . , R_k)is that for any cutΩ,

dim(S_I(Ω),Ω)≤C(Ω)−R_D(Ω) (3) Theorem 3: A necessary and sufficient condition for a code to achieve the rate tuple(R1, . . . , Rk)is that for any cut Ωthere exists a linear transformation T on E(Ω) and F ⊆ E(Ω) of sizeRD such that

• The dimension of the vector space spanned by the rows of F considering only the columns correspond- ing to the sources in SD isRD.

• The vector space spanned by the rows ofF consider- ing only the columns corresponding to the sources in S_I is linearly dependent to that inE − F.

• The linear transformationT onE(Ω)results inFwith columns corresponding to the sources in S_I nulled out and columns corresponding to the sources in S_D retaining rank R_D.

In the next section, we show how the presence of crosslinks can be used to tighten upper bounds on achiev- able rates.

IV. BOUND FORNETWORKS WITH CROSSLINKS

Definition 1 (Crosslink): A crosslink is an edge from source Si to sinkTj wherei6=j.

Networks with a large number of crosslinks arise in quite a few applications such as peer-to-peer file sharing where nodes simultaneously upload and download parts of files, in distributed storage etc. A well-known example is the butterfly network, whose modified versions are shown in Figure 4. Here,S2→T1in Figure 4a and theS1→T2in Figure 4b are the crosslinks. These crosslinks help to cancel out the interference at the sinks, but do not contribute directly to useful information flow.

Theorem 4 (Upper bound for networks with crosslinks):

For any cut Ω and any partition of SD(Ω) into SD1(Ω) and SD2(Ω), let C(Ω)˜ be the total capacity of the cut after removing all the crosslinks, then

RD(Ω)≤C(Ω) +˜ CCL(SD1(Ω),TD2(Ω)) (4) where CCL(SD1(Ω),TD2(Ω)) is the sum capacity of all the crosslinks which originate inS_D1(Ω) and terminate in any sink corresponding to S_D2(Ω).

Proof: The set of sourcesS_D1(Ω)act as interference for sinks T_D2(Ω). Hence by Theorem 2,

dim(S_D1(Ω),Ω)≤

C(Ω)˜ −RD2(Ω) +CCL(SD1(Ω),TD2(Ω)) (5) Since SD1(Ω)⊆SD(Ω), by Theorem 1 we get

RD1(Ω)≤dim(SD1(Ω),Ω) (6) Thus from equations (5) and (6),

RD1(Ω)≤C(Ω)˜ −RD2(Ω) +CCL(SD1(Ω),TD2(Ω)) (7) This leads to equation (4).

Example 1: Consider the butterfly network in Figure 4a.

The cut-set bound givesR1≤1,R2≤1 andR1+R2≤ 2. Choose a cutΩas shown in the figure. We getSD(Ω) = {S1,S2}, C(Ω) = 2. Choose SD1(Ω) = {S1}. Hence, SD2(Ω) ={S2}.

CCL(S1(Ω),T2(Ω)) = 0 (8) Removing the crosslinkS2→T1 , we get

C(Ω) = 1˜ (9) Thus from equation (4), we get

R1+R2≤1 (10)

S₁ S₂

A

B

T₂ T₁

Ω

(a)

S₁ S₂

A

B

T₂ T₁

Ω

(b)

Fig. 4: Two modifications of the butterfly network. Each edge has unit capacity.

Applying this theorem to the remaining cuts and parti- tions givesR1 ≤1 and R2≤1. Thus, the cut-set bound is tightened in this case.

Example 2: Now consider the butterfly network in Fig- ure 4b. Here, the cut-set bound and the bound given by Theorem 4 coincide to give R1 ≤ 1, R2 ≤ 1 and R1+R2≤2, which is achievable.

V. INTERFERENCEALIGNMENT- THE CRUX OF THE DISTRIBUTED STORAGE SOLUTION

In this section we show how the concept of interference alignment introduced in Section III can be put to good use in attacking the distributed storage problem.

Given an optimal construction for β = 1, optimal constructions for larger values of β can be obtained by partitioning the data into smaller chunks, and encoding them individually using the construction forβ= 1. Hence we consider onlyβ = 1.

The cut-set bound for the network corresponding to the distributed storage problem gives

β≥ α

d−k+ 1 (11)

which forβ = 1, yields

d≥α+k−1 (12)

We construct codes achieving this bound for the range of parametersd≥2k−1.

Consider the regeneration of a failed systematic node l (l ∈ {1, . . . , k}) using the existing k −1 systematic nodes and an arbitrary set of d−k+ 1 non-systematic nodesm1, . . . , m_d−k+1. The sinkl⁰ hasdincoming edges each of unit capacity, which constitute the trivial cut across l⁰(Figure 2). Denote the subspace spanned by the vectors corresponding to these edges byW.k−1 of these edges are crosslinks as they come from other systematic nodes and hence cannot carry anyuseful information.

Hence to achieve the lower bound given by equation (12), the remaining set of d−k+ 1(=α)edges (coming from the non-systematic nodes) have to carry all the useful

information, and the k−1 crosslinks only help to cancel interference. Consider the vectors corresponding to this set of d −k + 1 edges. Let W^{(N S)}_l be the subspace spanned by these vectors considering only the columns corresponding to systematic node l, and W^{(N S)}_lc be the subspace spanned by these vectors considering only the columns corresponding to all systematic nodes other than l.

Consider the vectors corresponding to the set of thek−1 edges from the existing systematic nodes to l⁰. Let W_l^(C) be the subspace spanned by these vectors considering only the columns corresponding to systematic node l , and let W^(C)_lc be the subspace spanned by these vectors consider- ing only the columns corresponding to all systematic nodes other thanl.

The following is an application of Theorem 1.

Lemma 5:

dim(W_l^{(N S)}) =α (13) Proof: Consider the trivial cut Ω across the sink l⁰. S_D(Ω) ={S_l},R_D(Ω) =R_l=α. Since thek−1 edges r →l⁰, r ∈ {1, . . . , k}, r 6=l are crosslinks, they have zero components alongSl. Thus

dim(W^(C)_l ) = 0 (14)

Number of edges across this cut which are not crosslinks is d−(k−1) =α.

By Theorem 1, we need dim(S_l,Ω) ≥ α. Thus the edges from the non-systematic nodes have to carry linearly independent components along node l.

The following is an application of Theorem 2. By projection of W on a systematic node, we mean the subspace spanned by the vectors corresponding todedges at sink l⁰ considering only the columns corresponding to that systematic node.

Lemma 6: Projection of W on any systematic node r(r ∈ {1, . . . , k}, r 6= l) is confined to a subspace of rank atmost one.

Proof: To satisfy Theorem 3, due to equations (13) and (14),

W_l^{(N S)}c ⊆W^(C)_lc (15) Hence, the projection ofW_l^{(N S)}c onrwill also be contained inside the projection of W^(C)_lc on r. Since the vectors carried by the edgesr˜→l⁰, forr˜= 1, . . . , k, r˜6=l, ˜r6=r originate at sources other thanr, they have zero projections along node r. Thus, dimension of projection ofW^(C)_lc on r is atmost 1. Thus, the projection ofW^{(N S)}_lc onris also confined to at most one dimension.

Thus the projections of the vectors corresponding to the edges from the d−k+ 1non-systematic nodes to sink l⁰ should be such that their projections on systematic nodel must be linearly independent, but on any other systematic must be scalar multiples of each other.

Exact regeneration of a failed systematic node l by connecting tok−1 systematic nodes and d−k+ 1non- systematic nodes implies that a sinkl⁰ connecting to these nodes is able to get its desired sources.

Theorem 7 (Regeneration): A necessary and sufficient

condition for exact regeneration of a failed systematic node l by connecting to the existing k −1 systematic nodes and d −k+ 1 non-systematic nodes is that the set of vectors corresponding to the edges from these non- systematic nodes to sinkl⁰ satisfy Lemmas 5 and 6.

Proof: Necessity: Follows from rom Lemmas 5 and 6. Sufficiency: In the vectors corresponding to edges from non-systematic nodes to sinkl⁰, columns corresponding to systematic node r(r 6=l) are confined to one dimension (Lemma 6). This can be nulled out by the vector corre- sponding to the edge from systematic noderto provideα interference-free vectors. Theseαinterference-free vectors are also linearly independent (Lemma 5). Hence the failed systematic node l can be regenerated exactly.

Theorem 8 (Reconstruction): A necessary and sufficient condition for data reconstruction by a DC connecting tok nodes is that the B×B matrix formed by stacking the α×B matrices corresponding to the edges from these k nodes to DC is full rank.

Proof: Apply Theorem 1 to the trivial cut across the DC.

VI. CODE CONSTRUCTION

In this section we give a solution to the distributed storage problem for the set of parameters d ≥ 2k−1.

We provide a code construction which achieves the lower bound given in equation (12). Equality in (12) givesα≥k.

The code is constructed using the insights obtained in Section V.

LetM^(m)(m=k+ 1, . . . , n)be the matrix associated with the edgem_in→m_out. The crux of the solution lies in the construction of these matrices which correspond to the global kernels of the symbols stored in the non-systematic nodes.

Since each source generates α symbols per unit time, and all edges emanating from sources have a capacity of α, we set the matrices associated with all such edges to be I_α. Thus, the matrices corresponding to incoming edges at any non-systematic node m has full rank B. This allows M^(m) to take any value as the only restriction of M^(m) is that it should be a linear combination of the matrices corresponding to incoming edges at min.

To satisfy Theorems (7) and (8) we set M^(m)=





























λ^(m)_1,1h^(m)_1,1 λ^(m)_1,2h_1,2 · · · λ^(m)_1,kh_1,k λ^(m)_2,1h_2,1 λ^(m)_2,2h^(m)_2,2 · · · λ^(m)_2,kh_2,k

... ... ...

λ^(m)_k,1h_k,1 λ^(m)_k,2h_k,2 · · · λ^(m)_k,kh^(m)_k,k λ^(m)_k+1,1h^(m)_k+1,1 λ^(m)_k+1,2h^(m)_k+1,2 · · · λ^(m)_k+1,kh^(m)_k+1,k

... ... ...

λ^(m)_α,1h^(m)_α,1 λ^(m)_α,2h^(m)_α,2 · · · λ^(m)_α,kh^(m)_α,k



























 (16)

where h^(m)_i,j is a row vector of length α, and λ^(m)_i,j is a scalar whose values will be determined subsequently.

Regeneration: For regeneration of systematic node l, for all the sinks (new nodes) l⁰ which connect to non- systematic nodem, the vector associated with mout →l⁰ is set tol^throw ofM^(m).

Observe that in row l of M^(m), the vectors h_l,j∀j 6=l are independent of m. Hence the projections of the set of vectors corresponding to the edges from thed−k+ 1non- systematic nodes to sink l⁰ on any systematic node r 6=l are just scalar multiples of each other, satisfying Lemma 6.

The interference can be cancelled at sink l⁰ by setting the vector corresponding to edge r→l⁰ to a vector with h_l,r as its r^th component and 0 elsewhere, ∀r ∈ {1, . . . , l− 1, l+ 1, . . . , k}.

the edge from systematic node rto sinkl⁰ carries the a vector which hash_l,ras itsr^thcomponent and0elsewhere.

To satisfy Lemma 5, we need

det









λ^(m_l,l¹⁾h^(m_l,l¹⁾ ... λ^(m_l,l^α)h^(m_l,l^α)









6= 0 (17)

for all systematic nodesl and all combinations of the non- systematic nodesm₁, . . . , m_α. This is a set of polynomials in h and λ as variables which are clearly not identically zero.

Reconstruction:For reconstruction, at any DC, theB×B matrix formed by stacking the k α×B matrices corre- sponding to the incoming edges should be full rank. The determinants of these matrices will also be polynomials in h and λ as variables, which can be shown to be not identically zero.

Hence, assignment of values to the variables satisfying all the above conditions (polynomials evaluating to non- zero values) can be obtained using the method given by Koetter and Medard [6]. An explicit code for this problem is provided in [7].

REFERENCES

[1] Y. Wu, A. G. Dimakis and K. Ramchandran, “Deterministic regener- ating codes for distributed storage,” inProc. Allerton Conference on Control, Computing and Communication, (Urbana-Champaign, IL), September 2007.

[2] K. V. Rashmi, Nihar B. Shah, P. Vijay Kumar and Kannan Ramchan- dran, “Explicit construction of optimal exact regenerating codes for distributed storage,” inProc. Allerton Conf.,September 2009.

[3] Y. Wu and A. Dimakis, “Reducing repair traffic for erasure coding- based storage via interference alignment,” inProc. ISIT,July 2009.

[4] A. R. Lehman and E. Lehman, “Complexity classification of network information flow problems,” inProc. Allerton Conf.,October 2003.

[5] R. Dougherty, C. Freiling, and K. Zeger, ”Insufficiency of linear coding in network information flow,” in IEEE Transactions on Information Theory,vol. 51, no. 8, pp. 2745-2759, Aug. 2005.

[6] Ralf Koetter and Muriel Medard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, v.11 n.5, p.782- 795, Oct. 2003.

[7] Nihar B. Shah, Rashmi K. V., P. Vijay Kumar and Kannan Ram- chandran, ”Explicit codes minimizing repair bandwidth for distributed storage,” to appear inProc. of Information Theory Workshop,, Cairo, January 2010.