Abstract
Boolean tomography is based on exploiting performance level correlations of end-to-end measurements to identify the congested links. Most work to date attempts to find the congested links according to the observed pattern of congested paths and the prior link congestion probabilities. In their work, the prior link congestion probabilities are either assumed to be unrealistically equal or estimated by a computationally complex algorithm. Furthermore, all congested paths are mapped down to the same “bad” state regardless of their congestion degrees, then separate causes of congestion may be identified as a common cause. In this paper, we propose a fast Bottom-Up Approach named BUA to estimate the prior probabilities based on a small number of measurement snapshots. BUA is computationally simpler than the existing approaches since it computes the congestion probability of each individual link through an explicit function of the measurements. We then extract the subsets of congested paths that might traverse the same congested links in current measurement snapshot according to their congestion degrees. The links that cause the congestion of each subset of paths are identified with the aid of the learnt probabilities. Simulations in different network scenarios demonstrate that our approach is able to improve the accuracy of the identification procedure.