Graph Based Induction of unresponsive routers in Internet topologies

Hakan Kardes, Mehmet Hadi Gunes, Kamil Sarac

    Research output: Contribution to journalArticlepeer-review

    8 Scopus citations

    Abstract

    Internet topology measurement studies utilize traceroute to collect path traces from the Internet. A router that does not respond to a traceroute probe is referred as an unresponsive router and is represented by a '' in the traceroute output. Unresponsive router resolution refers to the task of identifying the occurrences of ''s that belong to the same router in the underlying network. This task is an important step in building representative traceroute-based topology maps and obtaining an optimum solution, i.e.; minimal graph under trace and distance preservation conditions, is shown to be NP-complete. In this paper, we first analyze the nature of unresponsive routers and identify different types of unresponsiveness. We also conduct an experimental study to understand how the responsiveness of routers has changed over the last decade. We then utilize a novel graph data indexing approach to build an efficient solution to the unresponsive router resolution problem. The results of our experiments on both synthetic and sampled topologies show a significant improvement in accuracy and effectiveness over the existing approaches. Our experiments also demonstrate that applying IP alias resolution along with unresponsive router resolution results in a final topology closer to the original topology.

    Original languageEnglish
    Pages (from-to)178-200
    Number of pages23
    JournalComputer Networks
    Volume81
    DOIs
    StatePublished - 22 Apr 2015

    Keywords

    • Internet mapping
    • Internet topology measurement
    • Unresponsive router resolution

    Fingerprint

    Dive into the research topics of 'Graph Based Induction of unresponsive routers in Internet topologies'. Together they form a unique fingerprint.

    Cite this