Research Article
Efficient Design of End-to-End Probes for Source-Routed Networks
@INPROCEEDINGS{10.1109/COMSWA.2007.382610, author={Srinivasan Parthasarathy and Rajeev Rastog and Marina Thottan}, title={Efficient Design of End-to-End Probes for Source-Routed Networks}, proceedings={2nd International IEEE Conference on Communication System Software and Middleware}, publisher={IEEE}, proceedings_a={COMSWARE}, year={2007}, month={7}, keywords={Algorithm design and analysis Analytical models Degradation IP networks Loss measurement Network topology Performance analysis Performance loss Probes Telecommunication traffic}, doi={10.1109/COMSWA.2007.382610} }- Srinivasan Parthasarathy
Rajeev Rastog
Marina Thottan
Year: 2007
Efficient Design of End-to-End Probes for Source-Routed Networks
COMSWARE
IEEE
DOI: 10.1109/COMSWA.2007.382610
Abstract
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.