A network state is verified in real-time by precomputing a data structure representing header spaces of data packets in respective equivalence classes (ECs) in a first snapshot of the network and in a second snapshot of the network at a later time. The data structure includes respective bitmaps indicating for each data packet forwarding rule for each node in the network a forwarding action to be taken for each EC in the network. The respective bitmaps store bits indicating for each data packet forwarding rule whether the data packet forwarding rule applies to the respective ECs in the network. The snapshots are compared to identify network paths that have changed between a time of the first snapshot and the second snapshot of the network and network verification operations are performed on the changed network paths as a logical function of a bitmap corresponding to each changed network path.