# Topology Inference and Link Parameter Estimation Based on End-to-End Measurements +
## 1 Introduction
Although the aforementioned initial study forms the basis and the starting point of our current research, the present work has been vastly improved in terms of technical content, analysis, evaluation, and presentation, in a way that complements and significantly extends the contribution of the preliminary conference version. The main differences between the current article and the partial preliminary conference version can be briefly summarized as presenting new ideas (recovery of physical topologies, alternative reduction update formulas), additional experimentation (examining and quantifying a larger number of features and comparing with conventional tools), and a tangible application of the devised clustering algorithm. In greater detail, an important new feature of the proposed and implemented network tomography utility is the ability to infer not only logical routing trees but also the underlying physical routing trees by incorporating information about hop counts. Furthermore, we demonstrate that the reduction update formula, which is used at every iteration of the clustering algorithm for calculating the distances between the newly generated parent and the rest nodes, has a significant impact on the estimation of the link performance parameters. Taking that into consideration, we explore and experimentally compare several reduction update formulas that guarantee the correctness of the agglomerative algorithm, not being limited to only fixed schemes but also including an adaptive scheme that is tailored to the discovered hierarchy, since it depends on the number of offspring of the involved nodes. Finally, we go beyond simply presenting a modified nearest neighbor (NN) chain-extended agglomerative clustering algorithm. We design, implement, and experiment with a tangible application of the proposed inferential method that combines network tomography (NT)-based monitoring with change point analysis to realize performance anomaly detection over an actual topology constructed in an open large-scale testbed. Overall, through the extended experimentally-driven analysis, we demonstrate the feasibility of our approach, and we provide a more detailed performance evaluation by examining and quantifying a larger number of features while also underlining a number of practical tools that can be used in the development and testing of network services. By designing, implementing, and presenting a tangible application that leverages the devised algorithm and the described extensions/modifications, we demonstrate the practical value of our approach, motivate implementation-driven deployments of similar utilities, and provide insights and good practices that can be adopted by researchers and developers working in related problems. To summarize, the key contributions of this article are the following:  
* The logical routing tree can be considered as the \"skeleton\" of the underlying physical topology, including only its intermediate branching points. To infer physical routing trees, we extend the nearest neighbor (NN) chain-enhanced agglomerative clustering algorithm [13] by incorporating information about hop counts. * The reduction update formula, which is used at every iteration for calculating the distances between the newly generated parent and the rest nodes, is a critical feature of clustering algorithms. Taking that into consideration, we explore several reduction update formulas that guarantee the correctness of the proposed algorithm, and we examine their impact on the estimation accuracy of the link performance parameters. * We implement the proposed clustering algorithm with all extensions and alternative options discussed in this paper, creating a complete command-line-based network tomography tool. We publish [14] the source code under a permissive free software license, along with detailed documentation. * We extensively evaluate the performance of the proposed algorithm, over a comprehensive set of criteria, with real topologies constructed in an open large-scale testbed.