[en] Topology discovery systems are starting to be in- troduced in the form of easily and widely deployed software. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. This paper describes several contributions towards that end. These were first presented in the proceedings of ACM SIGMETRICS 2005. We show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We propose two metrics focusing on redundancy in probing and show that both are important. We also propose and evaluate Doubletree, an algorithm that strongly reduces redundancy while maintaining nearly the same level of node and link coverage. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Following the SIGMETRICS work, we implemented Doubletree, and deployed it in a real network environment. This paper describes that implementation, as well as preliminary favorable results.
Disciplines :
Computer science
Author, co-author :
Donnet, Benoît ; Université Pierre et Marie Currie - Paris 6 - UPMC > Laboratoire d'Informatique Paris 6 - LiP6 > NPA
Raoult, Philippe
Friedman, Timur
Crovella, Mark
Language :
English
Title :
Deployment of an Algorithm for Large-Scale Topology Discovery
V. Jacobsen et al., "TracerouteUNIX," 1989. [Online]. Available:ftp://ftp.ee.lbl.gov/traceroute.tar.gz, man page
B. Huffaker, D. Plummer, D. Moore, and k. claffy, "Topology discovery by active probing," in Proc. Symp. App. Internet, Jan. 2002, pp. 90-96.
WAND Network Research Group, "IPv6 scamper." [Online]. Available: http://www.wand.net.nz/~mjl12/ipv6-scamper/
F. Georgatos, F. Gruber, D. Karrenberg, M. Santcroos, A. Susanj, H. Uijterwaal, and R. Wilhelm, "Providing active measurements as aregular service for ISPs," in Proc. Passive Active Measuie. Workshop, 2001, pp. 45-56. [Online]. Available: http://www.ripe.net/test-traffic/
A. McGregor, H.-W. Braun, and J. Brown, "The NLANR network analysis infrastructure," IEEE Commun. Maga. vol. 38, no. 5, pp. 122-128, May 2000. [Online]. Available: http://watt.nlanr.net/
N. Spring, D. Wetherall, and T. Anderson, "Scriptroute: A public Internet measurement facility," in Proc. 4th USENIX Symp. Internet Technol. Syst., Mar. 2003, pp. 225-228. [Online]. Available: http://www.cs.washington. edu/research/networking/scriptroute/
M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the Internet topology," in Proc. ACM SIGCOMM, Sep. 1999, pp. 251-262.
J. J. Pansiot and D. Grad, "On routes andmulticast trees in the Internet," ACM SIGCOMM Comput. Commun. Rev., vol. 28, no. 1, pp. 41-50, Jan. 1998.
A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM, Apr. 2003, pp. 332-341.
A. Clauset and C. Moore, "Traceroute sampling makes random graphs appear to have power law degree distributions," Feb. 2004, arXiv, cond-mat0312674.
P. Erdös and A. Rényi, "On the evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci., vol. 5, pp. 17-61, 1960.
B. Cheswick, H. Burch, and S. Branigan, "Mapping and visualizing the Internet," in Proc. USENIX Annu. Tech. Conf., Jun. 2000, pp. 1-12.
A. Schmitt et al., "La météo du net," ongoing service. [Online]. Available: http://www.grenouille.com/
C. R. Simpson, Jr. and G. F. Riley, "NETI@home: A distributed approach to collecting end-to-end network performance measurements," in Proc. Passive Active Measure. Workshop, 2004, pp. 168-174. [Online]. Available: http://www.neti.gatech.edu/
Y. Shavitt and E. Shir, "DIMES: Let the Internet measure itself," ACM SIGCOMM Comput. Commun. Rev. vol. 35, no. 5, pp. 71-74, 2005. [Online]. Available: http://www.netdimes.org
B. Donnet, P. Raoult, T. Friedman, and M. Crovella, "Efficient algorithms for large-scale topology discovery," in Proc. ACM SIGMETRICS, Jun. 2005, pp. 327-338. [Online]. Available: http://trhome.sourceforge.net
A. Broido and k. claffy, "Internet topology: Connectivity of IP graphs," in Proc: SPIE Int. Symp. Convergence IT and Commun., Aug. 2000, pp. 172-187.
R. K. Jain, The Art of Computer Systems Performance Analysis. New York: Wiley, 1991.
B. Donnet, P. Raoult, T. Friedman, and M. Crovella, "Efficient algorithms for large-scale topology discovery," arXiv, cs.NI 0411013 v1, Nov. 2004. [Online]. Available: http://trhome.sourceforge.net
B. Donnet, T. Friedman, and M. Crovella, "Improved algorithms for network topology discovery," in Proc. Passive Active Measure. Workshop, Mar. 2005, pp. 149-162. [Online]. Available: http://trhome.sourceforge.net
B. Donnet, "Doubletree prototype code." Nov. 2005. [Online]. Available: http://trhome.sourceforge.net
B. Donnet, B. Huffaker, T. Friedman, and k. claffy, "Implementation and deployment of a distributed network topology discovery algorithm," arXiv, cs.NI 0603062, Mar. 2006. [Online]. Available: http://trhome.sourceforge. net
L. Peterson, V. Pai, N. Spring, and A. Bavier, "Using PlanetLab for network research: Myths, realities, and best practices," PlanetLab, Design Note 05-028, Jun. 2005.
Y. Bejerano and R. Rastogi, "Robust monitoring of link delays and faults in IP networks," in Proc. IEEE INFOCOM, Apr. 2003, pp. 134-144.
R. Govindan and H. Tangmunarunkit, "Heuristics for Internet map discovery," in Proc. IEEE INFOCOM, Mar. 2000, pp. 1371-1380.
N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel," in Proc. ACM SIGCOMM, Aug. 2002, pp. 133-145.
P. Barford, A. Bestavros, J. Byers, and M. Crovella, "On the marginal utility of network topology measurements," in Proc. ACM SIGCOMM Internet Measutf. Workshop (IMW), Nov. 2001, pp. 5-17.
A. Clauset and C. Moore, "Why mapping the Internet is hard," arXiv,cond-mat 0407339 v1, Jul. 2004.
T. Petermann and P. De Los Rios, "Exploration of scale-free networks," Eur. Phys. J. B, vol. 38, p. 201, 2004.
L. Dall' Asta, I. Alvarez-Hamelin, A. Barrat, A. Vàzquez, and A. Vespignani, "A statistical approach to the traceroute-like exploration of networks: Theory and simulations," in Proc. Workshop on Combinatorial and Algorithmic Aspects Netw., Aug. 2004, pp. 140-153.
J.-L. Guillaume and M. Latapy, "Relevance of massively distributed explorations of the Internet topology: Simulation results," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1084-1094.
B. Donnet and T. Friedman, "Topology discovery using an address prefix based stopping rule," in Proc. EUNICE Workshop, Jul. 2005, pp. 79-83. [Online]. Available: http://trhome.sourceforge.net
