Improving the Multicommodity Flow Rates with Network Codes for Two Sources
- 格式：pdf
- 大小：491.32 KB
- 文档页数：11
Improving the Multicommodity Flow Rates with Network Codes for Two SourcesElona Erez,Member,IEEE,and Meir Feder,Fellow,IEEEAbstract—In this work we introduce a construction and anal-ysis of network codes for two sources.The region of achievable rates for this problem is still unknown.The scheme we suggest is based on modifying the multicommodityflow solution and thus improving the achievable rate region,w.r.t the uncoded case.The similarity to theflow problem allows our method to be implemented distributively.We show how the construction algorithm can be combined with distributed backpressure routing algorithms for wireless ad-hoc networks.For both the non-distributed case and the distributed case,the computational complexity of our algorithm for network coding is comparable to that of the parallel multicommodityflow problem.We provide non trivial upper and lower bounds on the performance of our scheme,using random coding techniques.Index Terms—Multicommodityflow,Backpressure,Dis-tributed network coding,Multiple unicast,Ad-hoc networksI.I NTRODUCTIONM OST literature on network coding focuses on multi-cast where bounds on achievable rates and codes that achieve these bounds were found.The general case of multiple sources seems to be much more complicated.A classification complexity of network coding problems was carried out in [1],where it was shown that some of the non-multicast cases are NP-hard.For this category linear codes cannot achieve in general the optimal rates.It was further shown in[2]that vector linear codes of anyfinite dimension cannot achieve optimal rates for some networks.Koetter and M´e dard[3] gave an algebraic formulation of linear network codes with multiple sources.Yeung[4,Chapter15]gave information-theoretic inner and outer bounds to the rate region in the general case of acyclic networks with multiple sources.This result is extended in[5]to zero-error network codes.While these schemes are elegant and insightful,the computational cost is high for practical implementation.In multiple unicast for d users,source s i transmits to sink t i at rate R i.When no codes are employed,the problem is termed the multicommodityflow,which can be solved using linear programming.In[6]it was shown that the problem can be implemented distributively.In[7],which considers network coding for multiple unicast,the operations are restricted to binary XOR.The scheme is systematic but the computational complexity is high in comparison to the multicommodityflow. This approach was solved distributively in[8],[9].A different approach in the wireless setting is given in[10]and is again limited to XOR operations,which may lead to throughput loss. Manuscript received31July2008;revised20February2009.Elona Erez is with Department of of Electrical Engineering,Yale University, New Haven,CT,06511,USA(e-mail:elona.erez@).Meir Feder is with the Department of Electrical Engineering–Systems, Fleischman Faculty of Engineering,Tel-Aviv University,Tel-Aviv69978, Israel(e-mail:meir@eng.tau.ac.il).Digital Object Identifier10.1109/JSAC.2009.090620.In[11]the problem is formulated asfinding the stable set ofthe conflict hypergraph of the network.However,the size of the conflict graph grows exponentially andfinding the stableset may be difficult.We provide a code construction that improves the rate re-gion of multicommodityflows,with computational complexity comparable to that of the multicommodityflow construction.We focus on multiple unicast with two users.We formulateour method as a linear programming that is closely related to theflow problem.The similarity to theflow problem allowsour method to be implemented distributively,analogously tothe backpressure algorithm in[6].There is only one exception for the distributivity,in the sense that the sources do requirea small amount of feedback from the sinks at the setup stage of the code construction.Other than that,there is no globalmechanism responsible for the communication scheme.Thecoding coefficients are taken from a generalfield and unlike many previous schemes operations are not restricted to XOR,giving rise to richer families of codes.The distributed implementation is especially important forad-hoc wireless networks,where nodes may have knowledgeonly on their outgoing links.We show how to combine our construction with the backpressure algorithm for wireless ad-hoc networks[12].Unlike previous schemes,for both thenon-distributed and the distributed cases,the complexity of our network coding construction is comparable to that ofmulticommodity.For the case of random codes,wefind non-trivial upper and lower bounds on the performance of ourconstruction.These results partially appear in[13],[14].II.D EFINITIONS,N OTATIONS AND P RELIMINARIES Consider an acyclic,unit capacity directed network G= (V,E)where parallel edges are allowed.There are two sources s1,s2∈V and two sinks t1,t2∈V.Source s i transmits to sink t i at rate R i.As in[15],when convenient we adda dummy source s i which is connected to source s i with R i edges{e i1,...,e i Ri}.The dummy source s i is mentioned only when necessary for ease of description.The size of the minimal cut between s i and sink t i is h i.Define for each source-sink pair s i−t i,the subgraph G i of G containing only the nodes and edges that participate in a certainflow of magnitude h i from s i to the sink t i.Denote byΓI(v)andΓO(v)the set of incoming and outgoing edges of node v,respectively.Similarly,denote byΓI(e)andΓO(e) the set of incoming edges of the tail of e and outgoing edges of the head of e,respectively.Unless otherwise specified,we assume that the topology ofthe network is completely known to the code designer.In thiscase of a known network,we assume that G is given by:G=∪i=1,2G i(1)0733-8716/09/$25.00c 2009IEEEFor a general network,we can always find a subgraph of the network that has the form of (1)and implement our algorithm for that subgraph.For linear network codes,any edge e has a global coding vector v (e )of dimension R 1+R 2associated with it.For algebraic block network codes,the dummy source node s igets R i input symbols denoted as X i =(X i 1,···,X iR i)from the field F .For an outgoing edge e i j ,1≤j ≤R i of si all the coordinates are zero except for the coordinatek<i R k +j ,which is equal to X ij .For the rest of the edges v (e )is given recursively by:v (e )=e ∈ΓI (e )m (e ,e )v (e )(2)where e is an incoming edge of e ,and m (e ,e )is the codingcoef ficient.The symbol on e isy (e )=e ∈ΓI (v )m (e ,e )y (e )=v (e )T (X 1,X 2)(3)where (X 1,X 2)is a vector of dimension R 1+R 2containing the input symbols of s 1and s 2.III.C ODE C ONSTRUCTIONWe start our construction with global coding vectors of dimension h 1+h 2.The first h 1coordinates are associated with s 1and the last h 2with s 2.The vector of dimension h 1containing the first h 1coordinates of v (e )is denoted by v 1(e ),and analogously v 2(e )is de fined for the last h 2coordinates.We find an achievable rate region which improves that of the multicommodity flows.We start by a special case,where one of the sources,say s 2,transmits at its maximal flow rate h 2and find a possible rate for s 1.We show that this rate of s 1is better than the best multicommodity flow rate.We generalize this special case by considering a certain point on the boundary of the multicommodity flow rate region (R 1,R 2).We show how R 1can be improved for a given R 2using network codes.A.Code Construction for a Special CaseAssume that s 2transmits at its maximal rate R 2=h 2and that s 1tries to transmit at a certain,as high as possible,rate.The construction includes three stages.The first stage is the internal coding which determines the coding coef ficients of the intermediate nodes.The second and the third stages are the constraints setting stages,Stage A and Stage B.These stages determine the additional required coding at the s 1.Stage A ensures that t 2would be able to reconstruct s 2and Stage B ensures that t 1would be able to reconstruct s 1.It will be shown that with this scheme for each 2Δbits that s 1reduces its rate below h 1,s 2would be able to increase its rate by at least Δbits,as long as the capacity constraints are not violated.This tradeoff is not always possible without coding.1)Internal Coding:This stage is similar to the polynomial time algorithm for multicast [15].A path p is a sequence of consecutive edges.A flow is a set of edge disjoint paths be-tween two nodes.The algorithm starts by finding the maximal flows G 1of rate h 1from s 1to t 1and G 2of rate h 2from s 2to t 2.Each of the flows G l ,l =1,2consists of h l edge disjointpaths,denoted by {p l 1,···,p lh l }.There can be multiple choicesfor G 1and G 2,since there may be several different maximalflows associated with each source-destination pair.For our purposes,we choose arbitrary maximal flows G l ,l =1,2.We use only edges in the subgraph G 1∪G 2,so we assume that our original network is G =G 1∪G 2.The algorithm steps through the edges in G in topological order.For edge e a coding vector of dimension h 1+h 2is assigned.For e that participates in either G 1or G 2,but not both,we assign m (e ,e )=1for e that preceded e in the flow.For e that participates in both G l ,l =1,2,the coef ficients m (e 1,e ),m (e 2,e )are determined,where e 1precedes e in G 1and e 2precedes e in G 2.The code coef ficients are drawn from an algebraic field F .The set C l ,l ={1,2}contains one edge from each of thepaths {p l 1,···,p lh }in the flow G l ,l ={1,2},the edge whose global coding vector was de fined most recently.Denote the global coding vectors of the edges in C l ,l ={1,2}by V l ={v (e ):e ∈C l }.For l =1,2,denote by V 1l ={v 1(e ):e ∈C l }the corresponding set of vectors of dimension h 1and by V 2l ={v 2(e ):e ∈C l }the corresponding set of vectors of dimension h 2.The invariant maintained by the algorithm is that for t 1the set V 11spans F h 1,while for t 2the set V 22spans F h 2.Similarly to the proof in [15]for multicast,it can be seen that for field size two or larger,we are ensured that at least a single m (e ,e )in F maintains the invariant.At the end of the construction the edges in C l ,l =1,2are ΓI (t l ).The property of a code constructed by this scheme is that a certain sink can decode the data intended for it,provided that the other source is silent.An example of a code over the binary field is given in Figure 1,where h 1=3,h 2=1.In Figure 1(a)G 1is in thick lines,while in 1(b)G 2is in thick lines.De fine the symbols a 1,a 2,a 3as the symbols transmitted by t 1on its outgoing links from left to right,respectively.The sets C 1,C 2at the end of the internal coding are also speci fied.At each stage of the internal coding C 1contains one edge from each of the three paths from s 1to t 1.In Figure 1(a),C 1contains e 1,e 2,e 3which are the edges in the three paths from s 1to t 1,from left to right,respectively.At the end of the internal coding V 1={(1,0,0,1)T ,(1,1,0,1)T ,(1,1,1,1)T }.It follows that V 11={(1,0,0)T ,(1,1,0)T ,(1,1,1)T }.Like-wise V 2={(1,1,1,1)T }and V 22={(1)}.Note that when R 2=h 2=1,we cannot achieve a nonzero rate R 1using multicommodity flow.2)Constraints Setting-Stage A:Consider C 2,which at the end of the internal coding is ΓI (t 2).The sink t 2will be able to decode at rate h 2if all interference noise from s 1is canceled.The dimension R 12of the vector space spanned by V 12is R 12≤min {h 1,C 12,h 2},where C 12is the capacity from s 1to t 2.We choose a subset of V 12of size R 12that is the basisof V 12.Denoted the basis by B 12={v 1(e 1),...,v 1(e R 12)}and the edges whose vectors are in B 12by C 12.In Figure 1,we have R 12≤h 2=1and V 2={v (e 3)}={(1,1,1,1)T }.The vector in V 12is given by V 12={v 1(e 3)}={(1,1,1)T },andso B 12={v 1(e 3)}={(1,1,1)T }and C 12={e 3}.In order for t 2to achieve rate h 2=1we set the constraint a 1+a 2+a 3=0.In general,the interference noise can be canceled byforcing the symbols on C 12to be functions of s 2only.The interference components on the other edges of C 2will also be1s linesin thick (a)1G1s lines in thick (b)2G },,{3211e e e C }{32e C Fig.1.Example Code for InternalCoding1s 12s Fig.2.Final Code for Example Networkcanceled,since they are linear combinations of those on C 12.Each edge in C 12would add at most a single constraint on s 1.Each such constraint reduces the rate of s 1by at most a single bit.Therefore,rate h 1≥h 1−min {h 2,C 12,h 1}is transmitted from s 1.If h 1>h 2,h 1is strictly positive.3)Constraints Setting -Stage B:Consider t 1and the edges in C 1,which are now ΓI (t 1).The dimension R 21of the vector space spanned by V 21is R 21≤min {h 2,C 21,h 1},where C 21is the capacity from s 2to t 1.We choose a subset of V 21of size R 21that is the basis of V 21,denotedby B 21={v 2(e 1),...,v 2(e R 21)}.Denote the nodes whosevectors are in B 21as C 21.In Figure 1,R 21≤h 2=1and V 21={v 2(e 1),v 2(e 2),v 2(e 3)}={(1),(1),(1)}.We choose C 21={e 3}and B 21={v 2(e 3)}={(1)}.In general,we find additional constraints on s 1,such that the symbols on C 21depend on s 2only.Sink t 1can cancel the interference components on the other edges in ΓI (t 1)using the the symbolson C 21,since they are linearly dependent.Each edge in C 21adds at most a single constraint on s 1,which reduces the rate of s 1by at most a single bit.Since the rate was already reduced to h 1≥h 1−min {h 2,C 12,h 1},the final rate of t 1is h1≥h 1−min {h 2,C 12,h 1}−min {h 2,C 21,h 1}≥h 1−2h 2.If h 1>2h 2,h 1is strictly positive.In Figure 1,observe that since we already set the constraint a 1+a 2+a 3=0,t 1is already able to decode b 1,which is the interference noise at t 1.The final rate att 1is h 1=2R 11Fig.3.Rate Region for Example Networkh 1−min {h 2,C 12,h 1}=3−1=2,which is larger than thebound h 1≥h 1−2h 2=1.The final code is shown in Figure 2.The rate region is shown in Figure 3for multicommodity flow,and for our coding scheme.For this example,our scheme is optimal since it achieves the cut set bound,which is 3.Note that the rate region has an angle 45o with the negative x axis.This,however,turns out not to be the general case.Note that in the original network there may be several choices for the maximal flows G 1and G 2.Different choices of G 1and G 2might result in multiple code constructions and possibly different rates can be achieved.Nevertheless,enu-merating all the possible flows is complicated.From practical viewpoint,we propose to choose certain flows G 1and G 2and operate on them.An interesting problem would be to find an ef ficient way to choose the optimal flows G 1and G 2for the purpose of coding.B.Tradeoff Property of the CodeTheorem 1:If s 1reduces its maximal rate h 1by 2Δbits,then there is a code such that s 2will be able to transmit at a rate of at least Δbits,as long as the minimal cut condition is not violated.Proof:The proof is by constructing the code.We have shown in Section III-A that for the special case when s 2transmits at its maximal rate R 2=h 2then s 1can achieve rate which is at least h 1−2h 2.For the general case,we de fine asubgraph of G by ˜G =G 1∪G Δ2where G 1is a flow of size h 1from s 1to t 1and G Δ2is a flow of size Δfrom s 2to t 2.For thesubgraph ˜Gwe construct a code,according to the special case in Section III-A.The size of the maximal flow from s 1to t 1in ˜Gis denoted by ˜h 1and according to construction ˜h 1≥h 1.In fact,˜h1=h 1since ˜G is a subgraph of G ,and thus the maximal flow ˜h1in ˜G cannot be larger than the maximal flow h 1in G .The size of the maximal flow from s 2to t 2in ˜Gis denoted by ˜h 2and according to construction ˜h 2≥Δ.If˜h 2>Δ,then s 2can ignore the symbols that are not in G Δ2and not use them for decoding.Thus we can always assumethat ˜h2=Δ.Therefore,the rate of s 1in ˜G achieved by the code constructed according to Section III would be at least˜h1−2˜h 2≥h 1−2Δ.It follows that h 1lost at most 2Δbits relative to its maximal flow h 1and that the rate of s 2is at least Δ.It follows that if we take the point (h 1,0)in the rate region and draw a line of slope 1/2(which is equivalent to a 22.5o angle)with the negative x axis (that represents h 1),it will be within the capacity region of our scheme (as long as R 2≤h 2).This observation can be helpful in determining the situations for which our scheme is most useful.If for the multicommodity rate region the slope with the negative x of1s 122Fig.4.Example Code for Counterexample Networkthe line from (h 1,0)is smaller than 1/2,then our codingscheme is guaranteed to improve the multicommodity rate region.This can be performed by the construction in the proof of Theorem 1,which achieves the rate pair (h 1−2Δ,Δ),for Δs.t.R 1=h 1−2Δ≥0and R 2=Δ≤h 2.Likewise,for (0,h 2)if we draw a line of slope 1/2with the negative y axis,it will be contained in the capacity region of our scheme (as long as R 2≤h 2).If for the multicommodity rate region the slope with the negative y of the line from (0,h 2)is smaller than 1/2,then our coding scheme is guaranteed to improve the multicommodity region.Given a general point in the rate region (R 1,R 2)our coding scheme is guaranteed to improve the multicommodity rate region if the points (R 1−2Δ,R 2+Δ)or (R 1+Δ,R 2−2Δ)are not in the multicommodity rate region,for some Δ>0,if the individual capacity constraints are not violated.In Figure 1the slope from the point (h 1,0)=(3,0)with the negative x axis is 1/3,which is less than 1/2.Our coding scheme is guaranteed to improve the multicommodity rate region.We take the point (3,0)and apply the construction in the proof of Theorem 1with Δ≤h 2=1we are guaranteed to achieve the point (3−2·1,1)=(1,1),which is not achievable without coding.On the other hand,if we look at the point (0,1)in the multicommodity rate region,the slope with the negative y axis is 3which is larger than 1/2.It follows that we are not guaranteed to improve this point with our scheme.For the network in Figure 1we are able to improve the rate region beyond what Theorem 1guarantees.In the coded case,the slope from (h 1,0)=(3,0)is 1.For each Δbits that s 1reduces its rate below h 1,s 2can increase its rate by Δ.The one-to-one tradeoff is not always possible.In Figure 4,where h 1=3,if a one-to-one ratio is possible,then we expect the rate pair R 1=1,R 2=2to be achievable.A possible code is given,prior to the constraints setting.For R 2=2,the constraints setting reduces R 1to zero.In fact,for this network R 1=1,R 2=2is not achievable by any network code [14].Thus for this example,the min-cut bound is not always achievable.C.Improving the Multicommodity FlowSuppose we are given a rate pair (R 1,R 2),which is on the boundary of the rate region of the multicommodity flow.Weshow how the solution (R 1,R 2)can be improved.Denote the flow of source s i ,i =1,2at edge e as x i e .At edge e ,from the flow conversion and the capacity constraints:e ∈ΓI (e )x 1e = e ∈ΓO (e )x 1e , e ∈ΓI (e )x 2e = e ∈ΓO (e )x 2e ,x 1e +x 2e≤c (e )∀e,x 1e ≥0,x 2e ≥0(4)where for edge e =(u,v ),c (e )is the multiplicity of the unitcapacity edges between u and v .If rate (R 1,R 2)is achieved by the multicommodity flow,x 1s =x 1t =R 1,x 2s =x 2t =R 2(5)where x 1s is the flow leaving s 1and x 1t is the flow of s 1reaching t 1.The solution to the multicommodity de fines flowG 1from s 1to t 1and flow G 2from s 2to t 2.Flow G1mightbe a subgraph of a larger flow G 1from s 1to t 1.Given G1we add additional paths from s 1to t 1to compose G 1.Denote theadditional paths in G 1\G1by D 1.Likewise,we construct D 2,a set of paths added to G 2,which compose flow G2.Since the pair (R 1,R 2)is on the boundary of the multicommodityregion,in the network U =D 1∪G 2,if s 2transmits G2at rate R 2,then s 1cannot transmit without ing the scheme in Section III-A for U ,s 1can transmit at a certain rate.Thus in G ,s 1transmits at a rate higher than R 1and s 2transmits at rate R 2,improving the point (R 1,R 2).If we are not given a multicommodity flow solution,wecan formulate the required conditions on G 1,D 1,G2and D 2.De fine four commodities.The two commodities x a e and x c e (x be and x d e )are transmitted by s 1(s 2)and received by t 1(t 2).Theflows x a e and x c e de fine G1and D 1,respectively:e ∈ΓI (e )x a e = e ∈ΓO (e )x a e , e ∈ΓI (e )x ce = e ∈ΓO (e )x c e ,x a e +x ce≤c (e )∀e,x a e ≥0,x c e ≥0(6)Likewise the flows x b e and x d e de fine G2and D 2,respectively:e ∈ΓI (e )x b e = e ∈ΓO (e )x b e , e ∈ΓI (e )x de = e ∈ΓO (e )x d e ,x b e +x de ≤c (e )∀e,x b e ≥0,x d e ≥0(7)The flows x a e and x be constitute together the multicommodity flow,with rate pair (R a ,R b ).Therefore:x a e +x be≤c (e )∀e (8)Note that flow x a e is allowed to overlap with flow x de .Likewisefor flows x b e and x ce .De finition 1:Denote the set x a e ,x b e ,x c e ,x d e ,∀e ∈E that maintain conditions (6)-(8)as quasi flow Z .The computational complexity of finding the quasi flow Z is similar to that of the multicommodity since the linear program-ming has a similar number of variables and inequalities.GivenZ ,the code that improves the multicommodity solution x a e ,x be can be constructed as follows.At the first stage,to improveR 1,consider x a e ,x b e ,x c e .The data transmitted on x ae is leftuncoded.The data on x b e ,x ce is coded according to Section III-A.To improve R 2,in the second stage likewise considerx a e ,x b e ,x d e .D.Distributed Code Construction1)Distributed Quasiflow Construction:In our distributedsetting all nodes,except the sources,code and make routing decisions according to the information they receive from theirneighboring nodes.There is one exception to the distributivitysince the sources require a small amount of feedback from the sinks.Other than that,there is no global mechanism respon-sible for the communication scheme.Generally,distributed schemes incur some rate loss,but the rate loss becomes smallerif a largefield size is employed and larger routing delays areallowed.The quasiflow Z can be found by linear programming, which is not distributed.For the multicommodity problem,the backpressure algorithm in[6]is distributed.The algorithmis an approximation and has lower complexity than linear programming.We show how to modify the algorithm in[6]inorder tofind the quasiflow.Once Z is found,network codingcan be constructed,as will be shown in Section III-D2.The algorithmfinds a solution with demands d i for commodityi=a,b,c,d provided that there exists feasible quasiflow with demand(1+2 )d i per commodity i.For each source(sink),weconnect a dummy source(sink)with several unit capacity edgesto the source(sink),where the number of connecting edges is R(1+2 )d i and R is the number of rounds of the algorithm, defined below and upper bounded by(9).This quantity an upper bound on theflow that goes through the source,for a single operation of the algorithm.There is a regular queue for each commodity at the head and tail of each edge.The potential of a regular queue is defined asφi(q)=eαi q,where αi= /8ld i and l is the length of the longestflow path in G. The size of the source queue for each commodity i is boundedby Q i,where Q i=Θ(ld i ln(1/ )).The excess of commodity iis placed in an overflow queue at each source.The potential of the overflow queue is defined asσi(b)=bφ i(Q i)=bαi eαi Q i. Details on these definitions can be found in[6].The algorithm proceeds in rounds,where each unit-time round consists of the following four phases:1)For each source s i add(1+ )d i units of quasiflow tothe overflow queue of commodity i and move as much quasiflow as possible from the overflow queue to the source queue.2)For each edge push quasiflow across it(from the tailqueue to the head queue)so as to minimize the sum of potentials of the queues in it subject to constraints(6)-(8).3)For each commodity i empty the sink queue.4)For each i and each node v,rebalance commodity iwithin v so that the head queues of the incoming edges and the tail queues of the outgoing edges for commodityi are of equal size.The algorithm does not guarantee that each unit of quasiflow will reach its destination.However,it can be shown that the amount of undelivered quasiflow stays bounded over time,by upper bounding the size of the regular queues and overflow queues.The analysis is similar to the analysis in[6],except a quasiflow is treated instead of aflow.The full modification to quasiflow appears in[14].Over R rounds we inject R(1+ )d i units of commodity i.If we require the undeliveredflow to be at most R d i,it can be shown that it is sufficient to takeR=OEl(1+ln(1/ ))2(9) rounds.The complexity is R times the work performed at a single round.The number of rounds R required for the convergence of the algorithm isfinite and decreases when we allow a larger fraction of the quasiflow to remain undelivered.2)Incorporating Network Codes:We interpret the network as a time slotted network[16],[17].Definition2:Given a network G,and a positive integer R, the time slotted network denoted by G R,is defined as follows. It includes the nodes s1,s2and all nodes of the type x r where x is a non-source node in G and r ranges through integers1 and R.The edges in the network belong to one of the three types listed below.For any non-source nodes x and y in G:•For r≤R the capacity of the edge from s l,l=1,2to x r,is that of the edge from s i to x in G.•For r<R the capacity of the edge from x r to y r+1is the capacity of the edge from x to y in G.•For r<R the capacity of the edge from x r to x r+1is infinity.In Z,for each of theflows x i e,i=a,b,c,d,a symbol sent from s l,l=1,2to x r corresponds to the symbol sent on edge(s l,x)during round r.A symbol sent from x r to y r+1corresponds to the symbol sent on edge(x,y)during round r.A symbol sent from x r to x r+1corresponds to the accumulation of a symbol in the queue of x from round r to round r+1.For eachflow x i e,∀e∈E the edges in G R that participate in theflow form a subgraph with capacity Rd i. After the algorithmfinds the quasiflow Z,we construct the network code for network G R according to Section III-C. For the distributivity of the algorithm,we use random coding for the internal coding stage in Section III-A1,where each node chooses the coding coefficients from afield.The total number of coding edges in the network is ER.Thesuccess probability of the internal coding is at least P succ=1−2|F|ER[18].The block size is cER,where c is chosen according to the desired success probability and the block size as O(log(ER)).The block size can be larger than the capacity of each edge.The time scale is changed,so that each edge can carry at least a single symbol at each round.Since the delay of the quasiflow is at least R rounds,the coding delay is of logarithmic order.The distributed quasiflow construction in Section III-D1 does not guarantee that all of theflow will reach the sinks, and some packets may be lost.There are a number of ways to set up the coding scheme,and we present a possible way.We denote a set of R rounds as a step.In thefirst step quasiflow Z is determined using the algorithm in Section III-D1.The quasiflow in future steps will behave the same,since the quasiflow is constant and deterministic.The symbols that have not reached the sinks after an entire step are emptied from the queues in the network,so that they are not mixed with symbols in future steps.Since the quasiflow in G R is constant and deterministic,after thefirst step it is possible to learn exactly。
