2nd International IEEE Conference on Communication System Software and Middleware

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},
        keywords={Algorithm design and analysis  Analytical models  Degradation  IP networks  Loss measurement  Network topology  Performance analysis  Performance loss  Probes  Telecommunication traffic},
  • Srinivasan Parthasarathy
    Rajeev Rastog
    Marina Thottan
    Year: 2007
    Efficient Design of End-to-End Probes for Source-Routed Networks
    DOI: 10.1109/COMSWA.2007.382610
Srinivasan Parthasarathy1,*, Rajeev Rastog2,*, Marina Thottan2,*
  • 1: IBM T.J. Watson Research Center, 19, Skyline Drive Hawthorne, NY, 10532
  • 2: Bell Laboratories, 700, Mountain Avenue, Murray Hill, NJ, 07974
*Contact email: spartha@us.ibm.com, rastogi@bell-labs.com, marinat@lucent.com


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.