Efficient Design of End-to-End Probes for Source-Routed Networks

Migration to a converged network has caused service providers to deploy real time applications such as voice over an IP (VoIP) network. From the provider´s perspective, the success of such emerging multimedia services over IP networks depend on mechanisms which help understand the network-wide end-to-end performance dynamics. In this work, we present a mechanism to design efficient probes for measuring end-to-end performance impairments such as network delay and loss for a specific service in the provider network. We address two main issues related to deploying network probes: (1) the need for correlating the topology data with the measured values and (2) reducing the amount of probe traffic. We use explicitly routed probe packets to alleviate the need for correlation with topology measurements. We also present a 3.5-approximation algorithm for designing probe-sets which cover all the edges in the network. Further, we explore techniques for using observed performance degradations in a given set of probes to isolate the miscreant-edge which caused the degradations. We state a precise characterization for probe-sets which isolate miscreant edges in the network; this also suggests a natural heuristic for miscreant-edge detection. Simulations on ISP topologies obtained from the RocketFuel project show that our algorithms perform much better than the analytically guaranteed bounds and are near-optimal in practice with respect to probe costs.