APF: fast network all-pair reachability calculation

Network verification, which is mainly about checking network states against network invariants or operator beliefs, has been a popular research thesis recently. Fast calculation of all-pair reachability of the network beforehand for further query or overall analysis can be a huge assistance to network verification. In this paper, we propose a new fast all-pair reachability calculation algorithm Atomic Predicates Flooding(APF). Experiments on real-life datasets show that the new algorithm based on network atomization is about three to four orders of magnitude faster than existing algorithms without network atomization. On most kinds of datasets, APF is even 2 to 5 times faster than the Warshall based all pair reachability algorithm with atomization. We believe that our method is essential for developing more practical and more efficient network and verification tools.