Delay Invariant cnc

Delay Invariant Convolutional Network Codes

Qifu Tyler Sun, Sidharth Jaggi, and Shuo-Yen Robert Li

Institute of Network Coding

The Chinese University of Hong Kong

Hong Kong SAR, China

[e-mail], {jaggi, bobli}@ie.cuhk.edu.hk

This work is supported by AoE grant E-02/08 from the University Grants Committee of the Hong Kong Special Administration Region, China.

Abstract—In this work, we define delay invariant convolutional network codes which guarantee multicast communication at asymptotically optimal rates in networks with arbitrary delay patterns. We show the existence of such a code over every symbol field. Moreover, the code can be constructed with high probability when coding coefficients are independently and uniformly chosen from a sufficiently large set of coding operations. On the other hand, if the symbol field is no smaller than the number of receivers, we devise a method to efficiently construct a delay invariant convolutional network code with scalar coding coefficients.

Introduction

Convolutional network coding (See , , and ) is a form of linear network coding which deals with a pipeline of messages as a whole rather than individually. It allows coding over the combined space-time domain. Over a network with cycles, the propagation and encoding of sequential data symbols may convolve together. Thus the propagation delay becomes an essential factor in network coding and hence convolutional network coding is naturally adopted to ensure causal data propagation around cycles. Under the formulation of propagation delay in , the transmission delay over channels is absorbed into processing delay at nodes. The node processing delay, on the other hand, is measured on every adjacent pair (d, e) of channels, where d and e are, respectively, the incoming and outgoing edges of a node. The delay over (d, e), which is a nonnegative integer power of D, represents the latency from the time a data symbol is received from d till the time it is first incorporated into the information sent onto e. Consequently, when data is propagated over the network via a convolutional network code (CNC), a delay may either be introduced by the network, or inserted intentionally by the code as part of the coding operation. As exemplified in , as long as there is a positive delay along every cycle in the network, data propagation in a causal manner can be assured over each cycle by a CNC.

In order to guarantee causality, a CNC constructed by existing algorithms, such as the deterministic one and the random one , is optimal (in the sense that achieves asymptotically optimal data transmission rate) with respect to a certain delay pattern. In this paper, after reviewing some fundamentals on convolutional network coding in Section , we introduce a new class of CNCs, called delay invariant CNCs (DI-CNCs), in a multicast network in Section . A DI-CNC is optimal in the presence of any delays in the network. In this way, the code can be constructed without the knowledge of network delays. Moreover, once it is deployed into the network, its optimality will not be affected by any delay changes brought about by inappropriate synchronization or other issues. Even though there are infinitely many (integer) delay patterns, we show that every field-based optimal linear network code actually qualifies as a DI-CNC. Moreover, we shall further show that a DI-CNC exists over every symbol field, and random coding actually suffices to construct one with high probability. On the other hand, in Section , when the symbol field is no smaller than the number of receivers, a variation of the technique in will be proposed to adapt the acyclic algorithm of for the deterministic construction of a DI-CNC with scalar coding operations.

Fundamentals on Convolutional Network Coding

Conventions. We shall adopt the following convention unless otherwise specified.

A network means a finite directed multi-graph that contains a unique node s with no incoming edges. This node is called the source. No edge loops around a node. The edge set is denoted by E. Every edge represents a noiseless transmission channel of unit capacity.

For every node v, denote by In(v) and Out(v), respectively, the sets of its incoming and outgoing edges. An ordered pair (d, e) of edges is called an adjacent pair when there is a node v such that d  In(v) and e  Out(v).

Outgoing edges from s are called data-generating edges. Abbreviate |Out(s)| as , which represents the (fixed) data generating rate from the source. Assume an ordering on edges in E led by data-generating edges.

A sink means a non-source node v to which there are  edge-disjoint paths from s. The number of sinks in the network will be denoted by .

Let denote a finite field, which represents the symbol alphabet, and _q the finite field with q elements. Let P be a PID, which represents the general ensemble of data units. In conventional network coding, P = and in convolutional network coding, P = [(D)].

In a network, a P-linear network code (P-LNC), denoted by (k_d,e), assigns a coding coefficient k_d,e  P to every pair (d, e) of edges such that k_d,e = 0 when (d, e) is not an adjacent pair. An -CNC means an [(D)]-LNC (k_d,e) with k_d,e  [D]  [(D)].

A P-LNC is said to be normal if it determines a unique set of coding vectors. Normality of a LNC is a prerequisite for the notion of data propagation via the code. In a network with cycles, not every P-LNC is normal. A sufficient condition stated in for normality of a P-LNC (k_d,e) is that det(I_|E|  [k_d,e]_d,eOut(s)) is a unit in P, where [k_d,e]_d,eOut(s) is a square matrix with rows and columns indexed by E\Out(s). The conditions for a CNC to be normal are discussed in and . In particular, a causal CNC is normal.

Definition . A delay function t in a network assigns a non-negative integer to every adjacent pair (d, e) such that, along every cycle, there is at least one pair (d, e) with t(d, e) > 0. An -CNC is said to be t-causal if the coding coefficient for every adjacent pair (d, e) is divisible by z^{t(d, e)}.

In an acyclic network, every -LNC is naturally a t-causal -CNC with scalar coding coefficients in [D], where t is a zero function.

Proposition (). A causal -CNC is normal.

Example. For succinctness, all illustrations of networks in the paper will omit the source node s. Figure depicts the coding coefficients (k_d,e) of an ₂-CNC in the Shuttle Network . The code is not normal. However, given an arbitrary delay function t, the t-causal ₂-CNC (k_d,eD^t(d,e)) becomes normal.

Definition . A normal P-LNC with the coding vectors f_e is called a P-linear multicast when rank_P(f_e: eIn(v)) =  for each sink v. A linear multicast is optimal in the sense that all sinks can get enough information to recover the source message.

Delay Invariant Convolutional Network Codes

Figure . An ��₂-CNC in the Shuttle Network is prescribed by coding coefficients k_d,e. It is not normal, because there does not exist a set of coding vectors for (k_d,e). However, given an arbitrary delay function t, the ₂-CNC (k_d,eD^t(d,e)) becomes normal. For instance, if t assigns delay one to (e₇, e₃), (e₉, e₅), (e₁₀, e₄), and delay zero to all others, the coding vectors of the t-causal code (k_d,eD^t(d,e)) are f_e1 = f_e3 = (1 0)^T, f_e2 = f_e10 = (0 1)^T, f_e4 = f_e5 = f_e6 =, f_e7 = f_e8 = f_e9 =. Consequently, it qualifies as a delay invariant ��₂-CNC.

A causal -convolutional multicast is always affiliated with some delay function t. Therefore, the function t is always known in advance for code construction. However, when t is changed due to some unexpected reason, the already deployed convolutional multicast is not necessarily optimal anymore. For instance, consider the network depicted in Figure , and a delay function t which assigns delay one to (e₅, e₃), (e₈, e₄), (e₁₂, e₆), (e₁₃, e₈), (e₉, e₁₀), and delay zero to all others. If the efficient algorithm of is adopted to construct a t-causal -convolutional multicast (k_d,eD^t(d,e)), a possible resulting code is prescribed in Figure by nonzero k_d,e. In particular, the coding vectors for e₄ and e₁₂ are, respectively, and . However, if the delay function t is changed to assign delay one to (e₆, e₇) and delay zero to (e₈, e₄), then the new t-causal -CNC (k_d,eD^t(d,e)) is no longer a convolutional multicast, because the coding vectors for e₄ and e₁₂ become identical, i.e., , and thus sink t₁ cannot reconstruct both data streams. Therefore, under the new function t, the code (k_d,e) has to be redesigned in order to make it optimal. Hence, we propose a type of CNC that is optimal with respect to an arbitrary delay function.

Definition . An -CNC (k_d,e) is called a delay invariant -CNC (DI--CNC) if for any delay function t, the code (k_d,eD^t(d,e)) is a t-causal -convolutional multicast.

As an example, the ₂-CNC depicted in Figure is a DI-₂-CNC. One of the merits of DI-CNC is that the code design is independent of delay functions. One possible design of a DI-CNC is to construct an -linear multicast.

Proposition . Every -linear multicast is a DI--CNC.

Proof. Let (k_d,e) be an -linear multicast with coding vectors f_e. Given a delay function t, the t-causal -CNC (k_d,eD^t(d,e)) is normal by Proposition . Let f_e be coding vectors determined by (k_d,eD^t(d,e)). Define a homomorphism m that projects [(D)] onto by mapping D to 1. Applying componentwise, m extends to a mapping from [(D)]^ to ^. The code (k_d,eD^t(d,e)) is an -convolutional multicast because for every sink v,

(f_e:eIn(v))≥(m(f_e): eIn(v))

= (f_e: eIn(v)) = . ∎

Even though a source always generates a time sequence of messages to be propagated over a network, when the network is acyclic, a LNC is always assumed to ignore the issue of data communication delay and deal with each single message individually. One reason is that upstream-to-downstream ordering of nodes enables buffering, pipelining, and resulting concerted synchronization among all nodes so that the encoding and transmission of a message is independent of sequential messages. This facilitates the model of zero delay function. From another perspective justified by Proposition , even if nonzero network delays are taken into account, the design of a field-based optimal LNC still suffices to induce an optimal LNC in the combined space-time domain.

Proposition guarantees the existence of a DI--CNC when is sufficiently large. In fact, we can say more.

Theorem . In any network, there exists a DI--CNC, with every polynomial coding coefficient of degree at most O(|E|²log_p|E|), where p is the characteristic of .

Proof. The key is to establish a homomorphism from [D] onto an appropriate extension field  of such that infinitely many delays can be mapped to a finite number of values in . It then suffices to show the existence of a certain -LNC which can induce a DI--CNC. See Appendix for details. ∎

(a) (b)
Figure . (a) The given network  contains a cycle. (b) The associated acyclic network  in which the bottom layer nodes qualify as sinks. Every ��-linear multicast on  subject to (1) induces a delay invariant convolutional multicast on  via .

Corollary . Consider an -CNC with coding coefficients k_d,e independently and uniformly selected from those polynomials in [D] with degrees smaller than d. When p^d > (2(p+1)d)^|E|2, where p is the characteristic of , the probability for the code to be a DI-CNC is at least .

Proof. See Appendix. ∎

In comparison, random coding constructs a causal _q-convolutional multicast with respect to a delay function t at probability at least when q^d > .

Efficient Deterministic Code Construction

Although DI-CNCs can be generated by random coding, coding coefficients have to be chosen from a sufficiently large set of polynomials so as to guarantee high successful construction probability. Thus, encoding complexity may become very high. In this section, we shall demonstrate that when || ≥ , which is the number of sinks in a network , the deterministic acyclic algorithm of suffices to construct a DI--CNC with scalar coding coefficients, such that the coding complexity becomes much lower:

When is acyclic, the algorithm of directly constructs an -linear multicast, which is naturally a DI--CNC by Proposition . The computational complexity of the algorithm is O(|E|(+)).

When contains cycles, we can associate it with an acyclic network of  sinks via the algorithm below. An -linear multicast subject to a straightforward condition (1) on can then be constructed by the algorithm of , which in turn induces a DI--CNC on via (2). It takes O(|E|³) to construct a DI--CNC.

Algorithm. Given a network , the associated acyclic network  consists of nodes in five layers, which are labeled 0 to 4 from upstream to downstream. The notation for a node carries a subscript indicating the layer. All edges are between adjacent layers.

Layer 0 consists of just the source node.

Corresponding to each edge e  E\Out(s), there is a layer-1 node e₁ and an edge e₍₁₎ from s to e₁. Thus there are |E|– data-generating edges.

Corresponding to each edge e  E, there is a node e₂. When e  E\Out(s), there is also an edge e₍₂₎ from e₁ to e₂. Corresponding to every adjacent pair (d, e) in , there is an edge from e₁ to d₂.

Corresponding to each edge e  E, there is a node e₃ as well as an edge e₍₃₎ from e₂ to e₃.
Figure . Under the delay function t that assigns delay one to (e₅, e₃), (e₈, e₄), (e₁₂, e₆), (e₁₃, e₈), (e₉, e₁₀), and delay zero to all others, the algorithm of can construct an ��-CNC (k_d,e), which is depicted by nonzero coding coefficients. The code (k_d,eD^t(d,e)) is a t-causal convolutional multicast. Nevertheless, (k_d,e) is not a DI-CNC. This is because when t is changed to assign delay one to (e₆, e₇) and delay zero to (e₈, e₄), the new t-causal -CNC (k_d,eD^t(d,e)) has identical coding vectors for e₄ and e₁₂, such that sink t₁ cannot reconstruct both data streams.

Corresponding to each sink v in , there is a node v₄. Arbitrarily take  edge-disjoint paths in that lead from data-generating edges to v. For every e  E, install an edge from e₃ to v₄ unless e  In(v) and is an edge on these paths.

The association of with  is illustrated by Figure . The reference proved that every layer-4 node in  is a sink. Moreover, it justified that the algorithm of is able to construct an -linear multicast on subject to the following

(1)The coding coefficient is either 0 or 1 for every adjacent pair in the form of (e₍₁₎, x). The coding coefficient is 1 for every adjacent pair in the form of (e₍₁₎, e₍₂₎) or (e₍₂₎, e₍₃₎).

Proposition . Every -linear multicast (k_x,y) on subject to (1) induces a DI--CNC (k_d,e) on via



Proof. Let t be an arbitrary delay function on , and t a delay function on such that t(x, y) = t(d, e) if x = and y = d₍₃₎ for some adjacent pair (d, e) in . Else, t(x, y) = 0. According to Proposition , the code (k_x,yD^t(x,y)) is a t-causal -convolutional multicast. Let f_e denote the coding vector of edge e₍₃₎ for the code (k_x,yD^t(x,y)) on . Note that [f_e]_eE\Out(s) = _{}[k_d,e]_d,eIn(s). Since the -CNC (k_d,eD^t(d,e)) on is t-causal, it is also normal by Proposition , which implies det(_{}[k_d,e]_d,eIn(s)) ≠ 0. As a result, (f_e: e  E\Out(s)) = , and hence Theorem 20 in may be applied to prove (k_d,eD^t(d,e)) in to be a t-causal -convolutional multicast on . ∎

Summary

The coding coefficients k_d,e of a convolutional network code (CNC) are always selected to be polynomials over a symbol field. When they are implemented in the network, the effective coding coefficients are in fact k_d,eD^t(d,e), where t is a delay function on adjacent pairs of edges modeling the combination of any data propagation delays. In this paper, we introduce the concept of delay invariant CNCs (DI-CNCs), which are optimal with respect to any delays. In particular, a CNC (k_d,e) is said to be delay invariant if associated with any delay function t, the resultant CNC (k_d,eD^t(d,e)) is always optimal, i.e., a convolutional multicast. The main result in this paper shows the existence of a DI-CNC over any symbol field, and a random coding technique that can produce a DI-CNC with high probability when coding coefficients are selected from sufficiently many polynomials. Moreover, when the symbol field is no smaller than the number of sinks, a variation of the technique in can adapt the acyclic algorithm of for the construction of a DI-CNC with scalar coding coefficients. The DI-CNC constructed by the deterministic algorithm thus has much lower encoding complexities compared with the one generated by random coding. However, even in an acyclic network, it is still unclear whether there is a polynomial time algorithm for DI-CNC construction over a smaller symbol field, for instance the binary field. Any investigation along this line is very intriguing.

Acknowledgment

The authors appreciate helpful discussions with Pak Hou Che, Chung Chan and Xunrui Yin.

References

R. Alshwede, N. Cai, S.-Y. R. Li and R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, pp. 1204-1216, Feb., 2000.

N. Cai, W. Guo, “The conditions to determine convolutional network coding on matrix representation,” in Netcod, Lausanne, Switzerland, Jun., 2009.

E. Erez, M. Feder, “Efficient Network Code Design for Cyclic Networks,” IEEE Trans. Inf. Theory, vol. 56, no. 8, pp. 3862-3878, Aug., 2010.

C. Fragouli and E. Soljanin, “A connection between network coding and convolutional codes,” Proc. Int. Conf. Commun. (ICC), Paris, France, Jun. 2004, vol. 2, pp. 661-666.

T. Ho, M. Médard, R. Koetter, D. R. Karger, M. Effros, J. Shi, B. Leong, “A random linear network coding approach to multicast,” IEEE Trans. Inf. Theory, vol. 52, no. 10, pp. 4413-4430, Oct., 2006.

S. Jaggi, M. Effros, T. Ho, and M. Médard, “On linear network coding,” 42nd Allerton Conf. Commun. Control and Comput., Monticello, IL, Sep. 2004.

S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, “Polynomial time algorithms for multicast network code construction,” IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1973-1982, Jun., 2005.

R. Koetter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Trans. Netw., vol. 11, No. 5, pp. 782-795, Oct., 2003.

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.

S.-Y. R. Li and R. W. Yeung, “On convolutional network coding,” Proc. of ISIT, pp. 1743-1747, Seattle, USA, July, 2006.

S.-Y. R. Li and Q. T. Sun, “Network coding theory via commutative algebra,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 403-415, Jan. 2011.

S.-Y. R. Li and Q. T. Sun, “Linear network coding: theory and algorithms,” Proc. of the IEEE, vol. 99, no. 3, Mar. 2011.

R. W. Yeung, S.-Y. R. Li, N. Cai, and Z. Zhang, Network Coding Theory. Boston, MA: Now Publishers, 2006.

Appendix. Proof of Theorem and

Convention. For a normal P-LNC (k_d,e), we adopt the abbreviations

A_k = [k_d,e]_{dIn(s),eIn(s)}, B_k = _{} [k_d,e]_d,eIn(s).

Then, the coding vector f_e for e  E\In(s) can be represented by

f_e = ,

where Adj() means the adjugate of a square matrix, and u_e an (|E|)-dim column vector indexed by E\In(s) such that the entry labeled by e is 1 and all others are 0.

For a subfield _p of and an element   , denote by _p() the smallest subfield of containing _p and . ∎

Now associate every adjacent pair (d, e) with an indeterminate x_d,e. Let [D][] denote the polynomial ring in these indeterminates over [D]. Write x_d,e = 0 when (d, e) is not an adjacent pair. For every sink v, select  edge-disjoint paths from data-generating edges to  distinct edges belonging to In(v). Denote by P_v the juxtaposition of u_e, where e is among the said  distinct edges in In(v). Moreover, given a delay function t, let M_v(t) denote the |E||E| matrix

.

In order to qualify an -CNC (k_d,e) as a DI-CNC, it suffices to show that

1. 
   Given any delay function t, the evaluation of det(M_v(t)) at x_d,e = k_d,e is not 0  [D] for all sinks v.
   

To justify this, consider the t-causal -CNC (h_d,e), where h_d,e = k_d,eD^t(d,e). By Proposition , the code is normal, and hence det(B_h) ≠ 0 and det(Adj(B_h)) ≠ 0. Moreover, similar to the proof of Lemma 1 in , because



if ≠0, then det(A_hAdj(B_h)P_v)≠0, and thus

rank_��[(D)](f_e: eIn(v)) = rank_��[(D)](A_hAdj(B_h)[u_e]_eIn(v)) = .

First take = ₂ and let m be the integer such that 3^m ≥ |E|²log₂|E| > 3^m–1, where  is a constant subject to Define a homomorphism : [D][][] that fixes as well as indeterminates x_d,e, and maps D to , where  is an element in of order and ₂() = . Lemma asserts the existence of . Applying componentwise, the homomorphism  also extends to a mapping from matrices over [D][] to matrices over . Because  has order , for each sink v,

|({M_v(t): t is a delay function})| < .

Consequently, the highest degree of every indeterminate in the polynomial _{t:delay function}(det(M_v(t))) is less than . Therefore, when a subset F  has more than elements, there exist values k_d,e  F such that the evaluation of

_{v: sink}_{t: delay function}(det(M_v(t)))

at x_d,e = k_d,e is not 0  . Since

the choice of such F is possible. Let P denote the set of those polynomials in [D] that have degrees smaller than 23^m = O(|E|²log₂|E|). Since ₂() = , the minimal polynomial of  over has degree 23^m. Therefore, (P) = , and the ₂-CNC with coding coefficients k_d,e = P ^–1(k_d,e) abides by (1). In order to show under = ₂, redefine m to be the smallest integer such that 23^m ≥ d > 23^{m –1}. Let P denote the set of those polynomials in [D] that have degrees smaller than d. Note that the polynomial _v:sink_{t:delayfunction} (det(M_v(t))) over is of degree less than |E|, and the highest degree of every indeterminate in it is less than . Thus, Lemma 4 in asserts that when indeterminates x_d,e are independently and uniformly assigned to be values k_d,e in (P)  ,

Pr(_v:sink_{t:delayfunction}(det(M_v(t)) ≠ 0) >

Consequently, when coding coefficients of an ₂-CNC are independently and uniformly chosen from P ^–1(k_d,e), the probability for the code to be delay invariant is at least < (Since 5d > 3^m+1.)

Take = _p, where p is an odd prime number, and let m be the integer such that 2^m ≥ |E|²log_p|E| ≥ 2^m–1, where  is a constant subject to Define a homomorphism : [D]  that fixes and maps D to , where  is of order 2^m(p + (–1)^(p+1)/2) and _p() = . Lemma asserts the existence of such . By an argument similar to the case when = ₂, we can prove Theorem and under = _p.

Take = _q, where q is a positive integer power of a prime p. Let D and D, respectively, represent the unit time to carry one data symbol in _p and _q. Define a homomorphism  from _p[(D)] into _q[(D)] via fixing _p and mapping D to D. Because the mapping  is one-to-one, given a DI-_p-CNC (k_d,e) and a delay function t, ((k_d,eD^t(d,e))) qualifies as an _q-convolutional multicast too. ∎

Lemma . In , where m ≥ 0, there exists an element  of order such that ₂() = .

Proof. Let  be a primitive element in . First, divides , because by Euler's totient theorem, . Let  = and ��₂() = , where either

, 0  i  m, or

, 0  i  m.

Since  has order and , . Thus, d ≠  0  i  m, because . Assume d = , 0  i  m. Because for all i < m, in order to show i = m, it suffices to prove . When m = 1, it is trivially true that 3 is not divisible by 9. When m > 1, note that . By the induction hypothesis, . Therefore, if , then would be divisible by 9. However, this is impossible because

.

Lemma . Let p be a prime of odd characteristic. In , m ≥ 1, there exists an element  of order such that _p() = .

Proof. Let  be a primitive element in . First, , since

.

Assume . Let  = and () = , k  m. Since  has order and , divides , which implies

.

Moreover, because , the factors , 0  i < k, can be divisible by 2 but not by 4. Therefore, k = m.

The case when can be shown analogously such that () = , where  = .