Rule updates, such as policy or routing changes,
occur frequently and instantly in software-defined networks
managed by the controller. In particular, the controller software
can modify the network routes by introducing new forwarding
rules and deleting old ones in a distributed set of switches, a
challenge that has received lots of attention in the last few years.
In this paper, we present a problem that consists of determining
the appropriate point in the rule update where it
is safe to garbage collect old rules. To illustrate the difficulty
of the problem, we list the previously proposed assumptions,
like the upper-bound on the transmission delay of every packet
through the network, and we offer a solution that alleviates these
assumptions and significantly reduces the rule update time with
a guarantee that no data packet is lost due to the rule alteration
through the use of dedicated clean-up packets that detect the
absence of in-flight packets. We then prove that the proposed
technique guarantees per-packet consistency, blackhole-freedom,
and loop-freedom. Our evaluations, via network emulations and
real deployment in an SDN testbed, demonstrate that by using
the proposed garbage collection solution the rule update times
of the two phase rule update can be reduced by up to 99%.