Browsing by Author "Bhattacharjee, Bobby"
Now showing 1 - 20 of 25
Results Per Page
Sort Options
Item Adaptive Replication in Peer-to-Peer Systems(2003-08-01) Gopalakrishnan, Vijay; Silaghi, Bujor; Bhattacharjee, Bobby; Keleher, PeteRecent 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)Item Analysis of the NICE Application Layer Multicast Protocol(2002-08-01) Banerjee, Suman; Bhattacharjee, BobbyApplication layer multicast protocols organize a set of hosts into an overlay tree for data delivery. Each host on the overlay peers with a subset of other hosts. Since application layer multicast relies only on an underlying unicast architecture, multiple copies of the same packet can be carried by a single physical link or node on the overlay. The stress at a link or node is defined as the number of identical copies of a packet carried by that link or node. Stretch is another important metric in application layer multicast, which measures the relative increase in delay incurred by the overlay path between pairs of members with respect to the direct unicast path. In this paper we study the NICE application layer multicast protocol to quantify and study the tradeoff between these two important metrics --- stress and stretch in scalably building application layer multicast paths. Also UMIACS-TR-2002-60Item The Case for a Multi-hop Wireless Local Area Network(2003-12-18) Lee, Seungjoon; Banerjee, Suman; Bhattacharjee, BobbyWe propose a multi-hop wireless LAN architecture and demonstrate its benefits to wireless clients. For this architecture, we define implementation paths that allow interoperation with existing wireless LANs and therefore lead to an incremental deployment of this system. We quantify the performance benefits of the proposed schemes through measurements in realistic wireless LAN environments. We also examine the performance of such multi-hop wireless LANs through detailed simulation studies. Our results show that such multi-hop extensions can significantly improve the wireless access experience (in terms of data throughput, latency, etc.) for clients who enable such mechanisms. More interestingly, when multi-hop extensions are enabled by some of the clients, it also positively impacts the performance at other clients that are completely unaware of such extensions. UMIACS-TR-2003-73Item The Design of TerraDir(2001-12-17) Bhattacharjee, Bobby; Keleher, Pete; Silaghi, BujorWe present the design and initial evaluation of TerraDir: an approach for implementing customizable, distributed, peer-to-peer directories over which a broad range of wide-area resource discovery applications can be implemented. TerraDir's structure is two-tiered, consisting of a base protocol for providing arbitrary application-layer connectivity, and dynamic view materializations that efficiently realize different user-specified views of application-layer resources. TerraDir is specifically designed for data that can be arranged in a rooted hierarchy, and provides very efficient and robust lookups over such data while still being able to allow efficient searching. (Also referenced as UMIACS-TR-2001-4299)Item Efficient Geographic Routing in Multihop Wireless Networks(2006-01-13T21:40:55Z) Lee, Seungjoon; Bhattacharjee, Bobby; Banerjee, SumanWe 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.Item Efficient Lookup on Unstructured Topologies(2006-03-02T17:22:28Z) Morselli, Ruggero; Bhattacharjee, Bobby; Marsh, Michael A.; Srinivasan, AravindWe 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.Item Efficient Peer-to-Peer Namespace Searches(2004-04-19) Gopalakrishnan, Vijay; Bhattacharjee, Bobby; Chawathe, Sudarshan; Keleher, PeteIn 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)Item Intradomain Overlays: Architecture and Applications(2003-08-01) Kommareddy, Christopher; Guven, Tuna; Bhattacharjee, Bobby; La, Richard; Shayman, MarkWe introduce an architecture for ``Intradomain Overlays'', where a subset of routers within a domain is augmented with a dedicated host. These strategically placed hosts form an overlay network, and we describe a number of applications for such overlays. These applications include efficient network monitoring, policy- and load-based packet re-routing, and network resource accounting. In this paper, we elaborate on the network monitoring application and describe a distributed protocol for monitoring routers within an AS which has been augmented with a few overlay nodes. The routers and other infrastructure are unaware of the overlay nodes, and the monitoring of individual elements is conducted using plain SNMP. We describe techniques for efficiently synthesizing and transporting the monitored SNMP data, and present results using trace data collected from an AS with 400+ routers. Our results show that the overlay-based monitoring reduces overheads by 2--4 orders of magnitude, and thus enables much finer grained monitoring and traffic engineering than is otherwise possible. (UMIACS-TR-2003-70)Item 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.Item Matching Jobs to Resources in Distributed Desktop Grid Environments(2006-04) Kim, Jik-Soo; Bhattacharjee, Bobby; Keleher, Peter J.; Sussman, AlanDesktop 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.Item Measurement Based Optimal Multi-path Routing(2003-08-01) Guven, Tuna; Kommareddy, Chris; La, Richard J.; Shayman, Mark A.; Bhattacharjee, BobbyWe propose a new architecture for efficient network monitoring and measurements in a traditional IP network. This new architecture enables establishment of multiple paths (tunnels) between source-destination pairs without having to modify the underlying routing protocol(s). Based on the proposed architecture we propose a measurement-based multi-path routing algorithm derived from simultaneous perturbation stochastic approximation. The proposed algorithm does not assume that the gradient of analytical cost function is known to the algorithm, but rather relies on noisy estimates from measurements. Using the analytical model presented in the paper we prove the convergence of the algorithm to the optimal solution. (UMIACS-TR-2003-69)Item Misbehaving TCP Receivers Can Cause Internet-Wide Congestion Collapse(2005-11-15T19:10:55Z) Sherwood, Rob; Bhattacharjee, Bobby; Braud, RyanAn "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.Item Multi-dimensional Quorum Sets for Read-Few Write-Many Replica Control Protocols(2003-02-27) Silaghi, Bujor; Keleher, Pete; Bhattacharjee, Bobbye describe d-spaces, a replica control protocol defined in terms of quorum sets on multidimensional logical structures. Our study is performed in the context of transactional replica control protocols that support the strongest form of replica consistency guarantees, one-copy serializability. This work is primarily motivated by asymmetrical access patterns, where the number of read accesses to data are dominant relative to update accesses, i.e. where the consistency protocols should be read-few write-many. We show that quorums on d-spaces are optimal with respect to quorum group sizes (message complexity). We present a detailed availability analysis for read and write operations. For highly asymmetrical access patterns, our approach approximates the read-one write-all protocol with respect to read efficiency, while maintaining configurable levels of availability for write operations. Specifically, we show that implementing a read-few write-many replica protocol using $d$-spaces yields both superior operation availability, as well as message complexity, to the hierarchical quorum consensus method. UMIACS-TR-2003-10Item A Protocol for Scalable Application Layer Multicast(2001-09-05) Banerjee, Suman; Bhattacharjee, Bobby; Parthasarathy, SrinivasanWe describe a new application-layer multicast protocol that is specifically designed to scale to large groups. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers and can be used to produce a number of different data delivery trees with specific properties. On average, group members using our protocol maintain only a constant amount of state about other group members, and incur a constant amount of control overhead. We present extensive simulations of both our protocol and the Narada protocol over Internet-like topologies. Our results show that for groups of size 32 or more, we reduce control overhead by orders of magnitude, and link stress by 25%, while retaining similar end-to-end latencies and failure recovery properties.Item Ranking Search Results in Peer-to-Peer Systems(2006-01) Gopalakrishnan, Vijay; Morselli, Ruggero; Bhattacharjee, Bobby; Keleher, Peter; Srinivasan, AravindP2P 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.Item Robust Routing with Unknown Traffic Matrices(2006) Tabatabaee, Vahid; Kashyap, Abhishek; Bhattacharjee, Bobby; La, Richard J.; Shayman, Mark; Shayman, Mark; ISRItem Scalable Application Layer Multicast(2002-08-01) Banerjee, Suman; Bhattacharjee, Bobby; Kommareddy, ChristopherWe describe a new scalable application-layer multicast protocol, specifically designed for low-bandwidth data streaming applications with large receiver sets. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers and can support a number of different data delivery trees with desirable properties. We present extensive simulations of both our protocol and the Narada application-layer multicast protocol over Internet-like topologies. Our results show that for groups of size 32 or more, our protocol has lower link stress (by about 25%), improved or similar end-to-end latencies and similar failure recovery properties. More importantly, it is able to achieve these results by using orders of magnitude lower control traffic. Finally, we present results from our wide-area testbed in which we experimented with 32-100 member groups distributed over 8 different sites. In our experiments, average group members established and maintained low-latency paths and incurred a maximum packet loss rate of less than 1% as members randomly joined and left the multicast group. The average control overhead during our experiments was less than 1 Kbps for groups of size 100. Also UMIACS-TR-2002-53Item Scalable Resilient Media Streaming(2003-06-04) Banerjee, Suman; Braud, Ryan; Lee, Seungjoon; Bhattacharjee, Bobby; Srinivasan, AravindWe present a low-overhead media streaming system, called SRMS (Scalable Resilient Media Streaming) that can be used to scalably deliver streaming data to a large group of receivers. SRMS uses overlay multicast for data distribution to a large group of users. SRMS leverages a probabilistic loss recovery technique to provide high data delivery guarantees even under large network losses and overlay node failures. Through detailed analysis in this paper, we show that this loss recovery technique (and consequently SRMS) has efficient scaling properties --- the overheads at each overlay node asymptotically decrease to zero with increasing group sizes. We also present a detailed description of the SRMS architecture. The clients in the SRMS system are able to interoperate with existing media streaming servers that use RTP for data transport. One of the interesting features of SRMS is that it can simultaneously support clients with disparate access bandwidths. It enables the necessary bandwidth adaptations using standard Real-time Transport Protocol (RTP) mechanisms, e.g. RTP translators. We have implemented and evaluated the SRMS system in detail on an emulated network as well as on a wide-area testbed with up to 128 clients. Our results show that clients using SRMS achieve high (> 97%) data delivery ratios with low overheads (< 5%) even for very high failure rates (upto five per minute). (UMIACS-TR-2003-51)Item Scalable Secure Group Communication over IP Multicast(2001-05-16) Banerjee, Suman; Bhattacharjee, BobbyWe introduce and analyze a scalable re-keying scheme for implementing secure group communications IP multicast. We show that our scheme incurs constant processing, message, and storage overhead for a re-key operation when a single member joins or leaves the group, and logarithmic overhead for bulk simultaneous changes to the group membership. These bounds hold even when group dynamics are not known a-priori. Our re-keying algorithm requires a particular clustering of the members of the secure multicast group. We describe a protocol to achieve such clustering and show that it is feasible to efficiently cluster members over realistic Internet-like topologies. We evaluate the overhead of our own re-keying scheme and also of previously published schemes via simulation over an Internet topology map containing over 280,000 routers. Through analysis and detailed simulations, we show that this re-keying scheme performs better than previous schemes for a single change to group membership. Further, for bulk changes, our algorithm outperforms all previously known schemes by several orders of magnitude in terms of actual bandwidth usage, processing costs and storage requirements.Item A Secure DHT via the Pigeonhole Principle(2007-09-24) Baden, Randy; Bender, Adam; Levin, Dave; Sherwood, Rob; Spring, Neil; Bhattacharjee, BobbyThe 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.