Search

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 ). CALV is 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 CALV is 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. [ABSTRACT FROM AUTHOR]

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 (SD3). Since replicas need inter-datacenter data updates, datacenters in SD3 jointly consider update rates and visit rates to select user data for replication; furthermore, SD3 atomizes users’ different types of data (e.g., status update, friend post, music) for replication, ensuring that a replica always reduces inter-datacenter communication. SD3 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 SD3 in comparison to other replication methods and the effectiveness of its three schemes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A large-scale resource sharing system (e.g., collaborative cloud computing and grid computing) creates a virtual supercomputer by providing an infrastructure for sharing tremendous amounts of resources (e.g., computing, storage, and data) distributed over the Internet. A resource information service, which collects resource data and provides resource search functionality for locating desired resources, is a crucial component of the resource sharing system. In addition to resource discovery speed and cost (i.e., efficiency), the ability to accurately locate all satisfying resources (i.e., fidelity) is also an important metric for evaluating service quality. Previously, a number of resource information service systems have been proposed based on Distributed Hash Tables (DHTs) that offer scalable key-based lookup functions. However, these systems either achieve high fidelity at low efficiency, or high efficiency at low fidelity. Moreover, some systems have limited flexibility by only providing exact-matching services or by describing a resource using a pre-defined list of attributes. This paper presents a resource information service that offers high efficiency and fidelity without restricting resource expressiveness, while also providing a similar-matching service. Extensive simulation and PlanetLab experimental results show that the proposed service outperforms other services in terms of efficiency, fidelity, and flexibility; it dramatically reduces overhead and yields significant enhancements in efficiency and fidelity. [ABSTRACT FROM AUTHOR]

Advances in ubiquitous sensing, computing and wireless communication technologies are leading to the development of cyber-physical systems (CPS), which promise to revolutionize the way we interact with the physical world. CPS applications, such as healthcare monitoring, may involve many users and objects scattered over a wide area. One critical function of CPS is object search in the physical world through the cyber sphere that enables interaction between the cyber and physical spheres. Some of the previously proposed physical object search engines use RFID tracking, and others collect the information of object locations into a hierarchical centralized server. The difficulty of widely deploying RFID devices, the centralized search, and the need for periodical location information collection prevent CPS from achieving higher scalability and efficiency. To deal with this problem, we propose a Social-aware distributed Cyber-Physical human-centric Search engine (SCPS) that leverages the social network formed by wireless device users for object search. Without requiring periodical location information collection, SCPS locates objects held by users based on the routine user movement pattern. Moreover, using a social-aware Bayesian network, it can accurately predict the users’ locations even at the occurrence of exceptional (i.e., non-routine) events (e.g., raining) that break user movement pattern. Thus, SCPS is more advantageous than all previous social network based works which assume that user behaviors always follow a certain pattern. Further, SCPS conducts the search in a fully distributed manner by relying on a distributed hash table (DHT) structure. As a result, SCPS achieves high scalability, efficiency and location accuracy. Extensive real-trace driven simulation results show the superior performance of SCPS compared to other representative search methods including a hierarchical centralized method, a decentralized method, and two social network based methods. The results also show the effectiveness of different components of SCPS. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 with the soaring amount of users and video content. 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 on 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 four algorithms: a social network (SN)-based P2P overlay construction algorithm, an SN-based chunk prefetching algorithm, chunk delivery, and scheduling algorithm, and a buffer management algorithm. Experimental results from a prototype on PlanetLab and an event-driven simulator show that SocialTube can improve the quality of user experience and system scalability over current P2P VoD techniques. [ABSTRACT FROM PUBLISHER]

This paper addresses the data search problem in large-scale highly mobile and dense wireless networks. Current wireless network data search systems are not suitable for large-scale highly mobile and dense wireless networks. This paper presents a scalable and mobility-resilient LOcality-based distRibuted Data search system (LORD) for large-scale wireless networks with high mobility and density. Taking advantage of the high density, rather than mapping data to a location point, LORD maps file metadata to a geographical region and stores it in multiple nodes in the region, thus enhancing mobility-resilience. LORD has a novel region-based geographic data routing protocol that does not rely on flooding or GPSs for data publishing and querying, and a coloring-based partial replication algorithm to reduce data replicas in a region while maintaining the querying efficiency. LORD also works for unbalanced wireless networks with sparse regions. Simulation results show the superior performance of LORD compared to representative data search systems in terms of scalability, overhead, and mobility resilience in a highly dense and mobile network. The results also show the high scalability and mobility-resilience of LORD in an unbalanced wireless network with sparse regions, and the effectiveness of its coloring-based partial replication algorithm. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]