  Software-defined networking (SDN) allows operators to control the behavior of
a network by programatically managing the forwarding rules installed on
switches. However, as is common in distributed systems, it can be difficult to
ensure that certain consistency properties are preserved during periods of
reconfiguration. The widely-accepted notion of PER-PACKET CONSISTENCY requires
every packet to be forwarded using the new configuration or the old
configuration, but not a mixture of the two. If switches can be updated in some
(partial) order which guarantees that per-packet consistency is preserved, we
call this order a CONSISTENT ORDER UPDATE. In particular, switches that are
incomparable in this order can be updated in parallel. We call a consistent
order update OPTIMAL if it allows maximal parallelism. This paper presents a
polynomial-time algorithm for finding an optimal consistent order update. This
contrasts with other recent results in the literature, which show that for
other classes of properties (e.g., loop-freedom and waypoint enforcement), the
optimal update problem is NP-complete.
