School of Information and Computer Science, Anhui Agricultural University, Hefei, Anhui, China.
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China.
PLoS One. 2016 Oct 4;11(10):e0163706. doi: 10.1371/journal.pone.0163706. eCollection 2016.
In this study, we address the problem of selecting the optimal end-to-end paths for link loss inference in order to improve the performance of network tomography applications, which infer the link loss rates from the path loss rates. Measuring the path loss rates using end-to-end probing packets may incur additional traffic overheads for networks, so it is important to select the minimum path set carefully while maximizing their performance. The usual approach is to select the maximum independent paths from the candidates simultaneously, while the other paths can be replaced by linear combinations of them. However, this approach ignores the fact that many paths always exist that do not lose any packets, and thus it is easy to determine that all of the links of these paths also have 0 loss rates. Not considering these good paths will inevitably lead to inefficiency and high probing costs. Thus, we propose an adaptive path selection method that selects paths sequentially based on the loss rates of previously selected paths. We also propose a theorem as well as a graph construction and decomposition approach to efficiently find the most valuable path during each round of selection. Our new method significantly outperforms the classical path selection method based on simulations in terms of the probing cost, number of accurate links determined, and the running speed.
在这项研究中，我们解决了选择最佳端到端路径进行链路损耗推断的问题，以提高网络层析成像应用的性能，这些应用通过路径损耗率来推断链路损耗率。使用端到端探测数据包测量路径损耗率可能会给网络带来额外的流量开销，因此在选择最小路径集时，仔细选择并最大化其性能非常重要。通常的方法是同时从候选者中选择最大独立路径，而其他路径可以通过它们的线性组合来替代。然而，这种方法忽略了这样一个事实，即许多路径始终存在而不会丢失任何数据包，因此很容易确定这些路径的所有链路也具有 0 损耗率。不考虑这些良好的路径将不可避免地导致效率低下和高探测成本。因此，我们提出了一种自适应路径选择方法，该方法根据先前选择的路径的损耗率顺序选择路径。我们还提出了一个定理以及一种图构造和分解方法，以便在每次选择轮次中有效地找到最有价值的路径。我们的新方法在探测成本、确定的准确链路数量和运行速度方面，通过模拟显著优于基于经典的路径选择方法。
