Shifter: A Consistent Multicast Routing Update Scheme in Software-Defined Networks

Consistent routing update based on Software-Defined Networks (SDN) is a complicated problem due to the asynchronous and distributed data plane. Existing ordered update approaches mostly focus on the consistent routing update problem for unicast other than multicast, which should guarantee two consistencies, drop-freeness and duplicate-freeness. In this paper, we propose Shifter, a novel dynamic ordered update scheme for consistent multicast routing update based on SDN to guarantee both consistencies. Shifter advocates configuring inport match field in the forwarding rules to avoid duplicate. In order to guarantee drop-freeness, Shifter employs a dependency graph to dynamically schedule update operations, and uses a greedy solution to solve a subproblem named Replace Operation Tree Migration Problem (ROTMP). We conduct simulations to evaluate Shifter and find that Shifter can give a near optimal solution of ROTMP with very few rounds and little runtime for multicast routing update scenarios. To the best of our knowledge, Shifter is the first ordered update scheme to guarantee the two consistencies simultaneously.