Mechanisms for measuring network availability are described. A first network element produces a first knowledge digest encoding the first set of forwarding policy indicators associated with a set of packets into a fixed length bit array. The first network element periodically sends probe messages containing the knowledge digest to a second network element. The second network element produces a second knowledge digest encoding a second set of forwarding policy indicators into a fixed length bit array. The second network element compares the first knowledge digest to the second knowledge digest to determine whether the first set of forwarding policy indicators is a subset of the second set of forwarding policy indicators. The second network element indicates the availability of the path as long as probe messages are received from the first network element.