Abstract
Full knowledge of the routing topology of the Internet is useful for a multitude of network management tasks. However, the full topology is often not known and is instead estimated using topology inference algorithms. Many of these algorithms use Traceroute to probe paths and then use the collected information to infer the topology. We perform real experiments and show that, in practice, routers may severely disrupt the operation of Traceroute and cause it to only provide partial information. We propose iTop, an algorithm for inferring the network topology when only partial information is available. iTop constructs a virtual topology, which overestimates the number of network components, and then repeatedly merges links in this topology to resolve it toward the structure of the true network. We perform extensive simulations to compare iTop to state-of-The-Art inference algorithms. Results show that iTop significantly outperforms previous approaches and its inferred topologies are within 5% of the original networks for all considered metrics. Additionally, we show that the topologies inferred by iTop significantly improve the performance of fault localization algorithms when compared with other approaches.
Recommended Citation
B. Holbert et al., "Network Topology Inference with Partial Information," IEEE Transactions on Network and Service Management, vol. 12, no. 3, pp. 406 - 419, article no. 7140827, Institute of Electrical and Electronics Engineers, Sep 2015.
The definitive version is available at https://doi.org/10.1109/TNSM.2015.2451032
Department(s)
Computer Science
Keywords and Phrases
Fault localization; Partial information; Topology inference
International Standard Serial Number (ISSN)
1932-4537
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
01 Sep 2015
