On the Impact of Layer-2 on Node Degree Distribution

Mérindol, Pascal; Donnet, Benoît; Bonaventure, Olivier; Pansiot, Jean*-Jacques

Download

Paper published in a book (Scientific congresses and symposiums)

On the Impact of Layer-2 on Node Degree Distribution

Mérindol, Pascal; Donnet, Benoît; Bonaventure, Olivier et al.

2010 • In 10th annual conference on Internet measurement

Peer reviewed

Permalink
https://hdl.handle.net/2268/107077

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

paper.pdf

Author preprint (950.06 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Network topology; mrinfo; degree distribution; layer 2

Abstract :

[en] The Internet topology data collected through traceroute exploration has been extensively studied in the past. In particular, a remarkable property of the Internet, the power-law shape of node degree distribution, drew the attention of the research community. Several studies have since questioned this property. In this paper, based on a large dataset collected using mrinfo, we show that the node degree distribution is strongly impacted by the presence of layer-2 (L2) networks, such as switches. L2 devices interconnect a large number of routers, themselves being also involved in multiple L2 interconnec- tions. Such a situation induces nodes with very high degree when analyzing the layer-3 (L3) graph with traceroute probing. Considering the physical design of a network, our analysis provides a lower bound on the bias generated by using only an L3 view. We also provide a model that can be a first step towards L2 aware topology generation.

Disciplines :

Computer science

Author, co-author :

Mérindol, Pascal

Donnet, Benoît ; Université Catholique de Louvain - UCL > ICTEAM > INL

Bonaventure, Olivier

Pansiot, Jean*-Jacques

Language :

English

Title :

On the Impact of Layer-2 on Node Degree Distribution

Publication date :

November 2010

Event name :

ACM/USENIX IMC

Audience :

International

Main work title :

10th annual conference on Internet measurement

Peer reviewed :

Peer reviewed

Available on ORBi :

since 04 January 2012

Statistics

Number of views

82 (5 by ULiège)

Number of downloads

210 (6 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

k. claffy, Y. Hyun, K. Keys, M. Fomenkov, and D. Krioukov, "Internet mapping: from art to science," in Proc. IEEE Cybersecurity Applications and Technologies Conference for Homeland Security (CATCH), March 2009.
H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy, and A. Venkataramani, "iPlane: An information plane for distributed services," in Proc. USENIX Symposium on Operating Systems Design and Implementation (OSDI), November 2006.
Y. Shavitt and E. Shir, "DIMES: Let the internet measure itself," ACM SIGCOMM Computer Communication Review, vol. 35, no. 5, October 2005.
M. Luckie, "Scamper: a scalable and extensible packet probet for active measurement of the Internet," in Proc. USENIX/ACM Internet Measurement Conference (IMC), November 2010.
V. Jacobson et al., "traceroute," UNIX," man page, 1989, see source code: ftp://ftp.ee.lbl.gov/traceroute.tar.gz.
B. Donnet and T. Friedman, "Internet topology discovery: a survey," IEEE Communications Surveys and Tutorials, vol. 9, no. 4, pp. 2-15, December 2007.
R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: a Statistical Physics Approach. Cambridge University Press, February 2004.
M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the internet topology," in Proc. ACM SIGCOMM, September 1999.
A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM, April 2003.
A. Clauset and C. Moore, "Traceroute sampling makes random graphs appear to have power law degree distributions," arXiv, cond-mat 0312674, February 2004.
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.
J.-J. Pansiot and D. Grad, "On routes and multicast trees in the Internet," ACM SIGCOMM Computer Communication Review, vol. 28, no. 1, pp. 41-50, January 1998.
W. Willinger, D. Alderson, and J. Doyle, "Mathematics and the Internet: a source of enormous confusion and great potential," Notices of the American Mathematical Society, vol. 56, no. 5, pp. 586-599, May 2009.
V. Jacobson, "mrinfo ," 1995, see http://cvsweb.netbsd.org/ bsdweb.cgi/src/usr.sbin/mrinfo/?only with tag=MAIN.
P. Mérindol, V. Van den Schriek, B. Donnet, O. Bonaventure, and J.-J. Pansiot, "Quantifying ASes multiconnectivity using multicast information," in Proc. ACM USENIX Internet Measurement Conference (IMC), November 2009.
J.-J. Pansiot, P. Mérindol, B. Donnet, and O. Bonaventure, "Extracting intra-domain topology from mrinfo probing," in Proc. Passive and Active Measurement Conference (PAM), April 2010.
S. Deering, "Host extensions for IP multicasting," Internet Engineering Task Force, RFC 1112, August 1989.
T. Pusateri, "Distance vector multicast routing protocol version 3 (DVMRP)," Internet Engineering Task Force, Internet Draft (Work in Progress) draft-ietf-idmr-dvmrp-v3-11, October 2003.
J.-J. Pansiot, "mrinfo dataset," see http://svnet.u-strasbg.fr/ mrinfo/.
IANA, "Special-use IPv4 addresses," Internet Engineering Task Force, RFC 3330, September 2002.
W. Fenner, "Internet group management protocol (IGMP), version 2," Internet Engineering Task Force, RFC 2236, November 1997.
E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching architecture," Internet Engineering Task Force, RFC 3031, January 2001.
L. Andersson, P. Doolan, N. Feldman, A. Fredette, and B. Thomas, "LDP specification," Internet Engineering Task Force, RFC 3036, January 2001.
D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP tunnels," Internet Engineering Task Force, RFC 3209, December 2001.
Y. Rekhter and E. Rosen, "Carrying label information in BGP-4," Internet Engineering Task Force, RFC 3107, May 2001.
K. Kompella and Y. Rekhter, "Virtual private LAN service (VPLS) using BGP for auto-discovery and signaling," Internet Engineering Task Force, RFC 4761, January 2007.
M. Lasserre and V. Kompella, "Virtual private LAN service (VPLS) using label distribution protocol (LDP) signaling," Internet Engineering Task Force, RFC 4762, January 2007.
J.-J. Pansiot, P. Mérindol, B. Donnet, and O. Bonaventure, "Internet topology discovery through mrinfo probing," Université catholique de Louvain (UCL), Tech. Rep., October 2009, see http://inl.info.ucl.ac.be/content/mrinfo.
N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with Rocketfuel," in Proc. ACM SIGCOMM, August 2002.
Y. Ohara, S. Imahori, and R. Van Meter, "MARA: Maximum alternative routing algorithm," in Proc. IEEE INFOCOM, April 2009.
K.-W. Kwong, L. Gao, R. Guérin, and Z.-L. Zhang, "On the feasibility and efficacy of protection routing in IP networks," in Proc. IEEE INFOCOM, March 2010.
B. Rajagopalan, J. Luciani, and D. Awduche, "IP over optical networks: a framework," Internet Engineering Task Force, RFC 3717, March 2004.
Network Protection, "Shared risk link group (SRLG)," February 2010, http://www.network-protection.net/ shared-risk-link-group-srlg/.
B. Huffaker, A. Dhamdhere, M. Fomenkov, and k. caffy, "Toward topology dualism: Improving the accuracy of AS annotations for routers," in Proc. Passive and Active Measurement Conference (PAM), April 2010.
D. Magoni and J. J. Pansiot, "Analysis of the autonomous system network topology," ACM SIGCOMM Computer Communication Review, vol. 31, no. 3, pp. 26 - 37, July 2001.
A. Broido and k. claffy, "Internet topology: Connectivity of IP graphs," in Proc. SPIE International Symposium on Convergence of IT and Communication (ITCom), August 2001.
A. L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, October 1999.
A. Medina, I. Matta, and J. Byers, "On the origin of power laws in internet topologies," ACM SIGCOMM Computer Communications Review, vol. 30, no. 2, pp. 18-28, April 2000.
Q. Chen, H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "The origin of power laws in internet topologies revisited," in Proc. IEEE INFOCOM, June 2002.
T. Petermann and P. De Los Rios, "Exploration of scale-free networks," The European Physical Journal B, vol. 38, p. 201, 2004.
L. Dall'Asta, I. Alvarez-Hamelin, A. Barrat, A. Vásquez, and A. Vespignani, "A statistical approach to the traceroute-like exploration of networks: Theory and simulations," in Proc. Combinatorial and Algorithmic Aspects of Networking (CAAN) Workshop, August 2004.
J. L. Guillaume and M. Latapy, "Relevance of massively distributed explorations of the internet topology: Simulation results," in Proc. IEEE INFOCOM, March 2005.
L. Li, D. Alderson, W. Willinger, and J. Doyle, "A first-principles approach to understanding the Internet's router-level topology," in Proc. ACM SIGCOMM, August 2004.
D. Alderson, L. Li, W. Willinger, and J. Doyle, "Understanding Internet topology: Principles, models, and validation," IEEE/ACM Transactions on Networking, vol. 13, no. 6, pp. 1205-1218, December 2005.