## 3 Network Coding Enabled Network Tomography
### Topology Inference  
Among the first efforts to leverage _network coding_ in order to improve network tomography was the one presented in [27]. In particular, the authors address the problem of topology inference of binary trees, where multiple sources and receivers are employed at the edge of the network and the intermediate nodes are equipped with simple network coding capabilities (i.e., local XOR operations). The basic idea of their approach is that the combination of the incoming information flows by the intermediate nodes reveals information about the network structure that can be utilized during the inference. To that end, they develop an algorithm that exploits these topology dependent correlations and can deterministically infer the underlying topology in one pass, when there are no packet losses. Furthermore, in the presence of packet losses, the rapid discovery of the network topology is still possible after a relatively small number of probes, since the only thing required is one successfully received probe packet per end-to-end path. More precisely, the proposed algorithm starts by randomly choosing two of the tree leaves as sources (\(S_{1}\) and \(S_{2}\)) that send probe packets (\(P_{1}\) and \(P_{2}\), respectively) to the remaining nodes in the set of leaves. The intermediate nodes either receive one probe packet (\(P_{1}\) or \(P_{2}\)) and forward it to all their outgoing links or they receive both (within a predetermined time window \(W\)) and forward their linear (i.e., XOR) combination (\(P_{1}\oplus P_{2}\)). Eventually, each receiver observes one probe packet, either \(P_{1}\) or \(P_{2}\) or \(P_{1}\oplus P_{2}\). The set of leaves is divided into three parts based on the observed probe at each node, and the way these parts are connected to each other is deducted. When one of the constituent parts has two or less leaves, its internal structure is also revealed given that the tree is binary. The algorithm then proceeds in iterations within each part, choosing two different sources and repeating the process, until all edges are inferred. At each iteration, every link is traversed by one probe packet (or linear combination). The algorithm terminates in a number of iterations that is less than the number of leaves, and the binary tree topology is exactly discovered. The only difference in the presence of losses is that, in every iteration, each designated source sends \(K(>1)\) probe packets instead of just one. In order to avoid the case of probe packets meeting at different nodes during the same iteration, the direction of the edges is set for each iteration according to the first probe packet that arrives at each intermediate node. More precisely, each intermediate node maintains a table of neighbors marked as sources or sinks based on the reception of probes within a time window \(W\) after the first probe arrival. After that window passes, the node accepts probes only if they originate from one of its source neighbors, whereas it rejects probes coming from sink neighbors and it does not forward probe packets to source neighbors. The probability of error due to a leaf not receiving the \"correct\" probe decreases very fast as \(K\) increases, since it is sufficient for each node to receive exactly one probe packet from each of the sources it is connected to. The above hierarchical top-down approach is extended to full \(m\)-ary (intermediate nodes have a degree of \(m+1\), \(m\geq 3\)) and general \(m\)-ary (the degree of intermediate nodes is between \(3\) and \(m+1\)) trees in [28]. For the former, assuming no probe packets are lost, the number of components that are revealed in every iteration is increased by applying one of the following modifications.