[PDF] Beyond Routing: An Algebraic Approach to Network Coding

29441_304_2.pdf

Beyond Routing: An Algebraic Approach to

Network Coding

Ralf Koetter , Muriel M´edard

Abstract— In this paper we consider the issue of network ca- pacity. The recent work by Li and Yeung examined the network capacity of multicast networks and related capacity to cutsets. Ca- pacity is achieved by coding over a network. We present a new framework for studying networks and their capacity. Our frame- work, based on algebraic methods, is surprisingly simple and ef- fective. For networks which are restricted to using linear codes (we make precise later the meaning of linear codes, since the codes are not bit-wise linear), we find necessary and sufficient conditions for any given set of connections to be achievable over a given net- work. For multicast connections, linear codes are not a restrictive assumption, since all achievable connections can be achieved using linear codes. Moreover, coding can be used to maintain connec- tions after permanent failures such as the removal of an edge from the network. We show necessary and sufficient conditions for a set of connections to be robust to a set of permanent failures. For multicast connections, we show the rather surprising result that, if a multicast connection is achievable under different failure sce- narios, a single static code can ensure robustness of the connection under all of those failure scenarios. Index Terms—Network routing, coding.I. INTRODUCTION In this paper, we take a new look at the issue of network ca- pacity. Coding in networks has generally been considered as a method of combatting random intermittent deleterious effects in a network. A typical effect against which we might code would be the loss of packets across a networks owing to con- gestion at certain nodes. Coding is then used to mitigate the effect of such random intermittent losses, which are usually er- godic processes. An example of codes that are well-suited to these applications are Tornado codes [2]. Codes can also be used to improve throughput through net- works without random intermittent errors. In this paper, we restrict ourselves to such networks, which we define precisely in the next section. We consider coding in which nodes in a net- work operate on their inputs to generate their outputs. Recent work in this area [1], [4] has shown that, if coding is permit- ted over the nodes of a network, network capacity can be im- proved over that obtainable by routing alone. Routing itself can be viewed as a special case of coding wherein the outputs of a node are permutations of the inputs. The benefit of coding over routing is easily illustrated by the following example. Consider Figure 1 from [4]. Each link can

transmit a single bit error-free (we do not consider delays). OnCSL, University of Illinois at Urbana-Champaign, koetter@uiuc.edu

LIDS, MIT, Laboratory for Information and Decision Systems, Mas- sachusetts Institute of Technology, medard@mit.edu. This material is based upon work supported by the National Science Foundation under Grant No.

CCR 99-84515 and CCR-0093349.

the left-hand side network, the sourcesmay easily transmit two bits,b 1 andb 2 , to receiversyandz, by using switching atwand broadcasting attandu. On the right-hand side network, a code is required, wherewmust code over the arc(w,x). In this paper, we present a new framework for studying net- works and their capacity. Our framework is surprisingly simple and effective. For networks that are restricted to using linear codes (we make precise later the meaning of linear codes, since these codes are not bit-wise linear), we find necessary and suf- ficient conditions for any given set of connections to be achiev- able over a given network. The concept of using algebraic cod- ing methods that are well suited to arbitrary connections was first proposed by us in [3], without any of the detail or most of the results presented in this paper. Specific types of codes pre- viously proposed for multicast networks, such as convolutional codes [1] and specific types of block codes [4] do not extend well to the case of arbitrary connections. In this paper, we detail our approach and present several the- orems. Using our framework, we show that the case of a multi- cast connection over a network exhibits a very special structure, which makes its feasibility verifiable in polynomial time. This is an improvement over Li and Yeung"s approach, which re- quiresenumerationofthecutsets. Moreover, linearcodesovera network are sufficient to implement any feasible multicast con- nection.s tu yz xb 1 b 1 b 1 b 1 b 2 b 2 b 2 b 2 s tu y z w b 1 b 1 b 1 b 1 + b 2 b 2 b 2 b 2x b 1 + b 2 b 1 + b 2 Figure 1Networks with multicast connection fromstoy andz. For networks where connections are not multicast, the neces- sary and sufficient conditions for the connections to be feasible are, in general, an NP-complete problem. Moreover, while the cutset conditions are necessary and sufficient to establish the feasibility of a certain set of connections for multicast connec- tions, the cutset conditions are only necessary but provably not sufficient for the case of general connections, i.e. of some arbi- trary collection of point-to-point connections. Coding is not only applicable to networks in order to achieve capacity, but can also be used to recover from network failures. Such failures are different from random errors, such as packet losses or bit errors on links, that are described by probabilistic

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

processes. The failures we consider entail the permanent re- moval of an edge, such as would occur in a network if there were a long-term failure due to a link cut or other disconnec- tion. Currently, such failures are dealt with through the use of rerouting, such as link or path protection. Coding can also be used to protect against link failures in networks. The fundamental questions that we strive to answer in this paper are:

1) Under what conditions is a given linear network coding

problem solvable?

2) How can we efficientlyfind a solution to a given linear

network coding problem?

3) When does a static solution exist for a network that is

subject to link failures? Themaintoolswewilluseforansweringtheabove issuesare algebraic in nature and draw on concepts from algebraic geom- etry. In particular, we will relate the network coding problem to the problem offinding points on algebraic varieties, which is one of the central questions of algebraic geometry. In Section II, we present our network model. In Section III we introduce part of the algebraic framework. The goal of the section is to make the reader familiar with some of the employed concepts. The base theorem is an algebraic re- formulation of the M

IN-CUTMAX-FLOWtheorem. We point

out the algebraic interpretation of this theorem in the context of the Ford-Fulkerson algorithm. In Section IV we apply the al- gebraic framework to acyclic networks. Wefirst consider mul- ticast connections. We rapidly recover and extend the work of Li et al. [4] and Ahlswede et al. [1]. In particular, we are able to answer some of the problems left open by the authors [4]. Next, we address the general network coding problem for cycle-free networks. We derive necessary and sufficient condi- tions to guarantee the solvability of a network coding problem. In particular, we can relate the difficulty in deciding the solv- ability of a network coding problem to the problem of deciding if a given variety is empty. The main tool for an algorithmic approach to the problem is the use of Gr

¨obner bases. The case

of robust networks that are subject to link failure is treated in Section V. The main surprising result is that robust multicast is achievable with static network coding. II. P

ROBLEMFORMULATION

A communication network is a collection of directed links connecting transmitters, switches, and receivers. The goal of this section is to give a succinct formulation of the network communication problem of interest in this paper. A network may be represented by a directed graphG=(V,E)with a vertex setVand an edge setE?V×V. Edges (links) are denoted by round brackets(v 1 ,v 2 )?Eand assumed to be di- rected. Theheadandtailof an edgee=(v ? ,v)are denoted by v=head(e)andv ? =tail(e).

We defineΓ

I (v)as the set of edges that end at a vertex v?VandΓ O (v)as the set of edges originating atv.For- mally, we haveΓ I (v)={e?E:head(e)=v},Γ O (v)= {e?E:tail(e)=v}.Thein-degreeδ I (v)ofvis defined asδ I (v)=|Γ I (v)|while theout-degreeδ O (v)is defined as δ O (v)=|Γ O (v)|.A network is calledcyclicif it contains directed cycles, i.e. there exists a sequence of edges(v 0 ,v 1 ),(v 1 ,v 2 ),...,(v n ,v 0 ) inG. A network is calledacyclicif it does not contain directed cycles. To each linke?Ewe associate a non-negative number

C(e), called the capacity ofe.

LetX(v)={X(v,1),X(v,2),...,X(v,μ(v))}be a col-

lection ofμ(v)discrete random processes that are observable at nodev. We want to allow communication between se- lected nodes in the network, i.e. we want to replicate, by means of the network, a subset of the random processes in

X(v)at some different nodev

? .Wedefine aconnection cas a triple(v,v ? ,X(v,v ? ))?V×V×P X(v) , where P X(v) denotes the power set ofX(v).TherateR(c)of a connectionc=(v,v ? ,X(v,v ? ))is defined asR(c)=? i:X(v,i)?X(v,v ? )

H(X(v,i)), whereH(X)is the entropy rate

of a random processX.

Given a connectionc=(v,v

? ,X(v,v ? )), we callvasource andv ? asink ofcand writev=source(c)andv ? =sink(c).For notational convenience we will always assume that source(c)?= sink(c).

A nodevcan send information through a linke=(v,u)

originating atvat a rate of at mostC(e)bits per time unit. The random process transmitted through linkeis denoted by Y(e). In addition to the random processes inX(v), nodevcan observe random processesY(e ? )for alle ? inΓ I (v). In general the random processY(e)transmitted through linke=(v,u)? Γ O (v)will be a function of bothX(v)andY(e ? )ife ? is in Γ I (v). Ifvis the sink of any connectionc, the collection ofν(v) random processesZ(v)={Z(v,1),Z(v,2),...,Z(v,ν(v))} denotes the output atv=sink(c). A connectionc= (v,v ? ,X(v,v ? ))is established successfully if a (possibly de- layed) copy ofX(v,v ? )is a subset ofZ(v ? ). Let a networkGbe given together with a setCof desired connections. One of the fundamental questions of network in- formation theory is under which conditions a given communi- cation scenario is admissible. We make some simplifying as- sumptions:

1)ThecapacityofanylinkinGisaconstant, e.g. onebitper

time unit.This is an assumption that can be satisfied to an arbitrary degree of accuracy. If the capacity exceeds one bit per time unit, we model this as parallel edges with unit capacity. Fractional capacities can be well approximated by choosing the time unit large enough.

2)Each link in the communication network has the same de-

lay. Wewillallowforthecaseofzerodelayinwhichcase we call the networkdelay-free. We will always assume that delay-free networks are acyclic in order to avoid sta- bility problems.

3)Random processesX(v,l),l?{1,2,...,μ(v)}are in-

dependent and have a constant and integral entropy rate of, e.g., one bit per unit time. The unit time is chosen to equal the time unit in the definition of link capac- ity. This implies that the rateR(c)of any connection c=(v,v ? ,X(v,v ? ))is an integer equal to|X(v,v ? )|. This assumption can be satisfied with arbitrary accuracy by letting the time basis be large enough and by model-

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

ing a source of larger entropy rate as a number of parallel sources.

4)The random processesX(v,l)are independent for differ-

entv.This assumption reflects the nature of a communi- cation network. In particular, information that is injected into the network at different locations is assumed inde- pendent. In addition to the above constraints, we assume that commu- nication in the network is performed by transmission of vectors (symbols) of bits. The length of the vectors is equal in all trans- missions and we assume that all links are synchronized with respect to the symbol timing. Any binary vector of lengthmcan be interpreted as an el- ement inF 2 m,thefinitefield with2 m elements. The random processesX(v,l),Y(e)andZ(v,l)can hence be modeled as discrete processesX(v,l)={X 0 (v,l),X 1 (v,l),...},Y(e)= {Y 0 (e),Y 1 (e),...}andZ(v,l)={Z 0 (v,l),Z 1 (v,l),...}, that consist of a sequence of symbols fromF 2 m. We have the following definition of a delay-free (and hence by assumption acyclic)F 2 m-linear communication network, cf. [4]. Definition 1LetG=(V,E)be a delay-free communication network. We say thatGis aF 2 m-linear network, if for all links, the random processY(e)on a linke=(v,u)?Esatisfies Y(e)=

μ(v)

? l=1 α e,l

X(v,l)+?

e ? :head(e ? )=tail(e) β e ? ,e Y(e ? ), where theα e,l andβ e ? ,e are elements ofF 2 m. Definition 1 is concerned with the formation of random pro- cesses that are transmitted on the links of the network. It is pos- sible to consider time-varying coefficientsα e,l andβ e ? ,e and we call the networktime-invariant ortime varyingdepending on this choice. The outputZ(v,l)at any nodevis formed from the random processesY(e)fore?Γ I (v). It will be sufficient for the pur- pose of this paper to restrict ourselves to the case where the Z(v,l)are also linear combinations of theY(e), i.e.

Z(v,j)=?

e ? :head(e ? )=v ε e ? ,j Y(e ? ).(1) where the coefficientsε e ? ,j are elements ofF 2 m. Indeed, we will prove that it suffices to consider the formation of the

Z(v,j)by linear functions ofY(e)fore?Γ

I (v). We emphasize that we can freely choosemand thefieldF 2 m containing the constantsα e,l ,β e ? ,e , andε e ? ,j . In particular, we frequently choose to consider thealgebraic closure¯FofF 2 , which is defined as the union of all possible algebraic exten- sions ofF 2 . Once wefind suitable coefficients in¯Fit is clear that these coefficients also lie in afinite extension ofF 2 . For a given networkGand a given set of connectionsC,we formally define a network coding problem as a pair(G,C).The problem is to give algebraic conditions under which a set of de- sired connections is feasible. This is equivalent tofinding ele- mentsα e,l ,β e ? ,e , andε e ? ,j in a suitably chosenfieldF 2 msuch that all desired connections can be accommodated by the net- work. Such a set of numbersα e,l ,β e ? ,e , andε e ? ,j will be calledasolutionto the network coding problem(G,C). If a solution exists the network coding problem will be calledsolvable.The solution is time-invariant (time-varying) if theα e,l ,β e ? ,e , and ε e ? ,j are independent (dependent) of the time. We also consider the case of networks that suffer from link failures. Link failures are not assumed to be ergodic processes and we assume that a link either is working perfectly or is ef- fectively deleted from the network. A link failure pattern can be identified with binary vectorsfof length|E|such that each position infis associated with one edge inG. If a link fails we assume that the corresponding position infequals one, other- wise the entry infcorresponding to the link equals zero. We say that a network issolvable under link failure patternf if it is solvable once the links corresponding to the support off have been deleted. While it is straightforward to investigate the solvability for a given failure pattern,finding common solutions for classes of failure patterns is a more interesting task. We say that a network solution isstatic under a setFof link failure pattern, if the solution for the network under any link failure patternf?Fis the projection of the solution in the failure free case. Static solutions are particularly desirable becausei) no new solution has to be found and distributed in the network if a failure patternf?Foccurs,ii)the individual nodes in the network can be oblivious to the failure pattern, i.e. the basic operation performed at a node in the network are independent of the particular error pattern.

III. A

LGEBRAIC FORMULATION

Inthissectionwewilldevelopsomeofthealgebraicconcepts used throughout this paper. For the reader"s convenience we will follow a simple example of a point-to-point connection in the communication network given in Figure 2a. vv v v 4 13 2 vv v v 4 13 2

X(v,1)

X(v,2)

X(v,3)Z(vÕ,1)

Z(vÕ,2)

Z(vÕ,3)a) b)

e e eee ee 1 4 32
65
7 Figure 2a) A point-to-point connection in a simple net- work; b) The same network with nodes representing the random processes to be transmitted in the network.

We begin by considering the M

IN-CUTMAX-FLOWThe-

orem. LetG=(V,E)be a communication network. Acut between a nodevandv ? is a partition of the vertex set ofGinto two classesSandS ? =V-Sof vertices such thatScon- tainsvandS ? containsv ? .ThevalueV(S)of the cut is defined asV(S)=? edges fromStoS ?

C(e).The famous MIN-CUT

MAX-FLOWTheorem can be formulated as:

Theorem 1Let a network with a single source and a sin- gle sink be given, i.e. the only desired connection isc= (v,v ? ,X(v,v ? )). The network problem is solvable if and only if the rate of the connectionR(c)is less than or equal to the minimum value of all cuts betweenvandv ? .

ProofSee [5].

TheFord-Fulkersonlabelingalgorithmgivesawaytofinding a solution for point-to-point connections provided a network is

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

solvable. The algorithm is graph theoretic andfinds a solution such that all parametersα e,l andβ e ? ,e in Definition 1 are either zero or one. While the Ford-Fulkerson labeling algorithm provides an el- egant solution for point-to-point connections, the technique is not powerful enough to handle more involved communications scenarios. Intheremainderofthissectionwedevelopsomethe- ory and notation necessary for more complex setups. Wefirst consider a point-to-point setup. Let nodevbe the only source in the network. We letx =(X(v,1),X(v,2),...,X(v,μ(v))) denote the vector of input processes observed atv.Sim- ilarly letv ? be the only sink node in a network. We let z =(Z(v ? ,1),Z(v ? ,2),...,Z(v ? ,ν(v ? )))be the vector of out- put processes. The most important consequence of consider- ing anF 2 mlinearnetwork is that we can give atransfer matrix describing the relationship between an input vectorx and an output vectorz .LetMbe the system transfer matrix of a net- work with inputx and outputz, i.e.z=x".Forafixed set of coefficientsα e,l ,β e ? ,e , andε e ? ,j ,Mis a matrix whose coefficients are elements in thefieldF 2 mof polynomials inD for cycle-free networks or thefieldF 2 m(D)of rational func- tions overF 2 m. In our case, we go a step further and con- sider the coefficients as indeterminate variables. Hence, we consider the elements of matrixMas polynomials over the ringF 2 [...,α e,l ,...,β e ? ,e ,...,ε e ? ,j ,...]of polynomials in the variablesα e,l ,β e ? ,e , andε e ? ,j .

Example 1We consider the network of Figure 2.

We have the following set of equations governing the param- etersα e,l ,β e ? ,e andε e,j and the random processes in the net- work Y(e1)=αe1,1X(v,1) +αe1,2X(v,2) +αe1,3X(v,3) Y(e2)=αe2,1X(v,1) +αe2,2X(v,2) +αe2,3X(v,3) Y(e3)=αe3,1X(v,1) +αe3,2X(v,2) +αe3,3X(v,3)

Y(e4)=βe1,e4Y(e1)+βe2,e4Y(e2)

Y(e5)=βe1,e5Y(e1)+βe2,e5Y(e2)

Y(e6)=βe3,e6Y(e3)+βe4,e6Y(e4)

Y(e7)=βe3,e7Y(e3)+βe4,e7Y(e4)

Z(v?,1) =εe5,1Y(e5)+εe6,1Y(e6)+εe7,1Y(e7) Z(v?,2) =εe5,2Y(e5)+εe6,2Y(e6)+εe7,2Y(e7) Z(v?,3) =εe5,3Y(e5)+εe6,3Y(e6)+εe7,3Y(e7) It is straightforward to compute the transfer matrix describingthe relationship betweenx andz. In particular, let matricesAandBbe defined as A=( ( (α e1,1αe2,1αe3,1

αe1,2αe2,2αe3,2

αe1,3αe2,3αe3,3)

) ) B=( ( (ε e5,1εe5,2εe5,3

εe6,1εe6,2εe6,3

εe7,1εe7,2εe7,3)

) ).

The system matrixMis found to equal

M=A( ( (β

e1,e5βe1,e4βe4,e6βe1,e4βe4,e7βe2,e5βe2,e4βe4,e6βe2,e4βe4,e70βe3,e6βe3,e6)

) )BT.

The determinant of matrixMequals det(M)=

det(A)(β e1,e5 β e2,e4 -β e2,e5 β e1,e5 )(β e4,e6 β e3,e7 -β e4,e7 β e3,e6 ) det(B). We can choose parameters in an extensionfieldF m2 so that the determinant ofMis nonzero overF 2 m. Hence we

can chooseAas the identity matrix andBso that the overallmatrixMis also an identity matrix. For example the solution

found by the Ford-Fulkerson algorithm would be equivalent toβ e1,e5 =β e2,e4 =β e4,e6 =β e3,e7 =1while all other parameters of typeβ e ? ,e are chosen to equal zero. Clearly a point to point communication betweenvandv ? is possible at a rate of three bits per unit time. We note that there exists an infinite number of solutions to the posed networking problem, namely all assignments to parametersβ e ? ,e which render a nonzero determinant of the transfer matrixM. Inspecting Example 1 we see that the crucial prop- erty of the network is that the equation(β e1,e5 β e2,e4 - β e2,e5 β e1,e5 )(β e4,e6 β e3,e7 -β e4,e7 β e3,e6 )admitted a choice of variables so that the polynomial didnotevaluate to zero. The following simple lemma is the foundation of most existence proofs given in this paper:

Lemma 1LetF[X

1 ,X 2 ,...,X n ]be the ring of polynomi- als over an infinitefieldFin variablesX 1 ,X 2 ,...,X n .For any non-zero elementf?F[X 1 ,X 2 ,...,X n ]there exists an infinite set ofn-tuples(x 1 ,x 2 ,...,x n )?F n such that f(x 1 ,x 2 ,...,x n )?=0. ProofThe proof is by induction over the number of variables and the fact thatFis an infinitefield. The following theorem makes the connection between the network transfer matrixM(an algebraic quantity), and the M

IN-CUTMAX-FLOWTheorem (a graph-theoretic tool):

Theorem2Letalinearnetworkbegiven. Thefollowingthree statements are equivalent:

1) A point-to-point connectionc=(v,v

? ,X(v,v ? ))is pos- sible.

2) The M

IN-CUTMAX-FLOWbound (Theorem III) is sat-

isfied for a rateR(c).

3) The determinant of theR(c)×R(c)transfer matrixMis

nonzero over the ring F 2 [...,α e,l ,...,β e ? ,e ,...,ε e ? ,j ,...]. ProofMost of the theorem is a direct consequence of the M IN-CUTMAX-FLOWTheorem. In particular 1) and 2) are equivalent by this theorem. We show the equivalence of 1) and

3): The Ford-Fulkerson algorithm implies that a solution to the

linear network coding problem exists. Choosing this solution for the parameters of the linear network coding problem yields a solution such thatMis the identity matrix and hence the de- terminant ofMoverF 2 [...,α e,l ,...,β e ? ,e ,...,ε e ? ,j ,...]does not vanish identically. Conversely, if the determinant ofMis nonzero overF 2 [...,α e,l ,...,β e ? ,e ,...,ε e ? ,j ,...]we can in- vert matrixMby choosing parametersε e ? ,l accordingly. From Lemma 1 we know that we can choose the parameters as to make this determinant non-zero. Hence 3) implies 1) and the equivalences are shown. From Example 1, Lemma 1, and Theorem 2, we conclude that studying the feasibility of connections in a linear network scenario is equivalent to studying the properties of solutions to polynomialequationsoverthefield¯F, calledalgebraicvarieties. We will have to extend the consideredfields for cyclic networks and networks with delay. Note that it is sufficient in Theorem

2 to consider expressions overfields offixed characteristic. In

other words, if a solution to a point-to-point network problem exists, there does also exist a solution restricted to the algebraic closure ofF 2 . There is no need or advantage to considerfields

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

of other characteristic. In the following section, we investigate the structure of general transfer matrices and the polynomial equations to which they give rise. We may now present our representation of networks us- ing transfer matrices. In a linear communication network of

Definition 1 any nodev

i transmits, on an outgoing edge, a linear combination of the symbols observed on the incoming edges. This relationship between edges in a linear commu- nication network is the incidence structure in which we are most interested. We say that any edgee=(u,v)feeds intoedgee ? =(v,u ? )if head(e)is equal to tail(e ? ).We define the“directed labeled line graph"ofG=(V,E)as

G(V,E)with vertex setV=Eand edge setE={(e,e

? )? E 2 :head(e)=tail(e ? )}. Any edgee=(e,e ? )?Eis labeled with the corresponding labelβ e ? ,e . Figure 3 shows the directed labeled line graph of the network in Figure 2. e eee e 1 2 45
6 e 7 e 3 β

ββ

ββ

β β β e e e e e e ee 11 2 2 4 4 3 3 e e e e e e e e 5 5 6 6 7 744
Figure 3The directed labeled line graphGcorresponding to the network depicted in Figure 2a. We define the adjacency matrixFof the graphGwith ele- mentsF i,j given as F i,j =?β ei,ej head(e i )=tail(e j )

0otherwise.

Lemma 2LetFbe the adjacency matrix of the labeled line graph of a cycle-free networkG. The matrixI-Fhas a poly- nomial inverse inF 2 [...,β e ? ,e ,...]. ProofProvided the original networkGis acyclic, the graph Gis acyclic. Hence we may assume that the vertices inGare ordered according to an ancestral ordering. HenceFis a strict upper-triangular matrix and henceI-Fis invertible in thefield of definition ofF. The claim thatI-Fis invertible in the ring of polynomials rather than the corresponding quotientfield of rational functions follows from a direct back-substitution algo- rithm. In order to consider the case that a network contains multi- ple sources and sinks we considerx =(x 1 ,x 2 ,...,x μ )= (X(v 1 ,1),X(v 1 ,2),...,X(v 1 ,μ(v 1 )),X(v 2 ,1),...,X(v |V| ,

μ(v

|V| )))as the vector of input processes on all vertices inV. If a vertexvin a network is not a source node, we setμ(v)to zero.x =(x 1 ,x 2 ,...,x μ )is a vector of lengthμ=? i

μ(v

i ). Let the entries of aμ×|E|matrixAbe defined as A i,j =?α ej,l x i =X(tail(e j ),l)for somel

0otherwise.

Similarly, letz

=(z 1 ,z 2 ,...,z μ )=(Z(v 1 ,1)(D),Z(v 1 ,2), ...,Z(v 1 ,ν(v 1 )),Z(v 2 ,1),...,Z(v |V| ,ν(v |V| )))be the vec- tor of output processes. Ifv j is not a sink node of any con- nection we letν(v j )be equal to zero.zis a vector of length

ν=?

i

ν(v

i ). Let the entries of aν×|E|matrixBbe definedas B i,j =?ε ej,l z i =Z(head(e j ),l)for somel

0otherwise.

Example 2We consider the network depicted in Figure 4 a. The corresponding labeled line graph is depicted in Figure 4 b. e e e eeee v'u' u'u vu vv''vv' e v'v'' v''uv''u'a) b) vv' uu' v''

X(v,1)

X(v,2)X(v',1)

Z(u',1)

Z(u',2)

Z(u,1)ee

eee e v''u ee vv''v''u'v'v''v'u' u'u uvvv'

Figure 4a) A network with two source and two sink

nodes. b) The corresponding labeled line graph; Labels in b) are omitted for clarity. The edgee uv does not feed into any other edge and no edge feeds intoe uv , which renders an isolated vertex in the labeled line graph. We assume that the network is supposed to accommo- date two connectionsc 1 =(v,u ? ,{X(v,1),X(v,2)})and c 2 =(v ? ,u,{X(v ? ,1)}).Wefix an ordering of edges as e v,v ?,e v,v ??,e vu ,e v ? ,v ??,e v ? ,u ?,e v ?? ,u ,e v ?? ,u ?,e u ? ,u . From the or- dering of vertices(v,v ? ,v ?? ,u,u ? )the corresponding orderings of the edges inGare determined, i.e.e v,v ?? O e v,v ??? O e vu ? O e v ? ,v ??? O e v ? ,u ?? O e v ?? ,u ? O e v ?? ,u ?? O e u ? ,u ande v,v ??? I e v ? ,v ??? I e v,u ? I e v ?? ,u ? I e u ? ,u ? I e v ? ,u ?? I e v ?? ,u ? I e u ?? ,u . For this ordering the adjacency matrixFof the labeled line graphGis found to equal F=( ( ( ( ( (((((((0βev,v?,ev?,v??00βev,v?,ev?,u? 00000 00000 00000 00000 00000 00000 00000 000

βev,v??,ev??,uβev,v??,ev??,u?0

000

βev?,v??,ev??,uβev?,v??,ev??,u?0

00βev?,u?,eu?,u

000

00βev??,u?,eu?,u

000) ) ) ) ) ) ) ))))))).

Also, matricesAandBare found to equal:

A= ( ( ((α ev,v?,1αev,v??,1αev,u,10000 α ev,v?,2αev,v??,2αev,u,20000

000αv?,v??,1αv?,u?,100)

) )) and B=( ( ((00εev,u,100

0000εev?,u?,1

0000εev?,u?,2

ε ev??,u,10εeu?,u,1

0εev??,u?,10

0εev??,u?,20)

) ))) From the matricesF,AandB, we can easilyfind the transfer matrix of the overall network. Theorem 3Let a network be given with matricesA,Band

F. The transfer matrix of the network is

M=A(I-F)

-1 B T whereIis the|E|×|E|identity matrix.

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

ProofMatricesAandBdo not substantially contribute to the overall transfer matrix as they only perform a linear mixing of the input and output random processes. In order tofind the “impulse response"of the link between an input random pro- cessX(v,i)and an outputZ(v ? ,j)we have to add all gains along all paths that the random processX(v,i)can take in or- der to contribute toZ(v ? ,j). It is straightforward to verify that the path between nodes in the network are accounted for in the seriesI+F+F 2 +F 3 +....MatrixFis nilpotent and even- tually there will be aNsuch thatF N is the all zero matrix.

Hence, we can write(I-F)

-1 =(I+F+F 2 +F 3 +...).

The theorem follows.

The transfer matrixMis considered as a matrix over the ring of polynomialsF 2 [...,α e,l ,...,β e ? ,e ,...,ε(e ? ,j),...].Inthe sequel, we will use a vectorξ to denote the set of variables ...,α e,l ,...,β e ? ,e ,...,ε(e ? ,j),...and hence we considerM as matrix with elements inF 2 [ξ]. We will use the explicit form of the vectorξ only if we want to make statements about a spe- cific solution of a particular network problem(G,C). We conclude this section with a remark that it is sufficient to form the output processesZ(v,?)by a linear function of the processesY(e),e?Γ I (v). Indeed, provided a network problem is solvable, let the output processZ(v,?)be equal toψ(Y(e 1 ),Y(e 2 ),...,Y(e

δI(v)

))whereψ(·)is an arbitrary function and the edgese i are inΓ I (v).ByDefinition 1, the processesY(e)are a linear function of the input processes X(w,j). Hence, provided that the outputZ(v,?)equals any particular input, the functionψ(·)describes a vector space ho- momorphism from(Y(e 1 ),Y(e 2 ),...,Y(e

δI(v)

))toZ(v,?) for all?and henceψ(·)must be a linear function. Thus, the form of Equation (1) is no restriction on the solvability of a network coding problem. IV. D

ELAY-FREENETWORKS

Wefirst consider the multicast problem. In its simplest form the multicast problem consists of the distribution of the infor- mation generated at a single source nodevto a set of sink nodesu 1 ,u 2 ,...,u M such thatallsink nodes getallsource bits. In other words, the set of desired connections is given by {(v,u 1 ,X(v)),(v,u 2 ,X(v)),...,(v,u M ,X(v))}. Clearly, each connection(v,u i ,X(v))must satisfy the cut-set bound betweenvandu i . Ahlswede et al. [1] showed that this condi- tion is sufficient to guarantee the existence of a coding strategy that ensures the feasibility of the desired connections. Li et al. [4] showed that linear coding strategies are sufficient to achieve this goal. The following theorem recovers their result in the algebraic framework developed in the previous section.

Theorem 4Let a delay-free networkGand a

set of desired connectionsC={(v,u 1 ,X(v)), (v,u 2 ,X(v)),...,(v,u N ,X(v))}be given. The net- work problem(G,C)is solvable if and only if the M

IN-CUT

MAX-FLOWbound is satisfied for all connections inC. ProofWe have a single source in the network and, hence, we the system matrixMis a matrix with dimension|X(v)|× N|X(v)|. Moreover, by assumption and Theorem 1, each |X(v)|×|X(v)|submatrix corresponding to one connection has nonzero determinant overF 2 [ξ]. We consider the product of theNdeterminants of the|X(v)|×|X(v)|submatrices.This product is a nonzero polynomial inF(ξ ). By Lemma 1 we canfind an assignment forξ such that allNdeterminants are nonzero in ¯Fand hence that allNsubmatrices are invertible. By choosing matrixBaccordingly we can guarantee thatM is theN-fold repetition of the|X(v)|×|X(v)|unit matrix, proving the Theorem. The most important ingredient of Theorem 4 is the fact that all sink nodes get the same information. This implies that all interference between the connections can be resolved construc- tively. In other words, provided that the sink nodes know the part of the system matrix that describes their connection, the very notion of interference is moot. Another interesting aspect of this setup is that the sink nodes do not have to be aware of the topology of the network. Knowledge about the overall effects of all coding occurring in the network is sufficient to resolve their connection. We emphasize that it suffices to consider cod- ing strategies involving the algebraic closure of thefinitefield of characteristic two. In other words, if the network coding problem is solvable at all, it is also solvable for an arbitrary characteristic of the underlyingfinitefield. Also, it is solvable over essentiallyanyinfinitefield, so, e.g., also thefield of ra- tional functions in a delay parameterDwith coefficients from F 2 . The construction of special codes for the multicast network coding problem is rather easy. From the proof of Theorem 4, it is clear that we are given a polynomial inξ (the product of theNdeterminants) and we mustfind a point that doesnotlie on the algebraic variety cut out by this polynomial. A simple algorithmtofindavectora suchthatF(a)?=0forapolynomial

FisAlgorithm 1:

Input: A polynomialFin indeterminatesξ

1 ,ξ 2 ,...,ξ n ,in- tegers:i=1,t=1

Iteration:

1) Find the maximal degreeδofFin any variable

ξ j and letibe the smallest number such that 2 i >δ.

2) Find an elementa

t inF 2 isuch that

F(ξ

)|

ξt=at

? =0and letF←F(ξ)|

ξt=at

.

3) Ift=nthen halt, elset←t+1, goto 2).

Output:(a

1 ,a 2 ,...,a n ).

The determination of the coefficientsa

i renders a network such that all the transfer matrices between the single source and any sink node are invertible. Choosing the matrixBso that all these matrices are the identity matrix solves the multicast network problem. Algorithm 1 provides a bound on the degree of the extension ofF 2 we need to consider. Theorem 5Let a delay-free communication networkGand a solvable multicast network problem be given with one source andNreceivers. LetFbe the product of the determinants of the transfer matrices for the individual connections and letδbe the maximal degree ofFwith respect to any variableξ i . There exists a solution to the multicast network problem inF 2 i, where iis the smallest number such that2 i >δ. Algorithm 1finds such a solution. ProofWe only have to show that Algorithm 1 indeed termi- nates properly. Also it suffices to show that we canfindξ 1 in F 2 ias the rest of the proof follows by induction. We considerF

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

as a polynomial inξ 2 ,ξ 3 ,...,ξ n with coefficients fromF 2 [ξ 1 ]. By the definition ofδthe coefficients ofFare not divisible by ξ 2 i 1 -ξ 1 and hence there exists an elementa 1 ?F 2 isuch that on substitutinga 1 forξ 1 at least one of the coefficients evaluates to a nonzero element ofF 2 i. Substitutinga 1 forξ 1 and repeating the procedure yields the desired solution. A simple general upper bound on the necessary degree of the extensionfield for the multicast scenario is given in the follow- ing corollary: Corollary 1Let a delay-free communication networkGand a solvable multicast network problem be given with one source andNreceivers. LetRbe the rate at which the source gener- ates information. There exists a solution to the network coding problem in afinitefieldF 2 mwithm??log 2 (NR+1)?.

ProofEach entry in the matrix(I-F)

-1 has degree at most one in any variable. Hence, the degree of each variable in the determinant of a particular transfer matrix is at mostR. Hence the relevant polynomial has degree at mostNRin any variable. The situation is much changed if we consider the general net- work coding problem, i.e. we are given a networkGand an ar- bitrary set of connections,C. To accommodate the desired con- nections, we have to ensure thati)theM

IN-CUTMAX-FLOW

bound is satisfied for every single connection andii) there is no disturbing interference from other connections. vv u u 12 w we e e e e ee 1 4 ee e e e ee e 3 16 5 e 2 ξ ξ

ξξξ

ξ

ξξ

1 ee a) ξ 2 23
4

ξ47

5 67
8 9 1 098
1 5 8 9 22
63
1 7b)

Figure 5a) A network with two source and two sink

nodes. b) The corresponding labeled line graph The following example outlines the basic requirements for the general case: Example 3Let the networkGbe given as depicted in Fig- ure 5a). The corresponding labeled line graph is given in Figure 5 b). We assume that we want to accommodate two connections in the network, i.e.C={(v 1 ,u 1 ,{X(v 1 ,1), X(v 1 ,2)}),(v 2 ,u 2 ,{X(v 2 ,1),X(v 2 ,2)})}. Vectorsxandz are given asx=(X(v 1 ,1),X(v 1 ,2),X(v 2 ,1),X(v 2 ,2))and z =(Z(u 1 ,1),Z(u 1 ,2),Z(u 2 ,1),Z(u 2 ,2)). It is straightfor- ward to check that the system matrixMsuch thatz =x" holds, is given as M=( ( ( ( ( ( ( ((ξ

11ξ12ξ1300

ξ

14ξ15ξ1600

000ξ17ξ18

000ξ19ξ20)

) ) ) ) ) ) )) ( ( (((((((((((0ξ1ξ1ξ4ξ9ξ1ξ4ξ10

10ξ3ξ9ξ3ξ10

00ξ7ξ8

0ξ2ξ2ξ4ξ9ξ2ξ4ξ10

00ξ5ξ6)

) )))))))))))( ( ( ( ( ( ( ((ξ

21ξ2200

ξ

23ξ2400

00ξ25ξ26

00ξ27ξ28)

) ) ) ) ) ) )).

We can writeMas a block matrix

M=?M 1,1 M 1,2 M 2,1 M 2,2 ?

WhereM

1,1 denotes the transfer matrix between (X(v 1 ,1),X(v 1 ,2))and(Z(u 1 ,1),Z(u 1 ,2)),M 1,2 de- notes the transfer matrix between(X(v 1 ,1),X(v 1 ,2))and (Z(u 2 ,1),Z(u 2 ,2)),etc. It is easy to see that the network problem(G,C)is solvable if and only if the determinants ofM 1,1 andM 2,2 are unequal to zero, while the matricesM 1,2 andM 2,1 are all zero matri- ces. Note that the determinant ofM 1,1 andM 2,2 is nonzero overF 2 [ξ]if and only if the MIN-CUTMAX-FLOWbound is satisfied. Indeed, we have det(M1,1)=(ξ11ξ15-ξ12ξ14)ξ1(ξ21ξ24-ξ22ξ23) and det(M2,2)=ξ2ξ4(ξ17ξ20-ξ18ξ19)(ξ9ξ6-ξ5ξ10)(ξ25ξ28-ξ26ξ27). It is interesting to note that the MIN-CUTMAX-FLOWcon- dition is satisfied for each connection individually but also for the cut between both sources and both sinks. This condition is guaranteed by edgee 6 . If edgee 6 is removed the determinant of the transfer matrix would vanish identically, which indicates a violation of the M

IN-CUTMAX-FLOWcondition applied to

cuts separatingv 1 andv 2 fromu 1 andu 2 .

In order to satisfyM

2,1 =0we have to chooseξ 2 =0which implies that det(M 2,2 )equals zero. Hence, we cannot satisfy the requirements that det(M 2,2 )?=0andM 2,1 =0simultane- ously and hence, the network problem(G,C)is not solvable. It is worthwhile pointing out that this non-solvability of the net- work coding problem is pertinent foranycoding strategy and is not a shortcoming of linear network coding. As before, letxdenote the vector of input processes and let z denote a vector of output processes. We consider the transfer matrix in a block form asM={M i,j }such thatM i,j is the submatrix ofMthat describes the transfer matrix between the input processes atv i and the output processes atv j . The follow- ing theorem states a succinct condition under which a network problem(G,C)is solvable.

Theorem 6 -GeneralizedM

IN-CUTMAX-FLOWCondition

Let an acyclic, delay-free linear network problem(G,C)be given and letM={M i,j }be the corresponding transfer ma- trix relating the set of input nodes to the set of output nodes. The network problem is solvable if and only if there exists an assignment of numbers toξ such that 1)M i,j =0for all pairs(v i ,v j )of vertices such that (v i ,v j ,X(v i ,v j ))??C.

2) IfCcontains the connections(v

i1 ,v j ,X(v i1 ,v j )), (v i2 ,v j ,X(v i2 ,v j )),...,(v i ? ,v j ,X(v i ? ,v j ))the sub- matrix?M Ti 1,j M Ti 2,j ,...,M Ti ? ,j ?is a non singularν(v j )×

ν(v

j )matrix.. ProofAssume the conditions of the theorem are met and as- sume the network operates with the corresponding assignment

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

of numbers toξ. Condition 1) ensures that there is no disturbing interference at the sink nodes. Also, any sink nodev j can invert the transfer matrix?M Ti 1,j M Ti 2,j ,...,M Ti ? ,j ?and hence recover the sent information. Conversely, assume that either of the conditions is not satis- fied. If condition 1) is not satisfied, then the collection of ran- dom processes observed on the incoming edges ofv j is a super- position of desired information and interference. Moreover, the sink nodev j has no possibility to distinguish interference from desired information and hence, the desired processes cannot be reliably reproduced atv j . Condition 2) is equivalent to a MIN- C UTMAX-FLOWcondition, which clearly has to be satisfied if the network problem is solvable. Theorem 6 gives a succinct condition for the satisfiability of a network problem. However, checking the two conditions is a tedious task as we have tofind a solution, i.e. an assignment to numberξ that exhibits the desired properties. Nevertheless, the theory of Gr

¨obner bases provides a structured approach to

this problem. If we want to check if a given network problem is solvable without necessarily having to give a solution we can give a procedure that is guaranteed to reveal the solvability of the network problem. We will sketch this approach in the re- mainder of this section. However, an in depth treatment of the involved techniques lies outside the scope of this paper. Letf 1 (ξ),f 2 (ξ),...,f K (ξ),f i ?F 2 [ξ]denote all the en- tries inMthat have to evaluate to zero in order to satisfy thefirst condition of Theorem 6. We consider the ideal gen- erated byf 1 (ξ),f 2 (ξ),...,f K (ξ),f i ?F 2 [ξ]and denote this ideal byI(f 1 ,f 2 ,...,f K ). From the Hilbert Nullstel- lensatz [6] we know that this ideal is a proper ideal ofF 2 [ξ] if and only if we canfind an assignment of numbers forξ such that we can satisfy thefirst condition of Theorem 6. In order to satisfy the second condition of the theorem we let g 1 (ξ),g 2 (ξ),...,g L (ξ)denote the determinants of theν(v j )×

ν(v

j )matrices that have to be non-zero. Next, we introduce a newvariableξ 0 andconsiderthefunctionξ 0 ? L i=1 g i (ξ)-1.We call the idealI(f 1 (ξ),f 2 (ξ),...,f K (ξ),1-ξ 0 ? L i=1 g(ξ))the ideal of the linear network problem denoted by Ideal((G,C)). The algebraic variety associated with Ideal((G,C))is de- noted Var((G,C)),Var((G,C)) ={(a 1 ,a 2 ,...,a n )?¯F n : f(a 1 ,a 2 ,...,a n )=0?f?Ideal((G,C))}. Theorem 6Let a linear network problem(G,C)be given. The network problem is solvable if and only if Var((G,C)is nonempty and hence, the ideal Ideal((G,C))is a proper ideal of¯F[ξ 0 ,ξ], i.e Ideal((G,C))?F 2 [ξ 0 ,ξ]. ProofAssumefirst that the ideal Ideal((G,C))is a proper ideal ofF 2 [ξ 0 ,ξ]. Hilbert"s Nullstellensatz implies that the va- riety Var((G,C))of points where all elements of Ideal((G,C)) vanish is non-empty. Hence, there exists an assignment toξ 0 andξsuch that condition 1 of Theorem 6 is satisfied. More- over, it should be noted that for all solutions in the variety

Var((G,C))we haveξ

0 ? =0and? L i=1 g(ξ)?=0as otherwise

1is in the generating set of the ideal and hence Ideal((G,C))

is identified withF 2 [ξ 0 ,ξ]. Hence, condition 2 of Theorem 5 is satisfied and any element ofVis a solution of the linear net- work problem.

Conversely, assume that Ideal((G,C)) =F

2 [ξ 0 ,ξ]. Hence

the variety Var((G,C))is empty and there is no solution whichsatisfies the required conditions. Indeed, by choosing a proper

value forξ 0 any solution to the network coding problem would immediately give rise to a non-empty variety Var((G,C)). Using Theorem 6 we have reduced the problem of deciding the solvability of a linear network problem to the problem of deciding if a variety is empty or not. We can decide this prob- lem using Buchberger"s algorithm [7] to compute a Gr¨obner basis for the ideal Ideal((G,C)). A treatment of the neces- sary Gr ¨obner bases background exceeds the scope of this pa- per and we refer to Cox et al. [7] for a thorough treatment of G ¨obner bases and Buchberger"s algorithm. We only note that it is well known that, in general, the complexity of Gr

¨obner ba-

sis computations is not polynomially bounded in the number of variables. Nevertheless, commercial mathematics software rou- tinely solves large Gr

¨obner basis computations. A careful study

of the structure of Ideal((G,C)) =F 2 [ξ 0 ,ξ]as obtained from network problems as well as optimizing the computation of a Gr ¨obner basis for the ideal of a linear network problem is inter- esting and promises future tasks with much room for deriving efficient algorithms to decide network problems. V. R

OBUSTNETWORKS

An additional component to the problem of network coding is added if we assume that links in a network may fail. The question then becomes under which failure pattern a successful network usage is still guaranteed. Lete=(v,u)be a fail- ing link. We assume that any sink node that can be reached fromuvia a directed path can be notified of the failure of link e. However, no other nodes are being notified of the link fail- ure. Given a networkGand a link failure patternf?Fit is straightforward to consider the networkG f that is obtained by deleting the failing links and applying the results of the previ- ous section to this setup. We are interested in static solutions where the network is oblivious to the particular failure pattern. The idea is that each node transmits on outgoing edges a func- tion of the observed random processes, such that the functions are independent of the current failure pattern. Here we use the convention that the constant 0 is observed on failing links. We can achieve the effect of a failing linkeby setting parameters β e ? ,e ,β e,e ??andα e,? to zero for alle ? ,e ?? and?, which effec- tively removes the influence of any random process transmitted on edgee.LetM[ξ ]be the system matrix for a particular linear network coding problem. Moreover, let the set of parameters ξ i that are identified withβ e ? ,e ,β e,e ??andα e,? for alle ? ,e ?? and ?be denoted asB e , i.e.B e ={ξ i :ξ i is identified withβ e ? ,e ,β e,e ??orα e,? for anye ? ,e ?? and?}. Network recovery under non-ergodic failures has until now generally been considered in terms of routing, except for a very special case of coding for network recovery presented in [8]. For any particular link failure patternfwe defineB(f)as

B(f)=?

e:fe=1 B e The following lemma makes the connection between the net- work problem without and with a link failure patternf:

Lemma 3LetM[ξ

]be the system matrix of a linear network coding problem and letfbe a particular link failure pattern.

The system matrixM

f [ξ]for the networkG f obtained by delet- ing the failing links is obtained by replacing allξ i ?B(f)with zero, i.e.M f [ξ]=M[ξ]|

ξi=0:ξi?B(f)

.

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002

ProofThe effect of a failed link can be modeled by the fact that no information about a random process is either fed into a failed link or is fed from the failed link into another link. Set- ting the coefficientsξ i ?B(f)to zero is compliant with the assumption that a constant 0 is observed on failed nodes. LetFbe the set of failure patternsfsuch that the network coding problem(G f ,C)is solvable. For the multicast scenario we have the following surprising result: Theorem 7Let a linear networkGand a set of connections

C={(v,u

1 ,X(v)),(v,u 2 ,X(v)),...,(v,u N ,X(v))}be given. There exists a common static solution to the network problems(G f ,C)for allfinF. ProofLetfbe any particular failure pattern that renders a solvable network. Letg f,i (ξ)be the determinant of the trans- fer matrix corresponding to connection(v,u i ,X(v)). We con- sider the productg(ξ )=? N i=1 ? f?F g f,i (ξ). By Lemma 1 we canfind an assignment of numbers toξ such thatg(ξ)and hence every single determinantg f,i (ξ)evaluates to a non zero value. It follows that regardless of error pattern inFthe basic multicast requirements are satisfied. Theorem 7 makes very robust multicast scenarios possible - inasensethemulticastcanbeorganizedasrobustlyaspossible. In formulating the following theorem, the price we have to pay for this exceptional robustness becomes apparent. Theorem 8Let a delay-free communication networkGand a solvable multicast network problem be given with one source andNreceivers. Moreover, letFbe the set of failure pat- terns from which we want to recover. LetRbe the rate at which the source generates information. There exists a solu- tion to the network coding problem in afinitefieldF 2 mwith m??log 2 (|F|NR+1)?. ProofLetFbe the product of the determinants of the transfer matrices for the individual connections and letδbe the maximal degree ofFwith respect to any variableξ i . Following the proof of Corollary IV we know thatδis bounded byR. Altogether we have to consider the product ofN|F|determinants. The theorem follows. Thequestionarisesifsimilarstatementsaboutrobustnesscan be derived for a general network problem. The following ex- ample shows that simple network coding problems exist that do not allow a static solution for different failure patterns inF. We consider the networkGdepicted in Figure 6. Let the ca- pacity of all edges be one bit per time unit and let the set of desired connections be given asC={(v 1 ,u 1 ,X(v 1 )),v 2 ,u 2 , X(v 2 )}with|X(v 1 )|=|X(v 1 )|=1. The example is small enough that it is possible to verify directly thati) the network coding problem is solvable for any single failure involving a single link andii) there does not exist a static solution for any (linear or non-linear) coding strategy.

ξξ

ξ ξ ee e e ee 14 5 61
2 3 423
vv uu v e e ee 3 34
e e 5 62
112
1 2a) b) Figure 6a) A communication network with two source nodes(v 1 ,v 2 )and two sink nodes(u 1 ,u 2 ). b) The corre- sponding labeled line graphVI. C

ONCLUSIONS

We have presented an algebraic framework for network ca- pacity using linear codes. While we have considered acyclic delay-free networks, our results can be generalized to networks with delays, including cyclic networks with delays. Our results show that the algebraic approach is a very powerful means of establishing the capacity of networks. Non-linear codes may be useful for certain non-multicast cases, but are beyond the scope of this paper. Some aspects of non-linear codes can be found in [9], [10]. These results open many roads for further research. One di- rection is to consider, over many random networks, the benefits of coding over routing. Such results may indicate to what extent routing may be optimal or near-optimal for achieving network capacity. Another direction is considering the intrinsic require- ments, in terms of network management, for network robust- ness. Our results show that no network management overhead isrequiredformulticastconnections, butthatachangeofcodes, which needs to be initiated by network management, may be necessary in more general cases. Relating network manage- ment to the changing of codes may lead to determining the minimum number of bits required for network management to respond to a failure. R

EFERENCES

[1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung,“Network Infor- mation Flow",IEEE Transactions on Information Theory, vol. 46, pp.

1204-1216, 2000

[2] J.W. Byers, M. Luby, M. Mitzenmacher,“Accessing multiple mirror sites in parallel: using Tornado codes to speed up downloads", INFOCOM 1999.
[3] R. Koetter, M. M ´edard,“An Algebriac Approach to Network Coding", International Symposium on Information Theory 2001 [4] S.-Y. R. Li, and R. W. Yeung,“Linear Network Coding", preprint, 1999 [5] R. Diestel,Graph theory, Graduate texts in mathematics, Springer, 2000 [6] Fulton,Algebraic Curves, Benjamin Cummings Publishing Company,

California, 1969

[7] D. Cox, J. Little, and D. O"Shea,Ideals, Varieties, and Algorithms

Springer, 1992

[8] E. Ayanoglu, C.-L. I, R.D. Gitlin and J. E. Mazo,"Diversity Coding: Us- ing Error Control for Self-healing in Communication Networks", INFO- COM"90, Ninth Annual Joint Conference of the IEEE Computer and

Communication Societies, vol.1 pp. 95 -104, 1990

[9] R.W. Yeung and B. Zhang,"Distributed Source Coding for Satellite Com- munications",IEEE Transactions on Information Theory, vol. 45, pp.

111-1120, May 1999

[10] R.W. Yeung,A First Course in Information Theory, to be published by

Kluwer Academic Press

0-7803-7477-0/02/$17.00 (C) 2002 IEEEIEEE INFOCOM 2002