$D^{2}$ FL: Design and Implementation of Distributed Dynamic Fault Localization

Compromised or misconfigured routers have been a major concern in large-scale networks. Such routers sabotage packet delivery, and thus hurt network performance. Data-plane fault localization (FL) promises to solve this problem. Regrettably, the path-based FL fails to support dynamic routing, and the neighbor-based FL requires a centralized trusted administrative controller (AC) or global clock synchronization in each router and introduces storage overhead for caching packets. To address these problems, we introduce a dynamic distributed and low-cost model, D
²
FL. Using random two-hop neighborhood authentication, D
²
FL supports volatile path without the AC or global clock synchronization. Besides, D
²
FL requires only constant tens of KB for caching which is independent of the packet transmission rate. This is much less than the cache size of DynaFL or DFL which consumes several MB. The simulations show that D
²
FL achieves low false positive and false negative rate with no more than 3 percent bandwidth overhead. We also implement an open source prototype and evaluate its effect. The result shows that the performance burden in user space is less than 10 percent with the dynamic sampling algorithm.