On the inadequacy of link connectivity monitoring

Internet backbone networks are constantly evolving along several dimensions such as technology, protocols, and features. The rapid rate of this evolution often places a tremendous amount of burden on network operators and router vendors to cope with both unanticipated as well as complicated failure scenarios. While routing protocols are designed to detect these failures and respond by switching to alternate paths, we argue that current routing protocols (e.g., OSPF) do not completely verify all data plane paths properly. Thus, there potentially exist failure scenarios that are not detected by them and thereby recover from. To alleviate this problem, we show how a simple extension to OSPF, wherein each router injects probes to a 2-hop neighbor, can easily verify all the data plane forwarding paths within the adjacent router. While we point out the extension in the context of OSPF, we believe our approach is generally applicable to other control plane protocols as well. Using Rocketfuel topologies, we quantify the resulting overhead of injecting these 2-hop probes for routers in real ISPs.