# Topology Inference and Link Parameter Estimation Based on End-to-End Measurements +
## 1 Introduction  
Nowadays, due to the proliferation of network architectures and technologies, advanced network management requires successfully addressing the challenge of collecting and analyzing massive volumes of data. Network monitoring refers to systems that constantly monitor computer networks for problematic components or abnormal traffic variations, and either notify (via dedicated alarm mechanisms) and/or aid network administrators in troubleshooting and recovering normal operations. Considerable effort has been invested in network monitoring, especially lately, leading to the emergence of radical approaches and disruptive technologies like In-band Network Telemetry (INT) [1] and Programmable Forwarding Engine (PFE) accelerated telemetry systems [2]. These approaches address different challenges and operate in diverse, inter-connected environments, such as legacy, wireless, and SDN-enabled infrastructures. Among them, Network Tomography (NT) has been proposed as an efficient and lightweight methodology for inferential network monitoring based on indirect measurements [3]. Broadly speaking, NT can be classified into the following three categories [4]:  
_link-level NT_ that regards the estimation of per link Quality of Service (QoS) parameters (e.g., loss rates, delays, jitter) based on end-to-end path measurements,  
_path-level NT_ that concerns the estimation of the origin-destination (OD) traffic intensity matrix based on link-level measurements [5], and  
_topology inference_ for reconstructing the topology of the network itself, which is considered unknown. It can also be categorized as active (injecting probes) or passive (observing existing traffic), depending on the employed measurement methodology. Compared to conventional monitoring techniques that involve the direct measurement of all objects of interest, NT does not require the special-purpose cooperation of all intermediate network elements and reduces the measurement traffic overhead. In this paper, we jointly consider topology inference and link-level NT, aiming at a \"minimally-required knowledge\" holistic monitoring tool that needs only end-to-end measurements, obtained at the edge through active multicast probing. Our objective is to present and experimentally validate the proposed approach in a generic context, going beyond network monitoring in itself and providing a motivating example of a representative practical application of the developed clustering algorithm. Over the years, multicast-based NT has received a lot of research attention [6; 7; 8; 9; 10]. Compared to these studies, our approach makes use of additive metrics, recovers both the unknown topology and link performance parameters, requires only the pairwise joint empirical distribution of the outcome variables at the destination nodes as input, and is easier to implement since it comprises a heuristic recursive algorithm. Furthermore, it does not employ maximum likelihood estimators, which are not computationally efficient for large-size networks because they involve finding the roots of polynomials whose degrees depend on the number of outgoing links at the internal nodes. Finally, given that the required pairwise distances between terminal nodes can be calculated using unicast packet stripe probing as well, the proposed method is not only feasible under multicast probing. The grouping algorithms presented in [11; 12] are the most relevant to our work. However, by incorporating the use of nearest neighbor chains into the agglomerative clustering algorithm, we manage to further reduce the computational complexity of the proposed approach from \(O(n^{2}\log n)\) to \(O(n^{2})\). Moreover, all aforementioned works infer the logical routing trees, where paths with no branches are represented as a single logical link. Contrary to that, our method can successfully identify all single-child nodes. This work builds on [13] and provides important advances compared to what has been published so far.