| Today's Internet is a massive, distributed network which continues to explode in size as e-commerce and related activities grow. The heterogeneous and largely unregulated structure of the Internet renders tasks such as dynamic routing, optimized service provision, and detection of anomalous/malicious behavior extremely challenging. The problem is compounded by the fact that one cannot rely on the cooperation of individual servers and routers to aid in the collection of network traffic measurements vital for these tasks. In many ways, network monitoring and inference problems bear a strong resemblance to ill-posed inverse problems.;This thesis reviews the field of large-scale network tomography. The main focus of the thesis is the development of a pseudo likelihood approach for the general linear network tomography problems. The basic idea of pseudo likelihood is to form simple subproblems and ignore the dependences among the subproblems to form a product likelihood of the subproblems. As a result, this approach keeps a good balance between the computational complexity and the statistical efficiency of the parameter estimation. Some statistical properties of the pseudo likelihood estimator, such as consistency and asymptotic normality, are established. A pseudo expectation-maximization (EM) algorithm is developed to maximize the pseudo log-likelihood function. Another focus of the paper is the application of a uniform geometric interpretation to two up-to-date origin-destination traffic matrix estimation methods, namely gravity-MMI and pseudo-IPF. We study the convergence rates of iterative scaling methods for maximum entropy models, and justify the use of maximum entropy models in OD traffic network tomography problems under the Gaussian traffic model such that the maximum entropy estimate approximately converges to the minimum mean square error (MSE) estimate. A novel partial measurement approach is further proposed to the problem of dynamic system monitoring, with OD traffic matrix estimation as one of its applications. All proposed methods are validated either from real or simulated network datasets. |
