Example methods, apparatus and articles of manufacture to monitor communication paths in communication systems are disclosed. A disclosed example method includes identifying first and second inter-network communication links of a communication system, identifying a first plurality of router pairs associated with the first inter-network communication link, identifying a second plurality of router pairs associated with the second inter-network communication link, partitioning the first plurality of router pairs into a first subset of router pairs and a second subset of router pairs, partitioning the second plurality of router pairs into a third subset of router pairs and a fourth subset of router pairs, during a first time interval, performing first reachability tests for respective ones of the first and third subsets of router pairs, and during a second time interval, performing second reachability tests for respective ones of the second and fourth subsets of router pairs.