Modern computer networks pose a great challenge for monitoring the network performance due to their large scale and high complexity. Directly measuring the performance of internal network elements is prohibitive due to the tremendous overhead. Alternatively, network tomography, a technique that infers the unobserved network characteristics (e.g., link delays) from a small number of measurements (e.g., end-to-end path delays), is a promising solution for monitoring the internal network state in an e cient and e ective manner. This thesis initiates two variants of network tomography: concentrated network tomography and bound-based network tomography. The former is motivated by the practical needs that network operators normally concentrate on the performance of critical paths; the latter is due to the need of estimating performance bounds whenever exact performance values cannot be determined. This thesis tackles core technical di culties in concentrated network tomography and bound- based network tomography, including (1) the path identi ability problem and the monitor deploy- ment strategy for identifying a set of target paths, (2) strategies for controlling the total error bound as well as the maximum error bound over all network links, and (3) methods of constructing measure- ment paths to obtain the tightest total error bound. We evaluate all the solutions with real-world Internet service provider (ISP) networks. The theoretical results and the algorithms developed in this thesis are directly applicable to network performance management in various types of networks, where directly measuring all links is practically impossible. / Graduate

No description available.