TY - JOUR
T1 - Graph Based Induction of unresponsive routers in Internet topologies
AU - Kardes, Hakan
AU - Gunes, Mehmet Hadi
AU - Sarac, Kamil
N1 - Publisher Copyright:
© 2015 Elsevier B.V.
PY - 2015/4/22
Y1 - 2015/4/22
N2 - 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.
AB - 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.
KW - Internet mapping
KW - Internet topology measurement
KW - Unresponsive router resolution
UR - http://www.scopus.com/inward/record.url?scp=84924656947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84924656947&partnerID=8YFLogxK
U2 - 10.1016/j.comnet.2015.02.012
DO - 10.1016/j.comnet.2015.02.012
M3 - Article
AN - SCOPUS:84924656947
SN - 1389-1286
VL - 81
SP - 178
EP - 200
JO - Computer Networks
JF - Computer Networks
ER -