## 3 Network Coding Enabled Network Tomography
### Topology Inference
Either the intermediate nodes deterministically generate different linear combinations when receiving probe packets from two different neighbors and forward each resulting packet to a different outgoing link (i.e., different neighbor) or up to \(m\) (more than two) sources are used per iteration sending distinct probe packets \(P_{1},P_{2},\ldots,P_{m}\). In the first case, the leaves are partitioned into \(m+1\) components in each iteration based on the probe packet they receive and, once a component has \(m\) or less nodes, its internal structure is revealed, given that the tree is assumed full \(m\)-ary. In the second case, the intermediate nodes (i.e., coding points) send the same linear combination of the \(k\) (\(2\leq k\leq m\)) probe packets they receive within a time window \(W\) to all of their remaining neighbors and the leaves are divided into \(m+1\) or \(m\) components. For general \(m\)-ary trees, only the first modification can be applied. In the presence of packet losses, directions are assigned to edges at each iteration, as described before. Furthermore, the authors propose a method for reconstructing the topology of directed acyclic graphs (DAGs) with a fixed set of \(M\) sources and \(N\) receivers and a predetermined routing scheme by decomposing them into a number of two-source, two-receiver (2-by-2) subnetwork components, which are then merged accordingly. The multiple-source multiple-destination tomography problem was first introduced in [29], where it was shown that any DAG can be decomposed into a collection of 2-by-2 topologies, each of which belongs to one of four distinct types of 2-by-2 subnetwork components (Types 1, 2, 3, and 4). However, contrary to the methods proposed in [29], the network coding enabled approach can uniquely distinguish among all those 2-by-2 subnetwork component types. More precisely, the first step of the proposed method involves the identification of the type of every 2-by-2 component of the original DAG. In the second step, the identified 2-by-2 components are merged in order to reconstruct the \(M\)-by-\(N\) topology. To that end, the sources send multicast probe packets that are spaced apart by intervals of length \(T\) (duration of every experiment/iteration) to the receivers. In order to force the probe packets to meet at different points (or not meet at all) in different iterations, there is a per iteration randomly chosen time offset \(u\) between the sending times of the two sources. The intermediate nodes are divided into two categories: joining points that add and forward probe packets and branching points that forward the single received probe to all \"interested\" links (i.e., links that are the next hop for at least one source packet in the linearly combined packet). Assuming that there are no packet losses, in every 2-by-2 component, sources \(S_{1}\) and \(S_{2}\) multicast probe packets \(x_{1}\) and \(x_{2}\), respectively, to receivers \(R_{1}\) and \(R_{2}\). Depending on the underlying 2-by-2 topology, the receivers observe variations of the linear combinations \(r_{1}=c_{11}x_{1}+c_{12}x_{2}\) and \(r_{2}=c_{21}x_{1}+c_{22}x_{2}\). Types 2 and 3 result in unique observed combinations and can therefore be identified with the first observation. Types 1 and 4 are identified in subsequent iterations by forcing probes to meet at only one of the joining points through appropriately tuning the offset \(u\). In particular, Type 4 is identified the first time the two receivers observe different linear combinations, whereas Type 1 is inferred if the receivers see the same combined (i.e., coded) packets after a specific number of iterations chosen suitably to ensure small probability of error.