Please use this identifier to cite or link to this item:
Type: Thesis
Title: Link loss tomography and topology synthesis.
Author: Bowden, Rhys Alistair
Issue Date: 2015
School/Discipline: School of Mathematical Sciences
Abstract: Accurate and timely performance data are of vital importance for network administration. However, modern networks are so large and transmit such enormous quantities of data that collecting the complete measurements can be wildly impractical. Network tomography uses the measurements that are available to infer underlying performance statistics. In this thesis we consider estimating average packet loss rates on links from more easily collected path measurements. Most such work has concentrated on tree-networks, but here we consider the problem on a general network where the problem is typically underconstrained. In that context we need some criteria to select a solution from the infinite set of possibilities. Here we exploit the compressive sensing assumption of sparsity. However, although the assumption of sparsity makes a great deal of sense in this context, the standard conditions required for results in compressive sensing theorems do not hold for realistic routing matrices. We show that despite this, the underlying techniques can still provide useful answers. What's more, we show that the apparently inconvenient structure of routing matrices can actually help in solving the problem efficiently. We provide CTD, a new algorithm for finding sparsest solutions that is orders of magnitude faster than one of the standard compressive sensing algorithms, and which provides more certainty. We also provide a version of CTD for working with a limited number of measurements, CTDn. The success of a tomography algorithm often depends upon the underlying network topology. To test CTD we use two sources of topologies: the Internet Topology Zoo and synthetically generated topologies. We propose a new method for topology synthesis, Combined Optimisation and Layered Design (COLD), that mirrors the real-life design process of a data network. Since real data networks are designed, they are in some sense optimized to fulfil a function. However, strict mathematical optimisation is rarely performed at the router lever; rather the PoP-level is typically the one being optimized, because it is both more stable and less intricate. Once the PoP-level network is determined, the router-level network can be created using a templated design process, increasing regularity and aiding management and debugging. COLD mirrors this process by having two layers: PoP-level optimisation of realistic economic constraints subject to demand; and then router level synthesis with a templated design process using graph products. We show COLD produces sensible, varied yet controllable output with a clear relationship to the relatively few input parameters. We test CTD and CTDn with both Topology Zoo topologies and COLD-generated topologies. Because the COLD process can be controlled to generate a wide variety of topologies this allowed us to test the sensitivity of CTD and CTDn to the form of the underlying topology. We show that CTD and CTDn perform well across a wide variety of topological structures and forms of measurement, while relying on less detailed information than previous approaches.
Advisor: Roughan, Matthew
Bean, Nigel Geoffrey
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Sciences, 2015
Keywords: network topology; synthesis; network tomography; internet measurement
Provenance: This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at:
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf128.13 kBAdobe PDFView/Open
02whole.pdf2.11 MBAdobe PDFView/Open
PermissionsLibrary staff access only865.81 kBAdobe PDFView/Open
RestrictedLibrary staff access only2.21 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.