Algebraic Traceback Meets Network Coding

Traceback schemes aim at identifying the source(s) of a sequence of packets and the nodes these packets have traversed. We are particularly interested in algebraic traceback, which encodes the IDs of nodes on a single path as coefficients of a polynomial in a finite field, and determines the polynomial by evaluating it at different points. So far, algebraic traceback schemes have only been developed to infer single paths, and multi-path graphs have been considered as a collection of multiple individual paths. In this paper, we consider multi-path graphs that use network coding for marking, and we propose an algebraic traceback scheme that combines marks on packets from different paths for better inference. Our approach first identifies the topology by mapping the graph to a multivariate polynomial, marked on packets by intermediate nodes, and then reconstructs the node IDs within the topology by solving a system of linear equations. In addition to solving the multi-path algebraic traceback problem, for the first time efficiently, we also make the connections to two network coding problems: (i) we show that the dual of the traceback problem is a linear network coding problem; and (ii) we formulate our approach as passive topology inference with non-linear network coding.