DECENTRALIZED NETWORK BANDWIDTH PREDICTION AND NODE SEARCH
| dc.contributor.advisor | Sussman, Alan | en_US |
| dc.contributor.author | Song, Sukhyun | en_US |
| dc.contributor.department | Computer Science | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2012-10-11T06:16:47Z | |
| dc.date.available | 2012-10-11T06:16:47Z | |
| dc.date.issued | 2012 | en_US |
| dc.description.abstract | As modern computing becomes increasingly data-intensive and distributed, it is becoming crucial to effectively manage and exploit end-to-end network bandwidth information from hosts on wide-area networks. Inspired by the finding that Internet bandwidth can be represented approximately in a tree metric space, we focus on three specific research problems. First, we have designed a decentralized algorithm for network bandwidth prediction. The algorithm embeds the bandwidth information as distance in an edge-weighted tree, without performing full n-to-n measurements. No central and fixed infrastructure is required. Each joining node performs a limited number of sampling measurements. Second, we designed a decentralized algorithm to search for a centroid node that has high-bandwidth connections with a given set of nodes. The algorithm can find a centroid accurately and efficiently using the bandwidth data produced by the prediction algorithm. Last, we have designed another type of decentralized search algorithm to find a cluster of nodes that have high-bandwidth interconnections. While the clustering problem is NP-complete in a general graph, our algorithm runs in polynomial time with the bandwidth data predicted in a tree metric space. We provide proofs that our algorithms for bandwidth prediction and node search have perfect accuracy and high scalability when a network is modeled as a tree metric space. Also, experimental results with real-world data sets validate the high accuracy and scalability of our approaches. | en_US |
| dc.identifier.uri | http://hdl.handle.net/1903/13257 | |
| dc.subject.pqcontrolled | Computer science | en_US |
| dc.subject.pquncontrolled | Network Bandwidth Prediction | en_US |
| dc.subject.pquncontrolled | Node Search | en_US |
| dc.subject.pquncontrolled | Tree Metric Space | en_US |
| dc.title | DECENTRALIZED NETWORK BANDWIDTH PREDICTION AND NODE SEARCH | en_US |
| dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1