Pruning Network Coding Traffic by Network Coding—A New Class of Max-Flow Algorithms

This work explores new graph-theoretic and algebraic behaviors of network codes and provides a new class of coding-based, distributed max-flow algorithms. The proposed algorithm starts from broadcasting the coded packets, followed by continuously trimming the redundant traffic that does not constitute the maximum flow of the network information. The convergence speed of the proposed algorithms is no slower than that of the existing push-&-relabel max-flow algorithms. The algorithmic results in this work also possess several unique features that are especially suitable for practical network implementation with low control, communication, and complexity overhead.