  Software Defined Networks (SDN) decouple the forwarding and control planes
from each other. The control plane is assumed to have a global knowledge of the
underlying physical and/or logical network topology so that it can monitor,
abstract and control the forwarding plane. In our paper, we present solutions
that install an optimal or near-optimal (i.e., within 14% of the optimal)
number of static forwarding rules on switches/routers so that any controller
can verify the topology connectivity and detect/locate link failures at data
plane speeds without relying on state updates from other controllers. Our upper
bounds on performance indicate that sub-second link failure localization is
possible even at data-center scale networks. For networks with hundreds or few
thousand links, tens of milliseconds of latency is achievable.
