2026-09-19T03:32:59Zhttps://api.drum.lib.umd.edu/server/oai/request

oai:drum.lib.umd.edu:1903/132572016-03-29T10:25:15Zcom_1903_2224com_1903_12com_1903_2col_1903_2756col_1903_3

Sussman, Alan Song, Sukhyun Digital Repository at the University of Maryland University of Maryland (College Park, Md.) Computer Science 2012-10-11T06:16:47Z 2012-10-11T06:16:47Z 2012 http://hdl.handle.net/1903/13257 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. DECENTRALIZED NETWORK BANDWIDTH PREDICTION AND NODE SEARCH Dissertation Computer science Network Bandwidth Prediction Node Search Tree Metric Space open.access