[en] Over the past two decades, the research community has developed many approaches to study the Internet topology. In particular, starting from 2007, various tools explored the inference of subnets, i.e., sets of devices located on the same connection medium which can communicate directly with each other at the link layer.
In this paper, we first discuss how today's traffic engineering policies increase the difficulty of subnet inference. We carefully characterize typical difficulties and quantify them in the wild. Next, we introduce WISE (Wide and lInear Subnet inferencE), a new tool which tackles those difficulties and discovers, in a linear time, large networks subnets. Based on two ground truth networks, we demonstrate that WISE outperforms state-of-the-art tools. Then, through large-scale
measurements, we show that the selection of a vantage point with WISE has a marginal effect regarding accuracy. Finally, we discuss how subnets can be used to infer neighborhoods (i.e., aggregates of subnets located at most one
hop from each other). We discuss how these neighborhoods can lead to bipartite models of the Internet and present validation results and an evaluation of neighborhoods in the wild, using WISE. Both our code and data are freely
available.
Disciplines :
Computer science
Author, co-author :
Grailet, Jean-François ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique et intelligence artificielle
Donnet, Benoît ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorithmique des grands systèmes
Language :
English
Title :
Virtual Insanity: Linear Subnet Discovery
Publication date :
June 2020
Journal title :
IEEE Transactions on Network and Service Management
ISSN :
1932-4537
Publisher :
Institute of Electrical and Electronics Engineers, United States - New York
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
B. Donnet and T. Friedman, "Internet topology discovery: A survey, "IEEE Commun. Surveys Tuts., vol. 9, no. 4, pp. 56-69, 4th Quart., 2007.
B. Augustin et al., "Avoiding traceroute anomalies with Paris traceroute, "in Proc. ACM Internet Meas. Conf. (IMC), Oct. 2006, pp. 153-158.
B. Augustin, B. Krishnamurthy, and W. Willinger, "IXPs: Mapped" in Proc. ACM Internet Meas. Conf. (IMC), Nov. 2009, pp. 336-349.
G. Nomikos and X. Dimitropoulos, "traIXroute: Detecting IXPs in traceroute paths, "in Proc. Passive Active Meas. Conf. (PAM), Apr. 2016, pp. 346-358.
Y. Shavitt and N. Zilberman, "Geographical Internet PoP level maps, "in Proc. Traffic Monitoring Anal. Workshop (TMA), Mar. 2012. pp. 121-124.
D. Feldman, Y. Shavitt, and N. Zilberman, "A structural approach for PoP geo-location, "Comput. Netw., vol. 56, no. 3, pp. 1029-1040, Feb. 2012.
J. Mogul and J. Postel, "Internet standard subnetting procedure, "Internet Eng. Task Force, RFC 950, Aug. 1985.
M. H. Gunes and K. Saraç, "Inferring subnets in router-level topology collection studies, "in Proc. ACM/USENIX Internet Meas. Conf. (IMC), Nov. 2007, pp. 203-208.
M. E. Tozal and K. Saraç, "TraceNET: An Internet topology data collector, "in Proc. ACM Internet Meas. Conf. (IMC), Nov. 2010, pp. 356-368.
M. E. Tozal and K. Saraç, "Subnet level network topology mapping, "in Proc. IEEE Int. Perform. Comput. Commun. Conf. (IPCCC), Nov. 2011, pp. 1-8.
J.-F. Grailet, F. Tarissan, and B. Donnet, "TreeNET: Discovering and connecting subnets, "in Proc. Traffic Monitoring Anal. Workshop (TMA), Apr. 2016, pp. 9-16.
B. Augustin, R. Teixeira, and T. Friedman, "Measuring load-balanced paths in the Internet, "in Proc. ACM Internet Meas. Conf. (IMC), Oct. 2007, pp. 149-160.
K. Vermeulen, J. P. Rohrer, R. Beverly, O. Fourmaux, and T. Friedman, "Diamond-Miner: Comprehensive discovery of the Internet's topology diamonds, "in Proc. USENIX Symp. Netw. Syst. Design Implement. (NSDI), Feb. 2020, pp. 479-493.
J.-F. Grailet and B. Donnet, "Revisiting subnet inference WISE-ly, "in Proc. Network Traffic Meas. Anal. Conf. (TMA), Jun. 2019.
F. Tarissan, M. Latapy, P. Mérindol, J.-J. Pansiot, B. Quoitin, and B. Donnet, "Towards Internet topology modeling through bipartite graphs, "Comput. Netw., vol. 57, no. 11, pp. 2331-2347, Aug. 2013.
P. Mérindol, B. Donnet, O. Bonaventure, and J.-J. Pansiot, "On the impact of layer-2 on node degree distribution, "in Proc. ACM Internet Meas. Conf. (IMC), Nov. 2010, pp. 179-191.
P. Marchetta, P. Mérindol, B. Donnet, A. Pescapé, and J.-J. Pansiot, "Quantifying and mitigating IGMP filtering in topology discovery, "in Proc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2012, pp. 1871-1876.
K. Hubbard, M. Kosters, D. Conrad, D. Karrenberg, and J. Postel, "Internet registry IP allocation guidelines, "Internet Eng. Task Force, RFC 2050, Nov. 1996.
A. Retana, R. White, V. Fuller, and D. McPherson, "Using 31-bit prefixes on IPv4 point-to-point links, "Internet Eng. Task Force, RFC 3021, Dec. 2000.
H. Kardes, M. Gunes, and T. Oz, "Cheleby: A subnet-level Internet topology mapping system, "in Proc. Int. Commun. Syst. Netw. Workshops (COMSNETS), Jan. 2012, pp. 1-10.
Y. Vanaubel, J.-J. Pansiot, P. Mérindol, and B. Donnet, "Network fingerprinting: TTL-based router signatures, "in Proc. ACM Internet Meas. Conf. (IMC), Oct. 2013, pp. 369-376.
J.-F. Grailet and B. Donnet, "Towards a renewed alias resolution with space search reduction and IP fingerprinting, "in Proc. Netw. Traffic Meas. Anal. Conf. (TMA), Jun. 2017, pp. 100-108.
N. Spring, R. Mahajan, and D. Wetherall, "Measuring ISP topologies with rocketfuel, "in Proc. ACM Conf. Appl. Technol. Archit. Protocols Comput. Commun. (SIGCOMM), Aug. 2002, pp. 133-145.
K. Keys. Iffinder a Tool for Mapping Interfaces to Routers. Accessed: Feb. 5, 2020. [Online]. Available: Http://www.caida.org/tools/measurement/iffinder/
B. Donnet, P. Raoult, T. Friedman, and M. Crovella, "Efficient algorithms for large-scale topology discovery, "in Proc. ACM Int. Conf. Meas. Model. Computer Syst. (SIGMETRICS), Jun. 2005, pp. 327-338.
The CAIDA UCSD. (2013). The AS Relationship. [Online]. Available: Http://data.caida.org/datasets/as-relationships/
D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-world' networks, "Nature, vol. 393, pp. 440-442, Jun. 1998.
M. E. J. Newman, "Scientific collaboration networks. I. Network construction and fundamental results, "Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., vol. 64, no. 1, Jun. 2001, Art. no. 016131.
A. Iamnitchi, R. Matei, and I. T. Foster, "Small-world file-sharing communities, "in Proc. IEEE INFOCOM, Apr. 2004, pp. 952-963.
Y. Vanaubel, P. Mérindol, J.-J. Pansiot, and B. Donnet, "Through the wormhole: Tracking invisible MPLS tunnels, "in Proc. ACM Internet Meas. Conf. (IMC), Nov. 2017, pp. 29-42.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.