# Topology Inference and Link Parameter Estimation Based on End-to-End Measurements +
## 3 Topology Inference and Estimation of Link Parameters
### Distance-Based Agglomerative Hierarchical Clustering  
In order to infer the logical routing tree using the estimated pairwise distances between terminal nodes under the previously described additive metrics, we employ an agglomerative hierarchical clustering algorithm with \(O(n^{2})\) complexity [13], where \(n\) is the number of network nodes. Furthermore, given that there is a one-to-one mapping between the returned edge lengths \(d(e),\forall e\in E\) and the underlying link performance parameters \(\theta_{e},\forall e\in E\) (see Section 2.2), we can also estimate the latter from the former as follows:  
* loss rate of link \(e=1-\theta_{e}=1-10^{-d(e)}\), and
* jitter of link \(e=\sqrt{\theta_{e}}=\sqrt{d(e)},\ \forall e\in E\). Broadly speaking, the employed clustering algorithm operates in a bottom-up manner, starting with a set including all destination nodes, each one in its own cluster, and selecting at each iteration two nodes that are joined and replaced in the set by a new node designated as their parent. This process continues recursively on this reduced set until there is only one node left, which will be the (single) child of the root (source) \(s\). A high-level overview of the algorithm is presented in Figure 2.  
In the following, we discuss the specifics of the functionality and the detailed operation of each depicted step:  
* The _input_ of the algorithm is the source node \(s\), the set of destination nodes \(D\), and the estimated pairwise distances between terminal nodes \(\hat{\mathcal{D}}=\{\hat{d}(i,j):i,j\in\{s\}\cup D\}\), calculated as described in Section 2.2. * The _output_ of the algorithm is the logical routing tree \(T(s,D)=(V,E)\) and the link lengths \(d(e),\forall e\in E\), from which we can obtain the link parameters \(\theta_{e},\forall e\in E\). * At _initialization_, we start by adding the source and the destinations to the set of nodes, \(V=\{s\}\cup D\), and we initialize the set of edges equal to the empty set, \(E=\emptyset\). * For every pair of nodes \(i\) and \(j\) of the routing tree, the lowest common ancestor, LCA\((i,j)\), is the node that is located the farthest from the root and has both nodes as descendants. The depth of the lowest common ancestor, \(\ell(i,j)=d(s,\text{LCA}(i,j))\), expresses the length of the shared path from \(s\) to \(i\) and \(j\). Given that there is a one-to-one mapping between the pairwise distances and the LCA depths, we can equivalently employ the latter to infer the routing tree and estimate the link parameters. To that end, at the step _construction of LCA depths matrix_, we compute the \(|D|\times|D|\) matrix of LCA depths \(\mathbf{L}=[\ell(i,j)],\ \forall i,j\in D\) using the equations \[\ell(i,j)=\frac{1}{2}[d(s,i)+d(s,j)-d(i,j)],\ \forall i,j\in D\text{ and}\] (9) \[\ell(i,i)=d(s,i),\ \forall i\in D.\] (10)  
Figure 2: High-level overview of the proposed clustering algorithm. * At the _neighbor selection_ step, we choose the two nodes that are deemed siblings and are about to be joined. Taking into account that the LCA depth of two nodes expresses the length of their shared path, we select the nodes \(i\) and \(j\) that are _mutual or reciprocal nearest neighbor_ (RNNs), meaning that, for each one, their LCA depth is the largest among all others: \(\forall k\
eq i,j\), \(\ell(i,j)\geq\ell(i,k),\ell(j,k)\). The idea is that two siblings must have the largest shared path with one another, compared to all other nodes. Such RNNs can be found efficiently by constructing _nearest neighbor_ (NN) chains [16]. Essentially, a NN chain follows paths in the nearest neighbor graph of the clusters, until the paths terminate in a pair of RNNs. It starts at an arbitrary initial node, and it is iteratively extended from the current node at the top of the chain, say \(i\), to its nearest neighbor \(j\) such that \(\ell(i,j)=\max\limits_{k\
eq i}\ell(i,k)\), until it necessarily terminates at a pair of RNNs. After joining the discovered RNNs, the rest NN chain is still valid and, therefore, it is not discarded.