Active Topology Inference using Network Coding
The authors' goal, in this paper, is to infer the topology of a network when they can send probes between sources and receivers at the edge of the network and intermediate nodes can perform simple network coding operations, i.e., additions. Their key intuition is that network coding introduces topology-dependent correlation in the observations at the receivers, which can be exploited to infer the topology. For undirected tree topologies, they design hierarchical clustering algorithms, building on their prior work in. For Directed Acyclic Graphs (DAGs), first they decompose the topology into a number of two source, two receiver (2-by-2) sub-network components and then they merge these components to reconstruct the topology.