For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Fast Bottom-Up Approach to Identify the Congested Network Links
Haibo SU Shijun LIN Yong LI Li SU Depeng JIN Lieguang ZENG
IEICE TRANSACTIONS on Communications
Publication Date: 2010/03/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network Management/Operation
network tomography, congested links, CLINK algorithm,
Full Text: PDF(94.8KB)>>
In network tomography, most work to date is based on exploiting probe packet level correlations to infer the link loss rates and delay distributions. Some other work focuses on identifying the congested links using uncorrelated end-to-end measurements and link prior probability of being congested. In their work, the prior probabilities are identified by the matrix inversion with a number of measurement snapshots, and the algorithm to find the congested links is heuristic and not optimal. In this letter, we present a new estimator for the prior probabilities that is computationally simple, being an explicit function of the measurement snapshots. With these prior probabilities, the identification of the congested link set is equivalent to finding the solution for a probability maximization problem. We propose a fast bottom-up approach named FBA to find the solution for this problem. The FBA optimizes the solution step by step from the bottom up. We prove that the solution by the FBA is optimal.