John Heidemann / Papers / Selecting Representative IP Addresses for Internet Topology Studies

Selecting Representative IP Addresses for Internet Topology Studies
Xun Fan and John Heidemann
USC/Information Sciences Institute

Citation

Xun Fan and John Heidemann. Selecting Representative IP Addresses for Internet Topology Studies. Proceedings of the ACM Internet Measurement Conference (Melbourne, Australia, Nov. 2010), 411–423. [DOI] [PDF] [alt PDF]

Abstract

An Internet hitlist is a set of addresses that cover and can represent the the Internet as a whole. Hitlists have long been used in studies of Internet topology, reachability, and performance, serving as the destinations of traceroute or performance probes. Most early topology studies used manually generated lists of prominent addresses, but evolution and growth of the Internet make human maintenance untenable. Random selection scales to today’s address space, but most random addresses fail to respond. In this paper we present what we believe is the first automatic generation of hitlists informed censuses of Internet addresses. We formalize the desirable characteristics of a hitlist: reachability, each representative responds to pings; completeness, they cover all the allocated IPv4 address space; and stability, list evolution is minimized when possible. We quantify the accuracy of our automatic hitlists, showing that only one-third of the Internet allows informed selection of representatives. Of informed representatives, 50–60% are likely to respond three months later, and we show that causes for non-responses are likely due to dynamic addressing (so no stable representative exists) or firewalls. In spite of these limitations, we show that the use of informed hitlists can add 1.7 million edge links (a 5% growth) to traceroute-based Internet topology studies Our hitlists are available free-of-charge and are in use by several other research projects.

Bibtex Citation

@inproceedings{Fan10a,
  author = {Fan, Xun and Heidemann, John},
  title = {Selecting Representative IP Addresses for Internet
                  Topology Studies},
  booktitle = {Proceedings of the ACM Internet Measurement Conference},
  year = {2010},
  sortdate = {2010-11-01},
  project = {ant, amite, lacrend, lander},
  jsubject = {topology_modeling},
  usessoftware = {iplists},
  pages = {411--423},
  address = {Melbourne, Australia},
  month = nov,
  publisher = {ACM},
  jlocation = {johnh: pafile},
  keywords = {IPv4 address space, hitlists, internet topology},
  url = {https://ant.isi.edu/%7ejohnh/PAPERS/Fan10a.html},
  xtocompleteotherurl = {xxx},
  doi = {http://dx.doi.org/10.1145/1879141.1879195},
  pdfurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Fan10a.pdf},
  myorganization = {USC/Information Sciences Institute},
  copyrightholder = {ACM},
  copyrightterms = {
  Permission to make digital or hard copies of all or part of this work
  for personal or classroom use is granted without fee provided that
  copies are not made or distributed for profit or commercial advantage
  and that copies bear this notice and the full citation on the first
  page. To copy otherwise, to republish, to post on servers or to
  redistribute to lists, requires prior specific permission and/or a
  fee.
  }
}

Copyright

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Copyright © by John Heidemann