DECENTRALIZED NETWORK BANDWIDTH PREDICTION AND NODE SEARCH

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.

Department dc:contributor.department

Computer Science

Year dc:date.issued

2012

Author dc:creator

• Song, Sukhyun

Advisor dc:contributor.advisor

• Sussman, Alan

Handle dc:identifier.uri

http://hdl.handle.net/1903/13257

OAI identifier oai:identifier

oai:drum.lib.umd.edu:1903/13257