A belief-propagation approach for multicast scheduling in input-queued switches

Scheduling multicast traffic in input-queued switches requires solving a hard combinatorial optimization problem in a very short time. This task advocates the design of algorithms that are simple to implement and efficient in terms of performance. We propose a new scheduling algorithm, based on message passing and inspired by the belief propagation paradigm, meant to approximate the provably optimal scheduling policy. Our main finding is that our algorithm outperforms other centralized greedy scheduling policies, achieving a better tradeoff between complexity and performance.