## 3 Network Coding Enabled Network Tomography  
The operation of today's communication network infrastructures relies on the fundamental assumption that, although independent information flows may share network resources, the data themselves are separated. Network coding is a new paradigm based on the idea that independent data streams can be linearly combined throughout the network in order to achieve benefits in terms of throughput and robustness. As demonstrated in [3, 4], optimal multicast throughput (i.e., the min-cut/max-flow of the network to each receiver) can be achieved if intermediate nodes can perform local additions (i.e., Exclusive-Or (XOR) operations) on their incoming packets. Furthermore, network coding can be leveraged in the setting of packet erasure networks to achieve both optimal rate and optimal delay at the same time [24]. The basic premise of network coding is to make the network behave as a linear system with a transfer function that depends on the topology. Nodes are able to linearly combine (i.e., perform additions and multiplications on) the packets received on their incoming links and to broadcast the resulted packets on all of their outgoing links. The combined packets eventually observed at the end receivers can be leveraged to recover the original information by solving a set of linear equations over the employed finite field [25].  
To provide a more educated overview of NC, assuming that each packet consists of \(L\) bits (shorter packets are padded with trailing zeros) and interpreting \(l\) consecutive bits of a packet as a symbol over the finite field \(\mathcal{F}_{q}\) with \(q=2^{l}\) (each packet consists of a vector of \(L/l\) symbols), under linear network coding, the outgoing packets are linear combinations of the incoming ones with addition and multiplication being performed over the field \(\mathcal{F}_{q}\). Given the series of original packets \(P^{1},P^{2},\cdots,P^{n}\) that is generated by one or several sources, a combined/coded packet contains the _encoding vector_ (i.e., the coefficients \(c=(c_{1},\cdots,c_{n})\) with \(c_{i}\in\mathcal{F}_{q}\)) and the _information vector_ (i.e, the encoded data) \(D=\sum_{i=1}^{n}c_{i}P^{i}\), where the summation occurs for every symbol position (i.e., \(D_{k}=\sum_{i=1}^{n}c_{i}P^{i}_{k}\), with \(P^{i}_{k}\) and \(D_{k}\) as the \(k\)th symbol of \(P^{i}\) and \(D\), respectively). Encoding is performed recursively, over the  
Figure 1: Network tomography classes.  
original and/or previously encoded packets. An end receiver observing the sets \((c^{1},D^{1}),\cdots,(c^{n},D^{n})\), where \(c^{i}\) and \(D^{i}\) are the encoding and the information vectors of the \(i\)-th received packet, respectively, has to solve the system \(\{D^{j}=\sum_{i=1}^{n}c_{i}^{j}P^{i}\}\) with unknowns \(P^{i}\). The coefficients over the field \(\mathcal{F}_{q}\) can be chosen uniformly at random by each node (Random Linear Network Coding--RLNC). Alternatively, network codes can be constructed by deterministic algorithms (e.g., the polynomial time algorithm presented in [26]).  
In the next subsections, we present more particular approaches exploiting network coding in tomography, centered around specific problem areas.