Show simple item record

dc.contributor.advisorQui, Lili, Ph.D.en
dc.contributor.advisorZhang, Yin, doctor of computer scienceen
dc.creatorSong, Han Hee, 1978-en
dc.date.accessioned2016-03-03T15:55:15Z
dc.date.available2016-03-03T15:55:15Z
dc.date.issued2006-05en
dc.identifierdoi:10.15781/T2NX21en
dc.identifier.urihttp://hdl.handle.net/2152/33510en
dc.description.abstractAs the Internet continues to grow, it is increasingly important for users, service providers, and application developers to measure, debug, and understand the performance of the wide-area network. Consequently, network measurement studies have become an essential to a wide variety of current and emerging network applications. In this thesis, we research scalable and flexible network measurement. The thesis consists of two parts: Exact Reconstruction of Network Path Properties (Part I) and Approximate Reconstruction of Network Path Properties (Part II). In Part I, we solve the problem of selecting a set of paths to monitor in order to reconstruct the exact properties of all the paths comprising a network. For an overlay network with N end hosts, existing systems either require O (N²) measurements, and thus lack scalability, or can only estimate the latency but not congestion or failures. The algebraic approach we propose in this work selectively monitors k linearly independent paths that can fully describe all the O(N²) paths. The loss rates and latency of these k paths can be used to estimate the loss rates and latency of all other paths. Through an extensive scalability analysis, we find that for reasonably large N (e.g., 100), the growth of k is bounded to O(N log N). The findings in this work suggest an upper-bound of the monitoring cost for a scalable network monitoring system. Once we set up an upper-bound of the monitoring cost this way, in Part II, we present a framework that provides flexibility to a variety of design requirements and better scalability with the cost of little accuracy decrease. We apply Bayesian experimental design to select active measurements that maximize the amount of information we gain about the network path properties subject to given resource constraints. We then apply network inference techniques to reconstruct the properties of interest based on the partial, indirect observations we get through these measurements. By casting network measurement in a general Bayesian decision theoretic framework, we achieve flexibility. Our framework can support a variety of design requirements, including (i) differentiated design for providing better resolution to certain parts of the network, (ii) augmented design for conducting additional measurements given existing observations, and (iii) joint design for supporting multiple users who are interested in different parts of the network. Our framework is also scalable and can design measurement experiments that span thousands of routers and end hosts. We develop a toolkit that realizes the framework on PlanetLab. We conduct extensive evaluation using both real traces and synthetic data. The results show that the approach can accurately estimate network-wide and individual path properties by monitoring only within 2-10% of paths. We also demonstrate its effectiveness in providing differentiated monitoring, supporting continuous monitoring, and satisfying the requirements of multiple users.en
dc.format.mediumelectronicen
dc.language.isoenen
dc.relation.ispartofUT Electronic Theses and Dissertationsen
dc.rightsCopyright © is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works.en
dc.subjectComputer networksen
dc.subjectWide-area networken
dc.subjectNetwork measurementen
dc.titleScalable and flexible network measurementen
dc.typeThesisen
dc.description.departmentComputer Sciencesen
dc.type.genreThesisen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Sciencesen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Arten
dc.rights.restrictionRestricteden


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record