In data-intensive parallel computing clusters, it is important to provide deadline-guaranteed service to jobs while minimizing resource usage (e.g., network bandwidth and energy). Under the current computing framework (that first allocates data and then schedules jobs), in a busy cluster with many jobs, it is difficult to achieve high data locality (hence low bandwidth consumption), deadline guarantee, and high energy savings simultaneously. We model the problem to simultaneously achieve these three objectives using integer programming. Due to the NP-hardness of the problem, we propose a heuristic Cooperative job Scheduling and data Allocation method (CSA).CSAnovelly reverses the order of data allocation and job scheduling in the current computing framework. Job-scheduling-first enablesCSAto proactively consolidate tasks with more common requested data to the same server when conducting deadline-aware scheduling, and also consolidate the tasks to as few servers as possible to maximize energy savings. This facilitates the subsequent data allocation step to allocate a data block to the server that hosts most of this data's requester tasks, thus maximally enhancing data locality. To achieve the tradeoff between data locality and energy savings with specified weights,CSAhas a cooperative recursive refinement process that recursively adjusts the job schedule and data allocation schedule. We further propose two enhancement algorithms (i.e., minimum k-cut data reallocation algorithm and bipartite based task reassignment algorithm) to further improve the performance ofCSAthrough additional data reallocation and task reassignment, respectively. Trace-driven experiments in the simulation and the real cluster show thatCSAoutperforms other schedulers in supplying deadline-guarantee and resource-efficient services and the effectiveness of each enhancement. Also, the enhancement algorithms are effective in improvingCSA.

So far, there is no file replication method that tries to reduce data loss in correlated node failures, which however are common in Disruption Tolerant Networks (DTNs). In this paper, we propose a distributed file replication method (called MobileCopy) in DTNs, which aims to achieve low probability of totally losing a file at the expense of having a high number of impacted files in an individual large-scale correlated node failure. MobileCopy is designed for community-based file sharing systems. It has two main components: i) data loss resistant and popularity aware file replication, and ii) distributed hash table (DHT)-based file replica indexing. MobileCopy considers file popularity to determine the number of replicas of a file in each community. Through limiting the possible combination of candidate replica holders, MobileCopy greatly reduces the probability of node failures that will lead to data loss, i.e., losing all replicas of a file. Moreover, MobileCopy enables nodes to efficiently store and fetch the placement information of file replicas through competition based file replication and considering node mobility throughput among communities. Extensive trace-driven experiments demonstrate the effectiveness of MobileCopy against correlated node failures compared with previous methods.

More and more organizations move their data and workload to commercial cloud storage systems. However, the multiplexing and sharing of the resources in a cloud storage system present unpredictable data access latency to tenants, which may make online data-intensive applications unable to satisfy their deadline requirements. Thus, it is important for cloud storage systems to provide deadline guaranteed services. In this paper, to meet a current form of service level objective (SLO) that constrains the percentage of each tenant's data access requests failing to meet its required deadline below a given threshold, we build a mathematical model to derive the upper bound of acceptable request arrival rate on each server. We then propose a Deadline Guaranteed storage service (called DGCloud) that incorporates three basic algorithms. Its deadline-aware load balancing scheme redirects requests and creates replicas to release the excess load of each server beyond the derived upper bound. Its workload consolidation algorithm tries to maximally reduce servers while still satisfying the SLO to maximize the resource utilization. Its data placement optimization algorithm re-schedules the data placement to minimize the transmission cost of data replication. We further propose three enhancement methods to further improve the performance of DGCloud. A dynamic load balancing method allows an overloaded server to quickly offload its excess workload. A data request queue improvement method sets different priorities to the data responses in a server's queue so that more requests can satisfy the SLO requirement. A wakeup server selection method selects a sleeping server that stores more popular data to wake up, which allows it to handle more data requests. Our trace-driven experiments in simulation and Amazon EC2 show the superior performance of DGCloud compared with previous methods in terms of deadline guarantees and system resource utilization, and the effectiveness of its individual algorithms.

In data-intensive parallel computing clusters, it is important to provide deadline-guaranteed service to jobs while minimizing resource usage (e.g., network bandwidth and energy). Under the current computing framework (that first allocates data and then schedules jobs), in a busy cluster with many jobs, it is difficult to achieve these objectives simultaneously. We model the problem to simultaneously achieve the objectives using integer programming, and propose a heuristic Cooperative job Scheduling and data Allocation method (CSA). CSA novelly reverses the order of data allocation and job scheduling in the current computing framework, i.e., changing data-first-job-second to job-first-data-second. It enables CSA to proactively consolidate tasks with more common requested data to the same server when conducting deadline-aware scheduling, and also consolidate the tasks to as few servers as possible to maximize energy savings. This facilitates the subsequent data allocation step to allocate a data block to the server that hosts most of this data's requester tasks, thus maximally enhancing data locality and reduce bandwidth consumption. CSA also has a recursive schedule refinement process to adjust the job and data allocation schedules to improve system performance regarding the three objectives and achieve the tradeoff between data locality and energy savings with specified weights. We implemented CSA and a number of previous job schedulers on Apache Hadoop on a real supercomputing cluster. Trace-driven experiments in the simulation and the real cluster show that CSA outperforms other schedulers in supplying deadline-guarantee and resource-efficient services.

In Web applications served by datacenter nowadays, the incast congestion at the front-end server seriously degrades the data request latency performance due to the vast data transmissions from a large number data servers for a data request in a short time. Previous incast congestion control methods usually consider the direct data transmissions from data servers to the front-end server, which makes it difficult to control the sending speed or adjust workloads due to the transient transmission of only a few data objects from each data server. In this paper, we propose a Swarm-based Incast Congestion Control (SICC) system. SICC forms all target data servers of one request in the same rack into a swarm. In each swarm, a data server (called hub) is selected to forward all data objects to the front-end server, so that the number of data servers concurrently connected to the front-end server is reduced, which avoids the incast congestion. Also, the continuous data transmission from hubs to the front-end server facilitates the development of other strategies to further control the incast congestion. To fully utilize the bandwidth, SICC uses a two-level data transmission speed control method to adjust the data transmission speeds of hubs. A query redirection method further reduces the request latency by balancing the transmission remaining times between hubs. Our experiments in simulation and on a real cluster demonstrate that SICC outperforms other incast control methods in improving throughput and reducing the data request latency.

Question and Answer (Q&A) systems play a vital role in our daily life for information and knowledge sharing. Users post questions and pick questions to answer in the system. Due to the rapidly growing user population and the number of questions, it is unlikely for a user to stumble upon a question by chance that (s)he can answer. Also, altruism does not encourage all users to provide answers, not to mention high quality answers with a short answer wait time. The primary objective of this paper is to improve the performance of Q&A systems by actively forwarding questions to users who are capable and willing to answer the questions. To this end, we have designed and implemented SocialQ&A, an online social network based Q&A system. SocialQ&A leverages the social network properties of common-interest and mutual-trust friend relationship to identify an asker through friendship who are most likely to answer the question, and enhance the user security. We also improve SocialQ&A with security and efficiency enhancements by protecting user privacy and identifies, and retrieving answers automatically for recurrent questions. We describe the architecture and algorithms, and conducted comprehensive large-scale simulation to evaluate SocialQ&A in comparison with other methods. Our results suggest that social networks can be leveraged to improve the answer quality and asker's waiting time. We also implemented a real prototype of SocialQ&A, and analyze the Q&A behavior of real users and questions from a small-scale real-world SocialQ&A system.

Many cloud service providers (CSPs) provide data storage services with datacenters distributed worldwide. These datacenters provide different get/put latencies and unit prices for resource utilization and reservation. Thus, when selecting different CSPs' datacenters, cloud customers of globally distributed applications (e.g., online social networks) face two challenges: 1) how to allocate data to worldwide datacenters to satisfy application service level objective (SLO) requirements, including both data retrieval latency and availability and2) how to allocate data and reserve resources in datacenters belonging to different CSPs to minimize the payment cost. To handle these challenges, we first model the cost minimization problem under SLO constraints using the integer programming. Due to its NP-hardness, we then introduce our heuristic solution, including a dominant-cost-based data allocation algorithm and an optimal resource reservation algorithm. We further propose three enhancement methods to reduce the payment cost and service latency: 1) coefficient-based data reallocation; 2) multicast-based data transferring; and 3) request redirection-based congestion control. We finally introduce an infrastructure to enable the conduction of the algorithms. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage, and Google Cloud Storage) show the effectiveness of our algorithms for SLO guaranteed services and customer cost minimization.

Traditional web-based Question and Answer (Q&A) websites cannot easily solve non-factual questions to match askers' preference. Recent research efforts begin to study social-based Q&A systems that rely on an asker's social friends to provide answers. However, this method cannot find answerers for a question not belonging to the asker's interests. To solve this problem, we propose a distributed Q&A system incorporating both social community intelligence and global collective intelligence, named as iASK. iASK improves the response latency and answer quality in both the social domain and global domain. It uses a neural network based friend ranking method to identify answerer candidates by considering social closeness and Q&A activities. To efficiently identify answerers in the global user base, iASK builds a virtual server tree that embeds the hierarchical structure of interests, and also maps users to the tree based on user interests. To accurately locate the cooperative experts, iASK has a fine-grained reputation system to evaluate user reputation based on their cooperativeness and expertise, and uses a reputation based reward strategy to encourage users to be cooperative. To further improve the performance of iASK, we propose a weak tie assisted social based potential answerer location algorithm and an interest coefficient based uncategorized question forwarding algorithm. To further improve the response quality and cooperativeness, we propose a reputation based reward strategy that motivates users to answer questions from unknown users. Experimental results from large-scale trace-driven simulation and real-world daily usages of the iASK prototype show the superior performance of iASK. It achieves high answer quality with 24 percent higher accuracy, short response latency with 53 percent less delay and effective cooperative incentives with 16 percent more answers compared to other social-based Q&A systems. The results also show the effectiveness of the enhancement algorithms in improving the performance of iASK.

In large-scale computing clusters, when the server storing a task's requested data does not have sufficient computing capacity for the task, current job schedulers either schedule the task to the closest server and transmit to it the requested data, or let the task wait until the server has sufficient computing capacity. The former solution generates network load while the latter solution increases task delay. To handle this problem, load balancing methods are needed to reduce the number of overloaded servers due to computing workloads. However, current load balancing methods do not aim to balance the computing load for the long term. Through trace analysis, we demonstrate the diversity of computing workloads of different tasks and the necessity of balancing the computing workloads among servers. Then, we propose a cost-efficient Computing load Aware and Long-View load balancing approach (CALV). CALVis novel in that it achieves long-term computing load balance by migrating out an overloaded server data blocks contributing more computing workloads when the server is more overloaded and contribute less computing workloads when the server is more underloaded at different epochs during a time period. Based upon the task schedules, we further propose a task reassignment algorithm that reassigns tasks from an overloaded server to other data servers of the tasks to make it non-overloaded before CALVis conducted. The above methods are for the tasks whose submission times and execution latencies can be predicted. To handle unexpected tasks or insufficiently accurate predictions, we propose a dynamic load balancing method, in which an overloaded server dynamically redirects tasks to other data servers of the tasks, or replicates the tasks' requested data to other servers and redirects the tasks to those servers in order to become non-overloaded. Finally, we propose a proximity-aware tree based distributed load balancing method to reduce the reallocation cost and improve the scalability of CALV. Trace-driven experiments in simulation and a real computing cluster show that CALV outperforms other methods in terms of balancing the computing workloads and cost efficiency.

It is important for cloud service brokers to provide a multi-cloud storage service to minimize their payment cost to cloud service providers (CSPs) while providing service level objective (SLO) guarantee to their customers. Many multi-cloud storage services have been proposed or payment cost minimization or SLO guarantee. However, no previous works fully leverage the current cloud pricing policies (such as resource reservation pricing) to reduce the payment cost. Also, few works achieve both cost minimization and SLO guarantee. In this paper, we propose a multi-cloud Economical and SLO-guaranteed Storage Service (ES3), which determines data allocation and resource reservation schedules with payment cost minimization and SLO guarantee. ES3 incorporates (1) a coordinated data allocation and resource reservation method, which allocates each data item to a datacenter and determines the resource reservation amount on datacenters by leveraging all the pricing policies; (2) a genetic algorithm based data allocation adjustment method, which reduce data Get/Put rate variance in each datacenter to maximize the reservation benefit. We also propose several algorithms to enhance the cost efficient and SLO guarantee performance of ES3including i) dynamic request redirection, ii) grouped Gets for cost reduction, iii) lazy update for cost-efficient Puts, and iv) concurrent requests for rigid Get SLO guarantee. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage and Google Cloud Storage) show the superior performance of ES3in payment cost minimization and SLO guarantee in comparison with previous methods.

More and more organizations move their data and workload to commercial cloud storage systems. However, the multiplexing and sharing of the resources in a cloud storage system present unpredictable data access latency to tenants, which may make online data-intensive applications unable to satisfy their deadline requirements. Thus, it is important for cloud storage systems to provide deadline guaranteed services. In this paper, to meet a current form of service level objective (SLO) that constrains the percentage of each tenant's data access requests failing to meet its required deadline below a given threshold, we build a mathematical model to derive the upper bound of acceptable request arrival rate on each server. We then propose a Deadline Guaranteed storage service (called DGCloud) that incorporates three algorithms. Its deadline-aware load balancing scheme redirects requests and creates replicas to release the excess load of each server beyond the derived upper bound. Its workload consolidation algorithm tries to maximally reduce servers while still satisfying the SLO to maximize the resource utilization. Its data placement optimization algorithm re-schedules the data placement to minimize the transmission cost of data replication. Our trace-driven experiments in simulation and Amazon EC2 show the higher performance of DGCloud compared with previous methods in terms of deadline guarantees and system resource utilization, and the effectiveness of its individual algorithms.

Many Cloud Service Providers (CSPs) provide data storage services with datacenters distributed worldwide. These datacenters provide different Get/Put latencies and unit prices for resource utilization and reservation. Thus, when selecting different CSPs' datacenters, cloud customers of globally distributed applications (e.g., online social networks) face two challenges: (i) how to allocate data to worldwide datacenters to satisfy application SLO (service level objective) requirements including both data retrieval latency and availability, and (ii) how to allocate data and reserve resources in datacenters belonging to different CSPs to minimize the payment cost. To handle these challenges, we first model the cost minimization problem under SLO constraints using integer programming. Due to its NP-hardness, we then introduce our heuristic solution, including a dominant-cost based data allocation algorithm and an optimal resource reservation algorithm. We finally introduce an infrastructure to enable the conduction of the algorithms. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage and Google Cloud Storage) show the effectiveness of our algorithms for SLO guaranteed services and customer cost minimization.

It is important for cloud service brokers to provide a multi-cloud storage service to minimize their payment cost to cloud service providers (CSPs) while providing service level objective (SLO) guarantee to their customers. Many multi-cloud storage services have been proposed or payment cost minimization or SLO guarantee. However, no previous works fully leverage the current cloud pricing policies (such as resource reservation pricing) to reduce the payment cost. Also, few works achieve both cost minimization and SLO guarantee. In this paper, we propose a multi-cloud Economical and SLO-guaranteed Storage Service (ES3), which determines data allocation and resource reservation schedules with payment cost minimization and SLO guarantee. ES3 incorporates (1) a coordinated data allocation and resource reservation method, which allocates each data item to a datacenter and determines the resource reservation amount on datacenters by leveraging all the pricing policies; (2) a genetic algorithm based data allocation adjustment method, which reduce data Get/Put rate variance in each datacenter to maximize the reservation benefit; and (3) a dynamic request redirection method, which dynamically redirects a data request from a reservation-overutilized datacenter to a reservation-underutilized datacenter to further reduce the payment. Our trace-driven experiments on a supercomputing cluster and on real clouds (i.e., Amazon S3, Windows Azure Storage and Google Cloud Storage) show the superior performance of ES3 in payment cost minimization and SLO guarantee in comparison with previous methods.

Though the new OSN model, which deploys datacenters globally, helps reduce service latency, it causes higher inter-datacenter communication load. In Facebook, each datacenter has a full copy of all data, and the master datacenter updates all other datacenters, generating tremendous load in this new model. Distributed data storage, which only stores a user's data to his/her geographically closest datacenters mitigates the problem. However, frequent interactions between distant users lead to frequent inter-datacenter communication and hence long service latencies. In this paper, we aim to reduce inter-datacenter communications while still achieving low service latency. We first verify the benefits of the new model and present OSN typical properties that underlie the basis of our design. We then propose Selective Data replication mechanism in Distributed Datacenters ($SD^3$). Since replicas need inter-datacenter data updates, datacenters in$SD^3$jointly consider update rates and visit rates to select user data for replication; furthermore,$SD^3$atomizes users’ different types of data (e.g., status update, friend post, music) for replication, ensuring that a replica always reduces inter-datacenter communication.$SD^3$also incorporates three strategies to further enhance its performance: locality-aware multicast update tree, replica deactivation, and datacenter congestion control. The results of trace-driven experiments on the real-world PlanetLab testbed demonstrate the higher efficiency and effectiveness of$SD^3$in comparison to other replication methods and the effectiveness of its three schemes.

Content Delivery Networks (CDNs) play a central role in today's Internet infrastructure and have seen a sharp increase in scale. More and more internet sites are armed with live contents, such as live sports game statistics, e-commerce, and online auctions, and they rely on CDNs to deliver such contents freshly at scale. However, the problem of maintaining consistency for live (dynamic) contents while achieving high scalability is non-trivial in CDNs. The large number of widely scattered replicas guarantees the QoS of end-users while substantially increasing the complexity of consistency maintenance under frequent updates. Current consistency maintenance infrastructures and methods cannot simultaneously satisfy both scalability and consistency. In this paper, we first analyze our crawled trace data of cached sports game content on thousands of content servers of a major CDN. We analyze the content consistency from different perspectives, from which we break down the reasons for inconsistency among content servers. We verify that the CDN uses unicast instead of multicast trees as the update infrastructure, which may not scale effectively. Then, we further evaluate the performance in consistency, scalability and overhead for different infrastructures with different update methods. We itemize the advantages and disadvantages of different methods and infrastructures in different scenarios through the evaluation. Based on this evaluation, we propose our hybrid and self-adaptive update method to reduce network load and improve scalability under the conditions recorded in the trace and prove its effectiveness through trace-driven experiments. We aim to give guidance for appropriate selections of consistency maintenance infrastructures and methods for a CDN, and for choosing a CDN service with different considerations.

It is imperative for cloud storage systems to be able to provide deadline guaranteed services according to service level agreements (SLAs) for online services. In spite of many previous works on deadline aware solutions, most of them focus on scheduling work flows or resource reservation in datacenter networks but neglect the server overload problem in cloud storage systems that prevents providing the deadline guaranteed services. In this paper, we introduce a new form of SLAs, which enables each tenant to specify a percentage of its requests it wishes to serve within a specified deadline. We first identify the multiple objectives (i.e., traffic and latency minimization, resource utilization maximization) in developing schemes to satisfy the SLAs. To satisfy the SLAs while achieving the multi-objectives, we propose a Parallel Deadline Guaranteed (PDG) scheme, which schedules data reallocation (through load re-assignment and data replication) using a tree-based bottom-up parallel process. The observation from our model also motivates our deadline strictness clustered data allocation algorithm that maps tenants with the similar SLA strictness into the same server to enhance SLA guarantees. We further enhance PDG in supplying SLA guaranteed services through two algorithms: i) a prioritized data reallocation algorithm that deals with request arrival rate variation, and ii) an adaptive request retransmission algorithm that deals with SLA requirement variation. Our trace-driven experiments on a simulator and Amazon EC2 show the effectiveness of our schemes for guaranteeing the SLAs while achieving the multi-objectives.

In many countries, the Internet is under stringent censorship for political or religious reasons which severely undermines the free flow of information. A censorship-resistant web browsing system must be scalable, blocking resistant, and tracing resistant. However, current censorship-resistant web browsing systems, which use a group of dedicated proxies to bypass censorship, fail to meet these requirements. To tackle these challenges, we propose Freeweb, which relies on widely-distributed peer-to-peer (P2P) nodes in a decentralized manner rather than specified proxies in a centralized manner. We also proposed enhancement methods to reduce file access delay and avoid node overloads in Freeweb. Freeweb is built on top of a Distributed Hash Table (DHT)-based P2P network, where nodes not under censorship help nodes under censorship to access blocked webpages. Freeweb has a web browser front-end whose user interface resembles existing web browsers. The underlying complex process of retrieving blocked webpages is therefore hidden from users. We implemented an open-sourced Freeweb and conducted extensive real-world experiments on PlanetLab. The experimental results show that Freeweb has a high success rate and reasonable browsing latency, and its enhancement reduces much network load and file access latency, and avoids node overloads.

In large-scale computing clusters, when the server storing a task's input data does not have sufficient computing capacity, current job schedulers either schedule the task and transmit the input data to the closest server or let the task wait until the server has sufficient computing capacity, which generates network load or task delay. To handle this problem, load balancing methods are needed to reduce the number of overloaded servers due to computing workloads. However, current load balancing methods either do not consider the computing workload or assume that it is proportional to the number of data blocks in a server. Through trace analysis, we demonstrate the diversity of computing workloads of different tasks and the necessity of balancing the computing workloads among servers. Then, we propose a cost-efficient Computing load Aware and Long-View load balancing approach (CALV). In addition to the computing load awareness, CALV is also novel in that it achieves long-term load balance by migrating out data blocks from an overloaded server that contribute more computing workloads when the server is more overloaded and contribute less computing workloads when the server is more underloaded at different epochs during a time period. CALV also has a lazy data block transmission method to improve the load balanced state and avoid network load peak. Trace-driven experiments in simulation and a real computing cluster show that CALV outperforms other methods in terms of balancing the computing workloads and cost efficiency.

Question and Answer (Q&A) systems play a vital role in our daily life for information and knowledge sharing. Users post questions and pick questions to answer in the system. Due to the rapidly growing user population and the number of questions, it is unlikely for a user to stumble upon a question by chance that (s)he can answer. Also, altruism does not encourage all users to provide answers, not to mention high quality answers with a short answer wait time. The primary objective of this paper is to improve the performance of Q&A systems by actively forwarding questions to users who are capable and willing to answer the questions. To this end, we have designed and implemented SocialQ&A, an online social network based Q&A system. SocialQ&A leverages the social network properties of common-interest and mutual-trust friend relationship to identify an asker's friends who are most likely to answer the question. We describe the architecture, algorithms and user interface of SocialQ&A, and analyze the Q&A behavior of real users and questions from a small-scale real-world SocialQ&A system. We also conducted comprehensive large-scale simulation to evaluate SocialQ&A in comparison with other methods. Our results suggest that social networks can be leveraged to improve the answer quality and asker's waiting time.

It is critical for a cloud service broker to minimize its payment cost to cloud service providers for serving the broker's customers while providing SLA-guaranteed services. In this paper, we propose an Economical and SLA-guaranteed cloud Storage Service (ES3), which finds a data allocation and resource reservation schedule with cost minimization. ES3 incorporates (1) a data allocation and reservation algorithm, which allocates each data item to a datacenter and determines the reservation amount on data centers by leveraging all the pricing policies, (2) a genetic algorithm based data allocation adjustment approach, which makes data Get/Put rates stable in each datacenter to maximize the reservation benefit. Our trace-driven experiments show the superior performance of ES3.

Current reputation systems for peer-to-peer (P2P) file sharing systems either fail to utilize existing trust within social networks or suffer from certain attacks (e.g., free-riding and collusion). To handle these problems, we introduce a trust management system, called SocialLink, that utilizes social network and historical transaction links. SocialLink manages file transactions through both the social network and a novel weighted transaction network, which is built based on previous file transaction history. First, SocialLink exploits the trust among friends in social networks by enabling two friends to share files directly. Second, the weighted transaction network is utilized to 1) deduce the trust of the client on a server in reliably providing the requested file and 2) check the fairness of the transaction. In this way, SocialLink prevents potential misbehaving transactions (i.e., providing faulty files), encourages nodes to contribute file resources to non-friends, and avoids free-riding. Furthermore, the weighted transaction network helps SocialLink resist whitewashing, collusion and Sybil attacks. Extensive simulation demonstrates that SocialLink can efficiently ensure trustable and fair P2P file sharing and resist the aforementioned attacks.

It is imperative for cloud storage systems to be able to provide deadline guaranteed services according to service level agreements (SLAs) for online services. However, there are no previous works that provide the deadline guarantee specifically for cloud storage systems. In this paper, we introduce a new form of SLAs, which enables each tenant to specify a percentage of its requests it wishes to serve within a specified deadline. We first identify the multiple objectives (i.e., traffic and latency minimization, resource utilization maximization) in developing schemes to satisfy the SLAs. To satisfy the SLAs while achieving the multi-objectives, we propose a Parallel Deadline Guaranteed (PDG) scheme, which schedules data reallocation (through load re-assignment and data replication) using a tree-based bottom-up parallel process. We also enhance PDG through a prioritized data reallocation algorithm, which enables highly overloaded servers to autonomously probe nearby servers and enables the load balancer to instantly handle them. Our trace-driven experiments on a simulator show the effectiveness of our schemes for guaranteeing the SLAs while achieving the multi-objectives.

Traditional Web-based Question and Answer (Q&A) Web sites cannot easily solve non-factual questions to match askers' preference. Recent research efforts begin to study social-based Q&A systems that rely on an asker's social friends to provide answers. However, this method cannot find answerers for a question not belonging to the asker's interests. To solve this problem, we propose a distributed Q&A system incorporating both social community intelligence and global collective intelligence, named as iASK. iASK improves the response latency and answer quality in both the social domain and global domain. It uses a neural network based friend ranking method to identify answerer candidates by considering social closeness and Q&A activities. To efficiently identify answerers in the global user base, iASK builds a virtual server tree that embeds the hierarchical structure of interests, and also maps users to the tree based on user interests. To accurately locate the cooperative experts, iASK has a fine-grained reputation system to evaluate user reputation based on their cooperativeness and expertise. Experimental results from large-scale trace-driven simulation and realworld daily usages of the iASK prototype show the superior performance of iASK. It achieves high answer quality with 24% higher accuracy, short response latency with 53% less delay and effective cooperative incentives with 16% more answers compared to other social-based Q&A systems.

Motivated by the growing popularity of mobile devices and their increasing capacities, file sharing in disruption tolerant networks (DTNs) has attracted significant attention recently. Since nodes are sparsely distributed in separated areas and are intermittently disconnected in DTNs, it is difficult to achieve high data availability in file sharing. Many previous methods enhance file availability in DTNs through file replication. However, there has been no file replication method that tries to reduce data loss in correlated node failures, which however are common in wireless networks. In this paper, we propose a distributed file replication method (called MobileCopy) in DTNs, which aims to achieve low probability of totally losing a file at the expense of having a high number of impacted files in an individual large-scale correlated node failure. MobileCopy is designed for community-based file sharing systems. It has two main components: i) data loss resistant and popularity aware file replication, and ii) distributed hash table (DHT)-based file replica indexing. MobileCopy considers file popularity to determine the number of replicas of a file in each community. Through limiting the possible combination of candidate replica holders, MobileCopy greatly reduces the probability of node failures that will lead to data loss, i.e., losing all replicas of a file. Moreover, MobileCopy enables nodes to efficiently store and fetch the placement information of file replicas for efficient file searching. Extensive trace-driven experiments show that MobileCopy is robust against correlated node failures and efficient in file sharing in comparison with previous methods.

Efficient and trustworthy file querying is important to the overall performance of peer-to-peer (P2P) file sharing systems. Emerging methods are beginning to address this challenge by exploiting online social networks (OSNs). However, current OSN-based methods simply cluster common-interest nodes for high efficiency or limit the interaction between social friends for high trustworthiness, which provides limited enhancement or contradicts the open and free service goal of P2P systems. Little research has been undertaken to fully and cooperatively leverage OSNs with integrated consideration of proximity and interest. In this work, we analyze a BitTorrent file sharing trace, which proves the necessity of proximity- and interest-aware clustering. Based on the trace study and OSN properties, we propose a social network integrated P2P file sharing system with enhanced efficiency and trustworthiness (SOCNET) to fully and cooperatively leverage the common-interest, proximity-close, and trust properties of OSN friends. SOCNET uses a hierarchical distributed hash table (DHT) to cluster common-interest nodes, then further cluster proximity-close nodes into a subcluster, and connects the nodes in a subcluster with social links. Thus, when queries travel along trustable social links, they also gain higher probability of being successfully resolved by proximity-close nodes, and it simultaneously enhances efficiency and trustworthiness. We further propose different strategies to guide nodes to forward a file query to friends that are more trustworthy and more likely to resolve the queries or forward the query to file holders. We also propose follower- and cluster-based file replication algorithms to enhance file search efficiency. The results of trace-driven experiments on the real-world PlanetLab testbed demonstrate the higher efficiency, trustworthiness, and dynamism-resilience of SOCNET compared with other systems. Experimental results also confirm the effectiveness of the proposed strategies to improve SOCNET’s performance.

In peer-to-peer file sharing systems, file replication helps to avoid overloading file owners and improve file query efficiency. There exists a tradeoff between minimizing the number of replicas (i.e., replication overhead) and maximizing the replica hit rate (which reduces file querying latency). More replicas lead to increased replication overhead and higher replica hit rates and vice versa. An ideal replication method should generate a low overhead burden to the system while providing low query latency to the users. However, previous replication methods either achieve high hit rates at the cost of many replicas or produce low hit rates. To reduce replicas while guaranteeing high hit rate, this paper presents SWARM, a file replication mechanism based on swarm intelligence. Recognizing the power of collective behaviors, SWARM identifies node swarms with common node interests and close proximity. Unlike most earlier methods, SWARM determines the placement of a file replica based on the accumulated query rates of nodes in a swarm rather than a single node. Replicas are shared by the nodes in a swarm, leading to fewer replicas and high querying efficiency. In addition, SWARM has a novel consistency maintenance algorithm that propagates an update message between proximity-close nodes in a tree fashion from the top to the bottom. Experimental results from the real-world PlanetLab testbed and the PeerSim simulator demonstrate the effectiveness of the SWARM mechanism in comparison with other file replication and consistency maintenance methods. SWARM can reduce querying latency by 40-58 percent, reduce the number of replicas by 39-76 percent, and achieves more than 84 percent higher hit rates compared to previous methods. It also can reduce the consistency maintenance overhead by 49-99 percent compared to previous consistency maintenance methods.

Current reputation systems for peer-to-peer (P2P) file sharing networks suffer from high overhead on reputation querying. Also, purely relying on a threshold to detect malicious nodes may make a high-reputed node be reluctant to further increase its reputation in these reputation systems. On the other side, the social network concept of “friendship foster cooperation” can be utilized to alleviate the high overhead in reputation systems. However, the limited number of friends limits the availability of file resources in these approaches. To overcome the drawbacks, we propose a social network based reputation system, namely SocialTrust, that synergistically leverages the social network connections and traditional credit based reputation system to provide efficient reputation management for P2P file sharing. In SocialTrust, each node favors friends for service transactions, which are resulted from both real life acquaintances and online partnerships established between high-reputed and frequently-interacted nodes. When no friends are available for a request, a node chooses the server with the highest reputation. The benefits of friendship and partnership on file sharing and cost saving encourage nodes to be continuously cooperative. Further, SocialTrust considers the number of friends/partners and the reputation of a node in reputation rewarding/punishment in order to realize accurate reputation evaluation. SocialTrust can also prevent certain attacks such as deny of service and collusion. Extensive trace-driven simulation demonstrates the effectiveness of SocialTrust.

Efficient file query is important to the overall performance of peer-to-peer (P2P) file sharing systems. Clustering peers by their common interests can significantly enhance the efficiency of file query. Clustering peers by their physical proximity can also improve file query performance. However, few current works are able to cluster peers based on both peer interest and physical proximity. Although structured P2Ps provide higher file query efficiency than unstructured P2Ps, it is difficult to realize it due to their strictly defined topologies. In this work, we introduce a Proximity-Aware and Interest-clustered P2P file sharing System (PAIS) based on a structured P2P, which forms physically-close nodes into a cluster and further groups physically-close and common-interest nodes into a sub-cluster based on a hierarchical topology. PAIS uses an intelligent file replication algorithm to further enhance file query efficiency. It creates replicas of files that are frequently requested by a group of physically close nodes in their location. Moreover, PAIS enhances the intra-sub-cluster file searching through several approaches. First, it further classifies the interest of a sub-cluster to a number of sub-interests, and clusters common-sub-interest nodes into a group for file sharing. Second, PAIS builds an overlay for each group that connects lower capacity nodes to higher capacity nodes for distributed file querying while avoiding node overload. Third, to reduce file searching delay, PAIS uses proactive file information collection so that a file requester can know if its requested file is in its nearby nodes. Fourth, to reduce the overhead of the file information collection, PAIS uses bloom filter based file information collection and corresponding distributed file searching. Fifth, to improve the file sharing efficiency, PAIS ranks the bloom filter results in order. Sixth, considering that a recently visited file tends to be visited again, the bloom filter based approach is enhanced by only checking the newly added bloom filter information to reduce file searching delay. Trace-driven experimental results from the real-world PlanetLab testbed demonstrate that PAIS dramatically reduces overhead and enhances the efficiency of file sharing with and without churn. Further, the experimental results show the high effectiveness of the intra-sub-cluster file searching approaches in improving file searching efficiency.

Content Delivery Networks (CDNs) play a central role of today's Internet infrastructure, and have seen a sharp increment in scale. More and more internet sites are armed with dynamic (or live) content (such as live sports game statistics, e-commerce and online auction), and there is a need to deliver dynamic content freshly in scale. To achieve high scalability, the consistency maintenance problem for dynamic content (contents with frequent updates) served by CDNs is non-trivial. The large number of widely scattered replicas guarantee the service QoS of end-users, meanwhile largely increase the complexity of consistency maintenance. Current consistency maintenance infrastructures and methods cannot simultaneously satisfy the two requirements: scalability and consistency. In this paper, we first analyze our crawled trace data of a cached sports game content on thousands of content servers of a major CDN. We analyze the content consistency from different perspectives, from which we try to break down the reasons for inconsistency among content servers. Finally, we further evaluate the performance in consistency, scalability and overhead for different infrastructures with different update methods. We itemize the advantages and disadvantages of different methods and infrastructures in different scenarios through the evaluation. We aim to give guidance for appropriate selections of consistency maintenance infrastructures and methods for a CDN, and for choosing a CDN service with different considerations.

Advancements in cloud computing are leading to a promising future for collaborative cloud computing (CCC), where globally-scattered distributed cloud resources belonging to different organizations or individuals (i.e., entities) are collectively used in a cooperative manner to provide services. Due to the autonomous features of entities in CCC, the issues of resource management and reputation management must be jointly addressed in order to ensure the successful deployment of CCC. However, these two issues have typically been addressed separately in previous research efforts, and simply combining the two systems generates double overhead. Also, previous resource and reputation management methods are not sufficiently efficient or effective. By providing a single reputation value for each node, the methods cannot reflect the reputation of a node in providing individual types of resources. By always selecting the highest-reputed nodes, the methods fail to exploit node reputation in resource selection to fully and fairly utilize resources in the system and to meet users' diverse QoS demands. We propose a CCC platform, called Harmony, which integrates resource management and reputation management in a harmonious manner. Harmony incorporates three key innovations: integrated multi-faceted resource/reputation management, multi-QoS-oriented resource selection, and price-assisted resource/reputation control. The trace data we collected from an online trading platform implies the importance of multi-faceted reputation and the drawbacks of highest-reputed node selection. Simulations and trace-driven experiments on the real-world PlanetLab testbed show that Harmony outperforms existing resource management and reputation management systems in terms of QoS, efficiency and effectiveness.

Tremendous advances in pervasive networking have enabled wide-area distributed systems to connect distributed resources or users such as corporate data centers and high-performance computing centers. These distributed pervasive systems take advantage of resources and enhance collaborations worldwide. However, due to lack of central management, they are severely threatened by a variety of malicious users in today's Internet. Current reputation- and anonymity-based technologies for node communication enhance system trustworthiness. However, most of these technologies gain trustworthiness at the cost of efficiency degradation. This paper presents a P2P-based infrastructure for trustworthy and efficient node communication in wide-area distributed systems. It jointly addresses trustworthiness and efficiency in its operation in order to meet the high-performance requirements of a diversified wealth of distributed pervasive applications. The infrastructure includes two policies: trust/efficiency-oriented request routing and trust-based adaptive anonymous response forwarding. This infrastructure not only offers a trustworthy environment with anonymous communication but also enhances overall system efficiency through harmonious trustworthiness and efficiency trade-offs. Experimental results from simulations and the real-world PlanetLab testbed show the superior performance of the P2P-based infrastructure in achieving both high trustworthiness and high efficiency in comparison to other related approaches.

Recently, emerging research efforts have been focused on question and answer (Q&A) systems based on social networks. The social-based Q&A systems can answer non-factual questions, which cannot be easily resolved by web search engines. These systems either rely on a centralized server for identifying friends based on social information or broadcast a user's questions to all of its friends. Mobile Q&A systems, where mobile nodes access the Q&A systems through Internet, are very promising considering the rapid increase of mobile users and the convenience of practical use. However, such systems cannot directly use the previous centralized methods or broadcasting methods, which generate high cost of mobile Internet access, node overload, and high server bandwidth cost with the tremendous number of mobile users. We propose a distributed Social-based mObile Q&A System (SOS) with low overhead and system cost as well as quick response to question askers. SOS enables mobile users to forward questions to potential answerers in their friend lists in a decentralized manner for a number of hops before resorting to the server. It leverages lightweight knowledge engineering techniques to accurately identify friends who are able to and willing to answer questions, thus reducing the search and computation costs of mobile nodes. The trace-driven simulation results show that SOS can achieve a high query precision and recall rate, a short response latency and low overhead. We have also deployed a pilot version of SOS for use in a small group in Clemson University. The feedback from the users shows that SOS can provide high-quality answers.

In current reputation systems for peer-to-peer (P2P) file sharing networks, reputation querying generates high overhead in file service. Also, a high-reputed node may be reluctant to further increase its reputation in these reputation systems. Recently, social network-based P2P systems that favor file sharing among friends have been proposed for reliable file sharing. However, this approach contradicts the objective of widely file sharing in P2P systems. To overcome these drawbacks, we propose a social network integrated reputation system, namely SocialTrust, that synergistically leverages the concept of "friendship fosters cooperation''. In SocialTrust, each node maintains trusted relationships for the purpose of file sharing, which are resulted from both real life acquaintance and online partnership established between high-reputed and frequently-interacted nodes. Given a number of server options, a client first chooses a friend or a partner, if available, without querying their reputations. Otherwise, it chooses the server with the highest reputation. The benefits of friendship and partnership on file sharing and cost saving encourage nodes to be continuously cooperative. Further, in order to realize accurate reputation evaluation and strong cooperation incentives, SocialTrust considers the number of friends/partners and reputation of a node in the process of reputation rewarding and punishment. Extensive trace-driven simulation demonstrates the effectiveness of SocialTrust.

Though the new OSN model with many worldwide distributed small datacenters helps reduce service latency, it brings a problem of higher inter-datacenter communication load. In Facebook, each datacenter has a full copy of all data and the master datacenter updates all other datacenters, which obviously generates tremendous load in this new model. Distributed data storage that only stores a user's data to his/her geographically-closest datacenters mitigates the problem. However, frequent interactions between far-away users lead to frequent inter-datacenter communication and hence long service latency. In this paper, we aim to reduce inter-datacenter communications while still achieve low service latency. We first verify the benefits of the new model and present OSN typical properties that lay the basis of our design. We then propose Selective Data replication mechanism in Distributed Datacenters (SD3). In SD3, a datacenter jointly considers update rate and visit rate to select user data for replication, and further atomizes a user's different types of data (e.g., status update, friend post) for replication, making sure that a replica always reduces inter-datacenter communication. The results of trace-driven experiments on the real-world PlanetLab testbed demonstrate the higher efficiency and effectiveness of SD3in comparison to other replication methods.

File replication is widely used in structured P2P systems to avoid hot spots in servers and enhance file availability. The number of replicas and replication distance affect the file replication cost. These two elements and the replica update frequency determined in the file replication stage also affect the cost of subsequent consistency maintenance. However, most existing file replication protocols focus on improving file lookup efficiency without considering its cost and its subsequent influence on consistency maintenance. This paper studies the problem about how a server chooses files to replicate and where to replicate files to achieve low cost in both file replication and consistency maintenance stages without compromising the effectiveness of file replication. This paper presents a lightweight and Cooperative multifactOr considered file Replication Protocol (CORP) to achieve this goal. CORP simultaneously takes into account multiple factors including file popularity, update rate, node available capacity, file load, and node locality, aiming to minimize the number of replicas, update frequency, and replication distance. CORP also dynamically adjusts the number of replicas based on ever-changing file popularity and visit pattern. Extensive experimental results from simulation and PlanetLab real-world testbed demonstrate the efficiency and effectiveness of CORP in comparison with other file replication protocols. It dramatically reduces the overhead of both file replication and consistency maintenance. In addition, it exhibits high adaptiveness to skewed lookups and yields significant improvement in reducing overloaded nodes. Specifically, compared to the other replication protocols, CORP can reduce more than 71 percent of file replicas, 84 percent of overloaded nodes, 94 percent of consistency maintenance cost, and 72 percent of file replication and consistency maintenance latency.

File consistency maintenance in P2P systems is a technique for maintaining consistency between files and their replicas. Most previous consistency maintenance methods depend on either message spreading or structure-based pushing. Message spreading generates high overhead due to a large amount of messages; structure-based pushing methods reduce this overhead. However, both approaches cannot guarantee that every replica node receives an update in churn, because replica nodes passively wait for updates. As opposed to push-based methods that are not effective in high-churn and low-resource P2P systems, polling is churn resilient and generates low overhead. However, it is faced with a number of challenges: 1) ensuring a limited inconsistency; 2) realizing polling in a distributed manner; 3) considering physical proximity in polling; and 4) leveraging polling to further reduce polling overhead. To handle these challenges, this paper introduces a poll-based distributed file consistency maintenance method called geographically aware wave (GeWave). GeWave further reduces update overhead, enhances the fidelity of file consistency, and takes proximity into account. Using adaptive polling in a dynamic structure, GeWave avoids redundant file updates and ensures that every node receives an update in a limited time period even in churn. Furthermore, it propagates updates between geographically close nodes in a distributed manner. Extensive experimental results from the PlanetLab real-world testbed demonstrate the efficiency and effectiveness of GeWave in comparison with other representative consistency maintenance schemes. It dramatically reduces the overhead and yields significant improvements on effectiveness, scalability, and churn resilience of previous file consistency maintenance methods.

Video sharing has been an increasingly popular application in online social networks (OSNs). However, its sustainable development is severely hindered by the intrinsic limit of the client/server architecture deployed in current OSN video systems, which is not only costly in terms of server bandwidth and storage but also not scalable. The peer-assisted Video-on-Demand (VOD) technique, in which participating peers assist the server in delivering video content has been proposed recently. Unfortunately, videos can only be disseminated through friends in OSNs. Therefore, current VOD works that explore clustering nodes with similar interests or close location for high performance are suboptimal, if not entirely inapplicable, in OSNs. Based on our long-term real-world measurement of over 1,000,000 users and 2,500 videos in Facebook, we propose SocialTube, a novel peer-assisted video sharing system that explores social relationship, interest similarity, and physical location between peers in OSNs. Specifically, SocialTube incorporates three algorithms: a social network (SN)-based P2P overlay construction algorithm, a SN-based chunk prefetch algorithm, and a buffer management algorithm. The trace driven based simulation results show that SocialTube can improve the quality of user experience and system scalability over current P2P VOD techniques.

Efficient and trustworthy file querying is important to the overall performance of peer-to-peer (P2P) file sharing systems. Emerging methods are beginning to address this challenge by exploiting online social networks (OSNs). However, current OSN-based methods simply cluster common-interest nodes for high efficiency or limit the interaction between social friends for high trustworthiness, which provides limited enhancement or contradicts the open and free service goal of P2P systems. Little research has been undertaken to fully and cooperatively leverage OSNs with integrated consideration of proximity and interest. In this work, we analyze a BitTorrent file sharing trace, which proves the necessity of proximityand interest-aware clustering. Based on the trace study and OSN properties, we propose a SOcial Network integrated P2P file sharing system with enhanced Efficiency and Trustworthiness (SoNet) to fully and cooperatively leverage the common-interest, proximity-close and trust properties of OSN friends. SoNet uses a hierarchical distributed hash table (DHT) to cluster common-interest nodes, then further cluster proximity-close nodes into subcluster, and connects the nodes in a subcluster with social links. Thus, when queries travel along trustable social links, they also gain higher probability of being successfully resolved by proximityclose nodes, simultaneously enhancing efficiency and trustworthiness. The results of trace-driven experiments on the realworld PlanetLab testbed demonstrate the higher efficiency and trustworthiness of SoNet compared with other systems.

Advancements in technology over the past decade are leading to a promising future for large-scale distributed systems, where globally-scattered distributed resources are collectively pooled and used in a cooperative manner to achieve unprecedented petascale supercomputing capabilities. The issues of resource management (resMgt) and reputation management (repMgt) need to be addressed in order to ensure the successful deployment of large-scale distributed systems. However, these two issues have typically been addressed separately, despite the significant interdependencies between them: resMgt needs repMgt to provide a cooperative environment for resource sharing, and in turn facilitates repMgt to evaluate multi-faceted node reputations for providing different resources. Current repMgt methods provide a single reputation value for each node in providing all types of resources. However, a node willing to provide one resource may not be willing to provide another resource. In addition, current repMgt methods often guide node selection policy to select the highest-reputed nodes, which may overload these nodes. Also, few works exploited node reputation in resource selection in order to fully and fairly utilize resources in the system and to meet users' diverse QoS demands. We propose a system called Harmony that integrates resMgt and repMgt in a harmonious manner. Harmony incorporates two key innovations: integrated multi-faceted resource/reputation management and multi-QoS-oriented resource selection. The trace data we collected from an online trading platform confirms the importance of multi-faceted reputation and potential problems with highest-reputed node selection. Trace-driven experiments performed on PlanetLab show that Harmony outperforms existing resMgt and repMgt in terms of the success rate, service delay, and efficiency.