Home > Practical Network Tomography > HTML MARC |

000174697 001__ 174697 000174697 005__ 20190509132417.0 000174697 0247_ $$2doi$$a10.5075/epfl-thesis-5332 000174697 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis5332-9 000174697 02471 $$2nebis$$a6883242 000174697 037__ $$aTHESIS 000174697 041__ $$aeng 000174697 088__ $$a5332 000174697 245__ $$aPractical Network Tomography 000174697 269__ $$a2012 000174697 260__ $$bEPFL$$c2012$$aLausanne 000174697 300__ $$a160 000174697 336__ $$aTheses 000174697 520__ $$aIn this thesis, we investigate methods for the practical and accurate localization of Internet performance problems. The methods we propose belong to the field of network loss tomography, that is, they infer the loss characteristics of links from end-to-end measurements. The existing versions of the problem of network loss tomography are ill-posed, hence, tomographic algorithms that attempt to solve them resort to making various assumptions, and as these assumptions do not usually hold in practice, the information provided by the algorithms might be inaccurate. We argue, therefore, for tomographic algorithms that work under weak, realistic assumptions. We first propose an algorithm that infers the loss rates of network links from end-to-end measurements. Inspired by previous work, we design an algorithm that gains initial information about the network by computing the variances of links' loss rates and by using these variances as an indication of the congestion level of links, i.e., the more congested the link, the higher the variance of its loss rate. Its novelty lies in the way it uses this information – to identify and characterize the maximum set of links whose loss rates can be accurately inferred from end-to-end measurements. We show that our algorithm performs significantly better than the existing alternatives, and that this advantage increases with the number of congested links in the network. Furthermore, we validate its performance by using an "Internet tomographer" that runs on a real testbed. Second, we show that it is feasible to perform network loss tomography in the presence of "link correlations," i.e., when the losses that occur on one link might depend on the losses that occur on other links in the network. More precisely, we formally derive the necessary and sufficient condition under which the probability that each set of links is congested is statistically identifiable from end-to-end measurements even in the presence of link correlations. In doing so, we challenge one of the popular assumptions in network loss tomography, specifically, the assumption that all links are independent. The model we propose assumes we know which links are most likely to be correlated, but it does not assume any knowledge about the nature or the degree of their correlations. In practice, we consider that all links in the same local area network or the same administrative domain are potentially correlated, because they could be sharing physical links, network equipment, or even management processes. Finally, we design a practical algorithm that solves "Congestion Probability Inference" even in the presence of link correlations, i.e., it infers the probability that each set of links is congested even when the losses that occur on one link might depend on the losses that occur on other links in the network. We model Congestion Probability Inference as a system of linear equations where each equation corresponds to a set of paths. Because it is infeasible to consider an equation for each set of paths in the network, our algorithm finds the maximum number of linearly independent equations by selecting particular sets of paths based on our theoretical results. On the one hand, the information provided by our algorithm is less than that provided by the existing alternatives that infer either the loss rates or the congestion statuses of links, i.e., we only learn how often each set of links is congested, as opposed to how many packets were lost at each link, or to which particular links were congested when. On the other hand, this information is more useful in practice because our algorithm works under assumptions weaker than those required by the existing alternatives, and we experimentally show that it is accurate under challenging network conditions such as non-stationary network dynamics and sparse topologies. 000174697 6531_ $$aNetwork Loss Tomography 000174697 6531_ $$aNetwork Measurements 000174697 6531_ $$aNetwork Monitoring 000174697 6531_ $$aLink-loss Inference 000174697 6531_ $$aCongestion Probability 000174697 6531_ $$aCorrelated Links 000174697 700__ $$aGhita, Denisa Gabriela 000174697 720_2 $$aThiran, Patrick$$edir.$$g103925$$0240373 000174697 720_2 $$aArgyraki, Katerina$$edir.$$g176638$$0243542 000174697 8564_ $$uhttps://infoscience.epfl.ch/record/174697/files/EPFL_TH5332.pdf$$zTexte intégral / Full text$$s1154603$$yTexte intégral / Full text 000174697 909C0 $$xU10431$$0252454$$pLCA3 000174697 909C0 $$xU12550$$0252412$$pNAL 000174697 909CO $$ooai:infoscience.tind.io:174697$$qDOI2$$qGLOBAL_SET$$pthesis$$pthesis-bn2018$$pDOI$$pIC 000174697 918__ $$dEDIC2005-2015$$cIIF$$aIC 000174697 919__ $$aLCA3 000174697 919__ $$aNAL 000174697 920__ $$b2012 000174697 970__ $$a5332/THESES 000174697 973__ $$sPUBLISHED$$aEPFL 000174697 980__ $$aTHESIS