Persistent Link:
http://hdl.handle.net/10150/301548
Title:
Graph Algorithms for Network Tomography and Fault Tolerance
Author:
Gopalan, Abishek
Issue Date:
2013
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The massive growth and proliferation of media, content, and services on the Internet are driving the need for more network capacity as well as larger networks. With increasing bandwidth and transmission speeds, even small disruptions in service can result in a significant loss of data. Thus, it is becoming increasingly important to monitor networks for their performance and to be able to handle failures effectively. Doing so is beneficial from a network design perspective as well as in being able to provide a richer experience to the users of such networks. Network tomography refers to inference problems in large-scale networks wherein it is of interest to infer individual characteristics, such as link delays, through aggregate measurements, such as end-to-end path delays. In this dissertation, we establish a fundamental theory for a class of network tomography problems in which the link metrics of a network are modeled to be additive. We establish the necessary and sufficient conditions on the network topology, provide polynomial time graph algorithms that quantify the extent of identifiability, and algorithms to identify the unknown link metrics. We develop algorithms for all graph topologies classified on the basis of their connectivity. The solutions developed in this dissertation extend beyond networking and are applicable in areas such as nano-electronics and power systems. We then develop graph algorithms to handle link failures effectively and to provide multipath routing capabilities in IP as well as Ethernet based networks. Our schemes guarantee recovery and are designed to pre-compute alternate next hops that can be taken upon link failures. This allows for fast re-routing as we avoid the need to wait for (control plane) re-computations.
Type:
text; Electronic Dissertation
Keywords:
Computer networking; Fault tolerance; Graph theory; Network tomography; Electrical & Computer Engineering; Algorithms
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Electrical & Computer Engineering
Degree Grantor:
University of Arizona
Advisor:
Ramasubramanian, Srinivasan

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleGraph Algorithms for Network Tomography and Fault Toleranceen_US
dc.creatorGopalan, Abisheken_US
dc.contributor.authorGopalan, Abisheken_US
dc.date.issued2013-
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe massive growth and proliferation of media, content, and services on the Internet are driving the need for more network capacity as well as larger networks. With increasing bandwidth and transmission speeds, even small disruptions in service can result in a significant loss of data. Thus, it is becoming increasingly important to monitor networks for their performance and to be able to handle failures effectively. Doing so is beneficial from a network design perspective as well as in being able to provide a richer experience to the users of such networks. Network tomography refers to inference problems in large-scale networks wherein it is of interest to infer individual characteristics, such as link delays, through aggregate measurements, such as end-to-end path delays. In this dissertation, we establish a fundamental theory for a class of network tomography problems in which the link metrics of a network are modeled to be additive. We establish the necessary and sufficient conditions on the network topology, provide polynomial time graph algorithms that quantify the extent of identifiability, and algorithms to identify the unknown link metrics. We develop algorithms for all graph topologies classified on the basis of their connectivity. The solutions developed in this dissertation extend beyond networking and are applicable in areas such as nano-electronics and power systems. We then develop graph algorithms to handle link failures effectively and to provide multipath routing capabilities in IP as well as Ethernet based networks. Our schemes guarantee recovery and are designed to pre-compute alternate next hops that can be taken upon link failures. This allows for fast re-routing as we avoid the need to wait for (control plane) re-computations.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectComputer networkingen_US
dc.subjectFault toleranceen_US
dc.subjectGraph theoryen_US
dc.subjectNetwork tomographyen_US
dc.subjectElectrical & Computer Engineeringen_US
dc.subjectAlgorithmsen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineElectrical & Computer Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorRamasubramanian, Srinivasanen_US
dc.contributor.committeememberLazos, Loukasen_US
dc.contributor.committeememberBose, Tamalen_US
dc.contributor.committeememberEfrat, Alonen_US
dc.contributor.committeememberRamasubramanian, Srinivasanen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.