IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.8 AUGUST 2009

2141

LETTER

Decodability of Network Coding with Time-Varying Delay and No
Buﬀering
Terumasa TATENO†∗ , Student Member, Ryutaroh MATSUMOTO†a) , Member,and Tomohiko UYEMATSU† , Senior Member

SUMMARY
We show the suﬃcient conditions for coding by nodes
such that every sink can decode all information multicasted by the single
source when there exists time-varying delay of information transmission at
links in the network coding.
key words: time-varying delay, network coding, linear coding, multicast

1.

Introduction

In the traditional information transmission through a network, an intermediate node was only allowed to duplicate
input information and output the duplication. In contrast,in the transmission with the network coding, an intermediate node is able to code the input information from multiple
links and outputs the coded information. The multicast using the network coding can achieve higher information rate
than the traditional multicast [1]. Hence the network coding is attracting much attention as a method for multicast.
Furthermore, it is known that linear coding in each node issuﬃcient to multicast in such a rate [2]. Accordingly in thispaper, we only deal with the linear network coding. In thefollowing, the network coding refers to the linear network
coding, and the single source multicast is considered.
For practical realization of the network coding, weshould consider delay in the information transmission anddelay is not always constant in time. Because of timevarying delay, a sink may sometimes fail to decode transmitted information depending on the structure of the networkand coding. However, in most of past research of the network coding, it was assumed that there is constant delay that
does not change in time or that there is no delay of information transmission [1]–[4]. The drawback in these researches
is that each node have to wait for coding until all the information reaches to the node when there is time-varying delay.
This means that the buﬀer for coding by nodes is necessary
and that transmission delay unnecessary accumulates in every node.
As a research considering time-varying delay, Chou etal. proposed a scheme by employing generation [5]. In thescheme, packets containing information multicasted at the
Manuscript received February 19, 2009.
Manuscript revised April 28, 2009.
†
The authors are with the Department of Communications andIntegrated Systems, Tokyo Institute of Technology, Tokyo, 1528550 Japan.
∗
Presently, with the Central Japan Railway Company.
a) E-mail: ryutaroh@rmatsumoto.org
DOI: 10.1587/transfun.E92.A.2141

same time are said to be in the same generation. Each packet
header includes the index of generation and coeﬃcients oflinear combination. For the packet arriving at each intermediate node within a fixed time interval, the coding is done
among packets belonging to the same generation. We calltheir scheme the generation by generation network coding.
However, in their scheme, because the coding of each generation is only permitted, it is necessary to transmit as many
packets as the number of generations accumulated in eachnode. Hence the bandwidth is wasted. Also, the buﬀer tosynchronize the same generation packets is necessary.
We can consider a scheme that allows coding among
diﬀerent generations in order to decrease the amount of
buﬀers and to use the bandwidth eﬃciently compared withthe generation by generation network coding. Recently,
Halloush et al. proposed a approach called multi-generation
mixing (MGM) that allows coding among generations [6],[7]. However, they did not clarify the condition under which
every sink can decode all the information. They only verified the decodability by computer simulations in limited scenarios.
We propose the scheme in which information multicasted at the diﬀerent time is coded by intermediate nodes
without buﬀers when there is time-varying delay. Because
coding is permitted among all generations, when the sameamount of information as the generation by generation network coding [5] is multicasted, the amount of transmitted
packets decreases, that is, the bandwidth is more eﬃciently
used. In our scheme, it is important to clarify the condition under which every sink can decode all the informationand the condition under which a sink fails to decode. We
show the example when all information cannot be decoded,
and suﬃcient conditions for coding by nodes such that every sink can decode all information multicasted by the single
source.
The rest of paper is organized as follows. In Sect. 2 we
explain the definitions and model of a network with timevarying delay. In Sect. 3, we introduce an example in which
information cannot be decoded by a sink due to the timevarying delay. After that we show suﬃcient conditions forevery sink to decode all information, and analyze decoding
delay in Sect. 3. Section 4 gives conclusion and future tasks.

c 2009 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.8 AUGUST 2009

2142

2.

holds, and for the rest of linksb(e) =me (ei )b(ei )Preliminaries

2.1 Basic Notation
We shall assume a capacity of link that connects nodes together as a unit capacity, that is, it can only transmit oneof the elements in a finite field Fq per unit time. A directed acyclic network that permits multiedge is represented
by G = (V, E) in this paper, where V and E represent thesets of nodes and links, respectively. We also represent the
only source by s ∈ V, the dummy source by s ∈ V and theset of sinks by T = {t1 , t2 , · · · , td } ⊂ V. It is well known thatwhen the minimum of max-flow between the source s andeach sink ti ∈ T is denoted by h , the maximum amount of asymbol that can be multicasted from the source s to all sinks
is h in the network where all link capacities are 1 [1].
In this paper, we assume the number of input links fromthe dummy source s to the source s to be h ≤ h , and thedummy source s sends h symbols in Fq to the source s without coding per unit time. Also, we index h symbols from one
to h, and the source s sends them after coding. The set γ− (v)denotes the set of input links to a node v ∈ V, and start(e)denotes the node whose output link is e. Then the map me
associated to a link e of G is defined asme : γ− (start(e)) → Fq .
The me is called as the local coding vector (LCV), it decides the coeﬃcient of a linear relation between inputs andoutputs of each node [8].
2.2 Network Coding without Delay
In Sect. 2.2, we shall consider the case that there is no delay
in information transmission. The information that we wantto multicast is represented by an in f ormation vector i ∈ Fhq .
The j-th row of i denotes the j-th symbol from the dummysource s . Let y(e) be the symbol that flows through theoutput link e of an intermediate node (except for the dummysource s ) at a certain time, and we havey(e) =me (ei )y(ei ).
(1)
ei ∈γ− (start(e))

Also, for all i and y(e) for a link e, a column vector b(e) ∈ Fhq
which satisfies
y(e) = i · b(e)(2)

is defined as the global coding vector (GCV). Note that the
GCV is uniquely determined, because a GCV represents alinear map sending a vector in Fhq to a symbol in Fq [8].
The GCV b(e) represents the influence of coding by all upstream nodes of the link e. For links ei (i = 1, . . . , h) fromthe dummy source s to the source s,b(ei ) = [0i−1 , 1, 0h−i ]T(4)ei ∈γ− (start(e))(3)

holds [8]. In the following, the GCV is used for referring tocoding when there is no delay.
2.3 Network Coding with Time-Varying Delay
In Sect. 2.3, we shall consider that there is time-varying delay in information transmission. We shall use discrete timeindexing. The delay in information transmission between
nodes is assumed to be non-negative integer multiple of unit
time. In addition, an input symbol to a link is always output
before its succeeding input symbols and there is no loss orerror of symbols on a link. Also, at most one symbol is output from a link per unit time. The dummy source s sends hsymbols per unit time to the source s from time 1 to , butdoes not send symbols after time . We assume that there isno delay in links between s and s. The total number of Fq
symbols transmitted from s is h. We shall represent theseh symbols by the following h ×  matrix denoted by thein f ormation matrix i. The ( j, k) component of i represents
the j-th symbol among h symbols transmitted from s at thetime k.
Let yn (e) be the output symbol from a link e at time n.
If the link e does not output a symbol at time n because oftime-varying delay, then we define yn (e) = 0. We use thesame LCV me at every time slot. If a node does not receive
a symbol from an input link, then the node assumes that thelink outputs 0. Under these assumptions, we have following
relationyn (e) =me (ei )ym (ei ).
(5)
ei ∈γ− (start(e))

Equation (5) implies that input to link e at time m is output
at time n. Equation (5) corresponds Eq. (1), which assumes
no delay in information transmission.
For all i and yn (e) on a link e at time n, a matrix bn (e)which satisfies
yn (e) = i · bn (e)(6)

is defined as the global coding matrix (GCM), where theinner product of matrices A and B is defined as Tr[ABT ].
Equation (6) corresponds to Eq. (2). The GCM is uniquelydetermined as well as the GCV, because a GCM represents
to a symbol in Fq .
a linear map sending a matrix in Fh×q
Furthermore, in the case there is no output from a link e attime n, bn (e) becomes the zero matrix. Since symbols aresent from time 1 to , the GCM is an h ×  matrix, the sameas the information matrix i. In addition,
bn (e) =me (ei )bm (ei )(7)ei ∈γ− (start(e))

holds corresponding to Eq. (4). For bn (ei ) of a link ei (i =1, . . . , h) from the dummy source s to the source s, the n-th

LETTER

2143

column is [0i−1 , 1, 0h−i ]T , and the other components are 0.
We include GCM’s in packet headers for enabling every sink to decode i. A sink can recognize how linearly combined symbol is included in the arrived packet. If , which is
the time of last symbol transmitted from the dummy source,is large, then the packet header containing the GCM would
be bigger, but we explain a method to avoid this problem in
Sect. 3.2.
3.

Suﬃcient Conditions for Every Sink to Decode All
the Transmitted Symbols

In Sect. 3, Sect. 3.1 gives an example of a network where thesymbol cannot be decoded by a sink due to time-varying delay. For a network where the source receives two symbols
per unit time and multicasts them, Sect. 3.2 gives a suﬃcientcondition that all transmitted information can be decoded
regardless of time-varying delay. In Sect. 3.3 we show thatwhen the source multicasts three or more symbols, the suﬃcient condition in Sect. 3.2 is insuﬃcient. Section 3.4 gives
suﬃcient conditions that all transmitted information can be
decoded in the network where the source receives more than
two symbols per unit time and multicasts them.
3.1 Example of a Network Where Symbols Cannot be Decoded by the Sink Due to the Time-Varying Delay
Suppose that we have LCV’s on a network that allows every sink to decode the transmitted information when there
is no delay. We shall show an example of time-varying delay preventing a sink from successful decoding with such
LCV’s. Such example requires us to find suﬃcient conditions for successful decoding with every possible timevarying delay. Figure 1 is an example of a network where
the symbol cannot be decoded by the sink due to the timevarying delay. In Fig. 1, h is 1 and the characteristic of thefinite field is five or more. The source receives only symbol ai ∈ Fq at time i. The source sends ai at time i for
i = 1, 2, 3. The links ei (i = 1, · · · , 5) and the nodes s, 1, 2
and t are defined as Fig. 1. The LCV’s are defined as follows: me2 (e5 ) = 1, me3 (e5 ) = 1, me4 (e5 ) = −1, me1 (e2 ) =1, me1 (e3 ) = 1, me1 (e4 ) = 1. Assume that we have timevarying delay and output symbols from each link as shownin Table 1. The symbols received by the sink are output
from e1 . Observe that a1 and a2 are not decodable. Such asituation can occur in the random network coding [9].
3.2 Suﬃcient Condition for Two Symbols
We shall present a suﬃcient condition to decode all transmitted information when the source s receives two symbols
per unit time, multicasts them and there is time-varying delay in a network. The set Ei (i = 1, . . . , h) of links is definedas Ei = {e ∈ E | the i-th component of b(e) is non-zero }.
We introduce the suﬃcient condition.
Condition 3.1: For all i = 1, . . . , h and every link e except
the links from s to s, the cardinality of the set {e ∈ Ei | e isan immediate upstream of the link e and me (e ) is non-zero}is at most 1.
We remark that the butterfly network [1] satisfies Condition 3.1.
Lemma 3.1: We fix an input link e to a sink in this lemma.
For the network which satisfies Condition 3.1, the following
claims hold.
(1) If the i-th row of the GCV b(e) is 0, then the i-th row of
GCM bn (e) is 0 for all n.
(2) If the i-th row of the GCV b(e) is non-zero value x, there
exists unique n for each j such that the (i, j) component of the GCM bn (e) is non-zero, which is denotedby ti ( j). The (i, j) component of such bn (e) is x.
(3) The function ti ( j) is strictly increasing.
Proof: (1) Assume that there are two or more links in an
immediate upstream of a link f and they belong to Ei . If
the symbols that flow through each link in Ei are mutuallycancelled by linear combination on start( f ) when there is nodelay, then the i-th row of b( f ) is 0. However, when there istime-varying delay, the i-th row of bn ( f ) may be non-zero.
By Condition 3.1 there does not exist such a situation. There
are no other cases in which the i-th row of b( f ) is zero andthat of bn ( f ) is non-zero. Therefore we obtain (1) of Lemma
3.1.
(2) If Condition 3.1 is satisfied, then there is only at
most one path from the source s ending at a link e such thatevery link f on the path has a non-zero i-th component ofb( f ). This means that the i-th symbol from s at time j does
not split into two or more time slots nor disappear. Hence
we obtain (2) of Lemma 3.1.
(3) In addition to (2), because an input symbol to a
Table 1

Fig. 1

Network where transmitted symbol cannot be decoded.

Output symbols from each link outputs in Fig. 1.
time
1
2
3
4

e2
0
a1
a2
a3

e3
a1
a2
a3
0

e4
−a1
0
−a2
−a3

e1
0
a1 + a2
a3
0

IEICE TRANS. FUNDAMENTALS, VOL.E92–A, NO.8 AUGUST 2009

2144

link is always output before its succeeding input symbol andthere is no loss or error of symbols on a link, we obtain (3)of Lemma 3.1.
According to Lemma 3.1, a GCM can be compactly
recorded at a packet header by using two kinds of values.
These values are the value of non-zero component in eachrow of the GCM, and the column of the non-zero component, in other words, the time that the symbol is transmitted
from the dummy source (if there are no non-zero components in the row, these values are zero). Thus 2h values are
suﬃcient for recoding a GCM in a packet header.
Because the butterfly network satisfies Condition 3.1,
every sink can be decoded all transmitted information even
if there is time-varying delay by the following theorem.
We consider the following decoding procedure. We define a source symbol as a symbol flows from the dummysource s to the source s, that is, an information symbol to be
multicasted. Also we define an incoming symbol as a symbol flows on an input link to the sink. Consider an arbitrary
fixed sink. Two input links to the sink whose GCV’s are linearly independent are chosen. We pick the earliest incoming
symbol from each link to the sink containing an undecodedsource symbol. We decode the undecoded source symbols
in the pair of those two incoming symbols.
Theorem 3.1: Assume that a sink can decode all the source
symbols if there is no delay in a network with Condition 3.1
and that h is 2. Fix two links whose GCV’s are linearly independent. Then even if there is time-varying delay, whenever
the sink receive incoming symbols containing an undecodedsource symbol from both links, the undecoded source symbol contained in them can be decoded.
Proof: Let e1 and e2 be input links to the sink such thatb(e1 ) = [x1 , y1 ]T and b(e2 ) = [x2 , y2 ]T are linearly independent. We convert a GCM into a row vector such that the(n, m) component of the GCM is the ((n − 1) + m)-th component of the row vector. All the row vectors have size 2.
In all the row vectors, the components from the first (the( + 1)-st) to the -th (the 2-th) correspond to the first (second) source symbol, respectively. Also, the i-th ((i + )-th)component of the row vectors corresponds to the first (second) source symbol transmitted from the source at time i for1 ≤ i ≤ , respectively. We also define the reduced GCM as
the GCM in which the components corresponding to alreadydecoded symbols are set to 0.
Consider the two row vectors corresponding to the nonzero reduced GCM’s pair received from both links. It is assumed that p first source symbols and q second source symbols have been decoded by the time the sink decodes source
symbols corresponding to the non-zero reduced GCM’s pair.
Accordingly the sink has decoded the source symbols corresponding to the components from the first to the p-th component and from the (1 + )-th to the (q + )-th in the row
vectors. Thus the those components in the row vectors are
0. Then by Lemma 3.1 the row vectors can only have oneof the nine forms in Table 2. In any pattern, the number ofthe undecoded source symbol is 1 in every pair of incoming

pattern
1
2
3
4
5
6
7
8
9

Table 2 The row vectors from two links.
row vector from e1
row vector from e2(0 p , x1 , 0−1−p+q , y1 , 0−1−q )(0 p , x1 , 0−1−p+q , y1 , 0−1−q )(0 p , x1 , 0−1−p+q , y1 , 0−1−q )(0 p , x1 , 02−1−p )(0 p , x1 , 02−1−p )(0 p , x1 , 02−1−p )(0+q , y1 , 0−1−q )(0+q , y1 , 0−1−q )(0+q , y1 , 0−1−q )(0 p , x2 , 0−1−p+q , y2 , 0−1−q )(0 p , x2 , 02−1−p )(0+q , y2 , 0−1−q )(0 p , x2 , 0−1−p+q , y2 , 0−1−q )(0 p , x2 , 02−1−p )(0+q , y2 , 0−1−q )(0 p , x2 , 0−1−p+q , y2 , 0−1−q )(0 p , x2 , 02−1−p )(0+q , y2 , 0−1−q )Fig. 2 Example of a network where symbols cannot be decoded though
Condition 3.1 is satisfied.

symbols or the two vectors are linearly independent becauseof the linear independence for the GCV’s. Accordingly theundecoded source symbols can be decoded.
Therefore every time the sink received an incoming
symbol pair containing the undecoded source symbol fromboth links, the source symbol contained in them can be decoded.
Corollary 3.1: By the decoding procedure and Theorem
3.1, the sink can decode all the source symbols when thesource multicasts two symbols per unit time.
3.3 Insuﬃciency of Condition 3.1 for Three Symbols
When the source receives more than two symbols per unit
time and multicasts them, even if Condition 3.1 is satisfied,there are networks where all symbols cannot always be decoded by all sinks. The example is shown in Fig. 2. In the
network of Fig. 2, Condition 3.1 is satisfied. The source receives three symbols ai , bi , ci ∈ F2 (i = 1, 2) at time i, andmulticasts them to the sink. The e1 , e2 and e3 denote input
links to the sink as in Fig. 2. When delay is time-varying inthis network, there are cases that transmitted symbols cannot be decoded. Table 3 shows output symbols from eachlink in such a case. Because the system of linear equations
is underdetermined, not all symbols can be decoded.
3.4 Suﬃcient Conditions for More than Two Symbols
Condition 3.1 is insuﬃcient for more than two symbols be-

LETTER

2145
Table 3

Output symbols from each link outputs in Fig. 2.
time
1
2
3

e1
a1 + c1
a2 + b1
b2 + c2e2
a1 + c1
a2 + c20e3
b1 + c1
b2 + c20cause of the previous counter example in Sect. 3.3. Accordingly, we shall present an additional condition that
becomes a suﬃcient condition combined with Condition
3.1. When there is no delay, consider an arbitrary fixedsink. Let e1 , e2 , · · · , eh be input links to the sink such thatb(e1 ), b(e2 ), · · · , b(eh ) are linearly independent. Define S (v)
as the set of indices whose components in the vector v are
non-zero. We introduce Condition 3.2.
Condition 3.2: For i = 1, . . . , h/2 and input links e j ( j =1, · · · , h) to the sink, the following equation holds by renumbering of indices:
2(i−1)
2i

 


S (b(e j )) \S (b(e j )) = 2.
(8)


j=2i−1

j=1

h−1


the undecoded source symbols contained in them can be decoded.

j=1 S (b(e j )) in the incoming symbol from eh are decoded,

Corollary 3.2: By the decoding procedure and Theorem
3.2, the sink can decode all the source symbols when thesource multicasts three or more symbols.
4.

Conclusion and Future Tasks

The past researches of network coding did not adequately
consider the case that intermediate nodes combine information transmitted at diﬀerent time with time-varying delay. In
particular, it has not been clarified when a sink can decode
information with any time-varying delay. We showed such
suﬃcient conditions. We also showed the suﬃcient condition allowing a sink to start decoding of the symbols.
Future tasks include clarifying the maximum achievable rate under the suﬃcient conditions and constructing thealgorithm that composes the network coding satisfying sufficient conditions with the highest rate.

Also, if h is an odd number, the following equation holds inaddition to Eq. (8):


h−1



S (b(eh )) \S (b(e j )) = 1.
(9)



Acknowledgments

Theorem 3.2: Assume that a sink can decode all the source
symbols if there is no delay in a network with Conditions 3.1 and 3.2. Choose two links e2i and e2i−1 (1 ≤i ≤ h/2 ) which satisfy Eq. (8). Assume that there istime-varying delay and the sink received an incoming symbol containing undecoded source symbols corresponding to2(i−1) 2i
j=2i−1 S (b(e j )) \j=1 S (b(e j )). Then after source symbols corresponding to 2(i−1)
j=1 S (b(e j )) in the incoming symbol are decoded, the undecoded source symbols contained inthem can be decoded. Similarly when h is odd and the sinkreceived an incoming symbol containing undecoded source
symbols corresponding to S (b(eh )) \ h−1
j=1 S (b(e j )) from eh ,h−1 
after a source symbols corresponding to j=1 S (b(e j )) in theincoming symbol are decoded, the undecoded source symbol contained in it can be decoded.

References

j=1

Proof: If Condition 3.2 is satisfied, the number ofthe source symbol corresponding to 2ij=2i−1 S (b(e j )) \2(i−1) 
j=1 S (b(e j )) in incoming symbols from e2i and e2i−1 isat most 2. Therefore the source symbols can be decoded byusing the procedure in Sect. 3.2. On the other hand, when
h is odd, the number of the source symbol corresponding toS (b(eh )) \ h−1
j=1 S (b(e j )) in an incoming symbol from eh is at
most 1. Accordingly, after source symbols corresponding toThis research was partly supported by the Japan Society for the Promotion of Science under Grants-in-Aid No.
20760233.

[1] R. Ahlswede, N. Cai, S.Y.R. Li, and R.W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol.46, no.4, pp.1204–1216,
July 2000.
[2] S.Y.R. Li, R.W. Yeung, and N. Cai, “Linear network coding,” IEEE
Trans. Inf. Theory, vol.49, no.2, pp.371–381, Feb. 2003.
[3] S. Jaggi, P. Sanders, P.A. Chou, M. Eﬀros, S. Egner, K. Jain, and
L.M.G.M. Tolhuizen, “Polynomial time algorithms for multicast
network code construction,” IEEE Trans. Inf. Theory, vol.51, no.6,
pp.1973–1982, June 2005.
[4] R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Trans. Netw., vol.11, no.5, pp.782–795, Oct. 2003.
[5] P.A. Chou, Y. Wu, and K. Jain, “Practical network coding,” Proc.
41st Annu. Allerton Conf. Communication, Control, and Computing, vol.41, no.1, pp.40–49, Monticello, IL, Oct. 2003.
[6] M. Halloush and H. Radha, “Network coding with multi-generation
mixing,” Proc. 42nd Annu. Conf. Information Sciences and Systems(CISS 2008), pp.515–520, Princeton, NJ, March 2008.
[7] M. Halloush and H. Radha, “Network coding with multi-generation
mixing: Analysis and applications for video communication,” Proc.
IEEE International Conf. Communications (ICC 2008), pp.198–202,
Beijing, May 2008.
[8] P. Sanders, S. Egner, and L. Tolhuizen, “Polynomial time algorithms
for network information flow,” Proc. 15th Annu. ACM Symposium
on Parallel Algorithms and Architectures, pp.286–294, June 2003.
[9] T. Ho, M. Medard, R. Koetter, D. Karger, M. Eﬀros, J. Shi, andB. Leong, “A random linear network coding approach to multicast,”
IEEE Trans. Inf. Theory, vol.52, no.10, pp.4413–4430, Oct. 2006.