In response to a path monitoring task for a particular source/destination pair, a network controller determines whether stored information includes paths for the particular source/destination pair. When the stored information includes paths for the particular source/destination pair, a subset of source ports is selected that covers all the paths for the particular source/destination pair. A probe message is sent to cause an ingress switch to send probe packets using the subset of source ports. Paths for the particular source/destination pair are computed based on received probe packets. A determination is made whether a topology for the data center network has changed by comparing the paths computed based on the receive probe packets for the particular source/destination pair with the paths included in the stored information for the particular source/destination pair.