Dynamic Multicast Traffic Engineering with Efficient Rerouting for Software-Defined Networks

摘要

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.