Pseudo likelihood estimation and iterative proportional refitting in network tomography

摘要

Summary form only given. The network origin-destination (OD) matrix is very important for network performance improvement. In this talk, we review the pseudo likelihood approach (Liang and Yu, IEEE Trans. Signal Processing, to appear) for OD matrix estimation based on link counts collected at routers. The basic idea of pseudo likelihood is to construct simple subproblems and ignore the dependences among the subproblems to form a product likelihood of the subproblems. In doing so, we balance the computational requirements and estimation accuracies. As in Cao, Davis, Vander Wiel and Yu (J. Amer. Statist. Assoc, 2000), iterative proportional fitting (IPF) is used in our approach to match initial estimates obtained from pseudo likelihood estimation with the linear constraints imposed by observed link counts. We demonstrate the relationship between IPF and entropy minimization, and give the convergence rate of the IPF algorithm. Last, we present the connections and differences between IPF and the entropy penalization based method proposed by Donoho, Lund, Roughan and Zhang (Tech. Report 2003-15, Statistics Department, Stanford Univ).