Extending snBench to Support a Video-Based Intrusion Detection and Alerting System with a Centralized Hash Table

In this project we design and implement a centralized hashing table in the snBench sensor network environment. We discuss the feasibility of this approach and compare and contrast with the distributed hashing architecture, with particular discussion regarding the conditions under which a centralized architecture makes sense. There are numerous computational tasks that require persistence of data in a sensor network environment. To help motivate the need for data storage in snBench we demonstrate a practical application of the technology whereby a video camera can monitor a room to detect the presence of a person and send an alert to the appropriate authorities.

Simple Load Balancing for Distributed Hash Tables

Distributed hash tables have recently become a useful building block for a variety of distributed applications. However, current schemes based upon consistent hashing require both considerable implementation complexity and substantial storage overhead to achieve desired load balancing goals. We argue in this paper that these goals can b e achieved more simply and more cost-effectively. First, we suggest the direct application of the "power of two choices" paradigm, whereby an item is stored at the less loaded of two (or more) random alternatives. We then consider how associating a small constant number of hash values with a key can naturally b e extended to support other load balancing methods, including load-stealing or load-shedding schemes, as well as providing natural fault-tolerance mechanisms.

Cluster-Based Optimizations for Distributed Hash Tables

We consider the problem of performing topological optimizations of distributed hash tables. Such hash tables include Chord and Tapestry and are a popular building block for distributed applications. Optimizing topologies over one dimensional hash spaces is particularly difficult as the higher dimensionality of the underlying network makes close fits unlikely. Instead, current schemes are limited to heuristically performing local optimizations finding the best of small random set of peers. We propose a new class of topology optimizations based on the existence of clusters of close overlay members within the underlying network. By constructing additional overlays for each cluster, a significant portion of the search procedure can be performed within the local cluster with a corresponding reduction in the search time. Finally, we discuss the effects of these additional overlays on spatial locality and other load balancing scheme.

Realization of Open Addressing Hash Table in the Chained Allocated Memory

In this article, we examine a realization of an open addressing hash table in the chained allocated memory, giving us the opportunity to decrease the number of linear probing when a given element has not been inserted in the table.

DEX: Self-Healing Expanders

We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders - whose expansion properties hold deterministically - that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting, in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only O(log n) rounds and O(log n) messages are needed with high probability (n is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.

DEX: self-healing expanders

A DHT-Based Grid Resource Indexing and Discovery Scheme

This paper presents a DHT-based grid resource indexing and discovery (DGRID) approach. With DGRID, resource-information data is stored on its own administrative domain and each domain, represented by an index server, is virtualized to several nodes (virtual servers) subjected to the number of resource types it has. Then, all nodes are arranged as a structured overlay network or distributed hash table (DHT). Comparing to existing grid resource indexing and discovery schemes, the benefits of DGRID include improving the security of domains, increasing the availability of data, and eliminating stale data.

Reducing the bandwidth requirements of P2P keyword indexing

This paper describes the design and evaluation of a federated, peer-to-peer indexing system, which can be used to integrate the resources of local systems into a globally addressable index using a distributed hash table. The salient feature of the indexing systems design is the efficient dissemination of term-document indices using a combination of duplicate elimination, leaf set forwarding and conventional techniques such as aggressive index pruning, index compression, and batching. Together these indexing strategies help to reduce the number of RPC operations required to locate the nodes responsible for a section of the index, as well as the bandwidth utilization and the latency of the indexing service. Using empirical observation we evaluate the performance benefits of these cumulative optimizations and show that these design trade-offs can significantly improve indexing performance when using a distributed hash table.

Reducing cache lookup and publish overhead through locality awareness in P2P web caching

Peer-to-Peer (P2P) Web caching has been a hot research topic in recent years as it can create scalable and robust designs for decentralized Internet-scale applications. However, many P2P Web caching systems suffer expensive overheads such as lookup and publish messages, and lack of locality awareness. In this paper we present the development of a locality aware P2P cache system to overcome these limitations by using routing table locality, aggregation and soft state. The experiments show that our P2P cache system improves the performance of index operations through the reduction of the amount of information processed by nodes, the reduction of the number of index messages sent by nodes, and the improvement of the locality of cache pointers.

Adjacency cache : an efficient P2P web cache indexing and lookup system

This paper describes the design and evaluation of an efficient per-to-peer (P2P) web cache indexing and lookup system, which can be used to integrate the resources of locally available web pages into globally addressable index using a distributed hash table. The salient feature of the indexing system’s design is the efficient dissemination of cache index information using a next-url index which allows cache clients to determine ahead of time whether linked content is also available at a remote cache. In addition, conventional optimizations such as in browser caching and batching of index write requests are also used. These optimizations are evaluated using trace-driven simulation and the results show that these design trade-offs improve cache lookup performance.

Reducing the bandwidth requirements of P2P keyword indexing

This paper describes the design and evaluation of a peer-to-peer indexing system to integrate the resources of local document database systems into a globally addressable index using a distributed hash table. The salient feature of the indexing systems design is the efficient dissemination of term-document indices using a combination of duplicate elimination, ring based forwarding and conventional techniques such as aggressive index pruning, and batching. Together these indexing strategies help to reduce, the number of RPC operations required to locate the nodes responsible for a section of the index, the bandwidth utilization and the latency of the indexing service.

Virtual backbone content routing in wireless ad-hoc network

We developed a new content routing based on the virtual backbone structure, which groups wireless nodes and contents into a virtual architecture. Our approach is scalable, works with local information, and does not rely on address information. The naming system uses flat naming to identify nodes and contents, and organizes these identifiers together. Backbone nodes can be selected automatically or predefined to direct their associated normal nodes in a local area. The normal nodes are guided by the backbone nodes to full fill the searching and routing processes. With a virtual structure, the searching performance can be improved by using the DHT technique.

Experiments using ns2 simulator demonstrate that this virtual backbone routing architecture has the following significances: workable without being aware address in a mobile situation; scalable with the size of network; efficient in terms of the reduced hop counts and short end-to-end delay, and also resistant to the dead-end problem.

A locality aware cache diffusion system

Web caching is a widely deployed technique to reduce the load to web servers and to reduce the latency for web browsers. Peer-to-Peer (P2P) web caching has been a hot research topic in recent years as it can create scalable and robust designs for decentralized internet-scale applications. However, many P2P web caching systems suffer expensive overheads such as lookup and publish messages, and lack locality awareness. In this paper, we present the development of a locality aware cache diffusion system that makes use of routing table locality, aggregation, and soft state to overcome these limitations. The analysis and experiments show that our cache diffusion system reduces the amount of information processed by nodes, reduces the number of index messages sent by nodes, and improves the locality of cache pointers.

Virtual backbone routing structures in wireless ad-hoc networks

In this paper we studied several virtual routing structures (ring, ring-tree, cord, and mesh) which are scalable, independent on addresses, based on local information and partial global information for routing packets. These virtual routing structures are built on the top of the backbone nodes which are selected by considering power, connections, and immobility metrics.Our experimental results on the ns2 simulator and both TelosBand MicaZ sensor nodes tested platform prove that the virtual backbone structures are superior to the existing routing schemes and the different virtual structures fit in with the different physical scenarios.