We present a new set of solutions for topology verification and failure localization in Software Defined Networks (SDNs). Our solutions are targeted towards offloading the control plane as much as possible and bringing more resilience against congestion or partitioning in the control plane. The core idea is to define control flows for network diagnosis and utilize a fraction of the forwarding table rules on the switches to serve these control flows. For topology verification, we present provably optimal or order-optimal solutions in total number of static forwarding rules and control messages. For single link failure localization, we present a solution that requires at least 3 |E| but at most 6 |E| forwarding rules using at most 1+log2 |E| control messages, where |E| denotes the number of bidirectional links in the forwarding plane. We analyze the latency vs. rule and control message optimality trade-offs showing that sub-second failure localization is possible even in data center scale networks without significant additional overhead in the number of static rules and control messages. We further simulate the performance of failure localization in identifying multiple link failures.

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. When parts of the control plane become unavailable or unreliable, individual controllers should still be able to monitor the forwarding plane and run diagnostics to take the correct routing actions. In our paper, we present solutions that install an optimal or near-optimal number of static forwarding rules on switches/routers for any controller to be able to verify the topology connectivity and detect/locate link failures at data plane speeds without relying on state updates from forwarding plane nodes and other controllers while requiring reachability to only one (arbitrary) forwarding node. 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.