Dynamic Algorithms for Multicast with Intra-session Network Coding

We establish, for multiple multicast sessions with intra-session network coding, the capacity region of input rates for which the network remains stable in ergodically time-varying networks. Building on the back-pressure approach introduced by Tassiulas et al., we present a dynamic algorithm for multicast routing, network coding, rate control, power allocation, and scheduling that achieves stability for rates within the capacity region. Decisions on routing, network coding, rate control and scheduling between different sessions at a node are made locally at each node based on virtual queues for different sinks. For correlated sources, the sinks locally determine and control transmission rates across the sources. The proposed approach yields a completely distributed algorithm for wired networks. In the wireless case, scheduling and power control among different transmitters are centralized while routing, network coding, and scheduling between different sessions at a given node are distributed.