| Network tomography has recently emerged as a promising method for indirectly inferring network state information from end-to-end measurements. In this thesis, I present novel methodologies for several challenging network inference problems. I also tackle practical problems faced in deploying tomographic techniques in the Internet and provide practical solutions to address and overcome some of these difficulties.; The major contributions are four-fold. First, a passive monitoring technique for estimating internal link-level drop rates is proposed. This approach only requires TCP traces from the end hosts, and it is more effective and less invasive than other tomography schemes. I have demonstrated its effectiveness using ns-2 simulations. I have also conducted theoretical queuing analysis which corroborates the results obtained through simulation experiments.; Second, in delay distribution estimation, a non-parametric wavelet-based approach is developed for estimating link-level queuing delay characteristics. The approach overcomes the bias-variance tradeoff caused by delay quantization, a problem associated with most existing delay estimation methods. Realistic network simulations are carried out using ns-2 simulations to demonstrate the accuracy of the estimation procedure.; Third, in order to make tomographic inference techniques more practical, I investigated a Round Trip Time (RTT) based measurement technique. This novel technique does not require clock synchronization and does not require special-purpose cooperation from receivers, enabling deployment of my tomographic tool from any host in the Internet. I demonstrated that my RTT method is effective under a wide range of operating conditions both in an emulation environment and in the Internet.; Finally, to make inference techniques more reliable and robust, I formulated the tomographic data collection process as an optimal experimental design problem, in which a fixed number of network probes are optimally distributed to minimize the squared estimation error of the tomographic reconstruction. Explicit forms for the estimation errors are derived in terms of topology, noise levels, and number and distribution of probes. This analysis reveals the dominant sources causing ill-conditioning and scalability issues in network tomography. |
