# Topology Inference and Link Parameter Estimation Based on End-to-End Measurements +
## 2 Network Model and Problem Formulation
### Multicast Additive Metrics  
Additive link metrics are extremely important in the field of network tomography and have been widely used over the years. Under such formulations, the end-to-end measurements corresponding to paths between terminal nodes are the sums of the individual component link metrics. Delay is an example of an inherent additive link metric, whereas loss rates and other multiplicative metrics can be transformed into additive using a logarithmic scale. The network tomography inference problem can then be expressed as the inverse problem of solving the system of linear equations \(\mathbf{y}=\mathbf{A}\cdot\mathbf{x}\), where \(\mathbf{x}\) is the vector of unknown link parameters, \(\mathbf{A}\) is the routing or measurement matrix representing the network topology, and \(\mathbf{y}\) is the vector of observed path-level end-to-end measurements. The goal is to estimate the unobserved vector \(\mathbf{x}\) given the aforementioned linear model and the known vector of measurements \(\mathbf{y}\). The difficulty lies in the fact that the system of linear equations is heavily under-determined. Using the previously described notation, an additive metric \(d:V\times V\rightarrow\mathbb{R}^{+}\) on tree \(T=(V,E)\) is a non-negative function such that:  
* \(0<d(e)<\infty,\ \forall e\in E\),
* \(d(i,j)=0\) if and only if \(i=j\), and
* \(d(i,j)=d(j,i)=\sum_{e\in p(i,j)}d(e)\), otherwise. The topology and the link lengths \(d(e),\forall e\in E\) of a tree \(T(s,D)=(V,E)\) can be recovered by the pairwise distances \(\mathcal{D}=\{d(i,j):i,j\in\{s\}\cup D\}\) between the terminal nodes under an additive metric [15]. Assuming that the link states are independent and stationary during the measurement period, we can construct the following additive metrics:  
* \(d(e)=-\log(\theta_{e}),\forall e\in E\), where \(\theta_{e}\) is the success rate (i.e., the complement of loss rate) of link \(e\). * \(d(e)=\theta_{e}=\text{Var}(Y_{e}),\forall e\in E\), where \(Y_{e}\) is a random variable that expresses the random queuing delay of link \(e\) and \(\theta_{e}\) is the square of jitter of link \(e\), with jitter defined as the standard deviation of delay \(\sigma(Y_{e})\) in order to be additive. In the first case, the link-state variable \(Y_{e}\) is equal to one (or zero) with probability \(\theta_{e}\) (or \(1-\theta_{e}\)), if the probe traverses successfully (or is lost on) link \(e\), and the outcome variable \(X_{k}\) takes value 1, if the probe reaches node \(k\), and value 0 otherwise. Then, the outcome variable at a particular node can be expressed as the product of the link-state variables corresponding to the links comprising the path from the source to that specific node. Furthermore, the probability that this outcome variable takes value one can be computed as the product of the success rates corresponding to the links along that same path. Therefore, we can construct an additive tree metric with a link length equal to the negative logarithm of the complement of the packet loss rate. In the second case, the link-state variable \(Y_{e}\) expresses the random queuing delay of link \(e\) and the outcome variable \(X_{k}\) represents the cumulative end-to-end queuing delay that is experienced by the probe on its way to node \(k\). Then, the outcome variable at a particular node can be expressed as the sum of the link-state variables corresponding to the links comprising the path from the source to that specific node. Moreover, given that the variance of a sum of independent random variables is the sum of their variances, the variance of this outcome variable can be computed as the sum of the performance parameters associated with the links along that same path. Consequently, we can construct an additive tree metric with a link length equal to the square of jitter.