Show simple item record

dc.contributor.authorRangudu, Venkata Pavan Kumaren
dc.date.accessioned2017-02-09T18:28:26Zen
dc.date.available2017-02-09T18:28:26Zen
dc.date.issued2017-02-09en
dc.identifier.othervt_gsexam:9523en
dc.identifier.urihttp://hdl.handle.net/10919/74983en
dc.description.abstractIn many network applications, such as the Internet and infrastructure networks, nodes fail or get congested dynamically, but tracking this information about all the nodes in a network where some dynamical processes are taking place is a fundamental problem. In this work, we study the problem of inferring the complete set of failed nodes, when only a sample of the node failures are known---we will be referring to this particular problem as prob{} . We consider the setting in which there exists correlations between node failures in networks, which has been studied in the case of many infrastructure networks. We formalize the prob{} problem using the Minimum Description Length (MDL) principle and we show that, in general, finding solutions that minimize the MDL cost is hard, and develop efficient algorithms with rigorous performance guarantees for finding near-optimal MDL cost solutions. We evaluate our methods on both synthetic and real world datasets, which includes the one from WAZE. WAZE is a crowd-sourced road navigation tool, that collects and presents the traffic incident reports. We found that the proposed greedy algorithm for this problem is able to recover $80%$, on average, of the failed nodes in a network for a given partial sample of input failures, which are sampled from the true set of failures at some predefined rate. Furthermore, we have also proved that this algorithm will find a solution that has MDL cost with an additive approximation guarantee of $log(n)$ from the optimal.en
dc.format.mediumETDen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectNetwork Topology Inferenceen
dc.subjectNetwork Tomographyen
dc.subjectMinimum Description Lengthen
dc.titleInferring Network Status from Partial Observationsen
dc.typeThesisen
dc.contributor.departmentComputer Scienceen
dc.description.degreeMaster of Scienceen
thesis.degree.nameMaster of Scienceen
thesis.degree.levelmastersen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.disciplineComputer Science and Applicationsen
dc.contributor.committeechairMarathe, Madhav Vishnuen
dc.contributor.committeememberVullikanti, Anil Kumar S.en
dc.contributor.committeememberBisset, Keith R.en


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record