FAD and SPA: End-to-end link-level loss rate inference without infrastructure

It is highly desirable and important for end users, with no special privileges, to identify and pinpoint faults inside the network that degrade the performance of their applications. However, existing tools are inaccurate to infer the link-level loss rates and have large diagnosis granularity. To address these problems, we propose a suite of user-level diagnosis approaches in two categories: (1) the diagnosis tool needs to be deployed only at the source and (2) the tool has to be deployed at both source and destination. For the former, we propose two fragmentation aided diagnosis approaches (FAD), Algebraic FAD and Opportunistic FAD, which use IP fragmentation to enable accurate link-level loss rate inference. For the latter category, we propose Striped Probe Analysis (SPA) which significantly improves the diagnosis granularity over those of the source-only approaches. Internet experiments are applied to evaluate each individual scheme (including an improved version of the state-of-the-art tool, Tulip [R. Mahajan, N. Spring, D. Wetherall, T. Anderson, User-level internet path diagnosis, in: ACM SOSP, 2003]) and various hybrid approaches. The results indicate that our approaches dramatically outperform existing work (especially for diagnosis granularity). But more importantly, we show that combination of different individual approaches (e.g. OFAD + Tulip or OFAD + SPA) provide not only the best performance but also smooth tradeoff among deployment requirement, diagnosis accuracy and granularity.