Tech Reports in Computer Science and Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/5

The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu

Browse

Search Results

Now showing 1 - 10 of 23

A Secure DHT via the Pigeonhole Principle
(2007-09-24) Baden, Randy; Bender, Adam; Levin, Dave; Sherwood, Rob; Spring, Neil; Bhattacharjee, Bobby
The standard Byzantine attack model assumes no more than some fixed fraction of the participants are faulty. This assumption does not accurately apply to peer-to-peer settings, where Sybil attacks and botnets are realistic threats. We propose an attack model that permits an arbitrary number of malicious nodes under the assumption that each node can be classified based on some of its attributes, such as autonomous system number or operating system, and that the number of classes with malicious nodes is bounded (e.g., an attacker may exploit at most a few operating systems at a time). In this model, we present a secure DHT, evilTwin, which replaces a single, large DHT with sufficiently many smaller instances such that it is impossible for an adversary to corrupt every instance. Our system ensures high availability and low-latency lookups, is easy to implement, does not require a complex Byzantine agreement protocol, and its proof of security is a straightforward application of the pigeonhole principle. The cost of security comes in the form of increased storage and bandwidth overhead; we show how to reduce these costs by replicating data and adaptively querying participants who historically perform well. We use implementation and simulation to show that evilTwin imposes a relatively small additional cost compared to conventional DHTs.
Using Content-Addressable Networks for Load Balancing in Desktop Grids
(2007-03-29) Kim, Jik-Soo; Keleher, Peter; Marsh, Michael; Bhattacharjee, Bobby; Sussman, Alan
Desktop grids combine Peer-to-Peer and Grid computing techniques to improve the robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.
Ranking Search Results in Peer-to-Peer Systems
(2006-01) Gopalakrishnan, Vijay; Morselli, Ruggero; Bhattacharjee, Bobby; Keleher, Peter; Srinivasan, Aravind
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well-known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to a centralized implementation.
Matching Jobs to Resources in Distributed Desktop Grid Environments
(2006-04) Kim, Jik-Soo; Bhattacharjee, Bobby; Keleher, Peter J.; Sussman, Alan
Desktop grids use opportunistic sharing to exploit large collections of personal computers and workstations across the Internet and can achieve tremendous computing power with low cost. However, current systems are typically based on a traditional client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. In this paper, we propose a decentralized, robust, highly available, and scalable infrastructure to match incoming jobs to available resources. The key idea behind our proposed system is to leverage information provided by an underlying peer-to-peer system to create a hierarchical Rendezvous Node Tree, which performs the matching efficiently. Our experimental results obtained via simulation show that we can effectively match jobs with varying levels of resource constraints to available nodes and maintain good load balance in a fully decentralized heterogeneous computational environment.
KeyChains: A Decentralized Public-Key Infrastructure
(2006-03-02T18:59:57Z) Morselli, Ruggero; Bhattacharjee, Bobby; Katz, Jonathan; Marsh, Michael A.
A Certification Authority (CA) can be used to certify keys and build a public-key infrastructure (PKI) when all users trust the same CA. A decentralized PKI trades off absolute assurance on keys for independence from central control and improved scalability and robustness. The PGP ``web of trust'' model has been suggested as a decentralized certification system, and has been used with great success for secure email. Although the PGP web of trust model allows anyone to issue certificates which can be used to form certificate chains, the discovery and construction of certificate chains relies on centralized keyservers to store certificates and respond to queries. In this paper, we design and implement KeyChains, a peer-to-peer system which incorporates a novel lookup mechanism specifically tailored to the task of generating and retrieving certificate chains in completely unstructured networks. By layering our system on top of the web of trust model, we thus obtain the first PKI which is truly decentralized in all respects. Our analysis and simulations show that the resulting system is both efficient and secure.
Efficient Lookup on Unstructured Topologies
(2006-03-02T17:22:28Z) Morselli, Ruggero; Bhattacharjee, Bobby; Marsh, Michael A.; Srinivasan, Aravind
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT). We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.
Efficient Geographic Routing in Multihop Wireless Networks
(2006-01-13T21:40:55Z) Lee, Seungjoon; Bhattacharjee, Bobby; Banerjee, Suman
We propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic routing, NADV provides an adaptive and efficient cost-aware routing strategy. Depending on the objective or message priority, applications can use the NADV framework to minimize various types of link cost. In this paper we present efficient methods for link cost estimation and perform detailed simulations in diverse scenarios. Our results show that NADV outperforms current schemes in many aspects: for example, in high noise environments with frequent packet losses, the use of NADV leads to 83% higher delivery ratio. When compared to centralized routing, geographic routing using NADV finds paths whose cost is close to the optimum.
Misbehaving TCP Receivers Can Cause Internet-Wide Congestion Collapse
(2005-11-15T19:10:55Z) Sherwood, Rob; Bhattacharjee, Bobby; Braud, Ryan
An "optimistic" acknowledgment (OptAck) is an acknowledgment sent by a misbehaving client for a data segment that it has not received. Whereas previous work has focused on OptAck as a means to greedily improve end-to-end performance, we study OptAck exclusively as a denial of service attack. Specifically, an attacker sends optimistic acknowledgments to many victims in parallel, thereby amplifying its effective bandwidth by a factor of 30 million (worst case). Thus, even a relatively modest attacker can totally saturate the paths from many victims back to the attacker. Worse, a distributed network of compromised machines (``zombies'') can exploit this attack in parallel to bring about wide-spread, sustained congestion collapse. We implement this attack both in simulation and in a wide-area network, and show it severity both in terms of number of packets and total traffic generated. We engineer and implement a novel solution that does not require client or network modifications allowing for practical deployment. Additionally, we demonstrate the solution's efficiency on a real network.
Efficient Peer-to-Peer Namespace Searches
(2004-04-19) Gopalakrishnan, Vijay; Bhattacharjee, Bobby; Chawathe, Sudarshan; Keleher, Pete
In this paper we describe new methods for efficient and exact search (keyword and full-text) in distributed namespaces. Our methods can be used in conjunction with existing distributed lookup schemes, such as Distributed Hash Tables, and distributed directories. We describe how indexes for implementing distributed searches can be efficiently created, located, and stored. We describe techniques for creating approximate indexes that can be used to bound the space requirement at individual hosts; such techniques are particularly useful for full-text searches that may require a very large number of individual indexes to be created and maintained. Our methods use a new distributed data structure called the view tree. View trees can be used to efficiently cache and locate results from prior queries. We describe how view trees are created, and maintained. We present experimental results, using large namespaces and realistic data, showing that the techniques introduced in this paper can reduce search overheads (both network and processing costs) by more than an order of magnitude. (UMIACS-TR-2004-13)
Adaptive Replication in Peer-to-Peer Systems
(2003-08-01) Gopalakrishnan, Vijay; Silaghi, Bujor; Bhattacharjee, Bobby; Keleher, Pete
Recent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data items is relatively uniform. We describe a lightweight, adaptive, and system-neutral replication protocol, LAR, that delivers low latencies and good load balance even when demand is heavily skewed. Simulation of LAR in combination with both the Chord and TerraDir systems shows that LAR quickly adapts to non-uniformity in both the underlying system topology and in the input stream. Further, we demonstrate better performance than functionally similar application-layer protocols, using an order of magnitude less network bandwidth. (UMIACS-TR-2003-83)

Tech Reports in Computer Science and Engineering

Browse

Filters

Settings

Sort By

Results per page

Search Results