In this paper we present CAB, a Cost-Aware cloud Backup system, designed for users owning multiple connected devices. Putting client-side monetary cost reduction first, CAB allows users to access their data via multiple devices and applies file updates to the cloud backup with low time delay. We describe some of the optimizations necessary to achieve cost reduction, including data de-duplication, a log-structured data layout, garbage collection, and novel metadata management. Using two one-month long real-world traces, evaluation of a prototype implementation of CAB shows it reduces cost by 16 - 44% compared to a cost-oblivious baseline backup system. Our current prototype implementation stores data in Amazon S3, but is portable to different cloud providers that support REST protocol.

Three stakeholders come into play in peer-to-peer (P2P) video-on-demand (VoD), namely peers/viewers, content providers and ISPs. Different design choices have been proposed to improve quality of user experience, to bring down content server bandwidth cost and to reduce ISP-unfriendly traffic. However, it is unclear whether the ability of these design choices to meet interests of one stakeholder comes at the expense of their ability to satisfy the other stakeholders. Yet, another question remains open for two different types of mesh-based P2P VoD protocols: How well do the regular P2P VoD protocol and the network coding-based P2P VoD protocol perform compared to each other? In this paper, we present a simple performance versus cost framework (PCF) to evaluate impact of different design choices. Via detailed PCF-based simulations, we compare the two P2P VoD protocols and show that the two protocols each has its own territory on which it excels at efficiency. We reveal many important findings about P2P VoD design and hope they are useful to P2P VoD designers.

P2P file sharing networks are rife with unusable copies of files, polluted either incidentally or deliberately. Pollution has made P2P downloading undependable - users may end up receiving polluted copies of a target file. To combat pollution, we propose a recommender that maintains users' opinions on previously downloaded files over their social network and provides recommendations on demand to assist users in making file download decisions. The big challenge for the recommender is to produce right recommendations in face of various potential attacks. To this end, we propose novel techniques in managing user opinions and forming recommendations. Our experimental results show that our recommender greatly outperforms existing download selection strategies in identifying authentic files.

In online content voting networks, aggregate user activities (e.g., submitting and rating content) make high-quality content thrive through the unprecedented scale, high dynamics and divergent quality of user generated content (UGC). To better understand the nature and impact of online content voting networks, we have analyzed Digg, a popular online social news aggregator and rating website. Based on a large amount of data collected, we provide an in-depth study of Digg. We study structural properties of Digg social network, revealing some strikingly distinct properties such as low link symmetry and the power-law distribution of node outdegree with truncated tails. We explore impact of the social network on user digging activities, and investigate the issues of content promotion, content filtering, vote spam and content censorship, which are inherent to content rating networks. We also provide insight into design of content promotion algorithms and recommendation-assisted content discovery. Overall, we believe that the results presented in this paper are crucial in understanding online content rating networks.

One primary goal in P2P networks is to provide high search performance for users to retrieve interested documents distributed over nodes. Document indexing is the key to search performance. However, it is challenging to guarantee high search performance with small document index. In this paper, we present iSearch which aims to build small document index to deliver high search performance on Gnutella-like P2P networks. The number of index terms per document is typically 4, which dramatically reduces associated cost in index storage and dissemination. iSearch explores two options to build index: top term-based indexing (TTI) and query-driven indexing (QDI). TTI bases selection of document index terms on term statistics, while QDI progressively refines document index by past queries. Our simulations show that that TTI and QDI improve search performance over random walk significantly. By dynamically adapting index based on past queries, QDI outperforms TTI greatly, by up to 2× recall improvement.

File replication is a widely used technique for high performance in peer-to-peer file sharing systems. A file replication technique should be efficient and meanwhile facilitates efficient file consistency maintenance. However, most traditional methods don't consider node available capacity and physical location in file replication, leading to high overhead for both file replication and consistency maintenance. This paper presents a proactive low-overhead file replication scheme, namely Plover. By making file replication among physically close nodes based on node available capacities, Plover not only achieves high efficiency in file replication but also supports low-cost and timely consistency maintenance. It also includes an efficient file query redirection algorithm for load balancing between replica nodes. Simulation results demonstrate the effectiveness of Plover in comparison with other file replication schemes. It dramatically reduces the overhead of both file replication and consistency maintenance compared to other schemes. In addition, it yields significant improvements in reduction of overloaded nodes.

Internet-based distributed systems enable globally scattered resources to be collectively pooled and used in a cooperative manner to achieve unprecedented petascale super computing capabilities. Numerous resource discovery approaches have been proposed to help achieve this goal. To report or discover a multi-attribute resource, most approaches use multiple messages with each message for an attribute, leading to high overhead. Anther approach can reduce multi-attribute to one index, but it is not practically effective in an environment with a large number of different resource attributes. Furthermore, few approaches are able to locate resources geographically close to the requesters, which is critical to system performance. This paper presents a P2P-based intelligent resource discovery (PIRD) mechanism that weaves all attributes into a set of indices using locality sensitive hashing, and then maps the indices to a structured P2P. It further incorporates Lempel-Ziv-Welch algorithm to compress attribute information for higher efficiency. In addition, it helps to search resources geographically close to requesters by relying on a hierarchical P2P structure. PIRD significantly reduces overhead and improves the efficiency and effectiveness of resource discovery. Theoretical analysis and simulation results demonstrate the efficiency of PIRD in comparison with other approaches. It dramatically reduces overhead and yields significant improvements on the efficiency of resource discovery.

In this paper, we propose novel techniques to reduce bandwidth cost in a continuous keyword query processing system that is based on a distributed hash table. We argue that query indexing and document announcement are of significant importance towards this goal. Our detailed simulations show that our proposed techniques, combined together, effectively and greatly reduce bandwidth cost.

Peer-to-peer (P2P) networks are becoming increasingly popular and are an exciting new class of innovative, internet-based resource sharing systems. In a P2P network, a reputation system is essential to evaluate the trustworthiness of participating peers and to combat the selfish, dishonest, and malicious peer behaviors. The system collects locally-generated peer feedbacks and aggregates them to yield the global reputation values to represent peer trustworthiness. Reputation system guides peers in choosing a server for services/resources. Most of the approaches for peers to exploit reputation metrics are to select the one with the highest reputation value as a providing server. However, it may lead to unexpectedly low efficiency for high-reputed peers, and prevents P2P networks from taking full advantage of all resources for high performance. Other approaches restrict a peer to select a server in the same or lower reputation values. However, these approaches prevent P2P networks from achieving their goal of widely resource sharing and service exchanges. In this paper, we introduce a trust-based fairness-oriented server selection policy, FairTrust, for a peer to choose another peer to interact. FairTrust takes into account both reputation and capacity factors in server selection. It helps to create a secure P2P communication environment, and meanwhile to take full advantage of system resources for high performance by fair load distribution. Simulation results show the superiority of the FairTrust policy in achieving both high security and high performance in P2P networks in comparison with other related policies.

Publish/subscribe model has become a prevalent paradigm for building distributed event delivering systems. Content-based publish/subscribe allows high expresses in subscriptions and thus is more appropriate for content dissemination. However, the scalability has remained a challenge in the design of distributed content-based publish/subscribe systems due to the expensive matching and delivering cost of content-based events. In this paper we propose HyperSub, an infrastructure built on top of distributed hash table (DHT) for efficient content-based data distribution. Based on efficient subscription installation, event publication and event delivery mechanisms, Hyper- Sub can provide a scalable platform to simultaneously support any numbers of pub/sub schemes with different number of attributes. There are three key features in the design of HyperSub: (1) a locality-preserving hashing mechanism which partitions the content space into content zones. Subscriptions and events are mapped to the content zones for efficiently matching; (2) an efficient event delivery algorithm which exploits the embedded trees in the underlying DHT to deliver events to the corresponding subscribers; (3) light-weighted load balancing mechanisms to adjust the load among peers and ensure that no peer is unduly loaded.

One hurdle to using peer-to-peer networks as anonymizing networks is churn. Node churn makes anonymous paths fragile and short-lived: failures of a relay node disrupt the path, resulting in message loss and communication failures. To make anonymous routing resilient to node failures, we take two steps: (1) we use a simple yet powerful idea based on message redundancy by erasure coding and path redundancy to mask node failures; (2) we base mix choices of a path on node lifetime prediction and choose stable nodes as relay nodes, thereby prolonging single path durability. We present an allocation of erasure-coded message segments among multiple paths that provides a guideline on how to maximize routing resilience upon different node availabilities in real-world systems. Via detailed simulations, we compare routing resilience of our approach and existing anonymity protocols, showing that our approach greatly improves routing resilience while consuming modest bandwidth.

The scalability has remained a challenge in the design of distributed publish/subscribe systems. In this paper we propose a novel solution to address this problem in content-based pub/sub systems on top of distributed hash table. The main objective is to ensure an appropriate amount of rendezvous point nodes in the system, as well as maintain an even load distribution among them. An attribute-vector based publish/subscribe scheme and related load balancing mechanisms (ID space partitioning, attribute grouping, dynamic ID space split-merge) are proposed to achieve this goal. The experimental results show that our approaches can achieve a good scalability by efficiently distribute/balance load among an adaptive quantity of rendezvous point nodes, while retaining very small overhead and latency

We propose Ferry, an architecture that extensively yet wisely exploits the underlying distributed hash table (DHT) overlay structure to build an efficient and scalable platform for content-based publish/subscribe (pub/sub) services. Ferry aims to host any and many content-based pubservices: Any pubsub service with a unique scheme can run on top of Ferry, and multiple pub/sub services can coexist on top of Ferry. For each pub/sub service, Ferry does not need to maintain or dynamically generate any dissemination tree. Instead, it exploits the embedded trees in the underlying DHT to deliver events, thereby imposing little overhead. Ferry can support a pub/sub scheme with a large number of event attributes. To deal with a skewed distribution of subscriptions and events, Ferry uses one-hop subscription push and attribute partitioning to balance load

In this paper, we focus on how neighbor selection impacts DHT overlay structure, static resilience to failures and attacks, and lookup performance under churn. We present a deep comparison study of existing neighbor selection algorithms on the three aspects. We also propose a new neighbor selection policy and a new routing selection algorithm to improve lookup latency under churn. We hope this paper can provide some pieces of insight that will be useful in DHT routing-level designs, including neighbor selection and route selec

The big challenges facing the search techniques on Gnutella-like peer-to-peer networks are search efficiency and quality of search results. In this paper, leveraging information retrieval (IR) algorithms such as Vector Space Model (VSM) and relevance ranking algorithms, we present GES (Gnutella with Efficient Search) to improve search performance. The key idea is that GES uses a distributed topology adaptation algorithm to organize semantically relevant nodes into same semantic groups by using the notion of node vector. Given a query, GES employs an efficient search protocol to direct the query to the most relevant semantic groups for answers, thereby achieving high recall with probing only a small fraction of nodes. To the best of our knowledge, GES is the first to identify node vector size as an important role in impacting search performance and to show that the node vector size offers a good trade-off between search performance and bandwidth cost. Moreover, GES adopts automatic query expansion and local data clustering to improve search performance. We show that GES is efficient and even outperforms the centralized node clustering system SETS. For example, in the scenario where node capacity is heterogeneous, GES can achieve 73 percent recall when probing only 20 percent nodes, outperforming SETS by about 18 percent.

Leveraging DHTs (distributed hash table), we propose Ferry, an architecture for content-based publish/subscribe services. With its novel design in subscription installation, subscription management and event delivery algorithm, Ferry can serve as a scalable platform to host any and many content-based publish/subscribe services: any publish/subscribe service with a unique scheme can run on top of Ferry, and many publish/subscribe services can run together on top of Ferry. For each of the publish/subscribe services running on top of Ferry, Ferry does not need to maintain or dynamically generate any dissemination tree. Instead, it exploits the embedded trees in DHTs such as Chord to deliver events, thereby imposing little overhead. By delivering events along DHT links, Ferry has two main advantages: (1) it eliminates the cost in construction and maintenance of the dissemination trees; (2) it allows further optimization, i.e., the DHT link maintenance messages could be piggybacked onto the event delivery messages to reduce the maintenance cost which is inherent and nontrivial in DHTs. Moreover, Ferry can support a publish/subscribe scheme with a very large number of event attributes.

Most of structured P2P overlays exploit distributed Hash table (DHT) to achieve an administration-free, fault tolerant overlay network and guarantee to deliver a message to the destination within O(log N) hops. While elegant from a theoretical perspective, those systems face difficulties under an open environment. Not only frequently joining and leaving of nodes generate enormous maintenance overhead, but also various behaviors and resources of peers compromise overlay performance and security. Instead of building P2P overlay from the theoretical view, this paper builds the overlay network from the perspective of the physical network. By combining different network topology-aware techniques, a distinctive overlay network that closely matches the Internet topology is constructed. The P2P system based on this structure is not only highly efficient for routing, but also keeps maintenance overhead very low even under highly dynamic environment. Moreover, the system provides a new aspect to solve many security issues.

Many solutions have been proposed to tackle the load balancing issue in DHT-based P2P systems. However, all these solutions either ignore the heterogeneity nature of the system, or reassign loads among nodes without considering proximity relationships, or both. In this paper, we present an efficient, proximity-aware load balancing scheme by using the concept of virtual servers. To the best of our knowledge, this is the first work to use proximity information in load balancing. In particular, our main contributions are: 1) relying on a self-organized, fully distributed k-ary tree structure constructed on top of a DHT, load balance is achieved by aligning those two skews in load distribution and node capacity inherent in P2P systems - that is, have higher capacity nodes carry more loads; 2) proximity information is used to guide virtual server reassignments such that virtual servers are reassigned and transferred between physically close heavily loaded nodes and lightly loaded nodes, thereby minimizing the load movement cost and allowing load balancing to perform efficiently; and 3) our simulations show that our proximity-aware load balancing scheme reduces the load movement cost by 11-65 percent for all the combinations of two representative network topologies, two node capacity profiles, and two load distributions of virtual servers. Moreover, we achieve virtual server reassignments in O(log N) time.

We present TAP, a novel tunneling approach for anonymity in structured P2P systems. An important feature of TAP is that anonymous tunnels are fault-tolerant to node failures. Relying on P2P routing infrastructure and replication mechanism, the basic idea behind TAP is to decouple anonymous tunnels from "fixed" P2P nodes and form anonymous tunnels from dynamic tunnel hop nodes. The primary motivation of TAP is to strike a balance between functionality and anonymity in dynamic P2P networks. We have implemented the tunneling mechanism in Java on FreePastry 1.3. An analysis of its anonymity and performance was evaluated via detailed simulations.

Summary form only given. Many solutions have been proposed to tackle the problem of load balancing in structured P2P systems. However, all these solutions either ignore the heterogeneity nature of the system, or reassign loads among nodes without considering proximity relationships, or both. We propose an efficient scheme to ensure fair load distribution in such P2P systems by utilizing proximity information. To our knowledge, this is the first work to utilize the proximity information to guide load balancing. In particular, our main contributions are: (1) A self-organized, fully distributed K-nary tree structure is constructed on top of a distributed hash table (DHT) for load balancing information collection/dissemination and load reassignment. (2) Load balancing is achieved by aligning those two skews in load distribution and node capacity inhere in P2P systems - that is, have higher capacity nodes carry more loads. (3) Proximity information is utilized to guide load balancing such that loads are assigned and transferred between physically close heavy nodes and light nodes, thereby minimizing the load transferring overhead and allowing load balancing to perform more efficiently.

New demands brought by the continuing growth of the Internet will be met in part by more effective and comprehensive use of caching. We propose to exploit client browser caches in cooperative proxy caching by constructing the client caches within each organization (e.g., corporate networks) as a large peer-to-peer client cache. Via trace-driven simulations we evaluate the potential performance benefit of cooperative proxy caching with/without exploiting client caches. We show that exploiting client caches in cooperative proxy caching can significantly improve performance, particularly when the size of individual proxy caches is limited compared to the universe of Web objects. We further devise a cooperative hierarchical greedy-dual replacement algorithm (Hier-GD), which not only provides some cache coordination but also utilizes client caches. Through Hier-GD, we explore the design issues of how to exploit client caches in cooperative proxy caching to build large Web caches. We show that Hier-GD is technically practical and can potentially improve the performance of cooperative proxy caching by utilizing client caches

Structured peer-to-peer (P2P) systems address the load balancing issue in a rather naive way, by simply resorting to the uniformity of the hash function utilized to generate object IDs. Such a random choice of object IDs could result in O(log N) load imbalance. We propose an efficient, proximity-aware load balancing algorithm for such systems. To our knowledge, this is the first work to utilize the proximity information to guide load balancing. In particular, our main contributions are: (1) A self-organized, fully distributed K-nary tree structure is constructed on top of a DHT for load balancing information collection/dissemination and load reassignment. (2) Load balancing is achieved by aligning those two skews in both load distribution and node capacity inhere in P2P systems - that is, have higher capacity nodes carry more loads. (3) Proximity information is utilized to guide load balancing such that virtual servers are assigned and transferred between physically close heavy nodes and light nodes, thereby minimizing the load transferring overhead and making load balancing fast and efficient.

We present an architecture for a peer-to-peer (P2P) file system which supports semantics-based access. Central to this work is to provide semantic indexing and retrieval capabilities. Our semantic indexing and locating approach is based on distributed hash tables (DHTs) where the indices of semantically close files are clustered to the same peers with high probability (nearly 100%) by the use of locality sensitive hash functions. A query for finding semantically close files can be answered by consulting only a small number of peer nodes which are most responsible for such a query, instead of by query flooding. Our approach only adds index information to peer nodes, thus imposing only a small storage overhead. We constitute an initial step to integrate semantics-based access mechanisms into a P2P file system.

This paper presents a strong security scheme for network-attached storage (NAS) that is based on capability and uses a key distribution scheme to keep network-attached storage from performing key management. Our system uses strong cryptography to protect data from spoofing, tampering, eavesdropping and replay attacks, and it also guarantees that the data stored on the storage is copy-resistant. In spite of this level of security, our system does not impose much performance penalty. Our experimental results shows that, using a relatively inexpensive CPU in the storage device, there are little performance penalty for random disk accesses and about 9-25% performance degradation for large sequential disk accesses (/spl ges/4 KB).

Via detailed file system and disk system simulation, we examine the impact of disk built-in caches on the system performance. Our results indicate that the current trend of using large built-in caches is unnecessary and a waste of money and power for most users. Disk manufacturers could use much smaller built-in caches to reduce the cost as well as power-consumption, without affecting performance.

Web proxy caching servers play a key role in today's Web infrastructure. Previous studies have shown that disk I/O is one of the major performance bottlenecks of proxy servers. Most conventional file systems do not work well for proxy server workloads and have high overheads. This paper presents a novel, User-space, Customized File System, called UCFS, that can drastically improve the I/O performance of proxy servers. UCFS is a user-level software component of a proxy server which manages data on a raw disk or disk partition. Since the entire system runs in the user space, it is easy and inexpensive to implement. It also has good portability and maintainability. UCFS uses efficient in-memory meta-data tables to eliminate almost all I/O overhead of meta-data searches and updates. It also includes a novel file system called Cluster-structured File System (CFS). Similarly to the Log-structured File Systems (LFS), CFS uses large disk transfers to significantly improve disk write performance. However, CFS can also markedly improve file read operations and it does not generate garbage. Comprehensive simulation experiments using five representative real-world traces show that UCFS can significantly improve proxy server performance. For example, UCFS achieves 8-19 times better I/O performance than the state-of-the-art SQUID server running on a Unix Fast File System (FFS), 4-7.5 times better than SQUID on asynchronous FFS, and 3-9 times better than the improved SQUIDML.