# A Computational Perspective on Network Coding

Authors: Qin Guo; Mingxing Luo; Lixiang Li; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

From the perspectives of graph theory and combinatorics theory we
obtain some new upper bounds on the number of encoding nodes, which can characterize
the coding complexity of the network coding, both in feasible acyclic and cyclic multicast
networks. In contrast to previous work, during our analysis we first investigate the simple
multicast network with source rateh=2, and then h≥2. We find that for feasible acyclic
multicast networks our upper bound is exactly the lower bound given by M. Langberg et al. in 2006. So the gap between their lower and upper bounds for feasible acyclic multicast
networks does not exist. Based on the new upper bound, we improve the computational
complexity given by M. Langberg et al. in 2009. Moreover, these results further support
the feasibility of signatures for network coding.


---

## Body

## 1. Introduction

When network coding was firstly used by Ahlswede et al. [1], the node produced each of its outgoing packets as an arbitrary combination of its incomings, which is referred to as encoding node. Those functions applied by all nodes in the network specify the different network codes, such as linear network codes and random linear network codes via linear function and random linear function, respectively [1–3]. In [3], Li et al. showed that linear network codes are sufficient for achieving the capacity of the network. And in a subsequent work, Koetter and Médard [4] developed an algebraic framework for network coding and studied linear network codes for cyclic networks. Based on this framework, Ho et al. [2] showed that linear network codes can be efficiently constructed through a randomized algorithm. Jaggi et al. [5] presented a deterministic polynomial-time algorithm for finding a feasible network codes in multicast networks. Errors introduced into even a single packet transmitted on the way can propagate and pollute multiple packets making their way to the destination. To prevent the spread of the error packets, signatures for network coding are proposed [6, 7]. Nevertheless, whatever the kind of network codes will be used, the number of encoding nodes plays an important role on the encoding complexity of network coding. In [8, 9], Langberg et al. studied the design of multicast coding networks with a limited number of encoding nodes. And they showed that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by O(h3k2) (h is the source rate and k is the number of terminal nodes) which is independent of the size of the network. And for the general networks, in which there exist cycles, the number of encoding nodes is limited by the size of the minimum feedback link set and bounded by (2B+1)h3k2, where B is the minimum size of a feedback link set.In this paper, from the perspective of graph theory [10] and combinatorics theory [11] we mainly reinvestigate the upper bounds of encoding nodes in simple multicast networks and the computational complexity of constructing network coding on feasible acyclic multicast networks. Similar with [8], we put different colors on the paths from source to different terminal nodes. However, in this paper we investigate the number of encoding nodes instead of nodes on the paths. And we find that our upper bounds are their lower bounds in [8], so our upper bounds are optimal for simple multicast networks. Using this result, we can answer the open question raised in the end of [8]; that is, there donot exist such feasible acyclic multicast networks that the number of encoding nodes are between the lower bound and the upper bound in [8]. Based on these results for acyclic multicast networks, we improve the computational complexity of the deterministic algorithm of constructing network codes given by Langberg et al. in [9].The rest parts of this paper are organized as follows. In Section2 we mainly give some necessary notations and definitions. In Section 3 we reinvestigate the upper bounds of encoding nodes for simple acyclic and cyclic multicast networks, respectively. Some new results on computational complexity of constructing network codes for feasible multicast networks are also given. In the final section, Section 4, some conclusions and future topics are presented.


## 2. Basic Notions and Definitions

Letℕ(G,s,T,h) be a multicast network with a directed graph G, a source node s, a set of terminal nodes T, and source rate h. All links in G are of unit capacity. A network code for a multicast network ℕ(G,s,T,h) is said to be feasible if it allows communication at rate h between s and each terminal node t∈T. We say that ℕ(G,s,T,h) is a feasible multicast network if there exists a feasible network code for ℕ(G,s,T,h).Definition 2.1 (minimal multicast network [8]).
A feasible multicast networkℕ(G,s,T,h) is said to be minimal with respect to link removal if any network ℕ̂(Ĝ,s,T,h) formed from ℕ by deleting a link e from G is no longer feasible.Definition 2.2 (simple multicast network [8]).
A multicast networkℕ(G,s,T,h) is said to be simple if and only if (a) ℕ is feasible; (b) ℕ is minimal with respect to link removal; (c) the total degree of G each node in G is at most 3 (excluding the source and terminal nodes); (d) the terminal nodes in T have no outgoing links.In fact, for each general multicast networkℕ(G,s,T,h) there exists a simple multicast network ℕ̂(Ĝ,s,T̂,h) corresponding to it. And  the construction is computationally efficient and includes the following three steps.Step 1 (replacing terminal nodes).
For each terminal nodeti∈T, we add a new node t̂i to G and connect ti to t̂i by h parallel links. Denote the resulting graph by G1 and the new set {ti∣1≤i≤k} of terminal nodes by T̂. Then, the terminal nodes in T̂ have no outgoing links.Step 2 (reducing degrees).
SupposeG2 is the graph formed from G1 by replacing each node v∈G1,v≠s,v∉T̂ whose degree is more than 3 by a subgraph Γv, constructed as Figure 1. So in G2 there do not exist the nodes with degrees more than 3.Figure 1
(a) A nodev∈G1 with degree larger than 3. (b) The subgraph Γv for the node v in (a).Step 3 (removing links).
LetĜ be any subgraph of G2 such that ℕ̂(Ĝ,s,T̂,h) is minimal with respect to link removal.By Step2, we can learn that the number of encoding nodes in a feasible multicast network is no more than that of the corresponding simple multicast network. In this paper, we let α(ℕ) denote the number of encoding nodes in ℕ.In general communication networks with cycles, there exist feedback links. And we will show that the value ofα(ℕ) in a cyclic network ℕ(G,s,T,h) depends on the size of the minimum feedback link set.Definition 2.3 (minimum feedback link set [12]).
LetG(V,E) be a directed graph. A subset Ê⊆E is referred to as a feedback link set if the graph G′ formed from G by removing all links in Ê is acyclic. A feedback link set of minimum size is referred to as the minimum feedback link set.Given a networkℕ(G,s,T,h), let B denote the minimum size of feedback link set of underlying graph G.


## 3. Main Results

Letei, 1≤i≤h, be the h out links of source node s. Consider that Pri and Pbi (1≤i≤h) have the common starting link ei. And paths Pri and Pbj (i≠j) have different starting links. Let paths set Pi={Pji∣j=1,2,…,k}. In addition, all the paths in the sets {Pi}i=1ni can cover the whole network of G. If some link e belongs to G but any path Pni, then ℕ(G,s,T,h) will not be a simple multicast network, because this contradicts the minimality of ℕ(G,s,T,h).Similar to [8], we also put different colors on the paths from source node s to different terminal nodes. While the color of a link is the same to the color of the path which passes on it. Of course, one link can have several different colors if there are several paths to different terminal nodes passing on it. When all the colors of a link are blotted out, we consider that this link disappears.


### 3.1. New Upper Bounds

In this subsection, we establish the number of encoding nodes instead of nodes on a pair of link-disjoint paths. Since the source rateh may be very large, we investigate pairs of link-disjoint paths to terminal nodes one by one. For example, when investigating the pair of path sets Pi and Pj (1≤i≠j≤h), we only leave all the paths in the two sets Pi and Pj in which the paths have the same starting link ei and ej, respectively, and temporarily ignore other paths in the paths set Pl in which the paths have other starting links el, l≠i,j, see Figure 2. When investigating the number of encoding nodes on the paths in the sets P2 and P4 which have the starting links e2 and e4, respectively, we only leave the paths P12, P14, P22, and P24 (see Figure 2(b)).(a) A simple multicast network. (b) When investigating the number of encoding nodes on the paths in the setsP2 and P4, we ignore other paths which donot start at the links e2 and e4. So the only four paths P12,P14,P22, and P24 are left.
(a)(b)During the following analysis, we first investigate the simple multicast networks withh=2, and then generalize this result to the networks with h≥2. So our method is very different from that given by Langberg et al. in [8].Lemma 3.1.
Letℕ(G,s,T,2) be a simple acyclic multicast network. Then the number of encoding nodes α(ℕ) of ℕ is at most k-1, where k=|T|.Proof.
We prove this result by induction onk. For the base step, we note that a simple multicast network ℕ(G,s,{t1,t2},2) with k=2 has at most one encoding node (see, e.g., Figure 3(a)). If there exist two encoding nodes, then ℕ(G,s,{t1,t2},2) can only be characterized by Figure 3(b) (i.e., Figure 3(b) as a subnetwork of ℕ(G,s,{t1,t2},2)). However, we find that the two links (v1,v3) and (v2,v4) are redundant, since when we delete them, the network is also feasible. It means that Figure 3(b) is not a simple multicast network, and then ℕ(G,s,{t1,t2},2) is not simple which contradicts the assumption above. Similarly, we can prove that more than two encoding nodes are impossible for ℕ(G,s,{t1,t2},2).
For the induction step, we assume thatα(ℕ)≤k-1 for k=3,…,n. Now, we need to prove α(ℕ)≤n for k=n+1. By reduction to absurdity, suppose that α(ℕ)=n+1 for ℕ(G,s,T,2) with k=n+1. Notice that in ℕ(G,s,T,2) there does not exist such a color of pair paths to any terminal: when we blot out this color, two encoding nodes disappear. Assume there exists such a color. Then we can obtain two classes of subnetworks shown in Figure 4. In Figure 4(a), v5 and v6 are two such encoding nodes for terminal t1. For each of v5 and v6, one of the two incoming links has only one red color, such as (v1,v5) and (v4,v6). Otherwise, when we blot out red color, both of v5 and v6 are not encoding nodes anymore at the same time. But we find that the two links (v1,v5) and (v4,v6) are redundant, that is to say this network is not a simple multicast network. Because the messages can be transmitted along the paths (s,v2),(v2,v5),(v5,v7),(v7,t1) and (s,v3),(v3,v6),(v6,v8),(v8,t1) to terminal t1. Similarly, in Figure 4(b), v1 and v3 are two encoding nodes. We find that the blue incoming link of v3 is redundant for this multicast network, because the path P32 can go along the path (s,v6),(v6,v1),(v1,v2),(v2,v3),(v3,v4),(v4,t3). So, when we blot out one color, only one encoding node will disappear, and the corresponding terminal is no longer a terminal. Then in the rest simple multicast network there exist n terminals and α(ℕ)=n. This contradicts the assumption α(ℕ)≤n-1 for k=n.
Therefore, the number of encoding nodes in any simple acyclic multicast networkℕ(G,s,T,2) is no more than k-1.(a) A simple multicast network with two terminals has only one encoding node; (b) A feasible multicast network with two terminals has two encoding nodes. But it is not a simple multicast network, because if we delete(v1,v3) and (v2,v4), this multicast network is also feasible.
(a)(b)(a) One subnetwork of a feasible acyclic multicast network, in which if we blot out the red color, two encoding nodesv5 and v6 disappear. Here, at least one color path passes through the bold black links; (b) The other subnetwork in which if we blot out red color, two encoding nodes v1 and v3 disappear.
(a)(b)By the decomposition and combination of a simple acyclic multicast network, we can generalize this result to the multicast networks with anyh≥2.Theorem 3.2.
Letℕ(G,s,T,h) be a simple acyclic multicast network. Then,
(3.1)α(ℕ)≤(k-1)h(h-1)2=O(h2k).Proof.
We investigate a pair of path setsPi and Pj for all terminals. And all of the paths in these two sets compose a subnetwork ℕi,j(Gi,j,s,T,2) of ℕ(G,s,T,h) which is also a simple multicast network. By Lemma 3.1, there exist at most k-1 encoding nodes in ℕi,j(Gi,j,s,T,2). And each encoding node in ℕ(G,s,T,h) will be counted in some subnetwork ℕi,j(Gi,j,s,T,2). Suppose that an encoding node v is not counted and its two incoming links are e1 and e2. By the minimality of ℕ(G,s,T,h), e1 and e2 must be on some paths, which belong to the path sets Pm and Pn, respectively. Then v, as an encoding node, is in the corresponding subnetwork ℕm,n(Gm,n,s,T,2). This contradicts the assumption above. In ℕ(G,s,T,h) there are h(h-1)/2 pairs of paths; that is, there are h(h-1)/2 such subnetworks in all, so
(3.2)α(ℕ)≤(k-1)h(h-1)2=O(h2k).Being different from the results that the numbers of encoding nodes fork=2 and k>2 have different descriptions in [8], this theorem is a unified presentation for all simple acyclic multicast networks. Notice that by Lemma 12 of [8], each feasible multicast network ℕ(G,s,T,h) corresponds to a simple multicast network ℕ̂(Ĝ,s,T̂,h). Moreover, the minimum number of encoding nodes required for ℕ(G,s,T,h) is no more than that for ℕ̂(Ĝ,s,T̂,h). Therefore, by Lemma 12 of [8] and Theorem 3.2 above we can show the existence of network codes with at most (k-1)h(h-1)/2 encoding nodes for any feasible acyclic multicast network.Theorem 3.3.
LetG be an acyclic graph and ℕ(G,s,T,h) be a feasible multicast network. Then, there exists a feasible network code with at most (k-1)h(h-1)/2 encoding nodes.From the investigation above, we can find that our method is very different from that given by Langberg et al. in [8]. On one hand, they investigated the simple multicast networks based on the number of terminal nodes, classified by k=2 and k>2, and got two different results for these two kinds of networks. In this paper, we classify the simple multicast networks by source rate h. One is with h=2, and the other is with h>2. We first investigate the simple multicast networks with h=2, then generalize this result to the networks with any h≥2.On the other hand, by scaling law Langberg et al. estimated the number of nodes instead of encoding nodes on the three kinds of paths: red path Pr, blue path Pb and green path Pg (defined in [8]). And they proved that there exists at most one node that belongs to all three paths Pr,Pb, and Pg. Though each encoding node belongs to all these color paths, there exist such nonencoding nodes that belong to all three color paths. For example, see Figure 3 (a). By the definitions of three color paths in [8], paths Pr1={(s,v1),(v1,t1)} and Pr2={(s,v2),(v2,v3),(v3,v4),(v4,t1)} are two red paths, paths Pb1={(s,v1),(v1,v3),(v3,v4),(v4,t2)} and Pb2={(s,v2),(v2,t2)} are two blue paths, and paths Pg1={(t1,v1),(v1,v3),(v3,v2),(v2,t2)} and Pg2={(t1,v4),(v4,t2)} are two green paths. v1 belongs to three color paths Pr1, Pb1, and Pg1, v2 belongs to Pr2, Pb2, and Pg1, v3 belongs to Pb1,  Pr2, and Pg1, and v4 belongs to Pb1, Pr2, and Pg2. Obviously, only v3 is an encoding node, but v1,  v2, and v4. This shows that there exist nonencoding nodes that belong to all three paths of different colors. So they get a higher upper bound. In our paper, based on the properties of encoding nodes and simple acyclic multicast networks, we investigate the number of encoding nodes in simple acyclic multicast networks directly and obtain the new upper bound. And we find that our upper bound is just their lower bound. Therefore, the gap of hk between their lower and upper bounds for acyclic networks is inexistent which is the answer to the open question in the end of [8].Next, we consider the networks with cycles. Based on Lemma3.1, we also establish the number of encoding nodes in simple cyclic multicast networks. Before investigating general simple multicast networks, we first study the ones with h=2.Lemma 3.4.
Letℕ(G,s,T,2) be a simple cyclic multicast network and B be the size of the minimal feedback link set in ℕ. Then, the number of encoding nodes α(ℕ)≤(k-1)(B+1).Proof.
By Lemma3.1, if there are no feedback links, then there exist at most k-1 encoding nodes in ℕ(G,s,T,2), and if we add one feedback link in ℕ(G,s,T,2), then there will exist at most B(k-1) additional encoding nodes. Because the path on which the feedback link passes does not intersect with the paths with the same starting edge. Otherwise, there will exist redundant links for the simple multicast networks. See Figure 5, for example, in which the black path from v1 to v12 is a feedback link. The paths P31 and P21 have common starting link e1, and they have the nodes of intersection: v4 and v10. Since the path from source node s to t3 can go along with the path {(s,v10),(v10,v11),(v11,v12),(v12,v13),(v13,v14),(v14,t3)}, the black link from v1 to v10 is redundant. And this contradicts the minimality of the simple multicast network.Figure 5
A simple cyclic multicast network in which pathsP31 and P21 have common nodes.In the following theorem, we establish the upper bounds on the size ofα(ℕ) for simple cyclic multicast networks with source rate h≥2.Theorem 3.5.
Letℕ(G,s,T,h) be a simple cyclic multicast network. Then
(3.3)α(ℕ)≤(B+1)(k-1)h(h-1)2=O((B+1)h2k).Proof.
By Lemma3.4, the proof is similar with that of Theorem 3.2.We can find that ifB=0, that is to say there do not exist feedback links in ℕ(G,s,T,h), in Lemma 3.4 and Theorem 3.5, then they will degenerate into Lemma 3.1 and Theorem 3.2, respectively.By comparing our Theorem3.2 with Theorem 6 in [8], we find that their lower bound O(h2k) is indeed the real upper bound of the number of encoding nodes in simple acyclic multicast networks. So our upper bound is the optimal one. Moreover, by using Lemma 3.4 and Theorem 3.2 we have established a much tighter upper bound for cyclic network, shown in Theorem 3.5. In addition, for each encoding node in an arbitrary simple multicast network there exists at least one corresponding nonencoding node at which the joint flows are split. So it is impossible for us to construct a cyclic minimal multicast network with the number of encoding nodes more than |V|/2, where |V| is the total number of nodes in the network. Therefore, their lower bound of O(max(|V|/2,Bh,h2k)) in [8] can also be considered as another upper bound of encoding nodes in cyclic networks.In fact, our these results are further in favor of the feasibility of signatures for network coding. In the scheme of signature for network coding, when an intermediate node is a nonencoding node, the operations are in two steps at this node: (i) verify the signature for incoming packet; (ii) transmit the uncorrupted packet or discard corrupted packet. While at an encoding node, the operations are in four steps: (i) verify the two signatures for incoming packets; (ii) encode the two incoming packet if they are not corrupted, or discard it (or them) when corrupted. (iii) sign the encoded packet; (iv) transmit the signed packet. So the highly consuming signature operations are at the encoding nodes. While, by the results above, the number of encoding node is independent of the size of the network and its upper bound is(B+1)h2k/2 (B=0 when the network is acyclic).


### 3.2. New Computational Complexity of Network Coding Construction

In this subsection, we mainly extend the results on the computational complexity of network coding constructions, shown in [9]. Firstly, we briefly show some notations used in this subsection.For two multicast coding networksℕ(G(V,E),s,T,h) and ℕ̂(Ĝ(V̂,Ê),ŝ,T̂,ĥ), we say that ℕ̂ models ℕ if the following three conditions hold. (i)
ℕ is feasible if and only if ℕ̂ is feasible.(ii)
For any feasible network code𝔽̂(ℕ̂) for ℕ̂, there exists a corresponding network code 𝔽(ℕ) for ℕ that includes the same number of encoding nodes or less.(iii)
Given a feasible network code𝔽̂(ℕ̂) for ℕ̂, the corresponding network code 𝔽(ℕ) for ℕ can be found through an efficient procedure whose running time is bounded by O(|E|+|Ê|).In addition, we useℕ′(G′,s,T,h), ℕ*(G*,s,T,h), and ℕ̂(Ĝ,s,T,h) to denote three auxiliary coding networks, all of which model ℕ(G,s,T,h). They are constructed by algorithms Procedure EXPAND, Algorithm MIN-GLOBAL, and Procedure SHRINK (shown in [9] for details) as the following steps.Step 1.
ℕ′(G′,s,T,h) = Pro. EXPAND (ℕ(G,s,T,h)).Step 2.
ℕ*(G*,s,T,h) = Alg. MIN-GLOBAL (ℕ′(G′,s,T,h)).Step 3.
ℕ̂(Ĝ,s,T,h) = Pro. SHRINK (ℕ*(G*,s,T,h)).From the proofs of Theorems6 and 7 in [9], we find that their upper bound O(h3) for an acyclic multicast network with two terminal nodes has greatly influenced these two theorems. Based on our new results on the upper bound of encoding nodes in feasible multicast networks, we give two farther results as follows.Theorem 3.6.
Letℕ*(G*(V*,E*),s,T,h) be the coding network returned by Algorithm Min-Global(ℕ′(G′,s,T,h)). Let V¯* be the subset of V*∖T that includes nodes of in-degree two and E¯* be the set of incoming links of nodes in V¯*. Then, it holds that |E¯*|=O(h2k).Proof.
By Theorems 1, the proof follows the same line as that of Theorem6 in [9].Theorem 3.7.
Letℕ(G,s,T,h) be an acyclic feasible coding network. Then there exists a deterministic algorithm that computes a network code 𝔽(ℕ) in time O(|E|kh+|V|k2h2+h3k2(k+h)). Moreover, the number of encoding nodes in 𝔽(ℕ) is bounded by O(h2k).Proof.
By Theorems3.2 and 3.6, the proof follows the same line as that of Theorem 7 in [9].So the complexityO(|E|kh+|V|k2h2+h3k2(k+h)) of computing a feasible network code 𝔽(ℕ) in Theorem 7 of [9] is in fact O(|E|kh+|V|k2h2+h4k3(k+h)) and their bound on the number of encoding nodes O(h3k2) in this feasible network code is really O(h2k). This is the best known running time for constructing network code.The following two theorems are about integral and fractional network codes. In an integral network, codes packets cannot be split and have to be sent through the network in one piece. In fractional network codes, each packet can be split into a number of smaller packets, each of which is sent over different paths. We assume that all integral packets are elements in finite field GF(2n), which implies that each such packet can be represented by n bits. m-Fractional Network Code 𝔽m(ℕ)), let ℕ(G,s,T,h) be a feasible coding network, n be the size of the integral packet, and let m be a divisor of n. Suppose ℕm(Gm,s,T,mh) be the coding network in which Gm is formed from G by splitting each link e in G of bit capacity ce into m parallel links e1,…,em of bit capacity ce/m. Let 𝔽(ℕm) be a feasible integral network code for ℕm(Gm,s,T,mh) over finite field GF(2)n/m. We refer to 𝔽(ℕm) as a feasible m-fractional network code 𝔽m(ℕ) for ℕ(G,s,T,h).Theorem 3.8.
Letℕ(G,s,T,h) be a feasible acyclic network. Then a feasible integral network code 𝔽(ℕ) can be constructed in time |V|O(h4k2).Proof.
By Theorem3.2, the proof follows the same line as that of Theorem 11 in [9].By this theorem, we can find that the complexity|V|O(h6k4) of constructing a feasible integral network code 𝔽(ℕ) in Theorem 11 of [9] is |V|O(h4k2).Theorem 3.9.
Letℕ(G,s,T,h) be a feasible acyclic network. Then a feasible m-fractional network node 𝔽m(ℕ) for ℕ can be constructed in time |V|O(h2k).Proof.
By Theorem3.2, the proof is similar to that of Theorem 16 in [9].From this result, we can find that the complexity|V|O(h3k2) of constructing a feasible m-fractional network code in Theorem 16 of [9] is actually |V|O(h2k).


## 3.1. New Upper Bounds

In this subsection, we establish the number of encoding nodes instead of nodes on a pair of link-disjoint paths. Since the source rateh may be very large, we investigate pairs of link-disjoint paths to terminal nodes one by one. For example, when investigating the pair of path sets Pi and Pj (1≤i≠j≤h), we only leave all the paths in the two sets Pi and Pj in which the paths have the same starting link ei and ej, respectively, and temporarily ignore other paths in the paths set Pl in which the paths have other starting links el, l≠i,j, see Figure 2. When investigating the number of encoding nodes on the paths in the sets P2 and P4 which have the starting links e2 and e4, respectively, we only leave the paths P12, P14, P22, and P24 (see Figure 2(b)).(a) A simple multicast network. (b) When investigating the number of encoding nodes on the paths in the setsP2 and P4, we ignore other paths which donot start at the links e2 and e4. So the only four paths P12,P14,P22, and P24 are left.
(a)(b)During the following analysis, we first investigate the simple multicast networks withh=2, and then generalize this result to the networks with h≥2. So our method is very different from that given by Langberg et al. in [8].Lemma 3.1.
Letℕ(G,s,T,2) be a simple acyclic multicast network. Then the number of encoding nodes α(ℕ) of ℕ is at most k-1, where k=|T|.Proof.
We prove this result by induction onk. For the base step, we note that a simple multicast network ℕ(G,s,{t1,t2},2) with k=2 has at most one encoding node (see, e.g., Figure 3(a)). If there exist two encoding nodes, then ℕ(G,s,{t1,t2},2) can only be characterized by Figure 3(b) (i.e., Figure 3(b) as a subnetwork of ℕ(G,s,{t1,t2},2)). However, we find that the two links (v1,v3) and (v2,v4) are redundant, since when we delete them, the network is also feasible. It means that Figure 3(b) is not a simple multicast network, and then ℕ(G,s,{t1,t2},2) is not simple which contradicts the assumption above. Similarly, we can prove that more than two encoding nodes are impossible for ℕ(G,s,{t1,t2},2).
For the induction step, we assume thatα(ℕ)≤k-1 for k=3,…,n. Now, we need to prove α(ℕ)≤n for k=n+1. By reduction to absurdity, suppose that α(ℕ)=n+1 for ℕ(G,s,T,2) with k=n+1. Notice that in ℕ(G,s,T,2) there does not exist such a color of pair paths to any terminal: when we blot out this color, two encoding nodes disappear. Assume there exists such a color. Then we can obtain two classes of subnetworks shown in Figure 4. In Figure 4(a), v5 and v6 are two such encoding nodes for terminal t1. For each of v5 and v6, one of the two incoming links has only one red color, such as (v1,v5) and (v4,v6). Otherwise, when we blot out red color, both of v5 and v6 are not encoding nodes anymore at the same time. But we find that the two links (v1,v5) and (v4,v6) are redundant, that is to say this network is not a simple multicast network. Because the messages can be transmitted along the paths (s,v2),(v2,v5),(v5,v7),(v7,t1) and (s,v3),(v3,v6),(v6,v8),(v8,t1) to terminal t1. Similarly, in Figure 4(b), v1 and v3 are two encoding nodes. We find that the blue incoming link of v3 is redundant for this multicast network, because the path P32 can go along the path (s,v6),(v6,v1),(v1,v2),(v2,v3),(v3,v4),(v4,t3). So, when we blot out one color, only one encoding node will disappear, and the corresponding terminal is no longer a terminal. Then in the rest simple multicast network there exist n terminals and α(ℕ)=n. This contradicts the assumption α(ℕ)≤n-1 for k=n.
Therefore, the number of encoding nodes in any simple acyclic multicast networkℕ(G,s,T,2) is no more than k-1.(a) A simple multicast network with two terminals has only one encoding node; (b) A feasible multicast network with two terminals has two encoding nodes. But it is not a simple multicast network, because if we delete(v1,v3) and (v2,v4), this multicast network is also feasible.
(a)(b)(a) One subnetwork of a feasible acyclic multicast network, in which if we blot out the red color, two encoding nodesv5 and v6 disappear. Here, at least one color path passes through the bold black links; (b) The other subnetwork in which if we blot out red color, two encoding nodes v1 and v3 disappear.
(a)(b)By the decomposition and combination of a simple acyclic multicast network, we can generalize this result to the multicast networks with anyh≥2.Theorem 3.2.
Letℕ(G,s,T,h) be a simple acyclic multicast network. Then,
(3.1)α(ℕ)≤(k-1)h(h-1)2=O(h2k).Proof.
We investigate a pair of path setsPi and Pj for all terminals. And all of the paths in these two sets compose a subnetwork ℕi,j(Gi,j,s,T,2) of ℕ(G,s,T,h) which is also a simple multicast network. By Lemma 3.1, there exist at most k-1 encoding nodes in ℕi,j(Gi,j,s,T,2). And each encoding node in ℕ(G,s,T,h) will be counted in some subnetwork ℕi,j(Gi,j,s,T,2). Suppose that an encoding node v is not counted and its two incoming links are e1 and e2. By the minimality of ℕ(G,s,T,h), e1 and e2 must be on some paths, which belong to the path sets Pm and Pn, respectively. Then v, as an encoding node, is in the corresponding subnetwork ℕm,n(Gm,n,s,T,2). This contradicts the assumption above. In ℕ(G,s,T,h) there are h(h-1)/2 pairs of paths; that is, there are h(h-1)/2 such subnetworks in all, so
(3.2)α(ℕ)≤(k-1)h(h-1)2=O(h2k).Being different from the results that the numbers of encoding nodes fork=2 and k>2 have different descriptions in [8], this theorem is a unified presentation for all simple acyclic multicast networks. Notice that by Lemma 12 of [8], each feasible multicast network ℕ(G,s,T,h) corresponds to a simple multicast network ℕ̂(Ĝ,s,T̂,h). Moreover, the minimum number of encoding nodes required for ℕ(G,s,T,h) is no more than that for ℕ̂(Ĝ,s,T̂,h). Therefore, by Lemma 12 of [8] and Theorem 3.2 above we can show the existence of network codes with at most (k-1)h(h-1)/2 encoding nodes for any feasible acyclic multicast network.Theorem 3.3.
LetG be an acyclic graph and ℕ(G,s,T,h) be a feasible multicast network. Then, there exists a feasible network code with at most (k-1)h(h-1)/2 encoding nodes.From the investigation above, we can find that our method is very different from that given by Langberg et al. in [8]. On one hand, they investigated the simple multicast networks based on the number of terminal nodes, classified by k=2 and k>2, and got two different results for these two kinds of networks. In this paper, we classify the simple multicast networks by source rate h. One is with h=2, and the other is with h>2. We first investigate the simple multicast networks with h=2, then generalize this result to the networks with any h≥2.On the other hand, by scaling law Langberg et al. estimated the number of nodes instead of encoding nodes on the three kinds of paths: red path Pr, blue path Pb and green path Pg (defined in [8]). And they proved that there exists at most one node that belongs to all three paths Pr,Pb, and Pg. Though each encoding node belongs to all these color paths, there exist such nonencoding nodes that belong to all three color paths. For example, see Figure 3 (a). By the definitions of three color paths in [8], paths Pr1={(s,v1),(v1,t1)} and Pr2={(s,v2),(v2,v3),(v3,v4),(v4,t1)} are two red paths, paths Pb1={(s,v1),(v1,v3),(v3,v4),(v4,t2)} and Pb2={(s,v2),(v2,t2)} are two blue paths, and paths Pg1={(t1,v1),(v1,v3),(v3,v2),(v2,t2)} and Pg2={(t1,v4),(v4,t2)} are two green paths. v1 belongs to three color paths Pr1, Pb1, and Pg1, v2 belongs to Pr2, Pb2, and Pg1, v3 belongs to Pb1,  Pr2, and Pg1, and v4 belongs to Pb1, Pr2, and Pg2. Obviously, only v3 is an encoding node, but v1,  v2, and v4. This shows that there exist nonencoding nodes that belong to all three paths of different colors. So they get a higher upper bound. In our paper, based on the properties of encoding nodes and simple acyclic multicast networks, we investigate the number of encoding nodes in simple acyclic multicast networks directly and obtain the new upper bound. And we find that our upper bound is just their lower bound. Therefore, the gap of hk between their lower and upper bounds for acyclic networks is inexistent which is the answer to the open question in the end of [8].Next, we consider the networks with cycles. Based on Lemma3.1, we also establish the number of encoding nodes in simple cyclic multicast networks. Before investigating general simple multicast networks, we first study the ones with h=2.Lemma 3.4.
Letℕ(G,s,T,2) be a simple cyclic multicast network and B be the size of the minimal feedback link set in ℕ. Then, the number of encoding nodes α(ℕ)≤(k-1)(B+1).Proof.
By Lemma3.1, if there are no feedback links, then there exist at most k-1 encoding nodes in ℕ(G,s,T,2), and if we add one feedback link in ℕ(G,s,T,2), then there will exist at most B(k-1) additional encoding nodes. Because the path on which the feedback link passes does not intersect with the paths with the same starting edge. Otherwise, there will exist redundant links for the simple multicast networks. See Figure 5, for example, in which the black path from v1 to v12 is a feedback link. The paths P31 and P21 have common starting link e1, and they have the nodes of intersection: v4 and v10. Since the path from source node s to t3 can go along with the path {(s,v10),(v10,v11),(v11,v12),(v12,v13),(v13,v14),(v14,t3)}, the black link from v1 to v10 is redundant. And this contradicts the minimality of the simple multicast network.Figure 5
A simple cyclic multicast network in which pathsP31 and P21 have common nodes.In the following theorem, we establish the upper bounds on the size ofα(ℕ) for simple cyclic multicast networks with source rate h≥2.Theorem 3.5.
Letℕ(G,s,T,h) be a simple cyclic multicast network. Then
(3.3)α(ℕ)≤(B+1)(k-1)h(h-1)2=O((B+1)h2k).Proof.
By Lemma3.4, the proof is similar with that of Theorem 3.2.We can find that ifB=0, that is to say there do not exist feedback links in ℕ(G,s,T,h), in Lemma 3.4 and Theorem 3.5, then they will degenerate into Lemma 3.1 and Theorem 3.2, respectively.By comparing our Theorem3.2 with Theorem 6 in [8], we find that their lower bound O(h2k) is indeed the real upper bound of the number of encoding nodes in simple acyclic multicast networks. So our upper bound is the optimal one. Moreover, by using Lemma 3.4 and Theorem 3.2 we have established a much tighter upper bound for cyclic network, shown in Theorem 3.5. In addition, for each encoding node in an arbitrary simple multicast network there exists at least one corresponding nonencoding node at which the joint flows are split. So it is impossible for us to construct a cyclic minimal multicast network with the number of encoding nodes more than |V|/2, where |V| is the total number of nodes in the network. Therefore, their lower bound of O(max(|V|/2,Bh,h2k)) in [8] can also be considered as another upper bound of encoding nodes in cyclic networks.In fact, our these results are further in favor of the feasibility of signatures for network coding. In the scheme of signature for network coding, when an intermediate node is a nonencoding node, the operations are in two steps at this node: (i) verify the signature for incoming packet; (ii) transmit the uncorrupted packet or discard corrupted packet. While at an encoding node, the operations are in four steps: (i) verify the two signatures for incoming packets; (ii) encode the two incoming packet if they are not corrupted, or discard it (or them) when corrupted. (iii) sign the encoded packet; (iv) transmit the signed packet. So the highly consuming signature operations are at the encoding nodes. While, by the results above, the number of encoding node is independent of the size of the network and its upper bound is(B+1)h2k/2 (B=0 when the network is acyclic).


## 3.2. New Computational Complexity of Network Coding Construction

In this subsection, we mainly extend the results on the computational complexity of network coding constructions, shown in [9]. Firstly, we briefly show some notations used in this subsection.For two multicast coding networksℕ(G(V,E),s,T,h) and ℕ̂(Ĝ(V̂,Ê),ŝ,T̂,ĥ), we say that ℕ̂ models ℕ if the following three conditions hold. (i)
ℕ is feasible if and only if ℕ̂ is feasible.(ii)
For any feasible network code𝔽̂(ℕ̂) for ℕ̂, there exists a corresponding network code 𝔽(ℕ) for ℕ that includes the same number of encoding nodes or less.(iii)
Given a feasible network code𝔽̂(ℕ̂) for ℕ̂, the corresponding network code 𝔽(ℕ) for ℕ can be found through an efficient procedure whose running time is bounded by O(|E|+|Ê|).In addition, we useℕ′(G′,s,T,h), ℕ*(G*,s,T,h), and ℕ̂(Ĝ,s,T,h) to denote three auxiliary coding networks, all of which model ℕ(G,s,T,h). They are constructed by algorithms Procedure EXPAND, Algorithm MIN-GLOBAL, and Procedure SHRINK (shown in [9] for details) as the following steps.Step 1.
ℕ′(G′,s,T,h) = Pro. EXPAND (ℕ(G,s,T,h)).Step 2.
ℕ*(G*,s,T,h) = Alg. MIN-GLOBAL (ℕ′(G′,s,T,h)).Step 3.
ℕ̂(Ĝ,s,T,h) = Pro. SHRINK (ℕ*(G*,s,T,h)).From the proofs of Theorems6 and 7 in [9], we find that their upper bound O(h3) for an acyclic multicast network with two terminal nodes has greatly influenced these two theorems. Based on our new results on the upper bound of encoding nodes in feasible multicast networks, we give two farther results as follows.Theorem 3.6.
Letℕ*(G*(V*,E*),s,T,h) be the coding network returned by Algorithm Min-Global(ℕ′(G′,s,T,h)). Let V¯* be the subset of V*∖T that includes nodes of in-degree two and E¯* be the set of incoming links of nodes in V¯*. Then, it holds that |E¯*|=O(h2k).Proof.
By Theorems 1, the proof follows the same line as that of Theorem6 in [9].Theorem 3.7.
Letℕ(G,s,T,h) be an acyclic feasible coding network. Then there exists a deterministic algorithm that computes a network code 𝔽(ℕ) in time O(|E|kh+|V|k2h2+h3k2(k+h)). Moreover, the number of encoding nodes in 𝔽(ℕ) is bounded by O(h2k).Proof.
By Theorems3.2 and 3.6, the proof follows the same line as that of Theorem 7 in [9].So the complexityO(|E|kh+|V|k2h2+h3k2(k+h)) of computing a feasible network code 𝔽(ℕ) in Theorem 7 of [9] is in fact O(|E|kh+|V|k2h2+h4k3(k+h)) and their bound on the number of encoding nodes O(h3k2) in this feasible network code is really O(h2k). This is the best known running time for constructing network code.The following two theorems are about integral and fractional network codes. In an integral network, codes packets cannot be split and have to be sent through the network in one piece. In fractional network codes, each packet can be split into a number of smaller packets, each of which is sent over different paths. We assume that all integral packets are elements in finite field GF(2n), which implies that each such packet can be represented by n bits. m-Fractional Network Code 𝔽m(ℕ)), let ℕ(G,s,T,h) be a feasible coding network, n be the size of the integral packet, and let m be a divisor of n. Suppose ℕm(Gm,s,T,mh) be the coding network in which Gm is formed from G by splitting each link e in G of bit capacity ce into m parallel links e1,…,em of bit capacity ce/m. Let 𝔽(ℕm) be a feasible integral network code for ℕm(Gm,s,T,mh) over finite field GF(2)n/m. We refer to 𝔽(ℕm) as a feasible m-fractional network code 𝔽m(ℕ) for ℕ(G,s,T,h).Theorem 3.8.
Letℕ(G,s,T,h) be a feasible acyclic network. Then a feasible integral network code 𝔽(ℕ) can be constructed in time |V|O(h4k2).Proof.
By Theorem3.2, the proof follows the same line as that of Theorem 11 in [9].By this theorem, we can find that the complexity|V|O(h6k4) of constructing a feasible integral network code 𝔽(ℕ) in Theorem 11 of [9] is |V|O(h4k2).Theorem 3.9.
Letℕ(G,s,T,h) be a feasible acyclic network. Then a feasible m-fractional network node 𝔽m(ℕ) for ℕ can be constructed in time |V|O(h2k).Proof.
By Theorem3.2, the proof is similar to that of Theorem 16 in [9].From this result, we can find that the complexity|V|O(h3k2) of constructing a feasible m-fractional network code in Theorem 16 of [9] is actually |V|O(h2k).


## 4. Conclusion

In this paper, we reinvestigated the upper bounds of encoding nodes in acyclic and cyclic networks and answered the open question in [8]: the gap of hk between their lower and upper bounds for acyclic networks does not exist. Then, we gave out some new upper bounds for cyclic networks, which are tighter than those in [8]. The number of encoding nodes required to achieve the capacity of the network is independent of the size of the network. This fact is in favor of the feasibility of signatures for network coding to a certain extent. Furthermore, we also give a new result on the computational complexity of deterministic algorithm given by Langberg et al. [9], O(|E|kh+|V|k2h2+h3k2(k+h)). This is the best known running time for constructing network codes. At last, some new results on computational complexity of feasible integral and fractional network codes constructions are given for feasible acyclic networks.In this paper, we have established a much tighter upper bound for simple cyclic multicast networks, while this upper bound is not the optimal one. Therefore, like our result for simple acyclic multicast networks, to find the optimal upper bound for simple cyclic multicast networks is an interesting future topic. In addition, based on our current results whether a new algorithm of constructing network codes for cyclic multicast network with lower computational complexity can be found is an important further topic. Moreover, in future it is meaningful to discuss the relationships between the number of encoding nodes and the time-delay of network communication using network coding, between the number of encoding nodes and the optimizations of network resources (the encoding node can be viewed as the intelligent node in wireless sensor networks) and so on.



---

*Source: 436354-2010-09-22.xml*