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%.