On the predictive power of shortest-path weight inference

ABSTRACT

Reverse engineering of the Internet is a valuable activity. Apart from providing scientific insight, the resulting datasets are invaluable in providing realistic network scenarios for other researchers. The Rocketfuel project attempted this process, but it is surprising how little effort has been made to validate its results. This paper concentrates on validating a particular inference methodology used to obtain link weights on a network. There is a basic difficulty in assessing the accuracy of such inferences in that a non-unique set of link-weights may produce the same routing, and so simple measurements of accuracy (even where ground truth data are available) do not capture the usefulness of a set of inferred weights. We propose a methodology based on predictive power to assess the quality of the weight inference. We used this to test Rocketfuel's algorithm, and our tests suggest that it is reasonably good particularly on certain topologies, though it has limitations when its underlying assumptions are incorrect.

References

1. N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel," in ACM SIGCOMM, (Pittsburg, USA), August 2002.
2. N. Spring, R. Mahajan, and T. Anderson, "Quantifying the causes of path inflation," in ACM SIGCOMM 2003, (Karlsruhe, Germany), 2003.
3. B. Fortz and M. Thorup, "Robust optimization of OSPF/IS-IS weights," in Proc. INOC 2003 (W. Ben-Ameur and A. Petrowski, eds.), pp. 225--230, October 2003.
4. L. S. Buriol, M. G. C. Resende, C. C. Ribeiro, and M. Thorup, "A memetic algorithm for OSPF routing," in Proc. 6th INFORMS Telecom, pp. 187--188, 2002.
5. M. Roughan, M. Thorup, and Y. Zhang, "Traffic engineering with estimated traffic matrices," in ACM SIGCOMM Internet Measurement Conference (IMC), (Miami Beach, FL, USA), pp. 248--258, 2003.
6. R. Teixeira, K. Marzullo, S. Savage, and G. Voelker, "In search of path diversity in ISP networks," in ACM Internet Measurement Conference, Oct. 2003.
7. B. Augustin, T. Friedman, M. Curie, and R. Teixeira, "Measuring load-balanced paths in the Internet," in ACM SIGCOMM Internet Measurement Conference, (San Diego, CA, USA), October 2007.
8. L. Subramanian, S. Agarwal, J. Rexford, and R. Katz, "Characterizing the Internet hierarchy from multiple vantage points," in Infocom, 2002.
9. F. Wang and L. Gao, "On inferring and characterizing Internet routing policies," in ACM SIGCOMM/USENIX Internet Measurement Conference, (Miami, Florida, USA), October 2003.
10. J. Xia and L. Gao, "On the evaluation of AS relationship inferences," in Globecom, 2004.
11. W. Mühlbauer, A. Feldmann, M. R. O. Maennel, and S. Uhlig, "Building an AS-topology model that captures route diversity," in ACM SIGCOMM, (Pisa, Italy), 2006.
12. A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot, "Traffic matrix estimation: Existing techniques and new directions," in ACM SIGCOMM, (Pittsburgh, USA), August 2002.
13. Y. Zhang, M. Roughan, C. Lund, and D. Donoho, "An information-theoretic approach to traffic matrix estimation," in ACM SIGCOMM, (Karlsruhe, Germany), pp. 301--312, August 2003.
14. R. Cáceres, N. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal loss characteristics," IEEE Trans. in Information Theory, vol. 45, pp. 2462--2480, 1999.
15. N. Duffield, J. Horowitz, F. L. Presti, and D. Towsley, "Multicast topology inference from measured end-to-end loss," IEEE Transactions in Information Theory, vol. 48, no. 1, pp. 26--45, 2002.
16. A. Nucci, A. Sridharan, and N. Taft, "The problem of synthetically generating IP traffic matrices: Initial recommendations," ACM Computer Communication Review, vol. 35, no. 3, 2005.
17. A. Nucci, S. Bhattacharyya, N. Taft, and C. Diot, "IGP link weight assignment for operational Tier-1 backbones," Networking, IEEE/ACM Transactions on, vol. 15, no. 4, pp. 789--802, Aug. 2007.
18. M. Roughan, "Simplifying the synthesis of Internet traffic matrices," SIGCOMM Comput. Commun. Rev., vol. 35, pp. 93--96, October 2005.

Index Terms

• Networks

  • Network services

    • Network monitoring